Reverse Levenshtein distanza

Question

Nella distanza di levenshtein si pone la domanda, date queste due corde, qual è la loro distanza di levenshtein. Come andresti sul prendere una corda e una distanza di levenshtein e generare tutte le corde entro quella distanza di levenshtein. (Avrebbe anche preso un set di caratteri). Quindi se passo una stringa x e una distanza d. quindi mi darebbe tutte le stringhe entro quella distanza di modifica, inclusi d-1 e d-2 .... d-n; (n < d).

funzionalità prevista:

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

Si prega di notare che il programma è in grado di produrre app le come lo spazio è incluso nel set di caratteri.

Answer 1

C'è una struttura dati che chiama questo Levenshtein automaton. Lo si costruisce da un insieme di stringhe (che possono avere un solo membro) e una distanza fissa k, e quindi è possibile interrogarlo per tutte le stringhe con la distanza massima di k di qualsiasi stringa che memorizza. Un'implementazione Python è discussa here.

In alternativa, è possibile eseguire una ricerca con profondità limitata con il backtracking per tali stringhe.