• zhjin (sweptAway): 在开发中文分词器的时候， 一个高效的词典结构尤其重要。 词典
    的一种常见高效的实现方式就是使用 Trie 结构， 但是传统的 Trie
    结构的实现方式复杂， 也比较浪费内存。 双数组 是目前 Trie 结构
    中的一种高效的实现方式， 检索速度快， 也比较节约内存。 这里简
    要介绍两个比较实用的双数组实现
    1. Darts (http://chasen.org/~taku/software/darts/)
    Darts(Double-ARray Trie System) 是日本的 Taku kudo (也是 CRF++
    的作者) 实现的一个双数组， 接口简单，只提供了一个约 500 行代码
    的头文件 darts.h, 实现的逻辑也相对简单， 如果了解双数组的原理
    的话，要读懂代码并不难。目前两个著名的开源日文分词系统 Mecab,
    Chasen 都使用 Darts 构建词典， 检索速度快， 但是有点浪费内存。
    Darts 的接口文档是日文的， 我把它的主要接口翻译成了中文，
    可以参看我博客上的如下链接
    http://zhjin.spaces.live.com/blog/cns!2FEA4AA78B600980!692.entry?&_c02_vws=1
    2. Darts-clone (http://code.google.com/p/darts-clone/)
    另外一个日本人 Susumu Yata 开发的一个双数组实现， 接口完全兼容
    Darts, 因此叫做 Darts-clone, 实现算法可以参看论文
    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.
    从论文的署名顺利来看， 该作者应该是双数组的发明者 Junichi Aoe
    的学生。 在 Darts 中， 双数组的每个节点要由 base 和 check 两个
    32bit 整数来表示， Susumu Yata 的论文中给出了只用一个 32bit 整
    数来同时表示 base 和 check
    的简单方法， 同时又对只有单个分支的节点进行压缩，因此Darts-clone
    相比于 Darts大大节约了内存。 另外， Darts-clone 在实现的时候把双
    数组中的加法操作巧妙替换为位运算， 因此检索速度上也要比 Darts 稍
    快一些。
    有兴趣的读者可以参看 http://code.google.com/p/darts-clone/w/list
    中给出的 Darts & Darts-clone 的性能对比。作者给了 Darts-clone 的两个
    实现
    Darts clone 0.32f 内存消耗为 Darts 的 1/2, 速度比 Darts 快
    Darts clone 0.32e 内存消耗为 Darts 的 1/4, 速度比 Darts 慢
    当然以上为粗略结果， 性能表现在不同数据集上略有差异��
  • boycat (记得请冬子打球|我是乡下人，小地方来的): 赞~~~
    【 在 zhjin (sweptAway) 的大作中提到: 】
    : 在开发中文分词器的时候， 一个高效的词典结构尤其重要。 词典
    : 的一种常见高效的实现方式就是使用 Trie 结构， 但是传统的 Trie
    : 结构的实现方式复杂， 也比较浪费内存。 双数组 是目前 Trie 结构
    : ...................
  • jiju (Super.Jiju): zan
    【 在 zhjin (sweptAway) 的大作中提到: 】
    : 在开发中文分词器的时候， 一个高效的词典结构尤其重要。 词典
    : 的一种常见高效的实现方式就是使用 Trie 结构， 但是传统的 Trie
    : 结构的实现方式复杂， 也比较浪费内存。 双数组 是目前 Trie 结构
    • 声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。