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

• Item type: SIG Technical Reports(1)
• 公開日: 2011-07-26
• タイトル: 頻度情報を用いた類似文字列検索のための可変長N-gram
• タイトル / 言語: en
• タイトル: Variable Lengh N-gram Using Gram Frequency for Approximate String Matching
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: ●アルゴリズム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院情報利工学系研究科
• 著者所属: 国立情報学研究所
• 著者所属: 国立情報学研究所
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者名: 木村, 光樹; 高須, 淳宏; 安達, 淳
• 著者名(英): Mitsuki, Kimura; Atsuhiro, Takasu; Jun, Adachi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 類似文字列検索では類似した文字列同士は共有する部分文字列が多いことに着目し，gram と呼ばれる長さ N の部分文字列に文字列を分割し，それを索引語とする転置索引を構築し，検索に利用する gram ベースの索引付けを用いる手法が数多く研究されている．しかし，N を大きくすると索引数が N 乗のオーダーで増えていくため，N の値を大きく設定すると索引付けや問い合わせに時間がかかってしまうので N の値は小さい値に設定されることが多い．その一方で，N の値が大きいと長い部分文字列を共有する文字列は一般的に少なくなるため解候補の削減が容易に行えるという利点がある．このことを踏まえて，データ中に出現する長い gram のみを利用する，N の値を可変長に拡張した VGRAM という手法が提案された．しかし，VGRAM では可変長の gram の抽出をするために gram 長の上限値，下限値，抽出の判断基準となる頻度の閾値の 3 つのパラメータを事前に決めなければならない．これらのチューニングコストを考えると，VGRAM は実用的ではない．そこで我々は，Suffix Tree を利用して gram の長さに関するパラメータを必要としない新しい可変長 N-gram を提案する．我々の手法では，tree 上での出現頻度を考慮して文字列の最適な長さの gram の抽出を行う．評価実験では，VGRAM と比較してパラメータチューニングのコストが少なく，高速に類似文字列検索できる端緒を示すことができた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 研究報告 データベースシステム（DBS）; 巻 2011-DBS-152, 号 13, p. 1-8, 発行日 2011-07-26
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会