技术员博客      html  css  js  c++  java
  • 双数组 实现 Trie

    NewSMTH

  • 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 结构
  • 相关阅读:
    [Python]正则课程 再次回顾
    Category:Qt WebKit Nokia Developer Wiki
    sql lite 二个数据库之间的表进行复制
    三层结构概述
    CPU与编译器概论(读书笔记)
    Thinkphp 3.2中文章详情页的上一篇 下一篇文章功能
    REPL
    Python操作Sqlite正确实现方法解析
    mpeg4视频中,I帧、p帧、B帧的判定(转载)
    JavaScript is now a necessity
  • 原文地址:https://www.cnblogs.com/lexus/p/2731198.html
Copyright © 2011-2022 技术员博客