類似文字列検索は，あらかじめ与えられた文字列集合のうちから，入力クエリ文字列に類似した文字列集合を返却するタスクであり，古くから研究され続けている[1,2]．既存手法の多くは，類似性尺度として編集距離，あるいは文字N-gram素性（Q-gram）のcosine係数やJaccard係数を使用しており，各素性ごとの重みを同一と見なしている．しかし，出現頻度がべき乗則に従う自然言語を対象とする場合は，BM25[3]のように低頻度素性を重視するスコアリング手法を用いることで，文字列同士の比較回数削減と精度向上が見込める．本研究は類似文字列検索タスクを複数タームに基づくOR検索として定式化し直し，Top-kクエリ処理手法の一つであるMaxScoreアルゴリズムを使用することで，高速かつ正確に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ヤ’,‘ヤフ’,‘フー’]となる．