Cet article est le troisième d’une trilogie qui contient également :

• Index géographique : avant le géocodage, le gazetteer
• Géocodeur : la théorie

Vue d’ensemble

Indexation

Géocodage direct

Autocomplétion

Géocodage inverse

Autres fonctionnalités

Conclusion

Carte OpenStreetMap avec un résultat de géocodage.

Vue d’ensemble

Géocoder consiste à retrouver la localisation (sous forme de coordonnées latitude et longitude) d’une adresse. Les logiciels de géocodages offrent dans la plupart des cas les fonctionnalités suivantes:

• Géocodage direct : passer d’une adresse plutôt formatée comme une adresse postale vers une localisation en latitude et longitude
• Géocodage inverse : retrouver l’adresse associée à des coordonnées latitude et longitude
• Autocomplétion : permet de faire des suggestions en temps réel. Cela permet de gagner du temps sur la saisie de l'utilisateur et de minimiser les erreurs tout en facilitant le géocodage

Parmi ces fonctions, la plus compliquée est celle du géocodage direct. Elle consiste à rapprocher un texte libre d’adresses ou points d’intérêts (POI) présent dans une base de référence. Il faut notamment interpréter des abréviations, des omissions ou des erreurs.

Il faut être capable de retrouver « bd Miterand Clermont ». Malgré l’abréviation de « boulevard », l’omission du prénom, les fautes à « Mitterrand », l’abréviation de « Clermont-Ferrand » et l’omission du pays, il faut retrouver « Boulevard François Mitterrand, 63000 Clermont-Ferrand, France ».

Un géocodeur est composé de deux parties : les données d’un côté et le logiciel avec ses fonctionnalités de l’autre.

Données

Parmi les fournisseurs globaux de services et de données, on retrouve les trois plus gros acteurs que sont Google, HERE et TomTom. Google ne fournissant pas de données à la concurrence, il ne reste que HERE et TomTom utilisable par les autres services de géocodage.

Il y a toutefois d’autres sources importantes que sont l’ensemble des données des opérateurs locaux, qu’elles soient OpenData ou acquise de gré à gré. Le projet OpenAddresses est une compilation de ces sources de données OpenData.

Couverture mondiale de la base OpenAddresses

Une autre source globale est OpenStreetMap.

Mais cette carte est trompeuse. Bien qu’il y ait des adresses réparties dans le monde entier, la couverture est diffuse et il n’y a pas de notion d’exhaustivité des zones couvertes contrairement à OpenAddresses.

En France

En France plusieurs bases d’adresses sont également disponibles dont la principale est la BAN (Base Adresses Nationales) sensé être produite par l’IGN .

Il existe également la BD ADRESSE® de l’IGN (base de données non libre), la « Base Adresse Nationale, retravaillées », produite par data.gouv.fr, les BAL en OpenData des collectivistes locales (Base Adresses Locale) et la BANO (Base Adresses Nationales Ouverte) basée sur la compilation d’OpenStreetMap de l’OpenData.

La complexité des bases publiques d’adresses en France, en attendant la simplification attendue pour 2020

Services et logiciels

Choix du panel

Cette comparaison inclut les trois acteurs majeurs propriétaires de données géographiques que sont Google, HERE et TomTom. Ils fournissent des services en ligne depuis leurs propres données. Contrairement à HERE et TomTom, Google ne permet pas l’accès direct aux données qu’il utilise. Il faut obligatoirement passer par son API.

À titre de comparaison, l’IGN France est inclus pour les services qu’il met à disposition. Il fait partie des opérateurs qui sont producteurs et propriétaires de données.

Bing est un acteur secondaire du géocodage, dans le sens ou il utilise des données fournies par d’autres. Il est toutefois parmi ceux fournissant du géocodage web à usage générique.

Mapbox est un fournisseur de service important dans l’écosystème de la cartographie web et libre. Toutefois son service de géocodage n’utilise ni logiciel libre, ni données libres.

Un nombre important d’autres services de géocodage sont disponibles en ligne. Nous retenons ici ceux plus petits utilisant des données et logiciels libres.

OpenCage à la particularité d’être un méta-géocodeur. Il utilise plusieurs logiciels de géocodages libres pour fournir son service. La partie « méta » de consolidation n’est pas libre.

Les logiciels libres de géocodage ont la particularité d'être exploités comme service en ligne par les mainteneurs.

Pelias est le géocodeur initialement construit par Mapzen, aujourd'hui arrêté. Le projet continue toutefois d’être maintenu et exploité commercialement par ces concepteurs sous le nom de « geocode.earth ».

Gisgraphy est un projet français. Le code source en ligne est libre, mais il n’est pas maintenu à jour publiquement. C’est un projet également peu communautaire.

Nominatim est un projet proche d’OpenStreetMap, il s'agit plus d'un gazetteer qu’un géocodeur. Pour servir vraiment de géocodeur il doit être complété par Photon.

Addok est un projet porté par data.gouv.fr, à l’étendue limitée à la France.

Mimirsbrunn est un projet à vocation mondiale, mais qui dans les faits n’est encore limité qu’à la France. Il est porté par Kisio et Qwant.

Logiciels et données

Tout n’est pas toujours aussi simple, mais ici oui. Les données propriétaires sont utilisées par des logiciels propriétaires et celles libre par des logiciels libres.

Ci-dessous l’adéquation entre les logiciels et les données libres:

Service	Logiciel	OpenAddresses	OpenStreetMap	BAN, BANO
geocode.earth	Pelias	x	x
Gisgraphy	Gisgraphy	x	x
OpenStreetMap	Nominatim		x
komoot.de	photon, Nominatim		x
Kisio, Qwant	Mimirsbrunn	x	x	x
data.gouv.fr	Addok			x

Limitations

L’ensemble des services basés sur des données non libres ont deux limitations d’usages communes. Il est parfois, mais pas toujours, possible de les lever en payant plus cher.

Les services tel que Google, HERE, TomTom ou encore Mapbox demandent à ce que les utilisateurs de ces API ne stockent pas les résultats des géocodages. La mise en cache est quand même permise pour des raisons de performance, mais limitée à des durées allant de 24 h à 1 mois.

L’autre limitation de Google, HERE et TomTom est l’obligation de représenter les points géocodés sur la carte du fournisseur idoine. Il est donc impossible de géocoder chez Google Maps et d’afficher sur OpenStreetMap par exemple.

À l’opposé, les résultats des adresses géocodées depuis des données libres peuvent être conservées et affichées sur n’importe quelle carte.

Indexation

Avant de pouvoir effectuer une recherche d’adresse, un géocodeur doit indexer les données de référence sur lesquelles il va effectuer ces recherches. Il y a alors deux possibilités. Soient les données sont déjà liées aux entités administratives ou géographiques, soit ce n’est pas le cas.

64001_0140_00026;64001_0140;26;Chemin de Seron;64460;64001;Aast;-0.088888;43.289274

Exemple d’une adresse de la BAN. Ici le « 26, Chemin de Seron à Aast » avec le code INSEE : 64001. On a donc une localisation géographique de l’adresse et son rattachement à une commune, via son code INSEE. Il va toutefois falloir plus d’informations pour indexer pleinement cette adresse, comme le nom du département.

On peut aussi vouloir indexer des POI sur lesquels on a peu d’information, par exemple juste un nom, un type et des coordonnées géographiques. On ne connaît donc pas la commune ou la zone géographique de rattachement.

Point de vue;Belvédère Abbé Pierre;-1.40303;43.36296 

Pour indexer ces points d’intérêts ou compléter les adresses il va falloir utiliser un gazetteer (index des lieux géographiques). Notamment pour les POI, il faut partir des coordonnées géographiques et faire un géocodage inverse pour retrouver des zones administratives et régions auxquelles ils appartiennent. Il sera ensuite possible de faire une recherche dessus, par exemple avec la recherche « point de vue Combo-les-bains ».

Géocodage direct

Le géocodage est le rapprochement d’un lieu ou d’une adresse textuelle donnée avec une adresse de référence figurante dans les données indexées.

La recherche

La recherche peut être faite à partir d’un bloc unique de texte représentant l’adresse tout entière (plein texte). Elle peut aussi être une adresse déjà segmentée en champs.

La fonctionnalité de recherche la plus répandue est la recherche plein texte et l’indexation plein texte. Cependant, certains géocodeurs offrent aussi une recherche en champs segmentés. Il y a alors deux façons en interne au géocodeur d’indexer les données, de façon segmentée ou non. Le géocodeur peut alors posséder un outil de normalisation d’adresses capable de segmenter une adresse fournit en plein texte.

Les filtres

Des conditions peuvent être imposées pour réduire l’espace de recherche. L’objectif est de contraindre les résultats à être dans une zone spécifique lorsqu’elle est connue. Cela permet d’éviter les résultats erronés.

Les filtres disponibles dans les API ou logiciels limitent les résultats à :

• un pays ou plus génériquement à une zone administrative ;
• un code postal ;
• une zone rectangulaire définit par une paire de coordonnées (bbox), ou par un cercle défini par les coordonnées de son centre et par une distance maximale.

Un filtre est aussi parfois présent pour limiter les résultats à un type ou une source de données, comme les POI ou les adresses.

Les paramètres de filtres les plus fréquents sont le pays et la bbox.

Les biais

Les biais, contrairement aux filtres ne sont pas stricts et influent sur le résultat. L’idée est de conseiller ou d’aider le géocodeur à obtenir un meilleur résultat. On retrouve dans cette classe les paramètres suivants :

• zone administrative ;
• coordonnées pour privilégier des résultats proches, par exemple lorsqu’un utilisateur fait une recherche avec une carte déjà centrée sur une zone d’intérêt ;
• indication de langue dans laquelle est saisie l’adresse.

Le paramètre le plus courant est la recherche à proximité de coordonnées.

Paramètres de requête des API

Ci-dessous est présenté un résumé des paramètres de recherche par service.

Solution	Plein texte	Par champs	Autocomplétion	Prise en compte de la langue	Filtre	Biais
Google Maps	x	-	x	x	Bbox, Country, postal_code	route, Locality, adminstrative area, Region (TLD)
Here	x	x	x	-	Bbox, Country	countryfocus
Tomtom	x	-	x	-	bbox, CountrySet	Proximity, Radius, Language
IGN	x	-	x	-	bbox, admin_boundary
Mapbox	x	-	x	x	Type, Country, Bbox	Proximity, FuzzyMatch, Language
Bing	x	x	x	-	-	-
OpenCage	x	-	-	-	countrycode	Proximity
Addok	x	-	x	-	postal_code	Proximity
Pelias	x	x	x		placetype, Country, Bbox, Raduis, admin_boundary, Data source	Proximity
Gisgraphy	x	x	x	-	radius, Country	Proximity, Fuzzy
Mimirsbrunn	x	-	x	-	dataset, Type, Zone	Proximity
Nominatim	x	x	-	-	countrycodes, Bbox	-
photon, Nominatim	x	-	x	-	bbox, Tag osm	Proximity

La normalisation

La première phase de traitement est de nettoyer l’adresse recherchée. Il faut notamment essayer de reconnaître les abréviations. Suivant comment est implémenté le géocodeur il peut également segmenter l’adresse en champs (numéro, type de voie, nom de la voie…).

La stratégie la plus répandue dans les géocodeurs libres est d’utiliser des dictionnaires de synonymes et d’appliquer des expressions régulières. Ces traitements sont spécifiques au pays et à la langue. Ils sont donc à mettre en place pour chaque pays à supporter. Cette approche est celle adopté par Mimirsbrunn et Addok… qui sont justement les géocodeurs ne supportant que le français.

L’autre approche est de travailler de manière générique en utilisant un analyseur d’adresse probabiliste construit par apprentissage depuis des jeux de données d’adresses provenant de tous les pays. C’est ce que fait « libpostal » depuis les adresses contenues dans OpenStreetMap. Libpostal a été réalisé par Mapzen et est utilisé dans Pelias. Il est capable de segmenter l’adresse et de la reformuler (normalisation).

La corrélation

Une fois l’adresse améliorée il faut essayer de la faire correspondre à une adresse indexée. Les géocodeurs s’appuient sur d’autres logiciels pour stocker, indexer et retrouver rapidement des données. Pelias, Photon et Mimirsbrunn sont basés sur le moteur de recherche « Elasticsearch ». Gisgraphy utilise le moteur de recherche « Solr ». Mais Elasticsearch comme Solr sont basés sur le composant de recherche « Lucene ».

Addok n’utilise pas un moteur de recherche ou d’indexation. Il utilise une base de données clés-valeurs stocké en mémoire nommé « Redis ». Addok fait lui-même son indexation et sa recherche.

Les stratégies de corrélation sont différentes pour chaque logiciel.

Nominatim tout seul ne fait que de la recherche exacte.

Pelias et Gisgraphy font de la normalisation du texte à rechercher puis le découpent par mots. Ces mots normalisés sont alors nommés tokens. Ils sont ensuite recherchés dans l’index.

Addok utilise de la normalisation suivie d’une phonétisation pour créer les tokens. Cela permet plus de tolérance aux fautes.

Mimirsbrunn et Addok (en option) utilisent des trigrammes pour découper les tokens. C’est une autre approche pour être tolérant aux fautes qui ne dépend pas la phonétisation et donc de la langue.

Fonctionnement interne

Les détails de fonctionnement interne ne sont disponibles que pour les logiciels libres.

Solution	Normalisation, Standardisation	Corrélation	Corrélation autocomplétion	Moteur d’indexation	Gazetteer	Données
Addok	lexique	Phonétisation, ou, Trigrammes	EdgeNGram, Trigrams	Redis	-	BAN, BAL, BANO, Lux
Pelias	libpostal	Token normalisé + EdgeNGram	EdgeNGram	Elasticsearch	Who’s On First	OpenAddresses
Gisgraphy	lexique	Token normalisé (?)	EdgeNGram	Solr		OpenAddresses, OSM
Mimirsbrunn	regex (en dur)	Trigrammes	EdgeNGram	Elasticsearch	Cosmogony	OpenAddresses, OSM, BAN
Nominatim		strict	-	Postgres	Nominatim	OSM
photon, Nominatim			EdgeNGram	Elasticsearch	Nominatim	OSM

Le résultat du géocodage

Les géocodeurs fournissent en sortie une liste de résultats triés par pertinence.

Chacune des entrées du résultat sont des données structurées comprenant l’adresse ou l’entité trouvée avec des informations complémentaires issue du gazetteer, comme les zones administratives parentes. Ces informations permettent notamment à l’utilisateur de désambiguïser le résultat pour sélectionner le bon.

{
  "type": "FeatureCollection",
  "version": "draft",
  "features": [
    {
      "type": "Feature",
      "geometry": {
        "type": "Point",
        "coordinates": [
          -1.573606,
          47.250946
        ]
      },
      "properties": {
        "label": "Rue des Fleurs 44300 Nantes",
        "score": 0.979169746594336,
        "id": "44109_3156",
        "type": "street",
        "name": "Rue des Fleurs",
        "postcode": "44300",
        "citycode": "44109",
        "x": 354275.57,
        "y": 6693419.66,
        "city": "Nantes",
        "context": "44, Loire-Atlantique, Pays de la Loire",
        "importance": 0.7500369591320318,
        "distance": 0
      }
    }
  ],
  "attribution": "BAN",
  "licence": "ODbL 1.0",
  "query": "Rue des Fleurs 44300 Nantes",
  "center": [
    -1.573606,
    47.250946
  ],
  "limit": 5
}

Exemple de résultat du géocodeur au format GeocodeJSON

Score

Chaque résultat contient également une ou plusieurs notions de qualité pour ordonner les résultats entre eux. Le géocodeur calcule un score, mais ce score n’est pas toujours disponible en sortie. Il n’est souvent qu’une mesure interne et spécifique à une recherche.

Niveau de détail (up hierarchy)

Dans les résultats est souvent présent une notion de niveau de détail. Par exemple on recherche une rue, mais elle n’est pas trouvée et le résultat est uniquement au niveau de la ville.

Précision géographique

La précision concerne la qualité géographique du résultat. Par exemple les coordonnées retournées sont sur un bâtiment, au centre d’une parcelle, calculé par proximité à d’autres adresses (interpolation), au centre d’une commune…

Approximation (fuzzy)

C’est la mesure de la proximité entre le texte de l’adresse recherchée et celle trouvée.

On peut avoir trouvé un résultat avec un numéro de rue (bon niveau de détail) et géographiquement de bonne qualité (précis) mais seulement dans une ville au nom approchant celui demandé.

Contenus des résultats des API

Ci-dessous un tableau déataillant les attributs disponibles dans les résultats de géocodage

Solution	Approximation	Niveau de détail	Précision géographique	Catégorie	Score
Google Maps	partial_match	-	-	Types : Street_address, route, intersection, political, country, administrative_area_level_*, Colloquial_area, locality, sublocality, neighborhood, premise, subpremise, postal_code, natural_feature, airport, park, point_of_interest	-
Here	MatchQuality	MatchCode	MatchType		Relevance
Tomtom	fuzzyLevel	-	-	Type : POI, Street, Geography, Point Address, Address Range, Cross Street	score
IGN	-	matchType	Qualite	CountryCode:, Toponymes, Adresses, Parcelles	-
Mapbox	-	place_type	accuracy	Category : Country, Region, Postcode, District, Place, Locality, Neighborhood, Address, Poi	relevance
Bing	matchCodes		-	Address, Neighborhood, PopulatedPlace, Postcode1, AdminDivision1, AdminDivision2, CountryRegion	confidence (enum)
OpenCage	-	-	-	-	confidence, Rank
Addok	-	type	-	-	score
Pelias	match_type	-	match_type, Accuracy	Layer : Venue, Address, Street, Neighbourhood, Borough localadmin, Locality, County, Macrocounty, Region, Macroregion country, Coarse, Postalcode	confidence
Gisgraphy	-	-	-	-	score
Mimirsbrunn				addresses, points of interest, administrative regions, Streets
Nominatim	-	-	-	-	-
photon, Nominatim	-	-	-	-	-

Qualité

La qualité des résultats d’un géocodeur dépend donc de la qualité géographique des données qu’il indexe, mais aussi de tous les algorithmes de rapprochement entre les adresses à géocoder et celles de références. Pour finir, la qualité dépend également de la façon d’établir un score depuis l’ensemble des mesures pour proposer les « meilleures » concordances.

Mesure de la qualité

Des études évaluent la qualité des géocodeurs comme une boite noire. Il traite le géocodeur comme un tout : logiciel et données [0] [1] [2] [3].

Elles mesurent alors le taux de réponses des géocodeurs. Toutefois, la réponse ou non est liée à la politique du géocodeur, certains préfèrent ne pas apporter de réponse plutôt qu’une réponse avec une confiance trop faible. D’autres répondent à tous les coups, quel que soit ce qui est demandé.

Le second élément de mesure est la précision spatiale, quelle est la distance médiane ou moyenne avec la position effective de l’objet demandé.

La dernière est la mesure de la stabilité du géocodage à la variabilité de la demande. Des demandes différentes ou similaires pour un lieu unique doivent donner le même résultat.

Autocomplétion

L’autocomplétion est une aide à la saisie qui propose des mots complets.

Toutes les solutions libres ont ici la même approche. Elle consiste à indexer les mots constituant des adresses sous forme de « edge-n-grammes ». Derrière ce terme en apparence compliqué se cache quelque chose de simple. Pour aider à la saisie de « Toulouse », l’on va indexer « Toulouse » sous « t », mais aussi sous « to », « tou », « toul »… Ainsi l’on peut retrouver la suite rapidement depuis le début du mot.

Les propositions d’autocomplétion peuvent également être influencées par un éventuel biais, comme la proximité spatiale à une zone de recherche, ainsi que par ce qui a été saisi avant le mot en cours de complétion. Une adresse comprenant un token déjà saisi et un début de token possible va être priorisé dans la liste des propositions d’autocomplétion.

Lucene (Elasticsearch et Solr) possède de base cette fonctionnalité d’indexation par « edge-n-grammes ».

Géocodage inverse

Le géocodage inverse prend en entrée des cordonnées et recherche une entité à proximité. Cela consiste à retrouver l’adresse la plus proche ainsi que toute la hiérarchie d’élément supérieur (rue, commune…). Mais cette plus proche adresse peut être assez loin. Il faudra dans ce cas utiliser un élément moins précis mais géographiquement plus exact, comme un lieu-dit ou directement une route ou une commune.

Parmi tous les géocodeurs étudiés ici, seul Addok à la particularité de ne pas utiliser de gazetteer et donc de ne pas être capable de faire du géocodage inverse vers autre chose que des adresses.

Pour effectuer rapidement cette recherche, il faut créer un index géographique des adresses et entités du gazetteer. Cette indexation est un classique des bases de données géospatiales. Cela fait en particulier appel à des R-Trees et des algorithmes de « point dans un polygone ».

Autres fonctionnalités

Géocodage par lot

Le géocodage direct ou inverse d’une grande quantité de données prend du temps. Mais si l’API du service n’offre pas de point d’entrée dédiée au traitement de masse, une grande partie du temps va être perdue en temps d’échange réseau.

Une API de géocodage par lot va permettre d’envoyer un gros volume d’adresses (par exemple en CSV). L’appel va être fait en n’utilisant qu’un seul aller-retour sur le réseau avec le service. Au total le temps de traitement va être bien moindre qu’avec un aller-retour par adresse.

Autres détails

D'autres caractéristiques des géocodeurs sont étudiées ici.

Solution	Par lot	Format sortie	Couverture	Langue	Approche	Point de vue politique	Stockage
Google Maps	-		Monde	x		(x)	sans
Here	-			-	Multi-pays	x	sans
Tomtom	x			-		x	sans
IGN	-	OpenLS	France	-	Mono-pays	-
Mapbox	x			x		-	avec ou sans
Bing	-			-		-	sans
OpenCage	-		Monde (diffu)	-	Mixte	-	oui
Addok	x	GeocodeJSON	France, Lux	Français	Multi-pays	-	oui
Pelias	-	GeocodeJSON	Liste de Pays		Globale	-	oui
Gisgraphy	-		Monde (diffu)	-	Globale
Mimirsbrunn	-	GeocodeJSON	Monde (diffu)	Français	Globale	-	oui
Nominatim			Monde (diffu)	-	Globale	-	oui
photon, Nominatim	-	GeocodeJSON	Monde (diffu)	-	Globale	-	oui

Conclusion

Parmi ces géocodeurs, Google est celui qui a accès au plus de données. Pour autant, ce sont HERE et Pelias qui offrent le plus de fonctionnalités. Dans la catégorie des géocodeurs libres, Pelias utilise la normalisation de libpostal qui est là pour offrir internationalement de meilleurs résultats. Toujours dans le libre, Addok et Mimirsbrunn sont ceux qui ont un avantage algorithmique. Le géocodeur est limité au français mais celui ci pourrait être étendu à d’autres langues ou généralisé de manière indépendante de la langue. Pelias a été conçu comme un géocodeur global et il peut se révéler lourd et coûteux à mettre en œuvre face à des solutions plus légères comme Addok et Mimirsbrunn.

Vous avez des besoins en géocodages génériques ou spécifiques ? Vous souhaitez géocoder depuis votre propre base de données ? Nous pouvons vous accompagner dans cette démarche.

Références

[0] Paul A. Zandbergen. A comparison of address point, parcel and street geocoding techniques, 2007.

[1] Daniel W Goldberg, Morven Ballard, James H Boyd, Narelle Mullan, Carol Garfield, Diana Rosman, Anna M Ferrante and James B Semmens. An evaluation framework for comparinggeocoding systems, 2013.

[2] Sylvia Cho, Karthik Natarajan. Comparative evaluation and analysis of online geocoding services, 2006.

[3] Duangduen Roongpiboonsopit and Hassan A. Karimi. Comparative evaluation and analysis of online geocoding services, 2009.