Como posso medir a semelhança entre 2 cordas? [fechado
https://stackoverflow.com/questions/1034622
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Dada duas cordas text1 e text2
public SOMEUSABLERETURNTYPE Compare(string text1, string text2)
{
// DO SOMETHING HERE TO COMPARE
}
Exemplos:
Primeira String: Stackoverflow
Segunda String: Staqoverflow
Retorno: a semelhança é 91%
O retorno pode estar em % ou algo assim.
Primeira sequência: o teste de texto simples
Segunda sequência: o teste de texto complexo
Retorno: os valores podem ser considerados iguais
Alguma ideia? Qual é a melhor maneira de fazer isso?
Solução
Existem várias maneiras diferentes de fazer isso. Dê uma olhada no Página "Medidas de similaridade de cordas" da Wikipedia Para links para outras páginas com algoritmos.
Eu não acho Qualquer um desses algoritmos leva em consideração sons, no entanto - portanto, o "Overflow Staq" seria tão semelhante a "Stack Overflow" quanto "Staw Overflow", apesar do primeiro ser mais semelhante em termos de pronúncia.
Acabei de encontrar outra página o que oferece mais opções ... em particular, o SoundEx algoritmo (Wikipedia) pode estar mais próximo do que você procura.
Outras dicas
Distância de Levenshtein é provavelmente o que você está procurando.
Aqui está algum código que escrevi para um projeto em que estou trabalhando. Preciso conhecer a taxa de similaridade das cordas e a taxa de similaridade com base nas palavras das cordas. Este último, quero saber a razão de similaridade das palavras da menor corda (por isso ). Eu uso o algoritmo Levenshtein para encontrar a distância. O código não está otimizado, até agora, mas funciona como esperado. Espero que você ache isso útil.
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;
}
Eu escrevi a Implementação de metapalo duplo em C# um tempo atrás. Você achará muito superior ao SoundEx e similares.
A distância de Levenshtein também foi sugerida e é um ótimo algoritmo para muitos usos, mas a correspondência fonética não é realmente o que faz; Às vezes, parece assim, porque as palavras foneticamente semelhantes também geralmente são soletradas da mesma forma. Eu fiz um Análise de vários algoritmos de correspondência difusa que você também pode achar útil.
Para lidar com o 'som Alikes', você pode querer procurar a codificação usando um algoritmo fonético como metaphone duplo ou SoundEx. Não sei se a computação de distâncias de Levenshtein em cordas codificadas fonéticas seria benéfica ou não, mas pode ser uma possibilidade. Como alternativa, você pode usar uma heurística como: converter cada palavra na string em sua forma codificada e remover quaisquer palavras que ocorram em ambas as cordas e substituí -las por uma única representação antes de calcular a distância de Levenshtein.
Você pode procurar por string "distâncias", por exemplo A distância de Levenshtein.
Módulo Perl Texto :: fonético tem implementações de vários algoritmos.
Jeff Atwood escreveu sobre procurar uma solução semelhante Para determinar a autoria de postagens wiki que podem ajudá -lo a restringir sua pesquisa.
Se você estiver comparando valores em um banco de dados SQL, você pode usar o SoundEx função. Se você consultar o Google para SoundEx e C#, algumas pessoas escreveram uma função semelhante para isso e VB.
Eu também tenho que recomendar o SoundEx, usei -o no passado para processar nomes de cidades incorretas. Aqui está um bom link para uso: http://whitepapers.zdnet.com/abstract.aspx?docid=352953
Se você deseja comparar foneticamente, confira os algoritmos SoundEx e Metaphone: http://www.blackbeltcoder.com/articles/algorithms/phonetic-string-comparison-with-soundex
Metaphone 3 é a terceira geração do algoritmo metaphone. Aumenta a precisão da codificação fonética dos 89% da dupla metafone para 98%, conforme testado em um banco de dados das palavras em inglês mais comuns e nomes e palavras não inglesas familiares na América do Norte. Isso produz uma codificação fonética extremamente confiável para as pronúncias americanas.
O Metaphone 3 foi projetado e desenvolvido por Lawrence Philips, que projetou e desenvolveu os algoritmos originais de metapona e metapona dupla.
