Algorithme de clé de correspondance d'adresse

https://stackoverflow.com/questions/824588

05-07-2019
|

Question

J'ai une liste d'adresses dans deux tableaux distincts légèrement décalés que je dois pouvoir faire correspondre. Par exemple, la même adresse peut être entrée de plusieurs manières:

110 Test St
110 Test St.
110 rue test

Bien que simple, vous pouvez imaginer la situation dans des scénarios plus complexes. J'essaie de développer un algorithme simple capable de faire correspondre les adresses ci-dessus à une clé.

Par exemple. la clé peut être " 11TEST " - deux premiers de 110, deux premiers de Test et deux premiers de variante de rue. Une clé de correspondance complète comprendrait également les cinq premiers codes postaux. Ainsi, dans l'exemple ci-dessus, la clé complète pourrait ressembler à "11TEST44680".

Je suis à la recherche d’idées pour un algorithme efficace ou de ressources pouvant être prises en compte lors du développement. Toutes les idées peuvent être en pseudo-code ou dans la langue de votre choix.

Nous ne nous intéressons qu'aux adresses américaines. En fait, nous examinons uniquement les adresses de 250 codes postaux de l’Ohio et du Michigan. De plus, nous n’avons accès à aucun logiciel postal, mais nous serions ouverts à toute idée de solution rentable (ce serait essentiellement une utilisation ponctuelle). N'oubliez pas qu'il s'agit d'un premier dépotoir de données provenant d'une source gouvernementale. Les suggestions sur la façon dont les utilisateurs peuvent le nettoyer sont utiles car je construis l'application, mais j'aimerais beaucoup avoir la meilleure initiale possible en pouvant faire correspondre les adresses. le mieux possible.

La solution

Je travaille sur un algorithme similaire au moment où nous parlons, il devrait gérer les adresses au Canada, aux États-Unis, au Mexique et au Royaume-Uni au moment où j'ai terminé. Le problème auquel je suis confronté est qu’ils sont dans notre base de données dans un format texte clair à 3 champs [celui qui pensait que était une bonne idée devrait être filmé à mon humble avis], essayant donc de gérer les routes rurales, les livraisons générales , récepteurs volumineux, plusieurs pays, province ou État ou comté, codes postaux ou codes postaux, les fautes d’orthographe n’est pas une tâche simple ni une tâche difficile.

Les fautes d'orthographe n'étaient pas une mince affaire, surtout dans les pays qui utilisent des noms français: associer Saint, Sainte, Sainte, Sainte, Saints, Saintes, Sts, Stes, Grandes, Grandes, Grandes, Grandes avec ou sans point ou une césure à la plus grande partie du nom ne pose pas de problème de performances - en particulier lorsque St peut signifier rue Saint ou et peut avoir été entré ou non dans le bon contexte (par exemple féminin ou masculin) . Que se passe-t-il si l'adresse a été saisie en grande partie correctement mais que la province ou le code postal est incorrect?

Le algorithme de distance de Levenstein constitue un bon début de recherche. > que j'ai trouvé très utile pour éliminer une grande partie des fautes d'orthographe. Ensuite, il s’agit essentiellement de rechercher des mots-clés et de les comparer à une base de données postale.

Je souhaiterais vraiment collaborer avec tous ceux qui développent actuellement des outils pour le faire. Peut-être pourrions-nous nous aider mutuellement à trouver une solution commune. Je fais déjà partie du chemin et j’ai surmonté tous les problèmes que j’ai mentionnés jusqu’à présent. Il serait très utile de faire appel à une autre personne qui travaillerait sur le même problème pour échanger des idées.

A bientôt - [ben at afsinc point ca]

Autres conseils

Si vous préférez ne pas en développer un et utiliser plutôt un produit standard utilisant de nombreuses technologies mentionnées ici, voir: http://www.melissadata.com/dqt/matchup-api.htm

Avertissement: j'ai joué un rôle dans son développement et je travaille pour l'entreprise.

Au Royaume-Uni, nous utiliserions:

Nom ou numéro de la maison (où le nom comprend un numéro d'appartement pour les immeubles)
Code postal

Vous devriez certainement utiliser le code postal, mais aux États-Unis, je pense que vos codes postaux couvrent des zones très étendues par rapport aux codes postaux du Royaume-Uni. Vous devrez donc utiliser la rue et la ville.

Votre exemple ne ferait pas la différence entre 11 Test Street, 110 - 119 Test Street, etc.

Si votre société a accès à un système de recherche d’adresse, j’examinerai toutes les données afin de les récupérer dans un format cohérent, éventuellement avec des clés d’adresse pouvant être utilisées pour la mise en correspondance.

Si je devais essayer de résoudre ce problème, je convertirais chaque chaîne d'adresse en un arbre utilisant un ordre d'opérations prédéfini.

Par exemple. 110 Test Street Apt 3. Partout en Californie 90210 = &

Obtenir le type d'adresse. Par exemple, les adresses de rue ont différents formats et les adresses de route rurale, ce qui est différent selon les pays.
Etant donné qu'il s'agit d'une adresse postale, obtenez la chaîne qui représente le type de rue et convertissez-la en une énumération (eBoulevard, eRoad, etc.)
S'agissant d'une adresse postale, indiquez le nom de la rue (magasin en minuscule)
Étant donné qu'il s'agit d'une adresse postale, indiquez le numéro de la rue
Étant donné qu'il s'agit d'une adresse postale, recherchez un numéro d'appartement (avant le numéro avec un tiret, après "App.", etc.)
```
   eStreet  //1.an enum of possible address types eg. eStreet, eRuralRoute,...
      |
   eStreet        //2.an enum of street types eg. eStreet, eBlvd, eWay,...
   /   |   \
```
Nom Numéro Appt | | | test 110 3

Par exemple. RR n ° 3 partout en Californie 90210 = >

Obtenir le type d'adresse: route rurale
S'agissant d'une adresse de route rurale, obtenez le numéro de la route
```
   eRuralRoute 
      |
      3
```

Vous devez faire quelque chose de similaire pour les informations d'état et de zip du pays.

Comparez ensuite les arbres résultants.

Cela rend la comparaison très simple, cependant, le code pour générer les arbres est très délicat. Vous voulez tester la merde sur des milliers et des milliers d'adresses. Votre problème est plus simple s’il ne s’agit que des adresses américaines; Les adresses britanniques, comme il a déjà été mentionné, sont très différentes, et les adresses canadiennes peuvent contenir du français (par exemple, Place D'Arms, Rue Laurent, etc.)

S'il est rentable pour votre entreprise d'écrire son propre outil de normalisation d'adresses, nous vous conseillons de commencer par Adresse standard USPS . Autrement, de nombreux fournisseurs proposent des outils côté serveur et des services Web permettant de normaliser, corriger et vérifier les adresses.

Ma société utilise AccuMail Gold , car elle fait beaucoup plus que simplement normaliser & amp; corrigez l'adresse. Lorsque nous avons pris en compte le coût d'une semaine de salaire pour développer un outil en interne, le choix d'acheter un produit standard était évident.

Si vous n'avez pas choisi d'utiliser un système existant, vous pouvez notamment:

Extraire les numéros de la ligne d'adresse
remplacer les mots de la rue courants par des blancs
créer une chaîne de correspondance

c'est-à-dire: "555, rue Canal":

Le numéro de l'extrait donne " 555 " + "Canal Street"
Remplacer les mots de la rue donne " 555 " + "Canal"
La chaîne de correspondance donne "555Canal"

"Canal st 555" donnerait la même chaîne de correspondance.

Par mots de rue, je veux dire des mots et des abréviations pour "rue". dans votre langue, par exemple, "st", "st.", "blv", "ave", "avenue", etc., tous sont supprimés de la chaîne.

En extrayant les nombres et en les séparant de la chaîne, peu importe qu'ils soient premiers ou derniers.

utilisez une identité pour la clé primaire , elle sera toujours unique et facilitera la fusion ultérieure des doublons.

forcer la saisie correcte des données avec l'interface utilisateur. Faites-les entrer chaque composant dans sa propre zone de texte. Le numéro de rue est entré dans sa propre case, le nom de la rue dans sa propre case, la ville dans sa propre case, l’état de la liste de sélection, etc. Cela facilitera la recherche des correspondances

disposer d'un processus en deux étapes "enregistrer"

après la sauvegarde initiale, effectuez une recherche pour rechercher des correspondances et présentez-les avec la liste des correspondances possibles, ainsi que la nouvelle.
après avoir sélectionné le nouveau, sauvegardez-le, s’ils en choisissent un qui utilise cet identifiant

nettoyer les données. Essayez de dépouiller "street", "st", "drive", etc. et stockez-le en tant que StreetType char (1) qui utilise un FK vers une table contenant les abréviations appropriées, afin de pouvoir construire la rue.

se pencher sur SOUNDEX et DIFFERENCE

J'ai travaillé pour de grandes entreprises qui gèrent des listes d'envoi de courrier. Elles n'ont pas essayé de le faire automatiquement. Elles ont utilisé des personnes pour filtrer les nouveautés, parce que c'est si difficile à faire. Planifiez une fonction de fusion afin de pouvoir fusionner manuellement les doublons lorsqu'ils surviennent et transmettez les valeurs à travers les PC.

Vous pouvez regarder dans l'API Google Maps et voir si vous pouvez donner votre adresse et obtenir une correspondance. Je ne suis pas au courant, ce ne sont que des spéculations.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow