levenshtein-distance - textos - fuzzy search php
Compara algoritmos de similitud (2)
Ampliando mi comentario wiki-walk en la errata y tomando nota de la bibliografía de la planta baja sobre la comparabilidad de los algoritmos que se aplican a espacios con problemas similares, 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 de Jaro (Jaro, 1989, 1995) y principalmente [cita requerida] utilizada en el área de vinculación de registros (detección de duplicados). Cuanto mayor es la distancia Jaro-Winkler para dos cadenas, más similares son las cadenas. La métrica de distancia Jaro-Winkler está diseñada y es más adecuada para cadenas cortas, como nombres de personas. El puntaje se normaliza de manera que 0 equivale a ninguna similitud y 1 es una coincidencia exacta.
En teoría de la información y ciencias de la computación, la distancia de Levenshtein es una métrica de cuerda para medir la cantidad de diferencia entre dos secuencias. El término distancia de edición a menudo se usa para referirse específicamente a la distancia de Levenshtein.
La distancia de Levenshtein entre dos cadenas se define como el número mínimo de ediciones necesarias para transformar una cadena en la otra, con las operaciones de edición permitidas como inserción, eliminación o sustitución de un solo carácter. Lleva el nombre de Vladimir Levenshtein, quien consideró esta distancia en 1965.
En matemáticas, la distancia euclidiana o métrica euclidiana es la distancia "ordinaria" entre dos puntos que uno mediría con una regla, y está dada por la fórmula pitagórica. 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.
En los campos de la lingüística computacional y la probabilidad, un n-gram es una secuencia contigua de n elementos 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. Los n-gramas se recopilan a partir de un corpus de texto o voz.
Las dos ventajas principales de los modelos de n-gramas (y los algoritmos que los usan) son la simplicidad relativa y la capacidad de escalar; simplemente aumentando el modelo se puede usar para almacenar más contexto con un compromiso de espacio-tiempo bien entendido, permitiendo pequeñas experimentos para escalar de manera muy eficiente.
El problema es que estos algoritmos resuelven diferentes problemas que tienen diferente aplicabilidad dentro del espacio de todos los algoritmos posibles para resolver el problema de subsecuencia común más largo , en sus datos o en injertar una metric utilizable de los mismos. De hecho, no todas estas son métricas , ya que algunas de ellas no satisfacen la desigualdad del triángulo .
En lugar de desviarse de su camino para definir un esquema dudoso para detectar daños en los datos, hágalo correctamente: utilizando checksums y bits de paridad para sus datos. No intente resolver un problema mucho más difícil cuando lo haga una solución más simple.
Quiero usar funciones de similitud de cadenas para encontrar datos corruptos en mi base de datos.
Me encontré con varios de ellos:
- Jaro,
- Jaro-Winkler,
- Levenshtein,
- Euclidiano y
- Q-gram,
Quería saber cuál es la diferencia entre ellos y en qué situaciones funcionan mejor?
La similitud de cadenas ayuda de muchas maneras diferentes. Por ejemplo
- Google quería decir que los resultados se calculan utilizando la similitud de cadenas.
- la similitud de cadena se usa para corregir errores de OCR.
- la similitud de cadena se usa para corregir los errores de ingreso del teclado.
- la similitud de cadenas se usa para encontrar la secuencia más parecida de dos ADN en bioinformática.
Pero como un tamaño no cabe 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 char que cambias para hacer dos cadenas iguales.
kitten → sitten
Aquí la distancia es 1 cambio de personaje. 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 "métrica de distancia is está diseñado y es más adecuado para cadenas cortas como nombres de personas"
Por lo tanto, debes tener en cuenta tu problema.
Quiero usar funciones de similitud de cadenas para encontrar datos corruptos en mi base de datos.
¿Cómo se corrompen sus 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?