Algoritmos de coincidencia para la importación

Al importar datos, es muy común que haya ligeras diferencias entre nombres, topónimos y otros datos de referencia.

ActivityInfo ha sido desarrollado para hacer coincidir automáticamente los datos de referencia basándose en un conjunto de reglas que tienen en cuenta las diferencias comunes entre nombres que surgen debido a diferencias en la transliteración y la ortografía.

Actualmente, estas reglas solo se aplican a los nombres escritos en alfabeto latino. Al hacer coincidir nombres en otros alfabetos, como el árabe o el cirílico, se utiliza la coincidencia exacta. Esperamos desarrollar algoritmos de coincidencia comparables para alfabetos no latinos en el futuro.

Coincidencia de nombres latinos

El algoritmo de puntuación de nombres latinos ayuda a identificar pares de topónimos, escritos en un alfabeto latino, que probablemente sean los mismos, pero transliterados de forma diferente.

Estas diferencias pueden surgir de una serie de procesos aleatorios:

  1. El mismo sonido puede escribirse de forma diferente, quizás debido a un esquema de transliteración distinto, por ejemplo:

    • [ou]adi ⇒ [w]adi
    • zou[q] bha[nn]ine ⇒ zou[k] bha[n]ine
    • z[ai]toun ⇒ z[ei]toun[e]

  2. Los sonidos pueden variar regionalmente y con el tiempo, y estas diferencias dan lugar a nuevas ortografías.

  3. Los nombres que incluyen partes de una oración pueden reordenarse o descartarse arbitrariamente:

    • "Santa Rosa City" ⇒ "City of Santa Rosa"
    • "Commune de Goumera" ⇒ "Goumera"

  4. Las palabras pueden dividirse o unirse

    • "Bara Sara" ⇒ "Barassara"
    • "Nema Badenyakafo" ⇒ "Nema Badenya Kafo"

Para que sea útil en la comparación de grandes conjuntos de datos, necesitamos una tasa baja de falsos positivos; de lo contrario, los analistas se verán abrumados con cientos o miles de coincidencias basura que revisar.

Las métricas tradicionales de distancia de edición, como la distancia de Levenshtein o la similitud de Jaro-Winkler tienden a producir demasiados falsos positivos. Las cadenas AAIN y ZEBDINE, por ejemplo, tienen una similitud de Jaro-Winkler de 0,60, a pesar de que no hay ninguna posibilidad de que ZEBDINE sea una ortografía alternativa de AAIN.

El Puntuador de Nombres Latinos de ActivityInfo considera en cambio la probabilidad de que AAIN pueda ser transformado en ZEBDINE por los procesos enumerados anteriormente. Como consideramos que la adición de consonantes como Z, B, D es extremadamente improbable, el Puntuador devuelve un valor de cero.

Por otro lado, la cadena AIN difiere solo en una única vocal, lo que es una diferencia muy común en la transliteración, resultando en una puntuación de 0,925.

Algoritmo

El algoritmo de coincidencia de nombres latinos de ActivityInfo funciona de la siguiente manera:

Primero, cada cadena de entrada se convierte a mayúsculas y se le eliminan todas las marcas diacríticas, incluidos los apóstrofos cuando se encuentran entre letras. Por ejemplo:

A continuación, cada cadena de entrada se divide en una o más «partes». Todos los símbolos como «-», «/», «(», etc., se consideran el inicio de nuevas partes, y los dígitos iniciarán una nueva parte si van precedidos de caracteres. Por ejemplo:

Dadas dos cadenas de entrada, cada una dividida en una matriz de partes, por ejemplo, [COMMUNE, DE, GOUMERA] y [GOUMERA, COMUNE], calculamos una puntuación de similitud para cada par de partes de la izquierda y la derecha:

| | COMMUNE | DE | GOUMERA ||--------|--------:|---------:|:---------:||GOUMERA | 0.0 | 0.00 | 1.0 | |COMUNE |0.93 | 0.00 | 0.0 |

Los nombres de la «izquierda» y la «derecha» se eligen de tal manera que el nombre de la «izquierda» tenga un número de partes menor o igual que el nombre de la derecha.

La puntuación de similitud entre dos partes se calcula en función del tipo de partes:

Con la matriz de similitud en mano, encontramos la columna con la mejor coincidencia para cada fila de la matriz, asegurándonos de que cada columna coincida como máximo con una fila.

Finalmente, calculamos una puntuación entre 0 y 1 que indica qué tan bien coinciden los dos nombres. Específicamente:

Definimos el numerador como la suma de las longitudes de todas las partes que coinciden, ponderadas por sus puntuaciones de similitud. En el ejemplo anterior, «COMMUNE» coincide mejor con «COMUNE» con una similitud de 0,93. Usamos la longitud mínima de las dos partes, que en este caso es de 6 caracteres, ponderada por 0,93, lo que aporta 5,58 al numerador.

«GOUMERA» coincide exactamente con «GOUMERA», por lo que aporta 6 * 1,0 al numerador.

El denominador incluye las longitudes de las partes que coinciden (6 + 6), así como la parte no coincidente «DE» (2).

Algoritmo de similitud fonética

Al calcular la similitud de dos partes alfabéticas, se utiliza el algoritmo de Distancia de Palabras Latinas de ActivityInfo para calcular la distancia entre dos partes, que se asume que son palabras en alfabeto latino.

Al igual que el algoritmo de Levenshtein, calculamos el número mínimo de «ediciones» ( sustituciones, inserciones y eliminaciones), pero en lugar de tratar cada diferencia de caracteres por igual, a cada «edición» se le asigna un coste basado en la probabilidad de que sea el resultado de una diferencia de transliteración.

Por ejemplo, las vocales a menudo se transliteran de forma diferente, por lo que a las vocales adicionales o a las sustituciones de vocales se les asigna un coste relativamente bajo. En el caso de MREISSE y MRAISSE, por ejemplo, a la sustitución de E por A se le asigna un coste de 0,25.

Por otro lado, la mayoría de las sustituciones de consonantes son muy raras: es muy poco probable que la palabra RAS se translitere como RAB, y el algoritmo asigna un coste infinito a esta sustitución.

Algunas sustituciones de consonantes sí son comunes, incluyendo M → N y K → Q, y se les asigna un coste de 0,5 y 0,25 respectivamente.

Se han desarrollado reglas adicionales basadas en conjuntos de datos encontrados en Afganistán, Líbano, Malí y Filipinas.