12
Einführung in den Algorithmenentwurf (Subject) / Codebäume (Lesson)
Advertisement
- Alphabet Endliche, nicht leere Menge
- Wort Endliche Sequenz von Werten aus Alphabet
- Bitsequenz Wort über dem Alphabet {0, 1}
- Kompressionsfaktor (Komprimiert(Größe))/(Unkomprimiert(Größe))
- Kompressionsrate (Unkomprimiert(Größe))/(Komprimiert(Größe))
- Code fester Länge Codierung "code" von Alphabet, sodass ein "I" existiert mit "Betrag von(code(x)=I)" für alle Zeichen x aus AlphabetProblem: Meist ungeeignet/ineffizient
- Code variabler Länge Besser als Code fester Länge, wenn sich die Häufigkeiten der Zeichen in Alphabet unterscheidenProblem: Eindeutige Decodierung
- Codierung mit Codebäumen Gehe Weg von Wurzel zum Blatt, notiere für jede Kante ein Bit
- Decodierung mit Codebäumen Beginne in der Wurzel. Laufe Bitsequenz bitweise ab
- Länge des Codes Gesamtanzahl der Besuche an inneren Knoten beim Codieren
- Advertisement
- Knotengewichte Gibt an wie oft der Knoten durchlaufen wirdBlätter haben die Häufigkeit ihres Buchstabens als GewichtInnere Knoten erhalten die Summe ihre Kinder als Gewicht
- Huffman-Coding Ziel: Codebaum mit minimalen Gesamtgewicht zu konstruierenPrinzip: Bottom-Up Bäume mit geringsten Gewicht werden zuerst vereinigt Wiederhole bis nur noch ein Baum übrig ist