table.Ooda7o { border-collapse: collapse; } table.Ooda7o, table.Ooda7o td, table.Ooda7o th { border: 1px solid black; } table.Ooda7o td, table.Ooda7o th { padding: 2px; }

Cet article est le second d’une trilogie qui contient également :

• [Index géographique : avant le géocodage, le gazetteer](Index géographique)
• Les logiciels et API pour géocoder

Les adresses sont les données spatiales parmi les plus utilisées, mais elles ne sont que textuelles. Le géocodage consiste à assigner des coordonnées latitude et longitude à une adresse en la comparant à des adresses de références. Malgré l’utilisation importante des géocodeurs, la nature de ce qu’est un géocodeur reste assez floue et est à adapter en fonction du besoin et des données. [0]

835, boul. René-Lévesque Est
Québec (Québec) G1A 1B4

4746 SW 13th Place
Deerfield Beach
Florida 33442

Rue du Vivier 7
1000 Bruxelles

52, rue Jacques Babinet
31100 Toulouse

Exemple d’adresses dans le monde.

Pour des structures d’adresse très différentes voir le Japon.

Géocoder une adresse, consiste dans une première étape à la normaliser, c’est-à-dire à la retravailler. La seconde étape est de la comparer aux données de références, étape nommé corrélation (« linkage » en anglais) [6].

Normalisation

Les adresses sont des données textuelles adaptées aux humains. Bien qu’il y ait culturellement par pays une façon commune d’écrire une adresse, il n’en reste pas moins que des variantes sont possibles et n’empêche pas dans les faits de localiser le lieu de l’adresse.

L’adresse « 16 bis Avenue du Président-Kennedy, Paris 16ᵉ » peut s’écrit de différent façon sans perturber plus que cela un utilisateur humain, par exemple « 16 B Av Kennedy, Paris 16 ème ».

Si l’on recherche directement l’adresse en entrée dans la base d’adresses de référence, on va amoindrir les chances de trouver une correspondance, ou tout du moins trouver des correspondances avec moins de confiance.

Cette étape d’amélioration relève de la discipline de normalisation de textes (« Lexical Normalization »). Elle regroupe des techniques plus ou moins avancés pour corriger des fautes, faire de la reconnaissance optique ou vocale de textes…

Substitution et lexique

Un des premiers problèmes à traiter est en particulier l’utilisation d’abréviation qu’il faut identifier et substituer par une version attendu par la suite du traitement. Par exemple « B » pour « bis » ou « Av » pour « Avenue ». Il ne faut toutefois pas appliquer des règles de substitution trop à l’aveugle qui risqueraient de faire de la surinterprétation. Par exemple ici, « B » est-il l’abréviation de « Bis » ou un ordinal alphabétique (« 16 A », « 16 B », « 16 C ») ?

La première approche est d’utiliser un lexique de substitution, aussi nommé dictionnaire de synonymes.

Recherche	Substitution
100	cent
10e, 10eme, xe, xeme	dixieme
11e, 11eme, xie, xieme	onzieme
cdt	commandant
cf	chemin forestier
ch, che	chemin
std, stde	stade
ste	sainte

Extraits du lexique du géocodeur Addok pour le français.

Des expressions régulières peuvent également être utilisées.

Substitution contextuelle

Le contexte peut être utilisé pour contrôler les opérations faites sur l’adresse en entrée. On peut ne remplacer « Av » par « Avenue » qu’après un nombre (ou un ordinal).

Un exemple parlant en anglais est l’abréviation « St » qui est utilisé à la fois pour « Saint » et pour « Street ». Ce qui peut donner « St James’s St, London ».

En France, mais également en Suisse, l'on trouve des communes nommées « Rue », capable de mettre à l’épreuve la qualité des géocodeurs.

Les communes Rue en France et en Suisse.

Parseur

Une solution plus avancée est d’essayer de parser l’adresse pour détecter les natures des différentes composantes. C’est-à-dire identifier ce que représente chaque partie de l’adresse : le numéro, un ordinal, le type de voie, le nom de la voie…

Cette approche nécessite d’établir une grammaire des formats d’adresses possibles et des valeurs possible pour chacune des parties [1]. Si l’adresse ne correspond pas au modèle on peut y appliquer des substitutions ou des transformations.

Écrire toutes ces règles de substitution ou parseur pour analyser les adresses est atteignable pour un pays mais difficilement réalisable pour le monde entier.

Approche probabiliste

Une autre solution du domaine du traitement automatique du langage (NLP) est d’essayer de parser l’adresse mais cette fois non pas avec une grammaire classique mais avec une sorte de grammaire souple et non prédéterminée ou les enchaînements des parties sont probabilisées. Ce modèle est nommé « Modèle de Markov caché » [2].

Il est créé par apprentissage automatique depuis des jeux d’adresses disponibles et déjà annotés. C’est-à-dire que les différentes parties sont déjà identifiées.

D’autres approches similaire existent par exemple avec des réseaux de neurones [3] [4].

Libpostal

L’approche du « Modèle de Markov caché » a été implémentée par Mapzen dans le projet libpostal.

Libpostal permet de normaliser et de découper une adresse postale d’un pays quelconque en champs.

C’est un projet à l’arrêt suite à la fermeture de Mapzen, il est toute fois pleinement fonctionnel.

Découpage de l'adresse « 16 bis Avenue du Président-Kennedy, Paris 75016 » par libpostal.

Champ	Valeur
house_number	16 bis
road	avenue du président-kennedy
city	paris
postcode	75016

La normalisation de libpostal donne ensuite :

16 bis avenue du president-kennedy paris 75016
16 bis avenue du president kennedy paris 75016
16 bis avenue du presidentkennedy paris 75016

Analyse de l'adresse « 16 B Av Kennedy, Paris 75016 » par libpostal :

Champ	Valeur
house_number	16
road	b av kennedy
city	paris
postcode	75016

La normalisation de libpostal donne ensuite :

16 bairro avenida kennedy paris 75016
16 bairro avenida calle kennedy paris 75016
16 bairro avenue kennedy paris 75016
16 b avenida kennedy paris 75016
16 b avenida calle kennedy paris 75016
16 b avenue kennedy paris 75016

Structuration ou non de l’adresse

Suivant la technique de normalisation utilisée, l’adresse va être segmentée (numéro, type de voie, voie…) ou rester un bloc de texte.

À noter que l’adresse peut déjà être découpée en différents champs en amont, par exemple lors de la saisie dans un formulaire.

Corrélation

« La corrélation consiste à faire correspondre des entités d’origines différentes. En l’absence de clés partagées et uniques. Cela implique la comparaison d’ensemble d’entités partiellement identifiables et non uniques. » [2]

Si l’adresse a été structurée et découpée en champs, la corrélation va pouvoir être faite par champs. Les chances d’obtenir une bonne concordance sont alors plus grandes. Toutefois les champs peuvent être mal renseignés et une recherche plein texte peut à défaut donner un bon résultat.

Recherche simple dans l’index

La plus simple des façons est d’indexer les termes des adresses ou des champs des adresses après les avoir simplifiées : passage en minuscule, retrait des accents, découpe des mots liées… Ces morceaux sont alors nommés « tokens ». Ce sont ces tokens qui sont indexés. Lors d’une recherche le texte recherché subit le même traitement et ces tokens sont alors recherchés parmi ceux de référence. L’adresse de référence ayant le plus de tokens est alors le résultat de la recherche.

Recherche approximative

Si l’on souhaite être tolérant aux fautes et variantes d’écritures, la mise en correspondance des adresses passe par de la recherche floue. Même après la phase de normalisation cela est nécessaire.

La corrélation se fait en comparant l’adresse recherché avec les adresses de références. Il faut donc établir une « mesure » pour comparer deux adresses. Ces scores permettent d’ordonner les adresses candidates et donc de choisir la meilleure correspondance dans la base des adresses de références.

Il existe beaucoup de façon d’établir une mesure de distance entre deux textes. Il faut en choisir un ou plusieurs adaptées au géocodage [7].

Distance de Levenshtein

Une des mesures de similarité de texte les plus simples est la distance de Levenshtein. Cette distance est le nombre minimum d’opération de remplacement, de suppression ou d’ajout de caractères qu’il faut faire pour passer d’un texte à un autre.

Malheureusement cette métrique est peu adaptée à notre cas. Elle prend mal en compte certaines fautes comme d’orthographe : la distance entre « o » et « eau » est par exemple de 3 (remplacer « o » par « e » et supprimer « a » et « u »). Il n’est pas non plus possible d’indexer cette mesure pour accélérer les recherches.

Phonétique

Une première approche plus appropriée est d’utiliser la phonétisation. Cela consiste à créer une signature phonétique des mots qui n’est pas variable en fonction de l’orthographe (« f » ou « ph », « s » ou « ç ») ou des parties non phonétiques (comme « h » ou certaines lettres finales).

Le plus simple de ces codages phonétique est le Soundex, créé dès 1918.

Il en existe des variantes notamment adaptées à d’autres langues que l’anglais. Le codage le plus utilisé de ce type est aujourd’hui le Metaphone.

Ces codages ont l’avantage de s’abstraire de l’orthographe. Les signatures peuvent également être indexées pour retrouver rapidement les textes se prononçant de façon similaire.

N-gramme (N-Gram en anglais)

Un N-gramme, décliné en digramme, trigramme… est un échantillonnage d’un texte en groupes de lettres de longueur N. Le traitement est effectué à partir de chaque lettre.

« Bonjour » va donc être découpé en trigrammes suivant : « bon », « onj », « njo » « jou », « our ».

Une distance nommée q-grammes entre les n-grammes d’un texte est établi. C’est le nombre de n-grammes différent entre deux textes [5].

trigrammes	« Bonjour »	« Bonsoir »	différence
bon	1	1	0
onj	1	0	1
njo	1	0	1
jou	1	0	1
our	1	0	1
ons	0	1	1
nso	0	1	1
soi	0	1	1
oir	0	1	1

La distance q-gramme entre « Bonjour » et « Bonsoir » est la somme des différences, soit 8.

Cette mesure à l’avantage de supporter les permutations. Il est aussi possible d’indexer les n-grammes. À noter que des textes différents peuvent même avoir une distance de 0.

Conclusion

Le géocodage est donc un processus dépendant des données de références et du résultat souhaité. Il n’y a pas de façon unique d’effectuer du géocodage, en particulier si les adresses sont ou non structurées et si le géocodage doit être multilingue ou multi-pays. Les choix des approches de normalisation et de corrélation doit être mesuré en fonction des paramètres et des résultats souhaités. Aujourd’hui parmi les implémentations de géocodeurs connues, en logiciel libre, la plus part utilisent des lexiques de substitution non ou peu contextuel pour la normalisation. Pour la mise en corrélation les choix d’implémentation sont variées, on retrouve de la simple recherche de token, de la phonétisation ou du trigramme.

Références

[0] Daniel W. Goldberg, John P. Wilson, and Craig A. Knoblock. From Text to Geographic Coordinates: The Current State of Geocoding, 2007.

[1] Sen Xu, Soren Flexner, Vitor Carvalho. Geocoding Billions of Addresses: Toward a Spatial Record Linkage System with Big Data, 2012.

[2] Tim Churches, Peter Christen, Kim Lim and Justin Xi Zhu. Preparation of name and address data for record linkage using hidden Markov models, 2003.

[3] Nosheen Abid, Adnan ul Hasan and Faisal Shafait. DeepParse: Trainable Postal Address Parser, 2018.

[4] Minlue Wang, Valeriia Haberland, Amos Yeo, Andrew Martin, John Howroyd and J. Mark BishopTungsten. A Probabilistic Address Parser using Conditional Random Fields and Stochastic Regular Grammar, 2016.

[5] Esko Ukkonen. Approximate string-matching and the q-gram distance, 1993.

[6] Omar Charif, Hichem Omrani, Olivier Klein, Marc Schneider, Philippe Trigano. A method and a tool for geocoding and record linkage, 2010.

[7] Ioannis Koumarelas, Axel Kroschk, Clifford Mosley, Felix Naumann. Experience: Enhancing Address Matching with Geocoding and Similarity Measure Selection, 2018.