高速な類似文字列検索アルゴリズム 岡崎 直観 † 辻井 潤一 †‡ † 東京大学大学院情報学環 ‡ 英国マンチェスター大学 英国国立テキストマイニングセンター 1 はじめに 類似文字列検索は,文字列集合の中から検索クエリ文字列 に似ている文字列を見つけるタスクであり,柔軟な辞書引き, スペル訂正,重複レコード検出など,様々なアプリケーショ ンにおいて必須の技術である.本発表では,「文字列の集合 V の中で,検索クエリ文字列 x と類似度が α 以上の文字列を全 て見つけ出す操作」を,類似文字列検索と定義する.この操 作は,V の部分集合 Yx,α を求める問題として定式化できる. Yx,α = {y ∈ V sim(x, y) ≥ α} (1) ここで,sim(x, y) は文字列 x と y の類似度を与える関数(類 似度関数)である.この問題は,ある検索クエリ文字列 x と 集合に含