海的声音治愈系（Darts: DoubleARray Trie System海 的 声音我的搜狐）

我没有看懂base［］的值具体是如何确定的           ，这篇文章转载过来的

Darts 是用于构建双数组 Double-Array [Aoe 1989] 的简单的 C++ Template Library . 双数组 (Double-Array) 是用于实现 Trie 的一种数据结构, 比其它的类 Trie 实现方式(Hash-Tree, Digital Trie, Patricia Tree, Suffix Array) 速度更快           。 原始的 Double-Array 使能够支持动态添加删除 key, 但是 Darts 只支持把排好序的词典文件转换为静态的 Double-Array.

Darts 既可以像 Hash 一样作为简单的词典使用
  
 
  
 
  
 
  
 
  
 
 ，也能非常高效的执行分词词典中必须的 Common Prefix Search 操作
  
 
  
 
  
 
  
 
  
 
 。

自2003年7月起










， 两个开源的日语分词系统 MeCab, ChaSen 都使用了 Darts .

下载

Darts 是自由软件．遵循 LGPL(Lesser GNU General Public License) 和 BSD 协议, 可以修改后重新发布.

Source

darts-0.32.tar.gz: HTTP

安装

% ./configure % make% make check% make install然后在程序中 include /usr/local/include/darts.h

使用方法

Darts 只提供了 darts.h 这个 C++ 模板文件










。每次使用的时候 include 该文件即可.

使用这样的发布方式是希望通过内联函数实现高效率 
  
  
  
  
  。

类接口

namespace Darts { template <class NodeType, class NodeUType class ArrayType, class ArrayUType, class LengthFunc = Length<NodeType> > class DobuleArrayImpl { public: typedef ArrayType result_type; typedef NodeType key_type; DoubleArrayImpl(); ~DoubleArrayImpl(); int set_array(void *ptr, size_t = 0); void *array(); void clear(); size_t size (); size_t unit_size (); size_t nonzero_size (); size_t total_size (); int build (size_t key_size, key_type **key, size_t *len = 0, result_type *val = 0, int (*pg)(size_t, size_t) = 0); int open (const char *file, const char *mode = "rb", size_t offset = 0, size_t _size = 0); int save (const char *file, const char *mode = "wb", size_t offset = 0); result_type exactMatchSearch (const key_type *key, size_t len = 0, size_t node_pos = 0) size_t commonPrefixSearch (const key_type *key, result_type *result, size_t result_size, size_t len = 0, size_t node_pos = 0) result_type traverse (const key_type *key, size_t &node_pos, size_t &key_pos, size_t len = 0) }; typedef Darts::DoubleArrayImpl<char, unsigned char, int, unsigned int> DoubleArray;};

模板参数说明

NodeType Trie 节点类型 
  
  
  
  
  ， 对普通的 C 字符串检索
  
  
  
  
  
 ， 设置为 char 型即可. NodeUType Trie 节点转为无符号整数的类型, 对普通的 C 字符串检索
 


 


 


 


 


， 设置为 unsigned char 型即可. ArrayType Double-Array 的 Base 元素使用的类型, 通常设置为有符号 32bit 整数 ArrayUType Double-Array 的 Check 元素使用的类型, 通常设置为无符号 32bit 整数 LengthFunc 使用 NodeType 数组的时候 
 
 
 
 
 ，使用该函数对象获取数组的大小, 在该函数对象中对 operator() 进行重载.

NodeType 是 char 的时候
   
   
   
   
   
 ， 缺省使用 strlen 函数
 

 

 

 

 

， 否则以 0 作为数组结束标志计算数组的大小 .

typedef 说明

模板参数类型的别名. 在外部需要使用这些类型的时候使用 .

key_type 待检索的 key 的单个元素的类型. 等同于 NodeType. result_type 单个结果的类型. 等同于 ArrayType .

方法说明

int Darts::DoubleArrayImpl::build(size_t size, const key_type **str, const size_t *len = 0, const result_type *val = 0, int (*progress_func)(size_t, size_t) = 0) 构建 Double Array .

size 词典大小 (记录的词条数目),

str 指向各词条的指针 (共 size个指针)

len 用于记录各个词条的长度的数组(数组大小为 size)

val 用于保存各词条对应的 value 的数组 (数组大小为 size)

progress_func 构建进度函数.

str 的各个元素必须按照字典序排好序.

另外 val 数组中的元素不能有负值.

len, val, progress_func 可以省略,

省略的时候 

 

 

 

 

 ， len 使用 LengthFunc 计算,

val 的各元素的值为从 0 开始的计数值
  
  
  
  
  
 。

构建成功           ，返回 0； 失败的时候返回值为负.

进度函数 progress_func 有两个参数.

第一个 size_t 型参数表示目前已经构建的词条数

第二个 size_t 型参数表示所有的词条数 result_type Darts::DoubleArrayImpl::exactMatchSearch(const key_type *key, size_t len = 0, size_t node_pos = 0) 进行精确匹配(exact match) 检索, 判断给定字符串是否为词典中的词条.

key 待检索字符串,

len 字符串长度,

node_pos 指定从 Double-Array 的哪个节点位置开始检索.

len, 和 node_pos 都可以省略, 省略的时候

 
 

 
 

 
 

 
 

 
 

， len 缺省使用 LengthFunc 计算,

node_pos 缺省为 root 节点.

检索成功时









， 返回 key 对应的 value 值, 失败则返回 -1.

size_t Darts::DoubleArrayImpl::commonPrefixSearch (const key_type *key, result_type *result, size_t result_size, size_t len = 0, size_t node_pos = 0) 执行 common prefix search. 检索给定字符串的哪些的前缀是词典中的词条

key 待检索字符串,

result 用于保存多个命中结果的数组,

result_size 数组 result 大小,

len 待检索字符串长度,

node_pos 指定从 Double-Array 的哪个节点位置开始检索.

len, 和 node_pos 都可以省略, 省略的时候                 ， len 缺省使用 LengthFunc 计算,

node_pos 缺省为 root 节点.

函 数返回命中的词条个数. 对于每个命中的词条
 
 
 
 
 
 
 
 
 
 
， 词条对应的 value 值存依次放在 result 数组中. 如果命中的词条个数超过 result_size 的大小















， 则 result 数组中只保存 result_size 个结果
 


 


 


 


 


。函数的返回值为实际的命中词条个数           ， 可能超过 result_size 的大小 
 
 
 
 
 。

result_t Darts::DoubleArrayImpl::traverse (const key_type *key, size_t &node_pos, size_t &key_pos, size_t len = 0) traverse Trie
  
 
  
 
  
 
  
 
  
 
 ， 检索当前字符串并记录检索后到达的位置

key 待检索字符串,

node_pos 指定从 Double-Array 的哪个节点位置开始检索.

key_pos 从待检索字符串的哪个位置开始检索

len 待检索字符串长度,

该函数和 exactMatchSearch 很相似. traverse 过程是按照检索串 key 在 TRIE 的节点中进行转移.

但是函数执行后, 可以获取到最后到达的 Trie 节点位置










，最后到达的字符串位置 . 这和 exactMatchSearch 是有区别的.

node_pos 通常指定为 root 位置 (0) . 函数调用后 
  
  
  
  
  ， node_pos 的值记录最后到达的 DoubleArray 节点位置
   
   
   
   
   
 。

key_pos 通常指定为 0. 函数调用后
  
  
  
  
  
 ， key_pos 保存最后到达的字符串 key 中的位置
 

 

 

 

 

。

检索失败的时候
 


 


 


 


 


， 返回 -1 或者 -2 .

-1 表示再叶子节点失败, -2 表示在中间节点失败,.

检索成功的时候 
 
 
 
 
 ， 返回 key 对应的 value. int Darts::DoubleArrayImpl::save(const char *file, const char *mode = "wb", size_t offset = 0) 把 Double-Array 保存为文件.

file 保存文件名,

mode 文件打开模式

offset 保存的文件位置偏移量, 预留将来使用
   
   
   
   
   
 ， 目前没有实现 .

成功返回 0 
 

 

 

 

 

， 失败返回 -1

int Darts::DoubleArrayImpl::open (const char *file, const char *mode = "rb", size_t offset = 0, size_t size = 0) 读入 Double-Array 文件.

file 读取文件名,

mode 文件打开模式

offset 读取的文件位置偏移量

size 为 0 的时候, size 使用文件的大小 .

成功返回 0  

 

 

 

 

 ， 失败返回 -1

size_t Darts::DoubleArrayImpl::size() 返回 Double-Array 大小. size_t Darts::DoubleArrayImpl::unit_size() Double-Array 一个元素的大小(byte).

size() * unit_size() 是, 存放 Double-Array 所需要的内存(byte) 大小.

size_t Darts::DoubleArrayImpl::nonzero_size

() Double-Array 的所有元素中           ， 被使用的元素的数目, .

nonezero_size()/size() 用于计算压缩率.

例子程序

从静态词典构建双数组 Double-Array.

#include <iostream>#include <darts.h>int main (int argc, char **argv){ using namespace std; Darts::DoubleArray::key_type *str[] = { "ALGOL", "ANSI", "ARCO", "ARPA", "ARPANET", "ASCII" }; // same as char* Darts::DobuleArray::result_type val[] = { 1, 2, 3, 4, 5, 6 }; // same as int Darts::DoubleArray da; da.build (6, str, 0, val); cout << da.exactMatchSearch("ALGOL") << endl; cout << da.exactMatchSearch("ANSI") << endl; cout << da.exactMatchSearch("ARCO") << endl;; cout << da.exactMatchSearch("ARPA") << endl;; cout << da.exactMatchSearch("ARPANET") << endl;; cout << da.exactMatchSearch("ASCII") << endl;; cout << da.exactMatchSearch("APPARE") << endl; da.save("some_file");}执行结果123456-1

从标准输入读取字符串, 对 Double-Array 执行 Common Prefix Search

#include <iostream>#include <string>#include <algorithm>#include <darts.h>int main (int argc, char **argv){ using namespace std; Darts::DoubleArray da; if (da.open("some_file") == -1) return -1; Darts::DoubleArray::result_type r [1024]; Darts::DoubleArray::key_type buf [1024]; while (cin.getline (buf, 1024)) { size_t result = da.commonPrefixSearch(buf, r, 1024); if (result == 0) { cout << buf << ": not found" << endl; } else { cout << buf << ": found, num=" << result << " "; copy (r, r + result, ostream_iterator<Darts::DoubleArray::result_type>(cout, " ")); cout << endl; } } return 0;}

付属程序说明

mkdarts

% ./mkdarts DictionaryFile DoubleArrayFile

把排序好的词典 DictionaryFile 转换为 DoubleArrayFile

darts

% ./darts DoubleArrayFile

使用 DoubleArrayFile 做 common prefix search .

使用例子

% cd tests% head -10 linux.wordsALGOLANSIARCOARPAARPANETASCII .. % ../mkdarts linux.words darMaking Double Array: 100% |*******************************************|Done!, Compression Ratio: 94.6903 %% ../darts darLinuxLinux: found, num=2 3697 3713WindowsWindows: not foundLaTeXLaTeX: found, num=1 3529

参考文献, 链接

[Aoe1989] Aoe, J. An Efficient Digital Search Algorithm by Using a Double-Array Structure. IEEE Transactions on Software Engineering. Vol. 15, 9 (Sep 1989). pp. 1066-1077. [Datrie] Theppitak Karoonboonyanan An Implementation of Double-Array Triehttp://www.links.nectec.or.th/~thep/datrie/ [単語と辞書] 松本裕治 ほか. 単語と辞書 岩波講座言語の科学 Vol.3 pp.79-81