Sous le capot du géocodeur addok

addok est le moteur utilisé par l’API de géocodage d’Etalab sur adresse.data.gouv.fr

Cet article explique les grandes lignes de son fonctionnement et son histoire.

Géocodage ?

Le géocodage consiste à retrouver une adresse au sein d’un référentiel (par exemple la Base Adresse Nationale). Ceci permet d’obtenir sa position géographique mais aussi une adresse correctement structurée.

On peut valider l’existence officielle d’une adresse en la retrouvant dans le référentiel, mais aussi proposer des adresses complètes à partir de saisies incomplète. C’est l’auto-complétion qui aide un utilisateur d’un service en ligne en lui proposant des adresses sans avoir à saisir l’intégralité des informations.

Les éléments de départ sont en général une simple chaîne de caractères avec parfois la position géographique de l’utilisateur.

Cette dernière permettra par exemple de favoriser des adresses à proximité: une fonction très utile sur un usage mobile.

Dans le cas de l’autocomplétion, la réponse doit très rapidement parvenir à l’utilisateur pour que celui-ci ait au plus tôt des propositions d’adresses pertinentes et lui éviter de poursuivre sa saisie. On parle ici de dizaines de millisecondes, pas plus.

Il faut aussi tenir comptes:

• des fautes de frappes et d’orthographe,
• des inversions de mots,
• des variantes dans les noms (Mont Griffon, Montgriffon ou Mongrifon ?)
• des adresses partielles (manques de mots ou mots superflus)
• et bien sûr ne pas être sensibles aux majuscules/minuscules et accents !

Ceci implique une recherche autorisant plus ou moins de “flou”.

Retrouver (rapidement) une aiguille dans une meule de foin… étape par étape

addok fonctionne avec une logique de recherche en texte intégral. La structure hiérarchique d’une adresse (commune > voie ou lieu-dit > numéro) est peu prise en compte. Ceci lui permet même de fonctionner avec la même logique avec autre choses que des adresses.

La chaîne cherchée va être préparée, mise en forme et découpée en “tokens” correspondant plus ou moins à des mots simplifiés phonétiquement.

La recherche va passer ensuite par 2 phases bien distinctes :

• une collecte de voies et lieux-dit candidats (remplissage du seau)
• une évaluation de ces candidats en les comparant au texte initialement cherché (extraire de la crème)

La préparation des tokens

Avant d’être découpée en mot simplifiés (tokens) la chaîne cherchée est nettoyée pour éliminer le plus possible d’éléments qui ne feraient pas partie de l’adresse (nom d’entreprise, de personnes, complément d’adresse, etc).

1. Etalab, 20 av de Ségur, TSA 30719 75334 Paris Cedex 07
2. 20 av de segur tsa 30719 75334 Paris Cedex 04
3. 20 av de segur 75 paris

Ces traitements sont spécifiques aux adresses françaises et gérés par un plugin d’addok, addok-france pour isoler du moteur générique les particularités liées à un pays.

Les dernières étapes vont gérer des synonymes habituels (ici l’abréviation “av” pour “avenue”) et appliquer une simplification phonétique. Celle-ci est liée à la langue française et a été regroupée dans un second plugin: addok-fr

vin avenu de segur 75 pari

Nous avons donc réduit notre recherche à ces 6 “tokens”.

Le remplissage du seau

addok va chercher la fréquence de chacun des tokens dans son index pour les classer en plusieurs catégories:

• les tokens peu courants (segur, 75, pari),
• les tokens courants (avenu, de),
• un token correspondant au numéro de l’adresse (vin),
• les tokens inconnus.

Les tokens peu courant sont exploités en priorité pour trouver toutes les voies et lieux-dits où ils sont présents, ce qui permet de sélectionner immédiatement 4 candidats.

Si le seau, prévu pour une centaine de candidats potentiels, n’est pas très remplit, addok va tenter de le compléter de différentes façons, mais il ne cherchera pas de façon exhaustive.

Cet enchaînement de collectes de candidats en vue de remplir le seau est totalement paramétrable par les fichiers de configuration d’addok. On peut ainsi tester différentes stratégies assez facilement et en écrire de nouvelles sans toucher au cœur d’addok. La configuration par défaut d’addok enchaîne ainsi pas moins de 13 collecteurs… que je ne décrirais pas ici en détail, on ne fait que soulever le capot on ne démonte pas le moteur !

Un des collecteurs s’occupe par exemple des fautes de frappe qui auraient très bien pu se glisser dans l’adresse. Il peut même tenir compte de l’agencement classique d’un clavier (G sera substitué en F,T,H,B et V). Il poursuit le remplissage du seau en testant des variations sur les tokens (étape “fuzzy”), comme l’inversion de lettre, des suppressions, des substitutions :

• segur > seur
• pari > pai

Le remplissage continuera si besoin en utilisant moins de tokens, en supprimant les plus fréquents en premier mais aussi en tentant de compléter le dernier token (mécanisme d’autocomplétion). Dans notre cas l’autocomplétion pourra ajouter des tokens comme “parili”,”paribou”,”pariben”… là aussi via un index.

On se retrouve au final avec 7 candidats dans notre seau qui par défaut peut donc en contenir une centaine:

• Villa de Ségur 75007 Paris
• Avenue de Ségur 75015 Paris
• Avenue de Ségur 75007 Paris
• Rue Pérignon, Métro Segur 75015 Paris
• Impasse des 3 soeurs 75011 Paris
• Passage des 2 Soeurs 75009 Paris
• Avenue de la Soeur Rosalie 75013 Paris

Jusqu’à ce stade, le numéro de l’adresse n’a toujours pas été utilisé, on ne cherche que des voies/lieux-dits/communes.

Extraire la crème du seau

Chaque candidat présent dans le seau est évalué en comparant les libellés complets de l’adresse de référence avec celui cherché, numéro compris.

On découpe chaque libellé en trigrams, exemple :

Villa de Ségur 75007 Paris -> vil, ill, lla …

On regarde ensuite la proportion de trigrams cherchés présents dans l’adresse trouvée. Les trigrams ont l’avantage (et aussi l’inconvénient) de très peu tenir compte de l’ordre des mots. Pour départager avec une éventuelle “Avenue de Paris” à Ségur, on calcule aussi une distance de levenshtein, c’est à dire le nombre de modifications à apporter pour passer d’une chaîne à l’autre.

Ceci permet d’avoir un score de comparaison des libellés cherchés et trouvés et de sélectionner la “crème”, c’est à dire les résultats les plus proches du texte cherché, en tenant compte cette fois-ci du numéro.

Le score final

Pour le calculer, deux autres éléments vont éventuellement aussi servir:

• un score géographique
• un score d’importance

Le score de distance géographique est utilisé lorsqu’une position géographique a été fournie au moment de la recherche. Ceci permet de faire ressortir les résultats les plus proches géographiquement, une fonctionnalité très utile en usage mobile. Si l’on cherche “Place du Capitole” en étant physiquement à Saintes, on peut la faire sortir en premier alors qu’en étant physiquement à Toulouse c’est bien sûr cette dernière qu’on souhaitera obtenir en première position.

Ce score utilise un index géographique basé sur les geohash. Un geohash est une traduction sous forme de chaîne de caractères d’une position géographique (lat/lon). Il viendra en quelque sort s’ajouter aux tokens de recherche. Ces tokens de geohash servent aussi au géocodage inverse, c’est à dire retrouver l’adresse la plus proche d’une position géographique donnée.

Pour le score d’importance, celui-ce est en fait calculé en amont (hors addok) dans les données du référentiel. Il sert à donner un indice de l’importance relative pour chaque voie ou lieu-dit. Le calcul tient compte du niveau administratif de la commune, de sa population, de l’emprise et du nombre d’adresses numérotées. Ainsi, la Place du Capitole à Toulouse aura plus d’importance qu’à Saintes.

Ce score d’importance est utile pour les requêtes en auto-complétion, car au début de l’adresse saisie, les informations sur la commune sont encore absentes car elle ne sont en général entrées qu’à la fin. Cette importance n’est pas prise en compte lorsque les recherches ont désactivé les mécanismes d’autocomplétion (cas typique du géocodage de fichiers où les adresses sont en principe complètes).

Le cumul de ces différents score permet d’effectuer le tri final.

L’indexation du référentiel

Il a été fait mention d’un index à plusieurs reprises et cet index est un élément essentiel de la rapidité d’addok.

Lors de l’import des données, celles-ci subissent la même tokenisation et ces tokens sont indexés. Partant d’un token, on obtient la liste des voies où il figure.

Voici ceux pour notre Avenue de Ségur:

avenu 1.347 4449
de 1.347 312
segur 1.347 14
75007 1.041 14
pari 1.041 1507
75 0.208 403
pari 1.041 1507
il 0.208 4892
frans 0.208 4595

Pour chaque token, un poids dépendant du nombre de mots est calculé au moment de l’indexation. C’est le premier nombre qui figure après le token, nous verrons plus loin à quoi correspond le second. Il tient aussi légèrement compte de l’importance de la voie.

En plus de l’adresse “20 Avenue de Ségur 75007 Paris”, on constate que des tokens de contexte sont aussi présents qui correspondent à “75, Île de France”. Ils permettent de départager si besoin certaines adresses avec le nom de la région, du département et le numéro de département.

Ces index sont stockés dans une base “clé/valeur” Redis qui fonctionne totalement en RAM ce qui est une des raisons de la rapidité d’addok.

Redis permet d’associer à chaque token, un ensemble de voies dans les données en indiquant le poids du token pour cette voie (sorted sets). Là où Redis est très intéressant c’est qu’il peut calculer l’intersection entre ces ensembles (donc entre plusieurs tokens) et additionner les poids pour sortir les voies où les tokens cherchés ont finalement le plus de poids. C’est ce mécanisme qui est au cœur d’addok et ce mécanisme est ultra rapide.

Une intersection entre “segur” et “pari” retourne 4 résultats, déjà triés par poids.

Pour connaître la fréquence d’apparition d’un token dans la base, il suffit de demander à Redis combien d’éléments sont dans l’ensemble du token. Le token “segur” a 388 éléments, il apparaît donc dans 388 voie/lieux-dit ou communes de notre référentiel.

Le deuxième nombre qui figurait après notre token est le rang de notre voie dans l’ensemble. Pour notre “Avenue de Ségur 75007 Paris” trouvée, le poids de 1.347 la mettait en 14ème place du token “segur”, la commune de “Ségur” se trouve logiquement en première place avec un poids supérieur à 4.

D’autres tokens peuvent être ajoutés à l’index et servir à limiter la recherche uniquement aux voies possédant ce token. Ceci permet par exemple de ne chercher une adresse que sur une commune avec le filtre “citycode”. Là encore le mécanisme de filtre est totalement configurable.

Afin d’économiser de la RAM, Redis n’est désormais utilisé que pour stocker les index et les données plus complètes sont conservées dans une base sqlite séparée. Pour une instance France entière avec le référentiel d’adresses de la BAN, addok a besoin d’environ de 6 Go de RAM dans ses dernières versions.

Temps de traitement

Voici au final les principales étapes, ainsi que le temps passé en moyenne pour chacune d’elle :

• nettoyage de la requête et tokenisation (6%)
• classement des tokens (6%)
• recherche et combinaison des tokens principaux (18%)
• recherche “fuzzy” (27%)
• récupération des données complètes (16%)
• calcul de score (14%)

Après avoir optimisé le calcul de score dans la future version 1.1, ce sera peut être au tour de la recherche floue d’avoir droit prochainement à une optimisation.

Pourquoi addok ?

Addok est né fin 2014 après plusieurs tentatives d’utiliser un outil de recherche générique et très performant : Elasticsearch.

Son fonctionnement comme géocodeur était magique dans 80% dans cas, mais les 20% restants étaient très difficiles à améliorer d’autant plus que les adresses sont de tout petits documents avec des informations très répétitives, ce qui n’est pas ce pour quoi Elasticsearch est le plus efficace.

La recherche en texte intégral sur des adresses s’accomode mal des algorithmes présents dans des outils génériques.

Addok a été pensé dès le départ pour les adresses mais aussi pour bien comprendre ses résultats. Un shell intégré permet de tracer les différentes étapes qui conduisent à un résultat, d’explorer l’index, de vérifier la tokenisation, etc. C’est un outil de mise au point qui a été et reste encore très utile.

Addok a été développé au sein d’Etalab pour la mise en place d’une API publique de géocodage. Cette API est en production depuis avril 2015 avec comme référentiel la Base Adresse Nationale et a traité en 2017 plus d’un milliard de requêtes avec un temps moyen de réponse de 30ms.

Son code est totalement libre et disponible sur github. La documentation en ligne explique comment déployer sa propre instance. Un docker prêt à l’emploi est aussi disponible (avec des données pré-indexées).

Des adresses mais pas que…

Addok peut aussi être utilisé un peu au délà des adresses, des tests ont été faits en indexant des points d’intérêts issus d’OpenStreetMap ou un extrait de la base SIRENE.

Il suffit de préparer les données au format attendu par addok, c’est à dire du json.

Vous pouvez tester sur demo.addok.xyz une instance qui combine adresses et points d’intérêt. On peut ainsi chercher “Etalab” sans connaître son adresse !