Lempel-Ziv-Welch-Algorithmus
(mal ganz ausführlich, Schritt für Schritt ☺)
————————————————————————————————————————————————————————————
Initialisierung:
(jeder Character des Eingangsstrings wird in der Tabelle abgelegt)
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
————————————————————————————————————————————————————————————
Ausgangsstring (TOBEORNOTTOBEORTOBEORNOT) abarbeiten:
Startcharacter: T
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun T (tue sonst noch nichts)
————————————————————————————————————————————————————————————
weiter mit Character O
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun T + O = TO
TO wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
TO nicht in der Tabelle ⇒
TO wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters T (1) wird zur Ausgabe hinzugefügt:
Out: (leer)| 1
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (O).
————————————————————————————————————————————————————————————
weiter mit Character B
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun O + B = OB
OB wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
OB nicht in der Tabelle ⇒
OB wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters O (2) wird zur Ausgabe hinzugefügt:
Out: 1 | 2
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (B).
————————————————————————————————————————————————————————————
weiter mit Character E
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun B + E = BE
BE wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
BE nicht in der Tabelle ⇒
BE wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters B (3) wird zur Ausgabe hinzugefügt:
Out: 1 2 | 3
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (E).
————————————————————————————————————————————————————————————
weiter mit Character O
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun E + O = EO
EO wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
EO nicht in der Tabelle ⇒
EO wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters E (4) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 | 4
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (O).
————————————————————————————————————————————————————————————
weiter mit Character R
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun O + R = OR
OR wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
OR nicht in der Tabelle ⇒
OR wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters O (2) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 4 | 2
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (R).
————————————————————————————————————————————————————————————
weiter mit Character N
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun R + N = RN
RN wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
RN nicht in der Tabelle ⇒
RN wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters R (5) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 4 2 | 5
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (N).
————————————————————————————————————————————————————————————
weiter mit Character O
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun N + O = NO
NO wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
NO nicht in der Tabelle ⇒
NO wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters N (6) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 4 2 5 | 6
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (O).
————————————————————————————————————————————————————————————
weiter mit Character T
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun O + T = OT
OT wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
OT nicht in der Tabelle ⇒
OT wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters O (2) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 4 2 5 6 | 2
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (T).
————————————————————————————————————————————————————————————
weiter mit Character T
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun T + T = TT
TT wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
TT nicht in der Tabelle ⇒
TT wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters T (1) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 4 2 5 6 2 | 1
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (T).
————————————————————————————————————————————————————————————
weiter mit Character O
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun T + O = TO
TO wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
TO in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (TO).
————————————————————————————————————————————————————————————
weiter mit Character B
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun TO + B = TOB
TOB wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
TOB nicht in der Tabelle ⇒
TOB wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters TO (7) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 4 2 5 6 2 1 | 7
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (B).
————————————————————————————————————————————————————————————
weiter mit Character E
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun B + E = BE
BE wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
16 ⇨ TOB
BE in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (BE).
————————————————————————————————————————————————————————————
weiter mit Character O
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun BE + O = BEO
BEO wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
16 ⇨ TOB
BEO nicht in der Tabelle ⇒
BEO wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters BE (9) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 4 2 5 6 2 1 7 | 9
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (O).
————————————————————————————————————————————————————————————
weiter mit Character R
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun O + R = OR
OR wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
16 ⇨ TOB
17 ⇨ BEO
OR in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (OR).
————————————————————————————————————————————————————————————
weiter mit Character T
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun OR + T = ORT
ORT wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
16 ⇨ TOB
17 ⇨ BEO
ORT nicht in der Tabelle ⇒
ORT wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters OR (11) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 4 2 5 6 2 1 7 9 | 11
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (T).
————————————————————————————————————————————————————————————
weiter mit Character O
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun T + O = TO
TO wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
16 ⇨ TOB
17 ⇨ BEO
18 ⇨ ORT
TO in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (TO).
————————————————————————————————————————————————————————————
weiter mit Character B
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun TO + B = TOB
TOB wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
16 ⇨ TOB
17 ⇨ BEO
18 ⇨ ORT
TOB in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (TOB).
————————————————————————————————————————————————————————————
weiter mit Character E
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun TOB + E = TOBE
TOBE wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
16 ⇨ TOB
17 ⇨ BEO
18 ⇨ ORT
TOBE nicht in der Tabelle ⇒
TOBE wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters TOB (16) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 4 2 5 6 2 1 7 9 11 | 16
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (E).
————————————————————————————————————————————————————————————
weiter mit Character O
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun E + O = EO
EO wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
16 ⇨ TOB
17 ⇨ BEO
18 ⇨ ORT
19 ⇨ TOBE
EO in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (EO).
————————————————————————————————————————————————————————————
weiter mit Character R
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun EO + R = EOR
EOR wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
16 ⇨ TOB
17 ⇨ BEO
18 ⇨ ORT
19 ⇨ TOBE
EOR nicht in der Tabelle ⇒
EOR wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters EO (10) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 4 2 5 6 2 1 7 9 11 16 | 10
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (R).
————————————————————————————————————————————————————————————
weiter mit Character N
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun R + N = RN
RN wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
16 ⇨ TOB
17 ⇨ BEO
18 ⇨ ORT
19 ⇨ TOBE
20 ⇨ EOR
RN in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (RN).
————————————————————————————————————————————————————————————
weiter mit Character O
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun RN + O = RNO
RNO wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
16 ⇨ TOB
17 ⇨ BEO
18 ⇨ ORT
19 ⇨ TOBE
20 ⇨ EOR
RNO nicht in der Tabelle ⇒
RNO wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters RN (12) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 4 2 5 6 2 1 7 9 11 16 10 | 12
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (O).
————————————————————————————————————————————————————————————
weiter mit Character T
In: TOBEORNOTTOBEORTOBEORNOT
⬆
(Pointer)
⇒ Der Suchstring ist nun O + T = OT
OT wird in der Tabelle gesucht...
Tabelle:
1 ⇨ T
2 ⇨ O
3 ⇨ B
4 ⇨ E
5 ⇨ R
6 ⇨ N
7 ⇨ TO
8 ⇨ OB
9 ⇨ BE
10 ⇨ EO
11 ⇨ OR
12 ⇨ RN
13 ⇨ NO
14 ⇨ OT
15 ⇨ TT
16 ⇨ TOB
17 ⇨ BEO
18 ⇨ ORT
19 ⇨ TOBE
20 ⇨ EOR
21 ⇨ RNO
OT in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (OT).
————————————————————————————————————————————————————————————
Kein weiterer Character im Ausgangsstring.
letzten Character verarbeiten ⇒
Index von OT (14) wird zur Ausgabe hinzugefügt:
Out: 1 2 3 4 2 5 6 2 1 7 9 11 16 10 12 | 14
⬆
(hinzugefügt)
————————————————————————————————————————————————————————————
Ausgangsstring: T O B E O R N O T T O B E O R T O B E O R N O T
Resultat: 1 2 3 4 2 5 6 2 1 7 9 11 16 10 12 14
Länge Ausgangsstring: 24
Länge Resultat: 21
Ersparnis: 12.50%
————————————————————————————————————————————————————————————