読者です 読者をやめる 読者になる 読者になる

LOUDS++(7): trie - 比較

C++ algorithm

七回目。多分最後。

これまで作ってきたものを他のtrie実装と比較する。

比較対象

  • louds-trie: LOUDS++によるtrieの実装。五回目を参照
  • louds-trie-tail: LOUDS++によるtrie(TAIL配列/圧縮有)の実装。六回目を参照
  • doar-0.0.12: DoubleArray(TAIL配列/圧縮有)によるtrieの実装。まだunstable
  • tx-0.13: LOUDSによるtrieの実装。詳細不明。louds-trieに比べてbit-vectorの実装が省サイズ(1.3Nビットくらい?)
  • darts-32: DoubleArray(TAIL配列無)によるtrieの実装。詳細不明

比較内容

以下の二つの項目の比較を行う。

  • trie用のバイナリデータのサイズ
  • キー検索速度

データ

比較に用いるtrieのキーセットとしては、Wikipediaのタイトルを利用することにする。
以下、取得/作成手順。

# /tmp/に移動
$ cd /tmp

# Wikipediaのタイトルリストをダウンロード
$ wget http://download.wikimedia.org/jawiki/20100607/jawiki-20100607-all-titles-in-ns0.gz
$ wget http://download.wikimedia.org/euwiki/20100612/euwiki-20100612-all-titles-in-ns0.gz
$ wget http://download.wikimedia.org/zhwiki/20100612/zhwiki-20100612-all-titles-in-ns0.gz
$ wget http://download.wikimedia.org/fiwiki/20100620/fiwiki-20100620-all-titles-in-ns0.gz
$ wget http://download.wikimedia.org/frwiki/20100614/frwiki-20100614-all-titles-in-ns0.gz
$ wget http://download.wikimedia.org/svwiki/20100620/svwiki-20100620-all-titles-in-ns0.gz
$ wget http://download.wikimedia.org/trwiki/20100620/trwiki-20100620-all-titles-in-ns0.gz
$ wget http://download.wikimedia.org/hewiki/20100620/hewiki-20100620-all-titles-in-ns0.gz
$ wget http://download.wikimedia.org/nowiki/20100619/nowiki-20100619-all-titles-in-ns0.gz
$ wget http://download.wikimedia.org/cawiki/20100619/cawiki-20100619-all-titles-in-ns0.gz
$ gzip -d *-ns0.gz

# ソート & ユニーク
$ cat *-ns0 | LC_ALL=C sort | LC_ALL=C uniq > wiki.title  # wiki.titleという名前でキーセットを保存

# 行数
$ wc -l wiki.title
5340378 wiki.title   # 約500万行

# サイズ
$ ls -lh wiki.title
-rw-r--r-- 1 user user 103M 2010-06-20 21:22 wiki.title  


検索用データには、'wiki.title'をランダムに並び替えたものを用いる。※ このため検索は常に成功となる

# ファイル名: shuffle.rb
#
# 引数で指定されたファイルの各行をランダムに並び替えて出力する
titles = open(ARGV[0]).read.split("\n")

def swap(ary, x, y)
  tmp = ary[x]; ary[x] = ary[y]; ary[y] = tmp
end

titles.size.times {|i| swap(titles, i, rand(titles.size)) }

puts titles.join("\n")
# wiki.titleをランダムに並び替える
$ ruby shuffle.rb wiki.title > wiki.title.rand

構築/検索方法

各trieのデータの作成/検索方法。
検索用のコマンドに関しては、末尾の「比較用検索プログラム」を参照のこと。

$ echo $PWD
/tmp

# louds-trie
$ mklouds-trie wiki.title louds-trie.idx       # 作成
$ cklouds-trie louds-trie.idx wiki.title.rand  # 検索

# louds-trie-tail
$ mklouds-trie-tail wiki.title louds-trie-tail.idx       # 作成
$ cklouds-trie-tail louds-trie-tail.idx wiki.title.rand  # 検索

# doar 
$ mkdoar --conc-static doar.idx wiki.title  # 作成
$ ckdoar doar.idx wiki.title.rand           # 検索

# tx
$ txbuild wiki.title tx.idx    # 作成
$ cktx tx.idx wiki.title.rand  # 検索

# darts
$ mkdarts wiki.title darts.idx       # 作成
$ ckdarts darts.idx wiki.title.rand  # 検索

結果

データサイズ検索所要時間(秒)
louds-trie74MB32.1372s
louds-trie-tail52MB17.0782s
doar94MB*13.19229s
tx67MB51.556s
darts416MB3.35106s
サイズ的にはlouds-trie-tailが、検索速度的にはdoarおよびdartsが最も優れていた。
※ ただし、条件を厳密に合わせている訳ではないので、あまり正確なことは云えない
LOUDSを利用したtrie実装は、やはりDoubleArrayのそれよりも検索が低速だった(漠然と予想していた程ではなかったけど)
ただlouds-trie-tail(及びlouds-trie)の検索メソッド周りはまだ改良の余地があると思うので、もし今後の改良*2によって、DoubleArray版の三倍程度(の遅さ)にまで差を縮めることができたら、LOUDS(LOUDS++)によるtrie実装の、サイズと検索速度のトレードオフは結構リーズナブルなものになるのではないか、と思う。

比較用検索プログラム

キー検索用の各プログラム。
ckdoarに関しては、doarビルド時に作成されるコマンドを用いた。※ 他のコマンドの命名規則は、これに合わせた

参照: read_line.h, gettime関数


cklouds-trie:

/***
 * ファイル名: cklouds-trie.cc
 * コンパイル: g++ -O3 -o cklouds-trie cklouds-trie.cc
 */
#include <iostream>
#include "louds_trie.h"
#include "read_line.h"
#include "gettime.h"

int main(int argc, char** argv) {
  LoudsTrie lt(fopen(argv[1],"rb"));
  ReadLine rl(argv[2]);
  
  double beg_t = gettime();
  unsigned err = 0;
  unsigned cnt = 0;
  const char* line;
  
  while((line=rl.read())) {
    cnt++;
    if(lt.find(line) == lt.NOT_FOUND)
      err++;
  }

  std::cerr << "Not Found: " << err << "/" << cnt << std::endl;
  std::cerr << "Elapsed: " << gettime()-beg_t << " sec" << std::endl << std::endl;
  std::cerr << "DONE" << std::endl;

  return 0;
}


cklouds-trie-tail:

/***
 * ファイル名: cklouds-trie-tail.cc
 * コンパイル: g++ -O3 -o cklouds-trie-tail cklouds-trie-tail.cc
 */
#include <iostream>
#include "louds_trie_tail.h"
#include "read_line.h"
#include "gettime.h"

int main(int argc, char** argv) {
  LoudsTrieTail lt(fopen(argv[1],"rb"));
  ReadLine rl(argv[2]);
  
  double beg_t = gettime();
  unsigned err = 0;
  unsigned cnt = 0;
  const char* line;
  
  while((line=rl.read())) {
    cnt++;
    if(lt.find(line) == lt.NOT_FOUND)
      err++;
  }

  std::cerr << "Not Found: " << err << "/" << cnt << std::endl;
  std::cerr << "Elapsed: " << gettime()-beg_t << " sec" << std::endl << std::endl;
  std::cerr << "DONE" << std::endl;

  return 0;
}


cktx:

/***
 * ファイル名: cktx.cc
 * コンパイル: libtool --mode=link g++ -O3 -o cktx cktx.cc libtx.la
 * ※ あらかじめtxのソースをダウンロードし、ビルドしておくこと
 */
#include <iostream>
#include "tx.hpp"
#include "read_line.h"
#include "gettime.h"

int main(int argc, char** argv) {
  tx_tool::tx t;
  t.read(argv[1]);
  ReadLine rl(argv[2]);
  
  double beg_t = gettime();
  unsigned err = 0;
  unsigned cnt = 0;
  const char* line;
  
  while((line=rl.read())) {
    cnt++;
    unsigned retlen;
    if(t.prefixSearch(line,strlen(line),retlen) == t.NOTFOUND)
      err++;
  }

  std::cerr << "Not Found: " << err << "/" << cnt << std::endl;
  std::cerr << "Elapsed: " << gettime()-beg_t << " sec" << std::endl << std::endl;
  std::cerr << "DONE" << std::endl;

  return 0;
}


ckdarts:

/***
 * ファイル名: ckdarts.cc
 * コンパイル: g++ -O3 -o ckdarts ckdarts.cc
 * ※ あらかじめdartsのソースをダウンロードし、解凍しておくこと
 */
#include <iostream>
#include "darts.h"
#include "read_line.h"
#include "gettime.h"

int main(int argc, char** argv) {
  Darts::DoubleArray da;
  da.open(argv[1]);
  ReadLine rl(argv[2]);
  
  double beg_t = gettime();
  unsigned err = 0;
  unsigned cnt = 0;
  const char* line;
  
  while((line=rl.read())) {
    cnt++;
    if(da.exactMatchSearch<int>(line) == -1)
      err++;
  }

  std::cerr << "Not Found: " << err << "/" << cnt << std::endl;
  std::cerr << "Elapsed: " << gettime()-beg_t << " sec" << std::endl << std::endl;
  std::cerr << "DONE" << std::endl;

  return 0;
}

*1:追記(2010/06/24): これは76MBまで減らすことが可能

*2:その予定は今のところないけど