Eine mögliche Definition des approximate string matching Problems ist die folgende: Gegeben ist eine Musterzeichenfolge P = p 1 p 2 . . . p m {\displaystyle P=p_{1}p_{2}…p_{m}}
und einem Textstring T = t 1 t 2 … t n {\displaystyle T=t_{1}t_{2}\dots t_{n}}
einen Teilstring T j ‚ , j = t j ‚ … t j {\displaystyle T_{j‘,j}=t_{j‘}\ dots t_{j}}
in T , das von allen Teilstrings von T den kleinsten Bearbeitungsabstand zum Muster P hat.
Ein Brute-Force-Ansatz wäre, den Bearbeitungsabstand zu P für alle Teilstrings von T zu berechnen und dann den Teilstring mit dem minimalen Abstand auszuwählen. Dieser Algorithmus hätte jedoch die Laufzeit O(n3 m).
Eine bessere Lösung, die von Verkäufern vorgeschlagen wurde, beruht auf dynamischer Programmierung. Es verwendet eine alternative Formulierung des Problems: Berechnen Sie für jede Position j im Text T und jede Position i im Muster P den minimalen Bearbeitungsabstand zwischen den i ersten Zeichen des Musters, P i {\displaystyle P_{i}}
, und jedem Teilstring T j ‚ , j {\displaystyle T_{j‘,j}}
von T, das an Position j endet.
Gehen Sie für jede Position j im Text T und jede Position i im Muster P alle Teilzeichenfolgen von T durch, die an Position j enden, und bestimmen Sie, welche von ihnen den minimaledit Abstand zu den i ersten Zeichen des Musters P. Schreiben Sie diesen minimalen Abstand als E(i, j) . Nach der Berechnung von E(i, j) für alle i und j können wir leicht eine Lösung für das ursprüngliche Problem finden: Es ist die Teilzeichenfolge, für die E(m, j) minimal ist (m ist die Länge des Musters P.)
Die Berechnung von E(m, j) ist der Berechnung des Schnittabstands zwischen zwei Zeichenfolgen sehr ähnlich. Tatsächlich können wir den Levenshtein−Entfernungsberechnungsalgorithmus für E(m, j) verwenden, wobei der einzige Unterschied darin besteht, dass wir die erste Zeile mit Nullen initialisieren und den Berechnungspfad speichern müssen, dh ob wir E(i − 1,j), E(i, j − 1) oder E (i − 1, j – 1) bei der Berechnung von E (i, j).
In dem Array, das die E(x, y) -Werte enthält, wählen wir dann den Minimalwert in der letzten Zeile aus, lassen ihn E(x2, y2) sein und folgen dem Berechnungspfad rückwärts zurück zur Zeilennummer 0. Wenn das Feld, in dem wir angekommen sind, E(0, y1) war, dann T… T ist eine Teilzeichenfolge von T mit dem minimalen Bearbeitungsabstand zum Muster P.
Die Berechnung des E (x, y) -Arrays benötigt mit dem dynamischen Programmieralgorithmus O (mn) Zeit, während die Rückwärtsphase O (n + m) Zeit benötigt.
Eine weitere aktuelle Idee ist der Ähnlichkeits-Join. Wenn sich die Datenbank auf einen großen Datenumfang bezieht, kann die O (mn) -Zeit mit dem dynamischen Programmieralgorithmus nicht innerhalb einer begrenzten Zeit arbeiten. Die Idee ist also, anstatt die Ähnlichkeit aller Zeichenfolgenpaare zu berechnen, die Anzahl der Kandidatenpaare zu reduzieren. Weit verbreitete Algorithmen basieren auf Filterverifikation, Hashing, lokalitätssensitivem Hashing (LSH), Versuchen und anderen gierigen und Approximationsalgorithmen. Die meisten von ihnen sind so konzipiert, dass sie in ein Framework (z. B. Map-Reduce ) passen, um gleichzeitig zu berechnen.