反向Levenshtein距离

Question

在levenshtein距离中,你问这个问题,给定这两个字符串,他们的levenshtein距离是多少.你将如何获得一个字符串和levenshtein距离并在levenshtein距离内生成所有字符串.(它也会采用字符集).所以,如果我传入一个字符串x和一个距离d.然后它会给我编辑距离内的所有字符串,包括d-1和d-2 .... dn; (n <d).

预期功能:

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

请注意,该程序能够生成app le字符集中包含的空格.

Answer 1

有一种称为Levenshtein自动机的数据结构.您可以从一组字符串(可能只有一个成员)和固定距离k构造它,然后您可以查询它存储的任何字符串中距离最多为k的所有字符串.这里讨论Python实现.

或者,您可以对这些字符串进行回溯深度限制搜索.