Darts 是用于構(gòu)建雙數(shù)組 Double-Array [Aoe 1989] 的簡(jiǎn)單的 C++ Template Library . 雙數(shù)組 (Double-Array) 是用于實(shí)現(xiàn) Trie 的一種數(shù)據(jù)結(jié)構(gòu), 比其它的類 Trie 實(shí)現(xiàn)方式(Hash-Tree, Digital Trie, Patricia Tree, Suffix Array) 速度更快。 原始的 Double-Array 使能夠支持動(dòng)態(tài)添加刪除 key, 但是 Darts 只支持把排好序的詞典文件轉(zhuǎn)換為靜態(tài)的 Double-Array.
Darts 既可以像 Hash 一樣作為簡(jiǎn)單的詞典使用，也能非常高效的執(zhí)行分詞詞典中必須的 Common Prefix Search 操作。
自2003年7月起， 兩個(gè)開(kāi)源的日語(yǔ)分詞系統(tǒng) MeCab, ChaSen 都使用了 Darts .
- Darts 是自由軟件．遵循 LGPL(Lesser GNU General Public License) 和 BSD 協(xié)議, 可以修改后重新發(fā)布.
% ./configure
% make
% make check
% make install
然后在程序中 include /usr/local/include/darts.h
Darts 只提供了 darts.h 這個(gè) C++ 模板文件。每次使用的時(shí)候 include 該文件即可.
使用這樣的發(fā)布方式是希望通過(guò)內(nèi)聯(lián)函數(shù)實(shí)現(xiàn)高效率。
類接口
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;
};
模板參數(shù)說(shuō)明
| NodeType | Trie 節(jié)點(diǎn)類型， 對(duì)普通的 C 字符串檢索， 設(shè)置為 char 型即可. |
| NodeUType | Trie 節(jié)點(diǎn)轉(zhuǎn)為無(wú)符號(hào)整數(shù)的類型, 對(duì)普通的 C 字符串檢索， 設(shè)置為 unsigned char 型即可. |
| ArrayType | Double-Array 的 Base 元素使用的類型, 通常設(shè)置為有符號(hào) 32bit 整數(shù) |
| ArrayUType | Double-Array 的 Check 元素使用的類型, 通常設(shè)置為無(wú)符號(hào) 32bit 整數(shù) |
| LengthFunc | 使用 NodeType 數(shù)組的時(shí)候，使用該函數(shù)對(duì)象獲取數(shù)組的大小, 在該函數(shù)對(duì)象中對(duì) operator() 進(jìn)行重載.
NodeType 是 char 的時(shí)候， 缺省使用 strlen 函數(shù)， 否則以 0 作為數(shù)組結(jié)束標(biāo)志計(jì)算數(shù)組的大小 . |
typedef 說(shuō)明
模板參數(shù)類型的別名. 在外部需要使用這些類型的時(shí)候使用 .
| key_type | 待檢索的 key 的單個(gè)元素的類型. 等同于 NodeType. |
| result_type | 單個(gè)結(jié)果的類型. 等同于 ArrayType . |
方法說(shuō)明
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)- 構(gòu)建 Double Array .
size 詞典大小 (記錄的詞條數(shù)目),
str 指向各詞條的指針 (共 size個(gè)指針)
len 用于記錄各個(gè)詞條的長(zhǎng)度的數(shù)組(數(shù)組大小為 size)
val 用于保存各詞條對(duì)應(yīng)的 value 的數(shù)組 (數(shù)組大小為 size)
progress_func 構(gòu)建進(jìn)度函數(shù).
str 的各個(gè)元素必須按照字典序排好序.
另外 val 數(shù)組中的元素不能有負(fù)值.
len, val, progress_func 可以省略,
省略的時(shí)候， len 使用 LengthFunc 計(jì)算,
val 的各元素的值為從 0 開(kāi)始的計(jì)數(shù)值。
構(gòu)建成功，返回 0； 失敗的時(shí)候返回值為負(fù).
進(jìn)度函數(shù) progress_func 有兩個(gè)參數(shù).
第一個(gè) size_t 型參數(shù)表示目前已經(jīng)構(gòu)建的詞條數(shù)
第二個(gè) size_t 型參數(shù)表示所有的詞條數(shù)
result_type Darts::DoubleArrayImpl::exactMatchSearch(const key_type *key, size_t len = 0, size_t node_pos = 0)- 進(jìn)行精確匹配(exact match) 檢索, 判斷給定字符串是否為詞典中的詞條.
key 待檢索字符串,
len 字符串長(zhǎng)度,
node_pos 指定從 Double-Array 的哪個(gè)節(jié)點(diǎn)位置開(kāi)始檢索.
len, 和 node_pos 都可以省略, 省略的時(shí)候， len 缺省使用 LengthFunc 計(jì)算,
node_pos 缺省為 root 節(jié)點(diǎn).
檢索成功時(shí)， 返回 key 對(duì)應(yīng)的 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)- 執(zhí)行 common prefix search. 檢索給定字符串的哪些的前綴是詞典中的詞條
key 待檢索字符串,
result 用于保存多個(gè)命中結(jié)果的數(shù)組,
result_size 數(shù)組 result 大小,
len 待檢索字符串長(zhǎng)度,
node_pos 指定從 Double-Array 的哪個(gè)節(jié)點(diǎn)位置開(kāi)始檢索.
len, 和 node_pos 都可以省略, 省略的時(shí)候， len 缺省使用 LengthFunc 計(jì)算,
node_pos 缺省為 root 節(jié)點(diǎn).
函 數(shù)返回命中的詞條個(gè)數(shù). 對(duì)于每個(gè)命中的詞條， 詞條對(duì)應(yīng)的 value 值存依次放在 result 數(shù)組中. 如果命中的詞條個(gè)數(shù)超過(guò) result_size 的大小， 則 result 數(shù)組中只保存 result_size 個(gè)結(jié)果。函數(shù)的返回值為實(shí)際的命中詞條個(gè)數(shù)， 可能超過(guò) 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， 檢索當(dāng)前字符串并記錄檢索后到達(dá)的位置
key 待檢索字符串,
node_pos 指定從 Double-Array 的哪個(gè)節(jié)點(diǎn)位置開(kāi)始檢索.
key_pos 從待檢索字符串的哪個(gè)位置開(kāi)始檢索
len 待檢索字符串長(zhǎng)度,
該函數(shù)和 exactMatchSearch 很相似. traverse 過(guò)程是按照檢索串 key 在 TRIE 的節(jié)點(diǎn)中進(jìn)行轉(zhuǎn)移.
但是函數(shù)執(zhí)行后, 可以獲取到最后到達(dá)的 Trie 節(jié)點(diǎn)位置，最后到達(dá)的字符串位置 . 這和 exactMatchSearch 是有區(qū)別的.
node_pos 通常指定為 root 位置 (0) . 函數(shù)調(diào)用后， node_pos 的值記錄最后到達(dá)的 DoubleArray 節(jié)點(diǎn)位置。
key_pos 通常指定為 0. 函數(shù)調(diào)用后， key_pos 保存最后到達(dá)的字符串 key 中的位置。
檢索失敗的時(shí)候， 返回 -1 或者 -2 .
-1 表示再葉子節(jié)點(diǎn)失敗, -2 表示在中間節(jié)點(diǎn)失敗,.
檢索成功的時(shí)候， 返回 key 對(duì)應(yīng)的 value.
int Darts::DoubleArrayImpl::save(const char *file, const char *mode = "wb", size_t offset = 0)- 把 Double-Array 保存為文件.
file 保存文件名,
mode 文件打開(kāi)模式
offset 保存的文件位置偏移量, 預(yù)留將來(lái)使用， 目前沒(méi)有實(shí)現(xiàn) .
成功返回 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 文件打開(kāi)模式
offset 讀取的文件位置偏移量
size 為 0 的時(shí)候, size 使用文件的大小 .
成功返回 0 ， 失敗返回 -1
size_t Darts::DoubleArrayImpl::size()- 返回 Double-Array 大小.
size_t Darts::DoubleArrayImpl::unit_size()- Double-Array 一個(gè)元素的大小(byte).
size() * unit_size() 是, 存放 Double-Array 所需要的內(nèi)存(byte) 大小.
size_t Darts::DoubleArrayImpl::nonzero_size()- Double-Array 的所有元素中， 被使用的元素的數(shù)目, .
nonezero_size()/size() 用于計(jì)算壓縮率.
例子程序
從靜態(tài)詞典構(gòu)建雙數(shù)組 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");
}
執(zhí)行結(jié)果
1
2
3
4
5
6
-1
從標(biāo)準(zhǔn)輸入讀取字符串, 對(duì) Double-Array 執(zhí)行 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;
}
付屬程序說(shuō)明
mkdarts
% ./mkdarts DictionaryFile DoubleArrayFile
把排序好的詞典 DictionaryFile 轉(zhuǎn)換為 DoubleArrayFiledarts
% ./darts DoubleArrayFile
使用 DoubleArrayFile 做 common prefix search .
使用例子
% cd tests
% head -10 linux.words
ALGOL
ANSI
ARCO
ARPA
ARPANET
ASCII
..
% ../mkdarts linux.words dar
Making Double Array: 100% |*******************************************|
Done!, Compression Ratio: 94.6903 %
% ../darts dar
Linux
Linux: found, num=2 3697 3713
Windows
Windows: not found
LaTeX
LaTeX: found, num=1 3529
參考文獻(xiàn), 鏈接