Investigación y pruebas
Probamos varios algoritmos para comparar cadenas y seleccionamos el que mejor se ajustara a nuestras necesidades.
Comparamos la cadena A y la cadena B para tener métricas en los diferentes algoritmos.
Las reglas para la similitud de cadenas pueden diferir de un caso a otro. Si quieres considerar «nicho» y «chien» similares, usarías un algoritmo de similitud de cadenas que detecta anagramas. No en nuestro caso. Es muy probable que una aplicación llamada «nicho» y otra llamada «chien» sean dos aplicaciones completamente diferentes.
Después de una lluvia de ideas e investigación, se nos ocurrieron algunos métodos de algoritmos que ayudarían a nuestro caso. El algoritmo de Coseno demostró ser irrelevante para nosotros, ya que, por ejemplo, no parece tener en cuenta el orden de las letras, lo que conduce a un índice de 1 (cadena similar) en un anagrama («nicho» y «chien»).
Esto es lo que notamos:
Algoritmo de Levenshtein
La distancia de Levenshtein es el número mínimo de ediciones de un solo carácter necesarias para cambiar una palabra a la otra, por lo que el resultado es un entero positivo, sensible a la longitud de la cadena . Lo que hace que sea más difícil dibujar un patrón.
Por ejemplo,
- la distancia de Levenshtein entre» foo «y» bar «es de 3
- la distancia de Levenshtein entre» bellezas «y» hermosas «también es de 3
- Para nosotros, los humanos, el par»bellezas»/» hermosas «es mucho más similar que el par»foo»/» bar». Pero la distancia de Levenshtein es la misma.
La métrica que estamos usando aquí es la inversa de la distancia de Levenshtein (1 / levenshtein_distance), por lo que el resultado es un porcentaje y es más fácil de leer por nosotros. Pero el problema mencionado anteriormente seguía siendo el mismo.
Donde 1 es el resultado de comparar cadenas idénticas, «ShazamIphone» y «ShazamAndroid» tienen una similitud de 0,167. «chien» y «niche» tienen una similitud de 0,25.
Así que desde el punto de vista del algoritmo de Levenshtein, Chien/Niche son más similares que «ShazamIphone»/»ShazamAndroid» porque se necesitan menos ediciones para pasar de «chien» a «niche», que para pasar de «ShazamIphone» a «ShazamAndroid».
Comparación de trigramas
Un algoritmo de trigramas es un caso de n-gramo, una secuencia contigua de n (tres, en este caso) elementos de una muestra dada. En nuestro caso, un nombre de aplicación es una muestra y un carácter es un elemento.
Así que la secuencia «martha» tiene 4 trigramas { mar art rth tha}.
Podemos usar el método Trigrama para comparar dos cadenas.
Tomando por ejemplo «martha» y la misma palabra con un error tipográfico, «marhta», y podemos calcular sus trigramas:
Trigramas «martha»: { mar art rth tha }
Trigramas «marhta»: { mar arh rht hta }
Para medir la similitud dividimos el número de trigramas coincidentes en ambas cadenas: 1 { mar } por el número de trigramas únicos: 7 { mar art rth tha arh rht hta }
The result is 1/7 = 14%
Para equilibrar la desventaja de los caracteres externos (para reforzar la similitud de las cadenas que comienzan y terminan con los mismos trigramas), rellenamos la cadena con espacios en blanco a cada lado, lo que resulta en estos casos en tres trigramas más «_ma», «ha_» y «ta_».
Trigramas «martha»: { _ma mar art rth tha ha_ }
Trigramas «marhta»: { _ma mar arh rht hta ta_ }
Una vez hecho esto, el número de trigramas coincidentes es de hasta: 2 { _ma mar}
El número de todos los trigramas únicos: 9 {_ma mar art rth tha arh rht hta ha_ }
The result is now 2/9 = 22%
Usando este método para comparar «Twitter v1» y «Twitter v2» tenemos:
El número de trigramas coincidentes: 7 { _tw twi wit itt tte ter er_ }
El número de todos los trigramas únicos: 11 { tw twi wit itt tte ter er_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
El límite del método de trigramas para comparar cadenas es que las cadenas cortas con una (o dos)..) los trigramas diferentes tienden a producir una similitud menor que los largos.
Así es como obtenemos un 0.2 similitud entre» ShazamAndroid «y» ShazamIphone», ya que tienen trigramas más diferentes.
El número de trigramas coincidentes es: 5 { _sh sha haz aza zam}
El número de todos los trigramas únicos: 20
Como hay una fuerte dependencia con la longitud de la cadena, no nos proporciona una buena comparación.
Algoritmo Jaro-Winkler
«En informática y estadística, la distancia Jaro-Winkler es una métrica de cadena para medir la distancia de edición entre dos secuencias.
Informalmente, la distancia Jaro entre dos palabras es el número mínimo de transposiciones de un solo carácter requeridas para cambiar una palabra a la otra.
La distancia Jaro-Winkler utiliza una escala de prefijo que da calificaciones más favorables a las cadenas que coinciden desde el principio para una longitud de prefijo establecida»
Fuente: Wikipedia.
Dar «más importancia» a palabras con prefijos idénticos hizo que la distancia Jaro-Winkler pareciera muy interesante para nuestro caso de uso.
A partir del principio con la fórmula de distancia Jaro, aquí cómo funciona. No te asustes, vamos paso a paso:
La Distancia Jaro entre dos secuencias s1 y s2 se define por:
dj es la distancia Jaro
m es el número de caracteres coincidentes (caracteres que aparecen en s1 y en s2)
t es la mitad del número de transposiciones (compare el i-ésimo carácter de s1 y el i-ésimo carácter de s2 dividido por 2)
|s1| es la longitud de la primera cadena
|s2| es la longitud de la segunda cadena
Con un ejemplo. Tomemos «martha » y»marhta».
m = 6
t = 2/2 =1 (2 couples of non matching characters, the 4-th and 5-th) { t/h ; h/t }
|s1| = 6
|s2| = 6
Simplemente reemplazando los números es la fórmula, obtenemos:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
Ahora que sabemos cuál es la distancia Jaro, saltemos a la distancia Jaro-Winkler.
La similitud Jaro-Winkler utiliza una escala de prefijo p que da calificaciones más favorables a las cadenas que coinciden desde el principio para una longitud de prefijo establecida l.
p es un factor de escala constante para cuánto se ajusta la puntuación hacia arriba para tener prefijos comunes. El valor estándar para esta constante en el trabajo de Winkler es p=0.1.
l es la longitud del prefijo común al comienzo de la cadena (hasta un máximo de 4 caracteres).
Así que volvamos al ejemplo de «martha» / «marhta», tomemos una longitud de prefijo de l = 3 (que se refiere a»mar»). Llegamos a:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
Usando la fórmula de JaroWinkler, pasamos de la distancia de Jaro al 94% de similitud al 96%.
En nuestro caso, la mayoría de las aplicaciones similares comienzan con el mismo prefijo («twitter v1» vs «twitter v2″o» ShazamIphone » vs «ShazamAndroid», etc. Consulte la tabla de pruebas de algoritmos de arriba). Por lo tanto, es un criterio importante a tener en cuenta.
