Лучший алгоритм ранжирования сходства для строк переменной длины
Вы должны сделать:
string dest = Gimme<int, string>(5);
Вам нужно указать, какие ваши типы находятся в вызове общего метода. Как он мог знать, что вам нужна строка в выходе?
System.String - плохой пример, потому что это запечатанный класс, но сказать, что это не так. Как компилятор мог знать, что вы не хотите использовать один из своих подклассов, если вы не указали тип в вызове?
Возьмем этот пример:
System.Windows.Forms.Control dest = Gimme(5);
Как компилятор узнает, какой контроль на самом деле сделать? Вам нужно будет указать его так:
System.Windows.Forms.Control dest = Gimme<int, System.Windows.Forms.Button>(5);
4 ответа
Simon White из Catalysoft написал статью об очень умном алгоритме, который сравнивает пар смежного символа, который работает действительно хорошо на мои цели:
http://www.catalysoft.com/articles/StrikeAMatch.html
у Simon есть версия Java алгоритма, и ниже я записал МН версию / версию Ruby ее (взятый от простой рубиновой версии, сделанной в связанном комментарии записи форума Mark Wong-VanHaren) так, чтобы я мог использовать ее в своих запросах PostgreSQL:
CREATE FUNCTION string_similarity(str1 varchar, str2 varchar)
RETURNS float8 AS '
str1.downcase!
pairs1 = (0..str1.length-2).collect {|i| str1[i,2]}.reject {
|pair| pair.include? " "}
str2.downcase!
pairs2 = (0..str2.length-2).collect {|i| str2[i,2]}.reject {
|pair| pair.include? " "}
union = pairs1.size + pairs2.size
intersection = 0
pairs1.each do |p1|
0.upto(pairs2.size-1) do |i|
if p1 == pairs2[i]
intersection += 1
pairs2.slice!(i)
break
end
end
end
(2.0 * intersection) / union
' LANGUAGE 'plruby';
Работы как очарование!
-
1Я надеюсь Богу он isn' t настолько простой, но если это - Вы, собираются достигнуть кекс с цукатами это Рождество! I' m слишком усталый для попытки его теперь, хотя, но первым делом с утра... благодарит за быстрый ответ! – ubiquibacon 21 August 2010 в 05:28
Что относительно расстояния Левенштейна, разделенного на длину первой строки (или альтернативно разделенный моя продолжительность минуты/макс./в среднем обеих строк)? Это работало на меня до сих пор.
-
1+1: но я использовал бы
Math.toRadians(angle)вместо* Math.PI / 180... – Carlos Heuberger 23 August 2010 в 11:28
Строковые Метрики Подобия содержат обзор многих различных метрик, используемых в сравнении строк (, Википедия имеет обзор также). Большая часть этих метрик реализована в библиотеке simmetrics.
еще один пример метрики, не включенной в данный обзор, например расстояние сжатия (пытающийся приблизиться сложность Kolmogorov ), который может использоваться некоторое время более длинные тексты, чем тот, который Вы представили.
Вы могли бы также рассмотреть рассмотрение намного более широкого предмета Обработка естественного языка . Эти пакеты R могли запустить Вас быстро (или по крайней мере дать некоторое представление).
И одно последнее редактирование - ищут другие вопросы на этом предмете в Так, существует довольно много связанных.
-
1
ответ марзагао отличный . Я преобразовал его в C #, поэтому решил разместить его здесь:
/// <summary>
/// This class implements string comparison algorithm
/// based on character pair similarity
/// Source: http://www.catalysoft.com/articles/StrikeAMatch.html
/// </summary>
public class SimilarityTool
{
/// <summary>
/// Compares the two strings based on letter pair matches
/// </summary>
/// <param name="str1"></param>
/// <param name="str2"></param>
/// <returns>The percentage match from 0.0 to 1.0 where 1.0 is 100%</returns>
public double CompareStrings(string str1, string str2)
{
List<string> pairs1 = WordLetterPairs(str1.ToUpper());
List<string> pairs2 = WordLetterPairs(str2.ToUpper());
int intersection = 0;
int union = pairs1.Count + pairs2.Count;
for (int i = 0; i < pairs1.Count; i++)
{
for (int j = 0; j < pairs2.Count; j++)
{
if (pairs1[i] == pairs2[j])
{
intersection++;
pairs2.RemoveAt(j);//Must remove the match to prevent "GGGG" from appearing to match "GG" with 100% success
break;
}
}
}
return (2.0 * intersection) / union;
}
/// <summary>
/// Gets all letter pairs for each
/// individual word in the string
/// </summary>
/// <param name="str"></param>
/// <returns></returns>
private List<string> WordLetterPairs(string str)
{
List<string> AllPairs = new List<string>();
// Tokenize the string and put the tokens/words into an array
string[] Words = Regex.Split(str, @"\s");
// For each word
for (int w = 0; w < Words.Length; w++)
{
if (!string.IsNullOrEmpty(Words[w]))
{
// Find the pairs of characters
String[] PairsInWord = LetterPairs(Words[w]);
for (int p = 0; p < PairsInWord.Length; p++)
{
AllPairs.Add(PairsInWord[p]);
}
}
}
return AllPairs;
}
/// <summary>
/// Generates an array containing every
/// two consecutive letters in the input string
/// </summary>
/// <param name="str"></param>
/// <returns></returns>
private string[] LetterPairs(string str)
{
int numPairs = str.Length - 1;
string[] pairs = new string[numPairs];
for (int i = 0; i < numPairs; i++)
{
pairs[i] = str.Substring(i, 2);
}
return pairs;
}
}