獵詞（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('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.")

因為我們不是單詞重組，所以我們找到了「太」多單詞。使用上面提到的例子「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 來幫助預測用戶下一步想要輸入什么。正如我們所看到的，它也是在一個搜索大量的現有路徑時很好的結構，在這個例子中，這個路徑就是有效的單詞。