0

我正在为带有建议的拼写检查器构建一棵树。每个节点都包含一个键（一个字母）和一个值（沿着该路径的字母数组）。

所以假设我的大特里有以下子特里：

                W
               / \
              a   e
              |   |
              k   k
              |   |
   is word--> e   e
                  |
                 ...

这只是子树的子路径。W 是一个节点，a 和 e 是其值数组中的两个节点，等等......

在每个节点，我检查单词中的下一个字母是否是节点的值。我现在正在尝试支持错误输入的元音。所以 'weke' 将产生 'wake' 作为建议。这是我searchWord在尝试中的功能：

def searchWord(self, word, path=""):

    if len(word) > 0:
        key = word[0]
        word = word[1:]

        if self.values.has_key(key):
            path = path + key
            nextNode = self.values[key]
            return nextNode.searchWord(word, path)

        else:
             # check here if key is a vowel. If it is, check for other vowel substitutes

    else:
        if self.isWord:
            return path # this is the word found
        else:
            return None

给定“weke”，最后当单词长度为零且路径为“weke”时，我的代码将命中第二个大 else 块。weke未标记为单词，因此它将返回 None。这将返回searchWord无。

为了避免这种情况，在每次堆栈展开或递归回溯时，我需要检查一个字母是否是元音，如果是，请再次检查。

我将if self.values.has_key(key)循环更改为以下内容：

 if self.values.has_key(key):
    path = path + key
    nextNode = self.values[key]
    ret = nextNode.searchWord(word, path)

    if ret == None:
        # check if key == vowel and replace path
        # return nextNode.searchWord(...

    return ret

我在这里做错了什么？当回溯以实现我想要做的事情时，我能做什么？

4

1 回答 1

1

递归搜索。跟踪当前索引和原始单词。

letters = [chr(i) for i in range(97,97+26)]
print letters
max = 300

def searchWord(orig,word, curindex,counter):
    if counter>max: return

    if counter==0:
        s = letters[0] + word[1:]            
        searchWord(orig,s,0,counter+1)
    else:
        c = word[curindex]

        print 'checking ',word,curindex
        s = word
        i = letters.index(c)

        if i==len(letters)-1 and curindex==len(orig)-1:
            print 'done'
            return

        if i==len(letters)-1: 
            print 'end of letters reached'
            print 'curindex',curindex
            s = list(word)
            s[curindex] = list(orig)[curindex]
            s[curindex+1] = letters[0]
            s[1] = letters[0]
            s = ''.join(s)
            searchWord(orig,s,curindex+1,counter+1)

        else:
            s = list(word)
            try:
                s[curindex] = letters[i+1]
            except:
                print '?? ',s,curindex,letters[i]

            s = ''.join(s)
            searchWord(orig,s ,curindex,counter+1)


searchWord("weke","weke",0,0)

我不确定递归和树搜索是否是正确的方法。如果你的记忆中有一个单词表，loopkup 会非常快。只有当搜索空间很大时，才不得不拆分问题。所以更好的算法可能只是这样的：

corpus_words = {'wake',....} # this is in memory
allowed = word in corpus_words # perhaps improve this with adjusted binary search

一个典型的语料库有 5-30 百万字，不到 1 GB。查找将非常快，因为您可以进行二进制搜索，在平均情况下为 O(log n)。搜索单词子集的问题是您不知道输入的单词不是单词。但是，您可以构建允许的元音。某些字母组合不会出现在语料库中。所以在计算方面，这个问题现在很容易。当然，通过将核心语料库保存在内存中，将其余部分保存在磁盘中，可以快速改进简单的查找。在 android 上滑动效果很好。它使用个性化的语料库和一些机器学习。

为了解决这个特殊问题，我会做的是计算“weke”这个词的邻居并检查它们是否在语料库中，即

word = 'weke'             
suggestions = list()                                                      
letters = [chr(x) for x in range(97,97+26)]                                     
for i in range(len(word)):                                                      
    for a in letters: # or do this in a smarter way to iterate                                                           
        newword = word                                                          
        newword[i] = a                                                          
        if newword in corpus: suggestions.append(newword)

然后为了改进它，检查小节是否在音节语料库中。在这方面已经做了很多工作，因此您可能可以在互联网上找到标准解决方案，例如： http: //nltk.org/

于 2012-11-07T10:11:08.417 回答