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 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
————————————————————————————————————————————————————————————
Ausgangsstring (AACHEN_AAL_AALEN_AAR_AAS) abarbeiten:
Startcharacter: A
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun A (tue sonst noch nichts)
————————————————————————————————————————————————————————————
weiter mit Character A
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun A + A = AA
AA wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
AA nicht in der Tabelle ⇒
AA 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 (A).
————————————————————————————————————————————————————————————
weiter mit Character C
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun A + C = AC
AC wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
AC nicht in der Tabelle ⇒
AC wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters A (1) wird zur Ausgabe hinzugefügt:
Out: 1 | 1
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (C).
————————————————————————————————————————————————————————————
weiter mit Character H
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun C + H = CH
CH wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
CH nicht in der Tabelle ⇒
CH wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters C (2) wird zur Ausgabe hinzugefügt:
Out: 1 1 | 2
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (H).
————————————————————————————————————————————————————————————
weiter mit Character E
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun H + E = HE
HE wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
HE nicht in der Tabelle ⇒
HE wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters H (3) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 | 3
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (E).
————————————————————————————————————————————————————————————
weiter mit Character N
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun E + N = EN
EN wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
EN nicht in der Tabelle ⇒
EN wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters E (4) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 3 | 4
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (N).
————————————————————————————————————————————————————————————
weiter mit Character _
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun N + _ = N_
N_ wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
N_ nicht in der Tabelle ⇒
N_ wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters N (5) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 3 4 | 5
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (_).
————————————————————————————————————————————————————————————
weiter mit Character A
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun _ + A = _A
_A wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
_A nicht in der Tabelle ⇒
_A wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters _ (6) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 3 4 5 | 6
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (A).
————————————————————————————————————————————————————————————
weiter mit Character A
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun A + A = AA
AA wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
AA in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (AA).
————————————————————————————————————————————————————————————
weiter mit Character L
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun AA + L = AAL
AAL wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
AAL nicht in der Tabelle ⇒
AAL wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters AA (10) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 3 4 5 6 | 10
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (L).
————————————————————————————————————————————————————————————
weiter mit Character _
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun L + _ = L_
L_ wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
L_ nicht in der Tabelle ⇒
L_ wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters L (7) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 3 4 5 6 10 | 7
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (_).
————————————————————————————————————————————————————————————
weiter mit Character A
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun _ + A = _A
_A wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
18 ⇨ L_
_A in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (_A).
————————————————————————————————————————————————————————————
weiter mit Character A
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun _A + A = _AA
_AA wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
18 ⇨ L_
_AA nicht in der Tabelle ⇒
_AA wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters _A (16) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 3 4 5 6 10 7 | 16
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (A).
————————————————————————————————————————————————————————————
weiter mit Character L
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun A + L = AL
AL wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
18 ⇨ L_
19 ⇨ _AA
AL nicht in der Tabelle ⇒
AL wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters A (1) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 3 4 5 6 10 7 16 | 1
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (L).
————————————————————————————————————————————————————————————
weiter mit Character E
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun L + E = LE
LE wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
18 ⇨ L_
19 ⇨ _AA
20 ⇨ AL
LE nicht in der Tabelle ⇒
LE wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters L (7) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 3 4 5 6 10 7 16 1 | 7
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (E).
————————————————————————————————————————————————————————————
weiter mit Character N
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun E + N = EN
EN wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
18 ⇨ L_
19 ⇨ _AA
20 ⇨ AL
21 ⇨ LE
EN in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (EN).
————————————————————————————————————————————————————————————
weiter mit Character _
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun EN + _ = EN_
EN_ wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
18 ⇨ L_
19 ⇨ _AA
20 ⇨ AL
21 ⇨ LE
EN_ nicht in der Tabelle ⇒
EN_ wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters EN (14) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 3 4 5 6 10 7 16 1 7 | 14
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (_).
————————————————————————————————————————————————————————————
weiter mit Character A
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun _ + A = _A
_A wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
18 ⇨ L_
19 ⇨ _AA
20 ⇨ AL
21 ⇨ LE
22 ⇨ EN_
_A in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (_A).
————————————————————————————————————————————————————————————
weiter mit Character A
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun _A + A = _AA
_AA wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
18 ⇨ L_
19 ⇨ _AA
20 ⇨ AL
21 ⇨ LE
22 ⇨ EN_
_AA in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (_AA).
————————————————————————————————————————————————————————————
weiter mit Character R
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun _AA + R = _AAR
_AAR wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
18 ⇨ L_
19 ⇨ _AA
20 ⇨ AL
21 ⇨ LE
22 ⇨ EN_
_AAR nicht in der Tabelle ⇒
_AAR wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters _AA (19) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 3 4 5 6 10 7 16 1 7 14 | 19
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (R).
————————————————————————————————————————————————————————————
weiter mit Character _
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun R + _ = R_
R_ wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
18 ⇨ L_
19 ⇨ _AA
20 ⇨ AL
21 ⇨ LE
22 ⇨ EN_
23 ⇨ _AAR
R_ nicht in der Tabelle ⇒
R_ wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters R (8) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 3 4 5 6 10 7 16 1 7 14 19 | 8
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (_).
————————————————————————————————————————————————————————————
weiter mit Character A
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun _ + A = _A
_A wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
18 ⇨ L_
19 ⇨ _AA
20 ⇨ AL
21 ⇨ LE
22 ⇨ EN_
23 ⇨ _AAR
24 ⇨ R_
_A in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (_A).
————————————————————————————————————————————————————————————
weiter mit Character A
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun _A + A = _AA
_AA wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
18 ⇨ L_
19 ⇨ _AA
20 ⇨ AL
21 ⇨ LE
22 ⇨ EN_
23 ⇨ _AAR
24 ⇨ R_
_AA in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (_AA).
————————————————————————————————————————————————————————————
weiter mit Character S
In: AACHEN_AAL_AALEN_AAR_AAS
⬆
(Pointer)
⇒ Der Suchstring ist nun _AA + S = _AAS
_AAS wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ C
3 ⇨ H
4 ⇨ E
5 ⇨ N
6 ⇨ _
7 ⇨ L
8 ⇨ R
9 ⇨ S
10 ⇨ AA
11 ⇨ AC
12 ⇨ CH
13 ⇨ HE
14 ⇨ EN
15 ⇨ N_
16 ⇨ _A
17 ⇨ AAL
18 ⇨ L_
19 ⇨ _AA
20 ⇨ AL
21 ⇨ LE
22 ⇨ EN_
23 ⇨ _AAR
24 ⇨ R_
_AAS nicht in der Tabelle ⇒
_AAS wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters _AA (19) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 3 4 5 6 10 7 16 1 7 14 19 8 | 19
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (S).
————————————————————————————————————————————————————————————
Kein weiterer Character im Ausgangsstring.
letzten Character verarbeiten ⇒
Index von S (9) wird zur Ausgabe hinzugefügt:
Out: 1 1 2 3 4 5 6 10 7 16 1 7 14 19 8 19 | 9
⬆
(hinzugefügt)
————————————————————————————————————————————————————————————
Ausgangsstring: A A C H E N _ A A L _ A A L E N _ A A R _ A A S
Resultat: 1 1 2 3 4 5 6 10 7 16 1 7 14 19 8 19 9
Länge Ausgangsstring: 24
Länge Resultat: 22
Ersparnis: 8.33%
————————————————————————————————————————————————————————————