ALGORITMOS DE SIMILITUD ENTRE CADENAS DE TEXTO (PHP) [1] [2]



Normalizar [3]


Coeficientes
Valor directo [13] Similitud [14]
Coeficiente Rogers-Tanimoto [4] [a]
Distancia Levenshtein (adaptada para textos > 255 cars.) [5]
Distancia entre claves Metaphone [6]
Similar-Text [7]
Similitud coseno (Cosine Similarity) [8]
Coeficiente de Similitud de Jaccard [9] [b]
Coeficiente de Sorensen-Dice [10] [c]
Coeficiente de Ochiai [11] [d]
Distancia de Jaro [12]
Distancia de Jaro-Winkler [12]
Distancia de Hamming [15]
Similitud de n-gramas [16]


EJEMPLOS (Valores directos. El valor de la izquierda es sin normalizar, el de la derecha normalizado)
Texto 1 Texto 2 Dst. Levenshtein Similar-Text Similitud coseno Coeficiente Jaccard
El metro es una unidad de distancia equivalente a 100 centimetros y que fue establecido en el siglo XVIII. En el siglo XVII se creó el metro como unidad de distancia, que vale 100 centímetros. 81 | 41 53,89% | 64,35% 0,41 | 0,70 0,26 | 0,54
El átomo es la partícula mínima que compone los cuerpos. Esta formado por protones, electrones y neutrones. El átomo es una partícula compuesta por protones y electrones. 52 | 25 68,97% | 73,27% 0,46 | 0,65 0,29 | 0,45
Un algoritmo es un conjunto de instrucciones que al ejecutarse resuelven un problema computacional. Algoritmo es un grupo de instrucciones para resolver problemas filosóficos. 44 | 27 65,14% | 69,57% 0,35 | 0,53 0,21 | 0,36
La filosofia es el conjunto de reflexiones sobre la esencia, las propiedades, las causas y los efectos de las cosas naturales, especialmente sobre el hombre y el universo. La filosofia es la investigacion sobre la esencia y las causas de las cosas naturales y su influencia en el hombre y el universo. 68 | 36 70% | 69,57% 0,65 | 0,7 0,48 | 0,53
La brújula es un instrumento para orientarse que consiste en una caja cuyo fondo representa la rosa de los vientos y en la cual hay una aguja imantada que gira libremente sobre un eje. La brujula es una bola con un imán que marca el norte. 142 | 73 23,33% | 25,42% 0,27 | 0,2 0,14 | 0,1
La dialéctica es la ciencia del conocimiento supremo. La mayeutica es la diestra del cimiento superior. 18 | 18 73,79% | 50,85% 0,50 | 0,2 0,33 | 0,11

EJEMPLOS (cont.)
Texto 1 Texto 2 Coeficiente de Sorensen-Dice Coeficiente Rogers-Tanimoto Coeficiente de Ochiai Distancia claves metaphone
El metro es una unidad de distancia equivalente a 100 centimetros y que fue establecido en el siglo XVIII. En el siglo XVII se creó el metro como unidad de distancia, que vale 100 centímetros. 0,41 | 0,70 0,15 | 0,37 0,41 | 0,70 31 | 22
El átomo es la partícula mínima que compone los cuerpos. Esta formado por protones, electrones y neutrones. El átomo es una partícula compuesta por protones y electrones. 0,44 | 0,63 0,17 | 0,29 0,46 | 0,65 21 | 14
Un algoritmo es un conjunto de instrucciones que al ejecutarse resuelven un problema computacional. Algoritmo es un grupo de instrucciones para resolver problemas filosóficos. 0,35 | 0,53 0,12 | 0,22 0,35 | 0,53 21 | 13
La filosofia es el conjunto de reflexiones sobre la esencia, las propiedades, las causas y los efectos de las cosas naturales, especialmente sobre el hombre y el universo. La filosofia es la investigacion sobre la esencia y las causas de las cosas naturales y su influencia en el hombre y el universo. 0,65 | 0,7 0,32 | 0,36 0,65 | 0,7 29 | 19
La brújula es un instrumento para orientarse que consiste en una caja cuyo fondo representa la rosa de los vientos y en la cual hay una aguja imantada que gira libremente sobre un eje. La brujula es una bola con un imán que marca el norte. 0,24 | 0,18 0,07 | 0,05 0,27 | 0,2 61 | 37
La dialéctica es la ciencia del conocimiento supremo. La mayeutica es la diestra del cimiento superior. 0,50 | 0,2 0,2 | 0,06 0,50 | 0,2 9 | 8

EJEMPLOS (cont.)
Texto 1 Texto 2 Distancia de Jaro Distancia de Jaro-Winkler Distancia Hamming
El metro es una unidad de distancia equivalente a 100 centimetros y que fue establecido en el siglo XVIII. En el siglo XVII se creó el metro como unidad de distancia, que vale 100 centímetros. 0,69 | 0,72 0,72 | 0,75 101 | 59
El átomo es la partícula mínima que compone los cuerpos. Esta formado por protones, electrones y neutrones. El átomo es una partícula compuesta por protones y electrones. 0,71 | 0,75 0,83 | 0,85 93 | 45
Un algoritmo es un conjunto de instrucciones que al ejecutarse resuelven un problema computacional. Algoritmo es un grupo de instrucciones para resolver problemas filosóficos. 0,68 | 0,73 95 | 0,84 95 | 55
La filosofia es el conjunto de reflexiones sobre la esencia, las propiedades, las causas y los efectos de las cosas naturales, especialmente sobre el hombre y el universo. La filosofia es la investigacion sobre la esencia y las causas de las cosas naturales y su influencia en el hombre y el universo. 0,76 | 0,76 0,85 | 0,85 148 | 78
La brújula es un instrumento para orientarse que consiste en una caja cuyo fondo representa la rosa de los vientos y en la cual hay una aguja imantada que gira libremente sobre un eje. La brujula es una bola con un imán que marca el norte. 0,62 | 0,59 0,77 | 0,75 174 | 84
La dialéctica es la ciencia del conocimiento supremo. La mayeutica es la diestra del cimiento superior. 0,74 | 0,65 0,81 | 0,69 51 | 29


NOTAS:

[1] Estos algoritmos calculan la distancia o la similitud entre dos cadenas de texto en términos:
    a) del número de transformaciones que deben hacerse en una cadena para obtener la otra (distancia Levenshtein, Hamming y Similar-Text)
    b) del ángulo entre los vectores de ambas cadenas (Similitud Coseno).
    c) de la distancia entre las claves fonéticas entre las dos cadenas (Metaphone).
    d) del grado de 'comunalidad', esto es, términos únicos compartidos, entre las cadenas comparadas (coeficientes de Jaccard, Ochiai, Rogers-Tanimoto y Sorensen-Dice).
    e) del grado de coincidencia entre los caracteres de las cadenas comparadas (distancias de Jaro y Jaro-Wincker. La normalización de esta métrica es inversa, de manera que el valor 0 indica máxima similitud y el valor 1 ausencia total de similitud).
Se trata de algoritmos sintácticos o fonéticos, que no consideran el significado de las oraciones, lo que explica algunos resultados.
Téngase en cuenta al interpretar los algoritmos que los valores de distancia, excepto en Jaro y Jaro-Wincker, son la inversa de los valores de similitud. Esto es, en general: Distancia = 1 - Similitud.
Por otra parte, la 'granularidad' de los distintos coeficientes es diferente. Algunos actúan sobre palabras completas y otros sobre caracteres individuales. Para más información véanse las referencias de cada coeficiente.
Se ha añadido una función de simetría para aquellos algoritmos en los que el orden de comparación alteraba los resultados (p. ej. Levenshtein o Hamming) dado que el interés aquí es la comparación absoluta de cadenas, independientemente de su posición.

[2] Puede verse una exhaustiva relación de coeficientes de asociación, orientados a la ecología, en: https://books.google.es/books/about/Coeficientes_de_Asociaci%C3%B3n.html?id=hitW9gbEGwoC&hl=es

[3] La normalización aplica las siguientes funciones a las cadenas originales: paso a minúsculas, eliminación de acentos y caracteres especiales. Resta de stopwords. Lexematización (stemming).

[4] Para la distancia Rogers-Tanimoto véanse:
https://books.google.es/books/about/Coeficientes_de_Asociaci%C3%B3n.html?id=hitW9gbEGwoC&hl=es
http://www.scielo.br/scielo.php?script=sci_arttext&pid=S1415-47571999000300024
Este algoritmo pondera doblemente las discordancias, por lo que obtiene resultados más bajos a medida que aumentan éstas (normalmente cuanto más largos y dispares son los textos).

[5] Para la Distancia Levenshtein véanse:
https://es.wikipedia.org/wiki/Distancia_de_Levenshtein
http://php.net/manual/es/function.levenshtein.php
https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance

[6] Para el algoritmo Metaphone véase:
http://php.net/manual/es/function.metaphone.php
Este algoritmo es de tipo fonético. Se basa en el cálculo de las distancias Levenshtein entre las transcripciones fónicas de las cadenas de entrada.

[7] Para el algoritmo Similar-text véase:
http://php.net/manual/es/function.similar-text.php
Nótese que Similar-Text puede devolver de forma nativa tanto la distancia entre las cadenas como el porcentaje de similitud. En nuestro ejemplo se muestra el porentaje.

[8] Para la Similitud del Coseno véanse:
https://es.wikipedia.org/wiki/Similitud_coseno
https://github.com/aoiaoi/CosineSimilarity
Para una discusión del algoritmo utilizado aquí, ver: http://stackoverflow.com/questions/945724/cosine-similarity-vs-hamming-distance
Este algoritmo convierte las dos cadenas de entrada en representaciones en el espacio vectorial y luego calcula el valor del coseno del ángulo formado por dichos vectores. Es un algoritmo fundamental en PLN.

[9] Para la Similitud de Jaccard véase:
https://en.wikipedia.org/wiki/Jaccard_index
Este algoritmo, llamado también índice de Jaccard, mide la "comunalidad" entre las cadenas de entrada. Pondera igualmente las concordancias y las discordancias. Se trata de un coeficiente binario (booleano) que considera sólo la presencia/ausencia de términos en las cadenas. Por su parte, la "distancia de Jaccard" se obtiene restando de 1 el valor del coeficiente.

[10] Para la Similitud de Sorensen-Dice véase:
https://en.wikipedia.org/wiki/S%C3%B8rensen%E2%80%93Dice_coefficient
Este algoritmo, como el anterior, mide la "comunalidad" entre las cadenas de entrada. La diferencia es que éste otorga doble valor a las concordancias. Otras denominaciones son: coeficiente de Dice, índice de Sorensen o índice binario de Czekanowski. Se trata de un coeficiente binario (booleano) que considera sólo la presencia/ausencia de términos en las cadenas. Por su parte, el complemento del coeficiente de Sorensen-Dice se denomina índice de disimilitud de Bray-Curtis, de tal modo que: B-C(i) = 1 - SD(i). El coeficiente de Sorensen-Dice arroja rsultados muy parecidos a la Similitud del Coseno y el coeficiente de Ochiai.

[11] Para el coeficiente de Ochiai véanse:
http://www-01.ibm.com/support/knowledgecenter/SSLVMB_20.0.0/com.ibm.spss.statistics.help/cmd_proximities_sim_measure_binary.htm?lang=es
https://books.google.es/books/about/Coeficientes_de_Asociaci%C3%B3n.html?id=hitW9gbEGwoC&hl=es
Este algoritmo es equivalente a la Similitud del Coseno para datos binarios y con un menor coste computacional.

[12] Para las distancias de Jaro y de Jaro-Winkler, véase:
https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance
Este algoritmo, utilizado sobre todo en detección de duplicidades, funciona a nivel de caracteres, considerando también un coeficiente de transposición (t) que puede definirse de antemano o bien dejar que el algoritmo lo calcule automáticamente.

[13] El valor directo de cada coeficiente es el que se obtiene aplicando su fórmula de cálculo, sin ningún tipo de transformación posterior.

[14] El valor de similitud de cada coeficiente es el que se obtiene al normalizar su valor directo. Este valor permite una comparación inmediata entre todos los coeficientes, dado que los sitúa en intervalo 0-1, siendo 0 el valor de mínima similitud y 1 el valor de máxima similitud.

[15] Para la distancia Hamming, véase:
https://es.wikipedia.org/wiki/Distancia_de_Hamming
Este algoritmo se adapta mejor al análisis de cadenas cortas, tales como palabras o nombres de personas, ya que funciona a nivel de caracteres.

[16] Este algoritmo calcula los n-gramas, en este caso los trigramas, comunes a ambas cadenas.


REFERENCIAS DE LOS COEFICIENTES:

[a] Rogers, D.J. and Tanimoto, T.T. (1960). A computer program for classifying plants. Science 132: 1115-1118.
[b] Jaccard, P. (1901). Étude comparative de la distribution florale dans une portion des Alpes et des Jura. Bull. Soc. Vaudoise Sci. Nat. 37: 547-579.
[c] Dice, L.R. (1945). Measures of the amount of ecologic association between species. Ecology 26: 297-302.
[d] Ochiai, A. (1957). Zoogeographic studies on the soleoid fishes found in Japan and its neighbouring regions. Bull. Jpn. Soc. Sci. Fish. 22: 526-530.



Francesc Llorens. 2015