あいまい検索（文字列一致率）

質問

お世話になっております。
　少し無謀な質問かもしれませんが・・・。
dim s1 as string, s2 as string
dim v as double
s1 = "abcde"
s2 = "cd"
という条件の時、
v = aimai(s1, s2)
とすれば、vに0.4だとか0.2だとか、「s1とs2がどのくらい似ているか」を返す関数、もしくはアルゴリズムは存在するのでしょうか。
　返り値の最大値は1.0（完全一致）、最小値は0（何一つ同じ文字がなかった）となるとします。

　何を以て「似ている」と評価するかですが、
・何文字含まれるか
・並び順
という要素は、重要でしょうね。

　s2を1文字ずつ分解し、正規表現でヒットするかという流れ
/*
　初めは、.+c.+
　次は、.+cd.+、それと.+c.*d.+
*/
を考えたのですが、私には一般化できそうにありません。

回答No.1

Oh-Orange · ベストアンサー

★『あいまい評価関数』は標準ではないと思います。
・特に完全一致のときが『1.0』で不一致が『0.0』で、数箇所の文字が一致すると小数で返す関数は
　自分で実装するしかないでしょう。
・アルゴリズムは、上記の仕様を元に考えれば出来そうですね。
　つまり、完全一致した場合は『1.0』を返して数箇所の文字(文字列)が一致した場合は、文字列の
　長さと一致した個数からパーセントを算出します。このパーセントを小数に変換して返せば良いでしょう。
・また、一致する文字(文字列)が１つもなければ『0.0』を返すようにします。
・簡単なアルゴリズムでは、文字列『s1』の中に文字列『s2』が何箇所、含まれるかカウントします。
　ゼロの場合は、『s2』を文字単位に分解して文字列『s1』から何箇所、含まれるかカウントします。
　文字単位でどれも含まれなければ『0.0』を返す。
・上記のアルゴリズムで含まれる文字列の個数や文字単位の個数を使って、文字列『s1』の文字数との
　パーセントを算出します。算出方法は例えば、
　s1=abcdefcd123(11バイト)
　s2=cd(2バイト)
　の場合『cd』が2箇所一致します。そこで『s2の長さ』×『2箇所一致』÷『s1の長さ』＝4÷11＝0.3636…
　を戻り値に返せばいいでしょう。
・以上。おわり。→アルゴリズムの参考にして下さい。

お礼

ご回答、ありがとうございます。
　その後いろいろと考えたのですが、私が考えている事柄については、「沖田十三」という文字列に対して、「沖田十四」より「沖田十三（ヤマト初代艦長）」の方が、高い一致度を返して欲しいみたいです。
　となると、数値で返すという基本方針に、かなりの無理がありますね。

　再度、基本から見直してみます。

回答No.2

imogasi

VBの関数は数も少ないのでVBの本や解説WEBを見ればすぐ判る。質問しなくても判る。本やWEBを見なくても、その内容の盛り沢山さから、関数としては採用されてないことは判る。自分でそれ向けのプログラムを作るよりほかない。
＞もしくはアルゴリズムは存在するのでしょうか。
これもプログラムを作成する人が考えることです。アルゴリズム事典でも載っているなら、あるといえるでしょう。
プログラマが採用したロジックをすべてアルゴリズムというのはおこがましいと思う。
本件はそう壮大な（データが多い、処理計算が膨大に多いので工夫がいるなど）内容ではないので、アルゴリズムというほどのすっきりした解法の問題ではないでしょう。
質問者自身で（下記で）それを語っているではないですか。
＞返り値の最大値は1.0（完全一致）、最小値は0（何一つ同じ文字がなかった）となるとします。
　何を以て「似ている」と評価するかですが、
・何文字含まれるか
・並び順
ーー
文字の場合は機械的にそれで（上記で）よいでしょう。しかしその記号が現実世界の事象を抽象化したものなら、有無しのほか、距離とか近縁、質量（引力の源）などの定義を持ち込む人がいるかもしれない。ですからその辺は、プログラマに聞くより、理数系の方がみるカテゴリを選んで質問しなおしては。
人もの金の世界のプログラムを扱う方が文系プログラマには多く、質問のようなことを考える必要はほぼないと思うから。
正規表現が役立つかどうかも、文字列の有無の問題で、問いかけ法の集約にしか過ぎず、それ以上の一般化のプログラムテクニックの問題には使えないと思う。
VB使いに聞くべき以上の質問だといいたい。したがってOKWAVEでは現状カテ不適当。
それと実際は何の世界のことを考えた挙句なのか、やはり明示して質問すべきでは。それを回答者がわきまえないで回答すると、回答者はやけどする。Fazzy理論でも考えているお仲間に質問したら。
それに大学や大学院で議論する問題ではないかと思うが、それらをこのカテで質問されるのもどうかと思います。

お礼

ご意見、ありがとうございます。