一、什么是字典樹

在自然語言處理中，字符串集合常用字典樹存儲(chǔ)，這是一種字符串上的樹形數(shù)據(jù)結(jié)構(gòu)。字典樹中每條邊都對(duì)應(yīng)一個(gè)字，從根節(jié)點(diǎn)往下的路徑構(gòu)成一個(gè)個(gè)字符串。

字典樹并不直接在節(jié)點(diǎn)上存儲(chǔ)字符串，而是將詞語視作根節(jié)點(diǎn)到某節(jié)點(diǎn)之間的一條路徑，并在終點(diǎn)節(jié)點(diǎn)上做個(gè)標(biāo)記（表明到該節(jié)點(diǎn)就結(jié)束了）。

要查詢一個(gè)單詞，指需要順著這條路徑從根節(jié)點(diǎn)往下走。如果能走到標(biāo)記的節(jié)點(diǎn)，則說明該字符串在集合中，否則說明不在。下圖為字典樹結(jié)構(gòu)示例：

如上圖所示，每條路徑都是一個(gè)詞匯，且沒有子節(jié)點(diǎn)就可以判定該條路徑結(jié)尾了。具體可以映射為下標(biāo)所示：

至于字典樹的實(shí)現(xiàn)，相信只要認(rèn)真學(xué)過數(shù)據(jù)結(jié)構(gòu)的讀者，都能手到擒來，這里不在贅述。因?yàn)镠anLP庫已經(jīng)提供了多種字典樹。

二、DoubleArrayTrieSegment

認(rèn)識(shí)DoubleArrayTrieSegment類之前，我們需要了解雙數(shù)組字典書的概念。

我們都知道，在樹中遍歷查找之時(shí)，我們一般用二分查找，假如某一個(gè)樹的節(jié)點(diǎn)有N個(gè)節(jié)點(diǎn)，那么其復(fù)雜度就為O(logN)，這樣查找起來一條一條樹的遍歷會(huì)非常的慢，所以就誕生了雙數(shù)組字典樹的概念。

雙數(shù)組字典樹（DAT）是一種狀態(tài)轉(zhuǎn)移復(fù)雜度為常數(shù)的數(shù)據(jù)結(jié)構(gòu)。那么什么是狀態(tài)呢？從確定有限狀態(tài)自動(dòng)機(jī)（DFA）的角度來講，每個(gè)節(jié)點(diǎn)都是一個(gè)狀態(tài)，狀態(tài)表示當(dāng)前已查詢到的前綴。

從父節(jié)點(diǎn)到子節(jié)點(diǎn)的移動(dòng)過程可以看作一次狀態(tài)轉(zhuǎn)移。在按照某個(gè)字符進(jìn)行狀態(tài)轉(zhuǎn)移前，我們會(huì)向父節(jié)點(diǎn)詢問該字符與子節(jié)點(diǎn)的映射關(guān)系（也就是一條路徑一條邊）。如果父節(jié)點(diǎn)有滿足條件的邊，則狀態(tài)轉(zhuǎn)移到子節(jié)點(diǎn)；否則立即失敗，查詢不到。當(dāng)成功完成了全部轉(zhuǎn)移時(shí)，我們就拿到了最后一個(gè)狀態(tài)，詢問該狀態(tài)是否時(shí)最終狀態(tài)。如果是，就查詢到該詞匯，否則該單詞不存在于字典中。

比如我們查詢首圖的“北京大學(xué)”，狀態(tài)開始為0，查詢到北時(shí)狀態(tài)為3，查詢到京時(shí)狀態(tài)為4，查詢到大時(shí)狀態(tài)為6，查詢到學(xué)時(shí)狀態(tài)為7，最后判斷7是否還有子節(jié)點(diǎn)，如果沒有匹配該詞匯，如果有該詞匯不在字典中。比如查詢“北京大”就不在詞匯中。

而雙數(shù)組字典由base與check兩個(gè)數(shù)組組成，其中base數(shù)組即節(jié)點(diǎn)，也是狀態(tài)，分為空閑狀態(tài)與占用狀態(tài)，check數(shù)組為每個(gè)元素表示某個(gè)狀態(tài)的前驅(qū)狀態(tài)。具體公式如下：

base[s] + c = t
check[t] =  s

base樹組中的s代表當(dāng)前狀態(tài)的下標(biāo)，t代表轉(zhuǎn)移狀態(tài)的下標(biāo)，c代表輸入字符的數(shù)值

base[s] + c = t //表示一次狀態(tài)轉(zhuǎn)移

由于轉(zhuǎn)移后狀態(tài)下標(biāo)為t，且父子關(guān)系是唯一的，所以可通過檢驗(yàn)當(dāng)前元素的前驅(qū)狀態(tài)確定轉(zhuǎn)移是否成功

check[t] = s //檢驗(yàn)狀態(tài)轉(zhuǎn)移是否成功

這種算法相對(duì)于傳統(tǒng)的Trie樹二分查找的優(yōu)點(diǎn)是，只需要一個(gè)加法一次比較即可完成一次狀態(tài)轉(zhuǎn)移，只花費(fèi)了常數(shù)時(shí)間，下面給出了雙數(shù)組Tree樹的原理圖（注意觀察狀態(tài)轉(zhuǎn)移的過程）

了解了雙數(shù)組字典樹的原理，我們就可以來學(xué)習(xí)DoubleArrayTrieSegment，DoubleArrayTrieSegment分詞器是對(duì)DAT（雙數(shù)組字典樹）最長(zhǎng)匹配的封裝，默認(rèn)加載hanlp.properites中CoreDictionaryPath指定的詞典。

對(duì)應(yīng)的python代碼如下：

if __name__ == "__main__":
    HanLP.Config.ShowTermNature=False#分詞結(jié)果不顯示詞性
    segment=DoubleArrayTrieSegment()
    print(segment.seg("在來到這個(gè)世界之前，一起都很Happy"))

運(yùn)行之后，得到如下圖所示的結(jié)果：

當(dāng)然，這是HanLP提供給我們的默認(rèn)詞典，如果想加載自己的詞典，或者前文提到的其他開源的詞典庫，可以替換代碼如下所示：

DoubleArrayTrieSegment(["詞典1"，"詞典2"])

但是不知道讀者注意到了沒有，上面的英文happy，它給我們拆成了單個(gè)的字母，但其實(shí)這是一個(gè)整體，如果這里替換成數(shù)字，也是一個(gè)一個(gè)數(shù)字，那么如何不讓其拆開呢？

我們來看一段代碼：

if __name__ == "__main__":
    HanLP.Config.ShowTermNature=True
    segment=DoubleArrayTrieSegment()
    segment.enablePartOfSpeechTagging(True)
    print(segment.seg("在來到這個(gè)世界之前，一起都很Happy"))

enablePartOfSpeechTagging函數(shù)的意思是激活數(shù)字與英文識(shí)別，同時(shí)我們把ShowTermNature改為True，觀察其輸出的結(jié)果：

這里與我們前面自己寫的算法輸出一模一樣，有分開的詞匯以及詞匯的標(biāo)記屬性。

三、AhoCorasickDoubleArrayTrieSegment

雖然雙數(shù)組字典樹能遍歷大量的數(shù)據(jù)，但是如果數(shù)據(jù)比較長(zhǎng)的，這些長(zhǎng)的詞匯又比較多的話，比如“受命于天，既壽永昌”算一個(gè)詞匯，那么其處理起來時(shí)間復(fù)雜度依舊非常耗時(shí)。所以，我們就需要使用ACDAT進(jìn)行遍歷。

這里博主不講解其原理，因?yàn)樘L(zhǎng)篇幅有限，感興趣的可以專門學(xué)習(xí)樹結(jié)構(gòu)的處理。讀者只需要知道其原理，什么時(shí)候用雙數(shù)組遍歷，什么時(shí)候用ACDAT遍歷就行。而HanLP封裝的ACDAT的實(shí)現(xiàn)類是AhoCorasickDoubleArrayTrieSegment。

下面，我們來實(shí)現(xiàn)AhoCorasickDoubleArrayTrieSegment，代碼如下：

if __name__ == "__main__":
    HanLP.Config.ShowTermNature = False
    segment = JClass("com.hankcs.hanlp.seg.Other.AhoCorasickDoubleArrayTrieSegment")()
    print(segment.seg("在來到這個(gè)世界之前，一起都很井然有序"))

運(yùn)行之后，效果如下：

需要注意的是，python的HanLP雖然提供了AhoCorasickDoubleArrayTrieSegment類，但是讀者可以試試，替換后運(yùn)行會(huì)報(bào)錯(cuò)，控制臺(tái)會(huì)提示該類沒有seg函數(shù)。而HanLP庫又是基于Java開發(fā)的，所以在實(shí)際的項(xiàng)目中，盡量使用JClass加載Java類進(jìn)行實(shí)戰(zhàn)，因?yàn)閜ython的HanLP庫運(yùn)行速度比Java慢一倍，但python的好處是相對(duì)簡(jiǎn)單，可以調(diào)用其他程序的類，所以速度這方面只要python引用Java類進(jìn)行調(diào)用，其實(shí)速度一樣。

到此這篇關(guān)于python自然語言處理之字典樹知識(shí)總結(jié)的文章就介紹到這了,更多相關(guān)python字典樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論