Lempel-Ziv-Welch-Algorithmus
(mal ganz ausführlich, Schritt für Schritt ☺)
————————————————————————————————————————————————————————————
Initialisierung:
(jeder Character des Eingangsstrings wird in der Tabelle abgelegt)
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
————————————————————————————————————————————————————————————
Ausgangsstring (LZWLZ78LZ77LZCLZMWLZAP) abarbeiten:
Startcharacter: L
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun L (tue sonst noch nichts)
————————————————————————————————————————————————————————————
weiter mit Character Z
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun L + Z = LZ
LZ wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
LZ nicht in der Tabelle ⇒
LZ wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters L (1) wird zur Ausgabe hinzugefügt:
Out: (leer)| 1
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (Z).
————————————————————————————————————————————————————————————
weiter mit Character W
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun Z + W = ZW
ZW wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
ZW nicht in der Tabelle ⇒
ZW wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters Z (2) wird zur Ausgabe hinzugefügt:
Out: 1 | 2
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (W).
————————————————————————————————————————————————————————————
weiter mit Character L
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun W + L = WL
WL wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
WL nicht in der Tabelle ⇒
WL wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters W (3) wird zur Ausgabe hinzugefügt:
Out: 1 2 | 3
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (L).
————————————————————————————————————————————————————————————
weiter mit Character Z
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun L + Z = LZ
LZ wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
LZ in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (LZ).
————————————————————————————————————————————————————————————
weiter mit Character 7
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun LZ + 7 = LZ7
LZ7 wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
LZ7 nicht in der Tabelle ⇒
LZ7 wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters LZ (10) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 | 10
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (7).
————————————————————————————————————————————————————————————
weiter mit Character 8
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun 7 + 8 = 78
78 wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
78 nicht in der Tabelle ⇒
78 wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters 7 (4) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 10 | 4
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (8).
————————————————————————————————————————————————————————————
weiter mit Character L
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun 8 + L = 8L
8L wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
8L nicht in der Tabelle ⇒
8L wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters 8 (5) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 10 4 | 5
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (L).
————————————————————————————————————————————————————————————
weiter mit Character Z
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun L + Z = LZ
LZ wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
LZ in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (LZ).
————————————————————————————————————————————————————————————
weiter mit Character 7
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun LZ + 7 = LZ7
LZ7 wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
LZ7 in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (LZ7).
————————————————————————————————————————————————————————————
weiter mit Character 7
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun LZ7 + 7 = LZ77
LZ77 wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
LZ77 nicht in der Tabelle ⇒
LZ77 wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters LZ7 (13) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 10 4 5 | 13
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (7).
————————————————————————————————————————————————————————————
weiter mit Character L
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun 7 + L = 7L
7L wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
16 ⇨ LZ77
7L nicht in der Tabelle ⇒
7L wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters 7 (4) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 10 4 5 13 | 4
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (L).
————————————————————————————————————————————————————————————
weiter mit Character Z
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun L + Z = LZ
LZ wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
16 ⇨ LZ77
17 ⇨ 7L
LZ in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (LZ).
————————————————————————————————————————————————————————————
weiter mit Character C
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun LZ + C = LZC
LZC wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
16 ⇨ LZ77
17 ⇨ 7L
LZC nicht in der Tabelle ⇒
LZC wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters LZ (10) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 10 4 5 13 4 | 10
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (C).
————————————————————————————————————————————————————————————
weiter mit Character L
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun C + L = CL
CL wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
16 ⇨ LZ77
17 ⇨ 7L
18 ⇨ LZC
CL nicht in der Tabelle ⇒
CL wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters C (6) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 10 4 5 13 4 10 | 6
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (L).
————————————————————————————————————————————————————————————
weiter mit Character Z
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun L + Z = LZ
LZ wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
16 ⇨ LZ77
17 ⇨ 7L
18 ⇨ LZC
19 ⇨ CL
LZ in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (LZ).
————————————————————————————————————————————————————————————
weiter mit Character M
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun LZ + M = LZM
LZM wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
16 ⇨ LZ77
17 ⇨ 7L
18 ⇨ LZC
19 ⇨ CL
LZM nicht in der Tabelle ⇒
LZM wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters LZ (10) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 10 4 5 13 4 10 6 | 10
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (M).
————————————————————————————————————————————————————————————
weiter mit Character W
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun M + W = MW
MW wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
16 ⇨ LZ77
17 ⇨ 7L
18 ⇨ LZC
19 ⇨ CL
20 ⇨ LZM
MW nicht in der Tabelle ⇒
MW wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters M (7) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 10 4 5 13 4 10 6 10 | 7
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (W).
————————————————————————————————————————————————————————————
weiter mit Character L
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun W + L = WL
WL wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
16 ⇨ LZ77
17 ⇨ 7L
18 ⇨ LZC
19 ⇨ CL
20 ⇨ LZM
21 ⇨ MW
WL in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (WL).
————————————————————————————————————————————————————————————
weiter mit Character Z
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun WL + Z = WLZ
WLZ wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
16 ⇨ LZ77
17 ⇨ 7L
18 ⇨ LZC
19 ⇨ CL
20 ⇨ LZM
21 ⇨ MW
WLZ nicht in der Tabelle ⇒
WLZ wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters WL (12) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 10 4 5 13 4 10 6 10 7 | 12
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (Z).
————————————————————————————————————————————————————————————
weiter mit Character A
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun Z + A = ZA
ZA wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
16 ⇨ LZ77
17 ⇨ 7L
18 ⇨ LZC
19 ⇨ CL
20 ⇨ LZM
21 ⇨ MW
22 ⇨ WLZ
ZA nicht in der Tabelle ⇒
ZA wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters Z (2) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 10 4 5 13 4 10 6 10 7 12 | 2
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (A).
————————————————————————————————————————————————————————————
weiter mit Character P
In: LZWLZ78LZ77LZCLZMWLZAP
⬆
(Pointer)
⇒ Der Suchstring ist nun A + P = AP
AP wird in der Tabelle gesucht...
Tabelle:
1 ⇨ L
2 ⇨ Z
3 ⇨ W
4 ⇨ 7
5 ⇨ 8
6 ⇨ C
7 ⇨ M
8 ⇨ A
9 ⇨ P
10 ⇨ LZ
11 ⇨ ZW
12 ⇨ WL
13 ⇨ LZ7
14 ⇨ 78
15 ⇨ 8L
16 ⇨ LZ77
17 ⇨ 7L
18 ⇨ LZC
19 ⇨ CL
20 ⇨ LZM
21 ⇨ MW
22 ⇨ WLZ
23 ⇨ ZA
AP nicht in der Tabelle ⇒
AP wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters A (8) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 10 4 5 13 4 10 6 10 7 12 2 | 8
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (P).
————————————————————————————————————————————————————————————
Kein weiterer Character im Ausgangsstring.
letzten Character verarbeiten ⇒
Index von P (9) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 10 4 5 13 4 10 6 10 7 12 2 8 | 9
⬆
(hinzugefügt)
————————————————————————————————————————————————————————————
Ausgangsstring: L Z W L Z 7 8 L Z 7 7 L Z C L Z M W L Z A P
Resultat: 1 2 3 10 4 5 13 4 10 6 10 7 12 2 8 9
Länge Ausgangsstring: 22
Länge Resultat: 21
Ersparnis: 4.55%
————————————————————————————————————————————————————————————