txの最新のソースコードやドキュメントは現在google codeで管理されています。下記内容は2009年4月までの古い内容なので注意してください（順次移行していきます）。

Tx: Succinct Trie Data structure

English

概要

TxはコンパクトなTrieを構築するためのライブラリです．従来のTrieの実装（darts等）に比べ1/4〜1/10の作業領域量で辞書を保持することができ、数億〜十億キーワードなど大規模な辞書を扱うことが可能です．Trieは文字列からなるキー集合を処理するデータ構造で、キーが辞書に含まれているかのみではなく、キーのPrefixが含まれているかを高速に求めることができます．内部データ構造にはSuccinct Data StructureであるLevel-Order Unary Degree Sequence (LOUDS)を利用しています．

ダウンロード

Txはフリーソフトウェアです．BSD ライセンスに従って本ソフトウェアを使用,再配布することができます.

Archives

更新情報

使い方

ソースコードで配布しています。configure; make; make install して使ってください。

ライブラリのみ使いたい場合は./configure; make; sudo make installして#include をプログラムにつけ-ltxオプションをつけてコンパイルしてください。

Txは各行に1つずつキーが書かれたファイルを読み込み、辞書を構築しindexに保存します。利用するときはindexから読み込み、prefixMatchまたはexpandMatch呼び出します。

ライブラリとして使う例は、txbuild.cpp txsearch.cppを参照してください．

サンプルプログラムの説明

txbuild

% ./txbuild wordlist index
各行に一キーが書かれたファイルからTx用の辞書を構築しindexに保存します．

txsearch

% ./txsearch index

辞書をindexから読み込み対話的に common prefix search を行います.

txsearch_mmap

% ./txsearch_mmap index

txserachと同様ですが、読み込む際に内部でメモリは確保せずにmmapを行います．

s2sbuild

% ./s2sbuild word2wordlist index

各行にtabで区切られた二つのキーワードが書かれたファイルから1列目のキーワードから2列目のキーワードへのマッピング用の辞書を構築し，index.1 index.2 index.12に保存します．index.1 index.2がそれぞれ1列目, 2列目のキーワードに対応するtx辞書であり，index.12が1から2へのマッピングテーブルです．

s2sserach

% ./s2ssearch index

s2sbuildで構築された辞書をindexから読み込み対話的に1列目のキーワードを入力として受け取り，全ての部分文字列に対しcommon prefix searchを行い，対応する2列目のキーワードリストを表示します．

使用例

% head  wikipedia_titlelist
吉祥寺
改築
三越
円
なお
高い
定休
ファン
精肉
砂
..
% ./txbuild wikipedia_titlelist index
word list 682496 elements
outputSize:6790788 inputSize:9957698 ratio:68.20
% ./txsearch index
>東京
prefixSearch id:118049 len:6
expansionSearch 11
東
東京
東京03
東京bbs
東京jap
東京r&d
東京人
東京国
東京大
東京市
東京府
commonPrefixSearch 2
東 (id=11298)
東京 (id=118049)
predictiveSearch 10
東京 (id=118049)
東京03 (id=206482)
東京bbs (id=270748)
東京jap (id=270749)
東京r&d (id=270750)
東京人 (id=270751)
東京国 (id=270752)
東京大 (id=270753)
東京市 (id=270754)
東京府 (id=270755)

(最初に表示される elemNumはキーの数、nodeNumはtrie中のnodeの数です）

% ./head yomi2hyoki
ーーー  ○ー○ー○ー○
ーーー  ○ー○。
ぁ      （ぁ
ぁみにぃ        ぁみにぃ
ぁみみ  ぁみみ
ぁゃゃ  ぁゃゃ
あ      「あ」
あ      媚理
あーう゛ぇう゛ぇ        a.v.v
あーうーおじゃままん    アーウー・オジャママン
あーういんしょう        アーウィン・ショウ
あーえすもなこ  ASモナコ
あーえぬあーまいれーじくらぶ    ANAマイレージクラブ
あーかーげー    AKG
あーかーと      アーカート
あーかーど      アーカード
あーかーよんなな        ＡＫ４７
あーかいう゛    アーカイヴ
あーかいば      アーカイバ
あーかいぶ      アーカイブ

% ./s2sbuild yomi2hyoki y2hindex

% ./s2ssearch y2hindex
keyNum:174496 nodeNum:1620383
keyNum:195576 nodeNum:1530718
>どらごんくえすと
どらご  ドラゴ
どらごん        ドラゴン doragon dragon
どらごんくえすと        ドラゴンクエスト ドラゴン・クエスト Dragon Quest ドラゴンクエスト
らごん  ラゴン
ごん    GON!
く      クモハ313
くえすと        クエスト クエスト
えす    E’S 「Ｓ」 SP-NX502 es [es] es Es
すと    「スト」

メソッドの説明

int tx_tool::tx::build(vector<string>& wordList, const char* fileName) const
wordListを元にTxを構築しfileNameで指定されたファイルに保存します．このメソッドは構築して保存するだけであり，すぐ使いたい場合は，続いてreadを呼び出す必要があります．
wordListには保存したいキー集合入れます．必ずしもソートされている必要はありません。重複キーは構築時取り除かれます。
fileNameには保存先のファイル名を入れます．既にそのファイルがある場合はそのファイルは破壊されます．

int tx_tool::tx::read(const char* fileName)
TxをfileNameから読み込みます．失敗した場合は-1が返ります．

tx_tool::uint tx_tool::tx::prefixSearch(const char* str, const size_t len, size_t& retLen) const;
strに対し，そのprefixで最も長く一致したキーがある場合はそのキー固有の番号，一つも見つからない場合はtx_tool::NOTFOUNDを返します．retLenに一致したprefix長を返します．
キー固有の番号は登録したキー全てに0から順に番号が割り振られてます（必ずしも登録順とは一致しない）．

tx_tool::uint tx_tool::tx::expandSearch(const char* str, const size_t len, vector<string>& ret, const size_t limit= TX_LIMIT_DEFAULT) const;
strに対し，そのprefixにマッチするキー，また，そのstrをprefixとして持つキー全てをretに入れて返します．commonPrefixSearchとpredictiveSearchの和集合が返されます．返り値はretに入った要素数です。limitを指定した場合，短いキー順に最大limitの個数だけ返されます．

tx_tool::uint tx_tool::tx:commonPrefixSearch(const char* str, const size_t len, std::vector<std::string>& ret, std::vector<uint>& retID, const uint limit = TX_LIMIT_DEFAULT) const;
strに対し，そのprefixにマッチする全てのキーをretに入れて，retIDにそれらのキー固有の番号を返します．返り値はretに入った要素数です。limitを指定した場合，短いキー順に最大limitの個数だけ返されます．

tx_tool::uint tx_tool::tx:commonPrefixSearch(const char* str, const size_t len, std::vector<uint>& retLen, std::vector<uint>& retID, const uint limit = TX_LIMIT_DEFAULT) const;
strに対し，そのprefixにマッチする全てのキー長をretLenに入れて，retIDにそれらのキー固有の番号を返します．返り値はretに入った要素数です。limitを指定した場合，短いキー順に最大limitの個数だけ返されます．

tx_tool::uint tx_tool::tx:predictiveSearch(const char* str, const size_t len, std::vector<std::string>& ret, std::vector<uint>& retID, const uint limit = TX_LIMIT_DEFAULT) const;
strに対し，そのstrをprefixとして持つキー全てをretに入れて，retIDにそれらのキー固有の番号を返します．返り値はretに入った要素数です。limitを指定した場合，短いキー順に最大limitの個数だけ返されます．

tx_tool::uint tx_tool::tx:predictiveSearch(const char* str, const size_t len, std::vector<uint>& retLen, std::vector<uint>& retID, const uint limit = TX_LIMIT_DEFAULT) const;
strに対し，そのstrをprefixとして持つキー長をretLenに入れて，retIDにそれらのキー固有の番号を返します．返り値はretに入った要素数です。limitを指定した場合，短いキー順に最大limitの個数だけ返されます．

tx_tool::uint tx_tool::tx:reverseLookup(const tx_tool::uint id, std::string& ret) const;
prefixSearchなどで得られたtx固有のidからキーを復元し，retに返します．返り値はキー長です。無効なidを入力した場合はretには空文字列，長さは0が返されます．

string tx_tool::tx::getResultLog();
構築時、読み込み時の詳細情報をstringで返します．

string tx_tool::tx::getErrorLog();
構築時、読み込み時に発生したエラーの詳細情報をstringで返します．

string tx_tool::tx::getKeyNum();
登録されているキーの数を返します．

string tx_tool::tx::setArray(void* ptr, size_t readSize);
ptrを読み込み用の入力ファイルとみなし，read()と同様にインデクスを読み込みます．mmapなどを使いたい場合にはread()の代わりにこれを利用してください．利用方法については添付のtxsearch_mmap.cppを参照してください．

TX_LIMIT_DEFAULTは0xffffffff（符号無し32bit整数の最大値）です。

性能評価

インデクス構築時間とサイズ

入力データ

インデクスサイズ（入力サイズ比）構築時のtime結果
tx 0.02 (txbuild)52,626,805 (46.8%)30.581u 1.137s 3:50.95 13.7%
darts 0.31 (mkdarts) 406,358,432 (361.7%)16.688u 1.785s 8:13.52 3.7%

検索処理時間

入力データと評価方法

一回あたりの時間(micro-second) *1
tx 0.0210.8
std::map<std::string,int> 4.06
darts 0.31 1.05
std::tr1::unordered_map<std::string,int> 0.63
*1 clock()で計測。gettimeofdayの結果もほぼ同じでした。

TODO

その他

つくばエクスプレス(tx)の行き帰りで作ったので、その名前がついています。

謝辞

ライブラリ作成などでkzkさんに協力していただきました．またtakuさんから有益なコメントをいただきました．
ありがとうございます．

参考文献, リンク

連絡先

コメントやバグ報告などありましたらこちらまで
Daisuke Okanohara (hillbig ＠ is.s.u-tokyo.ac.jp) (全角＠を半角@に直してください）