SimStringメモ
どうやって高速化しているのか気になったのでメモ。
基本的には辞書となるキーワードリストに対して、n-gram→キーワードのID(SID)のリストのマッピングをCDB(Constant Database)に保存しておいて、そこから入力文字列のn-gramを含むSIDがいくつn-gramを含むか数えていき、コサインやジャッカード係数などの尺度でn-gramの類似度が閾値を超える数になったものを類似文字列として出力するという考え方。
高速化の方法としては2つ考えられている。1つは文字列の長さごとに別のCDBファイルにしてあるという部分。閾値と尺度と入力文字列の長さが決まると類似文字列の長さの上限と下限が決まる。そこで、下限から上限までの各長さのCDBファイルにアクセスすることで、辞書の全キーワードを対象にする必要がなくなる。
もう1つは各SIDがいくつn-gramを含むかを数える部分。これを1つでもn-gramを含むSIDに対して数えていくと効率が悪い。入力文字列がm個のn-gramに分割されるとき、閾値と尺度により、最低でもk個n-gramを含まなければならないというkの値が求められる。この時、閾値以上になる類似文字列は入力文字列のm個のn-gramのうちどのm-k+1個を選んでもそのうちの1個のn-gramは含まなければならない。そこで、最初のm-k+1個のn-gramのどれかを含むSIDの集合をつくって、それ以降はその集合のSIDに対してのみn-gramを数えていくようにする。さらに、この最初のSIDの集合が小さくなるように、最初にチェックするn-gramはヒット数が少ない順からm-k+1個選ぶようにしてある。
