頻度情報を用いた類似文字列検索のための可変長N-gram

概要

論文の詳細を見る
類似文字列検索では類似した文字列同士は共有する部分文字列が多いことに着目し,gram と呼ばれる長さ N の部分文字列に文字列を分割し,それを索引語とする転置索引を構築し,検索に利用する gram ベースの索引付けを用いる手法が数多く研究されている.しかし,N を大きくすると索引数が N 乗のオーダーで増えていくため,N の値を大きく設定すると索引付けや問い合わせに時間がかかってしまうので N の値は小さい値に設定されることが多い.その一方で,N の値が大きいと長い部分文字列を共有する文字列は一般的に少なくなるため解候補の削減が容易に行えるという利点がある.このことを踏まえて,データ中に出現する長い gram のみを利用する,N の値を可変長に拡張した VGRAM という手法が提案された.しかし,VGRAM では可変長の gram の抽出をするために gram 長の上限値,下限値,抽出の判断基準となる頻度の閾値の 3 つのパラメータを事前に決めなければならない.これらのチューニングコストを考えると,VGRAM は実用的ではない.そこで我々は,Suffix Tree を利用して gram の長さに関するパラメータを必要としない新しい可変長 N-gram を提案する.我々の手法では,tree 上での出現頻度を考慮して文字列の最適な長さの gram の抽出を行う.評価実験では,VGRAM と比較してパラメータチューニングのコストが少なく,高速に類似文字列検索できる端緒を示すことができた.
2011-07-26

頻度情報を用いた類似文字列検索のための可変長N-gram

スポンサーリンク

概要

著者

関連論文

スポンサーリンク