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 ⇨ G
3 ⇨ T
4 ⇨ C
————————————————————————————————————————————————————————————
Ausgangsstring (AAAGTCTGAC) abarbeiten:
Startcharacter: A
In: AAAGTCTGAC
⬆
(Pointer)
⇒ Der Suchstring ist nun A (tue sonst noch nichts)
————————————————————————————————————————————————————————————
weiter mit Character A
In: AAAGTCTGAC
⬆
(Pointer)
⇒ Der Suchstring ist nun A + A = AA
AA wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ G
3 ⇨ T
4 ⇨ C
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 A
In: AAAGTCTGAC
⬆
(Pointer)
⇒ Der Suchstring ist nun A + A = AA
AA wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ G
3 ⇨ T
4 ⇨ C
5 ⇨ AA
AA in der Tabelle gefunden ⇒
✎ merken: Den momentanen Suchstring (AA).
————————————————————————————————————————————————————————————
weiter mit Character G
In: AAAGTCTGAC
⬆
(Pointer)
⇒ Der Suchstring ist nun AA + G = AAG
AAG wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ G
3 ⇨ T
4 ⇨ C
5 ⇨ AA
AAG nicht in der Tabelle ⇒
AAG wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters AA (5) wird zur Ausgabe hinzugefügt:
Out: 1 | 5
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (G).
————————————————————————————————————————————————————————————
weiter mit Character T
In: AAAGTCTGAC
⬆
(Pointer)
⇒ Der Suchstring ist nun G + T = GT
GT wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ G
3 ⇨ T
4 ⇨ C
5 ⇨ AA
6 ⇨ AAG
GT nicht in der Tabelle ⇒
GT wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters G (2) wird zur Ausgabe hinzugefügt:
Out: 1 5 | 2
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (T).
————————————————————————————————————————————————————————————
weiter mit Character C
In: AAAGTCTGAC
⬆
(Pointer)
⇒ Der Suchstring ist nun T + C = TC
TC wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ G
3 ⇨ T
4 ⇨ C
5 ⇨ AA
6 ⇨ AAG
7 ⇨ GT
TC nicht in der Tabelle ⇒
TC wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters T (3) wird zur Ausgabe hinzugefügt:
Out: 1 5 2 | 3
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (C).
————————————————————————————————————————————————————————————
weiter mit Character T
In: AAAGTCTGAC
⬆
(Pointer)
⇒ Der Suchstring ist nun C + T = CT
CT wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ G
3 ⇨ T
4 ⇨ C
5 ⇨ AA
6 ⇨ AAG
7 ⇨ GT
8 ⇨ TC
CT nicht in der Tabelle ⇒
CT wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters C (4) wird zur Ausgabe hinzugefügt:
Out: 1 5 2 3 | 4
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (T).
————————————————————————————————————————————————————————————
weiter mit Character G
In: AAAGTCTGAC
⬆
(Pointer)
⇒ Der Suchstring ist nun T + G = TG
TG wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ G
3 ⇨ T
4 ⇨ C
5 ⇨ AA
6 ⇨ AAG
7 ⇨ GT
8 ⇨ TC
9 ⇨ CT
TG nicht in der Tabelle ⇒
TG wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters T (3) wird zur Ausgabe hinzugefügt:
Out: 1 5 2 3 4 | 3
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (G).
————————————————————————————————————————————————————————————
weiter mit Character A
In: AAAGTCTGAC
⬆
(Pointer)
⇒ Der Suchstring ist nun G + A = GA
GA wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ G
3 ⇨ T
4 ⇨ C
5 ⇨ AA
6 ⇨ AAG
7 ⇨ GT
8 ⇨ TC
9 ⇨ CT
10 ⇨ TG
GA nicht in der Tabelle ⇒
GA wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters G (2) wird zur Ausgabe hinzugefügt:
Out: 1 5 2 3 4 3 | 2
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (A).
————————————————————————————————————————————————————————————
weiter mit Character C
In: AAAGTCTGAC
⬆
(Pointer)
⇒ Der Suchstring ist nun A + C = AC
AC wird in der Tabelle gesucht...
Tabelle:
1 ⇨ A
2 ⇨ G
3 ⇨ T
4 ⇨ C
5 ⇨ AA
6 ⇨ AAG
7 ⇨ GT
8 ⇨ TC
9 ⇨ CT
10 ⇨ TG
11 ⇨ GA
AC nicht in der Tabelle ⇒
AC wird zur Tabelle hinzugefügt
Index des ✎ gemerkten Musters A (1) wird zur Ausgabe hinzugefügt:
Out: 1 5 2 3 4 3 2 | 1
⬆
(hinzugefügt)
✎ merken: Den momentanen Character (C).
————————————————————————————————————————————————————————————
Kein weiterer Character im Ausgangsstring.
letzten Character verarbeiten ⇒
Index von C (4) wird zur Ausgabe hinzugefügt:
Out: 1 5 2 3 4 3 2 1 | 4
⬆
(hinzugefügt)
————————————————————————————————————————————————————————————
Ausgangsstring: A A A G T C T G A C
Resultat: 1 5 2 3 4 3 2 1 4
Länge Ausgangsstring: 10
Länge Resultat: 9
Ersparnis: 10.00%
————————————————————————————————————————————————————————————