0

提案付きのスペルチェッカー用のツリーを構築しています。各ノードには、キー（文字）と値（そのパスに沿った文字の配列）が含まれています。

したがって、私の大きなトライで次のサブトライを想定します。

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

これは、サブトライの単なるサブパスです。Wはノードであり、aとeはその値配列などの2つのノードです。

各ノードで、単語の次の文字がノードの値であるかどうかを確認します。今のところ、タイプミスの母音をサポートしようとしています。したがって、「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'のとき、私のコードは2番目に大きいelseブロックにヒットします。wekeは単語としてマークされていないため、Noneで返されます。searchWordこれはNoneで戻ります。

これを回避するには、スタックの巻き戻しまたは再帰のバックトラックごとに、文字が母音であるかどうかを確認し、母音である場合はもう一度確認する必要があります。

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)

ここで再帰とツリー検索が正しいアプローチであるかどうかはわかりません。記憶に単語の表がある場合、ループアップは非常に高速になります。問題を分割しなければならないのは、検索スペースが非常に大きい場合だけです。したがって、より良いアルゴリズムはおそらく次のようなものになります。

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

典型的なコーパスには 500 万から 3000 万の単語があり、これは 1 ギガバイト未満です。平均的なケースでは 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 に答える