Даны две строки text1 и text2:
public SOMEUSABLERETURNTYPE Compare(string text1, string text2)
{
// DO SOMETHING HERE TO COMPARE
}
Примеры:
Первая строка: StackOverflow
Вторая строка: StaqOverflow
Доходность: сходство 91%
Возврат может быть в% или что-то в этом роде.
Первая строка: простой текстовый тест
Вторая строка: сложный текстовый тест
Результат: значения можно считать равными
Любые идеи? Как лучше всего это сделать?
Это можно сделать разными способами. Посетите страницу Википедии «Меры сходства строк» , чтобы найти ссылки на другие страницы с алгоритмами. .
Однако я не думаю, что какой-либо из этих алгоритмов учитывает звуки - поэтому «переполнение стека» будет таким же похоже на «переполнение стека», как «переполнение стека», несмотря на то, что первый более похож по терминам. произношения.
Я только что нашел другую страницу, которая дает гораздо больше возможностей .. . в частности, алгоритм Soundex (Wikipedia) может быть ближе к тому, что вам нужно.
Возможно, вы ищете расстояние Левенштейна.
Вот код, который я написал для проекта, над которым работаю. Мне нужно знать коэффициент схожести строк и коэффициент схожести на основе слов в строках. В этом последнем случае я хочу знать коэффициент схожести слов для наименьшей строки (поэтому, если все слова существуют и совпадают в более крупной строке, результат будет 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;
}
Некоторое время назад я написал реализацию Double Metaphone на C #. Вы обнаружите, что он значительно превосходит Soundex и тому подобное.
Также предлагалось расстояние Левенштейна, и это отличный алгоритм для множества применений, но на самом деле фонетическое сопоставление - это не то, что он делает; это только иногда кажется так, потому что фонетически похожие слова также обычно пишутся одинаково. Я провел анализ различных алгоритмов нечеткого сопоставления, который также может оказаться полезным.
Чтобы справиться со «подобными звуками», вы можете захотеть изучить кодирование с использованием фонетического алгоритма, такого как Double Metaphone или soundex. Я не знаю, будет ли полезно вычисление расстояний Левенштейна на строках с фонетической кодировкой, но это возможно. В качестве альтернативы вы можете использовать эвристику, например: преобразовать каждое слово в строке в его закодированную форму и удалить все слова, встречающиеся в обеих строках, и заменить их одним представлением перед вычислением расстояния Левенштейна.
Вы можете искать строку «расстояния», например расстояние Левенштейна.
Модуль 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.
Метафон 3 - это третье поколение алгоритма Метафон. Он увеличивает точность фонетического кодирования с 89% двойного метафона до 98%, что подтверждается проверкой на базе данных наиболее распространенных английских слов, а также имен и неанглийских слов, известных в Северной Америке. Это обеспечивает чрезвычайно надежное фонетическое кодирование американского произношения.
Metaphone 3 был разработан и разработан Лоуренсом Филипсом, который спроектировал и разработал оригинальные алгоритмы Metaphone и Double Metaphone.
