Lempel-Ziv-Welch-Algorithmus
(mal ganz ausführlich, Schritt für Schritt ☺)
————————————————————————————————————————————————————————————
Initialisierung:
(jeder Character des Eingangsstrings wird in der Tabelle abgelegt)
Tabelle:
1 ⇨ A
2 ⇨ B
3 ⇨ C
————————————————————————————————————————————————————————————
Ausgangsstring (ABBABABAC) abarbeiten:
Startcharacter: A
In: ABBABABAC
⬆
(Pointer)
⇒ Der Suchstring ist nun A (tue sonst noch nichts)
————————————————————————————————————————————————————————————
weiter mit Character B
In: ABBABABAC
⬆
(Pointer)
⇒ Der Suchstring ist nun A + B = AB
AB wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ B
3 ⇨ C
AB nicht in der Tabelle ⇒
AB wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters A (1) wird zur Ausgabe hinzugefügt:
Out: (leer)| 1
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (B).
————————————————————————————————————————————————————————————
weiter mit Character B
In: ABBABABAC
⬆
(Pointer)
⇒ Der Suchstring ist nun B + B = BB
BB wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ B
3 ⇨ C
4 ⇨ AB
BB nicht in der Tabelle ⇒
BB wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters B (2) wird zur Ausgabe hinzugefügt:
Out: 1 | 2
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (B).
————————————————————————————————————————————————————————————
weiter mit Character A
In: ABBABABAC
⬆
(Pointer)
⇒ Der Suchstring ist nun B + A = BA
BA wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ B
3 ⇨ C
4 ⇨ AB
5 ⇨ BB
BA nicht in der Tabelle ⇒
BA wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters B (2) wird zur Ausgabe hinzugefügt:
Out: 1 2 | 2
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (A).
————————————————————————————————————————————————————————————
weiter mit Character B
In: ABBABABAC
⬆
(Pointer)
⇒ Der Suchstring ist nun A + B = AB
AB wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ B
3 ⇨ C
4 ⇨ AB
5 ⇨ BB
6 ⇨ BA
AB in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (AB).
————————————————————————————————————————————————————————————
weiter mit Character A
In: ABBABABAC
⬆
(Pointer)
⇒ Der Suchstring ist nun AB + A = ABA
ABA wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ B
3 ⇨ C
4 ⇨ AB
5 ⇨ BB
6 ⇨ BA
ABA nicht in der Tabelle ⇒
ABA wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters AB (4) wird zur Ausgabe hinzugefügt:
Out: 1 2 2 | 4
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (A).
————————————————————————————————————————————————————————————
weiter mit Character B
In: ABBABABAC
⬆
(Pointer)
⇒ Der Suchstring ist nun A + B = AB
AB wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ B
3 ⇨ C
4 ⇨ AB
5 ⇨ BB
6 ⇨ BA
7 ⇨ ABA
AB in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (AB).
————————————————————————————————————————————————————————————
weiter mit Character A
In: ABBABABAC
⬆
(Pointer)
⇒ Der Suchstring ist nun AB + A = ABA
ABA wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ B
3 ⇨ C
4 ⇨ AB
5 ⇨ BB
6 ⇨ BA
7 ⇨ ABA
ABA in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (ABA).
————————————————————————————————————————————————————————————
weiter mit Character C
In: ABBABABAC
⬆
(Pointer)
⇒ Der Suchstring ist nun ABA + C = ABAC
ABAC wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ B
3 ⇨ C
4 ⇨ AB
5 ⇨ BB
6 ⇨ BA
7 ⇨ ABA
ABAC nicht in der Tabelle ⇒
ABAC wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters ABA (7) wird zur Ausgabe hinzugefügt:
Out: 1 2 2 4 | 7
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (C).
————————————————————————————————————————————————————————————
Kein weiterer Character im Ausgangsstring.
letzten Character verarbeiten ⇒
Index von C (3) wird zur Ausgabe hinzugefügt:
Out: 1 2 2 4 7 | 3
⬆
(hinzugefügt)
————————————————————————————————————————————————————————————
Ausgangsstring: A B B A B A B A C
Resultat: 1 2 2 4 7 3
Länge Ausgangsstring: 9
Länge Resultat: 6
Ersparnis: 33.33%
————————————————————————————————————————————————————————————