python - 我应该使用什么工具或算法从给定 Damerau–Levenshtein 距离的关键字生成单词？

Question

Damerau-Levenshtein 距离如下:

"abcd", "aacd" => 1 DL distance
"abcd", "aadc" => 2 DL distance

• 关于编辑距离的更多信息:https://pypi.python.org/pypi/editdistance
• 有关 Damerau-Levenshtein 距离的更多信息: https://pypi.python.org/pypi/pyxDamerauLevenshtein

我可以在 python 中使用 pyxDamerauLevenshtein 模块来确定 2 个单词的 DL 距离。我想制作一个生成器方法，它可以在给定的 DL 距离内生成给定关键字参数的每个单词。我只处理 1 或 2 个 DL 距离。

python 中是否有任何工具可以用来生成给定 DL 距离中单词的单词？

Answer 1

看看这篇 Norvig 的文章:How to Write a Spelling Corrector .

它包含您需要的确切代码:

def edits1(word):
    "All edits that are one edit away from `word`."
    letters    = 'abcdefghijklmnopqrstuvwxyz'
    splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]
    deletes    = [L + R[1:]               for L, R in splits if R]
    transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
    replaces   = [L + c + R[1:]           for L, R in splits if R for c in letters]
    inserts    = [L + c + R               for L, R in splits for c in letters]
    return set(deletes + transposes + replaces + inserts)

def edits2(word): 
    "All edits that are two edits away from `word`."
    return (e2 for e1 in edits1(word) for e2 in edits1(e1))