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

• 木村 光樹

• 高須 淳宏

• 安達 淳

書誌事項

タイトル別名

• Variable Lengh N-gram Using Gram Frequency for Approximate String Matching

抄録

類似文字列検索では類似した文字列同士は共有する部分文字列が多いことに着目し，gram と呼ばれる長さ N の部分文字列に文字列を分割し，それを索引語とする転置索引を構築し，検索に利用する gram ベースの索引付けを用いる手法が数多く研究されている．しかし，N を大きくすると索引数が N 乗のオーダーで増えていくため，N の値を大きく設定すると索引付けや問い合わせに時間がかかってしまうので N の値は小さい値に設定されることが多い．その一方で，N の値が大きいと長い部分文字列を共有する文字列は一般的に少なくなるため解候補の削減が容易に行えるという利点がある．このことを踏まえて，データ中に出現する長い gram のみを利用する，N の値を可変長に拡張した VGRAM という手法が提案された．しかし，VGRAM では可変長の gram の抽出をするために gram 長の上限値，下限値，抽出の判断基準となる頻度の閾値の 3 つのパラメータを事前に決めなければならない．これらのチューニングコストを考えると，VGRAM は実用的ではない．そこで我々は，Suffix Tree を利用して gram の長さに関するパラメータを必要としない新しい可変長 N-gram を提案する．我々の手法では，tree 上での出現頻度を考慮して文字列の最適な長さの gram の抽出を行う．評価実験では，VGRAM と比較してパラメータチューニングのコストが少なく，高速に類似文字列検索できる端緒を示すことができた．Fixed-length grams(N-gram) are widely used for the problem of approximate string matching, for similar strings share many grams in common. Recently, VGRAM improves the efficiency of the matching by optimizing the size of each gram. Although VGRAM sets the length of grams, it requires three parameters: the upper bound and the lower bound of the length of the grams, and the frequency criterion of the gram partitioning. The cost of the parameter tuning is heavy. In this paper, we propose a new variable length N-gram, which requires only one parameter and realizes efficient approximate substring matching. Our variable length N-gram automatically optimize the size of grams by using Suffix Tree. Experimental results compared with VGRAM indicate that our method is as efficient in finding similar substrings as VGRAM.

収録刊行物

• 研究報告 情報基礎とアクセス技術（IFAT）

  研究報告 情報基礎とアクセス技術（IFAT） 2011 (13), 1-8, 2011-07-26

詳細情報

• CRID: 1572261551916461312
• NII論文ID: 110008583042
• NII書誌ID: AN10114171
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles