Algorithmes de correspondance pour l'importation

Lors de l'importation de données, il est très courant qu'il y ait de légères différences entre les noms, les noms de lieux et d'autres données de référence.

ActivityInfo a été développé pour faire correspondre automatiquement les données de référence en se basant sur un ensemble de règles qui prennent en compte les différences courantes entre les noms, dues à des variations de translittération et d'orthographe.

Actuellement, ces règles ne s'appliquent qu'aux noms écrits en alphabet latin. Pour la correspondance des noms dans d'autres alphabets, comme l'arabe ou le cyrillique, une correspondance exacte est utilisée. Nous espérons développer à l'avenir des algorithmes de correspondance comparables pour les alphabets non latins.

Correspondance des noms latins

L'algorithme de notation des noms latins (Latin Name scorer) aide à identifier les paires de noms de lieux, écrits en alphabet latin, qui sont susceptibles d'être identiques, mais translittérés différemment.

Ces différences peuvent provenir d'un certain nombre de processus aléatoires :

  1. Le même son peut être écrit différemment, peut-être en raison d'un système de translittération différent, par exemple :

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

  2. Les sons peuvent évoluer régionalement et avec le temps, et ces différences entraînent de nouvelles orthographes

  3. Les noms qui incluent des parties du discours peuvent être réorganisés ou supprimés arbitrairement :

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

  4. Les mots peuvent être séparés ou joints

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

Pour être utile dans la mise en correspondance de grands ensembles de données, nous avons besoin d'un faible taux de faux positifs, sinon les analystes seront submergés par des centaines ou des milliers de correspondances inutiles à examiner.

Les métriques traditionnelles de distance d'édition, telles que la distance de Levenshtein ou la similarité de Jaro-Winkler ont tendance à produire beaucoup trop de faux positifs. Les chaînes de caractères AAIN et ZEBDINE, par exemple, ont une similarité de Jaro-Winkler de 0,60, bien qu'il n'y ait aucune chance que ZEBDINE soit une orthographe alternative de AAIN.

Le "Latin Name Scorer" d'ActivityInfo considère plutôt la probabilité que AAIN puisse être transformé en ZEBDINE par les processus énumérés ci-dessus. Comme nous considérons l'ajout de consonnes comme Z, B, D comme extrêmement improbable, le Scorer renvoie une valeur de zéro.

D'un autre côté, la chaîne de caractères AIN ne diffère que par une seule voyelle, ce qui est une différence très courante en translittération, résultant en un score de 0,925.

Algorithme

L'algorithme de correspondance des noms latins d'ActivityInfo fonctionne comme suit :

Premièrement, chaque chaîne de caractères d'entrée est mise en majuscules et débarrassée de tout signe diacritique, y compris les apostrophes lorsqu'elles se trouvent entre des lettres. Par exemple :

Ensuite, chaque chaîne de caractères d'entrée est divisée en une ou plusieurs "parties". Tous les symboles tels que "-", "/", "(", etc., sont considérés comme le début de nouvelles parties, et les chiffres commenceront une nouvelle partie s'ils sont précédés de caractères. Par exemple :

Étant donné deux chaînes de caractères d'entrée, chacune décomposée en un tableau de parties, par exemple, [COMMUNE, DE, GOUMERA] et [GOUMERA, COMUNE], nous calculons un score de similarité pour chaque paire de parties de gauche et de droite :

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

Les noms de "gauche" et de "droite" sont choisis de telle sorte que le nom de "gauche" ait un nombre de parties inférieur ou égal à celui du nom de droite.

Le score de similarité entre deux parties est calculé en fonction du type de parties :

Avec la matrice de similarité en main, nous trouvons la meilleure colonne correspondante for chaque ligne de la matrice, en veillant à ce qu'une colonne ne corresponde qu'à une seule ligne au maximum.

Enfin, nous calculons un score entre 0 et 1 indiquant à quel point les deux noms correspondent. Plus précisément :

Nous définissons le numérateur comme la somme des longueurs de toutes les parties correspondantes, pondérées par leurs scores de similarité. Dans l'exemple ci-dessus, "COMMUNE" correspond le mieux à "COMUNE" avec une similarité de 0,93. Nous utilisons la longueur minimale des deux parties, qui dans ce cas est de 6 caractères, pondérée par 0,93, ce qui contribue à hauteur de 5,58 au numérateur.

"GOUMERA" correspond exactement à "GOUMERA", et contribue donc à hauteur de 6 * 1,0 au numérateur.

Le dénominateur inclut les longueurs des parties correspondantes (6 + 6) ainsi que la partie non correspondante "DE" (2).

Algorithme de similarité phonétique

Lors du calcul de la similarité de deux parties alphabétiques, l'algorithme de distance des mots latins (Latin Word Distance) d'ActivityInfo est utilisé pour calculer la distance entre deux parties, supposées être des mots en alphabet latin.

Comme l'algorithme de Levenshtein, nous calculons le nombre minimum de "modifications" -- substitutions, insertions et suppressions -- mais au lieu de traiter chaque différence de caractère de la même manière, chaque "modification" se voit attribuer un coût basé sur la probabilité qu'elle résulte d'une différence de translittération.

Par exemple, les voyelles sont souvent translittérées différemment, de sorte que les voyelles supplémentaires ou les substitutions de voyelles se voient attribuer un coût relativement faible. Dans le cas de MREISSE et MRAISSE, par exemple, la substitution de E par A se voit attribuer un coût de 0,25.

D'un autre côté, la plupart des substitutions de consonnes sont très rares : il est très peu probable que le mot RAS soit translittéré en RAB, et l'algorithme attribue un coût infini à cette substitution.

Certaines substitutions de consonnes sont courantes, y compris M → N et K → Q, et se voient attribuer un coût de 0,5 et 0,25 respectivement.

Des règles supplémentaires ont été développées sur la base d'ensembles de données rencontrés en Afghanistan, au Liban, au Mali et aux Philippines.