怎么用Python完成獵詞游戲

創(chuàng)建 Trie 字典樹

我們需要從一個(gè)裝滿所有可能單詞的列表開始（網(wǎng)上有很多這類資源），然后我們的詞典加載函數(shù)可能長下面這樣：

def load():
    with open('words.txt') as wordFile:
        wordList = wordFile.read().split()
 
    trie = {}
    for word in wordList:
        addWordToTrie(trie, word)
   
    return trie

我們需要一個(gè)函數(shù)來給 Trie 中添加單詞。我們通過快速瀏覽 Trie 來檢查每一個(gè)字母，判斷我們是否需要添加一個(gè)新的 key。因?yàn)槲覀兺ㄟ^ key 來檢索 python 中的字典，所以無需在每個(gè)節(jié)點(diǎn)儲(chǔ)存一個(gè) value。這是一個(gè)有自己的 key 值的新詞典。

def addWordToTrie(trie, word, idx = 0):
    if idx >= len(word):
        return       
    if word[idx] not in d:
        d[word[idx]] = {}
    addWordToTrie(d[word[idx]], word, idx+1)

這里有一個(gè)簡單的想法。我們接收的參數(shù)是當(dāng)前所在位置的 Trie 字典樹（注意在這個(gè)例子中，Trie 中的所有節(jié)點(diǎn)也是一個(gè) Trie），這個(gè)單詞，以及我們所查看的字母在單詞中的索引。

如果索引超過了單詞的長度，我們就停止！如果沒有超過，我們需要檢查是否這個(gè)字母已經(jīng)在這個(gè) Trie 中。如果這個(gè)字母不在這個(gè) Trie 的下一層中，那么我們添加一個(gè)新的字典在這一層，當(dāng)前這個(gè)字母就是字典的 key。然后，我們遞歸的調(diào)用這個(gè)函數(shù)，并且傳入我們當(dāng)前字母對(duì)應(yīng)的詞典（也就是 Trie），這個(gè)單詞，以及下一個(gè)索引位置。

使用這兩個(gè)函數(shù)，我們就構(gòu)建了上面展示的 Trie 字典樹。但是有一個(gè)問題擺在我們面前。我們?nèi)绾沃牢覀冋业降氖且粋€(gè)「單詞」，而不是一個(gè)真正的單詞的前一「部分」呢？例如，在上面這個(gè) Trie 的例子中，我們希望 “in” 可以像 “inn” 一樣返回是一個(gè)單詞，但是并不希望將 “te” 作為一個(gè)詞典中的單詞來返回。

為了完成這一點(diǎn)，當(dāng)我們完成一個(gè)單詞時(shí)，「必須」在這個(gè)節(jié)點(diǎn)中儲(chǔ)存一個(gè)值。來回頭重新審視一下我們的 addWordToTrie 函數(shù)，如果這個(gè)節(jié)點(diǎn)表示一個(gè)完整的單詞，就將 “l(fā)eaf” 這個(gè) key 設(shè)置為 “True”。

def addWordToTrie(d, word, idx):
    if idx >= len(word):
        d['leaf']=True
        return
    if word[idx] not in d:
        d[word[idx]] = {'leaf':False}
    addWordToTrie(d[word[idx]], word, idx+1)

現(xiàn)在，無論何時(shí)我們完成一個(gè)單詞，都要設(shè)置當(dāng)前這個(gè)詞典節(jié)點(diǎn)的 “l(fā)eaf” 值為 True，或者我們添加一個(gè)新的節(jié)點(diǎn)，它的 “l(fā)eaf” 值為 “False”。

當(dāng)我們加載這個(gè)函數(shù)初始化時(shí)，應(yīng)該是同樣的設(shè)置 {‘leaf’：False}，所以我們就無需再拿一個(gè)空的字符串來作為有效詞的返回。

就是這樣！我們已經(jīng)創(chuàng)建了我們的 Trie 結(jié)構(gòu)，接下來啥時(shí)候使用它了。

單詞測試

找一個(gè)辦法來進(jìn)行嘗試：從一個(gè)空的列表開始。對(duì)我們單詞中的每個(gè)字母，檢查我們的 Trie 字典樹，看它是否在其中。如果在，就拿到這個(gè)詞典子樹再重新開始（這樣我們可以檢查重復(fù)的字母）。保持這樣進(jìn)行下去，直到我們找到一個(gè) leaf 標(biāo)志位為 true 的節(jié)點(diǎn)，或者我們在下一層的詞典子樹中找不到單詞中的任何字母。如果我們發(fā)現(xiàn)了一個(gè)標(biāo)記為 leaf 的節(jié)點(diǎn)，就把這個(gè)單詞添到列表中。如果我們沒有找到下一個(gè)詞典子樹，就返回并執(zhí)行下一個(gè)字母。

def findWords(trie, word, currentWord):
    myWords = [];
    for letter in word:
        if letter in trie:
            newWord = currentWord + letter
            if (trie[letter]['leaf']):
                myWords.append(newWord)
            myWords.extend(findWords(trie[letter], word, newWord))
    return myWords

這里注意一下，我們正在構(gòu)建一個(gè)新單詞傳遞到列表中，但是我們也會(huì)遞歸的去尋找新的單詞，用來擴(kuò)展我們的列表。

有的讀者可能已經(jīng)發(fā)現(xiàn)了接下來的問題。如果字母重復(fù)怎么辦呢？例如我們的單詞是 “「TEEN」”，并且我們現(xiàn)在在 “TE” 節(jié)點(diǎn)上，我們已經(jīng)在子樹上檢查了 “t“，這很好，然后我們在子樹上檢查 ”e“ 并發(fā)現(xiàn) ”tee“ 是一個(gè)單詞。我們將 ”tee“ 添加到列表中。但是單詞的下一個(gè)字母又是 ”e“，所以我們再次找到了 ”tee“。有一些方法去解決這個(gè)問題，但是最簡單的方法之一就是用集合代替列表。

def findWords(trie, word, currentWord):
    myWords = set()      
    for letter in word:
        if letter in trie:
            newWord = currentWord + letter
            if trie[letter]['leaf']:
                myWords.add(newWord)
            myWords = myWords.union(findWords(trie[letter], word, newWord))
    return myWords

現(xiàn)在無論我們把同一個(gè)單詞找到多少次，我們都可以保證列表中的唯一性。我們也可以將輸入單詞中的字母去重，進(jìn)而節(jié)約處理時(shí)間。

就這樣！利用這三個(gè)函數(shù)就可以通過我們輸入的字母來找到所有可能在字典中的單詞。來讓我們把這些包到一個(gè) main 函數(shù)里面，然后給一個(gè)輸入，具體步驟我們已經(jīng)完成了。

def main():
    print('Loading dictionary...')
    wordTrie = load()
    print('Done\n')
 
    word = raw_input("What letters should we use: ")
    minLength = int(raw_input("What is the minimum word length: "))
    print("")
 
    count = 0;
    for word in sorted(findWords(wordTrie, word, "")):
        if len(word) >= minLength:
            count = count+1
            print(word)
    print(str(count) + " words found.")

因?yàn)槲覀儾皇菃卧~重組，所以我們找到了「太」多單詞。使用上面提到的例子「MAINE」和一個(gè)我找到的詞典 — 大約有 370000 個(gè)單詞 — 這個(gè)程度發(fā)現(xiàn)了 208 個(gè)單詞。這也是為什么我添加了一個(gè)最短單詞長度的原因。限制單詞長度至少為七，我們可以得到如下結(jié)果：

Loading dictionary…

Done

What letters should we use: maine

What is the minimum word length: 7

amninia

anaemia

anamnia

animine

emmenia

enamine

manienie

mannaia

meminna

miminae

minaean

11 words found.

加載詞典消耗了大約半秒，后面的查找單詞基本上感受不到明顯的時(shí)間消耗。

為了一個(gè)單詞去每次都重新建樹是很低效的，所以最好可以重用它，要么是保存整個(gè)數(shù)據(jù)結(jié)構(gòu)，要么嘗試一次循環(huán)的查找多個(gè)單詞。

總結(jié)

但愿這篇文章可以為你提供一個(gè) Trie 的基本介紹，便于你去解決一些單詞問題。當(dāng)你想要一些自動(dòng)補(bǔ)充完成的任務(wù)時(shí)，Trie 是一個(gè)很好用的數(shù)據(jù)結(jié)構(gòu)。短信，搜索甚至是指引方向，都可以使用系統(tǒng)中的數(shù)據(jù)構(gòu)建 Trie 來幫助預(yù)測用戶下一步想要輸入什么。正如我們所看到的，它也是在一個(gè)搜索大量的現(xiàn)有路徑時(shí)很好的結(jié)構(gòu)，在這個(gè)例子中，這個(gè)路徑就是有效的單詞。