两组数据排序一致（双数组实现 Trie）

时间2025-05-04 10:56:05分类IT科技浏览5811

导读：zhjin (sweptAway : 在开发中文分词器的时候，一个高效的词典结构尤其重要。词典...

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 结构

两组数据排序一致（双数组 实现 Trie）

两组数据排序一致（双数组实现 Trie）