| 詞語 | 路徑 |
| 歡迎 | 0-1-2 |
| 北大 | 0-3-8 |
| 北京城 | 0-3-4-5 |
| 北京大學 | 0-3-4-6-7 |
至于字典樹的實現，相信只要認真學過數據結構的讀者，都能手到擒來，這里不在贅述。因為HanLP庫已經提供了多種字典樹。
認識DoubleArrayTrieSegment類之前，我們需要了解雙數組字典書的概念。
我們都知道，在樹中遍歷查找之時，我們一般用二分查找，假如某一個樹的節點有N個節點，那么其復雜度就為O(logN)，這樣查找起來一條一條樹的遍歷會非常的慢，所以就誕生了雙數組字典樹的概念。
雙數組字典樹（DAT）是一種狀態轉移復雜度為常數的數據結構。那么什么是狀態呢？從確定有限狀態自動機（DFA）的角度來講，每個節點都是一個狀態，狀態表示當前已查詢到的前綴。
從父節點到子節點的移動過程可以看作一次狀態轉移。在按照某個字符進行狀態轉移前，我們會向父節點詢問該字符與子節點的映射關系（也就是一條路徑一條邊）。如果父節點有滿足條件的邊，則狀態轉移到子節點；否則立即失敗，查詢不到。當成功完成了全部轉移時，我們就拿到了最后一個狀態，詢問該狀態是否時最終狀態。如果是，就查詢到該詞匯，否則該單詞不存在于字典中。
比如我們查詢首圖的“北京大學”，狀態開始為0，查詢到北時狀態為3，查詢到京時狀態為4，查詢到大時狀態為6，查詢到學時狀態為7，最后判斷7是否還有子節點，如果沒有匹配該詞匯，如果有該詞匯不在字典中。比如查詢“北京大”就不在詞匯中。
而雙數組字典由base與check兩個數組組成，其中base數組即節點，也是狀態，分為空閑狀態與占用狀態，check數組為每個元素表示某個狀態的前驅狀態。具體公式如下：
base[s] + c = t check[t] = s
base樹組中的s代表當前狀態的下標，t代表轉移狀態的下標，c代表輸入字符的數值
base[s] + c = t //表示一次狀態轉移
由于轉移后狀態下標為t，且父子關系是唯一的，所以可通過檢驗當前元素的前驅狀態確定轉移是否成功
check[t] = s //檢驗狀態轉移是否成功
這種算法相對于傳統的Trie樹二分查找的優點是，只需要一個加法一次比較即可完成一次狀態轉移，只花費了常數時間，下面給出了雙數組Tree樹的原理圖（注意觀察狀態轉移的過程）
了解了雙數組字典樹的原理，我們就可以來學習DoubleArrayTrieSegment，DoubleArrayTrieSegment分詞器是對DAT（雙數組字典樹）最長匹配的封裝，默認加載hanlp.properites中CoreDictionaryPath指定的詞典。
對應的python代碼如下：
if __name__ == "__main__":
HanLP.Config.ShowTermNature=False#分詞結果不顯示詞性
segment=DoubleArrayTrieSegment()
print(segment.seg("在來到這個世界之前，一起都很Happy"))
運行之后，得到如下圖所示的結果：
當然，這是HanLP提供給我們的默認詞典，如果想加載自己的詞典，或者前文提到的其他開源的詞典庫，可以替換代碼如下所示：
DoubleArrayTrieSegment(["詞典1"，"詞典2"])
但是不知道讀者注意到了沒有，上面的英文happy，它給我們拆成了單個的字母，但其實這是一個整體，如果這里替換成數字，也是一個一個數字，那么如何不讓其拆開呢？
我們來看一段代碼：
if __name__ == "__main__":
HanLP.Config.ShowTermNature=True
segment=DoubleArrayTrieSegment()
segment.enablePartOfSpeechTagging(True)
print(segment.seg("在來到這個世界之前，一起都很Happy"))
enablePartOfSpeechTagging函數的意思是激活數字與英文識別，同時我們把ShowTermNature改為True，觀察其輸出的結果：
這里與我們前面自己寫的算法輸出一模一樣，有分開的詞匯以及詞匯的標記屬性。
雖然雙數組字典樹能遍歷大量的數據，但是如果數據比較長的，這些長的詞匯又比較多的話，比如“受命于天，既壽永昌”算一個詞匯，那么其處理起來時間復雜度依舊非常耗時。所以，我們就需要使用ACDAT進行遍歷。
這里博主不講解其原理，因為太長篇幅有限，感興趣的可以專門學習樹結構的處理。讀者只需要知道其原理，什么時候用雙數組遍歷，什么時候用ACDAT遍歷就行。而HanLP封裝的ACDAT的實現類是AhoCorasickDoubleArrayTrieSegment。
下面，我們來實現AhoCorasickDoubleArrayTrieSegment，代碼如下：
if __name__ == "__main__":
HanLP.Config.ShowTermNature = False
segment = JClass("com.hankcs.hanlp.seg.Other.AhoCorasickDoubleArrayTrieSegment")()
print(segment.seg("在來到這個世界之前，一起都很井然有序"))
運行之后，效果如下：
需要注意的是，python的HanLP雖然提供了AhoCorasickDoubleArrayTrieSegment類，但是讀者可以試試，替換后運行會報錯，控制臺會提示該類沒有seg函數。而HanLP庫又是基于Java開發的，所以在實際的項目中，盡量使用JClass加載Java類進行實戰，因為python的HanLP庫運行速度比Java慢一倍，但python的好處是相對簡單，可以調用其他程序的類，所以速度這方面只要python引用Java類進行調用，其實速度一樣。
到此這篇關于python自然語言處理之字典樹知識總結的文章就介紹到這了,更多相關python字典樹內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家！
