Reverse Levenshtein Entfernung

Question

In Levenshtein Abstand stellen Sie die Frage, was ist ihre Levenshtein-Abstand, die diese beiden Strings gegeben. Wie würdest du eine Saite und eine Levenshtein-Distanz nehmen und alle Saiten innerhalb dieser Levenshtein-Distanz erzeugen? (Es würde auch einen Zeichensatz aufnehmen). Also, wenn ich eine Zeichenfolge x und eine Entfernung d übergeben. dann würde es mir alle Saiten innerhalb dieser Bearbeitungsdistanz geben, einschließlich d-1 und d-2 .... d-n; (n < d).

Expected Funktionalität:

>>> getWithinDistance('apple',2,{'a','b',' '}) 
['applea','appleb','appel','app le'...] 

Bitte beachten Sie, dass das Programm in der Lage ist app le zu produzieren als Raum im Zeichensatz enthalten ist.

Answer 1

Es gibt eine Datenstruktur, die dies nennt die Levenshtein automaton. Sie konstruieren es aus einer Reihe von Zeichenfolgen (die möglicherweise nur ein Element haben) und einem festen Abstand k, und dann können Sie es für alle Zeichenfolgen mit Abstand höchstens von alle Zeichenfolgen, die es speichert, abfragen. Eine Python-Implementierung wird diskutiert here.

Alternativ können Sie eine Tiefenlimitierte Suche mit Backtracking für solche Strings durchführen.