- 著者
-
岡崎 直観
辻井 潤一
- 出版者
- 一般社団法人 言語処理学会
- 雑誌
- 自然言語処理 (ISSN:13407619)
- 巻号頁・発行日
- vol.18, no.2, pp.89-117, 2011 (Released:2011-09-28)
- 参考文献数
- 34
- 被引用文献数
-
2
本論文では,コサイン係数,ダイス係数,ジャッカード係数,オーバーラップ係数に対し,簡潔かつ高速な類似文字列検索アルゴリズムを提案する.本論文では,文字列を任意の特徴(tri-gram など)の集合で表現し,類似文字列検索における必要十分条件及び必要条件を導出する.そして,類似文字列検索が転置リストにおける τ オーバーラップ問題として正確に解けることを示す.次に,τ オーバーラップ問題の効率的な解法として,CPMerge アルゴリズムを提案する.CPMerge は,検索クエリ文字列中のシグニチャと呼ばれる特徴と,解候補が枝刈りできる条件に着目し,τ オーバーラップ問題の解候補を絞り込む.さらに,CPMerge アルゴリズムの実装上の工夫について言及する.英語の人名,日本語の単語,生命医学分野の固有表現の 3 つの大規模文字列データセットを用い,類似文字列検索の性能を評価する.実験では,類似文字列検索の最近の手法である Locality Sensitive Hashing や DivideSkip 等と提案手法を比較し,提案手法が全てのデータセットにおいて,最も高速かつ正確に文字列を検索できることを実証する.また,提案手法による類似文字列検索が高速になる要因について,分析を行う.なお,提案手法をライブラリとして実装したものは,SimString としてオープンソースライセンスで公開している.