主頁 > 知識庫 > python自然語言處理之字典樹知識總結(jié)

python自然語言處理之字典樹知識總結(jié)

熱門標(biāo)簽:上海機器人外呼系統(tǒng)哪家好 蓋州市地圖標(biāo)注 浙江電銷卡外呼系統(tǒng)好用嗎 315電話機器人廣告 地圖制圖標(biāo)注位置改變是移位嗎 地圖標(biāo)注微信發(fā)送位置不顯示 地圖標(biāo)注的意義點 房產(chǎn)電銷外呼系統(tǒng) 南京銷售外呼系統(tǒng)軟件

一、什么是字典樹

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

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

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

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

詞語 路徑
歡迎 0-1-2
北大 0-3-8
北京城 0-3-4-5
北京大學(xué) 0-3-4-6-7

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

二、DoubleArrayTrieSegment

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

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

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

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

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

而雙數(shù)組字典由base與check兩個數(shù)組組成,其中base數(shù)組即節(jié)點,也是狀態(tài),分為空閑狀態(tài)與占用狀態(tài),check數(shù)組為每個元素表示某個狀態(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)系是唯一的,所以可通過檢驗當(dāng)前元素的前驅(qū)狀態(tài)確定轉(zhuǎn)移是否成功

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

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

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

對應(yīng)的python代碼如下:

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

運行之后,得到如下圖所示的結(jié)果:

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

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

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

我們來看一段代碼:

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

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

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

三、AhoCorasickDoubleArrayTrieSegment

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

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

下面,我們來實現(xiàn)AhoCorasickDoubleArrayTrieSegment,代碼如下:

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

運行之后,效果如下:

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

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

您可能感興趣的文章:
  • Python自然語言處理之切分算法詳解
  • Python自然語言處理 NLTK 庫用法入門教程【經(jīng)典】
  • Python自然語言處理之詞干,詞形與最大匹配算法代碼詳解
  • Python編程使用NLTK進行自然語言處理詳解
  • 用Python進行一些簡單的自然語言處理的教程
  • python第三方庫visdom的使用入門教程
  • Python自動安裝第三方庫的小技巧(pip使用詳解)
  • Python文件名的匹配之clob庫
  • Python的文本常量與字符串模板之string庫
  • python爬蟲請求庫httpx和parsel解析庫的使用測評
  • 能讓你輕松的實現(xiàn)自然語言處理的5個Python庫

標(biāo)簽:臨汾 金華 日照 陽泉 赤峰 貴州 雙鴨山 克拉瑪依

巨人網(wǎng)絡(luò)通訊聲明:本文標(biāo)題《python自然語言處理之字典樹知識總結(jié)》,本文關(guān)鍵詞  python,自然語言,處理,之,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題,煩請?zhí)峁┫嚓P(guān)信息告之我們,我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《python自然語言處理之字典樹知識總結(jié)》相關(guān)的同類信息!
  • 本頁收集關(guān)于python自然語言處理之字典樹知識總結(jié)的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章