Double-Array Trie树是目前 Trie 树各种实现中性能和存储空间均达到很好效果的实现，DAT 既可以像 Hash 一样作为简单的词典使用，也能非常高效的执行分词词典中必须的 Common Prefix Search 操作。自2003年7月起， 两个开源的日语分词系统 MeCab，ChaSen 都使用了 Darts。
DAT 完整的实现比较复杂，An Implementation of Double-Array Trie介绍了一种实现。作者Theppitak Karoonboonyanan好像是个泰国人，文中有他的c实现，以静态库/动态库的方式提供，以及Christos Gioran的Java实现。

我是没看明白实现细节，先看看怎么用好了。

安装libdatrie

从github下载libdatrie-0.2.12.tar.xz，解压进入目录，依次执行：

./configure
make
make install

即可安装。安装完毕，/usr/local/lib/下新增以下文件：

-rw-r--r-- 1 root root 192672 11月  8 10:16 /usr/local/lib/libdatrie.a
-rwxr-xr-x 1 root root    947 11月  8 10:16 /usr/local/lib/libdatrie.la
lrwxrwxrwx 1 root root     18 11月  8 10:16 /usr/local/lib/libdatrie.so -> libdatrie.so.1.3.5
lrwxrwxrwx 1 root root     18 11月  8 10:16 /usr/local/lib/libdatrie.so.1 -> libdatrie.so.1.3.5
-rwxr-xr-x 1 root root 110269 11月  8 10:16 /usr/local/lib/libdatrie.so.1.3.5

/usr/local/include/下新增datrie目录，包含4个头文件：alpha-map.h triedefs.h trie.h typedefs.h。

如不想安装到系统，可直接使用libdatrie-0.2.12/datrie/.libs/下的libdatrie.a静态库。

使用

进入libdatrie-0.2.12/tests/看一下测试代码。
gcc test_byte_alpha.c utils.c -ldatrie