頻度情報を用いた類似文字列検索のための可変長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
著者
-
安達 淳
国立情報学研究所
-
高須 淳宏
National Institute of Informatics
-
安達 淳
National Institute of Informatics
-
高須 淳宏
国立情報学研究所
-
安達 淳
東京大学工学部電子工学科:(現)東京大学大型計算機センター
-
木村 光樹
東京大学大学院情報利工学系研究科
-
安達 淳
国立情報学研究所コンテンツ科学研究系
-
安達 淳
国立情報学研
-
安達 淳
学術情報センター研究開発部
関連論文
- 特徴点軌跡の不均一性パターンに基づいた同一場面映像検出(メディア処理,第12回画像の認識・理解シンポジウム推薦論文,画像の認識・理解論文)
- 知識ベースを用いた人名検索時の曖昧性の解消(言語処理,夏のデータベースワークショップDBWS 2006)
- 知識ベースを用いた人名検索時の曖昧性の解消(言語処理)
- 外部知識を用いて同姓同名の曖昧解消
- 言い換え箇所と言い換え候補の提示による解説文リライト支援の書き手の評価実験(言い換え・略語・要約)
- 情報リンケージのための統計的文字列類似度
- 高さの制限された無順序木の編集距離問題に対する近似アルゴリズム
- 混合ディリクレ分布を用いた文書分類の精度について(情報融合)
- 文書間類似度によるソフトウェアパターン間関連分析と複合関連の導出
- マージン最大化によるメトリック空間分割手法(一般,「ユビキタス,センサ環境におけるデータベース」,及び一般)