我怎样才能测量两个string之间的相似性？
给定两个stringtext1和text2
public SOMEUSABLERETURNTYPE Compare(string text1, string text2) { // DO SOMETHING HERE TO COMPARE }
例子：
-
第一个string：StackOverflow
第二个string：StaqOverflow
回报率：相似度为91％
回报可以在％或类似的东西。
-
第一个string：简单的文本testing
第二个string：复杂的文本testing
返回：这些值可以被认为是相等的
有任何想法吗？ 做这个的最好方式是什么？
有多种不同的方式来做到这一点。 看看维基百科“string相似性度量”页面的链接到其他页面的algorithm。
然而，我认为这些algorithm都没有考虑到声音 – 所以“staq溢出”与“staw overflow”类似，“堆栈溢出”尽pipe第一个在发音方面更相似。
我刚刚find另一个页面 ，给出了更多的select…特别是， Soundexalgorithm（ 维基百科 ）可能更接近你以后。
Levenshtein距离可能是你正在寻找的。
这里是我为我正在编写的项目编写的一些代码。 我需要知道string的相似比和基于string的字的相似比。 这最后一个，我想知道最小string的词相似比（所以如果所有的单词存在和匹配在较大的string结果将是100％）和较大的string的字相似比（我称之为RealWordsRatio ）。 我使用Levenshteinalgorithm来find距离。 到目前为止，代码没有被优化，但是按预期工作。 希望对你有帮助。
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＃ a中写了一个Double Metaphone实现 。 你会发现它远胜于Soundex之类的。
Levenshtein距离也被提出，这是一个很好的algorithm，但是语音匹配并不是真正的function。 它似乎只是有时候，因为语音相似的词也通常拼写相似。 我做了各种模糊匹配algorithm的分析 ，你可能也会觉得有用。
要处理“声音相似”，您可能需要使用Double Metaphone或soundex等语音algorithm来查看编码。 我不知道在语音编码的string上计算Levenshtein距离是否有益，但可能是有可能的。 或者，您可以使用启发式：将string中的每个单词转换为其编码forms，并在计算Levenshtein距离之前，将两个string中出现的单词replace为单个表示forms。
您可能会寻找string“距离”，例如Levenshtein距离 。
Perl模块Text :: Phonetic具有各种algorithm的实现。
杰夫·阿特伍德写了关于寻找一个类似的解决scheme，以确定作者的维基文章，这可能会帮助你缩小search范围。
如果您正在比较SQL数据库中的值，则可以使用SOUNDEX函数。 如果你查询谷歌的SOUNDEX和C＃，一些人已经写了一个类似的function和VB。
我也必须推荐Soundex，我曾经用它来处理拼写错误的城市名称。 这是一个很好的使用链接： http : //whitepapers.zdnet.com/abstract.aspx? docid= 352953
如果你想比较语音，请查看Soundex和Metaphonealgorithm： http : //www.blackbeltcoder.com/Articles/algorithms/phonetic-string-comparison-with-soundex
Metaphone 3是第三代Metaphonealgorithm。 它将语音编码的准确度从89％的双音位提高到98％ ，这是针对最常见的英语单词以及北美熟悉的名字和非英语单词的数据库进行testing的。 这为美式发音产生了非常可靠的语音编码。
Metaphone 3是由Lawrence Philipsdevise和开发的，他devise并开发了原来的Metaphone和Double Metaphonealgorithm。
