28

レーベンシュタイン距離アルゴリズムを使用して、可能な一致の辞書に対して単一の検索語を一致させようとしています。このアルゴリズムは、検索文字列を一致する文字列に変換するために必要な操作の数として表される距離を返します。上位「N」（たとえば10）の一致のランク付けされたパーセンテージリストに結果を表示したいと思います。

検索文字列は個々の辞書文字列よりも長くても短くてもよいため、距離をパーセンテージで表現する適切なロジックは何でしょうか。これは、各結果がクエリ文字列にどれだけ近いかを定性的に反映します。 % 完全一致を示します。

次のオプションを検討しました。

Q = query string
M = matched string
PM = Percentage Match
Option 1. PMi = (1 - Lev_distance(Q, Mi)/Strlen(Q)) * 100
Option 2. PMi = (1 - Lev_distance(Q, Mi)/max(Strlen(Q), strlen(Mi))) * 100

オプション 1 では、距離が検索文字列の長さよりも長く、一致文字列が長い場合、負のパーセンテージになる可能性があります。たとえば、クエリ「ABC」は「ABC Corp.」と一致します。負の一致率になります。

オプション 2 では、Mi のセット全体で一貫したパーセンテージが得られないようです。これは、各計算で異なる分母が使用される可能性があり、結果のパーセンテージ値が正規化されないためです。

私が考えることができる唯一の他の方法は、lev_distance といずれかの文字列の長さの比較を捨てることですが、代わりに上位 "N" の一致の比較距離を逆パーセンタイル ランク (100 パーセンタイル ランク) として提示することです。

何かご意見は？より良いアプローチはありますか？レーベンシュタイン距離はおそらくあいまい一致の最も一般的なアルゴリズムであり、これは非常に一般的な問題であるに違いないため、何かが欠けているに違いありません。

4

8 に答える 8

5

この問題に対する私のアプローチは、レーベンシュタイン距離である最大許容操作を計算することでした。私が使用した式は次のとおりです。 

percent = 0.75; // at least 75% of string must match
maxOperationsFirst = s1.length() - s1.length() * percent;
maxOperationsSecond = s2.length() - s2.length() * percent;
maxOperations = round(min(maxOperationsFirst, maxOperationsSecond));

弦ごとの最大操作数を計算してくれるので、計算がわかりやすいと思います。両方の結果の最小値を使用し、最も近い整数に丸めます。この部分をスキップして、いずれかの文字列から最大操作の値のみを使用できます。実際にはデータに依存します。

最大操作数を取得したら、それをレーベンシュタインの結果と比較して、文字列が許容できるかどうかを判断できます。このようにして、拡張されたレーベンシュタイン法 (たとえば、 test -> tsetなどのスペルミスを 1 つの操作としてのみカウントするDamerau–Levenshtein distanceなど) を使用できます。これは、スペルミスが非常に頻繁に発生するユーザー入力をチェックする場合に非常に役立ちます。

これが、この問題を解決する方法についてのアイデアを得るのに役立つことを願っています.

于 2013-08-14T23:11:45.060 に答える
2 
Max = Lev_distance(Q,''); //max operations to transform query string to empty string
PM = (Max - Lev_distance(Q, Mi)) / Max * 100%;

これであなたのニーズは十分だと思います。極端な値に対しては正しく（まったく同じ文字列とまったく異なる文字列で十分です）、もっともらしい

于 2021-05-29T21:09:42.287 に答える
1

これは基本的に、私の質問で言及されているオプション 2 です。ただし、そのアプローチの問題を示してみましょう。

Q = "ABC Corp" (len = 8)
M1 = "ABC"
M2 = "ABC Corporati"
M3 = "ABC Corp"

M1 と M2 の Lev 距離が同じ (それぞれ 5) になるように選択しました。オプション 2 を使用すると、一致率は次のようになります。

M1 = (1 - 5/8)*100  = 37.5%
M2 = (1 - 5/13)*100 = 61.5%
M3 = 100%

この順番で並べてみるとわかるように、M1とM2はレフ距離が全く同じなのに、かなりのランク差があります。問題がわかりますか？

于 2013-01-11T01:01:45.557 に答える
0

これはどうですか：

100 - ( ((2*Lev_distance(Q, Mi)) / (Q.length + Mi.length)) * 100 )

と で同じ距離を与え(Q, M1)ます(Q,M2)

于 2016-05-08T09:06:52.137 に答える
0 
(1 - (levNum / Math.max(s.length,t.length) ) ) *100

正しいはずです

于 2013-01-09T14:51:50.137 に答える