NewSMTH

zhjin (sweptAway): 在開(kāi)發(fā)中文分詞器的時(shí)候， 一個(gè)高效的詞典結(jié)構(gòu)尤其重要。 詞典
的一種常見(jiàn)高效的實(shí)現(xiàn)方式就是使用 Trie 結(jié)構(gòu)， 但是傳統(tǒng)的 Trie
結(jié)構(gòu)的實(shí)現(xiàn)方式復(fù)雜， 也比較浪費(fèi)內(nèi)存。 雙數(shù)組 是目前 Trie 結(jié)構(gòu)
中的一種高效的實(shí)現(xiàn)方式， 檢索速度快， 也比較節(jié)約內(nèi)存。 這里簡(jiǎn)
要介紹兩個(gè)比較實(shí)用的雙數(shù)組實(shí)現(xiàn)
1. Darts (http://chasen.org/~taku/software/darts/)
Darts(Double-ARray Trie System) 是日本的 Taku kudo (也是 CRF++
的作者) 實(shí)現(xiàn)的一個(gè)雙數(shù)組， 接口簡(jiǎn)單，只提供了一個(gè)約 500 行代碼
的頭文件 darts.h, 實(shí)現(xiàn)的邏輯也相對(duì)簡(jiǎn)單， 如果了解雙數(shù)組的原理
的話(huà)，要讀懂代碼并不難。目前兩個(gè)著名的開(kāi)源日文分詞系統(tǒng) Mecab,
Chasen 都使用 Darts 構(gòu)建詞典， 檢索速度快， 但是有點(diǎn)浪費(fèi)內(nèi)存。
Darts 的接口文檔是日文的， 我把它的主要接口翻譯成了中文，
可以參看我博客上的如下鏈接
http://zhjin.spaces.live.com/blog/cns!2FEA4AA78B600980!692.entry?&_c02_vws=1
2. Darts-clone (http://code.google.com/p/darts-clone/)
另外一個(gè)日本人 Susumu Yata 開(kāi)發(fā)的一個(gè)雙數(shù)組實(shí)現(xiàn)， 接口完全兼容
Darts, 因此叫做 Darts-clone, 實(shí)現(xiàn)算法可以參看論文
Yata, S.; Oono, M.; Morita, K.; Fuketa, M.; Sumitomo, T. & Aoe, J.
A compact static double-array keeping character codes.
Information Processing and Management, Vol. 43, No. 1, pp. 237-247, 2007.
從論文的署名順利來(lái)看， 該作者應(yīng)該是雙數(shù)組的發(fā)明者 Junichi Aoe
的學(xué)生。 在 Darts 中， 雙數(shù)組的每個(gè)節(jié)點(diǎn)要由 base 和 check 兩個(gè)
32bit 整數(shù)來(lái)表示， Susumu Yata 的論文中給出了只用一個(gè) 32bit 整
數(shù)來(lái)同時(shí)表示 base 和 check
的簡(jiǎn)單方法， 同時(shí)又對(duì)只有單個(gè)分支的節(jié)點(diǎn)進(jìn)行壓縮，因此Darts-clone
相比于 Darts大大節(jié)約了內(nèi)存。 另外， Darts-clone 在實(shí)現(xiàn)的時(shí)候把雙
數(shù)組中的加法操作巧妙替換為位運(yùn)算， 因此檢索速度上也要比 Darts 稍
快一些。
有興趣的讀者可以參看 http://code.google.com/p/darts-clone/w/list
中給出的 Darts & Darts-clone 的性能對(duì)比。作者給了 Darts-clone 的兩個(gè)
實(shí)現(xiàn)
Darts clone 0.32f 內(nèi)存消耗為 Darts 的 1/2, 速度比 Darts 快
Darts clone 0.32e 內(nèi)存消耗為 Darts 的 1/4, 速度比 Darts 慢
當(dāng)然以上為粗略結(jié)果， 性能表現(xiàn)在不同數(shù)據(jù)集上略有差異��boycat (記得請(qǐng)冬子打球|我是鄉(xiāng)下人，小地方來(lái)的): 贊~~~
【 在 zhjin (sweptAway) 的大作中提到: 】
: 在開(kāi)發(fā)中文分詞器的時(shí)候， 一個(gè)高效的詞典結(jié)構(gòu)尤其重要。 詞典
: 的一種常見(jiàn)高效的實(shí)現(xiàn)方式就是使用 Trie 結(jié)構(gòu)， 但是傳統(tǒng)的 Trie
: 結(jié)構(gòu)的實(shí)現(xiàn)方式復(fù)雜， 也比較浪費(fèi)內(nèi)存。 雙數(shù)組 是目前 Trie 結(jié)構(gòu)
: ...................jiju (Super.Jiju): zan
【 在 zhjin (sweptAway) 的大作中提到: 】
: 在開(kāi)發(fā)中文分詞器的時(shí)候， 一個(gè)高效的詞典結(jié)構(gòu)尤其重要。 詞典
: 的一種常見(jiàn)高效的實(shí)現(xiàn)方式就是使用 Trie 結(jié)構(gòu)， 但是傳統(tǒng)的 Trie
: 結(jié)構(gòu)的實(shí)現(xiàn)方式復(fù)雜， 也比較浪費(fèi)內(nèi)存。 雙數(shù)組 是目前 Trie 結(jié)構(gòu)

總結(jié)

以上是生活随笔為你收集整理的双数组 实现 Trie的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。