cc-dict: ハッシュテーブル

C++ library speed size

ハッシュテーブルを実装してみた。
・cc-dict-0.0.3
チェイン法を用いたハッシュテーブルで、リンクリスト(チェイン)のノードを割り当てる際に自前のアロケータを使っている点以外は、特に変わったところもないと思う。

ベンチマーク

一応、ベンチマークも取ったので載せておく。
比較対象はg++のunordered_mapとGoogleのsparse_hash_map及びdense_hash_map。
ベンチマークプログラムにはHash Table Benchmarksに記載のものを使用させてもらった*1。
※ 実行環境は Ubuntu-11.11-64bit / Intel(R) Core(TM) i7 CPU L 620 @ 2.00GHz。

このベンチマーク結果を見る限りは、特別性能が悪い、ということはなさそう*2。

*1:ただし以下の追加・修正を施した。
　1: 検索処理時間の計測の追加
　2: もともとは文字列のベンチマークではキーの型const char*が使用されていたのをstd::stringに変更(関連)
　3: 処理時間にキー配列を生成する時間も含まれていたので、キー配列は最初にまとめて生成しておき、その後から計時を開始するように修正

*2:ベンチマークデータが結構恣意的(連番 or 乱数)なので、必ずしも実データで同様の性能がでるかは分からないけど・・・

std::tr1::unordered_mapのキーの型をconst char*にした場合の挙動

C++

g++(及びその他)のunordered_mapで文字列をキーにしたい場合の注意書き。
unordered_mapのようにconst char*を指定すると、キーが文字列ではなくポインタ(整数値)として解釈されてしまう*1。
以下、その際の挙動の確認用のコード:

/**
 * ファイル名: str_map.cc
 * コンパイル: g++ -o str_map str_map.cc
 * gcc-4.6.1
 */
#include <string>
#include <cstring>
#include <tr1/unordered_map>
#include <iostream>

int main() {
  // ハッシュマップ作成
  std::tr1::unordered_map<const char*, int> cstr_map;  // const char*用
  std::tr1::unordered_map<std::string, int> str_map;   // std::string用
  
  // キーを用意
  char key1[] = "abc";
  char* key2 = new char[4];
  strcpy(key2, "abc");
  
  // キーの値とアドレスを出力
  std::cout << std::endl << "--" << std::endl;
  std::cout << "key1: '" << key1 << "' (addr: " << (long)(key1) << ")" << std::endl;
  std::cout << "key2: '" << key2 << "' (addr: " << (long)(key2) << ")" << std::endl;
  
  // key1を要素挿入
  cstr_map[key1] = 10;
  str_map[key1] = 10;

  // key1とkey2を検索
  std::cout << std::endl << "--" << std::endl;
  std::cout << "cstr_map: key1=" << cstr_map[key1] << ", key2=" << cstr_map[key2] << std::endl;
  std::cout << " str_map: key1=" << str_map[key1] << ", key2=" << str_map[key2] << std::endl;

  // key1の値を変えてみる
  key1[1] = '2';  // key1 = "a2c"

  // key1を検索
  std::cout << std::endl << "--" << std::endl;
  std::cout << "key1: '" << key1 << "' (addr: " << (long)(key1) << ")" << std::endl;
  std::cout << "cstr_map: key1=" << cstr_map[key1] << std::endl;
  std::cout << " str_map: key1=" << str_map[key1] << std::endl;    
  return 0;
}

実行結果:

--
key1: 'abc' (addr: 140736322707456)  # key1とkey2は同じ文字列だけど、アドレスは異なる
key2: 'abc' (addr: 30732528)

--
cstr_map: key1=10, key2=0   # key1のみヒット
 str_map: key1=10, key2=10  # key1とkey2の両方にヒット

--
key1: 'a2c' (addr: 140736035469872)
cstr_map: key1=10           # ヒット(ポインタ値が同じなため)
 str_map: key1=0            # ヒットしない(文字列が変わっているため)

分かってみれば、これはこれで自然な動作なので特に違和感もないけど、最近はC++がご無沙汰だったためか(文字列ではなくポインタ値として扱われていることに)すぐに気づかずに少しはまってしまった。

*1:もちろん const char* 用に自前で定義したハッシュ関数と比較関数をテンプレート引数に渡してあげれば特に問題はない(はず)

フィールドのポインタから、オブジェクト全体のポインタを取得するためのマクロ

C++ utility

構造体やクラスのインスタンスの特定のフィールドのアドレス(ポインタ)だけ分かっている場合に、そこからオブジェクト全体のポインタを取得したい場合に使うマクロ。
やっていることは単にフィールドのアドレスから、そのフィールドの(クラスor構造体の)先頭からのオフセットを引いているだけ。

// type.fieldが、typeの先頭の何バイト目に配置されているかを求める
#define field_offset(type, field) \
  ((char*)&(((type*)NULL)->field) - (char*)NULL)

// type.filedのアドレス(field_ptr)から、fieldのオフセット分マイナスし、typeのアドレスを求める
#define obj_ptr(type, field, field_ptr) \
  ((type*)((char*)field_ptr - field_offset(type, field)))

メモリアロケータを自作する際に、割当メモリ領域にタグ付けするのに利用できそうだと思い作成。

/* main.cc */
#include <iostream>

// タグ付きメモリチャンク
struct chunk {
  struct {            // タグ情報:
    const char* type; // - 型名
    int size;         // - サイズ
  } tag;
  void* buf;
};

// メモリ割り当て
inline void* mem_allocate(const char* type, int size) {
  chunk* c = (chunk*)new char[sizeof(chunk::tag)+size];

  // タグ情報を保存する
  c->tag.type = type;
  c->tag.size = size;

  std::cout << "[" << c->tag.type << "] allocate: " << c->tag.size << " bytes" << std::endl;

  // 割り当てアドレスを返す
  return &c->buf;
}

// メモリ解放
void mem_free(void* p) {
  // 解放するアドレス(chunk::buf)から、タグ情報(chunk)を取得する
  chunk* c = obj_ptr(chunk, buf, p);
  std::cout << "[" << c->tag.type << "] free: " << c->tag.size << " bytes" << std::endl;
  delete c;
}

struct abc {
  int a;
  char b;
  long c;
};

// main関数
int main() {
  void* ptrs[3];

  std::cout << "# allocate:" << std::endl;
  ptrs[0] = new (mem_allocate("int", sizeof(int))) int;
  ptrs[1] = new (mem_allocate("pointer", sizeof(void*))) void*;
  ptrs[2] = new (mem_allocate("struct", sizeof(abc))) abc;
  
  std::cout << std::endl;
  std::cout << "# free:" << std::endl;
  for(int i=2; i >=0; i--)
    mem_free(ptrs[i]);

  return 0;
}

$ g++ -o main main.cc
$ ./main
# allocate:
[int] allocate: 4 bytes
[pointer] allocate: 8 bytes
[struct] allocate: 16 bytes

# free:
[struct] free: 16 bytes
[pointer] free: 8 bytes
[int] free: 4 bytes

Sanmoku(0.0.5): 原型や読みの情報取得に対応

Java library

Sanmoku(0.0.4): 辞書データサイズ縮小のコメントにて要望があったのでSanmokuを形態素の原型や読みの情報取得に対応させてみた。
Sanmoku本体のインターフェースは以前の同様*1で、原型・読み・発音の取得を行うためのFeatureExクラス(sanmoku-feature-ex-x.x.x.jar)を新しく追加した。

使用例:

import net.reduls.sanmoku.Tagger;
import net.reduls.sanmoku.Morpheme;
import net.reduls.sanmoku.FeatureEx; // 追加

for(Morpheme m : Tagger.parse("...")) {  // 形態素解析
  FeatureEx fe = new FeatureEx(m);       // 解析結果の形態素インスタンスから、追加の素性データを取得

  // 結果表示
  System.out.println(m.surface+"\t"+m.feature+","+fe.baseform+","+fe.reading+","+fe.pronunciation);
}

$ export CLASSPATH=sanmoku-0.0.5.jar:sanmoku-feature-ex-0.0.1.jar
$ echo '招待制でリリースしました' | java net.reduls.sanmoku.bin.SanmokuFeatureEx
招待	名詞,サ変接続,*,*,*,*,招待,ショウタイ,ショータイ
制	名詞,接尾,一般,*,*,*,制,セイ,セイ
で	助詞,格助詞,一般,*,*,*,で,デ,デ
リリース	名詞,サ変接続,*,*,*,*,リリース,リリース,リリース
し	動詞,自立,*,*,サ変・スル,連用形,する,シ,シ
まし	助動詞,*,*,*,特殊・マス,連用形,ます,マシ,マシ
た	助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
EOS

比較

以前の表にSanmoku-0.0.5(+ FeatureEx-0.0.1)を追加したもの。

　 辞書データサイズ(IPADIC) 最小所要メモリ(-Xmx) 起動(≒辞書ロード)時間*2 10MBテキストの解析時間
Igo-0.4.3 40MB 73MB 0.058秒 2.729秒
Gomoku-0.0.4 8.2MB 23MB 0.371秒 2.621秒
Sanmoku-0.0.4 4.8MB 2MB 0.057秒 5.807秒
Sanmoku-0.0.5(+ FeatureEx-0.0.1) 10MB 11MB 0.098秒 6.814秒

読み等の情報を取得した場合、性能は全体的に劣化しているけど、これくらいなら十分許容範囲内のような気がする。

*1:内部的にはMorphemeクラスが形態素IDを保持するように修正されている

*2:JVM自体の起動時間は除いた数値

UNF-0.0.4: サイズ削減

C++ size library

今日は久しぶりにUNF(ユニコード正規化ライブラリ)に手を加えていた。
大きな変更点は、正規化用変換テーブルを実現していたTRIEをDAWGにしたこと。
もともとは正規分解と互換分解用に、内容がほぼ等しいTRIEを別々に持っていたので、それを一つDAWGにして共有することでだいぶサイズが節約できた。

# unf-0.0.3
$ ls -lh unf-0.0.3/bin/unf
-rwxrwxr-x 1 user user 596K 2011-11-19 17:54 unf-0.0.3/bin/unf  # 596KB

# unf-0.0.4
$ ls -lh unf-0.0.4/bin/unf
-rwxrwxr-x 1 user user 411K 2011-11-19 20:20 unf-0.0.4/bin/unf  # 411KB

処理速度も、ごく僅かだけど新しいバージョンの方が速くなっているように見える。

# 17MBのテキストデータの正規化時間

# unf-0.0.3
$ unf-0.0.3/bin/unf-time < 17MB.txt 
= read: 
  == 172090 lines
  == average(line length): 99 byte
= time: 
  == NFD :  0.203354 sec
  == NFC :  0.109814 sec
  == NFKD:  0.215196 sec
  == NFKC:  0.137385 sec
DONE

# unf-0.0.4
$ unf-0.0.4/bin/unf-time < 17MB.txt 
= read: 
  == 172090 lines
  == average(line length): 99 byte
= time: 
  == NFD :  0.199866 sec
  == NFC :  0.104912 sec
  == NFKD:  0.206675 sec
  == NFKC:  0.137277 sec
DONE

Sanmoku(0.0.4): 辞書データサイズ縮小

Java library

この一週間でSanmokuの辞書データサイズの縮小をいろいろ試していたので、その結果を載せておく。
現時点でのバージョンは 0.0.4。

やったこと

試した主なこと。

データ 内容 サイズ
(Gomoku-0.0.4 => Sanmoku-0.0.4)
連接コストデータ
(matrix.bin)		 類似品詞の連接コストを併合*1 + コスト値を14bitで保持 3.5MB => 2.2MB
形態素辞書引きインデックス
(surface-id.bin)		 2バイト文字(UTF-16)DAWGから、1バイト文字(UTF-8)DAWGに変更。
かつIPADICに合わせてノードレイアウトを最適化		 2.7MB => 1.5MB
形態素データ
(morpheme.bin,id-morphems-map.bin)		 4バイト(品詞情報:2バイト、単語コスト:2バイト)から2バイトに 1.8MB => 1.0MB

比較

IgoとGomokuとSanmokuの比較。

　 辞書データサイズ(IPADIC) 最小所要メモリ(-Xmx) 起動(≒辞書ロード)時間*2 10MBテキストの解析時間
Igo-0.4.3 40MB 73MB 0.058秒 2.729秒
Gomoku-0.0.4 8.2MB 23MB 0.371秒 2.621秒
Sanmoku-0.0.4 4.8MB 2MB 0.057秒 5.807秒

Sanmokuは所要メモリや辞書ロード時間が短いが、辞書データを圧縮するためにビット演算や間接参照等を多用しているため、解析速度は他に比べて二倍以上遅くなっている。
Igoは辞書データサイズ自体は大きいが、mmap(java.nio.MappedByteBuffer)を利用しているため、ロード時間は高速となっている。

*1:このためSanmokuは、若干(Gomokuに比べ1%にも満たない程度だが)解析精度が落ちている。

*2:JVM自体の起動時間は除いた数値

Sanmoku: 省メモリな形態素解析器

Java library

GomokuをベースにしたSanmokuという形態素解析器を実装した。
Gomokuに比べて解析時に必要なメモリ量が少ないのと初期ロード時間が短いのが特徴。
将来的には解析精度を若干落として、辞書サイズ*1をさらに削減する可能性もあるけど、現状は解析結果はGomoku互換。
Android等のリソースの制限が厳しい環境での使用を想定。

最低メモリ所要量とロード時間

以下、自分の環境*2での計測結果。

## 最低メモリ所要量
# Gomoku(0.0.4)は 26MBのメモリが必要
$ java -Xmx26m -cp gomoku-0.0.4.jar net.reduls.gomoku.bin.Gomoku < /path/to/natsume-soseki.txt > /dev/null

# Sanmoku(0.0.1)は 11MBのメモリが必要
$ java -Xmx11m -cp sanmoku-0.0.1.jar net.reduls.sanmoku.bin.Sanmoku < /path/to/natsume-soseki.txt > /dev/null


## ロード時間
# Gomoku(0.0.4)は 0.633秒 (内 0.094秒はJVM起動時間)
time echo 'a' | java -Xmx26m -cp gomoku-0.0.4.jar net.reduls.gomoku.bin.Gomoku
a	名詞,固有名詞,組織,*,*,*
EOS

real	0m0.633s
user	0m0.808s
sys	0m0.044s

# Sanmoku(0.0.1)は 0.217秒 (内 0.094秒はJVM起動時間)
time echo 'a' | java -Xmx11m -cp sanmoku-0.0.1.jar net.reduls.sanmoku.bin.Sanmoku 
a	名詞,固有名詞,組織,*,*,*
EOS

real	0m0.217s
user	0m0.244s
sys	0m0.024s

Android

https://github.com/sile/sanmoku/downloads に Sanmoku-0.0.1.apk という名前でサンプルAndroidアプリを配置。
自分の環境(HTC EVO WiMAX ISW11HT)でしか動作確認していないので、他のスマートフォンで正常に動くかどうかは不明。

辞書ロード時間は、Gomokuに比べるとだいぶ短縮されてはいるが、それでも一番初めの解析が始まるまで、現状では数秒程度の時間を要する。

*1:現状はJAR展開時で7.6MB

*2:Linxu, x86-64bit