Python利用字典樹實現獵詞遊戲

獵詞（word hunt）是一類很常見的遊戲，給你一張字母組成的表，然後讓你在這些字母中儘可能多的去尋找單詞。這類遊戲有不同的變體，一類是你可以多次重複使用這些字母（這類遊戲叫做獵詞），或者你只能使用一次每個字母（這類遊戲叫做字母重組）。你組出來的單詞越長就得分越高，使用了所有字母就可以獲得最高分。

這類遊戲對計算機而言是很「容易」去完成的，而且要強調一個相當有用的資料結構叫做 “Trie”。

解決策略

讓我們先拿出一個單詞「MAINE」。

首先要做的決定我們要如何處理這個問題。如果問題是字母重組，那麼我們可以嘗試所有可能的字母組合，然後看看它們是否是單詞。這對字母重組是一個還不錯的解決方案，但是對獵詞而言就不能給我們多少幫助了，因為字母可以被重用。所以當你可能發現了單詞 ”name” 時，你將再不會發現單詞 “nine”。顯然我們不能嘗試窮盡這些字母所有可能的組合，因為我們不知道一個單詞可能被重複多少次。因為這個原因，我們退步為搜尋一個詞典，去看這個詞是否可以只由我們擁有的字母組成。當有一個很大的詞典時，這可能耗費大量的時間，並且你每次換了一個詞時都必須重複這一步。

作為替代，我們需要一個搜尋詞典的方法，可以快速告訴我們某個單詞是否在詞典中。這就是預測性文字結構 Trie 字典樹的用武之地。

什麼是 Trie？

Trie 是一個樹資料結構 — 作為原本樹節點儲存一個與 key 相關聯的值的代替 — 這個節點現在儲存 key 本身。節點中的值可用於根據遍歷次數來為某些葉子節點或概率值分配順序。

維基百科中一個 Trie 的例子

上面這個 Trie 的例子由 “A”，“to”，“tea”，“ted”，“ten”，“i”，“in” 和 “inn” 生成。一旦一個像這樣的 Trie 字典樹結構被生成，去判斷任何一個單詞是否在這個 Trie 字典樹中就是 O(n) 複雜度的。如果我在搜尋 “ted”，我會消耗 O(1) 去尋找 “t”，然後從 “t” 節點再消耗 O(1) 去尋找 “e”，並且再從 “te” 節點消耗 O(1) 去到 “d”。

面對問題“這一堆字母在不在這個詞典中？”，這就是一個「非常」快速的解答方案。我們首先要做的就是構建詞典。

在 Python 中，這個步驟很簡單。每個節點的樣子都應該是一個詞典。所以我們需要從一個空詞典開始，然後對詞典中的每一個單詞，逐字母的檢查下一個字母是否在我們的 Trie 字典樹結構中，如果不在就添進去。現在，這聽起來相當耗費時間，在某些方面也的確如此，但是它只需要完成一次。當 Trie 被建好後，你可以直接使用它而無需任何其它開銷。

建立 Trie 字典樹

我們需要從一個裝滿所有可能單詞的列表開始（網上有很多這類資源），然後我們的詞典載入函數可能長下面這樣：

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

我們需要一個函數來給 Trie 中新增單詞。我們通過快速瀏覽 Trie 來檢查每一個字母，判斷我們是否需要新增一個新的 key。因為我們通過 key 來檢索 python 中的字典，所以無需在每個節點儲存一個 value。這是一個有自己的 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)

這裡有一個簡單的想法。我們接收的引數是當前所在位置的 Trie 字典樹（注意在這個例子中，Trie 中的所有節點也是一個 Trie），這個單詞，以及我們所檢視的字母在單詞中的索引。

如果索引超過了單詞的長度，我們就停止！如果沒有超過，我們需要檢查是否這個字母已經在這個 Trie 中。如果這個字母不在這個 Trie 的下一層中，那麼我們新增一個新的字典在這一層，當前這個字母就是字典的 key。然後，我們遞迴的呼叫這個函數，並且傳入我們當前字母對應的詞典（也就是 Trie），這個單詞，以及下一個索引位置。

使用這兩個函數，我們就構建了上面展示的 Trie 字典樹。但是有一個問題擺在我們面前。我們如何知道我們找到的是一個「單詞」，而不是一個真正的單詞的前一「部分」呢？例如，在上面這個 Trie 的例子中，我們希望 “in” 可以像 “inn” 一樣返回是一個單詞，但是並不希望將 “te” 作為一個詞典中的單詞來返回。

為了完成這一點，當我們完成一個單詞時，「必須」在這個節點中儲存一個值。來回頭重新審視一下我們的 addWordToTrie 函數，如果這個節點表示一個完整的單詞，就將 “leaf” 這個 key 設定為 “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)

現在，無論何時我們完成一個單詞，都要設定當前這個詞典節點的 “leaf” 值為 True，或者我們新增一個新的節點，它的 “leaf” 值為 “False”。

當我們載入這個函數初始化時，應該是同樣的設定 {‘leaf’：False}，所以我們就無需再拿一個空的字串來作為有效詞的返回。

就是這樣！我們已經建立了我們的 Trie 結構，接下來啥時候使用它了。

單詞測試

找一個辦法來進行嘗試：從一個空的列表開始。對我們單詞中的每個字母，檢查我們的 Trie 字典樹，看它是否在其中。如果在，就拿到這個詞典子樹再重新開始（這樣我們可以檢查重複的字母）。保持這樣進行下去，直到我們找到一個 leaf 標誌位為 true 的節點，或者我們在下一層的詞典子樹中找不到單詞中的任何字母。如果我們發現了一個標記為 leaf 的節點，就把這個單詞添到列表中。如果我們沒有找到下一個詞典子樹，就返回並執行下一個字母。

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

這裡注意一下，我們正在構建一個新單詞傳遞到列表中，但是我們也會遞迴的去尋找新的單詞，用來擴充套件我們的列表。

有的讀者可能已經發現了接下來的問題。如果字母重複怎麼辦呢？例如我們的單詞是 “「TEEN」”，並且我們現在在 “TE” 節點上，我們已經在子樹上檢查了 “t“，這很好，然後我們在子樹上檢查 ”e“ 並行現 ”tee“ 是一個單詞。我們將 ”tee“ 新增到列表中。但是單詞的下一個字母又是 ”e“，所以我們再次找到了 ”tee“。有一些方法去解決這個問題，但是最簡單的方法之一就是用集合代替列表。

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
 

現在無論我們把同一個單詞找到多少次，我們都可以保證列表中的唯一性。我們也可以將輸入單詞中的字母去重，進而節約處理時間。

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

def main():
    print('Loading dictionary...')
    wordTrie = load()
    print('Donen')
 
    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.")

因為我們不是單詞重組，所以我們找到了「太」多單詞。使用上面提到的例子「MAINE」和一個我找到的詞典 — 大約有 370000 個單詞 — 這個程度發現了 208 個單詞。這也是為什麼我新增了一個最短單詞長度的原因。限制單詞長度至少為七，我們可以得到如下結果：

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.

載入詞典消耗了大約半秒，後面的查詢單詞基本上感受不到明顯的時間消耗。

為了一個單詞去每次都重新建樹是很低效的，所以最好可以重用它，要麼是儲存整個資料結構，要麼嘗試一次迴圈的查詢多個單詞。

總結

但願這篇文章可以為你提供一個 Trie 的基本介紹，便於你去解決一些單詞問題。當你想要一些自動補充完成的任務時，Trie 是一個很好用的資料結構。簡訊，搜尋甚至是指引方向，都可以使用系統中的資料構建 Trie 來幫助預測使用者下一步想要輸入什麼。正如我們所看到的，它也是在一個搜尋大量的現有路徑時很好的結構，在這個例子中，這個路徑就是有效的單詞。

以上就是Python利用字典樹實現獵詞遊戲的詳細內容，更多關於Python字典樹的資料請關注it145.com其它相關文章！