01
Informatik 1
12 – Use Case: Huffman-Trees
Winter 2020/21
Torsten Grust
Universität Tübingen, Germany
1 ┆ Zeichencodierungen
02
Zeichencodierungen bilden Zeichen auf Sequenzen von Bits ab. Die meisten dieser Codes nutzen eine fixe Anzahl von Bits:
Code
Details
ASCII
ISO-8859-1
Unicode
Codes 0-127, 7 Bit,
American Standard Code for Information Interchange
Codes 0-255, 8 Bit, 191 lateinische + Steuerzeichen
20 Bit, Unicode 13.0 codiert 143859 Zeichen
aktueller/historischer Scripts oder “Alphabete”
Beispiel: Zeichen € ≡ 0000 0010 0000 1010 1100 020ac
; Zeichen “€” in Unicode-Codierung
(: euro-symbol string)
(define euro-symbol )
“\U020ac”
Huffman-Codes nutzen Bitsequenzen variabler Länge.
Idee: Zeichen mit hoher Frequenz werden mit weniger Bits codiert, als seltene Zeichen ⇒ Datenkompression. Einsatz in JPEG, MP3 und ZIP.
Huffman-Codes sind Binärbäume, deren Blätter Labels tragen. Beispiel: Huffman-Code für “erdbeermarmelade”:1
┌─────┐ –
03
Huffman-Codes
┌─┐ ┌──┐
r ┌┐ ┌─┐ e
d m ┌┐ a
höher
│ Zeichenfrequenz
niedriger bl/
1 Dieser Huffman-Code kann Texte codieren, die (nur) die Zeichen a,b,d,e,l,m und r enthalten.
Huffman-Codes ≡ Pfade im Huffman-tree
04
Pfade im Huffman-Tree codieren die vorhandenen Zeichen:
┌─────┐
┌─┐ ┌──┐
r ┌┐ ┌─┐ e
d m ┌┐ a b l
Code für Zeichen 0:
1234 von Wurzel bis Blatt mit Label 0:
⭘ Abstieg in linken Teilbaum ≡ Bit 0
⭘ Abstieg in rechten Teilbaum ≡ Bit 1
Zeichencodes im Huffman-Tree für “erdbeermarmelade”:
Zeichen
Frequenz
Code (Bits)
e r m a d b l
5 3 2 2 2 1 1
11
00
011
101
010
1000
1001
Huffman-Codes sind präfixfrei
05
┌─────┐
┌─┐ ┌──┐
r ┌┐ ┌─┐ e
dm┌┐a bl
e ≡ 11 d ≡ 010 r ≡ 00 b ≡ 1000 m ≡ 011 l ≡ 1001 a ≡ 101
Huffman-Codes sind präfixfrei: die Bits eines Zeichens (= Blatt) sind niemals ein Präfix eines anderen Zeichens.
Ermöglicht die eindeutige Decodierung von Bitsequenzen (⇡ ≡ navigiere von der Wurzel des Huffman-Trees aus):
⇡1001⇡101⇡011⇡1000⇡010⇡101
l a m b d a
Länge: 20 Bit (Unicode hätte 120 Bit benötigt).
06
2 ┆ Racket: Huffman-Trees (1)
; Ein Blatt eines Huffman-Tree (huff-leaf) ╷
; – trägt ein Label (Zeichen #): #
(: make-huff-leaf (%a -> (huff-leaf-of %a)))
(: huff-leaf-label ((huff-leaf-of %a) -> %a)) (define-record-procedures-parametric huff-leaf huff-leaf-of
make-huff-leaf
huff-leaf?
(huff-leaf-label))
; Ein innerer Knoten eines Huffman-Tree (huff-node) besitzt ; – einen linken Teilbaum (left) und
; – einen rechten Teibaum (right): ┌──┐ (: make-huff-node (%a %b -> (huff-node-of %a %b)))
(: huff-node-left ((huff-node-of %a %b) -> %a))
(: huff-node-right ((huff-node-of %a %b) -> %b)) (define-record-procedures-parametric huff-node huff-node-of
make-huff-node
huff-node?
(huff-node-left huff-node-right))
Huffman-Trees sind eine Variante von Binärbäumen:
07
Racket: Huffman-Trees (2)
; Signatur (huff-tree-of (): Huffman-Tree mit Blättern ; mit Labeln der Signatur (
(define huff-tree-of ◀╌╌╌╌╌╌╌╌╌╌╌┬╌╌╌╌╌╌╌╌╌╌╌╌╌╌╮
(lambda (=) ┆ ┆ (signature ┆ ┆ (mixed (huff-leaf-of =) ▼ ▼
(huff-node-of (huff-tree-of =) (huff-tree-of =))
))))
Huffman-codierte Zeichen ≡ Bit-Sequenzen (list-of bit):
; Ein Bit eines Zeichencodes
(define bit
(signature (one-of 0 1))) ; oder (“L”,”R”), (“)”,”*”), …
3 ┆ Ein einfaches API für Huffman-Codierung
2. Codieren eines Strings:
┌────── = ──────┐
∀ string A: (huff-decode B= (huff-encode B= A)) = A
3. Huffman-Tree für gegebenen (Referenz-)Text konstruieren:
(: huffman-code (string -> (huff-tree-of string)))
08
1. Decodieren einer Bit-Sequenz:
(: huff-decode
((huff-tree-of string) (list-of bit) -> string))
(: huff-encode
((huff-tree-of string) string -> (list-of bit)))
4 ┆ API: Decodieren einer Bit-Sequenz (Erste Planskizze)
Ein erster Plan für einen Worker dec für huff-decode:
(: dec (huff-tree-of %a) (list-of bit) -> (list-of %a)))
╷
(dec 0 EF=A) = (make-pair 0 ??)
(dec ⟁ empty) = empty
0 (dec ┌──┐ (make-pair L EF=A)) = (dec M⟁ EF=A) M⟁ ⟁N
1 (dec ┌──┐ (make-pair P EF=A)) = (dec ⟁N EF=A) M⟁ ⟁N
Fall /??: Im Huffman-Tree bis zum Blatt mit Label 0 navigiert. Wiedereinsteig an der Wurzel (s. ⇡, Folie 5)?
09
API: Decodieren einer Bit-Sequenz (Fertiger Plan)
10
Idee: Schleife die Wurzel des Huffman-Tree B=⟁ durch die Rekursion. Wiedereinstieg an der Wurzel (⇡) ist nun einfach:
╷
(decB=⟁ 0 EF=A)=(make-pair0(decB=⟁B=⟁EF=A))
⇡ (dec B=⟁ ⟁ empty) = empty
0 (dec B=⟁ ┌──┐ (make-pair L EF=A)) = (dec B=⟁ M⟁ EF=A) M⟁ ⟁N
1 (dec B=⟁ ┌──┐ (make-pair P EF=A)) = (dec B=⟁ ⟁N EF=A) M⟁ ⟁N
Quiz: Ein endrekursives dec ist einfach zu erhalten. Wie?
5 ┆ API: Codieren eines Strings # (Plan A)
11
1. Codiere ein einzelnes Zeichen %:
Suche 0 via Tiefensuche von der Wurzel von B= aus. Protokolliere den Pfad beim Abstieg als Bit-Sequenz. Q: Wie reagieren wir, wenn uns die Tiefensuche zu einem Blatt mit Label Q ≠ 0 führt?
: Verfolge in jedem inneren Knoten ┌──┐ Teilbäume M⟁ und ⟁N. Suche schlägt entweder in M⟁ oder ⟁N fehl. Liefere leere Bit-Sequenz bei Fehlschlag ⭍. Beachte:
∀ QA: (append empty QA) = QA = (append QA empty)
2. Codiere Zeichen des Strings # wie in Schritt 1 (map). Verbinde Bit-Sequenzen zur gesamten Codierung (concat).
Plan A für einen Worker enc für huff-encode:
bisheriges Bit-Protokoll Zeichen 0
//
(: enc ((huff-tree-of string) (list-of bit) string
12
API: Codieren eines Strings # (Plan A)
(enc
(enc
╷
Q EF=A 0) = empty
╷
0 EF=A 0) = (reverse EF=A)
※
-> (list-of bit))) ; ⭍ , ≠ #
(enc ┌──┐ EF=A 0) = (append
M⟁ ⟁N (enc M⟁ (make-pair L EF=A) 0))
(enc ⟁N (make-pair P EF=A) 0)))
V────────W───────X
※ stellt nächstes Bit YZ[\] an
13
API: Codieren eines Strings # (Plan B)
Plan B für huff-encode geht zweiphasig vor ( Übung). 1. Phase 1: Führe ]`\abc`d eine Tiefensuche im Huffman-Tree
durch. Konstruiere dabei eine sortierte Code-Tabelle:
Zeichen
Code
a b ⋮ z
(list 0 1 1 0 …) (list 0 1 1 1 …)
(list 1 0 1 0 …)
2. Phase 2: Codiere ein Zeichen % durch Lookup in dieser Tabelle. Dazu ist der Huffman-Tree unnötig.
3. Codiere Zeichen des Strings # wie in Schritt 2 (map). Verbinde Bit-Sequenzen zur gesamten Codierung (concat).
6 ┆ API: Huffman-Tree für Text ()( konstruieren (Schritt 1.)
Plan zur Erstellung eines optimalen Huffman-Trees für einen
gegebenen (Referenz-)Text =Q=:
1. Stelle Häufigkeit des Vorkommens jedes Zeichens in =Q= fest. Organisiere Ergebnis in Liste nach steigender Häufigkeit (Funktion occurrences).
Definiere dazu occur-Records ⟪F,g⟫:
Ding F (item) kommt mit Häufigkeit g (freq) vor.
Beispiel:
14
(occurrences ⇝ (list ⟪ ⟪
“erdbeermarmelade”
“l” “m”
,1⟫ ⟪ ,2⟫ ⟪
“b” “r”
,1⟫ ⟪ ,3⟫ ⟪
“d” “e”
)
,2⟫ ⟪”a”,2⟫
,5⟫)
15
API: Huffman-Tree für Text ()( konstruieren (Schritt 2.)
2. Baue den Huffman-Tree von den Blättern her auf. Konstruiere Liste B=A trivialer Huffman-Trees:
╷ ⟪0,g⟫ j ⟪0,g⟫
—
Zeichen 0 Blatt mit Label 0
(string) (huff-leaf-of string)
Bewahre jetzt die folgende Eigenschaft (Invariante I): Die beiden Huffman-Trees, die die seltensten Zeichen in =Q= repräsentieren, stehen am Anfang der Liste B=A:
╷╷
(list ⟪01,g1⟫ ⟪02,g2⟫ …)
API: Huffman-Tree für Text ()( konstruieren (Schritte 3.+4.)
3. Wiederhole bis Liste B=A nur (noch) ein Element trägt: Fasse die zwei ersten occur-Records in B=A zusammen:
merge(⟪⟁1,g1⟫, ⟪⟁2,g2⟫) = ⟪┌──┐ , g1+g2⟫
⟁1 ⟁2
Bewahre Invariante I: Sortiere den neuen occur- Record bzgl. g1+g2 in B=A ein.
4. B=A = (list ⟪⟁, g⟫).2 ⟁ ist der gesuchte Huffman-Tree für den gegebenen (Referenz-)Text =Q=. Done.
2 Überlege, warum jetzt g = (string-length =Q=) gilt.
16
7 ┆ Neue Kontrollstrukturen durch H.O.F (Typ i)
17
Racket lässt sich mit Einsatz von H.O.F leicht um neue Kontrollstrukturen erweitern. Ein Beispiel ist until:
Iteriere l auf Q, bis Endebedingung mngo? erfüllt ist:
(: until ((%a -> boolean) (%a -> %a) %a -> %a))) (define until
(lambda (mngo? l Q) (if (mngo? Q)
Q
╲ (until mngo? l (l Q)))))
─
Echte Iteration: until ist endrekursiv und der erzeugte Reduktionsprozess ist damit tatsächlich iterativ.
18
8 ┆ API: Huffman-Tree für Text ()( konstruieren (Racket)
; Generiere optimalen Huffman-Tree für String s
(: huffman-code (string -> (huff-tree-of string))) (define huffman-code
(lambda (s)
(match (until singleton? merge
(huffman-leaves
(occurrences s)))
Schritt 3.
2.
1.
((list (make-occur ht _)) ht)))) 4.
Huffman-Code (Referenz: Scroll vor STAR WARS Episode IV):
┌─────────────────────┐
┌─────────┐ ┌──────────┐
┌────┐ ┌───┐ ┌─┐
t ┌───┐ a ┌──┐ ┌┐ e
┌┐ ┌─┐ n ┌─┐ o i
┌───────┐
┌────┐ ┌─┐
┌───┐ r s ┌┐
m c g ┌┐ ┌┐ d
uvyf w┌─┐
┌──┐ l h p
┌┐ b kx