拙作のぺけアニメデータベースは、アニメのタイトルやスタッフやキャストの人物名をユーザが検索できる仕組みを備えている。この検索では、ユーザがタイトルや人物名に完全一致するクエリを入力することは期待できないので、あいまいな検索をサポートする必要があった。例えばまどかマギカというクエリに対して、魔法少女まどか☆マギカを検索したい。
あいまいな検索をサポートするにあたって、まず考えたのは編集距離による検索だ。編集距離は、ある文字列と別の文字列を比較する際に、文字の挿入・削除・置換を何回行えば文字列が同一になるかを距離として、文字列同士を比較する方法だ。例えばabcとbcdの比較では、abcはaの削除とdの挿入でbcdとなることから、距離2となる。
編集距離は、動的計画法による高速な計算方法が知られている。しかし、ぺけアニメデータベースでは検索対象となるタイトル・人物名の数が25,000個にも及ぶ。入力された文字列に対してインクリメンタルな検索を行なって候補を表示するには、編集距離では計算が遅すぎるという問題があった。編集距離よりも多少精度が劣っても、もっと高速なあいまい検索の方法が必要だった。
そこで考えたのは、文字列の並びと出現回数を無視して、単にある文字列に含まれる文字が、別の文字列に含まれるかをカウントする方法だ。前の例だとabcとbcdではbとcが共に含まれているので、スコアを2とする。まどかマギカと魔法少女まどか☆マギカではスコア6である。これがなんちゃってあいまい検索である。
愚直に計算するには、まず文字列を文字に分割して、2つの文字列に含まれる文字を数え上げれば良い。これを更に洗練して、この方法では転置インデックスを使うことができる。予めaという文字が含まれる文字列の一覧、bという文字が含まれる文字列の一覧…、をインデックスとして保持しておく。abcというクエリが来た時はaとbとcのインデックスをそれぞれ参照して、文字列のスコアを算出する。
この方法で実装したのが以下のRubyスクリプトだ。ぺけアニメデータベースでは、これと同様の方法を使って、25,000個の文字列を対象とした検索で1クエリあたり0.02秒という高速なあいまい検索を実現することができた。概ね正確なクエリが入力されると期待できる場合には、このような単純な方法でも十分にあいまい検索が可能だとわかった。
# 検索対象の文字列の配列
target = %w(abc bcd cdf)
# インデックスの作成
index = Hash.new{|h, k| h[k] = [] }
target.each_with_index{|str, i|
str.split('').uniq.each{|c|
index[c] << str
}
}
# クエリ
query = 'bc'
# 検索
score = Hash.new(0)
query.each_char{|c|
index[c].each{|i|
score[i] += 1
}
}
# 結果表示
score.each{|k, v|
puts v.to_s + ' ' + k
}
=begin
2 abc
2 bcd
1 cdf
=end
