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 (ABBACABABB) abarbeiten:
Startcharacter: A
In: ABBACABABB
⬆
(Pointer)
⇒ Der Suchstring ist nun A (tue sonst noch nichts)
————————————————————————————————————————————————————————————
weiter mit Character B
In: ABBACABABB
⬆
(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: ABBACABABB
⬆
(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: ABBACABABB
⬆
(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 C
In: ABBACABABB
⬆
(Pointer)
⇒ Der Suchstring ist nun A + C = AC
AC wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ B
3 ⇨ C
4 ⇨ AB
5 ⇨ BB
6 ⇨ BA
AC nicht in der Tabelle ⇒
AC wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters A (1) wird zur Ausgabe hinzugefügt:
Out: 1 2 2 | 1
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (C).
————————————————————————————————————————————————————————————
weiter mit Character A
In: ABBACABABB
⬆
(Pointer)
⇒ Der Suchstring ist nun C + A = CA
CA wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ B
3 ⇨ C
4 ⇨ AB
5 ⇨ BB
6 ⇨ BA
7 ⇨ AC
CA nicht in der Tabelle ⇒
CA wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters C (3) wird zur Ausgabe hinzugefügt:
Out: 1 2 2 1 | 3
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (A).
————————————————————————————————————————————————————————————
weiter mit Character B
In: ABBACABABB
⬆
(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 ⇨ AC
8 ⇨ CA
AB in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (AB).
————————————————————————————————————————————————————————————
weiter mit Character A
In: ABBACABABB
⬆
(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 ⇨ AC
8 ⇨ CA
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 1 3 | 4
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (A).
————————————————————————————————————————————————————————————
weiter mit Character B
In: ABBACABABB
⬆
(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 ⇨ AC
8 ⇨ CA
9 ⇨ ABA
AB in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (AB).
————————————————————————————————————————————————————————————
weiter mit Character B
In: ABBACABABB
⬆
(Pointer)
⇒ Der Suchstring ist nun AB + B = ABB
ABB wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ B
3 ⇨ C
4 ⇨ AB
5 ⇨ BB
6 ⇨ BA
7 ⇨ AC
8 ⇨ CA
9 ⇨ ABA
ABB nicht in der Tabelle ⇒
ABB wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters AB (4) wird zur Ausgabe hinzugefügt:
Out: 1 2 2 1 3 4 | 4
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (B).
————————————————————————————————————————————————————————————
Kein weiterer Character im Ausgangsstring.
letzten Character verarbeiten ⇒
Index von B (2) wird zur Ausgabe hinzugefügt:
Out: 1 2 2 1 3 4 4 | 2
⬆
(hinzugefügt)
————————————————————————————————————————————————————————————
Ausgangsstring: A B B A C A B A B B
Resultat: 1 2 2 1 3 4 4 2
Länge Ausgangsstring: 10
Länge Resultat: 8
Ersparnis: 20.00%
————————————————————————————————————————————————————————————