5
PI (Fach) / Huffman-Kodierung (Lektion)
Huffman
Diese Lektion wurde von blace erstellt.
Diese Lektion ist leider nicht zum lernen freigegeben.
- Was ist die Huffman-Kodierung und wofür kann sie verwendet werden? Die Huffman Kodierung ist die Kodierung von zeichen(ketten) mit dem Ansatz, dass manche Zeichen öfter verwendet werden als andere, sodass man diesen weniger Bits zuordnet um Platz zu sparen.
- Was muss gegeben sein, damit Kodierung nach dem Huffman-Verfahren tatsächlich zu Platzersparnis (im Vergleich zur Kodierung mit fester Bitlänge) führt? Die Zeichen müssen nach häufigkeit sortiert sein
- Implementiere die Bestimmung der Zeichenhäufigkeiten einer Zeichenkette in Java. public class Frequency { private static int[] freq; public static void countFrequency(final String s) { freq = new int[65536]; for (int i = 0; i < s.length(); i++) { freq[s.charAt(i)]++; } printFreq(); } private static void printFreq() { for (int i=0; i < freq.length; i++) { if (freq[i] > 0) { System.out.println(String.format("%c:%d", i, freq[i])); } }}
- Implementiere die Bestimmung der Zeichenhäufigkeiten einer Zeichenkette in Java. public class Frequency {private static int[] freq;public static void countFrequency(final String s) {freq = new int[65536];for (int i = 0; i < s.length(); i++) {freq[s.charAt(i)]++;}printFreq();}private static void printFreq() {for (int i=0; i < freq.length; i++) {if (freq[i] > 0) {System.out.println(String.format("%c:%d", i, freq[i]));}}}
- Wie sieht ein Huffman-Baum aus und wie wird dieser konstruiert? Zuerst die Zeichen in der Zeichenkette nach Häufigkeit, sodass jedes Zeichen seine Häufigkeit bei sich stehen hat. Dann nimmt man immer jeweils die zwei Elemente mit der geringsten Häufigkeit und erstellt eine Wurzel, dessen Nachfolger diese Elemente sind, mit der Summe der Häufigkeiten als Häufigkeit, dies führt man fort bis alle Elemente in dem Baum vorhanden sind und die Wurzel gibt dann die Anzahl aller Zeichen in der Zeichen kette an Bsp. Aaron 1 1 1 2 n o r a 5 3 2 2 1 a 1 1 r n o
Anzeige