WEBVTT 00:10.220 --> 00:13.890 Hallo, ich begrüße Sie zur Vorlesung Algorithmen 2. 00:14.650 --> 00:16.410 Ich heiße Simon Grog. 00:17.050 --> 00:20.190 Ich arbeite im Lehrstuhl von Herrn Sanders. 00:23.390 --> 00:28.490 Im Lehrstuhl selbst machen wir auch Stringology, das heißt dieses 00:28.490 --> 00:32.530 Thema, das ich übernehmen werde und diese Woche damit anfange. 00:34.550 --> 00:42.330 Es geht um die Verarbeitung von Zeichenketten und ich werde diese 00:42.330 --> 00:45.630 Vorlesung bei drei Themen machen. 00:45.910 --> 00:50.950 Das erste ist Stringsortieren, Zeichenketten sortieren, dann 00:50.950 --> 00:57.510 Patternsuche und da gibt es eine Online-Version. 00:57.510 --> 01:04.010 Also ich habe einen Text und will darin quasi den Text 01:04.010 --> 01:08.350 unvorverarbeitet, ja irgendeine Datei, ich will darin einen Pattern 01:08.350 --> 01:08.710 suchen. 01:11.250 --> 01:14.810 Oder die andere Version, ich habe den Text, der ist vorher schon 01:14.810 --> 01:20.810 bekannt, also offline und den kann ich vorverarbeiten und dann will 01:20.810 --> 01:23.390 ich auch einen Pattern suchen in so einem Text. 01:24.690 --> 01:31.810 Da gibt es verschiedene Indizes, die man da aufbauen kann und das 01:31.810 --> 01:37.570 Schöne ist, dass in unserer Gruppe gibt es ein schönes Resultat, wie 01:37.570 --> 01:41.570 man diese Indizes effizient konstruiert und das wird man quasi auch 01:41.570 --> 01:43.290 vorstellen in der Vorlesung. 01:43.290 --> 01:48.870 Und was man auch noch machen kann, diese Algorithmen, die man 01:48.870 --> 01:52.090 kennenlernt, kann man auch für die Datenkompression verwenden. 01:53.130 --> 01:59.230 Und genau, die alltäglichen Tools, die man verwendet, wie Bzip oder 01:59.230 --> 02:08.410 7zip usw., da muss man Pattern suchen, um die Pattern durch kürzere 02:08.410 --> 02:09.710 Einträge zu ersetzen. 02:10.330 --> 02:15.390 Und genau, das machen wir da und dann gibt es noch mein Spezialgebiet. 02:15.970 --> 02:18.910 Man kann quasi in diesen komprimierten Daten auch gleichzeitig suchen, 02:19.010 --> 02:19.890 ohne alles zu dekomprimieren. 02:20.450 --> 02:29.150 Also das ist was ganz magisches, aber ist gar nicht so schwierig und 02:29.150 --> 02:30.270 ich werde Ihnen zeigen, wie das geht. 02:31.550 --> 02:35.690 Pattern Matching ist eigentlich nur, ich habe einen Text und will 02:35.690 --> 02:37.510 darin ein kürzeres Pattern suchen. 02:39.350 --> 02:41.770 Und da gibt es natürlich Variationen, was man da machen kann. 02:42.190 --> 02:45.870 Zum Beispiel habe ich Ihnen mitgebracht, das ist so eine Anwendung, 02:46.430 --> 02:48.550 Top -Key Query Completion. 02:49.050 --> 02:52.930 Heißt, ich habe einen Pattern, eine Query, da gebe ich irgendwas ein 02:52.930 --> 02:58.350 und das spuckt mir gewichtet Ergebnisse zurück. 02:58.350 --> 03:03.830 Erstmal werden wir uns einen Text geben, man kann das aber auch mit 03:03.830 --> 03:04.590 mehreren Texten. 03:04.870 --> 03:07.250 Und wenn man dann mehrere Texte hat, dann will man, wenn das Pattern 03:07.250 --> 03:13.010 vorkommt, auch den Text finden, der das höchste Gewicht hat. 03:14.430 --> 03:16.730 Und das muss natürlich auch effizient passieren. 03:17.750 --> 03:19.990 Das heißt mit so einem Index, wenn der vorverarbeitet ist, dann geht 03:19.990 --> 03:20.710 das rasend schnell. 03:21.170 --> 03:25.570 Also heute zum Beispiel in der Vorlesung würde ich den Knuth-Morris 03:25.570 --> 03:28.510 -Brett -Algorithmus zum Pattern Matching vorstellen und wenn ich den 03:28.510 --> 03:34.770 suche, dann geht das super schnell, weil die Komplizität von dem 03:34.770 --> 03:37.970 ganzen hängt nur ab von der Länge des Patterns, die ich da eingebe. 03:39.270 --> 03:41.010 Hier 6, 7, 8 oder so. 03:42.670 --> 03:47.630 Und dem K, also Top 10, dann wäre das von dem 10 abhängig. 03:48.470 --> 03:53.470 Das sind zum Beispiel alle Wikipedia-Titel, habe ich da indiziert. 03:55.430 --> 03:59.250 Und das Gewicht ist quasi die Pageviews pro Tag, die Wikipedia auch 03:59.250 --> 04:00.630 oder Wikimedia auch veröffentlicht. 04:01.230 --> 04:03.990 Und dann kann man so eine Datenbank machen und das wäre quasi ein 04:03.990 --> 04:07.570 motivierendes Beispiel, warum man denn Pattern Matching und 04:07.570 --> 04:09.350 Stringology usw. 04:09.710 --> 04:09.750 braucht. 04:09.870 --> 04:11.150 Das ist irgendwie alltäglich. 04:11.990 --> 04:14.170 Okay, genau. 04:14.750 --> 04:17.410 Dann fange ich an mit dem Stoff. 04:17.690 --> 04:23.550 Und das erste, was man da macht, das knüpft auch schon an die 04:23.550 --> 04:25.670 vorhergehenden Vorlesungen. 04:26.250 --> 04:27.230 Ja, das ist Sortieren. 04:27.450 --> 04:29.530 Sortieren haben sie in Algorithmen auch schon gehabt. 04:30.590 --> 04:37.670 Wenn man Strings hat, dann gibt es da so eine Anpassung von Quicksort. 04:37.670 --> 04:40.550 Das ist der sogenannte Multi-Key-Quicksort. 04:41.030 --> 04:47.450 Bei Multi-Key-Quicksort, da ist gegeben eine Sequenz oder eine Menge 04:47.450 --> 04:48.110 von Strings. 04:48.770 --> 04:50.050 Groß S bezeichnet. 04:51.290 --> 04:57.870 Und auch noch eine gewisse Länge der Strings. 04:59.550 --> 05:03.010 Oder das ist das L, genau, das ist ein Parameter des Algorithmus. 05:04.010 --> 05:07.570 In Zeile 1 sagt uns das, was dieser Parameter bedeutet. 05:07.650 --> 05:13.430 Der Parameter bedeutet, dass quasi alles, was in dem Stringset drin 05:13.430 --> 05:21.030 ist, die erste L-1 Buchstabe, die sind schon sortiert. 05:22.510 --> 05:26.930 Das heißt, wenn man den Algorithmus auf ein komplettes Stringset 05:26.930 --> 05:32.070 anwendet, dann wäre das erstmal 0. 05:32.070 --> 05:36.490 Das heißt, dann wäre quasi der leere String oder das leere Prefix 05:36.490 --> 05:37.390 sortiert. 05:37.490 --> 05:40.610 Ja, ich habe da mal hier ein Beispiel vom Stringset. 05:41.430 --> 05:45.750 Und ich würde anfangen, wenn ein komplettes Stringset und das Prefix 05:45.750 --> 05:50.070 für Länge 0 ist dann schon sortiert. 05:50.910 --> 05:53.410 Oder nicht sortiert, sondern ist gleich in diesem Bucket. 05:55.590 --> 05:59.890 Dann wählt man sich ein Pivot-Element aus in diesen Strings. 05:59.890 --> 06:05.970 Wie auch beim traditionellen Quicksort. 06:10.090 --> 06:14.010 Das Problem beim Stringsorting ist, wenn ich jetzt einfach den 06:14.010 --> 06:18.690 normalen, vergleichsbasierten Sortierer nehme, Quicksort, dann hat er 06:18.690 --> 06:23.010 eine Kompensität von NlogN, wenn N quasi die Menge an Elementen ist, 06:23.070 --> 06:23.710 also hier Strings. 06:24.830 --> 06:28.770 Und wenn ich das mache, dann habe ich NlogN mal ein Vergleich. 06:28.770 --> 06:32.670 Und wenn ich Strings habe, dann ist der Vergleich aber ein 06:32.670 --> 06:33.850 lexikografischer Vergleich. 06:34.010 --> 06:38.870 Das heißt, wenn ich zwei Strings vergleiche, dann kann ich die 06:38.870 --> 06:42.390 Ordnung, also was kleiner und größer ist, ist quasi regressiv 06:42.390 --> 06:42.870 definiert. 06:42.970 --> 06:46.930 Ich vergleiche den ersten Buchstaben, wenn vom ersten String der 06:46.930 --> 06:49.170 Buchstabe kleiner ist als vom zweiten String, dann ist auch der 06:49.170 --> 06:49.970 gesamte String kleiner. 06:51.070 --> 06:57.790 Und sonst gehe ich eine Position weiter und mache das Gleiche und so 06:57.790 --> 06:58.410 ist das definiert. 06:58.410 --> 06:59.750 Das ist die lexikografische Ordnung. 07:00.010 --> 07:06.690 Und jetzt wird, wenn ich ein Stringset habe, wo die Strings eine lange 07:06.690 --> 07:13.910 M haben, dann würde ich quasi pro String im Wurstkreis M Vergleiche 07:13.910 --> 07:14.630 machen, das ist schlecht. 07:15.530 --> 07:21.130 Und dieser Algorithmus, den ich jetzt vorstelle, der ist besser. 07:21.930 --> 07:23.610 Okay, also habe ich mein Stringset. 07:23.770 --> 07:27.110 Ich fange quasi an mit dem prefix der Ernährung Null, suche mir ein 07:27.110 --> 07:32.930 Pivot -Element raus und auf Ebene 1, und das ist das H in diesem Fall. 07:34.650 --> 07:37.690 Und darum heißt er auch Ternary Quicksort. 07:38.890 --> 07:41.110 Ich teile dann die Menge auf an Strings. 07:41.610 --> 07:47.130 Einmal in die Menge der Strings, die kleiner ist, wo der erste 07:47.130 --> 07:50.430 Buchstabe lexikografisch kleiner ist als der aktuell ausgewählte 07:50.430 --> 07:50.770 Strings. 07:51.310 --> 07:53.150 Sonst findet keine Umordnung statt. 07:53.470 --> 07:56.990 BA, das ist quasi so, wie es nur vorher in der Menge war. 07:58.230 --> 08:03.130 Dann die Menge, wo das gleiche Buchstabe ist, der erste, und dann die 08:03.130 --> 08:07.630 Menge von allen Buchstaben, die, oder alle Strings im Buchstabeanfang 08:07.630 --> 08:08.910 lexikografisch größer sind. 08:09.730 --> 08:15.610 So, und dann kriege ich quasi drei Mengen. 08:16.090 --> 08:17.390 Und dann geht es rekursiv weiter. 08:20.790 --> 08:27.150 In der ersten Menge weiß ich immer noch nichts über die Sortierung 08:27.150 --> 08:28.130 nach dem ersten Buchstabe. 08:28.610 --> 08:32.810 Darum suche ich mir wieder ein Pivot aus und mache nach dem ersten 08:32.810 --> 08:35.650 Buchstabe und sortiere entsprechend. 08:35.870 --> 08:37.330 Ich habe das E zum Beispiel jetzt ausgewählt. 08:39.070 --> 08:43.750 Dann muss ich A und B vor diesem E sortieren. 08:44.870 --> 08:47.210 So, und dann bin ich da schon fertig. 08:47.450 --> 08:50.450 Weil jetzt alle Buchstaben unterschiedlich sind, habe ich schon die 08:50.450 --> 08:52.650 korrekte Ordnung erhalten. 08:53.570 --> 08:57.170 Und dann wählt man sich ein Pivot aus in der nächsten Menge, die noch 08:57.170 --> 08:58.050 nicht ganz sortiert ist. 08:58.130 --> 09:00.990 Und das ist die Menge aller Strings, die mit H anfangen. 09:01.410 --> 09:03.850 Da wähle ich jetzt irgendwie das zweite Element aus. 09:04.170 --> 09:05.070 Das fängt mit A an. 09:05.670 --> 09:08.650 Und dann sortiere ich das wieder um. 09:09.930 --> 09:14.730 Das heißt, habe ich jetzt alle Strings, wo der zweite Buchstabe mit A 09:14.730 --> 09:19.330 anfängt, sind natürlich lexographisch kleiner als der String Hund, 09:19.450 --> 09:21.830 womit das U in zweiter Position ist. 09:23.030 --> 09:26.790 Und im nächsten Schritt geht es dann so weiter. 09:27.110 --> 09:31.050 Und den Rest mache ich dann auch mit der gleichen Methode. 09:32.570 --> 09:35.610 Im Algorithmus sieht es folgendermaßen aus. 09:37.210 --> 09:41.410 Also ich wähle mir dieses Pivot und nehme erstmal ein. 09:41.490 --> 09:42.490 Ja, das machen wir irgendwie random. 09:43.570 --> 09:45.390 Und habe die drei Mengen. 09:45.950 --> 09:51.390 Und jetzt fällt aber auf, dass in zwei Fällen bleibt man genau auf dem 09:51.390 --> 09:51.910 gleichen Level. 09:52.130 --> 09:57.630 Weil da müssen wir noch herauskriegen, wie die Strings untereinander 09:57.630 --> 09:59.050 sortiert werden müssen. 09:59.550 --> 10:02.370 Und sonst wissen wir schon, dass sie alle mit dem gleichen Buchstabe 10:02.370 --> 10:02.690 anfangen. 10:02.690 --> 10:05.470 Und dann können wir quasi einen Schritt weiter gehen. 10:05.770 --> 10:07.990 Was ist die Laufzeit dieses Algorithmus? 10:08.370 --> 10:13.050 Naja, die Hauptarbeit steckt natürlich im Bestimmen dieser drei 10:13.050 --> 10:14.050 Mengen. 10:15.210 --> 10:19.790 Und die Laufzeit... 10:19.790 --> 10:23.350 Naja, es gibt jetzt diese drei Fälle. 10:23.790 --> 10:29.510 In einem Fall, wo das L plus 1 steht, gehen wir 1 weiter in den 10:29.510 --> 10:30.370 entsprechenden Strings. 10:33.330 --> 10:36.430 Und naja, wie oft kann das passieren? 10:38.750 --> 10:40.830 Das kommt auf eine später Folie. 10:41.110 --> 10:45.010 Aber das kann, wo String einfach nur die... 10:45.010 --> 10:48.110 Ja, also ganz pessimistisch gesehen kann das quasi... 10:48.110 --> 10:50.950 Da laufen wir quasi beim String bis zum Ende. 10:50.950 --> 11:00.170 Das heißt, die Summe dieser Vorwärtsbewegungen ist die Summe der Länge 11:00.170 --> 11:01.950 aller Strings in S. 11:02.310 --> 11:06.270 Das seht ihr hier in der ersten Formel. 11:06.490 --> 11:09.310 Das ist dieser zweite Teil. 11:10.210 --> 11:13.750 Okay, dann gibt es noch ein Slog S. 11:15.350 --> 11:18.330 Und dieses Slog S... 11:20.530 --> 11:25.670 Das hat mit der Auswahl zu tun, wie jetzt die Menge berechnet wird. 11:26.070 --> 11:32.690 Also unter der Annahme, dass dieses Pivot-Element optimal gewählt ist. 11:32.890 --> 11:37.750 Das heißt, dass es so gewählt ist, dass diese zwei Mengen... 11:39.290 --> 11:45.830 Die Anfangsbuchstaben, die kleiner und größer sind als das Pivot 11:45.830 --> 11:46.270 -Element. 11:46.870 --> 11:50.510 Kleiner sind als die Hälfte der Menge. 11:52.730 --> 11:59.750 Dann passiert es pro String höchstens log viele Male... 12:00.650 --> 12:04.490 von der Größe dieses Gesamtstringsets. 12:04.490 --> 12:08.470 Weil ich halbiere jedes Mal die Menge. 12:09.650 --> 12:14.310 Das heißt, hier in dem zweiten Term rechnet man das jedes Mal einem 12:14.310 --> 12:15.110 Buchstabe zu. 12:16.030 --> 12:17.150 Eines Strings. 12:17.330 --> 12:19.550 Und geht eins vor in dem String. 12:20.110 --> 12:26.190 Und in dem ersten Term rechnet man das immer pro String zu und in 12:26.190 --> 12:27.050 welcher Menge er liegt. 12:27.050 --> 12:32.810 Und er kann höchstens log ein Mal in diesen zwei anderen Fällen 12:32.810 --> 12:33.190 liegen. 12:34.590 --> 12:37.730 Und so kommt man dann auf diese Komplizität. 12:38.530 --> 12:41.710 Es geht eigentlich noch besser. 12:42.410 --> 12:45.690 Was passiert, wenn ich da sortiere? 12:46.130 --> 12:48.790 Ich sortiere nur soweit, das sieht man vielleicht hier am Ende. 12:48.790 --> 12:57.070 Ich sortiere nur soweit, wie sich dieses Prefix von dem String 12:57.070 --> 13:05.210 unterscheidet von dem lexographisch nächsten String, der in diesem 13:05.210 --> 13:06.530 Stringset liegt. 13:06.530 --> 13:18.190 Und das nennt man die Länge der unterscheidbaren Prefixe. 13:19.830 --> 13:27.210 Das heißt, wenn ich sowas habe wie ein Stringset, das besteht aus A, 13:29.230 --> 13:35.810 Strings der Länge 2 bestehen aus A, Strings der Länge 3 bestehen aus A 13:35.810 --> 13:36.350 und so weiter. 13:38.350 --> 13:42.210 Dann müsste ich da jedes Mal bis hinten laufen. 13:42.210 --> 13:48.910 Und dann müsste ich jedes Mal alle Buchstaben nehmen. 13:49.050 --> 13:54.870 Aber in der Praxis ist es oft so, dass die Distinguishing Prefixes 13:54.870 --> 13:57.730 viel kürzer sind als der komplette String. 14:07.040 --> 14:12.120 Ich habe das in den Algorithmus nochmal aufgeschrieben, um den ganz 14:12.120 --> 14:12.860 korrekt zu machen. 14:15.680 --> 14:20.660 Wenn das Stringset kleiner ist als 1, dann sind wir fertig im 14:20.660 --> 14:21.360 Algorithmus. 14:22.020 --> 14:25.340 Und was man dann noch machen muss ist, wenn man ins Ende eines Strings 14:25.340 --> 14:29.360 kommt, also wenn so ein String genau die Länge L hat, dann muss man 14:29.360 --> 14:30.540 alle diese Strings abziehen. 14:33.320 --> 14:36.760 Die kommen quasi vor allen anderen Strings lexikografisch. 14:38.000 --> 14:41.420 Man wird auch später in der Vorlesung sehen, dass man oft an einem 14:41.420 --> 14:46.820 String einfach ein Symbol dran hängt, das eindeutig und lexikografisch 14:46.820 --> 14:49.720 kleiner ist als alle anderen Symbole, die man behandelt. 14:49.720 --> 14:53.500 Und so kann man das umgehen in diesem Spezialfall. 14:54.500 --> 14:55.740 Aber hier nehmen wir es einfach raus. 14:56.260 --> 14:59.040 Dann selektieren wir dieses Pivot. 14:59.740 --> 15:01.240 Es gibt jetzt verschiedene Techniken. 15:01.340 --> 15:05.160 Man kann auch einfach einen Buchstabe auswählen statt einen 15:05.160 --> 15:06.780 Pivotstring und das dann so aufteilen. 15:09.400 --> 15:12.640 Macht die drei Mengen und dann hängt man wieder die Ergebnisse 15:12.640 --> 15:13.220 zusammen. 15:13.220 --> 15:19.780 Und das ist korrekt natürlich, weil alle Strings in dieser Menge, weil 15:19.780 --> 15:26.540 der Buchstabe in der Position L kleiner ist als vom Pivot, kommt vor 15:26.540 --> 15:31.320 allen Elementen oder allen Strings in der zweiten Menge, wo sie gleich 15:31.320 --> 15:34.460 sind und alle die in der dritten Menge sind, sind lexikografisch 15:34.460 --> 15:38.120 größer, weil der Buchstabe in der Position L auch größer ist. 15:40.140 --> 15:50.560 Und hier steht nochmal diese Argumentation, wie man auf diese zwei 15:50.560 --> 15:51.480 Komplizitäten kommt. 15:51.600 --> 15:57.760 Im einen Fall hat man zur gleichen quasi immer den jeweiligen 15:57.760 --> 16:01.040 Buchstaben zu, im Gleichfall, und geht eins weiter. 16:01.420 --> 16:02.960 Das heißt, man zählt es niemals doppelt. 16:04.800 --> 16:11.920 Und es ist aus, wenn die maximale Länge des längsten gemeinsamen 16:11.920 --> 16:16.320 Breivs von E mit irgendeinem anderen String in der Menge da ist. 16:17.360 --> 16:24.780 Und im zweiten Fall, wenn die Buchstaben verschieden sind, dann 16:24.780 --> 16:26.400 rechnen wir diesen String E zu. 16:29.460 --> 16:35.540 Und E liegt dann entweder in der kleinen oder der größten Menge und 16:35.540 --> 16:39.740 durch die Annahme, dass das Pivot optimal gewählt ist, sind die Mengen 16:39.740 --> 16:41.640 höchstens 1,5 groß. 16:42.020 --> 16:44.420 Das geht natürlich auch, wenn die nicht genau 1,5 ist, sondern 16:44.420 --> 16:51.500 irgendwie 1,75 usw., dann muss aber immer ein Bruch, ein Ding sein, 16:51.620 --> 17:04.200 das kleiner ist als die Ursprungsmenge, dann ist der Faktor beim Log 17:04.200 --> 17:05.000 ein bisschen schlechter. 17:06.340 --> 17:12.760 Und bei 2 ist es gleich Log 2 und dann ist es richtig sortiert. 17:13.620 --> 17:21.760 In der Praxis ist das ein sehr schneller Algorithmus, der auch später 17:21.760 --> 17:26.520 in der Konstruktion eines Index als Subroutine eingesetzt wird. 17:29.740 --> 17:32.680 Der Nachteil von ihm ist immer noch, wenn es zu einer Würstgeld 17:32.680 --> 17:37.660 -Einkabe kommt, dann habe ich immer noch was, das abhängt von der 17:37.660 --> 17:39.720 Summe aller Strings, die da drin liegen. 17:40.540 --> 17:44.520 Und wie wir später sehen bei so einem Index, da habe ich einen Text, 17:44.880 --> 17:51.520 ich nehme alle Suffixe dieses Textes und wenn ich die sortieren will, 17:52.280 --> 17:55.260 dann wird quasi in einem Würstgeld das quadratische Laufzeiten mal 17:55.260 --> 17:59.780 dieses Nlog oder plus NlogN rauskommen und das ist zu schlecht. 18:00.820 --> 18:07.720 Genau, aber darum kann man den dann nicht anwenden, aber sonst ist das 18:07.720 --> 18:12.760 für Stringsets, wo die Stringsets nicht implizit definiert sind, ist 18:12.760 --> 18:13.820 das ein guter Algorithmus. 18:15.200 --> 18:19.640 Ich weiß nicht, Präfixe und Suffixe, das ist ja bekannt, hoffe ich 18:19.640 --> 18:19.860 doch. 18:20.400 --> 18:25.340 Also wenn Sie Fragen haben, wie ich zu schnell bin oder zu langsam, 18:26.180 --> 18:27.200 können Sie mir das Ganze sagen. 18:28.980 --> 18:33.160 Okay, also das ist jetzt quasi mal ein Algorithmus, den man dann 18:33.160 --> 18:34.300 später auch wiederverwenden wird. 18:35.880 --> 18:38.460 Da haben wir jetzt noch kein Pattern Matching gemacht, aber natürlich, 18:38.560 --> 18:43.520 wenn so ein Stringset sortiert ist, dann kann man auch leicht darin 18:43.520 --> 18:43.760 suchen. 18:43.860 --> 18:46.260 Wenn ich jetzt ein Pattern habe, dann kann ich eben Binärsuche machen 18:46.260 --> 18:49.400 nach diesem Pattern, nach dem ersten Buchstabe, nach dem zweiten 18:49.400 --> 18:50.320 Buchstabe usw. 18:50.920 --> 18:58.040 Das heißt, das ist eigentlich was sehr gut ist, wenn der Text 18:58.040 --> 18:58.940 vorverarbeitet ist. 19:01.720 --> 19:06.880 Wenn der Text nicht vorverarbeitet ist, dann müssen wir Pattern 19:06.880 --> 19:08.940 Matching machen ohne Index. 19:09.980 --> 19:11.500 Und da ist es natürlich so, 19:14.660 --> 19:24.020 dass es da einen Algorithmus gibt, der sehr naiv ist und schlechte 19:24.020 --> 19:24.740 Laufzeit hat. 19:25.020 --> 19:29.680 Und den kann man aber so dahingehend verbessern und ich schreibe den 19:29.680 --> 19:38.440 jetzt einfach nochmal hier hin, weil mir nachher ein komplizierterer 19:38.440 --> 19:45.380 Algorithmus machen wird und ich es nochmal schön langsam entwickeln 19:45.380 --> 19:45.770 will. 19:48.520 --> 19:49.860 Naiv ist Pattern Matching. 19:51.720 --> 19:58.140 Ich sollte es vielleicht tauschen, dass das in der Mitte ist. 20:01.760 --> 20:04.300 Und die andere Folie, die machen wir. 20:05.980 --> 20:07.260 Naiv ist Pattern Matching. 20:07.440 --> 20:15.060 Da haben wir einen Text und wir fangen jetzt immer irgendwie die 20:15.060 --> 20:18.760 Indizes von dem Text, fangen wir bei 1 an jetzt erstmal, im ersten 20:18.760 --> 20:19.800 Teil der Vorlesung. 20:19.800 --> 20:27.740 Und jetzt führen wir mal so einen Matching-Algorithmus durch. 20:30.200 --> 20:31.980 3, 4 und so weiter. 20:32.740 --> 20:34.040 Und das ist unser Text. 20:34.140 --> 20:39.520 Der Text ist immer definiert, dass die Länge quasi in ist. 20:41.040 --> 20:45.700 Und bei Pattern ist definiert, dass die Länge immer in ist. 20:47.220 --> 20:52.560 Und das Beispiel-Pattern nehmen wir mal A, N, A, A. 20:54.320 --> 20:59.480 Und naja, dieser ganz naive Algorithmus, der fängt hier in jeder 20:59.480 --> 21:00.240 Position an. 21:01.240 --> 21:02.560 Natürlich, den können sie bestimmt. 21:02.960 --> 21:04.240 Und dann gibt es hier ein Match. 21:04.420 --> 21:05.720 Und das mache ich immer durch so einen Strich. 21:06.680 --> 21:08.720 Und dann kommt hier ein N. 21:09.500 --> 21:12.000 Und das stimmt nicht überein, dann mache ich so einen Blitz. 21:13.540 --> 21:15.400 Und dann fange ich wieder neu an. 21:15.840 --> 21:17.640 Ich fange hier, das ist wieder ein Match. 21:17.980 --> 21:20.080 Dann kommt hier das N, das ist wieder ein Match. 21:20.260 --> 21:22.040 Dann kommt das A, Match. 21:22.600 --> 21:23.940 Dann das A, Match. 21:24.360 --> 21:25.260 So, und jetzt sind wir fertig. 21:25.720 --> 21:27.160 Jetzt haben wir quasi einen Vorkommen gefunden. 21:28.340 --> 21:30.500 Und dann fängt man das nächste an. 21:31.520 --> 21:33.580 Also A und N matchen nicht. 21:34.180 --> 21:36.680 Also ist das schlecht. 21:37.420 --> 21:38.220 Hier auch. 21:38.220 --> 21:42.000 Und dann kommt das nächste Vorkommen. 21:42.200 --> 21:44.620 A matcht wieder und N matcht nicht. 21:45.100 --> 21:53.920 Und das ist sehr, sehr schlecht, dieser Algorithmus, weil die Worst 21:53.920 --> 22:02.780 -Case -Compensate dieses Algorithmus, der ist offensichtlich bei N mal 22:02.780 --> 22:10.900 M, weil ich hier N mal dieses Pattern aligniere und dann im 22:10.900 --> 22:14.120 schlimmsten Fall bis zu M Vergleiche mache. 22:17.720 --> 22:22.720 Und der Worst-Case-Anzugeber ist auch ganz einfach, weil ich hier auf 22:22.720 --> 22:32.660 einem Pattern habe, das A hoch N, also ein Pattern A hoch M und einen 22:32.660 --> 22:33.700 Text A hoch N habe. 22:34.780 --> 22:35.820 Genau, sehr schlecht. 22:36.440 --> 22:43.420 Das Gute ist, dass es einen viel besseren Algorithmus gibt und dieser 22:43.420 --> 22:50.980 bessere Algorithmus, der bessere Algorithmus, der ist sogar optimal. 22:51.760 --> 22:54.360 Das heißt, was muss ich denn betrachten? 22:54.520 --> 22:57.880 Ja, ich muss mindestens den Text betrachten, der Länge N und 22:57.880 --> 23:00.600 mindestens das Pattern, der Länge M. 23:02.100 --> 23:08.440 Das heißt, in meinem Maschinenmodell brauche ich mindestens N plus M 23:08.440 --> 23:15.100 Vergleiche und das heißt, ich würde jetzt einen Algorithmus 23:15.100 --> 23:17.860 präsentieren, der hat Worst-Case-Komplexität 23:26.800 --> 23:29.860 von N plus M. 23:32.940 --> 23:34.240 Und durch was? 23:34.320 --> 23:37.700 Ja, durch besseres Verschieben des Patterns. 23:38.460 --> 23:42.300 Durch besseres Verschieben. 23:42.700 --> 23:46.240 So, und wie ich schon am Anfang gesagt habe, dieser Algorithmus 23:46.240 --> 23:50.660 Verschieben des Patterns, 23:54.440 --> 23:59.640 dieser Algorithmus wurde erfunden von einem gewissen Herrn Knuth, 23:59.900 --> 24:01.520 einem gewissen Herrn Morris und einem gewissen Herrn Brett. 24:02.140 --> 24:04.420 Diesen Herrn Knuth kennen Sie bestimmt, weil er hat zum Buch 24:04.420 --> 24:08.500 geschrieben The Art of Computer Programming mit verschiedenen Volumes. 24:12.940 --> 24:16.700 Und wie ist denn das Prinzip von diesem Algorithmus? 24:16.880 --> 24:19.200 Also ich habe wieder den Text. 24:20.860 --> 24:24.260 Dann deute ich jetzt hier mal nur so schematisch N und das Wichtige 24:24.260 --> 24:27.040 ist, dass ich hier eine Position I habe. 24:27.480 --> 24:35.300 Und diese Position I matche ich jetzt und habe so ein Pattern, das ich 24:35.300 --> 24:36.600 da aligniere. 24:38.040 --> 24:42.140 Und da habe ich matchende Stellen. 24:44.280 --> 24:49.600 Und ich bin jetzt hier in Position J. 24:51.620 --> 24:56.560 Ich brauche ja so ein Ding, das nicht matcht, aber nicht 24:56.560 --> 24:57.200 übereinstimmt. 24:57.780 --> 24:59.240 Und das sei jetzt in Position J. 25:00.140 --> 25:05.280 Und wenn es in Position J ist in diesem Pattern, das fängt auch bei 1 25:05.280 --> 25:14.140 an, dann ist es in Position I plus J minus 1. 25:15.220 --> 25:18.520 Also wenn man quasi mit J gleich 1 anfängt, dann muss es genau wieder 25:18.520 --> 25:19.220 ein I sein usw. 25:19.340 --> 25:21.300 Da muss man hier noch eins abziehen. 25:22.940 --> 25:29.300 Und genau, jetzt ist es natürlich so, dass wenn ich hier... 25:30.300 --> 25:33.380 Ich habe jetzt einen Präfix hier. 25:34.700 --> 25:35.720 Das heißt Alpha. 25:38.740 --> 25:46.820 Und das tritt auch hier auf am Ende von dem Pattern, bevor dieser 25:46.820 --> 25:48.520 Mismatch existiert. 25:49.100 --> 25:50.200 Auch hier Alpha. 25:51.300 --> 25:58.560 Dann ist jetzt die Idee, dass ich dieses Pattern so verschiebe, dass 25:58.560 --> 26:05.460 dieses Alpha, das hier als Präfix von dem Pattern existiert, aliniert 26:05.460 --> 26:13.320 wird auf dieses Vorkommen als Suffix von diesem Pattern bis zur Stelle 26:13.320 --> 26:15.340 J minus 1. 26:16.040 --> 26:24.600 Das heißt, nachher will ich es so haben, dass dieses Pattern so 26:24.600 --> 26:32.340 anliegt, dass hier dieses Alpha, quasi diese ersten zwei Positionen, 26:33.160 --> 26:33.380 matcht. 26:35.800 --> 26:39.220 Und dann das dann natürlich dahinter wieder auftritt und dann das so 26:39.220 --> 26:40.440 weitergeht. 26:40.440 --> 26:45.440 Das heißt, ich verschiebe hier um. 26:46.260 --> 26:49.920 Naja, dieser Shift, den ich hier mache, 26:52.960 --> 27:07.180 der ist jetzt dieses J minus 1 bin ich hier. 27:09.500 --> 27:15.980 Und dann ziehe ich das Alpha ab und dann habe ich quasi diese Distanz. 27:17.240 --> 27:19.480 Also minus Alpha. 27:24.460 --> 27:34.960 Wenn man das so macht, dann muss dieses Präfix natürlich gewisse 27:34.960 --> 27:38.060 Eigenschaften haben, dass man da nichts überspringt. 27:46.790 --> 27:51.890 Und die Eigenschaft, die es haben muss, ist, dass es das längste 27:51.890 --> 27:59.930 Präfix ist, das da auch echtes Suffix ist, das quasi aliniert wurde. 28:01.350 --> 28:08.490 Weil wenn da irgendwas Kleines wäre, der wäre irgendwie ein Beta, das 28:08.490 --> 28:17.950 quasi nur ein Buchstabe groß wäre und das tritt dahinter wieder auf, 28:18.090 --> 28:22.550 dann kann es sein, dass das Beta quasi auch dazwischen ist und dann 28:22.550 --> 28:25.470 könnte man das überspringen. 28:30.450 --> 28:38.990 Das ist so ein Fall, wo das dann nicht funktionieren würde, wenn das 28:38.990 --> 28:39.770 nicht das Längste wäre. 28:40.950 --> 28:44.370 Vielleicht können wir das in der Übung mal machen, was da passiert, 28:44.690 --> 28:46.050 wenn das nicht das Längste ist. 28:50.750 --> 29:03.050 Und jetzt, nicht jedes Mal, jetzt müsste ich ja dieses längste Präfix, 29:03.750 --> 29:07.870 das auch echtes Suffix ist, bis zu einer Position J, wenn ich das 29:07.870 --> 29:12.130 jedes Mal berechne, dann müsste ich ja jedes Mal durch das Pattern 29:13.830 --> 29:15.590 jedes Mal das bestimmen. 29:15.910 --> 29:22.450 Ich gehe von der ersten Position und schaue danach, ob der erste 29:22.450 --> 29:25.270 Buchstabe oder der letzte Buchstabe hier ist und dann sage ich okay, 29:25.970 --> 29:29.030 vielleicht finde ich, dass Länge 2 hat, also ob der erste und zweite 29:29.030 --> 29:32.870 Buchstabe vielleicht der erste und zweitletzte Buchstabe sind usw. 29:33.350 --> 29:35.110 Das wäre ein bisschen ineffizient. 29:36.310 --> 29:41.290 Aber weil das Pattern ja immer gleich ist, kann man das vorberechnen, 29:41.550 --> 29:42.510 diese Information. 29:43.430 --> 29:47.450 Das heißt, das speichert man sich ab in eine Tabelle und diese Tabelle 29:47.450 --> 29:49.330 ist das sogenannte Border Array. 29:50.590 --> 30:01.910 Das heißt, dieses Alpha, das entspricht jetzt dem Border Array Eintrag 30:01.910 --> 30:10.550 an Stelle J und der ist genau so definiert, dass die Länge des 30:10.550 --> 30:12.610 längsten Präfixes 30:19.950 --> 30:25.790 das auch suffix das, genau, Präfixes von und jetzt ist das nur bis, 30:25.890 --> 30:33.690 natürlich Präfix nicht von P, sondern nur P von 1 bis Position J-1, 30:38.890 --> 30:44.650 das auch echtes, und jetzt muss ich gleich erklären, was echtes heißt, 30:45.130 --> 30:54.370 echtes Suffix von P1 bis J-1 ist. 30:55.670 --> 31:01.630 Das echte Suffix heißt, dass dieses Suffix nicht der komplette String 31:01.630 --> 31:01.890 ist. 31:02.330 --> 31:10.530 Wenn es der komplette String wäre, dann wäre das Alpha gleich J-1 und 31:10.530 --> 31:14.510 dann wäre unser Shift 0 und wenn man dann quasi um 0 shiftet, ist es 31:14.510 --> 31:18.310 schlecht, weil dann kommen wir nicht voran und der Algorithmus dauert 31:18.310 --> 31:19.890 unendlich lang. 31:21.350 --> 31:26.910 So ist quasi echtes Suffix definiert, dass das quasi nicht der 31:26.910 --> 31:27.990 komplette String ist. 31:31.450 --> 31:38.970 Dann gibt es so Randfälle, die man da betrachten müsste, das heißt, da 31:38.970 --> 31:45.930 gibt es so Border von 0, hier steht quasi 1 und J-1 und wenn das J 31:45.930 --> 31:50.490 gleich 0 ist, dann müssen wir das entsprechend definieren, dass es gut 31:50.490 --> 31:53.130 ist und das ist so definiert, dass es Minus 1 ist, also nach dem 31:53.130 --> 31:59.630 selben Algorithmus, dass es gut ist und Border von 1, da ist es so, 31:59.890 --> 32:06.130 dass dieses P von 1 bis J-1, das ist das P von 1 bis 1 und da ist 32:06.130 --> 32:11.570 immer dieses, das echte Suffix gibt es da nicht oder ist quasi immer 32:11.570 --> 32:16.370 das echte Suffix, auch das Präfix, genau, dieses Suffix ist quasi 32:16.370 --> 32:18.950 immer der komplette String, also ist kein echtes Suffix und darum 32:18.950 --> 32:19.650 definieren wir das 0. 32:19.970 --> 32:23.170 Das heißt, diese zwei erste Einträge in diesem Border-Array, die sind 32:23.170 --> 32:27.750 Minus 1 und 0 und die funktionieren da auch immer schön und wenn sie 32:27.750 --> 32:32.310 quasi so eine Border-Tabelle oder Array berechnet, dann können sie 32:32.310 --> 32:38.230 immer schon bei 2 anfangen, weil die ersten zwei Einträge, die sind so 32:38.230 --> 32:38.710 faszinierend. 32:45.970 --> 32:50.430 Und jetzt schauen wir uns den Algorithmus nochmal an, den werfe ich 32:50.430 --> 32:51.550 jetzt auf diese Wand. 33:10.680 --> 33:16.540 Jetzt müssen wir uns erst einmal um die Laufzeit kümmern, wie denn das 33:16.540 --> 33:16.960 aussieht. 33:18.760 --> 33:19.560 Die Laufzeit... 33:19.560 --> 33:22.960 Na, also ich habe jetzt genau das ist, was ich... 33:23.820 --> 33:25.600 Ah, das ist immer noch naiv. 33:26.100 --> 33:26.960 Gehen wir mal... 33:28.740 --> 33:32.060 Das habe ich jetzt auch als Folienbild nochmal, was ich hier 33:32.060 --> 33:32.740 anzeichnet habe. 33:34.020 --> 33:35.820 Genau, und jetzt sind wir hier beim Algorithmus. 33:36.300 --> 33:40.520 So, genau, das sind zwei Weißschleifer, eine mit dem I, und I geht 33:40.520 --> 33:48.740 immer durch den Text, heißt, die maximale Position, an der es in dem 33:48.740 --> 33:53.500 Pattern vorkommt, dann ist genau Position N minus N plus 1. 33:53.980 --> 33:57.680 Wenn man weiter geht, dann ist der Rest vom Text nicht so groß. 34:01.980 --> 34:06.340 Jetzt haben wir eine innere Schleife mit J. 34:06.440 --> 34:08.380 J ist dieser Index im Pattern. 34:10.120 --> 34:17.180 Und solange quasi diese Buchstabenposition I plus J minus 1 34:17.180 --> 34:23.660 übereinstimmt mit unserem Patternbuchstaben, dann Position J. 34:26.020 --> 34:26.640 Genau, PJ. 34:27.680 --> 34:31.800 Solange gehen wir da in unserem Matching-Algorithmus nach vorne im 34:31.800 --> 34:32.160 Pattern. 34:33.220 --> 34:36.100 Und dann haben wir noch die Bedingung natürlich, dass dieses J kleiner 34:36.100 --> 34:40.820 gleich ist als dieses M, weil wenn das gleich M ist, genau, wenn das 34:40.820 --> 34:44.840 größer wird als M, das heißt dann, dass wir quasi das gesamte Pattern 34:44.840 --> 34:46.060 gefunden haben und wir sind glücklich. 34:46.940 --> 34:47.080 So. 34:49.060 --> 34:53.940 Genau, und wenn das der Fall ist, hier müsste ich dieses Return, 34:55.080 --> 34:59.180 genau, das Return heißt quasi, ich gebe nur die erste Position aus und 34:59.180 --> 35:01.260 ich müsste es nur einrücken im Pseudocode. 35:01.940 --> 35:02.400 Okay. 35:03.600 --> 35:05.420 Und genau, dann haben wir das gefunden. 35:05.420 --> 35:10.460 In allen Fällen machen wir diese Operation, die ich vorgeführt habe. 35:10.720 --> 35:16.940 Also wir verschieben dieses Pattern genau so weit, also wir holen das 35:16.940 --> 35:19.920 um J minus 1 minus dieses Border von J. 35:22.880 --> 35:25.880 Und genau, aber jetzt haben wir da hier zwei Schleifen, zwei 35:25.880 --> 35:29.760 Wahlschleifen und jetzt kann man ja skeptisch sein und sagen, ja, 35:29.980 --> 35:33.320 vielleicht braucht dieser Algorithmus ja genauso lang wie dieser 35:33.320 --> 35:35.840 Algorithmus, wie dieser naive Algorithmus. 35:35.960 --> 35:41.080 Also muss man jetzt argumentieren, warum dieser Algorithmus schneller 35:41.080 --> 35:48.680 ist und deutlich schneller, weil wir sind von N mal M nach N plus M. 35:49.480 --> 35:50.040 Ja, so. 35:50.800 --> 35:54.800 Und wenn man sich das, genau, wenn man sich das anschaut, naja, da 35:54.800 --> 36:03.080 gibt es jetzt wieder zwei Fälle, also die Analyse, Analyse der 36:03.080 --> 36:09.960 Komplexität, nämlich in einem Fall. 36:13.600 --> 36:19.700 Also das erste ist, dass man quasi so, und das mache ich jetzt mit 36:19.700 --> 36:29.280 zwei Fällen, einmal so, da sage ich, da stimmt Buchstabe TI, Buchstabe 36:29.280 --> 36:42.860 TI, stimmt mit PJ überein, oder bei I plus J überein. 36:47.450 --> 36:53.010 Na, ich mache jetzt, genau, ich mache jetzt hier, hier, nur ein J, nur 36:53.010 --> 36:53.790 ein J, das reicht schon. 36:54.150 --> 36:55.330 Okay, das ist der erste Fall. 36:55.910 --> 37:00.410 Und der zweite Fall ist, dass es nicht übereinstimmt, und da mache ich 37:00.410 --> 37:08.050 hier so einen Runterkeil, so, und genau, das ist dann Buchstabe, 37:11.820 --> 37:13.860 Buchstabe TI, stimmt nicht, 37:17.940 --> 37:21.920 nicht mit PJ überein. 37:26.020 --> 37:27.120 Naja, so. 37:28.820 --> 37:34.320 Und wenn man sich das so anschaulicht, ja, also man bewegt sich ja im 37:34.320 --> 37:36.260 Pattern, und man bewegt sich auch im Text. 37:36.740 --> 37:44.320 So, und ich sage, das ist quasi die Richtung, in der ich mich im Text 37:44.320 --> 37:47.040 bewege, das ist quasi, wie ich mich im Pattern bewege. 37:48.900 --> 37:54.520 Das heißt, wenn da was matcht, dann bewege ich mich im Pattern, und 37:54.520 --> 37:57.180 auch im Text, bewege ich mich quasi vorwärts. 37:57.840 --> 38:04.360 So, und jetzt habe ich dann diese Verschiebetabelle, das heißt, wenn 38:04.360 --> 38:12.680 da irgendwann mal ein Missmatch kommt, dann geht es hier im Pattern 38:13.460 --> 38:17.940 vielleicht ein, vielleicht zwei, verschiedene Positionen runter, ja, 38:18.300 --> 38:19.180 durch diese Verschiebetabelle. 38:22.320 --> 38:27.940 So, und dann geht es, geht es vielleicht dann nochmal runter, wenn ich 38:27.940 --> 38:31.260 das nächste match, und dann geht es wieder hoch. 38:33.380 --> 38:38.260 So, und jetzt muss man sich überlegen, wie oft, wie viele Schritte 38:38.260 --> 38:44.400 kann ich, also wie viele Schritte mache ich da in diesem Gitter, das 38:44.400 --> 38:44.900 ich da habe. 38:45.660 --> 38:48.040 Ja, und ich kann, 38:51.360 --> 38:55.600 also das ist genau das, ich kann, also ich bin sehr interessiert, 38:56.400 --> 38:59.980 diese innere Schleife zu zählen, ja, und in dieser inneren Schleife, 39:01.980 --> 39:07.080 da kann ich aber nur so oft quasi im Pattern wieder runter gehen, wie 39:07.080 --> 39:07.740 ich schon gematcht habe. 39:11.800 --> 39:18.000 Und im Text gehe ich quasi immer vorwärts, das heißt, diese Matches, 39:18.820 --> 39:25.260 das kann höchstens n sein, folglich kann ich auch höchstens n Mal 39:25.260 --> 39:27.020 wieder da runter gehen. 39:28.060 --> 39:35.160 Das heißt, das ist eine amortisierte Analyse, die uns dann auf 2n 39:35.160 --> 39:42.500 Vergleiche bringt, in diesem Algorithmus. 39:45.100 --> 39:45.200 Genau. 39:45.460 --> 39:51.980 Plus, ich muss dieses Border Array, ja, plus Komplizität, 39:55.580 --> 40:03.420 plus Komplizität, um Border Array zu berechnen. 40:12.080 --> 40:12.360 Genau. 40:16.400 --> 40:21.100 Und genau, das kommt dann natürlich als nächstes, wie ich diesen 40:21.100 --> 40:22.080 Border Array berechne. 40:29.210 --> 40:33.250 Ich könnte auch ein Beispiel machen, wie das nochmal funktioniert. 40:35.750 --> 40:39.490 Dann mache ich das mal schnell, bevor ich das Border Array berechne, 40:40.430 --> 40:41.310 bevor ich die mache. 40:45.070 --> 40:53.910 Beispiel, wieder Text, a, a, n, a, a, n, a, a, und dann berechnen wir 40:53.910 --> 41:00.390 mal, für den Pattern berechnen wir jetzt auch mal dieses Border Array, 41:01.310 --> 41:09.030 a, n, a, a, okay, und dieses Border Array, ja, wir haben gesagt, für 41:09.030 --> 41:17.410 Eintrag 0 war das minus 1, dann kommt dieses erste Ding, und jetzt 41:17.410 --> 41:24.110 habe ich hier quasi, ich schaue an, dieses Prefix, und das Prefix ist 41:24.110 --> 41:30.030 zu der Stelle hin, genau, ist genau auch dieses Suffix, und das Suffix 41:30.030 --> 41:34.550 ist dann aber der ganze Text bis zur Position, also alles bis zur 41:34.550 --> 41:39.650 Position inklusive 1, darum haben wir diese Definition, dass es 41:39.650 --> 41:40.250 eigentlich 0 war. 41:41.570 --> 41:49.250 Im nächsten Schritt haben wir hier ein a und ein n, das n stimmt ja 41:49.250 --> 41:52.830 nicht mit a überein, also gibt es hier auch immer noch kein Suffix, 41:52.830 --> 41:57.750 das ist kein echtes Suffix, das auch ein Prefix ist, ist immer noch 41:57.750 --> 42:03.710 Position 0, und immer noch die Länge 0, bei diesem a jetzt, da 42:03.710 --> 42:07.950 betrachten wir quasi alles bis j minus 1, das heißt, das ist dieses 42:07.950 --> 42:12.650 ganze Ding, und da ist jetzt dieses a hier, kommt auch davor, also ist 42:12.650 --> 42:18.590 es auf jeden Fall mal 1, und ein größeres, also a, n, ist ein längeres 42:18.590 --> 42:25.070 Prefix, aber es gibt kein a, n als Suffix, von daher ist das Maximale, 42:25.270 --> 42:26.550 was man reichen kann, ist 1. 42:28.150 --> 42:33.690 Und jetzt gibt es nochmal einen Fall, wenn ich quasi was match, dann 42:33.690 --> 42:37.970 betrachte ich auch, dann berechne ich hier bei diesem Border Array 42:37.970 --> 42:43.870 auch dieses letzte Element, obwohl da kein Buchstabe steht, das heißt, 42:44.090 --> 42:48.370 hier schaut man dann wieder, okay, das ist wieder das längste echte 42:48.370 --> 42:52.650 Suffix, das Prefix ist, okay, ich habe hier ein a, das ist auf jeden 42:52.650 --> 42:56.310 Fall auf Länge 1, denn a, n gibt es hier nicht, folglich gibt es auch 42:56.310 --> 43:00.210 a, n, a, nicht hier drin, weil das n ja quasi nur da vorne vorkommt. 43:00.670 --> 43:03.830 Das heißt, ich hätte hier wieder die Länge 1. 43:05.110 --> 43:11.370 Und jetzt anhand dieser Tabelle, fülle ich den Algorithmus jetzt mal 43:11.370 --> 43:17.430 aus, ich habe hier ein a, und dann kommt ein Mismatch, weil ich habe 43:17.430 --> 43:26.090 hier dann ein n, okay, und naja, jetzt benutze ich dann also dieses 43:26.090 --> 43:33.530 Border Array an Position 2, da steht ein 0 drin, also verschiebe ich 43:33.530 --> 43:43.230 um j-1, j war 2, minus dieses Border Array Eintrag, der ist 0, also um 43:43.230 --> 43:43.550 1. 43:50.550 --> 43:51.030 Einverstanden? 43:51.170 --> 43:53.010 Ja, genau so haben wir es definiert. 43:53.870 --> 43:59.290 Das heißt, hier haben wir ein Match, dann gibt es ein weiterer Match 43:59.290 --> 44:04.530 mit diesem n, a, a, und genau. 44:04.770 --> 44:07.130 Und jetzt sind wir quasi am Ende von diesem Ding. 44:07.650 --> 44:11.070 Unser Algorithmus würde jetzt quasi sagen, okay, diese Bedingung, dass 44:11.070 --> 44:15.770 dieses j kleiner sein muss als m, die gilt nicht mehr. 44:16.070 --> 44:19.690 Okay, das heißt, wir brechen hier ab, dann gibt es hier einen Haker, 44:19.810 --> 44:21.690 und jetzt, genau, wenn man jetzt verschiebt, 44:25.530 --> 44:31.710 verschieben wir, genau, jetzt sind wir, ist quasi, unser j ist dann 44:31.710 --> 44:46.850 gleich 5, und ich verschiebe dann um 5, 5 minus 1 und nochmal minus 1, 44:46.930 --> 44:51.150 wenn ich das richtig habe, ja, also genau, 5 minus 1, das sind wir in 44:51.150 --> 44:55.770 der Position, und dann ziehen wir diesen Eintrag hier ab, dieses 44:55.770 --> 44:56.810 Alpha, genau. 44:57.370 --> 45:00.830 Das heißt, das verschieben wir jetzt um 3, und dann aligniere ich also 45:00.830 --> 45:05.490 dieses a, das erste a von dem Pattern wieder da, und das heißt, ich 45:05.490 --> 45:09.350 habe hier wieder diesen ersten Vergleich, habe ich wieder gespart. 45:10.650 --> 45:14.210 Dann gibt es hier wieder den Missmatch mit dem n, und so weiter. 45:16.450 --> 45:19.990 Okay, das heißt, wenn wir einfach nur zeigen, dass wir dieses Border 45:19.990 --> 45:27.090 Array in O von m konstruieren können, dann haben wir gezeigt, dass wir 45:27.090 --> 45:27.990 diese Komplizität haben. 45:28.770 --> 45:32.870 Und das wirklich nette an diesem Algorithmus ist, dass diese 45:32.870 --> 45:37.330 Argumentation, dass man jetzt quasi bei der Konstruktion dieses Border 45:37.330 --> 45:41.550 Arrays kann man quasi fast den gleichen Algorithmus wieder anwenden. 45:42.830 --> 45:45.450 Und darum habe ich auch letztes Jahr eine Klausuraufgabe gestellt, in 45:45.450 --> 45:52.670 der es um diesen Algorithmus ging, weil da kann man irgendwie immer 45:52.670 --> 45:57.290 schöne Klausuraufgaben stellen, wo man das variiert, dieses Schema. 45:57.290 --> 45:59.850 So, genau. 46:00.630 --> 46:03.290 Da kam dann die Frage, wie... 46:04.010 --> 46:10.290 genau, weil ich habe so ein Border Array und... 46:12.090 --> 46:13.210 wie habe ich das gemacht? 46:13.350 --> 46:16.110 Ich habe ein Border Array... 46:16.110 --> 46:20.390 genau, ich muss erst ein Border Array Konstruktionsalgorithmus machen, 46:20.610 --> 46:22.210 bevor ich das sage. 46:22.910 --> 46:24.790 Okay, so, das ist es hier. 46:26.010 --> 46:32.770 Schauen wir uns einmal an, diesen Algorithmus und das Bild dazu. 46:36.510 --> 46:36.590 Genau. 46:38.930 --> 46:45.450 Also, geht es mal davon aus, dass wir jetzt dieses Border Array schon 46:45.450 --> 46:50.450 mal bis zu einer bestimmten Position j gerechnet haben. 46:52.210 --> 46:55.330 So, oder j-1. 46:56.330 --> 47:07.690 Das heißt, ich weiß dann schon für die Position j-1, was denn das 47:07.690 --> 47:13.110 längste echte Suffix ist, das auch Präfix ist in diesem Pattern. 47:13.390 --> 47:14.130 Das weiß ich schon. 47:16.290 --> 47:22.130 Und jetzt will ich das erweitern auf die Position j. 47:22.130 --> 47:26.430 So, an Position j lese ich jetzt ein Buchstabe, da ist es vielleicht 47:26.430 --> 47:26.750 y. 47:29.770 --> 47:33.510 Und weil ich ja die Länge weiß, das längste Präfix, das das Suffix 47:33.510 --> 47:40.390 ist, und dieses längste Präfix quasi auch erweitern will, schaue ich 47:40.390 --> 47:49.090 nach, ob der nächste Buchstabe von meinem Präfix, ob der gleich ist 47:49.090 --> 47:50.910 mit meinem y. 47:51.230 --> 47:55.230 Das ist als nächstes Buchstabe von meinem längsten echten Suffix. 47:57.230 --> 48:01.370 Wenn das der Fall wäre, dann könnte ich nämlich hier im Border Array 48:01.370 --> 48:05.770 quasi einfach die vorgehende Zahl nehmen und plus eins dazu addieren 48:06.310 --> 48:07.170 und dann wäre ich fertig. 48:09.630 --> 48:10.750 So, genau. 48:11.390 --> 48:18.450 Wenn das nicht der Fall ist, dann will ich jetzt auch nicht wieder 48:18.450 --> 48:19.450 alles neu berechnen. 48:20.390 --> 48:26.470 Das heißt, ich könnte ja dann, dann habe ich jetzt quasi dieses 48:26.470 --> 48:30.890 längste echte Suffix, das auch Präfix ist. 48:32.230 --> 48:38.030 Ist jetzt quasi rekursiv ja auch für dieses längste echte Suffix, das 48:38.030 --> 48:41.170 auch Präfix ist, habe ich ja rekursiv wieder definiert, was für dieses 48:41.170 --> 48:46.410 Alpha wieder das längste Suffix ist, das auch echtes Präfix ist. 48:47.010 --> 48:50.850 Das heißt hier dieses Beta. 48:54.070 --> 48:57.670 Und das heißt, das wäre dann quasi der nächste Kandidat, der da in 48:57.670 --> 49:01.970 Frage kommt, als längstes Suffix, das auch Präfix ist. 49:02.410 --> 49:08.610 Das heißt, ich würde jetzt dann den Buchstabe Y, würde ich jetzt dann 49:08.610 --> 49:11.010 wieder mit dem Buchstabe Z vergleichen. 49:12.210 --> 49:16.970 Und ich mache das rekursiv so lang, bis ich was finde, weil entweder 49:16.970 --> 49:20.690 das gleich ist, dann kann ich den entsprechenden Eintrag um 49:20.690 --> 49:21.730 einzuhöhen. 49:23.970 --> 49:31.750 Und am Ende komme ich quasi an bei der Position, wo der Border-Rate 49:31.750 --> 49:35.350 ist minus 1 dran stehe ich habe, und dann erhöhe ich aber das minus 1 49:35.350 --> 49:36.490 und dann kriege ich 0 raus. 49:37.350 --> 49:42.070 Also so geht es von Start an, dieser Algorithmus. 49:50.360 --> 49:57.160 Das heißt, wenn man jetzt da hier auch wieder die Kompensationsanalyse 49:57.160 --> 49:57.640 machen will, 50:01.860 --> 50:08.140 dann gehe ich ja hier wieder in diesem Pattern, gehe ich ja wieder 50:08.140 --> 50:15.960 jeden Schritt, also es sind wieder zwei Streifen, also ich gehe durch 50:15.960 --> 50:22.500 dieses Pattern durch, von Position 2 an, weil die ersten zwei Einträge 50:22.500 --> 50:23.940 schon fest definiert sind. 50:26.600 --> 50:37.140 Und wenn ich es nicht erweitern kann, dann erniedrige ich dieses Y und 50:37.140 --> 50:44.000 deswegen quasi gerade den Border-Rate-Eintrag von Stelle i, von Stelle 50:44.000 --> 50:47.740 i plus 1. 50:50.650 --> 50:52.210 Warum mache ich es denn plus 1? 51:02.770 --> 51:06.770 Genau, weil da die Länge steht, an i plus 1 steht ja die Länge von dem 51:06.770 --> 51:09.710 nächsten Präfix, das auf Suffix ist, an Position i. 51:10.470 --> 51:12.630 Genau, das steht an i plus 1. 51:12.630 --> 51:17.750 Da gibt es so ein Offset drin, wenn man das quasi immer exklusiv 51:17.750 --> 51:19.430 macht, in diesem Border-Rate. 51:20.290 --> 51:22.810 Genau, das ist noch wichtig zu wissen. 51:23.010 --> 51:24.730 Genau, da steht ja hier, das ist i plus 1. 51:27.710 --> 51:33.170 Genau, und dann zählen wir quasi 1 dazu, weil dann die Buchstaben hier 51:33.170 --> 51:38.070 nach dieser Bedingung übereinstimmen oder dieses Ding gleich kleiner 51:38.070 --> 51:39.030 als... 51:39.030 --> 51:42.090 Also wenn wir ganz am Anfang angekommen sind, dann steht ja quasi 51:42.090 --> 51:46.090 minus 1 drin, dann ist dieses i plus plus, erhöht es dann wieder auf 51:46.090 --> 51:48.570 0, dass es schön definiert ist. 51:49.170 --> 51:49.930 Okay, so. 51:50.410 --> 51:55.090 Und jetzt ist es so, dass natürlich hier wieder das gleiche gilt für 51:55.090 --> 51:58.130 diese Laufjahre I und für J. 51:58.130 --> 52:10.690 Ich kann dieses durch J, das läuft bis M, also O von M, und dieses i 52:10.690 --> 52:17.530 kann ich nur so oft erniedrigen, dekrementieren vielleicht besser, wie 52:17.530 --> 52:18.430 ich es hochzählt habe. 52:19.470 --> 52:24.750 Und das ist jedes Mal beim Match und das kann wieder höchstens M Mal 52:24.750 --> 52:26.310 in diesem Fall passieren. 52:27.150 --> 52:33.430 Das heißt insgesamt habe ich wieder die gleiche Analyse wie vorher, 52:33.850 --> 52:37.470 dass ich insgesamt wieder zwei M Vergleiche habe. 52:38.150 --> 52:42.510 Und das heißt, diese ganze Konstruktion liegt in O von M. 52:44.190 --> 52:50.710 So, jetzt haben wir diese Vorberechnung in O von M und dieses Matching 52:50.710 --> 52:57.050 in O von N und es gibt dann insgesamt eine Kompensität von O von N 52:57.050 --> 53:00.630 plus M für unseren Algorithmus. 53:01.470 --> 53:06.750 Okay, da gibt es natürlich jetzt, das ist jetzt aber leider, genau, 53:06.950 --> 53:09.190 habe ich keine Folien dafür, erzähle ich nur so. 53:10.230 --> 53:13.270 Beim Pattern Matching gibt es natürlich auch Algorithmen, die noch 53:13.270 --> 53:16.510 sehr viel schneller sein können, potenziell. 53:18.170 --> 53:23.730 Und das ist, ja da gibt es, also hier matchen wir ja von links nach 53:23.730 --> 53:24.930 rechts im Pattern. 53:26.330 --> 53:30.970 Und man kann das natürlich auch so machen, dass wenn ich hier 53:30.970 --> 53:36.510 irgendwie einen Text habe und einen Pattern, dann steht da vielleicht 53:36.510 --> 53:37.750 irgendwie XY hinter dran. 53:39.230 --> 53:45.710 Das fängt irgendwie hier an und dann vergleiche ich einfach mal, fange 53:45.710 --> 53:49.730 ich von rechts an und vergleiche hier, dann stimmt es nicht überein. 53:49.730 --> 53:54.930 Und dann kann ich das Pattern schon, genau, sagen wir mal, wenn da 53:54.930 --> 53:57.470 jetzt irgendwie, dann schreiben wir es sich noch ab für jeden 53:57.470 --> 54:00.770 Buchstabe, wo das erste Mal vorkommt in diesem Pattern. 54:01.290 --> 54:05.370 Wenn das Y das erste Mal hier vorkommt, oder nee, ich will mir quasi 54:05.370 --> 54:08.070 abstrahlen, wo das B vorkommt. 54:08.070 --> 54:12.570 Wenn das B da als erstes Mal vorkommt, also die linkeste Position, in 54:12.570 --> 54:16.750 der es vorkommt in dem Pattern, dann aligniert es so, dass dann das B 54:16.750 --> 54:20.730 genau hier aligniert ist, also das erste B. 54:21.490 --> 54:25.730 Und dann vergleiche ich wieder hier vorne nach dem Y und wenn dann Y 54:25.730 --> 54:30.350 vorkommt, dann matche ich dann quasi nach links. 54:31.010 --> 54:35.810 Und somit kann man quasi mit einem Alignierer schon mehrere, also bis 54:35.810 --> 54:40.270 zu Patternlänge, viele Buchstabe überspringen. 54:40.690 --> 54:44.510 Und wenn man dann Glück hat, kommt dann eben so eine Laufzeit raus von 54:44.510 --> 54:51.710 O von N durch M und das ist natürlich dann sehr viel schneller. 54:51.710 --> 54:55.290 Aber im Worst-Case ist das eben auch nicht schnell. 54:55.470 --> 55:03.930 Also genau, da gibt es keine Worst-Case-Garantie in diesem Fall. 55:04.410 --> 55:10.050 Aber sowas, wenn Sie in die Literatur schauen, da gibt es den Boyer 55:10.050 --> 55:15.030 -Moore -Horstpul-Algorithmus, der beruht auf dem Prinzip. 55:15.030 --> 55:20.650 Und der wird dann in der Praxis auch eingesetzt. 55:21.670 --> 55:21.670 Genau, 55:24.990 --> 55:31.870 das wäre quasi unser Ausflug in dieses Online-Pattern-Matching. 55:31.870 --> 55:40.750 Also nichts vorberechnet und ich will ohne Vorberechnung im Text 55:40.750 --> 55:43.250 machen. 55:47.630 --> 55:56.130 Jetzt kommen wir dann zur Volltextsuche mit Vorberechnung, also mit 55:56.130 --> 55:57.250 Vorverarbeitung. 55:58.530 --> 56:05.270 Das heißt, ich baue mir da einen Index auf und dann will ich jetzt 56:05.270 --> 56:08.430 wissen, wo kommt das Pattern vor oder kommt es überhaupt vor in dem 56:08.430 --> 56:09.190 Text. 56:11.930 --> 56:18.650 Wenn es vorkommt, wie oft kommt es vor und wenn es oft vorkommt, will 56:18.650 --> 56:22.790 ich auch wissen, wo es vorkommt oder in welchem Dokument es vorkommt, 56:22.850 --> 56:24.010 wenn es mehrere Strings sind. 56:25.870 --> 56:31.850 Genau, wir haben gesehen, dass dieser naive Ansatz N mal M nicht gut 56:31.850 --> 56:32.030 ist. 56:33.350 --> 56:37.030 Wenn wir da dieses Pattern vorverarbeiten, haben wir dieses N plus M, 56:37.770 --> 56:42.050 aber wenn man den Text vorverarbeitet hat, dann kann man das ganz 56:42.050 --> 56:44.290 unabhängig von diesem N machen. 56:45.270 --> 56:51.050 Das heißt, ich habe eine Anfragezeit, die ist sogar nur abhängig vom 56:51.050 --> 56:52.590 Pattern, also auch von M. 56:59.250 --> 57:03.990 Einen Index, den ich vorstellen will, ist dieses Suffix Array und der 57:03.990 --> 57:09.290 hat eine Kompensität von M mal Log N, wenn man quasi nur diesen Suffix 57:09.290 --> 57:11.350 Array plus den Originaltext verwendet. 57:12.350 --> 57:18.710 Da kann man dann verschiedene Zusatzinformationen dazu tun, dann habe 57:18.710 --> 57:23.310 ich die optimale Kompensität von O von M. 57:24.050 --> 57:28.270 Ein anderer Index wäre der Suffix Baum, der kommt hier auch noch dran. 57:29.270 --> 57:34.110 Da ist dieser Algorithmus ziemlich trivial, der das in O von M machen 57:34.110 --> 57:39.870 kann, mit dem Suffix Array und dieser Zusatzinformation, das ist ein 57:39.870 --> 57:40.750 bisschen komplexer. 57:42.950 --> 57:46.610 In der Praxis, also wenn Sie z.B. 57:47.350 --> 57:53.910 so eine Suchmaschine benutzen, so eine Web-Suchmaschine, da steckt 57:53.910 --> 57:57.840 kein Suffix Array dahinter, da steckt ein Inverted Index dahinter. 57:57.840 --> 58:05.520 Und dieser Inverted Index, der heißt Inverted, weil er invertiert 58:05.520 --> 58:06.440 quasi den Text. 58:08.560 --> 58:13.200 Das ist jetzt quasi zur Information, wie das so funktioniert. 58:14.140 --> 58:19.020 Das wollen wir nicht behandeln, weil die Garantien, die da dahinter 58:19.020 --> 58:20.720 liegen, sind nicht besonders gut. 58:21.280 --> 58:25.560 Das macht der Web-Suchmaschine auch nichts, weil die Web-Suchmaschine 58:25.560 --> 58:30.520 zeigt auch nicht immer das an, findet auch nicht immer alles. 58:32.000 --> 58:44.720 Aber wir wissen das nicht, weil wir ja auch kein Wissen haben über 58:44.720 --> 58:47.220 alle Dokumente, die im Internet existieren. 58:47.220 --> 58:48.460 Merkt man das gar nicht. 58:48.800 --> 58:49.900 Das ist vielleicht gar nicht so. 58:53.940 --> 58:58.720 Das heißt, wenn ich jetzt eine Text-Kollektion habe, wie diese sechs 58:58.720 --> 59:13.460 Dokumente, dann sieht der Inverted Index so aus, dass man für jedes 59:13.460 --> 59:22.620 Dokument, oder für jedes Wort, schreibt man sich auf, in welchem 59:22.620 --> 59:24.200 Dokument dieses Wort vorkommt. 59:24.860 --> 59:34.000 Das heißt, das funktioniert nur gut für natürlichsprachige Texte, wo 59:34.000 --> 59:36.520 das Vokabular vorher fest definiert ist. 59:36.520 --> 59:42.620 Also wenn ich DNA-Strings habe, was ist denn da das Vokabular? 59:42.740 --> 59:43.800 Das weiß man nicht so genau. 59:45.980 --> 59:50.260 Aber bei natürlichsprachigem Text natürlich, da kann ich mir jetzt so 59:50.260 --> 59:52.440 eine Liste machen. 59:52.440 --> 59:59.620 Ich habe einen Term T, dieses End zum Beispiel, und dieses End taucht 59:59.620 --> 01:00:03.340 in Dokument Nummer 2 auf und wie oft? 01:00:03.540 --> 01:00:04.160 Zweimal. 01:00:05.180 --> 01:00:11.200 Big, dieses Wort taucht in Dokument 2 auf zweimal und in Dokument 3 01:00:11.200 --> 01:00:12.960 taucht es einmal auf. 01:00:12.960 --> 01:00:16.120 Also das wäre quasi ein Inverted Index. 01:00:16.640 --> 01:00:20.380 Wenn ich jetzt so eine Web-Kollektion habe, dann ist dieses Alphabet 01:00:20.380 --> 01:00:25.920 natürlich dann ein bisschen größer wie hier. 01:00:26.120 --> 01:00:31.740 Das sind dann irgendwie 100 Millionen an Worten, vielleicht auch noch 01:00:31.740 --> 01:00:36.340 mit Tippfelder und so, also alles was da so auftaucht. 01:00:37.140 --> 01:00:42.620 Und dann speichert man sich quasi jetzt für jedes dieses Wort auf, wo 01:00:42.620 --> 01:00:43.180 es vorkommt. 01:00:43.360 --> 01:00:47.060 Wenn ich jetzt allgemein Pattern-Matching machen will, also bisher 01:00:47.060 --> 01:00:50.380 haben wir ja quasi betrachtet, dass dieses Pattern aus Buchstaben 01:00:50.380 --> 01:00:55.500 besteht und jetzt besteht das Pattern aber aus Worten. 01:00:56.340 --> 01:01:00.720 Das heißt, wir suchen eigentlich Sätze. 01:01:02.320 --> 01:01:05.940 Also ich will, dass End und Big hintereinander sind. 01:01:06.220 --> 01:01:10.960 Und wenn ich End und Big suchen will in diesem Index, dann muss ich 01:01:10.960 --> 01:01:14.320 aber schauen, dass End und Big im gleichen Dokument vorkommen. 01:01:14.500 --> 01:01:16.740 Und wenn sie im gleichen Dokument vorkommen, dann bräuchte ich hier 01:01:16.740 --> 01:01:21.420 sogar noch Zusatzinformationen, nämlich die, dass End an Position X 01:01:21.420 --> 01:01:23.560 vorkommt und Big an Position X plus 1. 01:01:24.160 --> 01:01:27.060 In diesem Beispiel von dem invertierter Index ist die nicht dabei, 01:01:27.380 --> 01:01:30.200 gibt es aber auch welche, die speichern sich dazu und dann kann man 01:01:30.200 --> 01:01:32.020 dann durch... 01:01:32.020 --> 01:01:32.960 Ja, was ist die Operation? 01:01:33.820 --> 01:01:38.740 Die Operation ist einfach das Schneiden von diesen Lichten. 01:01:40.320 --> 01:01:44.320 Und darum ist die Worst-Case-Komplexität nämlich auch abhängig von der 01:01:44.320 --> 01:01:45.100 Länge dieser Lichten. 01:01:45.100 --> 01:01:49.260 Also wenn man so eine Lichte hat wie dieses In, dann ist die aber sehr 01:01:49.260 --> 01:01:54.460 groß und in der Realität, wenn man so etwas hat wie die im englischen 01:01:54.460 --> 01:02:03.920 Web, dann sind die Lichten so groß, dass man sie gar nicht betrachtet, 01:02:04.140 --> 01:02:06.240 weil das so viel Aufwand kostet, die Durchzugeher. 01:02:07.560 --> 01:02:12.220 Genau, das kann man jetzt trotzdem irgendwie schön komprimieren, weil 01:02:12.220 --> 01:02:15.940 ich spreche immer so, dass die Integers aufsteigend sind und dann kann 01:02:15.940 --> 01:02:20.740 man da Kompressionsalgorithmen anwenden, die für aufsteigende Lichten 01:02:20.740 --> 01:02:23.920 sind und dann wird das ziemlich klein. 01:02:24.880 --> 01:02:29.140 Genau, aber weil die Komplexität einfach abhängt, wenn man hier 01:02:29.140 --> 01:02:33.300 Pattern -Matching macht, also irgendwie nicht nur von einem wissen 01:02:33.300 --> 01:02:38.400 will, sondern quasi eine Folge, ein Pattern, eine bestimmte 01:02:38.400 --> 01:02:41.800 Reihenfolge, läuft das auf dieses Schneiden von den Lichtern aus. 01:02:42.400 --> 01:02:45.520 Und darum ist das ineffizient. 01:02:46.640 --> 01:02:47.840 Okay, dieser Fall. 01:02:50.980 --> 01:02:54.860 Genau, aber in Websuche machen wir eher so dieses Back-of-Words, also 01:02:54.860 --> 01:02:57.800 ich habe quasi ein Set von Wörtern und ich will quasi ein Dokument, 01:02:58.160 --> 01:03:05.620 das dieses Set enthält, ist diese Anfrage ein bisschen anders als das, 01:03:05.780 --> 01:03:06.940 was mir hier jetzt löst. 01:03:07.680 --> 01:03:09.640 Okay, und wir machen das mit Suffix Arrays. 01:03:10.980 --> 01:03:19.900 Okay, dann gibt es vielleicht auch noch diese Suche mit Fehlern. 01:03:20.680 --> 01:03:25.060 Das heißt, ich will inexakt matchen, das heißt, ich lasse ein bisschen 01:03:25.060 --> 01:03:25.860 Freiheit. 01:03:26.380 --> 01:03:28.320 Das heißt, wenn ich einen Pattern habe, der Länge M, 01:03:32.450 --> 01:03:35.930 dann kann ich hier vielleicht auch definieren, dass ich da höchstens K 01:03:35.930 --> 01:03:39.830 -Fehler mit K-Fehlern matchen will. 01:03:40.730 --> 01:03:47.910 Und da ist die Technik dann so, dass gibt es natürlich verschiedene 01:03:47.910 --> 01:03:53.550 Distanzen, vielleicht die Edges-Distanz aus dem dynamischen 01:03:53.550 --> 01:03:58.290 Programmieren, das ist ein Beispiel, oder Hemming-Distanz, das heißt, 01:03:58.490 --> 01:04:03.610 wenn ich dann die Anzahl verschiedener Positionen in die nicht 01:04:03.610 --> 01:04:07.850 matchenden Positionen, die ich da habe, bei Edges-Distanz, weil ich 01:04:07.850 --> 01:04:10.930 das irgendwie einfüge und lösche, und so weiter. 01:04:12.270 --> 01:04:15.310 Aber zum Beispiel für Hemming-Distanz kann man das dann so machen, 01:04:15.370 --> 01:04:18.850 wenn ich K-Fehler erlaube, würde ich diese Pattern einteilen in K plus 01:04:18.850 --> 01:04:21.710 1 Teile. 01:04:22.470 --> 01:04:28.470 Und wenn ich K-Fehler erlaube, dann muss mindestens eins dieser Teile, 01:04:28.570 --> 01:04:30.690 muss ein exakter Match sein. 01:04:30.870 --> 01:04:33.110 Und dann kann man das zurückführen auf exaktes Matching. 01:04:33.900 --> 01:04:37.110 Wollen wir hier aber auch nicht behandeln. 01:04:42.450 --> 01:04:47.270 Das Wichtigste bei diesem Index, oder eines der wichtigsten Punkte 01:04:47.270 --> 01:04:52.030 ist, dass man diesen Index, wenn man den konstruiert, ziemlich schnell 01:04:52.030 --> 01:04:52.530 bauen kann. 01:04:52.530 --> 01:04:56.870 Also diese invertierte Listen, die sind ziemlich einfach zu bauen, 01:04:56.990 --> 01:05:01.410 weil ich habe meinen Korpus an Dokumenten, ich scanne die und dann 01:05:01.410 --> 01:05:05.330 habe ich eine Hash-Tabelle, die das Wort auf eine bestimmte Position 01:05:05.330 --> 01:05:05.790 hasht. 01:05:06.210 --> 01:05:09.270 Und dann füge ich einfach dieses Dokument, wo es vorkommt, ein. 01:05:10.490 --> 01:05:14.890 Und Suffix Arrays, das was jetzt kommt, da ist es ein bisschen 01:05:14.890 --> 01:05:15.490 komplizierter. 01:05:16.300 --> 01:05:22.810 Der Professor Sanders, zum Juha Kalkine 2003, das ist quasi die 01:05:22.810 --> 01:05:24.470 Journal -Version von seiner Arbeit. 01:05:25.130 --> 01:05:30.370 2003 gab es drei unabhängige Gruppen, also drei Gruppen, die 01:05:30.370 --> 01:05:34.590 unabhängig voneinander einen Linearzeitalgorythmus für die 01:05:34.590 --> 01:05:36.890 Konstruktion dieses Suffix Arrays konnten. 01:05:37.490 --> 01:05:40.790 Und den stelle ich jetzt hier in der Vorlesung vor. 01:05:42.030 --> 01:05:47.530 Genau, so ein bisschen Notation von Arrays. 01:05:47.730 --> 01:05:52.850 Wenn ich hier hinter eine runde Klammer habe, dann heißt es aber 01:05:52.850 --> 01:05:56.070 exklusive dieses Index. 01:05:57.070 --> 01:06:05.310 Genau, das heißt ein String und das Suffix, das ist definiert durch 01:06:05.310 --> 01:06:10.130 den Substring von Suffix si, durch den Substring, der an Position i 01:06:10.130 --> 01:06:14.310 anfängt und dann an Position n aufhört. 01:06:15.570 --> 01:06:19.290 Vorher war es immer bei 1 Starter, jetzt starten wir bei 0 mit diesen 01:06:19.290 --> 01:06:19.710 Strings. 01:06:20.910 --> 01:06:25.870 Weil auch dieser Algorythmus, der hat eine Implementierung, die hängt 01:06:25.870 --> 01:06:26.710 an diesem Paper dran. 01:06:27.190 --> 01:06:30.110 Der ist nur irgendwie 90 Zeile oder 100 Zeile, wenn ich mich richtig 01:06:30.110 --> 01:06:30.490 erinnere. 01:06:31.670 --> 01:06:36.170 Also er ist quasi sehr kurz auch, was auch ein Vorteil ist gegenüber 01:06:36.170 --> 01:06:40.270 all den anderen Algorythmen, die da auch linearzeit- und 01:06:40.270 --> 01:06:43.610 vorgeschlagbar sind, weil die sind ein bisschen komplizierter auch von 01:06:43.610 --> 01:06:44.010 der Struktur. 01:06:44.730 --> 01:06:47.970 Und dann gibt es auch diese Endmarkierung, die ich gesagt habe. 01:06:48.630 --> 01:06:55.690 Also man definiert sich am Ende eine ausreichende Anzahl an Symbolen, 01:06:55.770 --> 01:06:58.970 die quasi lexikografisch kleiner sind als alles andere in diesem 01:06:58.970 --> 01:06:59.310 String. 01:07:00.670 --> 01:07:02.710 Also das heißt hier dann 0. 01:07:03.810 --> 01:07:07.370 Genau, und so sieht dieser Suffix Array jetzt folgendermaßen aus. 01:07:07.690 --> 01:07:11.010 Ich habe einen String, ich nehme hier alle Suffixe. 01:07:12.410 --> 01:07:13.730 Banana heißt der String. 01:07:16.110 --> 01:07:21.730 Und dann wird die identifiziert durch diese Startposition i dieses 01:07:21.730 --> 01:07:22.230 Suffixes. 01:07:22.870 --> 01:07:27.310 Heißt ich habe dann, der Suffix Array besteht aber aus Zahlen zwischen 01:07:27.310 --> 01:07:28.490 0 und n-1. 01:07:31.190 --> 01:07:32.970 Und die sortiere ich. 01:07:33.250 --> 01:07:38.510 Heißt ich habe zu jedem Suffix, zu jeder Nummer ist ja dieses Suffix 01:07:38.510 --> 01:07:39.010 zugeordnet. 01:07:39.410 --> 01:07:44.730 Und wenn ich die lexikografisch sortiere, etwa durch diesen Multi 01:07:44.730 --> 01:07:52.290 -QuickSort, dann kriege ich eine Permutation dieser Zahlen von 0 bis n 01:07:52.290 --> 01:07:52.890 -1. 01:07:53.690 --> 01:08:00.250 Und wenn die derart sind, dass wenn ich zwei Suffixe nehme, die 01:08:00.250 --> 01:08:04.210 richtig geordnet sind, lexikografisch, dann nennt man diese 01:08:04.210 --> 01:08:06.290 Permutation ein Suffix Array. 01:08:10.830 --> 01:08:16.150 Das Schöne ist dann, wenn man diese alle Suffixe geordnet hat, die 01:08:16.150 --> 01:08:19.490 speichern wir sich ja erstmal nicht explizit ab, sonst wenn ich die 01:08:19.490 --> 01:08:25.050 explizit abspeichere, dann hätte ich ja einen Platzbedarf von der 01:08:25.050 --> 01:08:26.010 Summe aller Suffixe. 01:08:26.010 --> 01:08:34.650 Und weil die Länge 1, 2 bis n haben, hätte ich dann ja dann diese 01:08:34.650 --> 01:08:40.990 Gauss -Summe, die auf O von n mal n-1 halbe, also O von n, rausläuft. 01:08:41.510 --> 01:08:47.270 Darum speichern wir sich nur diesen Pointer auf dieses Suffix im Text. 01:08:47.990 --> 01:08:50.870 Das heißt im Endeffekt speichern wir nur diese Permutation ab an 01:08:50.870 --> 01:08:53.190 Zahlen plus den Originaltext. 01:08:53.890 --> 01:08:56.930 Und das definiert mir dann meinen Index. 01:09:02.910 --> 01:09:09.930 Das Alphabet, über das man das macht, kann bis zu n groß sein. 01:09:12.610 --> 01:09:16.810 Anwendungen sind eine Volltextsuche, dann die Boris-Wieder 01:09:16.810 --> 01:09:19.350 -Transformierte, das wollen wir auch noch kennenlernen an der 01:09:19.350 --> 01:09:24.370 Vorlesung, das wird zur Textkompression eingesetzt, z.B. 01:09:24.750 --> 01:09:35.610 in den Bzip2-Kompressor, dann genau, ist das dieses Suffix-Array, weil 01:09:35.610 --> 01:09:38.250 ich kann ja einfach diese Binärsuche machen, wenn ich ein Pattern 01:09:38.250 --> 01:09:44.210 habe, ich match quasi den ersten Buchstaben meines Patterns mit der 01:09:44.210 --> 01:09:48.470 Menge aller Suffixe in dem Suffix-Array und weil die lexographisch 01:09:48.470 --> 01:09:51.970 geordnet sind, kann ich da Binärsuche machen nach dem ersten 01:09:51.970 --> 01:09:56.630 Buchstaben und dann habe ich ein kleineres Intervall und da kann ich 01:09:56.630 --> 01:09:59.230 dann nach dem zweiten Buchstaben dieses Pattern suchen und so weiter, 01:09:59.370 --> 01:10:02.810 kriege ich immer noch ein kleineres Intervall und darum ist das quasi 01:10:02.810 --> 01:10:08.830 ganz einfach und hat eine Kompensität von m mal Logarithmus von der 01:10:08.830 --> 01:10:11.710 Größe von dem Suffix-Array, was n ist. 01:10:13.810 --> 01:10:19.470 Und genau, mit Suffix-Bäumen kann ich das in O von M machen, weil ein 01:10:19.470 --> 01:10:25.090 Suffix -Baum wäre quasi ein Präfix-Baum, in dem man alle Suffixe 01:10:25.090 --> 01:10:25.750 eingefügt hat. 01:10:28.250 --> 01:10:31.990 Und andere Anwendungen sind in der Bioinformatik, es gibt viele 01:10:31.990 --> 01:10:38.290 Anwendungen für so Suffix-Bäume oder so Suffix-Arrays, zum Beispiel 01:10:38.290 --> 01:10:46.390 will ich den längsten Substring, der zweimal im String vorkommt, also 01:10:46.390 --> 01:10:50.290 längste Zeichenkette, die zweimal als Subzeichenkette, die zweimal 01:10:50.290 --> 01:10:50.810 vorkommt. 01:10:53.450 --> 01:10:58.490 Und genau, das war eigentlich auch eines dieser Kernprobleme, das auch 01:10:58.490 --> 01:11:02.830 Donald Knuth, also von Knuth mal Spread, der hat behauptet, dass man 01:11:02.830 --> 01:11:09.510 dieses Problem nicht optimal lösen kann, also in O von N. 01:11:11.350 --> 01:11:19.750 Und wenn man hier so ein Suffix-Array hat und man will den längsten 01:11:19.750 --> 01:11:27.150 Substring finden, der zweimal vorkommt, dann ist es eigentlich 01:11:27.150 --> 01:11:29.550 ziemlich einfach, das zu lösen, das Problem. 01:11:33.710 --> 01:11:37.910 Vielleicht Vorschläge, wenn ich diese Struktur so vor mir habe und ich 01:11:37.910 --> 01:11:42.290 will den Substring, den längsten Substring, der zweimal vorkommt, 01:11:42.890 --> 01:11:47.270 bestimmen, wie man das machen könnte. 01:11:48.950 --> 01:11:57.490 Also ein allgemeines Substring ist ja quasi definiert durch das, also 01:11:57.490 --> 01:12:01.690 ich kann sagen, wenn ich ein Präfix habe, eine Suffixes, dann ist es 01:12:01.690 --> 01:12:02.670 ein allgemeines Substring. 01:12:05.130 --> 01:12:08.830 Das heißt, wenn ich jetzt hier ein Präfix von Suffixen nehme, dann 01:12:08.830 --> 01:12:09.810 sind die auch ein Substring. 01:12:12.390 --> 01:12:14.530 Zum Beispiel ein Substring, der vorkommt ist A. 01:12:17.270 --> 01:12:20.850 Ist das der längste Substring, der zweimal in dem Text vorkommt? 01:12:25.330 --> 01:12:30.410 Nein, sicherlich nicht, weil AN kommt ja auch vor und AN kommt auch 01:12:30.410 --> 01:12:37.990 zweimal vor und steht sogar auch untereinander in diesem Suffix-Array. 01:12:39.430 --> 01:12:45.210 Weil Dinge, die gleich sind, mit gleichem Präfix statt sind, die 01:12:45.210 --> 01:12:53.770 stehen in dem Suffix-Array natürlich, sind benachbart, weil die ja das 01:12:53.770 --> 01:12:58.590 gleiche Präfix teilen und darum sind sie in dem String-Sort, den wir 01:12:58.590 --> 01:13:02.210 gemacht haben, sind die im gleichen Bereich. 01:13:03.450 --> 01:13:07.690 Das heißt, was man machen kann, ist, man kann hier durchgehen und 01:13:07.690 --> 01:13:08.210 dann... 01:13:09.370 --> 01:13:12.950 Naja, stimmt, Sie können das noch nicht, weil dann brauche ich nur die 01:13:12.950 --> 01:13:16.930 Information, was das längste gemeinsame Präfix ist zwischen zwei so 01:13:16.930 --> 01:13:17.910 benachbarten Strings. 01:13:19.250 --> 01:13:21.830 Aber das wollen wir auch noch vorlesen und kennenlernen, wie man diese 01:13:21.830 --> 01:13:23.790 Information auch in Linearzeit noch berechnen kann. 01:13:24.290 --> 01:13:28.070 Aber wenn man das hat, dann kann man hier einfach runtergehen und dann 01:13:28.070 --> 01:13:34.370 quasi das Paar an Suffixen nehmen, die das längste gemeinsame Präfix 01:13:34.370 --> 01:13:34.990 haben. 01:13:35.970 --> 01:13:38.190 Dann ist das Problem trivial gelöst. 01:13:41.770 --> 01:13:45.630 Gibt es noch andere Probleme, wie zum Beispiel Palindrome finden. 01:13:45.790 --> 01:13:51.870 Palindrome ist ein String, der von vorne und rückwärts genau das 01:13:51.870 --> 01:13:52.590 gleiche Wort ergibt. 01:13:52.590 --> 01:13:57.350 Otto oder andere Sachen. 01:13:59.230 --> 01:13:59.590 Oder Anna. 01:14:01.790 --> 01:14:05.490 Und genau, das Problem zum Beispiel, den längsten palindromischen 01:14:05.490 --> 01:14:06.270 Substring zu finden. 01:14:07.890 --> 01:14:12.330 Oder eben Wiederholungen, die mehrfach hintereinander vorkommen. 01:14:12.790 --> 01:14:17.370 Am Ende von so Chromosomen sind so Zelomere. 01:14:18.010 --> 01:14:19.370 Also gibt es viele Anwendungen. 01:14:22.590 --> 01:14:28.270 Genau, das heißt, diese binäre Suche, die Konstantnummer und dann 01:14:28.270 --> 01:14:32.690 genau, wenn man das mit diesem längsten gemeinsamen Präfix-Array noch 01:14:32.690 --> 01:14:36.330 kombiniert, dann kann man diese Suche verbessern und dann kann ich 01:14:36.330 --> 01:14:40.370 auch diesen Suffix Baum, der jetzt hier dran kommt, kann ich auch 01:14:40.370 --> 01:14:42.370 effizient berechnen. 01:14:42.970 --> 01:14:51.190 Wie gesagt, dieser Suffix Baum ist genau quasi ein Baum, in dem man 01:14:51.190 --> 01:14:57.630 alle Suffixe eingefügt hat und wenn zwei Suffixe einen gemeinsamen 01:14:57.630 --> 01:15:02.790 Präfix teilen, dann ist es auf einem Pfad. 01:15:05.110 --> 01:15:11.410 Und genau, das Interessante ist, dass man diesen Suffix Baum, der 01:15:11.410 --> 01:15:16.910 jetzt eher komplizierter ist, als dieser Suffix Array, weil dieser 01:15:16.910 --> 01:15:20.630 Suffix Array, den kann man eigentlich, weil jetzt diese, genau, in 01:15:20.630 --> 01:15:25.790 jedem Knoten habe ich jetzt quasi ausgehende Kanten und diese 01:15:25.790 --> 01:15:30.390 ausgehenden Kanten enthalten quasi die gemeinsamen Präfixe von Suffixe 01:15:31.770 --> 01:15:35.590 und die habe ich, in dem Suffix Baum sind die natürlich lexographisch 01:15:35.590 --> 01:15:37.470 geordnet, dass man da drin suchen kann. 01:15:37.470 --> 01:15:46.030 Also wenn ich jetzt ein Pattern finden will, dann kann ich dann, wenn 01:15:46.030 --> 01:15:51.290 ich im Wurzelknoten bin, dann spricht der Wurzelknoten quasi allen 01:15:51.290 --> 01:15:56.650 Suffixen und das gemeinsame Präfix ist der leere String, also Epsilon 01:15:57.590 --> 01:16:02.530 und wenn ich jetzt quasi ein Pattern habe, das vielleicht mit A 01:16:02.530 --> 01:16:07.070 anfängt, dann kann ich jetzt quasi Binärsuche machen über den ersten 01:16:07.070 --> 01:16:13.110 Buchstabe der ausgehenden Kanten in diesem Baum, wenn die geordnet 01:16:13.110 --> 01:16:13.410 sind. 01:16:14.050 --> 01:16:18.450 Das heißt aber auch, wenn das quasi für jeden gilt, dann sind diese 01:16:18.450 --> 01:16:25.110 Suffixe, und die Suffixe sind hier als Blätter markiert, das heißt, 01:16:26.110 --> 01:16:32.750 das linkeste Blatt ist auch das lexographisch kleinste Suffix in dem 01:16:32.750 --> 01:16:33.090 String. 01:16:34.170 --> 01:16:38.810 Und dann geht es von links nach rechts, steigen diese Suffixe dann 01:16:38.810 --> 01:16:39.110 auf. 01:16:40.550 --> 01:16:45.150 Und das ist genau eigentlich die Definition vom Suffix Array. 01:16:47.970 --> 01:16:54.750 Die Blätter sind markiert mit den Suffixen und das sind Zahlen 01:16:54.750 --> 01:17:01.850 zwischen 0 und n-1 und die sind genauso in lexographischer Reihenfolge 01:17:01.850 --> 01:17:07.310 dieser Strings, die die Suffixe, die attached sind. 01:17:11.590 --> 01:17:16.570 Das heißt, man kann diesen Suffix Array einfach in linearer Zeit aus 01:17:16.570 --> 01:17:18.330 dem Suffix Tree konstruieren. 01:17:18.650 --> 01:17:22.350 Das Interessante ist aber, dass diese Knutsche Vermutung, dass dieses 01:17:22.350 --> 01:17:29.530 Problem nicht in linearer Zeit gelöst werden kann, die hat Weiner 1973 01:17:29.530 --> 01:17:33.430 widerlegt, indem er einen Algorithmusangeber hat, der diesen Suffix 01:17:33.430 --> 01:17:34.130 Baum konstruiert. 01:17:34.130 --> 01:17:36.570 Nicht diesen einfachen Suffix Array, sondern diesen Suffix Baum. 01:17:40.690 --> 01:17:43.150 Diese Konstruktionsalgorithmen, da kam dann später noch ein anderer 01:17:43.150 --> 01:17:47.510 raus, von McRae 1976 und dann in den 90er Jahre von noch mal einem 01:17:47.510 --> 01:17:49.130 Wissenschaftler aus Finnland, von Uconnen. 01:17:50.950 --> 01:17:55.490 Und die sind aber alle hochkompliziert, das heißt, ich brauche hier 01:17:55.490 --> 01:17:58.590 vielleicht 3 oder 4 Wochen, um die zu erklären. 01:17:59.710 --> 01:18:03.830 Und das Schöne ist, dass eigentlich diese Suffix Array Konstruktion, 01:18:04.590 --> 01:18:11.510 die ist einfach, weil es ist ein Dividend Conquer Algorithmus, der 01:18:11.510 --> 01:18:18.830 sehr elegant ist und mit dem, wenn ich den habe und den Suffix Array 01:18:18.830 --> 01:18:22.070 konstruiere, kann ich dann aus dem Suffix Array und noch mal McRae, 01:18:22.490 --> 01:18:24.390 kann ich einfach den Suffix Baum wieder konstruieren. 01:18:28.710 --> 01:18:34.710 Und ein weiterer Nachteil dieses Suffix Baums ist natürlich der Platz, 01:18:35.590 --> 01:18:36.810 wenn man sich das so anschaut. 01:18:37.170 --> 01:18:43.490 Also erstens, hier habe ich ja die Kantenlabel auf dem Baum. 01:18:44.110 --> 01:18:48.530 Wenn ich die Kantenlabel addiere, dann habe ich quasi wieder alle 01:18:48.530 --> 01:18:51.810 Suffixe minus die gemeinsamen Präfixe. 01:18:52.620 --> 01:18:58.050 Aber da kann man sich auch Strings konstruieren, für die die 01:18:58.050 --> 01:19:05.670 expliziten Kantenlabel quasi auch wieder quadratisch Platz braucht, im 01:19:05.670 --> 01:19:09.130 Vergleich zu dem Text der Länge n. 01:19:10.450 --> 01:19:15.010 Das sind die Probing Sequences. 01:19:17.130 --> 01:19:20.870 Das ist nicht so wichtig, aber das heißt, man wird sich eigentlich 01:19:20.870 --> 01:19:29.790 nicht diese Labels speichern, sondern nur die Tiefe der Knoten und mit 01:19:29.790 --> 01:19:34.630 der Tiefe der Knoten und den Markierungen, also ich kann mir auch 01:19:34.630 --> 01:19:42.210 einen Pointer speichern auf ein Label im Subbaum, auf ein Suffix im 01:19:42.210 --> 01:19:50.350 Subbaum und dann kann ich durch Addition von dieser Tiefe plus dieses 01:19:50.350 --> 01:19:56.550 Suffix, kann ich ein Kantenlabel quasi extrahieren aus dem Text. 01:19:58.370 --> 01:20:07.370 Und weil ich diese kompaktierte Trie, Wer weiß was ein kompaktierter 01:20:07.370 --> 01:20:09.790 Trie ist, im Vergleich zum normalen Trie? 01:20:10.350 --> 01:20:10.770 Alle? 01:20:14.870 --> 01:20:20.070 Der Unterschied ist, beim normalen Trie kann ich Knoten haben, die 01:20:20.070 --> 01:20:22.170 Ausgangsgrad und Eingangsgrad 1 haben. 01:20:22.980 --> 01:20:31.490 Dann heißt, wenn ich statt NA eine Kante mit Label NA hätte ich einen 01:20:31.490 --> 01:20:36.410 Knoten N und dann hätte ich nochmal einen Knoten mit Kante A. 01:20:36.930 --> 01:20:40.390 Also ich hätte zwei Kanten und einen Knoten anstatt einer Kante. 01:20:42.850 --> 01:20:48.790 Und im kompaktifierten Trie, da lösche ich alle diese Knoten. 01:20:48.790 --> 01:20:58.190 Das heißt, jeder Knoten ist quasi verzweigend, also hat mindestens 01:20:58.190 --> 01:20:58.830 zwei Kinder. 01:20:59.890 --> 01:21:03.530 Und wenn ich mindestens zwei Kinder habe von jedem inneren Knoten und 01:21:03.530 --> 01:21:09.370 nur Blätter, haben quasi keine Kinder natürlich, und ich habe N 01:21:09.370 --> 01:21:17.470 Blätter, dann habe ich höchstens N minus 1 innere Knoten. 01:21:17.470 --> 01:21:20.930 Das kann man sich klar machen, indem man sagt, der Basisfall ist, ich 01:21:20.930 --> 01:21:22.530 habe einen Baum, der hat zwei Kinder. 01:21:23.770 --> 01:21:24.730 Na ja, was kann ich jetzt machen? 01:21:24.830 --> 01:21:30.650 Ich kann jetzt, wenn ich ein Blatt anfüge, dann kann ich das, also 01:21:30.650 --> 01:21:35.170 wenn ich ein Blatt anfüge, dann kann ich das zur Wurzel hinzufügen. 01:21:37.230 --> 01:21:40.950 Dann habe ich quasi, ist das sogar noch besser, dann habe ich N minus 01:21:40.950 --> 01:21:42.230 2 innere Knoten. 01:21:42.230 --> 01:21:45.950 Wenn ich das Blatt irgendwo in ein anderes Blatt hinfüge, dann ändert 01:21:45.950 --> 01:21:48.830 sich nichts, weil ich würde es wieder kompaktifizieren und sonst 01:21:48.830 --> 01:21:50.650 müsste ich quasi zwei Blätter hinfüge und so weiter. 01:21:52.310 --> 01:21:55.210 Dann bleibt es immer kleiner als N minus 1. 01:21:57.110 --> 01:22:03.410 Das heißt, diese Anzahl Knoten da drin plus Blattknoten sind dann 01:22:03.410 --> 01:22:04.370 höchstens 2 mal N. 01:22:06.490 --> 01:22:11.030 Und das heißt, ich habe dann eben, wenn ich das klassisch mache mit 01:22:11.030 --> 01:22:15.190 Pointer, diesen Baum, dann habe ich 2 mal N Pointer. 01:22:17.090 --> 01:22:22.230 Wenn ich jetzt ein großes Text habe und dieses Alphabet, auf das wir 01:22:22.230 --> 01:22:27.170 dann auch bei der Konstruktion zurückkommen, normalerweise hat man ein 01:22:27.170 --> 01:22:31.230 Alphabet, das eigentlich klein ist, mit zum Beispiel irgendwie Bytes 01:22:31.230 --> 01:22:32.910 oder DNA-Symbole. 01:22:34.550 --> 01:22:40.790 Und dieses Alphabet, das bezeichnen wir eigentlich mit Sigma oder 01:22:40.790 --> 01:22:42.050 Klein -Sigma ist die Größe. 01:22:43.030 --> 01:22:46.690 Dann habe ich Nlog-Sigma-Bits für den Originaltext. 01:22:47.830 --> 01:22:52.970 Wenn ich es irgendwie in ein Genom nehme, dann hat es 3 Gigabasenpaare 01:22:52.970 --> 01:22:58.150 und weil jedes Basenpaar nur 2 Bits braucht, weil ich ACGT habe, habe 01:22:58.150 --> 01:22:59.470 ich 750 Megabyte. 01:23:00.250 --> 01:23:04.730 Wenn ich es aber zu Pointer abspeichere, dann hat jeder Pointer 01:23:04.730 --> 01:23:07.810 irgendwie 4 Byte oder auch 8 Byte. 01:23:09.270 --> 01:23:16.370 Das heißt, es ist ein Vielfaches von diesen 750 Megabyte, weil es sind 01:23:16.370 --> 01:23:17.090 ja nur 2 Bits. 01:23:17.090 --> 01:23:22.190 Und wenn ich dann 32 Bit oder 64 Bit nehme, dann komme ich am Ende auf 01:23:22.190 --> 01:23:24.070 einen Index, der hat irgendwie 20 Gigabyte. 01:23:26.170 --> 01:23:28.350 Und das sind quasi noch die besten Implementierungen. 01:23:29.230 --> 01:23:33.230 Und darum nimmt man heute nicht mehr solche Suffix-Trees, weil in der 01:23:33.230 --> 01:23:34.630 Praxis die einfach zu groß sind. 01:23:35.230 --> 01:23:38.170 Bei so einem Suffix-Array, der ist schon besser, weil der braucht 01:23:38.170 --> 01:23:41.110 quasi nur 4 Byte pro Basenpaar. 01:23:41.110 --> 01:23:48.250 Der hat dann vielleicht nur 12 Gigabyte plus den Text, also 13 01:23:48.250 --> 01:23:48.830 Gigabyte. 01:23:50.730 --> 01:23:53.510 Aber wir machen eine Vorlesung, also was ich mache, ich mache so 01:23:53.510 --> 01:23:59.090 Indizes, da ist die Größe des komprimierten Textes. 01:23:59.250 --> 01:24:03.070 Also ich würde quasi sowas kriegen wie einen Index, der hat quasi 750 01:24:03.070 --> 01:24:08.470 Megabyte und kann dann trotzdem in der optimalen Zeit suchen. 01:24:09.270 --> 01:24:16.230 Okay, das heißt, jetzt ist der Beginn von diesem Algorithmus, der 01:24:16.230 --> 01:24:18.330 diesen Suffix-Array konstruiert. 01:24:20.030 --> 01:24:23.710 Den kriege ich aber heute nicht mehr hin in 3 Minuten oder 4. 01:24:25.430 --> 01:24:30.930 Von daher würde ich da schon... genau, vielleicht sind es noch Fragen 01:24:30.930 --> 01:24:32.750 zur Vorlesung, dann können wir die noch beantworten. 01:24:35.550 --> 01:24:37.910 Sonst sehen wir uns nächste Woche wieder.