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.

[mister3957]

Oui effectivement, c'est pour ça que j'avais fait une fonction qui renvoyait LA meilleure adresse, avec un seuil en dessous duquel il fallait appelait une autre fonction qui renvoyait les 10 adresses les plus crédibles. C'est histoire de ne pas laisser en plan mon utilisateur en disant "ben démerde toi, on a pas trouvé".

Mais déjà je me rends compte que je devrais séparer la correction d'erreur du système de pondération, et ainsi en retour proposer un facteur de précision du résultat (100% si on a même le numéro, 90% si on a juste la rue, 50% si on a juste la ville, par exemple), ainsi qu'un facteur de correspondance entre la nature des données en entrée et celle du résultat (ex : Toulose et Toulouse : 93%, Toulouse et Toulouse : 100%).

D'ailleurs dans le facteur de précision, je pourrais prendre en compte la géométrie de l'élément le plus pertinent trouvé. par exemple si on a juste la rue et pas le numéro, il y aura une différence dépendante de si la rue fait 15 bornes ou 100 mètre. Pareil si on géocode au clocher, selon la superficie de la ville, le facteur précision ne sera pas le même. De plus, ces données là peuvent être pré calculées, donc ils n'y aura pas d'opération géométrique dans la fonction de géocodage.

Ce qui est compliqué à gérer, c'est lorsque l'on va chercher les X adresses les plus pertinentes, et qu'il y a une erreur.

Par exemple, "Toulose" au lieu de "Toulouse", en appliquant l'algorithme de Levenshtein, ça va me renvoyer de grosses correspondances avec "Toulouse" mais aussi "Toulon" (et peut-être d'autres). Alors je devrais chercher la rue dans chacune de ces villes et trier les résultats après coup.

Je sens que je vais m'amuser..

[prgasp77]

Interpréter les données utilisateurs, c'est toujours un peu lourd et frustrant. Peut être pourrais-tu aussi ajouter des « vues » à ta base de données pour ajouter un peu de redondance et pouvoir faire des recherches différentes. Par exemple, lister toutes les viles dans lesquelles on trouve une rue « des petits cailloux ronds ». Pourquoi pas aussi rectifier un nom de rue en n'utilisant que celui-ci (« avenue du Général de Galles » → « du Gal de Gaulle »).

Toutes les propositions que je pourrais te faire ne seront que des idées vagues. Peut-être peux-tu aussi te tourner vers les membres des forums base de données ?

[Pandapi]

Bonsoir,

Tu n'as pas encore l'air vraiment fixé sur le fonctionnement de ton système côté utilisateur. Du coup tu pourrais t'inspirer de ce qui existe déjà dans le domaine. Si tu es capable de décomposer les différents éléments de l'adresse (de toute façon c'est nécessaire pour ton système), tu es capable de cibler les erreurs de ton utilisateur. Tu peux donc lui proposer des corrections précises plutôt que juste des adresses qui semblent coller.

Par exemple si il fait une faute dans le nom de sa rue, tu peux facilement lui en proposer des proches de ce qu'il a écrit vu qu'il t'a correctement renseigné le pays, le code postale et la ville. De cette façon, tu lui permets également de comprendre ce qui pose problème dans ce qu'il a tapé (c'est important que l'utilisateur comprenne ce que fait le système et que ça lui semble logique, ça lui permet ensuite de se corriger puis de mieux l'utiliser).
Cela me semble plus normal pour ce type de système, d'aider l'utilisateur à obtenir ce qu'il souhaite en l'accompagnant plutôt que de lui sortir des résultats à tous prix, car dans le cas où aucun de tes 10 résultats ne sera bon, l'utilisateur n'aura aucune indication sur ce qu'il doit modifier ou faire pour obtenir ce qu'il veut (car aucun feedback des problèmes rencontrés par le système).

Ce sont des idées d'aspect purement utilisateur, mais je pense qu'elles sont importantes à se poser si tu veux produire un système utile (après je ne sais pas dans quel contexte tout cela se place, peut-être que sortir un mauvais résultat de temps en temps reste plus tolérable que de demander des précisions à l'utilisateur)

[Graffito]

Bonjour,

Une recherche d'adresse s'apparente à une recherche documentaire en texte libre. Le prncipe est de considérer chaque adresse de la base de donnée comme un document et de l'indexer suivant les mots clés qui la composent. Avec le même "parsing", on extrait les mots clé de la question (adresse recherchée), puis on affecte une note à chaque adresse dela base partageant des mots clés avec la question, cette note dépendant du nombre de mots clés communs (avec une dépréciation en cas d'orthographe inexacte) et du caractère discriminant de chaque mots clé commun (Honfleur sera plus sélectif que Paris).

Regarde cette discussion : http://www.developpez.net/forums/sho...=pond%E9ration

[mister3957]

Bon ben voilà, je vous tiens au courant de l'avancé des travaux,

J'ai donc modifié mon import de données afin d'avoir un schéma plus relationnel :

- Pays
- Régions
- Places
- Villes
- Rues
- Numéros de rues

Avec des tables reliant

- Pays <=> régions
- Pays <=> places
- Pays <=> villes
- Régions <=> villes
- Villes <=> places
- Villes <=> rues
- Rues <=> numéro

Les régions ça ne sert pas en France, mais plutôt pour les USA, ça corresponds aux états.

Dès la semaine prochaine j'attaquerais le géocodage pour la France, puis essayerais de flexibiliser pour les autres pays (si on prend en compte les régions, puis les différents formats d'adresses).

En tout cas pour le moment ça sent bon

Merci à vous et à bientôt