Frage an levenshtein-distance, regex – Levenshtein Abstand in regulären Ausdruck

9

Gibt es eine Möglichkeit, wie levenshtein Abstand in regulären Ausdrucksabfragen eingeschlossen werden kann?

Mit Ausnahme der Vereinigung von Permutationen. Wie die Suche nach "Hallo" mit L.d. 1

<code>.ello | h.llo | he.lo | hel.o | hell.
</code>

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

Deine Antwort

2   die antwort
7

rde das als Übung für den Leser belassen, aber für die Ausgabe dieser hypothetischen Funktion (bei einer Eingabe von "word") möchten Sie so etwas wie diese Zeichenfolge:

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

Im Englischen wird zuerst versucht, das Wort selbst abzugleichen, dann jede mögliche einzelne Transposition, dann jede mögliche einzelne Einfügung, dann jede mögliche einzelne Auslassung oder Substitution (kann gleichzeitig erfolgen).

Die Länge dieser Zeichenkette ist bei einem Wort der Länge n linear (und insbesondere nicht exponentiell) mit n.

Welches ist vernünftig, denke ich.

Sie übergeben dies an Ihren Regex-Generator (wie in Ruby Regexp.new (str)) und bam, Sie haben einen Matcher für ein beliebiges Wort mit einem Damerau-Levenshtein-Abstand von 1 von einem bestimmten Wort.

(Damerau-Levenshtein-Abstände von 2 sind weitaus komplizierter.)

Beachten Sie die Verwendung des (?> Non-backtracing -Konstrukts, dh die Reihenfolge der einzelnen | d Ausdrücke in dieser Ausgabe.

Ich konnte mir keine Möglichkeit vorstellen, diesen Ausdruck zu "verdichten".

EDIT: Ich habe es zum Laufen gebracht, zumindest in Elixir!https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

Ich würde dies jedoch nicht unbedingt empfehlen (außer für Bildungszwecke), da Sie dadurch nur Entfernungen von 1 erreichen. Mit einer legitimen D-L-Bibliothek können Sie Entfernungen> 1 berechnen. Obwohl dies ein regulärer Ausdruck ist, würde er nach der Erstellung wahrscheinlich recht schnell funktionieren (beachten Sie, dass Sie den "kompilierten" regulären Ausdruck irgendwo speichern sollten, da dieser Code ihn derzeit bei JEDEM Vergleich rekonstruiert!).

5

wie Levenshtein-Abstand in reguläre Ausdrucksabfragen einbezogen werden kann?

Nein, nicht auf vernünftige Weise. Das Implementieren - oder Verwenden eines vorhandenen - Levenshtein-Entfernungsalgorithmus ist der richtige Weg.

ok, ich werde warten, wenn jemand anderes antwortet, sonst werde ich deine Antwort als richtig markieren :-) zdenda.online

Verwandte Fragen