¿Cómo puedo medir la similitud entre 2 cadenas? [cerrado]
https://stackoverflow.com/questions/1034622
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Dadas dos cadenas text1 y text2
public SOMEUSABLERETURNTYPE Compare(string text1, string text2)
{
// DO SOMETHING HERE TO COMPARE
}
Ejemplos:
-
Primera cadena: StackOverflow
Segunda cadena: StaqOverflow
Retorno: la similitud es del 91%
El retorno puede estar en% o algo así.
-
Primera cadena: la prueba de texto simple
Segunda cadena: la prueba de texto complejo
Retorno: los valores pueden considerarse iguales
¿Alguna idea? ¿Cuál es la mejor manera de hacer esto?
Solución
Hay varias formas diferentes de hacer esto. Echa un vistazo a la Wikipedia " Medidas de similitud de cadenas " página para enlaces a otras páginas con algoritmos.
No creo que piense ninguno de esos algoritmos tenga en cuenta los sonidos, por lo tanto, "desbordamiento de staq" sería tan similar a "desbordamiento de pila" como " desbordamiento de staw " a pesar de que el primero es más similar en términos de pronunciación.
Acabo de encontrar otra página que ofrece bastante más opciones ... en particular, el algoritmo Soundex (< a href = "http://en.wikipedia.org/wiki/Soundex" rel = "noreferrer"> Wikipedia ) puede estar más cerca de lo que busca.
Otros consejos
La distancia de Levenshtein es probablemente lo que estás buscando.
Aquí hay un código que he escrito para un proyecto en el que estoy trabajando. Necesito saber la relación de similitud de las cadenas y la relación de similitud basada en las palabras de las cadenas. Este último, quiero saber tanto la Relación de similitud de palabras de la cadena más pequeña (por lo tanto, si todas las palabras existen y coinciden en la cadena más grande, el resultado será 100%) y la Relación de similitud de palabras de la cadena más grande (que llamo RealWordsRatio ) Yo uso el algoritmo de Levenshtein para encontrar la distancia. El código no está optimizado, hasta ahora, pero funciona como se esperaba. Espero que les sea ú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;
}
Escribí una Implementación de doble teléfono en C # hace un tiempo. Lo encontrarás muy superior a Soundex y similares.
La distancia de Levenshtein también se ha sugerido, y es un gran algoritmo para muchos usos, pero la correspondencia fonética no es realmente lo que hace; a veces solo parece así porque las palabras fonéticamente similares también se escriben de manera similar. Hice un análisis de varios algoritmos de coincidencia difusa que también puede resultarle útil.
Para tratar con 'sonidos similares', es posible que desee analizar la codificación utilizando un algoritmo fonético como Double Metaphone o soundex. No sé si calcular las distancias de Levenshtein en cadenas fonéticas codificadas sería beneficioso o no, pero podría ser una posibilidad. Alternativamente, podría usar un heurístico como: convertir cada palabra en la cadena a su forma codificada y eliminar cualquier palabra que ocurra en ambas cadenas y reemplazarlas con una sola representación antes de calcular la distancia de Levenshtein.
Puede buscar cadenas " distancias " ;, por ejemplo la distancia de Levenshtein .
El módulo Perl Text :: Phonetic tiene implementaciones de varios algoritmos.
Jeff Atwood escribió acerca de buscar una solución similar para determinar la autoría de publicaciones wiki que pueden ayudarte a acotar tu búsqueda.
Si está comparando valores en una base de datos SQL, puede usar la función SOUNDEX . Si consulta a Google para SOUNDEX y C #, algunas personas han escrito una función similar para eso y VB.
También tengo que recomendar Soundex, lo he usado en el pasado para procesar nombres de ciudades mal escritas. Aquí hay un buen enlace para su uso: http://whitepapers.zdnet.com/abstract. aspx? docid = 352953
Si desea comparar fonéticamente, consulte los algoritmos Soundex y Metaphone: http://www.blackbeltcoder.com/Articles/algorithms/phonetic-string-comparison-with-soundex
Metaphone 3 es la tercera generación del algoritmo Metaphone. Eso aumenta la precisión de la codificación fonética del 89% de Double Metaphone a 98% , según lo probado en una base de datos de los más comunes Palabras inglesas, y nombres y palabras no inglesas familiares en el norte America. Esto produce una codificación fonética extremadamente confiable para Pronunciaciones americanas.
Metaphone 3 fue diseñado y desarrollado por Lawrence Philips, quien diseñó y desarrolló el original Metaphone y Double Metaphone algoritmos.
