algorithm - levenshtein - ¿Cuáles son algunos algoritmos para comparar cuán similares son dos cadenas?
algoritmos para comparar textos (3)
Lo que estás buscando se llama algoritmos de métrica String . Hay un número significativo de ellos, muchos con características similares. Entre los más populares:
- Distancia Levenshtein : la cantidad mínima de ediciones de un solo carácter requeridas para cambiar una palabra por otra. Las cadenas no tienen que ser del mismo largo
- Hamming Distance : el número de caracteres que son diferentes en dos cadenas de igual longitud.
- Smith-Waterman : una familia de algoritmos para calcular similitudes de subsecuencias variables.
- Coeficiente Sørensen-Dice : Algoritmo de similitud que calcula los coeficientes de diferencia de pares de caracteres adyacentes.
Echa un vistazo a estos y otros en la página wiki sobre el tema.
Necesito comparar cadenas para decidir si representan lo mismo. Esto se relaciona con los títulos de casos ingresados por humanos, donde las abreviaturas y otros detalles pequeños pueden diferir. Por ejemplo, considere los siguientes dos títulos:
std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP";
Opuesto a:
std::string second = "Harper v. The Law Offices of Huey & Luey, LLP";
Un humano puede medir rápidamente que estos son probablemente uno y el mismo. El enfoque actual que he tomado es para normalizar las cadenas al minúsculas de todas las letras y eliminar todos los signos de puntuación y espacios que dan:
std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp";
Y:
std::string secondNormalized = "harpervthelawofficesofhueylueyllp";
Comparando en este caso, una es una subsecuencia de la otra, pero puedes imaginar otras variaciones más complejas donde eso no ocurre necesariamente, sin embargo, tienen subsecuencias significativas en común. También podría haber errores de entrada humanos ocasionales, como letras transpuestas y errores de ortografía.
Tal vez algún tipo de programa de diferencias de caracteres podría ayudar? He visto buenos programas de diferencias de línea para comparar las diferencias en el código que se va a controlar, ¿hay algo así por carácter, tal vez en impulso? Si pudieras contar el número de caracteres consecutivos en común y tomar la proporción de los caracteres no compartidos, ¿quizás sería una buena heurística?
Al final, necesito una decisión booleana sobre si considerarlos igual o no. No tiene que ser perfecto, pero lo ideal es que raramente sea incorrecto.
¿Qué algoritmo puedo usar que me dará algún tipo de cuantificación en cuanto a cuán similares son las dos cadenas el uno con el otro, que luego puedo convertir en una respuesta sí / no por medio de alguna heurística?
Puedes usar ngrams para eso. Por ejemplo, transforma las dos cadenas en trigramas de palabras (generalmente minúsculas) y compara el porcentaje de ellas que son iguales entre sí.
Su desafío es definir un porcentaje mínimo de similitud.
La distancia Damerau Levenshtein es otro algoritmo para comparar dos cadenas y es similar al algoritmo de distancia de Levenshtein. La diferencia entre los dos es que también puede verificar transposiciones entre caracteres y, por lo tanto, puede dar un mejor resultado para la corrección de errores.
Por ejemplo: La distancia de Levenshtein entre la night y la nigth es 2, pero Damerau Levenshtein, la distancia entre la night y la nigth será 1 porque es solo un intercambio de un par de caracteres.