如何根据len1或len+1匹配字典中的单词？Python

Question

如果我有一个单词'raqd'，我将如何使用python进行拼写检查，也就是说，在'spellcheck'中找到单词'rad'作为一个选项？我一直想做的是：

def isbettermatch(keysplit, searchword):
    i = 0
    trues = 0
    falses = 0

    lensearchwords = len(searchword)

    keysplits = copy.deepcopy(keysplit)
    searchwords = copy.deepcopy(searchword)
    #print keysplit, searchwords
    if len(keysplits)  == len(searchwords)-1:
        i = 0
        while i < len(keysplits):
            j = 0
            while j < lensearchwords:
                if keysplits[i] == searchwords[j]:
                    trues +=1
                    searchwords.pop(j)
                    lensearchwords = len(searchwords)
                elif keysplits[i] != searchwords[j]:
                    falses +=1
                j +=1
            i +=1
        if trues >= len(searchwords)-1:
            #print "-------------------------------------------------------", keysplits
            return True            

keysplit是一个类似于['s', 'p', 'o', 'i', 'l']的列表，searchword就是一个列表['r', 'a', 'q', 'd']。你知道吗

如果函数返回True，那么它将打印匹配的关键字。例如，“rad”，表示searchword“raqd”。你知道吗

我需要为searchword查找所有可能的匹配项，只需添加或删除一个字母。你知道吗

例如，“raqd”可以选择“rad”，“poted”可以是“posted”或“potted”。你知道吗

到目前为止，我一直试图用列表来比较每个单词中的字符。我的问题是：为什么我目前的策略不起作用，我该如何改进它？我不知道为什么它给了我不正确的输出：

dna   ira   fra   had   har   nra   jar   jaq   bra   era   amd   

只是我听到的单词的一个小例子

Answer 1

很久以前，我曾为一项课程作业写过一次拼写检查。它必须像你说的那样：给定一个“单词”，建议所有可能的匹配项，给一个字母添加或删除。我记得我所做的是将主词典单词列表加载到一个哈希表（具有快速O（1）访问权限的东西）中，然后为给定的单词生成所有可能的字母添加和删除组合，并检查它们是否在主单词列表中。任何匹配项都将用作建议。你知道吗

对于更复杂的拼写检查器，可以尝试使用Levenshtein距离编写BK树： http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees