RengaStreet:Top-kクエリ処理アルゴリズムによる高速類似文字列検索の実装

類似文字列検索は自然言語を対象とした曖昧検索やスペル訂正，名寄せのみではなく，DNA配列検索[4]，類似音楽検索[5]のような自然言語以外を対象とするアプリケーションにおいても使用される．そのため既存手法の多くは各素性の重みを均一に取り扱うが，自然言語のみを対象とする場合は，出現頻度に基づいて重み付けするIDF（InverseDocumentFrequency）ベースのスコアリング手法を用いることで，より高精度な検索が実現できると予想される．しかしIDFベースのスコアリング手法を用いる場合，CountFiltering，LengthFiltering[1,2]のような既存の類似文字列候補削減手法をそのまま適用することができず，文字列同士の比較回数が大幅に増加してしまう．本研究ではこれらの高速化手法の代わりに，Top-kクエリ処理を伴う複数タームOR検索としてタスクを定式化し直すことで，高速な類似文字列検索を実現する．Top-kクエリ処理のうち，動的枝刈り[6]に着目する．動的枝刈りは上位푘件に含まれないドキュメントのスコア評価を省略することで，Top-kOR検索における転置インデックスの走査を高速化する．動的枝刈り手法としてはMaxScore[7]，WAND[8]，Block-MaxWAND[9]など，いくつか提案されているが，今回はMaxScoreアルゴリズムを実装し，既存手法と比較する．本研究ではいずれの手法においても，素性としてQ-gramを使用する．Q-gramとは文字N-gramのことを指し，例えば「LINEヤフー」に含まれる푞=2のQ-gramは[‘LI’,‘IN’,‘NE’,‘Eヤ’,‘ヤフ’,‘フー’]となる．