Verlustfreie Komprimierung
Es gehen keinerlei Daten verloren. Die Originaldaten können exakt wiederhergestellt werden. Man spricht von Redundanzreduktion.
Verlustbehaftete Komprimierung
Irrelevante Informationen werden entfernt, man spricht von Irrelevanzreduktion. Ein Teil der Daten geht verloren.
RLE-Verfahren
Es werden die Läufe gezählt und dan aufgeschrieben. Es handelt sich um eine verlustfreie Kompression. Das Verfahren eignet sich vorallem für Bilder mit kleiner Farbpalette. Eignet sich nicht gut für Texte, da dort meist keine Symbole mehrfach hintereinander auftreten.
AAAABBBCCCCDEEEEE —> 4A 3B 4C 1D 5E
Huffman
Das Huffman-Verfahren ist Präfixfrei und Längenvariabel
- Erstelle für jedes Zeichen einen Knoten, der mit der Häufigkeit des Zeichen markiert ist
- Solange es mehr als einen Knoten gibt, zu dem keine Kante hinführt:
- Suche zwei Knoten u und v mit minimaler Makierung p(u) bzw. p(v), zu denen noch keine Kante hinführt
- erzeuge einen neuen Knoten w und verbinde w mit u und v; markiere den Knoten w mit p(u) + p(v)
- Markiere die Kanten der inneren Knoten zu ihren Nachfolgern mit 0 und 1
Mittlere Codewortlänge
Es kann unterschiedliche Bäume geben, um herauszufinden, welcher der beste ist, berechnet man die Mittlere Codewortlänge:
Beispiel bei 11 Buchstaben (Tabelle erstellt aus dem Huffman Baum)
| A | 5 | 5 / 11 | 0 |
| B | 2 | 2 / 11 | 110 |
| C | 1 | 1 / 11 | 101 |
| D | 1 | 1 / 11 | 100 |
| E | 2 | 2 / 11 | 111 |
5/11*1 + 2/11*3 + 1/11*3 + 1/11*3 + 2/11*3 = 23/11 = 2,09
Speicherersparnis
z.B.: Es sind 11 Buchstaben zu codieren, mit einer Mittleren Codewortlänge von 2,09 = 23 Bits
Im Vergleich zu 8 Bit = 88 Bit
7 Bit 77 Bit
Präfixcode
Ein Präfixcode ist ein Code, bei dem kein Codewort ein Präfix eines anderen Codeworts ist. Also kein Codewort taucht am Anfang eines anderen auf, dies wird als Fano-Bedingung bezeichnet.
Längenvariabel bedeutet das Codewörter unterschiedliche Längen haben können
Bisher keine Kommentare