Actualmente se puede encontrar software que cuenta con funcionalidades que pueden ser aplicadas para realizar cruce de listas. Uno de estos software es OpenRefine, el cual permite encontrar similitudes en cadenas de texto a partir de varias técnicas como la aproximación fonética y los conglomerados.
OpenRefine
El sitio web de OpenRefine (anteriormente llamado Google Refine) describe dicho software como una potente herramienta para trabajar con datos no estructurados, permitiéndole al usuario limpiarlos, transformarlos de un formato a otro y brindándole la posibilidad de vincularlos a otras bases de datos.
El software funciona bajo la licencia BSD, la cual es parte de una familia de software libre que impone restricciones mínimas a su distribución. El programa puede ser descargado sin costo en la siguiente dirección: http://openrefine.org/.
Técnicas de agrupación textual
De acuerdo con OpenRefine, las técnicas de agrupación textual hacen referencia a la operación de ‘‘búsqueda de grupos de valores diferentes que podrían ser representaciones alternativas de una misma categoría o nombre’’. Por ejemplo, es muy probable que las dos cadenas de texto ‘Nueva York’ y ‘nueva york’ se refieran al mismo concepto, pues solo hay diferencias con las mayúsculas. Del mismo modo, ‘Gödel’ y ‘Godel’ probablemente se refieran a la misma persona.
Algoritmos utilizados por la herramienta
OpenRefine tiene a su disposición una serie de algoritmos y técnicas de agrupación para encontrar coincidencias entre palabras y frases que tengan cierto nivel de similitud. A continuación infolaft hace una descripción de dichos algoritmos a partir de la documentación técnica del software.
Key Collision Methods o Métodos de colisión clave
Según la documentación del software, este método se basa en la idea de crear una representación (una ‘llave’) que contiene solo la parte más valiosa o significativa de la cadena de texto para posteriormente asociar diferentes cadenas basado en el hecho de que su ‘llave’ es la misma (de ahí el nombre de ‘colisión clave’). Es uno de los métodos más rápidos, su análisis es lineal y permite agrupar, en segundos, millones de registros.
Los métodos de colisión clave disponibles en Open Refine se encuentran repartidos de la siguiente forma:
Fingerprint o Huella Digital
Según la documentación del software, este método se caracteriza por ser rápido y simple, es el que tiene menos probabilidades de producir falsos positivos y funciona relativamente bien en una variedad de contextos. A continuación se lista el proceso que realiza el algoritmo:
- Quita espacio inicial y final de la cadena.
- Cambia todos los caracteres por su equivalente en minúsculas.
- Elimina todos los signos de puntuación y de control.
- Divide la cadena en fichas separadas por espacios en blanco.
- Ordena las fichas y elimina duplicados.
- Une las letras de nuevo.
- Normaliza caracteres occidentales extendidos a su representación ASCII; por ejemplo: ‘averigüé’ → ‘averigue’.
Este algoritmo funciona muy bien a la hora de identificar casos en los que hay comas, puntos, tildes o mayúsculas que diferencien, en teoría, los nombres, pero que realmente representan lo mismo.
La siguiente imagen muestra cómo el software, bajo este algoritmo, agrupa un conjunto de nombres cuya única diferencia es una coma.
N-Gram Fingerprint o Huella Digital N-Gram
Según el sitio web este método es similar al de la huella digital anteriormente descrito, con la diferencia de que en lugar de utilizar espacios en blanco separados por fichas, usa n-gramas, donde n (o el tamaño en caracteres de la ficha) puede ser especificado por el usuario. Este algoritmo sigue el siguiente proceso:
- Cambia todos los caracteres a su equivalente en minúsculas
- Elimina todos los caracteres de puntuación, espacios en blanco y de control
- Obtiene todos los n-gramas
- Ordena los n-gramas y elimina duplicados
- Une los n-gramas ordenados de nuevo
- Normaliza caracteres occidentales extendidos a su representación ASCII
El sitio web cita el siguiente ejemplo para dicho método: la huella digital de 2-gramas de ‘Paris’ es "arispari" y la huella digital de 1-grama es "aiprs". En la práctica, según el software, el uso de valores grandes de n en los n-gramas no produce ninguna ventaja sobre el método de la huella digital anterior, pero utilizando 2-gramas y 1-grama se pueden encontrar grupos que el método anterior no es capaz de encontrar incluso con cadenas que tienen pequeñas diferencias.
Phonetic Fingerprint o Huella digital fonética
Según OpenRefine, el método de Huella digital fonética es una manera de transformar las fichas en la representación gráfica de su pronunciación. Dicha transformación trae una ventaja pues es útil para detectar los errores cuando las personas entienden mal o desconocen la escritura de una palabra. La idea es que las palabras que suenan similares terminarán siendo agrupadas en el mismo conglomerado.
Bajo este método OpenRefine puede emplear el algoritmo “metaphone3” para el idioma inglés y “Cologne phonetic” para el idioma alemán.
El algoritmo metaphone3 para el idioma español no está disponible en OpenRefine pero sí en el sitio web http://www.amorphics.com/, con costo y con versiones disponibles en Java y C#.
En la siguiente imagen se muestran los resultados luego de emplear el algoritmo metaphone3 sobre el mismo listado de nombres.
Métodos vecino más cercano
De acuerdo con OpenRefine, los métodos de colisión clave, descritos anteriormente, son muy rápidos pero tienden a ser muy estrictos o muy laxos, “sin poder afinar qué tanta diferencia entre las cadenas estamos dispuestos a tolerar”.
Según OpenRefine, los métodos de vecino más cercano (también conocidos como kNN), proporcionan un parámetro (el radio o k) que representa un umbral de distancia, el cual sirve de referencia para agrupar un par de cadenas de texto si su distancia es cercana.
Sin embargo, el sitio web del software advierte que a mayor número de registros mayor es el tiempo que se tarda en realizar el procedimiento; por ejemplo: para un conjunto de datos con 10 registros se requieren 45 cálculos de distancia, mientras que con un archivo de 3000 registros se requieren 4,5 millones de cálculos, lo cual es relativamente parsimonioso frente a los métodos de colisión clave.
Los métodos de vecinos más cercanos disponibles en Open Refine se encuentran repartidos de la siguiente forma:
Distancia Levenshtein
En términos generales, la Distancia Levenshtein mide el número mínimo de operaciones de edición que se requieren para cambiar una cadena en otra.
En la siguiente tabla se explica brevemente en qué consiste la Distancia Levenshtein:
|
Palabras |
Explicación |
|
‘París’ → ‘parís’ |
Tienen una distancia de edición de 1 debido a que el cambio de P a p es la única operación requerida. |
|
‘Nueva York’ → ‘newyork’ |
Tiene una distancia de edición de 3: 2 sustituciones y 1 eliminación. |
De acuerdo con OpenRefine, esta distancia “es útil para identificar errores tipográficos, errores de ortografía o cualquier cosa que los métodos anteriores no capturan, aunque las grandes distancias dan muchos falsos positivos (especialmente para las cadenas cortas) y no son tan útiles”.
En la siguiente imagen se muestran los resultados después de aplicar la distancia Levenshtein sobre el mismo listado de nombres.
PPM o Predicción por Coincidencia Parcial
Según el sitio web del software, el algoritmo de Predicción por Coincidencia Parcial estima similitudes entre cadenas de texto empleando una operación que mide los recursos empleados por un computador para definir una cadena de texto.
El sitio web indica que la operatividad del algoritmo surge a partir de la forma en que funcionan los compresores de texto; por ejemplo, si dos cadenas de texto A y B son idénticas, al momento de comprimirlas, es decir, al realizar la operación (A+B), se genera muy poca diferencia. Por otro lado, si A y B son muy diferentes, al momento de comprimirlas se deben producir diferencias dramáticas en longitud. La documentación del software recomienda emplear esta técnica como último recurso.
Como se expuso anteriormente, existen varios métodos que pueden ser de gran utilidad para el cruce de listas y que a su vez generan distintos resultados al emplear la misma información. La selección del mejor método para este fin puede hacerse a partir de los resultados realizados sobre los listados a verificar o tomando como referencia la documentación de OpenRefine que suministra un orden de preferencias para estos métodos.
