天天看點

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

經過了n長時間.有時候想放棄有時候.想繼續斷斷續續的.終于寫完了CQ分詞的基本原型.目前實作了正向最大比對.和正向最好比對.全文全比對取詞等功能.希望大家能支援我.我一定會寫出更好的分詞的.

[b]分詞的速度.大家自己試去吧.我這裡是300w字/s.估計我電腦好點吧嘿嘿[/b] :lol:

傳統的分詞方式有:

 整詞二分法

結構:首字散清單、詞索引表、詞典正文

優點:資料結構簡單、占用空間小。

缺點:全詞比對,效率相對來說不高。

 Tire索引樹法

結構:首字散清單、Trie索引樹結點

優點:分詞中,不需預知待查詢詞的長度,沿樹鍊逐字比對。

缺點:構造和維護比較複雜,單詞樹枝多,浪費了一定的空間。

 逐字二分法

結構:同整詞二分法

優點:查詢采用逐字比對,提高了一定的比對效率。

缺點:由于詞典結構未改變,效率的提高有限。

然後我們先了解一下雙數組tire樹.以下是雙數組tire樹的簡介.

基于雙數組Trie的詞典查詢算法

[size=large][color=red]雙數組構造完成之後,查詢實質上就是将待查詞的各字分别轉換為相應的序列碼,然後作幾次加法,即可查到相應的詞語。查詢效率是極高的[/color][/size]

好了不說了這些都是抄來的.

如果有興趣的朋友可以和我聯系互相學習.

下面我來介紹下CQ分詞的大體實作.至于詞典的實作比較複雜在這裡不多說了.如有需要我會放出源碼的

目前實作的接口有兩個

這個接口負責從文章中取詞.

比如”中華人民共和國萬歲”

在allWords()方法取得的結果應該是.全文全比對

在maxFrontWords()方法取得的結果應該是.正向最大比對

在minFrontWords()方法取得的結果應該是.正向最小比對

還有一個簡單的文本分割.現在比較亂.我盡快生成api就好多了

對字元串進行簡單的标記, 複雜的根據詞性的可以自己擴充.

注意: