テキストデータベースからの文字列のあいまい検索と高速化

IPSJ

Search this article

Description

文書処理やテキストデータベースで文字列の部分マッチによる検索を必要とすることが多い。この分野の研究としては、検索自体を高速にする方法としてBM法などが有名である。これらの方法は、検索パターンと完全一致するテキストの部分列を検索することを目的としている。一方、2つの文字列について、適当な基準を定め、類似しているかどうかを判定するアルゴリズムも発表されている。このアルゴリズムは、Levenshteinの距離に基づくもので、あらかじめ決められた距離以内にある、2つの文字列を類似していると判定する。本発表では、テキスト中から文字列パターンに類似した部分列を高速に検索する方法について述べる。提案のアルゴリズムの計算量は、検索パターンの長さをm、テキストの長さをnとしたときO(mm)である。

Journal

Details 詳細情報について

Report a problem

Back to top