Discussion :

[mister3957]

Bonjour,

Je ne sais pas bien où poster ma question, j'espère que cette catégorie est la bonne, veuillez m'excuser si ça n'est pas le cas.

On m'a demandé d'étudier le sujet du geocodage, c'est à dire la recherche de la position (lati/longi) d'une adresse donnée, de manière textuelle.

Niveau sources de données, j'ai trouvé OpenStreetMap ainsi que GeoNames, le premier fournissant pas mal d'information sur les limites administratives ainsi que les routes, et le second, d'après ce que j'ai compris, sur les traductions (du genre Lille <=> Rijsel, Antwerpen <=> Anvers ou encore Barcelone <=> Barcelona).

Ensuite il a la formulation de l'adresse, en France, on dira [numero], [rue], [CP] [ville] (ex: 5, chemin des tulipes, 75000 Paris) tandis qu'en Belgique ou en Espagne, ce sera plutôt [rue], [numero] [CP] [ville] (ex : "Chemin des tulipes, 5, 1040 Etterbeek" ou encore "Calle Del Sol, 46, 28000 Madrid"). Aux USA, j'imagine que c'est encore différent.

Puis il y a les fautes de frappes à gérer, car souvent les adresses proviennent de saisies de secrétaires ou de particulier sur notre formulaire web, par exemple "5, chemin des Tulipes, 75000 Paris" au lieu de "5, chemin des Tulies, 75000 Paris". L'adresse erronée doit pouvoir revenir à l'adresse exacte, mais avec un "score" de par exemple 97% au lieu de 100%. On définira les coefficients (genre se tromper dans le nom d'une ville est plus important que dans le nom d'une rue, par exemple).

Et enfin les nombres, comme "12, rue du 11 Novembre" au lieu de "12, rue du Onze Novembre". Et puis j'imagine qu'il y encore 10.000 diableries auxquelles je n'ai pas encore pensé.

Enfin bref, l'objectif est de retrouver le point d'une adresse, en quelques millisecondes, comme le fait Google Maps.. J'ai fait des tests là dessus, et une formulation différente du pays, avec des fautes de frappes, ainsi que les traductions de nombre littéraux en chiffres et inversement, en très peu de temps, il arrive à me "corriger" et à trouver la bonne adresse finale.

Mais comment font-ils ?

Actuellement, j'ai pu importer les données d'adressage d'OpenStreetMap ainsi que les données de GeoNames (ciblées sur la France) dans une base de données PostgreSQL. En requête, j'utilise la fonction "levenstein" contenue dans l'extension "fuzzystrmatch" pour au moins pondérer les choses.

Mais c'est long, très très long à s'exécuter, sur une requête SQL via PostgreSQL, bref, inexploitable au quotidien.

J'ai donc questionné mon entourage, notamment des chercheurs que j'ai rencontré dans mon ancienne entreprise, spécialisés dans la R&D. Ils m'ont dit qu'il fallait engranger toutes les informations que je possédais dans un graph, et ensuite effectuer des calculs dessus.. Bon, à part savoir que je faisais fausse route, ça ne m'avançait pas trop.

J'ai donc essaye Nominatim ainsi que gisgraphy, mais l'un ne gère pas les fautes de frappes, l'autre ne prend pas en compte des numéros d'adresses, du coup l'un comme l'autre ne conviennent pas.

Est-ce que quelqu'un peut me donner des indications pour résoudre ce type d'exercice de manière à ce qu'il soit exploitable ?

En vous remerciant par avance

[Pandapi]

Bonjour,

Je trouve ton problème intéressant, je serais curieux de connaitre la modélisation que tu y as apporté ?
Parce que ton explication est claire sur les différents aspects du problème que tu veux pouvoir résoudre (différence de nomenclature d'une adresse selon les langues, fautes de frappe...), mais tu ne dis pas comment tu les as résolus.
Pour avoir une idée du pourquoi la requête met tant de temps il faudrait savoir comment tu as implémenté les choses.

Ceci dit, en dehors des performances probablement bonnes des serveurs de google map, il y a surement également des soucis de modélisation si tu n'as fait qu'importer des open data, comme on te l'a apparemment déjà dit.

[mister3957]

Merci pour cette réponse.

Je ne voudrais pas trop rentrer dans les détails de l'implémentation via PostgreSQL pour éviter d'être hors sujet, mais dans un premier temps, ma préoccupation est de savoir si je suis dans le droit chemin ou alors si je fais fausse route.

Donc sans rentrer dans les détails, j'ai importé les données d'adressage d'OpenStreetMap dans une table "addresses" pour me retrouver avec cette structure :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
  country character varying(255),
  city character varying(255),
  postcode character varying(255),
  street character varying(255),
  geometry geometry,
  housenumber integer

Cette table possède 3406835 lignes pour les données de la France.

Et voici la requête pour trouver l'adresse la plus pertinente en fonction des arguments passés :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
SELECT
	(100
		- Coalesce((levenshtein(argCity, "city") * 4), 50)
		- Coalesce((levenshtein(argPostcode, "postcode") * 4), 50)
		- Coalesce((levenshtein(argStreet, "street") * 3), 50)
		- (abs(("housenumber" % 2) - (argNumber%2)) * 3)
		- (CASE WHEN "housenumber"=argN THEN 0 ELSE 1 END)) as rankvalue,
		"country",
		"city",
		"postcode",
		"street",
		"housenumber",
		St_Y("geometry"),
		St_X("geometry")
	FROM
		addresses
	WHERE country = argCountry
	ORDER BY rankvalue DESC
	LIMIT 1;

Ça met un peu plus d'une seconde à s'exécuter, ce qui est trop long, sachant que ça ne gère pas le type d'adresse littérale, mais par composante d'adresse, et que ça ne gère pas non plus les chiffres en lettre ou inversement.

Donc ma première interrogation est :
- Est-ce que c'est le rôle d'une base de donnée d'effectuer ce genre d'exercice ? L'objectif est de savoir si je me lance dans l'amélioration du travail déjà effectué sur PostgreSQL ou si je change complètement de stratégie pour un service en python ou C++ à base de calcul sur graph ?

Et ensuite :
- Comment gérer les différentes nomenclatures d'adresse ? => expression régulières ?
- Comment gérer les différents termes (Rijsel <=> Lille, Barcelone <=> Barcelona, Milan <=> milano, etc.) ?
- Comment gérer les chiffres (rue du 11 Novembre VS rue du Onze Novembre) ? => Algorithme phonétique style Soundex ou Metaphone / Double Metaphone ?

Merci à vous

A bientôt

[Pandapi]

Je pense que déjà ça dépend des performances que tu veux atteindre et du temps que tu as pour ce projet, parce que modifier le modèle de fonctionnement sera plus long à faire qu'importer les données telles quelles.

Tu pourrais peut-être te renseigner sur les technologies sémantiques (j'y pense parce que je suis dedans en ce moment) qui pourraient éventuellement se prêter à ton cas voire à certaines améliorations que tu pourrais vouloir dans le futur (comme tenir compte de la provenance de tes données, vu que tu utilises des open data) :
http://fr.wikipedia.org/wiki/Triplestore
Cependant ça nécessiterait un travail certain sur la création d'un modèle et l'incorporation de tes données dans celui-ci (il en existe peut-être déjà qui seraient adaptés à ce que tu veux).

Sinon, comme tu sembles penser à le faire, il y a surement des améliorations possibles sur ce que tu as déjà (optimisation des performances de ta BD), après savoir à quel point et si ça t'amènera aux performances que tu souhaites, je ne peux pas te dire (la section SGBD du site pourra probablement t'aider pour ça si tu leur donnes ton implémentation/configuration actuelle)

Pour tes autres problèmes tu as l'air d'avoir déjà des pistes, les regex pourraient en effet résoudre plusieurs de tes problèmes, tout comme les technologies sémantiques.
Par contre quand tu dis

Ça met un peu plus d'une seconde à s'exécuter, ce qui est trop long, sachant que ça ne gère pas le type d'adresse littérale, mais par composante d'adresse, et que ça ne gère pas non plus les chiffres en lettre ou inversement.

Même si un utilisateur ne fera pas la différence entre les différents temps de traitement, je ne pense pas que tu doivent tout mettre dans le même sac. Tu as différents problèmes et tu devrais, comme tu l'as déjà fait, bien établir les limites de chaque problème et trouver la solution la plus adaptée au niveau performances pour chacun d'eux (vu qu'apparemment les performances ont l'air primordiales dans ton cas).

Je repasserai voir comment le sujet avance (si tu donnes des nouvelles de ton projet et/ou si d'autres personnes répondent), parce que je le trouve intéressant

[mister3957]

Merci beaucoup pour cette réponse.

Un peu plus d'une seconde ça ne parait pas beaucoup, mais en batch sur des milliers d'adresses, ça commence à poser problème. D'autant plus que c'est surtout la fonctionnalité de sortir les, par exemple, 10 adresses les plus crédibles.

Mais j'ai trouvé un programme qui géocode des adresses américaines. Il tourne sous ruby avec comme base de donnée sqlite3. La différence avec ma fonction est que lui divise le traitement plutôt que faire une seule fonction "usine à gaz".

Peut-être qu'en faisant pareil et en optimisant la base, ça peut améliorer les performances. Je traduirait ce petit programme en SQL.

Concernant les fonctionnalités, je vais oublier les chiffres à traduire en lettre, ça me parait futile, du moins pour le moment.

Pour les noms des pays / villes dans différentes langues, j'ai vu que les traductions étaient présentent dans OpenStreetMap, donc à moi de les extraire et de me débrouiller pour les utiliser.

Enfin pour les nomenclatures d'adresses, je verrai plus tard, c'est optionnel pour le moment.

Je vous tiendrai au courant

A bientôt

[prgasp77]

Je dis peut être quelque chose de stupide, mais peut être que tu ne devrais effectuer le calcul de points que pour des lignes pré-filtrées. Pourquoi ne pas présumer dans un premier temps que la ville est correctement orthographiée, chercher dans cette ville l'adresse, et si le meilleur résultat est trop bas --- avec une seconde requête --- élargir la recherche.

Un petit Where peut tout changer.