Entry

プログラミングメモ - fuzzy search のアルゴリズムで思いついたこととか

2010年06月01日

文字列比較のアルゴリズムというと,最長共通部分列問題(Longest-Common Subsequence probrem; LCS) に解消した上で,最短編集距離(Shortest Edit Distance; SED)を求める方法が有名です。エディットグラフを作って,その最短経路を求めることで文字列の比較を行うことができる。

で,今日ふと思ったんだけれども,こいつはいわゆる fuzzy search(あいまい検索)にも応用できるんでねいのかな,とかつらつら。

fuzzy search ってのは,それだけでは問題が定義されていなくて,結局のところ「どれだけあいまいに検索するのか」が分からないと,適切な答えが出てこなかったりします。また,一般に,LCS/SED は,diff(1) のような長めの文字列に対して,一致している箇所と不一致の箇所,そして比較対象が見つからない箇所を効率よく求める手段だったりする。検索語を文字列(文字の集合)から見つけ出す場合は,検索語がすでに与えられていて,こいつを単位に探すことから,一見無関係なものにも見えます。

しかし,fuzzy search は,普通の検索におけるそれと違って,すべてが共通していなくても一致しているとみなす必要がある。この点,Google の「もしかして」は,主にユーザの入力履歴と統計的な計算から検索語に修正をかけているようだけれども,履歴のないところでは役に立たなかったりするし,第一検索語に修正をかけるというのは,なんとなく数理的に美しくない気もする(偉そうなんだけれども)。ある文字の並びが,それ自体として「近い」とか「遠い」とか判断するには,どういう基準が適当なんだろう,と。で,あいまいさの基準を,「最短編集距離との差が閾値以内であること」といった基準に設定するのはどうだろう,と思ったわけです。

もちろん,単純にエディットグラフを構成して,その編集距離だけから文字列の類似度を判別するだけでは,あまり実用にはならないかもしれません。どうしてかというと,検索後に対する意味論的な解釈が欠けているから。この点,生の人間が入力した検索後は,何らかの意味を持っていると考えられるから,fuzzy search を構成する手段として手っ取り早い。

通常のエディットグラフは,各文字が等距離に離れていることを前提にしているけれども,もしかしたら,意味論的にグラフの辺に長さを持たせる必要があるのかもしれません。つか,それ以外にないようにも思える。

ま,ただふと思っただけです。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN