Comparar algoritmos de similitud

Question

Quiero utilizar funciones de similitud de cadenas para encontrar datos dañados en mi base de datos.

me encontré con varios de ellos:

• Jaro,
• Jaro-Winkler,
• Levenshtein,
• euclidiana y
• Q-gramo,

I quería saber cuál es la diferencia entre ellos y en qué situaciones funcionan mejor?

Answer 1

Ampliando mi comentario wiki-walk en la errata y noting some of the ground-floor literature on the comparability of algorithms that apply to similar problem spaces, exploremos la aplicabilidad de estos algoritmos antes de determinar si son numéricamente comparables.

De Wikipedia, Jaro-Winkler:

En informática y estadística, la distancia Jaro-Winkler (Winkler, 1990) es una medida de similitud entre dos cadenas.Es una variante de la métrica de distancia Jaro (Jaro, 1989, 1995) y principalmente [citación necesitada] utilizada en el área del enlace de registro (detección duplicada ). Cuanto mayor sea la distancia de Jaro-Winkler para dos cadenas, , más similares son las cadenas. La métrica de distancia Jaro-Winkler es diseñada y más adecuada para cadenas cortas como nombres de personas. La puntuación está normalizada de forma que 0 equivale a sin similitud y 1 es una coincidencia exacta .

Levenshtein distance:

En teoría de la información y la informática, la distancia Levenshtein es una cadena métrica para medir la cantidad de diferencia entre dos secuencias . El término editar distancia se usa a menudo para referirse específicamente a a distancia Levenshtein.

La distancia Levenshtein entre dos cadenas se define como el mínimo número de ediciones necesarias para transformar una cadena en la otra, con las operaciones de edición permisibles siendo inserción, deleción, o sustitución de un solo carácter. Lleva el nombre de Vladimir Levenshtein, que considera esta distancia en 1965.

Euclidean distance:

En matemáticas, la distancia euclídea o la métrica euclidiana es la distancia "ordinario" entre dos puntos que uno medir con una regla , y está dada por la fórmula de Pitágoras. Al usar esta fórmula como distancia, el espacio euclidiano (o incluso cualquier espacio de producto interno) se convierte en un espacio métrico. La norma asociada se llama norma euclidiana. La literatura anterior se refiere a la métrica como métrica pitagórica.

Y Q- or n-gram encoding:

En los campos de la lingüística computacional y probabilidad, un n-gram es una secuencia contigua de n elementos a partir de una secuencia dada de texto o discurso. Los ítems en cuestión pueden ser fonemas, sílabas, letras, palabras o pares de bases según la aplicación. n-grams son recopilados de un corpus de texto o voz.

Los dos núcleo ventajas de los modelos n-gram (y algoritmos que utilizan ellos) son la sencillez relativa y la capacidad de escalar hacia arriba - por simplemente creciente na modelo puede ser utilizado para almacenar más contexto con una bien entendió por la compensación del espacio-tiempo, permitiendo experimentos pequeños a escalar de manera muy eficiente.

El problema es que estos algoritmos resolver diferentes problemas que tienen diferentes aplicabilidad dentro del espacio de los algoritmos posibles para resolver el problema longest common subsequence, en sus datos o en injertar un utilizable metric de los mismos. De hecho, no todos estos son incluso métricas, ya que algunos de ellos no satisfacen el triangle inequality.

En lugar de salir de su manera de definir un esquema de dudosa para detectar la corrupción de datos, hacer esto correctamente: mediante el uso de checksums y parity bits para sus datos. No intente resolver un problema mucho más difícil cuando lo haga una solución más simple.

Answer 2

La similitud de cadenas ayuda de diferentes maneras. Por ejemplo,

• google's quiso decir que los resultados se calculan utilizando la similitud de cadenas.
• similitud de cadena se utiliza para corregir errores de OCR.
• similitud de cadena se utiliza para corregir los errores de entrada del teclado.
• similitud de cadena se utiliza para encontrar la secuencia más coincidente de dos ADN en bioinformática.

Pero como una talla no sirve para todos. Cada algoritmo de similitud de cadena está diseñado para un uso específico, aunque la mayoría de ellos son similares. Por ejemplo, Levenshtein_distance es la cantidad de caracteres que cambia para hacer dos cadenas iguales.

kitten → sitten 

Aquí la distancia es de 1 cambio de caracteres. Puede dar diferentes pesos a la eliminación, adición y sustitución. Por ejemplo, los errores de OCR y los errores de teclado dan menos peso para algunos cambios. OCR (algunos caracteres son muy similares a otros), el teclado algunos caracteres están muy cerca el uno del otro. La similitud de la cadena bioinformática permite una gran cantidad de inserción.

Su segundo ejemplo de "Jaro–Winkler distancia métrica está diseñado y el más adecuado para cadenas cortas tales como nombres de personas"

Por lo tanto usted debe mantener en su mente acerca de su problema.

Quiero utilizar funciones de similitud de cadenas para encontrar datos dañados en mi base de datos.

¿Cómo se corrompen los datos? ¿Es un error de usuario, similar al error de entrada del teclado? ¿O es similar a los errores de OCR? ¿O algo completamente diferente?