2012-04-10 9 views
6

ist es möglich, Levenshtein Abstand in regulären Ausdruck Abfrage enthalten?Levenshtein Abstand in regulärem Ausdruck

Außer Vereinigung zwischen Permutationen zu machen. Wie suchen "Hallo" mit L.d. 1

.ello | h.llo | he.lo | hel.o | hell. 

das ist eine Menge dumm und nicht verwendbar für größere Anzahlen von L.d.

Antwort

3

ist es möglich, Levenshtein Abstand in regulären Ausdruck Abfrage enthalten?

Nein, nicht gesund. Das Implementieren - oder Verwenden eines vorhandenen - Levenshtein-Distanzalgorithmus ist der Weg zu gehen.

+0

ok, ich werde warten, wenn jemand anderes antwortet, sonst werde ich deine Antwort als korrekt markieren :-) – d1x

6

Sie können die Regex programmatisch generieren. Ich werde für den Leser das als eine Übung verlassen, aber für den Ausgang dieser hypothetischen Funktion (eine Eingabe von „Wort“ genannt) Sie so etwas wie diese Zeichenfolge wollen:

"^(?>word|wodr|wrod|owrd|word.|wor.d|wo.rd|w.ord|.word|wor.?|wo.?d|w.?rd|.?ord)$" 

In Englisch, zuerst Sie versuchen, entsprechen auf das Wort selbst, dann auf jede mögliche einzelne Transposition, dann auf jede mögliche einzelne Einfügung, dann auf jede mögliche einzelne Auslassung oder Ersetzung (kann gleichzeitig getan werden).

Die Länge dieser Zeichenkette ein Wort der Länge n gegeben ist linear (und insbesondere nicht exponential) mit n.

Welche sinnvoll ist, glaube ich.

Sie übergeben dies an Ihren Regex-Generator (wie in Ruby wäre es Regexp.new (str)) und bam, Sie haben einen Matcher für jedes Wort mit einem Damerau-Levenshtein Abstand von 1 von einem gegebenen Wort.

(Damerau-Levenshtein Entfernungen von 2 sind weit komplizierter.)

Hinweis Verwendung des (> Nicht-Backtracing-Konstrukts, das die Reihenfolge der einzelnen bedeutet |? ". D Ausdrücke in dieser Ausgabe Materie

ich konnte nicht einen Weg finden, um „compact“, dass die Expression

EDIT:. ich habe es zumindest in Elixir zu arbeiten, https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

ich würde dies aber nicht unbedingt empfehlen (außer Bildungs! Pu r), da es dich nur auf Entfernungen von 1 bringen wird; eine legit DL Bibliothek können Sie Entfernungen berechnen> 1. Obwohl da diese regex ist, wäre es wahrscheinlich einmal gebaut ziemlich schnell arbeitet (beachten Sie, dass Sie den „kompilierte“ regex irgendwo speichern sollten, da zur Zeit dieser Code auf jedem Vergleich rekonstruiert!)

Verwandte Themen