2つの文字列の類似性を測定するにはどうすればよいですか？ [閉まっている]
https://stackoverflow.com/questions/1034622
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
2つの文字列 text1 および text2
public SOMEUSABLERETURNTYPE Compare(string text1, string text2)
{
// DO SOMETHING HERE TO COMPARE
}
例：
-
最初の文字列：StackOverflow
2番目の文字列：StaqOverflow
戻り値：類似度は91％です
戻り値は％またはそのようなものになります。
-
最初の文字列：単純なテキストテスト
2番目の文字列：複雑なテキストテスト
戻り値：値は等しいと見なすことができます
アイデアはありますか？これを行う最良の方法は何ですか？
解決
これにはさまざまな方法があります。 ウィキペディア＆quot;文字列類似度測定＆quot;をご覧ください。ページ：アルゴリズムを使用した他のページへのリンク。
これらのアルゴリズムは音を考慮していませんが、考えません-だから「staq overflow」 ＆quot; stack overflow＆quot;と同様になります。 ＆quot; staw overflow＆quot;最初の方が発音の点で似ているにもかかわらず。
別のページを見つけました。オプション...特に、 Soundex アルゴリズム（< a href = "http://en.wikipedia.org/wiki/Soundex" rel = "noreferrer">ウィキペディア）は、あなたが望んでいるものに近いかもしれません。
他のヒント
レーベンシュタイン距離は、おそらく探しているものです。
これは、私が取り組んでいるプロジェクトのために書いたコードです。文字列のSimilarity Ratioと、文字列の単語に基づくSimilarity Ratioを知る必要があります。 この最後の1つは、最小文字列の単語類似率（すべての単語が存在し、より大きな文字列に一致する場合、結果は100％になる）と、より大きな文字列の単語類似率（RealWordsRatioと呼ぶ）の両方を知りたい）。 レーベンシュタインアルゴリズムを使用して距離を見つけます。これまでのところ、コードは最適化されていませんが、期待どおりに機能します。役に立つと思います。
public static int Compute(string s, string t)
{
int n = s.Length;
int m = t.Length;
int[,] d = new int[n + 1, m + 1];
// Step 1
if (n == 0)
{
return m;
}
if (m == 0)
{
return n;
}
// Step 2
for (int i = 0; i <= n; d[i, 0] = i++)
{
}
for (int j = 0; j <= m; d[0, j] = j++)
{
}
// Step 3
for (int i = 1; i <= n; i++)
{
//Step 4
for (int j = 1; j <= m; j++)
{
// Step 5
int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;
// Step 6
d[i, j] = Math.Min(
Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
d[i - 1, j - 1] + cost);
}
}
// Step 7
return d[n, m];
}
double GetSimilarityRatio(String FullString1, String FullString2, out double WordsRatio, out double RealWordsRatio)
{
double theResult = 0;
String[] Splitted1 = FullString1.Split(new char[]{' '}, StringSplitOptions.RemoveEmptyEntries);
String[] Splitted2 = FullString2.Split(new char[]{' '}, StringSplitOptions.RemoveEmptyEntries);
if (Splitted1.Length < Splitted2.Length)
{
String[] Temp = Splitted2;
Splitted2 = Splitted1;
Splitted1 = Temp;
}
int[,] theScores = new int[Splitted1.Length, Splitted2.Length];//Keep the best scores for each word.0 is the best, 1000 is the starting.
int[] BestWord = new int[Splitted1.Length];//Index to the best word of Splitted2 for the Splitted1.
for (int loop = 0; loop < Splitted1.Length; loop++)
{
for (int loop1 = 0; loop1 < Splitted2.Length; loop1++) theScores[loop, loop1] = 1000;
BestWord[loop] = -1;
}
int WordsMatched = 0;
for (int loop = 0; loop < Splitted1.Length; loop++)
{
String String1 = Splitted1[loop];
for (int loop1 = 0; loop1 < Splitted2.Length; loop1++)
{
String String2 = Splitted2[loop1];
int LevenshteinDistance = Compute(String1, String2);
theScores[loop, loop1] = LevenshteinDistance;
if (BestWord[loop] == -1 || theScores[loop, BestWord[loop]] > LevenshteinDistance) BestWord[loop] = loop1;
}
}
for (int loop = 0; loop < Splitted1.Length; loop++)
{
if (theScores[loop, BestWord[loop]] == 1000) continue;
for (int loop1 = loop + 1; loop1 < Splitted1.Length; loop1++)
{
if (theScores[loop1, BestWord[loop1]] == 1000) continue;//the worst score available, so there are no more words left
if (BestWord[loop] == BestWord[loop1])//2 words have the same best word
{
//The first in order has the advantage of keeping the word in equality
if (theScores[loop, BestWord[loop]] <= theScores[loop1, BestWord[loop1]])
{
theScores[loop1, BestWord[loop1]] = 1000;
int CurrentBest = -1;
int CurrentScore = 1000;
for (int loop2 = 0; loop2 < Splitted2.Length; loop2++)
{
//Find next bestword
if (CurrentBest == -1 || CurrentScore > theScores[loop1, loop2])
{
CurrentBest = loop2;
CurrentScore = theScores[loop1, loop2];
}
}
BestWord[loop1] = CurrentBest;
}
else//the latter has a better score
{
theScores[loop, BestWord[loop]] = 1000;
int CurrentBest = -1;
int CurrentScore = 1000;
for (int loop2 = 0; loop2 < Splitted2.Length; loop2++)
{
//Find next bestword
if (CurrentBest == -1 || CurrentScore > theScores[loop, loop2])
{
CurrentBest = loop2;
CurrentScore = theScores[loop, loop2];
}
}
BestWord[loop] = CurrentBest;
}
loop = -1;
break;//recalculate all
}
}
}
for (int loop = 0; loop < Splitted1.Length; loop++)
{
if (theScores[loop, BestWord[loop]] == 1000) theResult += Splitted1[loop].Length;//All words without a score for best word are max failures
else
{
theResult += theScores[loop, BestWord[loop]];
if (theScores[loop, BestWord[loop]] == 0) WordsMatched++;
}
}
int theLength = (FullString1.Replace(" ", "").Length > FullString2.Replace(" ", "").Length) ? FullString1.Replace(" ", "").Length : FullString2.Replace(" ", "").Length;
if(theResult > theLength) theResult = theLength;
theResult = (1 - (theResult / theLength)) * 100;
WordsRatio = ((double)WordsMatched / (double)Splitted2.Length) * 100;
RealWordsRatio = ((double)WordsMatched / (double)Splitted1.Length) * 100;
return theResult;
}
しばらく前に C＃でのダブルMetaphoneの実装を作成しました。 Soundexなどに比べて非常に優れていることがわかります。
レーベンシュタイン距離も提案されており、多くの用途に最適なアルゴリズムですが、音声マッチングは実際にはそうではありません。音声的に類似した単語も通常は同じように綴られるため、そのように思われることがあります。 さまざまなファジーマッチングアルゴリズムの分析を行いました。 / p>
「似たような音」を扱うには、Double Metaphoneやsoundexなどの音声アルゴリズムを使用したエンコードを検討することをお勧めします。音声符号化された文字列でレーベンシュタイン距離を計算することが有益かどうかはわかりませんが、可能性があるかもしれません。または、文字列の各単語をエンコードされた形式に変換し、両方の文字列に出現する単語をすべて削除して、レーベンシュタイン距離を計算する前に単一の表現に置き換えるなどのヒューリスティックを使用できます。
Levenshtein distance などの文字列＆quot; distances＆quot;を検索できます。
Perlモジュール Text :: Phonetic にはさまざまなアルゴリズムが実装されています。
SQLデータベースの値を比較する場合、 SOUNDEX 関数を使用できます。 GoogleにSOUNDEXとC＃を照会すると、一部の人々はそれとVBに対して同様の関数を作成しました。
Soundexも推奨する必要があります。過去にスペルミスの都市名を処理するために使用していました。使用方法の良いリンクを次に示します。 http://whitepapers.zdnet.com/abstract。 aspx？docid = 352953
音声学的に比較したい場合は、SoundexおよびMetaphoneアルゴリズムを確認してください： http://www.blackbeltcoder.com/Articles/algorithms/phonetic-string-comparison-with-soundex
Metaphone 3は、Metaphoneアルゴリズムの第3世代です。それ 音声エンコードの精度を89％のDoubleから向上 最も一般的なデータベースに対してテストされた 98％へのMetaphone 英語、および北でよく知られている名前と英語以外の単語 アメリカ。これにより、非常に信頼性の高い音声エンコードが生成されます。 アメリカの発音。
Metaphone 3はLawrence Philipsによって設計および開発されました。 オリジナルのMetaphoneおよびDouble Metaphoneを設計および開発 アルゴリズム。
