用 Python 完成詞游戲：字典樹
獵詞（word hunt）是一類很常見的游戲，給你一張字母組成的表，然后讓你在這些字母中盡可能多的去尋找單詞。這類游戲有不同的變體，一類是你可以多次重復(fù)使用這些字母（這類游戲叫做獵詞），或者你只能使用一次每個字母（這類游戲叫做字母重組）。你組出來的單詞越長就得分越高，使用了所有字母就可以獲得最高分。
這類游戲?qū)τ嬎銠C而言是很「容易」去完成的，而且要強調(diào)一個相當有用的數(shù)據(jù)結(jié)構(gòu)叫做 “Trie”。
解決策略
讓我們先拿出一個單詞?「MAINE」。
首先要做的決定我們要如何處理這個問題。如果問題是字母重組，那么我們可以嘗試所有可能的字母組合，然后看看它們是否是單詞。這對字母重組是一個還不錯的解決方案，但是對獵詞而言就不能給我們多少幫助了，因為字母可以被重用。所以當你可能發(fā)現(xiàn)了單詞 ”name” 時，你將再不會發(fā)現(xiàn)單詞 “nine”。顯然我們不能嘗試窮盡這些字母所有可能的組合，因為我們不知道一個單詞可能被重復(fù)多少次。因為這個原因，我們退步為搜索一個詞典，去看這個詞是否可以只由我們擁有的字母組成。當有一個很大的詞典時，這可能耗費大量的時間，并且你每次換了一個詞時都必須重復(fù)這一步。
作為替代，我們需要一個搜索詞典的方法，可以快速告訴我們某個單詞是否在詞典中。這就是預(yù)測性文本結(jié)構(gòu) Trie 字典樹的用武之地。
什么是 Trie？
Trie 是一個樹數(shù)據(jù)結(jié)構(gòu) — 作為原本樹節(jié)點儲存一個與 key 相關(guān)聯(lián)的值的代替 — 這個節(jié)點現(xiàn)在儲存 key 本身。節(jié)點中的值可用于根據(jù)遍歷次數(shù)來為某些葉子節(jié)點或概率值分配順序。
維基百科中一個 Trie?的例子:
上面這個 Trie 的例子由 “A”，“to”，“tea”，“ted”，“ten”，“i”，“in” 和 “inn” 生成。一旦一個像這樣的 Trie 字典樹結(jié)構(gòu)被生成，去判斷任何一個單詞是否在這個 Trie 字典樹中就是 O(n) 復(fù)雜度的。如果我在搜索 “ted”，我會消耗 O(1) 去尋找 “t”，然后從 “t” 節(jié)點再消耗 O(1) 去尋找 “e”，并且再從 “te” 節(jié)點消耗 O(1) 去到 “d”。
面對問題“這一堆字母在不在這個詞典中？”，這就是一個「非常」快速的解答方案。我們首先要做的就是構(gòu)建詞典。
在 Python 中，這個步驟很簡單。每個節(jié)點的樣子都應(yīng)該是一個詞典。所以我們需要從一個空詞典開始，然后對詞典中的每一個單詞，逐字母的檢查下一個字母是否在我們的 Trie 字典樹結(jié)構(gòu)中，如果不在就添進去。現(xiàn)在，這聽起來相當耗費時間，在某些方面也的確如此，但是它只需要完成一次。當 Trie 被建好后，你可以直接使用它而無需任何其它開銷。
創(chuàng)建 Trie 字典樹
我們需要從一個裝滿所有可能單詞的列表開始（網(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
我們需要一個函數(shù)來給 Trie 中添加單詞。我們通過快速瀏覽 Trie 來檢查每一個字母，判斷我們是否需要添加一個新的 key。因為我們通過 key 來檢索 python 中的字典，所以無需在每個節(jié)點儲存一個 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)
這里有一個簡單的想法。我們接收的參數(shù)是當前所在位置的 Trie 字典樹（注意在這個例子中，Trie 中的所有節(jié)點也是一個 Trie），這個單詞，以及我們所查看的字母在單詞中的索引。
如果索引超過了單詞的長度，我們就停止！如果沒有超過，我們需要檢查是否這個字母已經(jīng)在這個 Trie 中。如果這個字母不在這個 Trie 的下一層中，那么我們添加一個新的字典在這一層，當前這個字母就是字典的 key。然后，我們遞歸的調(diào)用這個函數(shù)，并且傳入我們當前字母對應(yīng)的詞典（也就是 Trie），這個單詞，以及下一個索引位置。
使用這兩個函數(shù)，我們就構(gòu)建了上面展示的 Trie 字典樹。但是有一個問題擺在我們面前。我們?nèi)绾沃牢覀冋业降氖且粋€「單詞」，而不是一個真正的單詞的前一「部分」呢？例如，在上面這個 Trie 的例子中，我們希望 “in” 可以像 “inn” 一樣返回是一個單詞，但是并不希望將 “te” 作為一個詞典中的單詞來返回。
為了完成這一點，當我們完成一個單詞時，「必須」在這個節(jié)點中儲存一個值。來回頭重新審視一下我們的 addWordToTrie 函數(shù)，如果這個節(jié)點表示一個完整的單詞，就將 “l(fā)eaf” 這個 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è)置當前這個詞典節(jié)點的 “l(fā)eaf” 值為 True，或者我們添加一個新的節(jié)點，它的 “l(fā)eaf” 值為 “False”。
當我們加載這個函數(shù)初始化時，應(yīng)該是同樣的設(shè)置 {‘leaf’：False}，所以我們就無需再拿一個空的字符串來作為有效詞的返回。
就是這樣！我們已經(jīng)創(chuàng)建了我們的 Trie 結(jié)構(gòu)，接下來啥時候使用它了。
單詞測試
找一個辦法來進行嘗試：從一個空的列表開始。對我們單詞中的每個字母，檢查我們的 Trie 字典樹，看它是否在其中。如果在，就拿到這個詞典子樹再重新開始（這樣我們可以檢查重復(fù)的字母）。保持這樣進行下去，直到我們找到一個 leaf 標志位為 true 的節(jié)點，或者我們在下一層的詞典子樹中找不到單詞中的任何字母。如果我們發(fā)現(xiàn)了一個標記為 leaf 的節(jié)點，就把這個單詞添到列表中。如果我們沒有找到下一個詞典子樹，就返回并執(zhí)行下一個字母。
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)建一個新單詞傳遞到列表中，但是我們也會遞歸的去尋找新的單詞，用來擴展我們的列表。
有的讀者可能已經(jīng)發(fā)現(xiàn)了接下來的問題。如果字母重復(fù)怎么辦呢？例如我們的單詞是 “「TEEN」”，并且我們現(xiàn)在在 “TE” 節(jié)點上，我們已經(jīng)在子樹上檢查了 “t“，這很好，然后我們在子樹上檢查 ”e“ 并發(fā)現(xiàn) ”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
現(xiàn)在無論我們把同一個單詞找到多少次，我們都可以保證列表中的唯一性。我們也可以將輸入單詞中的字母去重，進而節(jié)約處理時間。
就這樣！利用這三個函數(shù)就可以通過我們輸入的字母來找到所有可能在字典中的單詞。來讓我們把這些包到一個 main 函數(shù)里面，然后給一個輸入，具體步驟我們已經(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.")
因為我們不是單詞重組，所以我們找到了「太」多單詞。使用上面提到的例子「MAINE」和一個我找到的詞典 — 大約有 370000 個單詞 — 這個程度發(fā)現(xiàn)了 208 個單詞。這也是為什么我添加了一個最短單詞長度的原因。限制單詞長度至少為七，我們可以得到如下結(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ù)據(jù)結(jié)構(gòu)，要么嘗試一次循環(huán)的查找多個單詞。
總結(jié)
但愿這篇文章可以為你提供一個 Trie 的基本介紹，便于你去解決一些單詞問題。當你想要一些自動補充完成的任務(wù)時，Trie 是一個很好用的數(shù)據(jù)結(jié)構(gòu)。短信，搜索甚至是指引方向，都可以使用系統(tǒng)中的數(shù)據(jù)構(gòu)建 Trie 來幫助預(yù)測用戶下一步想要輸入什么。正如我們所看到的，它也是在一個搜索大量的現(xiàn)有路徑時很好的結(jié)構(gòu)，在這個例子中，這個路徑就是有效的單詞。
原文地址：Solving Word Hunt in Python: The Trie
原文作者：Citizen Upgrade
更多閱讀
特別推薦
點擊下方閱讀原文加入社區(qū)會員