Micterの単語分割部の高速化を試してみた結果

tkngさんが作成したMicterという単語分割器の分割部を高速化できるような気がしたので試してみた。
そのメモ。

試した結果のソース一式はmimicという名前でgithubに保存しておくことにする*1。

結果

まず、結果から*2。

# 分割対象のテキスト(のサイズ)
$ ls -lh /tmp/test.data
-rw-r--r-- 1 user user 41M 2010-07-05 22:48 /tmp/test.data

# MeCab
$ time mecab -Owakati /tmp/test.data > /dev/null
real	0m10.843s  # 10秒
user	0m10.777s
sys	0m0.068s

# Micter
$ ls -lh micter.model
-rw-r--r-- 1 user user 1.8M 2010-07-06 08:30 micter.model

$ time micter -m micter.model < /tmp/test.data > /dev/null
real	0m31.283s  # 31秒
user	0m31.198s
sys	0m0.088s

# mimic
$ ls -lh mimic.index
-rw-r--r-- 1 user user 4.0M 2010-07-06 07:59 mimic.index  # DoubleArrayインデックス + α

$ time ./mimic-split mimic.idx /tmp/test.data > /dev/null
real	0m3.980s  # 4秒
user	0m3.908s
sys	0m0.072s

条件を全く合わせていないし、計時に用いたデータの情報もオープンにしていないので、細かい点に関しては全く参考にならない数値だが、おおまかにmimicがMeCabよりも高速に単語分割が行えていることは分かる。
高速化は成功。

修正点

mimicがMicterに対して何を修正したか。
基本的には、分割時に分割可否の判断を行うために必要な、素性群を取り出す方法を変えただけ*3。

Micterでの単語分割処理を擬似コードで記すと(多分)以下のようになる。
※ かなり単純化している。ちゃんと知りたい人は、(当たり前だけど)オリジナルのソースコードを参照のこと。

# Ruby風
#
# 入力文字列の各文字位置で、素性群を取り出し、スコアを算出し、分割するかどうかを決定

def word_split(line)  # lineは文字列  ※バイト列ではい
  line.length.times do |i|
    fs = get_feature_list(line, i)         # 位置iの素性群を取得する
    score=0; fs.each{|f| score += f.score} # 各素性のスコア(?)の合計を求める
    if score >= 0.0                        # 0.0以上なら、ここで分割を行う
      # 分割!
    end
  end
end

# 位置iに紐付く素性群を取得する
def get_feature_list(line, i)
  ary = Array.new
  ary += get_unigram_feature_list(line, i)           # 一文字素性を取り出して、配列に追加 
  ary += get_bigram_feature_list(line, i)            # 二文字素性を取り出して、配列に追加
  ary += get_trigram_feature_list(line, i)           # 三文字素性を取り出して、配列に追加
  ary += get_char_type_bigram_feature_list(line, i)  # 文字カテゴリ素性を取り出して、配列に追加
  return ary
end

def get_bigram_feature_list(line, i)
  word = line[i,2]               # 現在位置のバイグラム取得
  feature = feature_table[word]  # 素性取得   ※ feature_tableはハッシュ
  return [feature]
end

対して、mimic。
※ こっちもかなり単純化している

## 前処理
# 各素性(Nグラム文字列)のスコアを格納したDoubleArrayインデックスを読み込む
#   トライのキー: 素性文字列
#   トライの値　: 素性の分割スコア 
TRIE = DoubleArrayTrie.load "モデルデータのパス"   

def word_split(line)
  score_array = (0..line.length-1).to_a.map{|i| 0.0}

  line.length.times do |i|
    # 入力文字列の全位置に対して、common-prefix-search(素性文字列の検索)を行う
    TRIE.common_prefix_search(line, i) do |match_pos, score|
      score_array[match_pos] += score   # マッチした場合は、その文字位置の分割スコアを修正する
    end
  end

  line.length.times do |i|
    if score_array[i] >= 0.0
      # 分割!
    end
  end
end

学習時に取得した全素性(文字列)をDoubleArrayに登録してしておき、分割時にはそれを用いて入力文字列の各位置でcommon-prefix-searchを行うだけで、分割のためのスコアが算出可能なので高速、というわけ。

注意

mimicは分割部の実装を簡潔にするために、学習部もMicterのものから若干変更している。
そのため、mimicの分割結果はMicterのそれとは同一ではなく、分割精度が劣化している可能性もある。

あと、あくまでも高速化案を試すことが目的だったので実装はテキトウ*4、かつ、今後の改善の予定もなし。

追記(2010/07/06)

ちなみに、僕の環境ではテンプレート周りでエラーが発生してしまい、Micterのビルドが出来なかった。
util.hppに以下のコードを追加したら、(原因は不明だが)一応解決した。

namespace std {
  namespace tr1 {
    
    template<class T>
    struct hash {
    };
    
    template <>
    struct hash<feature> : public std::unary_function<feature, std::size_t>
    {
      // これはfeature_hash構造体の、operator()メソッドと同じ内容
      size_t
      operator()(feature val) const
      {
        size_t __length = val.len_;
        const char *__first = val.str_;
        
        size_t __result = static_cast<size_t>(2166136261UL);
        __result ^= static_cast<size_t>(val.ftype_);
        //    __result += static_cast<size_t>(val.ftype_ << 8);
        __result *= static_cast<size_t>(16777619UL);
        
        for (; __length > 0; --__length)
          {
            __result ^= static_cast<size_t>(*__first++);
            __result *= static_cast<size_t>(16777619UL);
          }
        return __result;
      }
    };
  }
}

*1:コンパイルや実行方法はREADMEに記載。実装言語はcommon lispとC++。

*2:学習データには、手元にあったテキスト約100MBをMeCabで形態素解析したものを使用

*3:細かい部分はいろいろ変えているし、学習部はcommon lispになっているけど、分割部の素性取り出し方法以外は、本質的なロジックに差異はない

*4:動けば良い、というレベル