Willkommen zurück in der Vorlesung mit dem Thema Stringology und
letztes Mal sind wir standgeblieben bei Suffix Trees und Suffix
Arrays.
Ja, ich habe das nochmal auf die Dokumentenkamera, also hier war ein
Text, wir kennen diesen Suffix Tree-Bauer, was ein Prefix Tree ist
über alle Suffixe und dann haben wir gesagt, okay, das braucht zu viel
Platz und dann kamen wir also zum Suffix Array und der Suffix Array,
das enthält die Suffixe in sortierter Reihenfolge und jedes Suffix ist
identifiziert mit dem Anfangsindex.
Und heute in der Vorlesung, also die erste Dreiviertelstunde, wollen
wir erklären, wie das in linearer Zeit konstruiert werden kann, dieses
Suffix Array.
So, und jetzt schalte ich um auf die Folien, die wir bisher noch nicht
benutzt haben.
Michael, warum funktioniert das nicht?
Video, VGA,
hm?
Ah, okay, gut.
So,
genau, ich kenne da einmal nochmal den Anfang.
So, und genau, am Anfang haben wir gesagt, ja, Stringology gibt es
quasi zwei Indizes, die wichtig sind, und zwar einmal das Suffix
Array, was wir heute besprechen, und dann gibt es invertierte Indizes.
Und wir hatten schon einmal was vom invertierter Index gehört.
Invertierter Index, wo wird das eingesetzt?
In Suchmaschinen.
Ja, so, das heißt, Suffix Arrays, das wird in der Bioinformatik
eingesetzt vor allem, und invertierte Indizes, das wird in der
Suchmaschine eingesetzt.
Und das ist ein ganz einfacher Index.
Ich mache nachher vielleicht noch ein Beispiel dazu.
Also da gibt es nichts auf die Folien zu invertierter Index, aber ich
zeichne das dann nachher auch noch in der Dokumentakamera auf.
So, genau, aber jetzt, genau, machen wir Suffix Array Konstruktion.
Und da gab es ein Paper, wie das in Linearzeit geht, von Joachim
Kalkein und Peter Sanders, 2003.
Und genau das Resultat, das schauen wir uns an.
Das Schöne ist, es gibt mehrere solche Algorithmen, die das in
Linearzeit konstruieren.
Und selbst der Suffix Tree, also wenn man das hier schaut, diese zwei
Referenzen, 73 und 76, das war Linearzeitkonstruktion für diesen
Suffix Tree.
Und wenn man diesen Suffix Tree hat, dann kann man natürlich auch den
Suffix Array in Linearzeit berechnen, indem man diese Blätter von
links nach rechts liest, von dem Suffix Baum.
Genau, aber der Vorteil des Algorithmus, den wir heute kennenlernen,
ist, dass er sehr kurz ist.
Ja, da ist irgendwie nur sehr wenig Code, nur eine Seite oder eine
Halbseite.
Und der Vorteil ist auch, dass man diesen Algorithmus für verschiedene
Maschinemodelle, also External Memory zum Beispiel, oder auch im
Imperium Modell, der schöne Eigenschaften hat.
Jetzt kommen wir erstmal zu ein bisschen Notation in der Stringology.
Also wenn ich ein Array habe, dann sage ich, ich habe ein halboffenes
Intervall.
Das heißt, ich mache da die runde Klammer am Ende und die Eckenklammer
vorne, dann heißt es, ich bin aber irgendwie bis n-1 und die Suffixe
vom Text, wenn es ein Array von Buchstaben ist, ist quasi der
Substring von i bis n und das n ist aber halboffen.
Das heißt, es geht bis n-1.
Und am Schluss, wie letztes Mal in der Vorlesung auch, da machen wir
so ein Zeichen hin, das hier 0 ist und das ist kleiner als alle
anderen Buchstaben, manchmal nimmt man auch Dollar.
Aber das heißt, alle anderen Buchstaben, die nach dem Ende des Textes
kommen, sind 0.
Wie das dann auch beim C-String zum Beispiel auch ist.
Da ist am Ende irgendwie ein 0 dran und das ist schön.
Okay, so.
Und dann, genau, wenn man jetzt diese Suffixe hat von einem Text, dann
sortiert man die und dann kriegt man dann die Pondentation der Suffixe
und die haben die Eigenschaft, dass die lexographisch sortiert sind.
Also hier ist ein Beispiel für Banana.
Da wäre das kleinste Suffixe a, weil da drauf die 0 folgt und dann
kommt a n und n ist größer als die 0, weil die 0 das lexographisch
kleinste Zeichen ist.
Okay, genau.
Was gibt es da für Einwendungen?
Volltextsuche gibt es.
Also ich habe ein großes Text und will dann das Pattern suchen drin.
Böruswiedertransformation, das werden wir auch noch kennenlernen im
nächsten Jahr.
Wird in der Datakonfektion eingesetzt.
Also wenn man Bzip2 z.B.
nimmt oder Bzip, das beruht auf dieser Böruswiedertransformierten.
Was man aber auch noch machen kann mit dem Suffixbaum ist, die Lz
-Faktorisierung auszurechnen.
Das werden wir auch noch kennenlernen, was das ist.
Und die Lz-Faktorisierung ist Grundlage für andere
Komprimierungsalgorithmen oder Programme wie Gzip oder Lz4.
Das heißt, in den Kompressionsalgorithmen selber wird man immer suchen
nach Wiederholungen, die man ersetzt durch etwas Kürzeres.
Und das heißt, da braucht man einen Index, um das zu machen.
Und dann ist der Suffix-Array natürlich auch noch ein schönerer Satz
für diese Suffixbäume.
Das heißt, letztes Mal haben wir gesehen, dass man MlogN, wenn M die
Patternlänge ist, die Komplizität, kann man das erreichen.
Und die Übung, die wir dann machen, ist auch, wie man das mit M plus
LogN macht als Komplizität.
Und aus dem Suffixbaum kann man natürlich den Suffix-Array berechnen,
wie gesagt.
Und da gab es dann aber auch diese Algorithmen.
Und dieser Suffixbaum hier, der ist quasi ein wirklich mächtiges
Werkzeug, weil mit diesem Suffixbaum kann man zum Beispiel auch dieses
Problem, das ich letztes Mal erwähnt habe, wenn man zwei Strings hat
und man will den längsten gemeinsamen Substring bestimmen, kann man
zum Beispiel lösen und dabei viele andere Sachen auch.
Und man weiß nicht, also der wird jetzt nicht angewendet, weil er so
viel Platz verbraucht.
Dieser andere Index, dieser invertierte Index, der ist eben viele
Dinge, die man alltäglich braucht, wie Suchmaschine integriert.
Das heißt, dieser invertierte Index ist wahrscheinlich der
meistgebrauchte Index, den es gibt.
Und diese Konstruktionen aus den 70er-Jahren, die sind sehr
kompliziert.
Gab es dann auch Vereinfachungen, Ukonans Algorithmus in den 90er
-Jahren, aber das ist auch noch ziemlich kompliziert.
Und genau das, was man jetzt heute macht, ist viel einfacher.
Gut, und jetzt fangen wir mal an, diesen Algorithmus vorzustellen.
Erstens mal müssen wir uns da jetzt über das Alphabetmodell Gedanken
machen.
Es gibt verschiedene Alphabetmodelle.
Erstmal ein geordnetes Alphabet, da können wir nur durch einen
Vergleich herausfinden, ob eins gleiche Größe ist wie das andere.
Konstante Alphabetgröße, wenn man ein fixes Alphabet hat, wie DNA4,
dann ist das einfach fix und nicht abhängig von der Eingabegröße zum
Beispiel.
Und was wir jetzt nehmen, hier ist das grenzzahlige Alphabet.
Das ist ein Integer-Alphabet, das geht von 1 bis Sigma.
Und wenn man jetzt einfach einen Text hat, der nur ein geordnetes
Alphabet hat, dann kann man das überführen in ein ganzzahliges
Alphabet, in dem man jetzt einfach den Text hat.
Und jetzt sortiert man den, vergleichsbasiert, also der n log n, dann
hat man diesen sortierten Text.
Und jetzt schaut man einfach, okay, wenn jetzt ein Buchstabe gleich
ist wie der vorhergehende, dann kriegt er kein neues Alphabetsymbol.
Und wenn der größer ist, wie zum Beispiel dieses B ist größer als das
A, dann führen wir ein neues Alphabetsymbol ein.
Und das geht ja in linearer Zeit.
Das heißt, ich kann in linearer Zeit von meinem geordneten Alphabet,
oder eben linear plus Sortieraufwand, in dieses Integer-Alphabet
gehen.
Das heißt, dieses A wird eben 1 zugeordnet, das B ist das zweitgrößte,
wird 2 zugeordnet, das N ist das drittgrößte, wird 3 zugeordnet.
Also das ist eigentlich etwas sehr Einfaches.
Und wenn man jetzt nicht nur Buchstaben betrachtet, sondern eine Folge
von Buchstaben, also K-Buchstaben, dann können wir die drei Buchstaben
zusammenfassen und Lexikograph sortieren und können aber auch dieses
Tuppel durch den Rangersetzer in diesen Trippeln.
Also wenn ich irgendwie ein AAA habe und dann kommt irgendwann mal ein
AAB, dann ist das AAB natürlich größer als AAA und kriegt einen
kleineren Wertzugwieser.
Das heißt, das geht auch.
Okay, so und jetzt diese erste Idee für den Algorithmus ist folgende.
Ich habe ja Suffixe und die ordne ich jetzt ein.
Also einmal die Suffixe, die in geraden Positionen beginnen und die
Suffixe, die in ungeraden Positionen beginnen.
Und dann sortiere ich jetzt mal eine Menge.
Also zum Beispiel diese alle Suffixe, die ungerade sind.
Und naja, das sind quasi dann, also ungerade, das heißt ich nehme nur
zwei Tuppel an Buchstaben und das ist mein neues Alphabet.
Das ist höchstens so groß wie ein Halbe, dieses Alphabet, wenn ich
diese Transformation mache.
Und dann mache ich das dann auch regressiv.
Und dann habe ich aber immer die Hälfte vom Text, die Hälfte, die
Hälfte vom Text und so weiter.
Also ein Viertel, ein Achtel und so weiter.
Das heißt, der Aufwand ist dann insgesamt linear.
Okay, wenn ich das habe, dann kann ich auch die zweite Menge sortieren
mit Informationen aus der ersten Menge.
Heißt, ich ersetze jetzt, also wenn ich jetzt den...
Ich mache noch ein Beispiel dazu, jetzt mache ich es erstmal abstrakt.
Das heißt, wenn ich jetzt ein Suffix habe, eine gerade Position, zum
Beispiel Position 0, was die erste Position ist und es fängt mit einem
A an, dann sage ich, okay, ich ersetze dieses Suffix durch A und als
zweite Komponente brauche ich jetzt quasi, wie groß es ist in den...
Also quasi als nächstes folgt ein ungerades Suffix und da weiß ich den
Rang.
Also wie vergleiche ich das zu anderen ungeraden Suffixen.
Und das haben wir schon ausgerechnet durch den Suffixerei für diese
Teilmenge, also den SA1.
Und jetzt kann ich quasi alle ungeraden Suffixe vergleichen, indem ich
einen Radixsort mache über den ersten Buchstabe des Suffixes und den
Rang des darauffolgenden Suffixes.
Das heißt, das geht dann auch mit dem Radixsort in linearer Zeit zu
allem.
Das Problem ist jetzt, wenn ich diese, ich habe bei diese sortiert,
die ungeraden und die geraden und jetzt will ich das zusammenfügen.
Ich will einen Merge machen und will dann herausfinden, welches Suffix
ich jetzt nehmen muss, von der geraden und der ungeraden Menge.
Und ja, dann ist es schlecht, weil jetzt kann ich zwischen gerade und
ungerade, habe ich keine, kann ich nicht entscheiden, weil ich einmal
quasi, wenn ich quasi den Buchstabe habe und dann quasi den Rang vom
darauffolgenden habe und Buchstabe und Rang, dann lande ich immer in
unterschiedlichen Mengen drin und dann ist es, das geht nicht.
Das heißt, der Algorithmus, so wie der da steht, der geht nicht, weil
dieses, ich kann nicht, ich würde quasi immer wieder auf Sachen
kommen, von der einen Menge in der anderen Menge und die sind
unvergleichbar.
So, genau, das kann man lösen, indem man eine ganz komplizierte
Konstruktion macht und die ist so kompliziert, dass man sie auch hier
nicht machen könnte, aber glücklicherweise gibt es einen besseren
Ansatz.
Okay, das ist hier jetzt einmal ein Beispiel für das Berechnen von
diesem Suffixerei für die ungeraden Suffixe.
Also ich nehme jetzt, also der erste Buchstabe in Position 0, der
entspricht meinem geraden Suffix, den nehme ich einmal weg.
Dann kriege ich eine Zeichenkette, die jetzt mit einem ungeraden
Buchstabe anfängt oder Buchstaben in ungerader Position.
Ich nehme diese Zweitruppel, also A1, A1 und dann A hier am Ende, dann
kriegt man ein 0 ein.
Dann mache ich diese Lexikografische, die Umbenennung, das heißt,
dieses A0 ist kleiner als A1, also kriegt es die 1.
Dieses A1 und dieses A1 sind gleich, das heißt, als nächstes in der
Lexikografischen Folge kriegt es also 1 dazu und weil die gleich sind,
kriegt es auch der gleiche Buchstabe, das heißt, dieser Text wird
ersetzt durch einen Text der halben Länge und diesen neuen Symbolen.
Und die Symbole sind zwischen 0 und N in halbe höchstens.
Und dann geht man in die Rekursion und rechnet den Suffixerei auf und
hier habe ich jetzt quasi nur diese Suffixe in Lexikografische
Reihenfolge notiert.
Also diese 1 wäre am kleinsten, dann kommt die 2,1 und dann die 2,2,1.
Also das sind drei Suffixe, weil ich habe einen Text der Länge 3.
Und jetzt kommen wir in den Rückübersetzer und dann kriegt man heraus,
dass A, also diese 1 steht für das A hier, dieses 2,1 steht für A in A
und das ist 2,2,1 für A in A.
So, und das ist jetzt das Beispiel, wie man jetzt aus diesem SA von 1
das SA von 0 berechnet.
Ja, das ist ein Ding in Geraden.
Das ist unser Ergebnis, das man aus der Rekursion bekommt.
Und jetzt ersetzen wir hier jeden Suffix SI durch einen Tuppel.
Und das Tuppel enthält erstmal den Anfangsbuchstaben des Suffixes,
also SI, und dann den Rang des darauffolgenden Suffixes, das in der
Menge SA1 drin ist.
So, das heißt für das 0.
Suffix heißt es der erste Buchstabe vom textischen B an Position 0.
Und jetzt das darauffolgende Suffix ist das Suffix an Position 1.
Und für das haben wir schon ausgerechnet, dass dieses da an dritter
Position im Suffixerei von SA- entsteht.
Und die Position im Suffixerei, und das ist aber quasi von 1 an zählt,
nicht von 0 an, weil das 0, das braucht man immer als kleinstes
Symbol, darum fängt man hier nicht bei 0 an zu zählen.
Genau, das ist dann, das nennt man auch den Rang.
Also den Rang von dem darauffolgenden Suffix im Suffixerei der
ungeraden Suffixe.
Also das heißt, dieses Suffix hier wird durch den Rang ersetzt, was 3
ist, und in dem Fall von 2 und 4, Suffixen 2 und 4, fängt jeweils mit
N an.
Und genau, Position 2 wird durch A an A gefolgt, und das ist Nummer 2
im Suffixerei von dem Teilerei.
Und genau, das andere ist 1.
So, das heißt, wenn man jetzt das sortiert und dann Radixort macht,
genau, dann das B bleibt immer noch oben und wird von der 3 gefolgt.
Und die zwei andere Suffixe, die tauscht man jetzt, weil da hier was
Lexikografisch Kleineres dran steht.
Die 1 ist Lexikografisch Kleiner als die 2.
Und genau, das heißt, da kommt jetzt der Tausch, jetzt sind die auch
sortiert.
So, aber wie gesagt, dieses Mischen, das geht jetzt nicht so einfach.
Darum gibt es jetzt einen Trick.
Und der Trick ist, dass man das ganze Zeug nicht so aufteilt, dass ich
es gerade und ungerade aufteile, sondern man hat jetzt drei Klassen
und eine Klasse, genau, drei Klassen, weil ich jetzt die Suffixe
einteile in Klassen Modulo 3.
Das heißt, dieses SA12, das heißt nicht 12, sondern 12, das sind alle
Suffixe, die Modulo 3 ungleich 0 sind.
Also in Position 1, 2, 4, 5, 7, 8, 10, 11 und so weiter.
Und die Suffixe, die Modulo 3 gleich 0 sind, das sind einfach alle 0,
3, 6 und so weiter, alle restlichen Suffixe.
So, und was man dann macht ist, dann geht das Mischen nämlich einfach,
weil jetzt habe ich nämlich zwei Möglichkeiten, da einen Vergleich zu
machen, wenn diese Teilmengen jeweils sortiert sind.
Wenn ich ein Suffix habe, das Modulo 3 gleich 0 ist, dann kann ich
einmal ein Buchstabe nehmen und mit dem Rang von einem Suffix, von
einem Folge-Suffix habe, oder ich nehme zwei Buchstaben und habe den
Rang von dem Suffix, das 2 später darauf folgt.
So, und das heißt, ich habe zwei Möglichkeiten, in die andere Menge,
was in Rang in der anderen Menge zu bestimmen.
In der Menge der Suffixe, die Modulo 3 gleich 1 oder 2 sind.
Und das heißt, ich habe, wenn ich da ein Suffix von der Menge, von
einem Suffix, das gleich 0 ist, Modulo 3,
dann kann ich entweder ein oder zwei Buchstaben nehmen für den
Radixsort plus den Rang.
Und dann habe ich immer die Möglichkeit, gegen ein Suffix zu
vergleichen.
Genau, dann lande ich immer in der Menge der Suffixe, die Modulo 3
ungleich 0 sind.
Und in der Menge weiß ich die absolute Sortierung.
So, und dann geht es immer.
So, und da machen wir jetzt ein bisschen ein Beispiel dazu, wie das
genau funktioniert.
Dann verstehen wir es auch.
Genau, dann schalte ich um auf die Dokumentenkamera.
Genau,
das ist, sagen wir mal, als Beispiel.
Dann nehme ich jetzt genau den Text, der im Skript auf den Folien ist.
Das ist eine Ananas.
Ananas...
mit nochmal einem Na hinter dran, also Ananas.
Und dann kommt noch ein Punkt.
Und ich zeichne hier dann auch die Indizes, die Suffixe.
Genau, das geht also von 0 bis 8.
Wie man das sieht.
Und genau, was man da jetzt genau macht.
Also diesmal ist es so, dass...
den Text teilt man jetzt auf, in Suffixe, die Modulo 3 ungleich 0
sind.
Das heißt, ich kriege keine Tuppel an Buchstaben, sondern Trippel.
Und genau, das machen wir jetzt.
Ich habe jetzt quasi hier den ersten Buchstabe weggelassen.
Ich will ja Modulo 3 gleich 1 sein.
Da habe ich jetzt den ersten weggelassen.
Jetzt lasse ich 2 weg.
Fange also da an bei A, N.
A, N.
A, S.
Habe ich jetzt schon Fehler gemacht?
A, N.
S.
Jetzt muss ein Punkt...
Stopp.
N.
N, A, S.
Genau.
Und dann kommt Punkt und 0, 0.
So.
Ich mache immer diese 0 da hinten dran.
So.
Und genau, was man jetzt mit diesen Triplets macht.
Da will ich jetzt den...
Ich will jetzt Übersetzer in neue Symbole.
Das heißt, ich sortiere die Triplets jetzt mit Radixort.
Das heißt, ich habe hier...
Dieser Punkt ist jetzt leicht so grafisch kleiner wie jedes andere
Symbol.
Das heißt, ich kriege Punkt, 0, 0.
Und dann kommen die Triplets, die mit A anfangen.
Also A, N, A.
Das habe ich dann nochmal.
A, A, N, A, N, A.
Dann habe ich...
N, A und N.
Dann kommt da nochmal ein N, A und dann kommt aber ein S.
Und das Ding, das mit S anfängt, ist das lexographisch Größte.
So, jetzt machen wir die Benehmung.
Das ist das Kleinste.
Also kriegt das nicht die 0, sondern die 1.
Weil die 0 reservieren wir uns.
Dann kommt das A, N, A.
Das kriegt also die 2.
Und jetzt dieses A, N, A kommt nochmal.
Also kriegt das jetzt wieder die 2.
Und das N, A, N, das unterscheidet sich jetzt von A, N, A.
Also kriegt das eine 3.
Das nächste Triplet unterscheidet sich auch.
Das kriegt also die 4.
Und das nächste unterscheidet sich auch.
Das kriegt also die 5.
Und das heißt, jetzt ersetzen wir diese Triplets durch die neuen
Symbole.
Das heißt, hier schreibt man die 1 hin.
Das N, A, S, das kriegt eine 4.
Das A, N, A, das kriegt eine 2.
Da kommt auch eine 2 hin.
Ah, doch, genau.
Dann kommt hier eine 3 hin.
Und da kommt eine 5 hin.
Wunderbar.
Genau, jetzt bauen wir uns einen neuen Text auf.
Und dieser neue Text geht jetzt nur über die...
Genau, der ist jetzt quasi eine Wiederholung.
Also erstmal nochmal alle Suffixe, die Modulo 3, 1 sind.
Und dann dahinter hängen wir quasi auch alle Suffixe, die Modulo 3, 2
sind.
So, 4, 1.
Das ist unser neuer Text.
Und ich mache wieder, wie die Indizien sind.
3, 4, 5.
Und jetzt haben wir einen neuen Text.
Und der Text hat eine Länge, die ist nur zwei Drittel vom
vorhergehenden Text.
Und jetzt wenden wir einfach Rekursion an.
Um den Suffix-Reiher auszurechnen.
Und dieser...
Also Rekursive Aufruf...
oder Rekursive SA-Konstruktion...
ist dann hier.
Konstruktion.
So, und genau, was kommt da raus?
Also das kleinste Suffix hier drin...
das fängt bei Position 5 an.
Also ist das erste Zeichen 5.
Das nächste kleinere.
Wo fängt das an?
Bei Suffix Nummer 3.
Ja, hier.
Die 2 ist das nächste kleinste.
Also kommt hier Position 3 hin.
Weil da gibt es 2, die mit 2 anfangen.
Aber da fällt eine 4 drauf und hier eine 5 drauf.
Also wird der Algorithmus, wenn man Rekursiv aufruft...
hier die 3 zurückgeben und dann erst die 1.
Und der Rest ist jetzt einfach, weil die Zahlen ja alle
unterschiedlich sind.
Das heißt, ich schaue nur, wo die 3 steht.
Die steht in Position 0.
Ich schaue, wo die 4 steht.
Die steht in Position 4.
Und wo steht die 5?
Die steht in Position 2.
Das heißt, jetzt haben wir das Suffixerei konstruiert.
Und jetzt kann man sich quasi auch den lexographischen Rang
ausrechnen.
Dieser Suffixe.
Also lexographischen Rang unter den 1-2-Suffixen.
Also wieder nicht 12, sondern 1-2-Suffixen.
Und das heißt,
jetzt will ich quasi wissen, wo steht die 0.
Also von diesem 0-Suffix hier drin, wo steht das hier drin?
Und das steht an Position 3.
Das wäre quasi der lexographische Rang, wenn man diesen Rang quasi 0
-indiziert machen würde.
Aber diese 0, die wollen wir uns ersparen.
Wir wollen immer, dass 0 frei ist.
Das heißt, diese Frage, wo das Suffix 0 hier drin steht, ist mit 3
richtig beantwortet.
Wenn wir aber quasi alles um 1 shiften wollen, um die 0 frei zu
halten, addieren wir da 1 drauf.
Das heißt, das ist nicht 3, sondern dann 4 unter diesen Suffixen.
So, der nächste Eintrag.
Da fragen wir uns, wo steht das Suffix Nummer 1.
Aha, das steht hier.
Das ist in Position 2.
Und weil ich jetzt wieder das von 1 abmache, muss ich wieder 1
dazuzählen.
Naja, das ist 3.
Ich hoffe, das ist so klar.
Das nächste ist dann, wo steht die 3?
Die 3 steht in Position 0, 1, 2.
Wo steht die?
Habe ich einen Fehler gemacht?
Nein.
Wo steht die?
Ah, 0, 1, genau.
Das Nächste ist Nummer 2.
Also, wo steht die 2?
Die 2 steht in Position 5.
Ich zähle wieder 1 dazu, dann ist es 6.
So, wo steht die 3?
Die 3 steht in Position, vielleicht kann mir wer helfen?
Die 3 steht in Position 1.
Okay, und ich mache 1 dazu, das heißt, ich kriege 2.
Dann kommt die 4.
Ja, wo steht die?
Die 4 steht in Position 4.
Ich zähle 1 drauf, dann sind es 5.
Und wo steht die 5?
Die 5 steht in Position 0, dann kriege ich 1.
Also, es ist nichts anderes als die inversige Kombination plus 1.
Das ist der lexographische Rang unter den 1,2-Suffixen.
Genau, das sagt mir jetzt dieses erste Suffix in diesem neuen Text.
Dieses N-A-A-N-A-S-O.0, das hat den lexographischen Rang 4 in diesem
Suffixerei, das ich regressiv berechnet habe.
Von allen Suffixen, die Modulo 3 gleich 1 oder 2 sind.
Und das sagt mir auch zum Beispiel dieses Suffix 5.
0, 1, 2, 3, 4, 5.
Das ist das lexographisch Kleinste in dem Ding.
Also, da muss man sich das nochmal anschaulichen, was das heißt.
Ich schreibe jetzt nochmal auf, was es im Originaltext heißt.
Also, wenn ich den Originaltext jetzt nochmal nehme.
A-N-A-N-A-N-A-S-Punkt.
Das heißt jetzt, dass...
Und jetzt nehme ich mal eine Farbe.
Ich mache zum Beispiel jetzt blau.
Hoffentlich sieht man das.
Genau, diese 4, die entspricht jetzt...
Ja, das ist quasi der Rang.
Das ist der Rang des ersten Suffixes.
Und das erste Suffix ist das Suffix, das quasi hier an Position 1
anfängt.
Das nächste Suffix, das wir hier haben, das ist das Suffix, das an
Position 1 plus 3.
Ja, anfängt.
Das heißt, das ist das Suffix an der Stelle 4.
Ja, also 0, 1, 2, 3, 4.
Und das hat dann den Rang 3.
Und das nächste ist das, das an Position 6 anfängt.
Ja, und das hat Position 6.
Ja, das heißt, diese Ränge, die ordne ich jetzt original den Suffixen
zu.
So, und das sind quasi alle, die Modulo 3 gleich 1 sind, diese
Suffixe.
Und jetzt kommen die, die Modulo 3 gleich 2 sind.
Das heißt, dieses da, mit Rang 2, das entspricht diesem Suffix da
oben.
Also wenn man quasi diesen Text aneinander hängt.
Und das heißt, das steht jetzt, der Rang steht jetzt hier.
Ja, das ist da.
Und jetzt, das nächste ist dann wieder, weil es Dribble sind, gehen
wir wieder 3 weiter.
Ja, steht dann quasi hier eine 5.
Und hier steht eine 1.
Genau.
Und, ja.
Und das, genau, wenn das jetzt quasi regressiv so weiter geht, dann...
sieht man, dass man quasi alles auch hier, das Zeug, wenn man sagt,
das geht in linearer Zeit, dann kann man auch diese Zuordnung wieder
in linearer Zeit machen.
Genau.
So, und jetzt, als nächstes, jetzt haben wir quasi eine Aussage über
diese Suffixe, die Modulo 3 gleich 0 oder 1 sind.
Und was man dann als nächstes macht, ist, dass man die Suffixe
berechnet.
Also Berechnung, die Modulo 3 gleich 0 sind, also den SA 0.
Ja, was kann man da machen?
Also wie gesagt, man setzt jetzt, also unser Text war ja A, N, A, N
und so weiter.
Das heißt, das Suffix 0, ich schreibe das mal so, das Suffix 0, das
entspricht jetzt einem Tuppel.
Und zwar das Tuppel A4.
Ja, ich habe A und dann den Rang 4 in den sortierten Suffixen, die
Modulo 3 und gleich 0 sind.
Dann das Suffix Nummer 3, das entspricht einem N und dem Rang 3.
Ja, und dann habe ich auch noch das Suffix Nummer 6 und das entspricht
also A und 6.
So, und mit der Information kann ich jetzt da wieder einen Radixsort
machen.
Und das gibt mir jetzt, dass ich jetzt, wenn ich das sortiere, dieses
A4, dann kommt dieses A6 und dann kommt N3.
So, und jetzt kann ich diese Suffixe, die ich hier habe, die
entsprechen jetzt, ja, ich kann jetzt quasi wieder zuweisen, dieses
A4, das entsprach ja immer noch Suffix Nummer 0 und das war Suffix
Nummer 6 und das war Suffix Nummer 3.
So, und ich kann das jetzt auf zwei Weisen ausdrücken.
Ich kann entweder sagen, das ist ein Tuppel A und 4 oder ich kann das
auch ausdrücken als ein Trippel.
Ja, also das ist Suffix 0, kann ich jetzt auch ausdrücken durch A, N,
ich habe die falsche Farbe, so, ich schreibe das nochmal hin, dass ich
das durch Trippel A ausdrücken kann.
Und jetzt wollen wir gleich sehen, warum das wichtig ist.
Genau, jetzt machen wir da das in, genau, also ich habe die andere
Ränge, die in Rot gemacht habe und jetzt kann ich, das 0 des Suffixes
kann ich auch ausdrücken durch A, N und jetzt den Rang 2.
Ja, so, und dieses andere Suffix, dieses 6, das 6 des Suffix kann ich
auch ausdrücken durch Suffix Nummer 6, das ist ein S, dann ist das ein
Punkt und dann wäre das 0, weil da folgt ja nichts mehr und dieses
dritte Suffix kann ich ausdrücken durch ein N, ein A und 5, 5 und N
und A, N und A.
So, und genau, das ist wichtig, dass ich das durch zwei Arten
ausdrücken kann, weil ich will jetzt diese Suffixe, die ich hier habe,
mischen mit den Suffixen, die ich hier oben ausgerechnet habe.
So, das heißt, genau, jetzt kommt das Mischen und genau, das machen
wir auf einen neuen Blatt.
Also, genau, jetzt halten wir mal diese Suffixe, die wir durch diese,
weil diese Suffixe, die Modulo 3 gleich 0 sind und genau, dann
schreibe ich nochmal auf die andere Suffixe, die im Text, das war die
Suffixe, machen wir die mal auf die Seite, das war Suffix 8, 2, 4, 1,
5 und 7.
Also, das kommt aus, ja,
6, 0, 3, 0, 3, 6,
ja, A, S, 1, genau.
Das ist hier, ja, genau, A, S und dann, genau, da kommt eine 1, ich
bin 1 verrutscht.
Gut, genau, so und jetzt, genau, jetzt hole ich mir alle Suffixe, die
Modulo 3, ja, stopp, genau, die Modulo 3 ungleich sind.
Das heißt, einmal kriege ich das in Position 8.
Da gibt es jetzt zwei Arten, wie man jetzt die Position beschreiben
kann.
Also, diese Position, wo ich jetzt sage, die ist jetzt quasi im
Originaltext und das kann man natürlich, also das was quasi an 1
steht, oder quasi an 1 im Originaltext, das war in unserer Rekursion,
war das eigentlich in Position 0, ja, das was an Position 4 stand, war
an Position 1, denn man zahlt ja immer 3 dazu, das war in Position 2,
das war, genau, dann kommt die 2, die war ja in Position 3, dann kommt
die 5 war in Position 4 und die 8 war in Position 5 von unserem Text.
Ja, wenn man diese Transformation hier macht, dass man die
aneinanderreiht und quasi immer 3 Zeichen hervorspringt, ja, also das
heißt, dieses ist da, das wäre quasi in unserer Rekursion und das ist
im Originaltext, aber das kann man natürlich in konstanter Zeit
umrechnen, diese 2 Sachen, aber ich würde es quasi nicht darauf
eingehen.
So, das heißt, genau, jetzt hat man die 2 Möglichkeiten, also erstmal
dieses an Position 8, wenn man jetzt irgendwie den Originaltext noch
hat, sieht man das, dann hat man quasi dieses Punkt und 0 oder ich
kann das einfach durch Punkt 0 und 0 ausdrücken, dieses, genau, dieses
an Position 2, was war das?
0, 1, 2, genau, das war an A, genau, das kann ich jetzt, aha, genau,
jetzt kommt der Trick, das kann ich jetzt.
Genau, wenn man jetzt nur durch A ausdrücken würde und dann würde man
in der Menge von Suffixen lernen, die Modulo 3 gleich 0 sind und das
wollen wir nicht, weil dann kann man es nicht vergleichen und darum
drücken wir das jetzt aus durch A, N und dann jetzt dieses Suffix 3.
Das heißt, ich habe jetzt eigentlich immer eine Möglichkeit, immer ein
Shift, entweder 1 oder 2, dass ich wieder drin lande in der Menge
selbst, wo ich die absoluten Ränge habe.
Das heißt, dieses 4, das wäre 0, 1, 2, 3, 4, das wäre A und 5, also
ich mache das jetzt immer mit einer Farbe, also Rot ist immer, was das
Modulo 3 gleich 2 war und das Blau ist für Modulo 3 gleich 1.
So, dann mache ich das jetzt mal, schreibe ich da mal, genau, das ist
N, genau, N und das wird eine 2, und hier kommt N, A und 6 und dann
kommt hier bei 7 ein S, genau, und jetzt kommt bei dem 1, nach dem N
kommt eine 2, bei 7 kommt eine 1 und genau, bei der 5, 0, 1, 2, 3, 4,
5 und N, A kommt eine 6.
So, okay, und jetzt kann ich den Merging Step elegant lösen, weil ich
habe jetzt für die Suffixe, die Modulo 3 gleich 0 sind, habe ich jetzt
immer zwei Möglichkeiten.
Ich kann das immer ausdrücken, als ein Tuppel, das endet mit dem Rang
vom Suffix, das Modulo 3 gleich 1 ist, oder mit einem Trippel, das
endet mit dem Rang vom Suffix, das Modulo 3 gleich 2 ist.
Das heißt, jetzt habe ich quasi immer eine Möglichkeit, den Vergleich
zu machen, um zu entscheiden.
Das heißt, ich habe jetzt die zwei Mengen und jetzt kann ich in
konstanter Zeit einen Vergleich machen.
Das heißt, ich habe dieses Suffix 8, das vergleiche ich jetzt mit dem,
das ist lexographisch kleinste, das ist auch lexographisch kleinste,
in dieser Menge und das in der Menge.
Das heißt, in dem ersten Vergleich hätte ich jetzt die Möglichkeit,
die zweite Möglichkeit, die brauchen wir eigentlich gar nicht hier,
das können wir jetzt löschen, kann ich jetzt vergleichen.
Und natürlich, dieser Punkt ist kleiner als das A, also wäre das
Suffix 8 das kleinste, das heißt, das können wir uns jetzt streichen
und dann gehen wir hier jetzt weiter.
Das habe ich, das Suffix Nummer 2, das entspricht A, N, 3 und das
vergleiche ich jetzt dann hier mit der zweiten Möglichkeit als Triple.
Und da habe ich A, N und jetzt habe ich da 2, das heißt, das Suffix
Nummer 0 kommt erst.
Dann habe ich hier die 6 und dann nehme ich jetzt wieder die zweite
Möglichkeit, um das zu vergleichen und dann kommt hier A und dann
kommt A auch und dann kommt S.
Das sind immer Triple, die kann ich immer in konstanter Zeit
vergleichen und hier, das S ist größer, das heißt, ich schreibe dann
erst die 2, bin da fertig.
Dann habe ich hier, genau, dann habe ich jetzt hier einen Tuppel und
nehme ich dann die Darstellung und da ist es so, das A ist gleich,
okay, aber die 6 ist größer, also kommt dann erst hier dieses Tuppel
und das entspricht der 4.
Dann kommt das Nächste, das ist hier ein N und da ist es immer noch
ein A, das heißt, ich nehme noch die 6, da habe ich die 1, entspricht
dem N und 2, da habe ich N und 3, okay, das heißt, da kommt erst die
1.
Dann kommt, genau, jetzt kommt hier N und A und 6 für das Suffix
Nummer 5 und da ist N und A und 5, also kommt dann erst die 3.
Okay, jetzt ist die Menge leer und jetzt kann ich quasi die andere
Menge anhängen, das ist 5 und 7.
Und das heißt, jetzt habe ich den Suffixerei komplett berechnet und
jetzt das Mischen, die Phase, die geht natürlich auch in linearer
Zeit, weil ich jedes Mal mit konstantem Aufwand diesen Vergleich
machen kann, weil ich diese Triples habe.
Und jedes Mal für die Menge zwei Möglichkeiten habe, das darzustellen
und dann quasi immer einen Vergleich machen kann, wo ich das Ergebnis
schon vorher weiß, weil es immer in der Menge S1, S2 liegt.
Also das heißt, wenn man das einmal verstanden hat, dann kann man auch
das Beispiel genauso ausrechnen, ohne große Hilfe.
Gut, dann wechsle ich wieder auf den Laptop, den Folien.
Okay, also hier wäre das nochmal dran, das Beispiel, nicht interaktiv.
Also man sortiert diese Triples, findet die lexographischen Namen,
dann geht man in die Diskussion für die Suffixe, die Modulo 3 ungleich
0 sind.
Dann kriegt man die Lösung der Suffixerei, von da kriegt man die
Ränge.
Und genau, den Radixsort, den machen wir hier least significant digit
Radixsort.
Das heißt, wenn man so ein Triplet hat, dann sortiert man erst nach
der letzten Position und sortiert dann weiter stabil nach der zweiten
Position und auch nach der dritten Position.
Und dann ist das eigentlich klar, dass das richtig sortiert.
Und genau, es gibt eben noch viele Tricks, wie man das effizient
macht.
Das sind jetzt alles technische Details.
Hier ist jetzt noch Folge.
Hier kommt dann nochmal ein Beispiel.
Und genau, da ist jetzt nochmal, dass man quasi ersetzt die Buchstaben
durch die Ränge.
Und genau, die Analyse, die mache ich jetzt mal schnell in 5 Minuten.
Also es heißt, die Komplizität ist so, dass ich gehe in der
Rekordsurfe Aufruf mit zwei Drittel der Menge.
Das heißt, ich habe einen linearen Aufwand 10 mal n und dann habe ich
jeweils immer zwei Drittel und auch mit der Konstante davor.
Und wenn man das aufsummiert, kann man sich einfach als geometrische
Summe aufschreiben.
Also kommt da 1 durch 1 minus das zwei Drittel und das gibt dann also
1 durch ein Drittel und dann der Kehlwert davon ist das 3.
Daher kommt dann die 3 in dem Taumal.
Das heißt, das ist kleiner als 3 mal cn.
Vielleicht mache ich das nächstes Mal noch.
Das sind die verschiedenen Schritten vom Code.
Und das kann man dann auch noch verallgemeinern.
Jetzt haben wir das gemacht für Triples, das geht aber auch für 7
Tuppel, 9 Tuppel und so weiter.
Da muss nur die Eigenschaft sein, dass ich dann diese Menge, die ich
da raussuche, dass ich immer eine Möglichkeit habe, aus der anderen
Menge in die andere Menge zu springen mit einem Offset.
Okay, genau.
Aber jetzt übernimmt der Michael die Übung und wir sehen uns nächstes
Jahr wieder.
Dankeschön.
Gut, heute schauen wir uns zwei Themen an.
Einmal Rekurrenzrelationen und in Blaze Multi-Key-Quicksort.
Die Rekurrenzrelationen, die haben jetzt mit dem Thema von dieser
Woche eigentlich nichts zu tun.
Das ist letztendlich noch Stoff, den ihr braucht, um parametrisierte
Algorithmen gut analysieren zu können.
Also bei parametrisierten Algorithmen, da habt ihr ja oftmals eine
Aufgabenstellung.
Okay, denkt euch irgendwie einen Algorithmus aus und dann habt ihr da
in der Laufzeit irgendwie ein N und ein K.
Und in der Regel habt ihr dann so einen rekursiven Algorithmus, wo ihr
auf einem Level irgendwie Zeit verbraucht.
Die hängt oftmals von N ab.
Und dann habt ihr aber eine bestimmte Anzahl von Level, die hängt von
K ab.
Und wie viel Level ihr habt und wie viel Knudeln es dann in dem Baum
gibt, das könnt ihr letztendlich durch eine Rekurrenzrelation
ausdrücken.
Um dann aber wirklich zu wissen, was die Laufzeit von diesem
Algorithmus ist und ob der Algorithmus Fixed Parameter Tractable ist,
braucht ihr die letztendliche Laufzeit, um zu zeigen, okay, ihr könnt
die Laufzeit in zwei Funktionen aufteilen.
Die eine Funktion hängt von N ab und die andere Funktion hängt von K
ab.
Und dafür gibt es eben die Rekurrenzrelationen und speziell für
Rekurrenzrelationen, die von zwei Parametern abhängen, N und K, und in
solch einer Form hier ausgedrückt werden können, gibt es ziemlich
geschickte Methoden, um die Gesamtlaufzeit in der geschlossenen Form
auszurechnen.
Was ihr habt, ist dann am Anfang von eurer Analyse eben eine Funktion
oder eine Rekurrenz, T von N, K, und die drückt ihr aus durch weitere
Funktionen, die mit dem gleichen N arbeiten, aber in der Rekursion ein
kleineres K nutzen.
Und für jede dieser rekursiven Aufrufe könnt ihr noch einen konstanten
Faktor A1 bis AJ angeben und auf jedem Level könnt ihr sagen, okay,
wir haben eine Arbeit F von N.
Es gibt dann drei Methoden, um so eine Rekurrenz zu lösen mit einem
Verzweigungsvektor.
Das ist die einfachste Variante, da habt ihr ziemlich viele
Einschränkungen und das könnt ihr dann aber einfach in der Tabelle
nachschauen.
Die zweite Variante, da erzeugt ihr ein Polynom, löst die Nullstellen
auf und kriegt dann eine Lösung, die sieht dann aus wie O von K hoch M
minus 1 und Alpha hoch K und das Alpha ist eben genau die größten
Nullstelle und M ist die Vielfachheit von dieser Nullstelle.
Und mit der dritten Methode könnt ihr inhomogene Rekurrenzrelationen
auflösen.
Da habt ihr dann am wenigsten Einschränkungen.
Ihr könnt nämlich in den inhomogenen Rekurrenzrelationen einmal
Vorfaktoren A1 bis AJ angeben, die nicht 1 sein müssen und zusätzlich
könnt ihr eben eine lokale Arbeit ebenfalls in die Rekurrenzrelation
mit einrechnen.
Dann gehen wir einfach mal Beispiele für alle drei Verfahren durch.
Das einfachste Verfahren, wie gesagt, ist das einfachste.
Einfach Verzweigungsvektoren erstellen.
Die Verzweigungsvektoren haben die Form K1 bis KJ und das lest ihr
letztendlich aus der Rekurrenzrelation ab, die ihr selbst erstellt
habt.
Guckt in der Tabelle nach, kriegt dann Alpha raus und habt dann am
Schluss eine Laufzeit nach oben beschränkt von Alpha hoch K.
Ein Beispiel hier ist jetzt zum Beispiel die Rekurrenzrelation T von N
K ist gleich T von N K minus 1 plus T von N K minus 1.
Da ist in beiden Fällen K1 und K2, äh K1 und K2 1.
Also habt ihr einen Verzweigungsvektor 1 1.
Das guckt ihr in eurer Tabelle nach.
Da kriegt ihr dann einen Wert für Alpha von 2 raus und habt dann eine
Gesamtlaufzeit von 2 hoch K.
Dieses Verfahren könnt ihr halt nur benutzen, wenn die Vorfaktoren A1
bis AJ1 sind und ihr dürft auch eigentlich keine lokale Arbeit
verrichten, beziehungsweise, das ist nicht ganz gerecht, die lokale
Arbeit muss konstant sein.
Sobald das eine Funktion ist, die von N abhängt, log N oder N hoch
irgendwas, könnt ihr diese Variante nicht mehr benutzen.
In diesem Fall, wenn die AIs nicht gleich 1 sind, ihr aber immer noch
keine lokale Arbeit habt, dann könnt ihr das Verfahren mit erzeugenden
Polynomen benutzen.
Was ihr da macht ist letztendlich, ihr macht eine Aussage, der Ansatz
ist, dass ihr sagt, die Funktion oder die Rekurrenz T von NK sieht
irgendwie so aus wie X hoch K und das setzt ihr gleich mit der
Rekurrenz, die ihr aufgestellt habt und versucht dann die Nullstellen
zu finden.
Das ist genau was ihr dann in der Zeile da unten drunter seht, da habt
ihr das X hoch K und dann zieht ihr eure Rekurrenz ab, das muss gleich
0 sein.
Ihr bestimmt die betragsmäßig größte Nullstelle Alpha mit der
Vielfachheit M und dann bekommt ihr eben genau diese Laufzeitgarantie
raus.
Ein Beispiel mit der gleichen Rekurrenzrelation.
Unten drunter habt ihr dann das Polynom, welches ihr nach 0 auflesen
möchtet.
In diesem Fall dann eben X hoch K gleich X hoch K minus 1 plus X hoch
K minus 1 und das ist eben äquivalent zu X hoch K minus 1
multipliziert mit X minus 2 gleich 0 und die größte betragsmäßige
Nullstelle ist die 2 und deswegen habt ihr eine Laufzeitgarantie.
Von 2 hoch K.
Gibt es dazu Fragen?
Also ich denke das Verfahren ist ganz straightforward.
Man wendet einfach hier dieses Rezept an und bekommt seine Laufzeit.
Wir haben jetzt aber immer noch die Einschränkung, dass wir nur
konstant viele lokale Arbeit verrichten dürfen.
Was wir da nämlich jetzt genau berechnen haben, sind so ungefähr die
Anzahl an Knoten und wenn die Arbeit pro Konoden jetzt konstant ist,
ist die Laufzeit eben genau die Anzahl an Knoten und wenn wir jetzt
zusätzlich noch erlauben, dass wir eine lokale Arbeit von F und N mit
beliebigen Funktionsdefinitionen zulassen, dann müssen wir
letztendlich einfach zu der Anzahl an Knoten, die wir durch ein
Lösungsverfahren für homogene Rekurrenzen, berechnen, da müssen wir
letztendlich einfach noch die lokale Arbeit dazu multiplizieren.
Da haben wir dann auch die Wahl, was für ein Verfahren wir für
homogene Rekurrenzen benutzen, um dann später eben diese inhomogene
Rekurrenz mit der nicht konstanten lokalen Arbeit auflösen zu können.
Ein Beispiel hier, wir haben jetzt wieder das gleiche Beispiel, aber
wir haben eine lokale Arbeit von N und können mit jedem beliebigen
Verfahren die homogene Lösung berechnen, das ist dann 2 hoch K und da
multiplizieren wir dann einfach die lokale Arbeit mit N dran und
bekommen dann eine obere Schranke für die Laufzeit von 2 hoch K mal N.
Und dafür können wir dann letztendlich auch einen Test machen, indem
wir einfach in die Rekurrenz, die wir oben definiert haben oder die
uns hier in diesem Beispiel gegeben ist, da setzen wir einfach unsere
Lösung ein.
Hier auf der rechten Seite und das muss eben genau die Laufzeit sein,
die wir für dieses T von NK ausgerechnet haben und wenn wir das dann
auflösen, also hier haben wir die rechte Seite der Rekurrenz ersetzt
durch unser Ergebnis.
Und wenn wir das auflösen, bekommen wir, also wenn wir durch N teilen,
dann haben wir die linke Seite der Rekurrenz ist dann 2 hoch K und auf
der rechten Seite haben wir dann dieses N rausmultipliziert und dann
haben wir auf der linken Seite 2 hoch K ist gleich 2 hoch K minus 1
plus 2 hoch K minus 1, jeweils im O-Kalkül.
Und 2 hoch K minus 1 plus 2 hoch K minus 1 ist eben genau auch 2 hoch
K.
Und damit hat unser Test dann funktioniert.
Als zweites möchte ich nochmal zum einen Multi-Key-Quicksort
wiederholen.
Das wurde in der Vorlesung gestern durchgenommen und gleichzeitig
möchte ich euch erklären, wie man das dann in place implementieren
kann.
Also Multi-Key-Quicksort war bei mir so, da habe ich erstmal gestutzt,
ehrlich gesagt, als ich da das erste Mal in der Vorlesung stand.
Bei Multi-Key-Quicksort habe ich mir irgendwie sowas überlegt, ok man
wählt irgendwie mehr Pivots als 1 und z.B.
2 Pivots und teilt dann nicht in einen kleinen Bereich und einen
größeren Bereich, sondern man teilt dann in 3 Bereiche, so wie beim
Multi -Key-Samplesort, einen Bereich, der kleiner ist als das kleinere
Pivot, einen Bereich, der zwischen den 2 Pivots liegt und einen
Bereich, der größer ist als das Pivot.
Das ist hier jetzt aber nicht gemeint.
Das sieht man auch daran, es gibt nämlich eine andere Bezeichnung für
diesen Algorithmus der Three-Way-Radix-Quicksort.
Und zwar ist die Aufgabe hier, Elemente zu sortieren, die mehrere
Schlüssel haben.
Also allgemein kann man sich das einfach vorstellen, man möchte
Objekte sortieren und die Objekte haben mehr als eine lokale Member
-Variable und man möchte einfach lexikografisch sortieren.
Was man da machen würde, ist, man sortiert einfach erstmal nach der
ersten Member-Variable, dann nach der zweiten, dann nach der dritten
und so weiter.
Und dieses Prinzip können wir eben auch auf Strings anwenden, weil
Strings kann man eben auch als Objekte sehen, die haben halt nicht
konstant viele Member-Variablen, sondern jeder String hat halt
unterschiedlich viele Member-Variablen und jede Member-Variable ist
letztendlich ein Zeichen.
Und das Ziel ist eben, diese Strings dann zu sortieren.
Und der Algorithmus funktioniert ähnlich wie bei Quicksort, nur dass
wir hingehen und zuerst nach dem ersten Zeichen sortieren und sobald
wir nach diesem ersten Zeichen sortieren, nach dem zweiten Zeichen
sortieren, dann nach dem dritten und so weiter.
Und nach dem ersten Zeichen sortieren wir nicht wie beim normalen
Quicksort, dass wir einfach in einem Bereich unterteilen, der kleiner
gleich dem Pivot ist und im Bereich, der größer als dem Pivot ist,
sondern wir teilen in drei Teile auf.
Wir teilen in einen Teil auf, der ein Zeichen hat, kleiner ist das
Pivot, ein Bereich, der Zeichen hat, größer ist das Pivot und ein
Bereich, ein Bucket, welches eine Partition enthält mit Strings, die
an dieser jeweiligen Stelle, die wir uns gerade anschauen, das gleiche
Zeichen haben wie das Pivot.
Hier haben wir nochmal den Pseudocode für die allgemeine Variante.
Man wählt sich einfach beim normalen Multi-Key Quicksort ein Pivot und
teilt dann in drei Partitionen auf und zu Beginn hat man oder wir
haben hier eine Variable i, die eben genau sagt, bei welchem Zeichen
sortieren wir jetzt gerade.
Am Anfang ist es mit 0 initialisiert, also wir sortieren nur nach dem
ersten Zeichen und betrachten dann auch beim Vergleich nur dieses
jeweilige Zeichen der Strings, vergleichen das, wenn das Zeichen
kleiner ist als das Zeichen im Pivot anstelle i, dann kommen wir in
die erste Partition, wenn es größer ist, in die dritte Position, wenn
es gleich ist, in die zweite Partition.
Und wenn wir in der zweiten Partition sind, haben wir ja schon nach
dem i-den Zeichen sortiert, weil alle Elemente in dieser Partition
sind gleich an der Stelle i, also die Zeichen an der Stelle i und
deswegen können wir dann gleich nach dem nächsten Zeichen sortieren.
Bei der ersten Partition und der letzten Partition, da können wir das
nicht garantieren, da wir einfach in diesen Partitionen Strings haben,
die an der Stelle i einfach nur Zeichen haben, die kleiner als das i
-den Zeichen im Pivot sind, deswegen müssen wir nochmal nach dem i-den
Zeichen rekursiv sortieren.
Dazu ein Beispiel.
Wir haben hier eine Menge von Strings, die wir sortieren wollen.
Wir gucken uns am Anfang das erste Zeichen an, wählen ein Pivot und da
wird auch nur das erste Zeichen für diesen Rekursionslevel verwendet.
Was wir jetzt machen wollen, wir generieren drei Partitionen.
Eine linke Partition, das sind alle Elemente, alle Strings drin, die
als erstes ein Zeichen haben, kleiner als h.
Eine rechte Partition, das sind alle Strings drin, die ein Zeichen an
der ersten Position haben, die größer als h sind.
Und eine Partition, eine Equal Partition mit Strings, die an der
ersten Partition das Zeichen h haben.
Der Algorithmus funktioniert dann ganz straight forward, dass wir die
Partitionierung uns berechnet haben und dann führen wir drei
Rekursionen aus auf dem linken Teil, auf dem mittleren Teil und auf
dem rechten Teil.
Und auf dem linken Teil sortieren wir jetzt nochmal nach dem ersten
Zeichen.
In der Equal Partition sortieren wir jetzt nach dem zweiten Zeichen,
weil wir ja schon nach dem ersten Zeichen sortiert haben.
Und in der rechten Partition müssen wir jetzt nochmal nach dem ersten
Zeichen sortieren.
Dann gibt es ein normales Quicksort auch schon in Place.
Ich glaube, das wurde auch in Algorithmen 1 erklärt.
Ich wiederhole das einfach nochmal kurz.
Was wir machen, wir wollen beim normalen Quicksort einfach in Elemente
oder in zwei Partitionen aufteilen.
In der linken Partition kleiner gleich den Schlüssel und in der
rechten Partition größer als den Schlüssel.
Und der Algorithmus dafür ist straightforward.
Wir haben links einen Teil, der schon kleiner gleich dem Schlüssel ist
und rechts auch einen Teil, der schon größer ist als der Schlüssel.
Und zwei Zeiger, die genau auf die Ränder zeigen und im mittleren
Bereich, den wir noch nicht partitioniert haben.
Und wir laufen einfach von der Position A nach rechts, bis wir ein
Zeichen haben, welches in die rechte Partition muss.
Und vom Zeiger B laufen wir nach links, bis wir ein Element finden,
welches in die linke Partition gehört.
Und dann sorten wir diese beiden Elemente.
Und genau zu Beginn wird eben dieses Pivot ganz am Anfang verschoben.
Das Pivot wird verschoben und dann laufen wir mit dem Zeiger A und B
nach rechts.
Jetzt haben wir hier diese 41 gefunden, das ist größer als das Pivot,
das muss nach rechts.
Und genauso haben wir hier jetzt eine 14 gefunden, die muss nach
links.
Dann machen wir einen Swap und dann führen wir den Algorithmus einfach
fort, bis sich die beiden Zeiger überkreuzen.
Jetzt wollen wir das gleiche mit Multi-Key-Quicksort machen, auch in
place.
Und da verfolgen wir einfach eine ähnliche Variante.
Was wir jetzt machen, wir teilen die Elemente wie vorher eben auch in
kleiner, gleich und größer Teil auf, abhängig von dem Pivot.
Und merken uns aber vier Zeiger.
Wir haben einen Zeiger A und einen Zeiger D, die beschränken nach
links und nach rechts die Elemente, die gleich dem Pivot sind.
Und einen Zeiger B und einen Zeiger C.
Und zwischen den Zeiger A und B im Array stehen die Elemente, die sind
kleiner als das Pivot.
Und zwischen Zeiger C und D die Elemente, die sind größer als das
Pivot.
Und was wir dann am Schluss machen wollen, ist eben, diese Partition
mit den Elementen kleiner als das Pivot muss am Anfang verschoben
werden und die Partition mit den Elementen größer als das Pivot muss
ans Ende verschoben werden.
Und was wir dann wollen, ist, dass die Elemente gleich dem Pivot in
der Mitte stehen.
Da gibt es auch nochmal ein Beispiel dazu.
Wir gucken uns zu Beginn das erste Zeichen in den Strings an, wählen
ein Pivot, in diesem Fall hier jetzt H, laufen von links nach rechts
und suchen uns ein Element, welches größer gleich dem Pivot ist und
vorher verschieben wir das Pivot an den Anfang.
Wir fangen jetzt an, von links nach rechts zu laufen.
Jetzt haben wir hier mit dem Zeiger B ein H gefunden und das können
wir jetzt einfach in die Equal-Partition nach links swappen.
Und wir laufen weiter mit dem Zeiger B, bis wir ein Element größer als
H gefunden haben.
Das ist jetzt hier zum Beispiel das M und das wollen wir nach rechts
swappen.
Und jetzt müssen wir rechts erstmal ein Element suchen, welches nach
links geswappt werden kann.
Erstmal haben wir zu Beginn ein Element H gefunden und dieses H muss
in die rechte Equal-Partition verschoben werden.
Danach haben wir dieses A gefunden, das muss nach links verschoben
werden und das können wir genau mit diesem M swappen.
Und so führen wir den Algorithmus fort.
Und jetzt haben wir aber eigentlich noch nicht, was wir wollen, weil
wir haben jetzt hier in der Links eine Equal-Partition, dann haben wir
eine kleine Partition, eine größere Partition und nochmal eine Equal
-Partition und jetzt verschieben wir einfach die Equal-Partition in
die Mitte und die kleine Partition nach links und die größere
Partition nach rechts.
Und dann führen wir eben die Rekursion auf.
Einmal auf dem linken Teil wieder eine Sortierung nach dem ersten
Zeichen, auf dem mittleren Teil eine Sortierung jetzt nach dem zweiten
Zeichen und in der dritten Partition nochmal eine Sortierung nach dem
ersten Zeichen.
Das war es letztendlich auch schon zum In-Place-Multi-Key-Quicksort
-Algorithmus.
Nicht ganz einleuchtend am Anfang ist vielleicht, warum die Laufzeit
von einem Algorithmus Betrag oder Anzahl der Schlüssel, Log-Anzahl der
Strings plus D, wobei D hier jetzt die Länge der unterscheidenden
Präfixe ist.
Wir können uns jetzt hier im Ergebnis mal anschauen, was sind
unterscheidende Präfixe.
Präfixe beginnen ja immer am Anfang von einem String und unterscheiden
bedeutet, wir gucken uns benachbarte Strings an und gucken uns den
kürzesten Präfix an, sodass sich der String von beiden Nachbarn
unterscheidet.
Also wenn wir uns jetzt hier die Equal-Partition anschauen, dann ist
das erste Zeichen auf jeden Fall nicht unterscheidend, weil das bei
allen gleich ist.
Für diese beiden Strings hier, die mit H beginnen und dann mit A
weitergehen, sind die ersten beiden Zeichen auch nicht unterscheidend,
aber dann das nächste Zeichen unterscheidet diese beiden Strings.
Also für diese beiden Strings sind die ersten drei Zeichen jeweils
unterscheidend und das sind dann die unterscheidenden Präfixe jeweils
der Länge 3.
Und dieses D in dieser Abschätzung hier ist eben die Summe der Längen
aller unterscheidenden Präfixe.
Und jetzt ist die Frage, warum ist die Laufzeit damit jetzt wirklich
beschränkt und warum ist diese Beschränkung korrekt?
Naja, letztendlich haben wir zwei Fälle.
Also dieser linke Teil hier, der sieht schon ähnlich aus wie die
normale Laufzeit von Quicksort.
Und daher kommt dieser linke additive Term von der Laufzeitschranke
auch, weil alle Vergleiche, die man auf diesem Level hier jetzt
gemacht hat, für Strings, die entweder in die kleiner Partition kommen
oder in die größere Partition, die bezahlen wir mit diesem Blockbetrag
S.
Und das ist genau der Aufwand, den man beim normalen Quicksort auch
machen müsste.
Jetzt hat man noch einen zusätzlichen Aufwand für diese Equal
-Partition hier, weil man hier ja nicht in der Rekursion irgendwie
weiter nach unten, also in der Rekursion vergleicht man die
Elemente...
Okay, ich versuche es anders auszudrücken.
Also für die kleine Partition und für die größere Partition betrachtet
man die Elemente jetzt einfach als komplett unterschiedlich.
Genauso wie beim Quicksort auch.
Und für die Equal-Partition rufen wir eben auch eine Rekursion aus,
gucken uns aber nicht das nächste Element an und nicht mehr das
gleiche.
Und da sagen wir jetzt einfach, okay, die Vergleiche, die wir mit
diesen Strings in der Equal-Partition gemacht haben, das sind eben
genau Vergleiche mit Zeichen, die in diesen unterscheidenden Präfixen
enthalten sind.
Immer wenn wir eine Gleich-Partition haben, hier zum Beispiel mit
diesen H´s, trägt dieses H ja nicht zum Unterscheiden zu allen anderen
Strings bei.
Sprich, das ist eben einer von diesen, oder ist in diesen
unterscheidenden Präfixen enthalten.
Und diese Vergleiche bezahlen wir einfach mit diesem D.
Und es kann eben höchstens D von diesen Vergleichen geben.
Gut, jetzt haben wir eigentlich Feierabend, aber ich wollte euch
gerade nochmal kurz auf der Dokumentenkamera was zeigen, um
euch einfach nochmal das Handhaben mit Suffix Arrays und Suffix Trees
und suchenden Suffix Trees ein bisschen einfacher zu machen.
Wenn man Suffix Arrays und so weiter definiert und sich das einmal
angeschaut hat, ist es vielleicht noch nicht ganz klar, wie das alles
zusammenhängt, wie das funktioniert, wie man das eine möglichst
effizient, sag ich mal, einmal per Algorithmus natürlich berechnen
kann, aber auch auf der Hand, aber auch auf dem Papier.
Und da wollte ich jetzt einfach mal ein Beispiel dazu machen, weil ich
finde es wichtig, erst mal mit Hand verstanden zu haben, was ein
Suffix Array ist und wie man das konstruiert, wie man daraus einen
Suffix Baum macht, wie man einen Suffix Baum sucht, bevor man dann
überhaupt rangehen kann und den Algorithmus verstehen kann.
Also was wir jetzt haben, ist nun zum Beispiel ein String, der gegeben
ist.
Und der String ist jetzt Bubumbu und wir haben hier so ein
terminierendes Symbol.
Und jetzt möchten wir dafür ein Suffix Array erstellen.
Und was bedeutet Suffix?
Naja, wir haben hier Teile von diesem String und der endet eben immer
mit dem letzten Zeichen.
Also das hier ist ein Suffix, das hier ist ein Suffix, das hier ist
ein Suffix.
Und im Suffix Array, oder letztendlich wird im Suffix Array die
sortierte Ordnung von diesen Suffixen angegeben.
Zu Beginn gehe ich dann eigentlich einfach immer hin und schreibe mir
erstmal auf, was für Suffixe gibt es und den jeweiligen Index dazu.
Wir haben hier acht verschiedene Suffixe.
0, 1, 2, 3, 4, 5, 6, 7.
Und dazu eben jeweils ein Suffix.
Der 0.e Suffix beginnt hier an der 0.e Stelle und geht bis ganz zum
Ende.
Und das ist dann Bubumbu und das Trim Symbol.
Und genau so können wir dann die anderen Suffixe hinschreiben.
Das ist jetzt der Suffix, der am Index 1 beginnt.
Also dieser hier.
Und der nächste Suffix ist dann der Suffix, der bei diesem b hier
beginnt.
So, jetzt haben wir uns die mal aufgeschrieben.
Und diese Indexes sind für mich jetzt einfach erstmal Repräsentanten
dieser Suffixe.
Also wenn ich hier vom Suffix oder vom 1 Suffix spreche, dann ist es
einfach der Suffix, der an der Position 1 im Eingabe Array beginnt.
Und jetzt kann man natürlich den Algorithmus verwenden, um das Suffix
Array sich zu berechnen.
Bei solchen einfachen Eingaben kann man das aber ziemlich effizient
mit der Hand machen.
Was man jetzt einfach macht, im Suffix Array an der 0.
Position steht der Index des kleinsten Suffixes.
Und der kleinste Suffix hier ist der letzte Suffix, das Trim Symbol,
das ist immer das kleinste Symbol.
Und der Index davon ist die 7.
Und deswegen ist im Suffix Array an der Stelle 0 der Wert 7
gespeichert.
Und da kann man jetzt dann rechts dazu zum einfachen Aufbau einfach
mal noch den Suffix hinschreiben.
Und für die einfache Berechnung kann man jetzt einfach hingehen und
sagen, okay, was ist hier das kleinste Zeichen?
Das ist das b.
Also müssen hier Indizes im Suffix Array gespeichert werden auf
Positionen im Ausgangsstring, die auf das Zeichen b zeigen, weil das
auf jeden Fall die nächstkleineren Suffixe sind.
Wenn man dann etwas genauer hinschaut, dann beginnen alle Suffixe, die
mit b beginnen, folgen nach dem b in u.
Jeweils hier das u, hier das u und hier das u.
Also muss man nochmal in weiteren Buchstaben angucken, weil da hat man
bei diesem b hier ein b, hier ein m und hier ein Trim Symbol.
Deswegen haben wir diesen 5, Suffix 5, ist der zweitkleinste Suffix
und dann kann man sich das einfach hier dann mit der 5 notieren und
ich schreibe mir für später dann einfach nochmal den Suffix auf.
Und genauso macht man das bei den anderen beiden Suffixen, die mit b
beginnen.
Hier haben wir dann an der dritten Position b, hier ein m.
Deswegen ist der Suffix 0 kleiner als der Suffix 2.
Deswegen haben wir 0, 2, b, u, b, u und b, u, m, b, u.
Und das können wir dann mit den anderen Suffixen auch machen.
Als nächstes größeres Zeichen haben wir das m.
Davon gibt es nur einen Suffix.
Der ist an der Stelle mit Index 4.
Und dann haben wir noch drei Suffixe, die beginnen mit u und da können
wir dann diese Suffixe, die bei u beginnen, auch nochmal nach dem
nächsten Zeichen sortieren und dann bekommen wir den Suffix, der mit u
beginnt und im Trim Symbol endet.
Dann den Suffix, der mit u beginnt und dann mit bum, bu und im Trim
Symbol fortführt und nochmal einen mit u und der dann mit m
weitergeht.
Jetzt haben wir hier unser Suffix Array konstruiert.
Der rechte Teil hier gehört eigentlich nicht zum Suffix Array, lässt
sich aber einfach durch das Suffix Array berechnen, indem man hier zum
Beispiel für den größten String, der beginnt an Index 3, 0, 1, 2, 3,
guckt man im Eingabe Array nach und findet dadurch dann den größten
Suffix.
Warum habe ich das jetzt hier rechts hingeschrieben?
Naja, wenn jetzt zum Beispiel die Aufgabe ist, man hat hier einen
Eingabetext und soll daraus den Suffix 3 bauen, dann kann man aus
diesem Eingabe Array das Suffix Array aufbauen und mit Hilfe dieser
Zuordnung ziemlich einfach den Suffix 3 aufbauen.
Was man da dann gewöhnlich macht, ist man guckt sich die gemeinsamen
längsten Präfixe an, um die einzelnen Kantenbeschriftungen sich in
dieser Auflistung einfach mal auszurechnen.
Und die gemeinsamsten längsten Präfixe von diesen drei Strings oder
von diesen drei Suffixen ist eben das BU und für die letzten drei
Suffixe ist das gemeinsame Zeichen U.
Und die anderen Suffixe, die haben kein gemeinsames Zeichen mit
irgendwelchen anderen Suffixen und diese Suffixe, die mit U beginnen,
die haben an den lexikografisch folgenden Stellen hier auch keine
gleichen Zeichen.
Deswegen ist der gemeinsame längste Präfix hier eben das U und hier
das BU und es gibt sonst keine anderen gemeinsamen Präfixe.
Und mit Hilfe dieser gemeinsamen längsten Präfixe kann man jetzt eben
ziemlich einfach den Suffixbaum aufbauen.
Wir haben jetzt hier verschiedene längste gemeinsame Suffixe.
Also wir haben hier das Trennsymbol, das ist sozusagen der längste
gemeinsame Suffix von diesem Suffix mit keinem anderen, sondern nur
mit sich selbst.
Dann haben wir das BU, dann haben wir das M mit diesem BU und dem
Trennsymbol.
Das ist eben ein längster gemeinsamer Suffix, aber nur mit sich
selbst.
Es gibt halt keinen anderen.
Und dann der letzte längste gemeinsame Suffix ist das U.
Und was dieser Suffixbaum eben genau macht, der splittet die Suffixe
nach den längsten gemeinsamen Suffixen.
Und deswegen habe ich die jetzt eingezeichnet und wir haben beim
Suffixbaum am Anfang jeweils eine Wurzel.
Und da trennen wir nach den längsten gemeinsamen Suffixen.
Und das längste gemeinsame Suffix ist eben einmal hier das
Trennsymbol.
Dann haben wir das BU,
das ist eben dieses längste gemeinsame Suffix.
Dann haben wir hier ein längstes gemeinsames Suffix, M, B, U, das
Trennsymbol.
Und dann haben wir hier nochmal ein längstes gemeinsames Suffix, das
ist das U.
Und was der Suffixbaum macht, der sortiert seine ausgehenden Kanten
eben lexikografisch.
Das bedeutet, diese Kante hier, BU, die kommt vor der Kante, M, B, U,
Terminierungssymbol.
Weil eben dieses B kleines S ist M.
Es vereinfacht einfach letztendlich die Suche in dem Baum.
Wenn man das dann mit einer Bienen-Suche durchsuchen würde, man kann
den Baum natürlich auch mit einer Hashtabelle irgendwie versuchen zu
durchlaufen, dann ist es vielleicht nicht mehr so wichtig.
Was man sich dann in die Blätter ranschreibt, ist jeweils der Index
von dem Suffix.
Der Index von diesem Suffix ist eben 7, weil es eben das Trennsymbol
ist.
Und das ist der Suffix an der Position 7.
Hier haben wir nochmal einen Suffix, der schon endet.
Und dieser Suffix beginnt mit M, B, mit M.
Und das ist dann der Suffix am Index 4.
Jetzt haben wir noch nicht alle Suffixe komplett in diesen Baum
eingebaut.
Jetzt müssen wir das mit den verbleibenden Zeichen der Strings
rekursiv auf die gleiche Variante weitermachen.
Wir haben hier zum Beispiel die Gruppe, die mit B, U beginnt.
Da suchen wir Lieder, die längst gemeinsam Präfixe.
Und da die Zeichenketten oder die Suffixe hier, das Trennsymbol, diese
Suffix und dieser Suffix jeweils unterschiedlich sind, sind es die
eigenen, oder es sind jeweils die kompletten Suffixe, die längst
unterscheidenden Präfixe.
Und deswegen haben wir dann hier drei Kanten, die jeweils den
kompletten Rest des Suffixes beinhalten.
Einmal das Trennsymbol, hier dann B, U, M, B, U und das
Terminierungssymbol.
Und für diesen Fall das M, B, U und das Trennsymbol.
Und da schreiben wir dann auch jeweils noch die Indizes hin.
Da haben wir dann hier eine 5, dann haben wir hier eine 0 und hier
eine 2.
Und das Gleiche machen wir hier auch mit der letzten Gruppe, welche
bei U begonnen hat.
Hier haben wir auch keine gemeinsamen Präfixe, deswegen gibt es auch
wieder drei Blätter.
Einmal mit dem Trennsymbol, das ist dann die 6 hier, mit B, U, M, B,
U, Terminierungssymbol, das ist die 1 und das M, B, U,
Terminierungssymbol hier beginnt bei Index 3.
Und wenn jetzt die Aufgabe ist, zu überprüfen, ob dieser Eingabe
-String das Pattern B, A beinhaltet, kann man einfach hingehen bei der
Wurzel beginnen und gucken, ob es hier eine Ausgangskante gibt, die
Präfix von unserem Pattern ist.
Das gibt es nicht, weil wir haben hier zwar ein B, aber ein A und eine
der Ausgangskanten hier ist eben kein Präfix, weil wir hier ein B, U
haben.
Wenn wir uns fragen, gibt es ein B, U, dann wissen wir, es gibt eins,
weil dieses B, U eben genau über diese Kante erzeugt werden kann.
Wenn wir uns jetzt fragen, wie oft dieses B, U vorkommt, müssen wir
uns letztendlich einfach berechnen, bei diesem Knoten, wie viele
Kinder hat dieser Knoten.
Und dieser Knoten hier, der hat drei Kinder,
drei Blätter.
Das ist einmal das Blatt, welches den Suffix 5 repräsentiert, das
Blatt, welches den Suffix 0 repräsentiert und das Blatt, welches den
Suffix 2 repräsentiert.
Und das ist eben genau dann hier der Suffix, der an dieser Stelle 0
beginnt, der Suffix, der an der Stelle 2 hier beginnt und der Suffix,
der hier an der Stelle 0 beginnt.
Gut, das war es zu den Suffixbäumen.
Gibt es dazu noch Fragen?
Okay, also ich finde, das ist eine ganz geschickte Sache.
Schaut euch das mal an.
Das ist auf jeden Fall wichtig.
Ebenfalls die Rekurrenzrelation, weil die braucht man einfach, um die
Laufzeiten von den parametrisierbaren Algorithmen auszurechnen und
dann überprüfen zu können, naja, kann man den Algorithmus oder ist es
überhaupt ein parametrisierbarer Algorithmus und was sind die
Laufzeiten davon?
So viel von meiner Seite.
Schöne Feiertage und einen schönen Rutsch ins neue Jahr.
Diese Woche ist ein Weihnachtsübungsblatt rausgekommen mit
Wiederholungsaufgaben und Aufgaben zu den Themen von den letzten
Wochen.
Wenn ihr wollt, könnt ihr da einfach schon mal reinschauen und euch
ein bisschen vorbereiten.
Gut, das war es für dieses Jahr.
Bis nächstes Jahr.