adresses et syntaxe formelle ?

[invitecf343e72]

Bonsoir,

je ne sais pas exactement ce que je cherche, le but de ce post est de trouver des conseils pour m'orienter dans mes travaux.

Je travaille actuellement sur le géocodage d'adresses.
Je dispose d'un référentiel d'adresses contenant toutes les adresses connues d'une ville, département ou région peu importe.

Le but du travail est de faire correspondre les adresses du référentielle avec des adresses que l'on peut rencontrer dans des fichiers du type administratif qui ne sont pas forcément "normées"

Par exemple dans le référentiel je vais avoir

"6 Rue du Général de Gaulle , 55 555 LE VILLAGE"

alors que dans mon fichier d'adresses à localiser je vais rencontrer plutôt

"6, Rue du Gal de Gaulle , Résidence "Le Fleurus", 4ème gauche , 55555 LE VILLAGE"
ou encore
"Le Fleurus , Appt 254 , 6 R du GENERAL DE GAULLE , 55 555-LE VILLAGE"

et encore bien d'autres choses...

Je suis à la recherche d'un cadre théorique pertinent de compréhension syntaxique des adresses (je ne sais pas si c'est exactement la façon de formuler les choses) me permettant par la suite d'élaborer des algorithme de "compréhension" des adresses dans le but de leur normalisation (et séparer l'inutile par exemple "4ème gauche", "Appt 254", le pertinent "6 R du général de Gaulle" et le peut-être pertinent "Résidence "Le Fleurus"")

Voilà si vous avez des idées, des connaissances, des conseils d'approche ou de lecture, je suis tout ouïe !

Merci
-----

[shokin]

Permettez que je déplace cela en informatique.

Si cela n'a même pas sa place en informatique, je n'y vois guère place sur ce forum.

[invite4492c379]

Hello,

je pense que le plus simple et le plus rapide est de demander ces infos à Google maps, Bing et compagnie via leur API d'accès ... enfin en première idée.

[invitecf343e72]

API d'accès ? Qu'est ce que c'est ?

Il doit y avoir des droits de propriété par ailleurs...

La volumétrie des données est de plusieurs dizaines de millions d'adresses.

[A voir en vidéo sur Futura]

[invite4492c379]

API d'accès ? Qu'est ce que c'est ?

Une explication en anglais, mais en gros c'est ce que tu recherches : faire faire à un programme une recherche du genre "18, rte de lilas, 99780 petaouch" et il te répond un truc du genre (bon il y a du boulot quand même ) formatted address:"18 route des Lilas, F-99780 Pétaouch, France" (quand il arrive à décoder l'adresse).

Bing et d'autres doivent le faire aussi ...

Il doit y avoir des droits de propriété par ailleurs...

La volumétrie des données est de plusieurs dizaines de millions d'adresses.

plusieurs dizaines de millions ??? En gros toute le France métropolitaine ???
Le nombre de requêtes sur Google est limité à 2500 rq/j => dans les 10.000 jours de boulot
Avec un accès payant tu peux monter à 100.000 rq/j => 1 année de boulot ...

Par curiosité ... Comment se retrouve-t-on à vouloir (devoir ?) faire une analyse de 10⁷ adresses ? Tu travailles à la Poste ? Les adresses sont locales ? Tu as des doublons ? Tu veux devenir le maître du monde ?

[invite4492c379]

Si tu cherches un peu sur google tu trouves aussi un tas d'applications mais bon 10.000.000 d'adresses ...

[invitecf343e72]

oui c'est pour ça que je n'envisage pas de solution "externe" , ce sont des fichiers divers et variés.

Le temps de traitement envisagé est de l'ordre de la demi journée une fois l'algorithme mis au point.

C'est pour ça je cherche des fondements conceptuels pour mettre de "l'ordre" dans les infos.

[invite765732342432]

Il existe plusieurs solutions de ce genre sur le marché, vendues en général assez cher...
Ceci est juste pour dire que ce n'est pas un problème trivial.

Néanmoins, il doit être possible de faire un travail correct.
La première étape à faire est de trouver le code postal, c'est le plus simple à identifier.
Ensuite, tu disposes d'une liste de communes correspondant à ce code (je suppose que tu as ça sous la main)
Tu fais une recherche non-stricte dans la chaine pour trouver un truc qui ressemble à l'un des noms de commune obtenu.
Ca nettoie déjà bien la chaine, après il te reste un peu de boulot, mais pas grand chose.

PS: le temps de traitement envisagé me semble faible pour "plusieurs dizaines de millions d'adresses". Il suffit de regarder le nombre de traitement à la seconde que ça représente.

[invitecf343e72]

Je ne cherche pas de solutions "du marché" mais merci quand même de me le signaler
Le problème est effectivement non trivial.
La récupération du code postal et du nom de commune pour une première localisation grossière (niveau commune) est assez aisée en fait.

C'est pour le reste que ça se corse gravement.

Concernant le temps si j'ai un algo robuste et un minimum bien pensé et optimisé il est même probable qu'il tourne entièrement en moins d'une heure sur ce volume.
Ce n'est absolument pas le temps de traitement qui me préoccupe.

Je suis à la recherche d'algorithme de compréhension de la syntaxe, c'est pour ça que j'avais préalablement posté en sciences humaines pour atteindre des linguistes, alors le modo a préféré le déplacer en informatique... :/

[invite4492c379]

De quel d'elai disposes-tu ? Sous quelle forme se présente ta base ?

[invite765732342432]

Je dispose d'un référentiel d'adresses contenant toutes les adresses connues d'une ville, département ou région peu importe.

Le but du travail est de faire correspondre les adresses du référentielle avec des adresses que l'on peut rencontrer dans des fichiers du type administratif qui ne sont pas forcément "normées"

En fait je n'avais pas bien saisi ton objectif (lu trop vite).
Dans ce cadre, le plus simple est de faire une recherche de proximité entre le référentiel et les adresses "réelles".
pas la peine de matcher 100%, il peut suffire de faire matcher X% des mots de l'adresse avec Y% de différence sur les mots (pour les fautes d'orthographe).
En faisant varier X et Y, tu devrais pouvoir identifier une grosse proportion de la base et quelques règles spécifiques permettront de traiter le reste.
Ou prendre les Z meilleurs résultats qui ont un X suffisant

Pour tes exemples:
Ref: "6 Rue du Général de Gaulle , 55 555 LE VILLAGE"
"6, Rue du Gal de Gaulle , Résidence "Le Fleurus", 4ème gauche , 55555 LE VILLAGE"
"Le Fleurus , Appt 254 , 6 R du GENERAL DE GAULLE , 55 555-LE VILLAGE"

dans les deux cas, tu vas matcher "le village", "55555" (il suffit d'une petite règle pour avoir tous les codes sur le même format) et "Gaulle"
rien qu'avec ces 3 matches, tu vas pouvoir restreindre à quelques adresses possibles
le match correct de "6" et de "général" et éventuellement le match incorrect de "254" réduiront encore le nombre.

Quoiqu'il arrive, il est impossible d'avoir 100% de match dans ce genre de traitements.
Ce genre de traitement ne peut être fait qu'avec un minimum de tatonnements.

[invitecf343e72]

Bonjour,

mon problème n'est pas le "match" lui même on a déjà une appli qui réalise très bien ce "match" avec la précision que l'on souhaite (on ne souhaite pas "matcher" dans tous les coins seulement pour "matcher"). Et donc compte tenu que l'on veut une certain qualité, il y a un résidu non "matché" avec la précision voulue à la fin mais pas forcément non "matchable".

Ce que je veux faire, c'est justement "re traiter" ces adresses non "matchées" pour les rendre "matchables".

Deux pistes :

--> analyse syntaxique (pistes sur laquelle je demande des infos dans ce post)

--> jointure floue : basée sur une longueur de chaine commune aux deux adresses et suffisamment longue et pertinente.

D'ailleurs pour cette dernière partie, je cherche un algorithme rapide d'extraction de la plus longue chaine de caractères communs consécutifs entre deux chaines.
Vous avez des idées ? Des algos ?

Merci et bon we a vous.

[invitecf343e72]

De quel d'elai disposes-tu ? Sous quelle forme se présente ta base ?

Désolé je ne t'avais pas répondu, niveau délais rien de pressant, c'est pour faire un module de traitement supplémentaire, la base est une base de donnée classique, que j'attaque avec un langage de programmation ad-hoc, j'ai la possibilité de faire des requetes SQL, de la programmation basique, programmation de fonction, accès aux regExp de Perl. Tout ce qui est nécessaire pour manipuler données et chaines de caractère donc.

[Dlzlogic]

Bonjour,
J'avais pensé à une toute autre approche. Au lieu de chercher à transformer un chaine illisible en une chaine lisible, il serait peut-être intéressant de chercher auquel de ces éléments connus, cette chaine peut se rattacher.
Le principe intellectuel est simple : si cette adresse existe, son possesseur doit bien avoir un ou deux voisins.

[invitecf343e72]

Bonjour,
J'avais pensé à une toute autre approche. Au lieu de chercher à transformer un chaine illisible en une chaine lisible, il serait peut-être intéressant de chercher auquel de ces éléments connus, cette chaine peut se rattacher.
Le principe intellectuel est simple : si cette adresse existe, son possesseur doit bien avoir un ou deux voisins.

bonjour, merci pour ta participation.

Par contre j'ai un peu de mal à saisir ton idée ? Peux tu développer ?

[Dlzlogic]

Le principe général est le suivant.
Au fur et à mesure de la lecture d'adresses "bien formées", une liste des CP, des villes, des rues est mise à jour.
Pour comprendre un adresse "mal formée" on la compare à ce fichier CP+VILLE+RUES.
Un peu comme un facteur (P&T) qui doit distribuer une lettre, l'adresse est incompréhensible, mais comme il connait toutes les rues de son secteur, il aura vite fait de trouver, contrairement à son remplaçant.

[invite4492c379]

Désolé je ne t'avais pas répondu, niveau délais rien de pressant, c'est pour faire un module de traitement supplémentaire, la base est une base de donnée classique, que j'attaque avec un langage de programmation ad-hoc, j'ai la possibilité de faire des requetes SQL, de la programmation basique, programmation de fonction, accès aux regExp de Perl. Tout ce qui est nécessaire pour manipuler données et chaines de caractère donc.

Ça va dépendre de ton niveau principalement, tu peux trouver une tonne d'articles intéressants sur citeseer, arxiv ou hal par exemple ; google scholar (ou google tout court avec le filtre filetypedf) peut aussi trouver des pistes intéressantes. Si tu tombes sur article payant, tu peux souvent le trouver «gratuitement» sur le site d'un des auteurs (parfois une version préimpression).

Par contre tu restes vague ... quelle est la taille réelle des données que tu vas traiter ? tu as plusieurs dizaine de millions d'adresses fautives ?

[invite4492c379]

Le principe général est le suivant.
Au fur et à mesure de la lecture d'adresses "bien formées", une liste des CP, des villes, des rues est mise à jour.
Pour comprendre un adresse "mal formée" on la compare à ce fichier CP+VILLE+RUES.
Un peu comme un facteur (P&T) qui doit distribuer une lettre, l'adresse est incompréhensible, mais comme il connait toutes les rues de son secteur, il aura vite fait de trouver, contrairement à son remplaçant.

Effectivement ça peut être un voie sympathique à emprunter. Surtout si on dispose d'un jeu de données correctes, apprentissage non supervisé d'un réseau de neurone. Mais bon il y a pas mal de boulot derrière.

[invitecf343e72]

Bonsoir, je reviens ici, mon projet est toujours en cours (en mode "fond de tache" ).

Je suis un peu plus avancé, j'ai un algo qui me permet de bien coder la commune (99.95%) et des "faux positifs" (erreurs) de l'ordre de 5p10000 tout à fait acceptables.
Je me suis effectivement un peu inspiré de l'esprit de la proposition de Dlzlogic (notamment pour mettre de côté automatiquement l'étranger et l'élaboration d'un fichier de codes postaux avec des rétroactions "données"-->algo-->"données" ) et ça se révèle assez efficace.
Je vais me replonger prochainement dans le "dur" des adresses à présent.


Je vais essayer de reproduire le même schéma.
J'ai à présent des fonctions de comparaisons "tolérantes" aux abréviations, des motifs d'expression régulière de nettoyage avec prise en compte des ordinaux ("Bat 1 3ème Etage 2ème porte --> "Bat 1 Etage 3 Porte 2" , des boucles de rétroaction de correction des fautes mineures).

Je vais à présent devoir créer des algorithmes pour rendre compréhensibles les adresses "complexes"

ex:
"15 RUE DES PLANTES / RESIDENCE LES LILAS "
"19 RUE DES PLANTES / 2 RESIDENCE DES CHARMES"
"RESIDENCE DES CHARMES / BATIMENT 2 / RUE DES PLANTES"
"RESIDENCE LES LILAS"
"19 RUE DES PLANTES RESIDENCE DES CHARMES No 1"

Il va me falloir un algo qui m'indique que les observations 1 et 4 sont les mêmes, les 2 et 3 sont les mêmes et la 5 une autre différente des observations 1,2,3,4.

Je suis preneur des bonnes (ou moins bonnes) idées comme toujours.

[invitecf343e72]

"apprentissage non supervisé d'un réseau de neurone."

@photon, tu aurais des références où je pourrais partir à la pèche de ce qui peut m'intéresser ?

[invitecf343e72]

Bonjour,

toujours à la recherches de solutions.

Des solutions pourraient partiellement se trouver du côté de l'analyse syntaxo-morphologique par chaine de Markov cachées.
Si vous avez des références intéressantes à ce sujet ?

Merci.