Sommer Sitzung 10
| Thema | Stichworte | Material ___________________________ |
| Überblick | Thema: Ausbau Volltextsuche: Editierdistanz für unscharfe Suche | Beispiele und Literatur: Home |
| Unscharfe Suche | Volltextsuche, was bisher? – Index, Vorverarbeitung; Anknüpfung Suchindex: was passiert bei Google, wenn wir uns vertippen? – quasi Rechtschreibekorrektur: Anfrage wird korrigiert, gesucht wird nach korrigierter Version (mit Angabe der Änderung und Option nach ursprünglicher Version zu suchen); wie kann man das grundsätzlich implementieren? – z.B. bei schlechtem Ergebnis (z.B. keine, wenig) nach dem ähnlichsten Begriff zur Eingabe suchen; dafür brauchen wir? – ein Ähnlichkeitsmaß für Strings | — |
| Editierdistanz | Ein Ähnlichkeitsmaß: Editierdistanz (oder Levenshtein-Distanz): Anzahl der Operationen die nötig sind um S1 in S2 zu ändern; welche Art von Änderung denkbar? – z.B. ehe-ehre? – eine Einfügung (insert), ehre-ehe? – eine Löschung (deletion), auf-aus? – eine Änderung (replace); d.h. 3 Operationen: I,D,R | — |
| Implementierung: Grundsätzlich | — | — |
| Strategie | Grundidee wieder: Gesamtproblem zerschlagen (divide and conquer), z.B. Distanz von S1 mit Länge 0 zu S2? – Länge von S2 und umgekehrt; grundsätzliche Idee: Distanz ist Kosten für eine Operation plus Distanz des Rests (z.B. auf-aus: letztes Zeichen ändern, plus Kosten für Rest); gleiches Zeichen: 0, sonst beste Variante von I,R,D; Grundproblem: alle Kombinationen könnten zu bestem Ergebnis führen, d.h. erst I, dann zweimal R, dann D oder erst D, dann R usw. | — |
| Rekurrenz-Relation | Zum Ausdrücken von Teilen für die ganzen Kombinationen: D(i,j) für Distanz der ersten i Zeichen in S1 zu den ersten j Zeichen in S2, d.h. Gesamtproblem? – D(i,j), i = Länge S1, j= Länge S2; eindeutige Fälle: 1. D(0,j) = ? – alle j weg oder alle i dazu – d.h. j; 2. D(i,0) = ? – alle i weg oder alle j dazu – d.h. i; man sieht schon am Bsp. oben: hinzufügen in S1 ~ Löschen in S2; Daher Optionen f. D(i,j): 1. Löschen in S1: D(i – 1,j) + 1 d.h. (eh)-e- – (eh); 2. Löschen in S2: D(i, j – 1) + 1 d.h. (eh) – (eh)-e-; 3. Ersetzen o. Lassen: D(i-1, j-1) + t d.h. (eh)e – (eh)e oder (au)f – au(s) mit t = 0 wenn S1 = S2, sonst 1; von den drei Optionen die Beste, d.h. min(ins, del, rep) für jedes Paar i,j |  |
| Rekursion: Implementierung | Rekursive Methode bekommt was für Parameter? – int i, int j, Rekursive Methode aufrufen wie? – mit S1.length und S2.length, rekursive Methode s. Code: initialer Aufruf, dann Rekurrenz-Implementierung | s. Code |
| Rekursion: Laufzeit | Berechnung der Editierdistanz, die intuitive Variante: rekursive Berechnung für alle Substring-Distanzen, dabei werden die bei der Rekursion mehrfach auftretenden Kombinationen immer wieder neu (und wieder rekursiv) berechnet; Laufzeit? – 3 * 3 * 3 etc. für jeden edit; d.h. O(3^x) bei x edits (d.h. relativ zur Länge der Strings, und abhängig von der Ähnlichkeit), also exponentiell; d.h. intuitiv, aber völlig ineffizient | — |
| Implementierung: Memoisierung | — | — |
| Memoisierung: Idee | Problem der rekursiven Lösung? – i,j-Paare mehrfach auf den verschiedenen Pfaden im Baum (im Code: i,j-Paare ausgeben); Lösung? – Zwischenergebnisse merken, abfragen statt neu zu berechnen; diese Technik nennt sich Memoisierung (en. memoization) und bringt hier schon einen beträchtlichen Gewinn. Das Schöne bei der Memoisierung ist, dass die intuitiv entwickelte, rekursive Lösung konzeptuell beibehalten aber optimiert wird (im Gegensatz zur Dynamic-Programming-Lösung, die die rekursive Lösung nur simuliert, siehe unten) | — |
| Memoisierung: Implementierung | Wir haben also Plan für effizientere Implementierung; wie für Vergleich implementieren? – Interface, alternative Implementierung, Aufruf identischer Methode zweimal, mit den unterschiedlichen Implementierungen (s. Code); Eigentliche Optimierung: i,j-Kombinationen merken wie? – z.B. in Map, vor Berechnung checken, nach Berechnung speichern; was machen wir im Vergleich zur rekursiven Implementierung? – das Gleiche, nur seltener; wie Code aus rekursiver Lösung nicht verdoppeln? – Ableiten, bei Bedarf Superklasse Berechnung ausführen lassen (s. UML, Code); | s. Code |
| Memoisierung: Laufzeit | Laufzeit? – wie oben Abhängig von edits, aber jedes i,j nur einmal in Rekursion; konkret z.B. 200 ms. vs. 60000 ms.; Gut: nachvollziehbar; Laufzeit mit Map besser, aber Alternative zu i,j als String in Map? – für jedes Paar i,j einen Wert? – Tabelle mit i und j als Zeilen, Spalten | — |
| Implementierung: Dynamic Programming | — | — |
| Dynamic Programming: Implementierung | Statt rekursiv laufen und Map oder Tabelle füllen: direkt Tabelle mit Teillösungen für ‘i, j’-Paare füllen, Basis: alle Kombinationen bottom-up (von den Teilstrings ausgehend) berechnen, statt wie bei der Memoisierung top-down, von den Gesamtstrings ausgehend. Diese Technik nennt sich ‘Dynamic Programming’ (Ursprung des Begriffs: sowas wie ‘dynamisches Planen des besten Programms’, im Sinne eines Lösungsweges). Base-Condition gegeben, auf Basis davon weiter, auf Basis der I,R,D-Alternativen von oben (1. Base-Condition in erste Zeile, erste Spalte; 2. in die Ecken I,D,R, 3. in die Mitte Minimum); Implementierung s. Code (genau wie auf Papier; technisch: Matrix durchlaufen, Nachbarn checken, vgl. GOL-Hausarbeit und s. Code) |  |
| Dynamic Programming: Laufzeit | Laufzeit? – entspricht der Größe der Tabelle, d.h. S1.length + 1 * S2.length + 1; ist also O(m*n), d.h. linear | — |
| Zusammenfassung und Integration | — | — |
| Implementierung: Fazit | Alle Laufzeiten, z.B. 3, 200, 60000 ms.; beide Schritte jeweils beträchtlich, Vor- und Nachteile: intuitiv verständliche, relativ schnelle rekursive Lösung bei Memoisierung vs. relativ kryptische, aber sehr effiziente DP-Lösung; Gesamt-Klassendiagramm s. Abb., vgl. Code |  |
| Integration | Berechnung selber mit Dynamic Programming sehr performant; Einbau z.B.? – einfachste Variante: wenn keine Treffer, Anfrage mit allen Einträgen im Dictionary (Index-Keys) vergleichen; Optimierung über Heuristiken: nur die mit gleichem Anfangsbuchstaben; nur solche mit ähnlichen Bestandteilen (k-gram Index); zu Details s. Literatur (Manning et al.) | — |
| Hausaufgabe | Gewichtete Editierdistanz; Einbau in Suchindex | Sommer-Aufgabe-09 |