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;
};

模板參數說明

 

NodeTypeTrie 節點類型， 對普通的 C 字符串檢索， 設置為 char 型即可.
NodeUTypeTrie 節點轉為無符號整數的類型, 對普通的 C 字符串檢索， 設置為 unsigned char 型即可.
ArrayTypeDouble-Array 的 Base 元素使用的類型, 通常設置為有符號 32bit 整數
ArrayUTypeDouble-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");
}

執行結果
1
2
3
4
5
6
-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.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

參考文獻, 鏈接