Brevet FR2840090A1 — publié le 20031128

CORRECTION ET CONTROLE DES ADRESSES POSTALES La presente invention concerne le domaine de la correction et du controle des adresses postales. Une adresse se definie comme la description, dans la langue vehiculaire d'un pays, exprimee avec des lettres et des chiffres d'un point sur un plan representant une zone sur une carte geographique. Cette description doit decrire sans aucune ambiguite ce point et ce point uniquement. La relation imposee entre ce point et son image sur un plan est en axiomatique de type biunivoque. La description de toutes les composantes d'une adresse se fait au moyen de la langue officielle du pays ou de la langue parlee de sa region (cas des pays trilingues comme la Suisse, ou bilingues comme la Belgique ou le Canada). Le nombre de variantes ecrites pour un meme mot dans un referential linguistique donne est indefini. Le nombre de signes evolue pour un meme terme dans la limite de son acception reconnaissable par une personne pratiquant la langue. L'erreur d'un ou de plusieurs signes n'empache pas pour autant dans un maximum de cas au lecteur dattention moyenne de retrouver la forme usuelle de ce mot. Seule restriction, cette malformation scriberee ne peut etre dans un environnement donne, c'est-a-dire pour une adresse precise, la forme erronee que d'un seul mot. Les deux idees directrices sur lesquelles est basee la logique de reconnaissance-con/role-correction de l'existant vent: (1) ltenvironnement d'un mot deforme a ete identifie et les variables vent de nature et d'une amplitude reconnues experimentalement possibles, et (2) la forme ne peut etre rapprochee que d'une seule forme de l'environnement suscite. En 1966, la preoccupation de lthomme de l'art etait d' augmenter les possibilites d'automatisation des lettres envoyees. Le brevet FR1463663 donne l'exemple d'une enveloppe a lisere codifie pour le triage electromecanique du courrier. Le besoin de codage l'emportait sur celui de correction de l'adresse elle-m8me. La norme experimentale AFNOR E55- 220 de mai 1976 donne des indications sur la qualite de reproduction de l'adresse. Dans le meme esprit, les postiers n'ont pas hesites a coder physiquement par une indication au verve des plis les enveloppes revenant a leur expediteur pour non-distribution, comme dans le brevet US5510608. La posse italienne imagine pour resoudre le probleme de sa mauvaise distribution de courrier de mettre en place un code postal elargi. Le brevet WO0149426 s'etonne des quinze millions d'adresses individuelles que le procede doit couvrir de facon unique et non equivoque. Le brevet WO0174502 innove en couplant le systeme de codage de chacune des lettres par l'adjonction d'un nouveau code client etendu imprime en dessous de l'adresse du destinataire. Arriva ensuite les innovations sur l'adresse postale elle-meme (AFNOR Z69-300, puis AFNOR XP Z10-011). La seule nouveaute est le passage d'une adresse de trots lignes a 18 caracteres, a six lignes de 32 puis de 38 caractbres alphanumeriques afin de permettre aux imprimantes matricielles d'optimiser ['usage de leur ruban encreur. Le tout est resume sur le plan international par la norme ISO 11180 de mars 1993. Recemment, les Etats-Unis s'interesserent aux bases de donnees d'adresses et a la presentation de ces derrieres (WO0175551) ou a leur plate-forma d'acces (comme le brevet WO0108432). La problematique des doublons a ete abordee de facon embryonnaire et rapide dans les brevets US4853882 et US5303149, mais le femme de depart reste que les adresses a rapprocher vent bonnes. L 'usage d'un reseau etendu pour le routage des courriers non distribuables directement est analyse dans le brevet EP0500180, puis repris dans un usage intensif de la base des adresses des demenages americains dans EP0673686. Voyant arriver les systemes d' information de plus en plus complexes necessitant d'assurer la conservation et l'integrite des adresses stockes (AFNOR NF Z42-013), l'homme de l'art essaya de simplifier au maximum l'acces aux donnees adresse soit par la frappe du moins de touche possible sur un clavier (EP0584607), soit encore par la reconnaissance des mots forts de l'environnement d'une adresse donnee (EP1197885). I1 est necessaire de definir l'environnement, les mots connus, les groupes homogenes de lettres ou de chiffres, et les signes auxquels le mot examine est lie. Cette notion de lien fait intervenir a son tour deux notions: (1) le lien logique ou physique tel qu'un numero dans une rue suivi du type de la rue ( avenue, chemin, place) faisant lui-meme appel a un nom (place de la mairie), et (2) le lien semantique, fonction des regles syntaxiques de la langue utilisee pour enoncer ces propositions ou decrire ces adresses: dans rue grande Chaussee, grande est un qualificatif qui ouvre une possibilite, celle d'un mot qualifie par grande, ici Chaussee. L' absence de reconnaissance des liens entre les mots est le principal handicap des progiciels universellement utilises. Ils decoupent l'adresse soumise en segments sans tenir compte des liens eventuels entre les groupes de caracteres reperer. Tous les systemes etudies tronconnent l'adresse en supprimant simplement les caracteres blancs entre les groupes de caracteres. Ces morceaux d'adresse ne peuvent plus etre recolles ni 4 2840090 utilises. Toute possibilite d'identifier un element ainsi denature a un element du referential est devenu impossible. Les rapprochements evidents a l'il nu vent rendus impossibles. Le tronconnage traditionnel d'une adresse correcte n'est pas une methode valable. Le resultat obtenu donne des adresses denaturees. Des adresses incorrectes sans difficulte majeure de correction vent laissees en l'etat. La recherche des mots auxquels chaque mot de l'adresse soumise peut etre lie semantiquement est delicate. Wile doit etre bornee afin d'eviter de somber dans le meme excbs genere par la non-reconnaissance de liens. La denaturation de l'adresse impose l'impossibilite d'une future validation-correction. Dans l'exemple cite ci-dessus, le mot grande peut egalement etre lie a rue. Si cette option etait retenue dans l'analyse initiale mot a mot, le mot suivant Chaussee pouvant etre reconnu comme un type de voie, se trouve alors isole, deplace. I1 se retrouve au mieux en parasite ou sous une forme incorrecte, moindre mal d'une correction mal realisee. Dans le cas de notre invention, l' innovation technique repose sur le fait que si dans l'adresse a corriger un element est lie a un ou plusieurs mots reconnus identiques ou egaux a leur forme dans un referential donne, le mot non reconnu doit etre egal au mot lie du referential. Les conditions discriminantes de la solution presentee dans ce brevet vent l'exhaustivite des referentiels usites et le principe de lever de douses. L'axiome se change en sophisme si le referential n'est pas exhaustif. La necessite de routines de comparaison visant a eliminer les consequences d'une lacune imprevue dans le referential devient indispensable. Dans le cas ou un meme environnement est commun a plusieurs moss, au lieu d'un rejet pur et simple pour impossibilite de decision securisee, un second niveau de routines d'analyse permet de privilegier une solution avec un risque nul de substitution. L' innovation du procede est constitue par tout cet ensemble de tables, thesaurus, routines avec la codification des fonctions des mots d'une langue donnee pour decrire une adresse. Les adresses peuvent contenir des mots differents sans liens semantiques, ni logiques, resultat le plus souvent de l' evolution des dialectes et des langues vernaculaires. Un recueil d'expressions de cette nature est construit par programme en fin d' elaboration pour ameliorer la securisation des decisions pour des cas sans autre indice. Le progiciel controleur-correcteur automatique doit parler parfaitement la langue utilisee pour decrire les adresses locales et etre capable. Dans l 'expression qui lui est soumise pour n'importe queue adresse, il doit tout d'abord reconnatre sans aucune ambiguite cette adresse, et en-quite, le cas echeant substituer a l'adresse soumise sa forme parfaite suivants les conventions locales. Cette forme va se trouver unique de ce fait. Dans cette traduction d'un type particulier, le correcteur doit matriser la syntaxe et le vocabulaire de cette langue d'un type special. Tous les mots de ce lexique n'ont pas le meme poids, le meme role, la meme frequence. Un referential exhaustif comprend les mots commune a une division physique sur une carte dont la dimension va en decroissant: region, departement, code postal, localite, lieu dit, voie, ensemble immobilier, batiment. Chaque adresse doit pouvoir etre reconnue sans ambiguite comme faisant partie d'un sur-ensemble: l'appartement dans un etage, l'etage d'un escalier, l'escalier dans un immeuble, l'immeuble dans une residence, la residence ouvrant sur un numero d'une voie, etc. Le lexique est la liste des mots utilises. Il comprends les fetes de rubriques ou types et les mots courants designant les types accompagnes de leurs differentes fonctions logiques dans une adresse. L'ensemble des fonctions du progiciel correcteur-controleur peut btre resume comme la recherche d' identification d'une adresse a corriger a un element du referential et un seul. La reconnaissance globale de l'adresse est la somme des reconnaissances de chaque element. Chaque combinaison d'elements de 1' adresse a corriger doit avoir une correspondence avec un element du referential et un seulement. La recherche d'egalite 1/1 entre adresse a corriger et referential est quasi impossible. Par contre, s i les comparai sons se font entre groupe de mot s de l'adresse a corriger et ceux des re'fe'rentiels ayant les memes fonctions, elles peuvent aboutir dans un nombre significatif de cast La notion de groupes de mots lies logiquement est fondamentale dans la recherche de la forme correcte dun mot. Si des mots vent reconnus dans un referential exhaustif lies de facon biunivoque a un mot (groupe de lettres, de signes, de nombres ou de caracteres), la reconnaissance dans l' adresse a controler de ces mots implique ltegalite entre le mot anquel les mots reconnus vent lies dans le referential et le ou les element(s) non reconnu(s) de l' adresse a corriger. Pour se premunir contre une identification forcee liee a un ensemble de circonstances rassemblees du fait du nombre quasi indefini de combinaisons possibles entre mots d'un vocabulaire riche de millions d' elements, l' elimination des solutions impossibles sera le resultat de l'analyse des lettres ou nombres commune et des nombres ou lettres differents entre probleme et solution supposee. Les deux idees directrices de l' invention presentee vent venues du fait que l'acception d'une proposition dans une langue depend non seulement des liens physiques entre les composantes de cette proposition, mais aussi des liens semantiques. of en anglais relic logiquement deux mots de fac,on tres forte. Les liens semantiques peuvent relier de facon moins exclusive deux mots apparemment independents. Seule exception, les possibilites de liaisons semantiques ouvertes par la syntaxe de la langue utilisee. Par exemple: Monsieur entralne la presomption d'une definition de la personne comme Monsieur le Prince sans pour autant refuser la possibilite d'une absence de lien comme dans rue Monsieur. Les procedes classiques utilises faute de mieux n'ont pas les moyens d'eviter ces non-reconnaissance d'anomalies, non-corrections, ou corrections a tort visibles a l'il nut Notez que par definition, les comparaisons automatiques vent incompletes ou non-abouties. L'adresse soumise est reconnue et/ou corrigee si les liens semantiques entre ses composantes ne vent pas ignores par le systeme informatique. Generalement, il nta aucun moyen de les reconnaltre, done d'eviter le tronc,onnage mutilant l'adresse de fac,on irreparable. L' identification des elements d'une adresse a controler inclut la detection des mots auxquels chaque element peut etre lie par l'emploi d'une logique developpee autour de la semantique. Est venue confirmer le besoin imperatif de reconnaissance de tous les liens non-explicites entre les mots composant une adresse la presence de disjonctions frequentes entre elements d'une adresse passee dans un progiciel de correction qui la denaturent, genent ou empechent sa distribution, provoquent des enregistrements parasites, doublons et multiplons non detectes. L'universalite d'une demarche de correction controle d'adresses valable pour tous les pays decoule d'une caracteristique commune: l' existence de types commune a toutes les adresses qui ont leur equivalence a l'identique dans tous les pays ou ces types simples ou composites vent seulement exprimes dans la langue ou meme le dialecte local. Les expressions qui qualifient ces types correspondent a un ensemble find d' arrangements de groupes composant les differentes structures homogenes de fonctions pour ces ensembles qualifiant chacun de ces types. Un mot (groupe de lettres et de chiffres comportant une variante par rapport a la forme correcte sous laquelle il a ete enregistre dans le referential suppose sans faute) ne peut 8tre rectifie ou corrige senl. Il doit etre considere dans son environnement reduit propre a la zone a laquelle l'adresse examinee appartient. La recherche se fait par zone geographique (localite, groupe de localites, code postal) et par toute forme supposee corrigee d'un element ou groupe d'elements. Wile doit etre compatible avec l'environnement reconstruit dans une etape precedente, ou au moins non-infirme par une etape suivante. La recherche se fait a partir du sur-ensemble le plus etendu. Wile est iterative, allant du plus complexe au plus simple (l'adresse individuelle) , exclusion faite du ou des residents a ce niveau. Les elements d'une correspondence exhaustive entre le niveau le plus fin de l'adresse, ctest-a-dire le domicile appartement ou maison individuelle et le ou les residents n' existent pas. La recherche d'egalite entre adresses individuelles (doublons) ne se fera qu'apres avoir reconstitue l'egalite de toutes les composantes de l'adresse physique. s COMPLEXITE DE LA STRUCTURE D'UNE ADRESSE Dans une adresse' il faut qutil y ait une commune (souvent le bureau distributeur postal) avec son code postal unique ou un lieu-dit, mais pas les deux; s'il y a mention d'une bote postale' il n'y a pas de mention de rue, mais un code postal CEDEX specifique; un autochtone donne n'habite que dans une seule rue d'une commune donnee. Cette enigme logique illustre un probleme fondamental de l'adresse, le probleme de satisfaisabilite, ou probleme SAT r qui est un probleme de nature combinatoire. L'expression formalisee d'un tel probleme est parfois de taille considerable et a necessite la recherche d'un algorithme efficace pour la resoudre. Par efficacite, on entend la complexite de resolution' soit le temps maximal necessaire a la resolution par un algorithme de tout probleme du meme type. Le probleme reste de distinguer les problemes traitables r dont l'algorithme de resolution est de complexite polynomiale r de ceux intraitables r pour lesquels on dispose seulement dalgorithmes de complexite exponentielle. Exprimons le probleme SAT de ladresse sous une forme plus mathematique. Chaque fonction elementaire de l'adresse est representee par une lettre: c' la commune; p, le code postal; l, le lieu dit; b' la bote postale, r, la rue; a r l'autochtone. Chacune correspond a une variable logique qui prend deux valeurs: V (vrai) loreque l' option est retenue ou F (faux) quand l' option est rejetee. La premiere contrainte (il faut qu'il y est un code postal a une commune donnee) est satisfaite lorsque c ou p vent vrais, mais pas c ou p a la foist Cette distinction n'est pas contenue dans le . Ainsi, la proposition ' - soit la commune a un code postal, soit elle n'en a pas - doit etre satisfaite. On ecrit symboliquement clauses, cVp et /cV/p, qui doivent etre satisfaites. Ainsi, chaque terme d'une clause est une variable logique ou sa negation. Les trots autres contraintes de notre exemple s'ecrivent de la meme facon sous la forme de clauses. Au total, on obtient sept clauses: cvp, 7cv 7p, cvl, 7cv 71, bV 7rv 7p, avr et rvc, av k et 7rv 7c. Or pour resoudre cette formule SAT de six variables, on enumere au maximum 26, soit 64 combinaisons. L'algorithme le plus efficace pour resoudre ce probleme SAT est fonde sur une procedure cite de Davis, Putman et Loveland, du nom des mathematicians qui l'ont elaboree en 1962. Wile consiste en une sorte de cheminement, par successions d'essais et de corrections d'erreurs, que l'on represente sous la forme d'un arbre de recherche qui croft a mesure que lton resout la formule SAT. Dans tel arbre chaque nud represente une variable et chaque branche le choix d'une valeur pour la variable associee au nud d'ou elle est issue. L'algorithme choisit une variable dans la premiere clause de notre probleme, par exemple c et lui attribue une valeur logique afin de satisfaire la clause, ici vrai. Ensuite, pendant une phase cite de propagation, l'algorithme analyse les consequences logiques du choix effectue: les clauses ou apparalt cette variable vent eliminees, car satisfaites; enfin, celles ou figure la negation de la variable vent reduites aux autres variables qui restent seules en lice pour satisfaire la clause. L'algorithme repete la meme operation sur la nouvelle formule SAT. Lorsque l'algorithme aboutit a deux clauses unitaires contradictoires, par exemple c et 7c, il , dans l'arbre au nud precedent et modifie la valeur de la derriere variable pour explorer une nouvelle branche. Selon que la formule SAT est satisfaisante ou non, une solution est atteinte ou toutes les branches se terminent par une contradiction. Bien que rudimentaire, l'algorithme de Davis, Putnam et Loveland est le meilleur procede connu pour resoudre les formules SAT appliquees a la qualite de l'adresse postale. Il est la base d'algorithmes plus elabores qui util i sent de s heuri stique s pour guider le parcours dans l'arbre de recherche. Ces heuristiques choisissent a chaque nxud de l'arbre une variable, de sorte que l'algorithme soit s'oriente le plus rapidement vers une solution, soit detecte des que possible qutil n'y a pas de solution (adresse refugee). Les heuristiques influent notamment sur le temps de resolution d'une formule SAT. Par exemple, une des heuristiques peut etre de recuperer, d'une part, qu'une variable b est repetee souvent dans les clauses et, d'autre part, que cette variable est plus frequente sous une forme positive (b) que negative ( 7b): l'algorithme lui attribuera preferentiel lement la valeur Vrai afin daugmenter les chances de trouver une solution. Quand une formule SAT est facile a resoudre, l'algorithme a le choix quant a la valeur qu'il attribue aux variables. Le franchissement du seuil de satisfaisabilite de notre formule SAT suite a l'ajout d'un nombre de clauses tres petit devant le nombre de variables s'accompagne de l' apparition brutale de nombreuses variables contraintes, ou gelees, c'est-a-dire qui ont toujours les memes valeurs queues que soient les solutions. En effet, lorsque l'algorithme explore l'arbre des combinaisons, il affecte une valeur a une variable. Quand celle-ci n'est pas gelee, il trouvera vraisemblablement une solution. En revanche, lorsque cette variable est gelee (et que l'algorithme lui attribue la mauvaise valeur), l'algorithme perd beaucoup de temps a attribuer des valeurs aux variables suivantes sans obtenir de reponse: il lui faut remonter jusqu'a la variable gelee et lui attribuer l'autre valeur. L'algorithme utilise dans cette invention est nomme cnfs. Il utilise une heuristique qui cherche dans la formule SAT a resoudre les variables gelees, a qui l'on peut attribuer rapidement une valeur Vrai ou Faux. Cette heuristique determine de queue fac,on une variable est contrainte. Prenons un exemple avec une formule SAT dont la premiere clause est cdl. Quand la variable a pour valeur Faux, elle contraint la variable c a etre vraie afin que la clause soit satisfaite. Lorsque la variable l apparalt une seule fois dans la formule SAT, la variable c est peu contrainte. En revanche, quand la variable 1 est frequente dans la formule et, de surcrolt, sous sa forme negative 71 (il est probable que sa valeur sera Faux), elle contraindra la variable c a etre vraie. L' heuristique examine de la meme fac,on toutes les variables et, au final, identifie les variables le plus vraisemblablement contraintes, done gelees, et queue valeur leur donner. Un exemple eclatant du benefice tire de cnfs pour le probleme SAT-adresse est le concept de variables gelees grace auquel on a pu reduire considerablement le seuil d'insatisfaisabilite de notre approche sur l'adresse postale. ETAPE DE LA MISE EN UVRE La demarche suivie a consiste a creer les instruments de celle-ci avant de la developper. Tout d'abord, il est necessaire de proceder a S la compilation des mots groupes par fonctions logiques. Certains moss, multifonctions tent grammaticales que logiques, imposent des iterations systematiques dont les traces doivent etre conservees jusqu'a la table de decision finale. Cette etape est executee pour un ensemble langue/pays sur trots niveaux: a) Les types À les voies avec environnements possibles: rue, grande rue, nieme rue, nieme avenue, allee, impasse, chemin, ancienne route, voJe communale, route departementale, sentier, cami, vie, carraire, straete, etc. À les ensembles de groupes d'immoubles: residence, domaine, groupe, lotissement, village, HLM, ILM; familistere, ensemble, etc. À les domiciles de divers niveaux: maison, chalet, villa, immeuble, bfitiment, tour... cour, cage, escalier, etage, couloir... appartement, studio, bureau, loft, duplex À les elements divers d'adresse (divisions et elements topologiques); À les personnel physiques (titre et civilites); À les activites. b) Les mots courants specifiques I1 est compose des categories de mots courants specifiques tels que: À Prenoms; À Titres de personnel morales et/ou physiques; À Mots specifiques aux intitules d'adresse militaire; À Qualificatifs par groupe de fonction; À Numeriques cardinaux et ordinaux avec correspondences litterale/numerique; À Mots liens avec leurs categories d'environnements; À Designant d'ensemble immobilier; À Professions et fonctions; À Activites et elements d'activite. c) Les expressions courantes Il est compose de groupes de mots classiquement lies dans les adresses, utilises pour une premiere reconnaissance rapide, ainsi que des mots dont les liens semantiques ont disparus avec levolution des dialectes. Ceux des designants dit classiques de personne, d'evenement, de concept, de groupes humains, etc. Enfin, il est necessaire de proceder a une recherche d' identification par la demarche suivante: l)Balayage en recherche de structures par la consultation des tables pour reconnaltre les liens logiques et semantiques entre les mots engendrant les groupes possibles de mots pour les presenter ensuite aux referentiels; 2)Hypotheses de decoupe en volets logiques pour le code postal, la localite, le principal de voie, le secondaire de voie, les differents niveaux de domicile, les majeurs de domicile, les qualifiants personnels, les intitules, les parasites supposes; 3)Recherche de criteres majeurs sur les codes postaux; 4) Recherche sur les departements, les etats (equivalence) et les localites; )Recherche sur les elements d'adresses professionnelles; 6)Appel referential voies, localite supposee; 7)Premier essai d' identification du segment suppose voJe en mono-mot ou multi-mots avec usage de routines d'erreurs sur voles logique disjoint, mot disjoint, mot fusionne, accbs par masque, accbs par segment, non-decision; 8)Essai d'identification du segment suppose secondaire de voJe a l'identique de la routine precedente; 9) Analyse des elements de domicile; )Analyses des majeurs de domicile selon les ragles d'environnement; ll)Analyses des elements personnels; 12) Analyses des intitules avec reperage du cas des professionnels, des multidestinataires, des parasites intitules; 13)Tous les mots sont-ils identifies ? Dans ['affirmative, restructuration suivant l' option choisie (sortie normalisee ou selon une convention d'abreviation prealablement definie). Sinon, appel au traitement des parasites non reconnus par usage des clef-adresse, avec rejet final. 14)L'appel repetes aux routines decrite en 8) lors d'une absence de correspondence trouvee ou un douse sur plusieurs choix possibles impose un rejet sur echec d/identification. LES ETAPES D'UNE ACTION QUALITE La justification d'une meilleure qualite dadresse est financibre, tent pour les proprietaires et gestionnaires de fichiers que pour les services postaux. Le test francais de La Poste montre qu'une remise sur les affranchissements maximum de l'ordre de 3% pour coux qui satisfont a toutes les conditions ntest pas incitative: il faut les comparer aux 47% de remise accordee par 1'USPS. Cette amelioration de la qualite represente par ailleurs un investissement initial pour les gestionnaires de fichier et un cout supplementaire pour son entretien, qui est du meme ordre que cette remise minime. L'amelioration vraisemblable du service aux clients grand public n'est pas quantifiee et ne peut done etre prise en compte au premier niveau. La qualite d'une adresse est-ce l'identite de chacune a sa forme ideale ou est-elle definir par rapport a l'interet que represente cette qualite pour (1) une distribution postale assuree par des interpretes humains, les facteurs, ou (2) pour le respect des contraintes dues a l'automatisation integree des tris postaux ? De plus, la mesure peut s'appliquer a toute la base ou a un echantillon representatif de celle-ci. Seule l' etude soignee des retours postaux fournit un echantillon sur des trots problemes oberant la qualite d'un fichier: (1) adresses mal redigees cause d' incidents a la distribution, (2) doublons parasites, ou (3) adresses perimees sources de la perte de clients, debiteurs ou autres enjeux. Les retours postaux baptises NPAI (n'habite pas a l'adresse indiquee) doivent etre tries par causes declarees, compares a la bonne forme de chaque adresse, avec l' evaluation de leurs consequences et les mesures possibles pour les reduire. Des cas vent preleves, disseques, remontes a l'origine dans la chane de traitement des adresses et compares a la forme correcte de chaque adresse examinee. Les doublons non detectes issus de NPAI mettent en evidence d'autres depenses inutiles liees aux logiciels de traitement d'adresse ou aux logiciels de detection des doubles ou aux procedures de saisie ou autre processus operationnels. L'analyse mettra en evidence des zones geographiques sensibles de la base de donnees consideree, des modes de saisie ou de controle deficients ou encore, des parametres susceptibles d'influer sur la qualite de l'adresse. La mise a j our de faiblesses tolerees en l' absence tent de solutions que de mesure de leurs consequences risque de provoquer des reactions qu'il faudra prevenir dans les services operationnels habitues a considerer comme inevitables les lacunes des systemes classiques de restructuration d'adresses, ainsi que celles des services postaux peu enclins a se voir opposer les preuves de leurs negligences. Bien que l'objectif initial soit de corriger sans ambiguite un maximum d'adresses c'est-a-dire avec un nombre de rejets limite aux adresses nondistribuables, ce nombre reduit de rejets inevitables doit avoir ete prevu ainsi que leur recyclage par traitement manuel. Certains doubles avec ambiguite sur le patronyme en font partie. Les cle-adresses vent extraites en fin de correction de la base de donnees et la table des cle adresses corrigees est creee, sans laquelle il ne serait pas possible de communiquer avec les individus a travers leur seule cle-adresse. Autour des cle-adresses vent centralisees pour chaque adresse les informations de gestion qui accompagnent l'adresse dans chacun des fichiers qui la contiennent. Tout dabord le profil du titulaire de l'adresse, dautant plus complet qu'un plus grand nombre de fichiers sources aura ete fusionne. Chaque cle-adresse affiche toutes les bases dans lesquelles chaque adresse est geree. Toutes ses utilisations declenchees par son profil synthetique peuvent etre suivies et permettre de mesurer les reactions individuelles a ces stimuli emis automatiquement. A partie de la gestion centralisee multi fichiers et de ses utilisations comme vecteur de messages, une matrice, table de decision multidimentionnelle doit etre creee pour gerer l'utilisation de l'adresse. Parmi les contraintes programmables figurent le respect de la confidentialite individuelle ainsi que des regles de partages d' information entre gestionnaires de fichiers. Toute adresse entree est ramenee a sa forme unique, independante du mode d'acces, sequential ou aleatoire. Que le traitement se fasse en differe (batch) ou en-ligne, par lignes dediees ou par reseau d'acces mondial TCP/IP de type Internet, la correction est independante de l'acces aux bases de donnees. Toute adresse soumise entralne la creation de sa cle-adresse suivie d'une recherche de simple egalite sur la base des cle-adresses creees lors de l' operation initiale. Cette egalite sans ambiguite indique la presence dans la base de l'adresse soumise, done d'un doublon. Chaque cle-adresse porte une entete ( trailer) indiquant les origines de l'adresse, c'est-a-dire les differentes bases de donnees dans lesquelles l'adresse a ete trouvee, completee automatiquement par chaque nouvelle appartenance detectee. Parallelement, une trace de l'utilisation a chaque lecture de la base peut etre programmee. Wile comporte une selection des adresses repondant a certains criteres en vue de contacts directs, individuals ou foyers. Cette trace repond a une logique differente de la trace comportementale declenchee par egalite de deux cle adresses. L,unicite de l'adresse, done de la cle-adresse qui la cite, evite les tatonnements, balayages successifs de zones a la recherche d'elements commune, avec le flou de leur resultat' bloquant depuis des decennies la gestion securisee d'immenses bases d'adresses. Ces approches successives imposaient auparavant des traitements batch. Il est souvent utilise pour des bases a utilisation discontinue comme les fichiers de prospection, les rapprochements de fichiers pour acquisition de nouveaux clients, ou les enrichissements de profile. Le processus est le meme qu'il s'agisse d'eliminer toutes les adresses presentes simultanement dans plusieurs fichiers primaires (repoussoirs), ou de memoriser les appartenances multiples pour enrichir un profil donne. Quand une base de donnees deja corrigee est utilisee, ses adresses vent entrees au niveau de leur cle adresse. Senles les adresses nouvelles passent en correction, allegeant le traitement. Le rapprochement banalise se fait ensuite par simple recherche d'egalite sur les cle-adresse. Toutes les adresses d'un groupe pays-langue etant compatibles, un nombre indetermine de gestionnaires de bases de donnees peut, dans le cadre legal de chaque pays, regrouper leurs fichiers autour d'une base centrale des cle-adresses et des adresses uniques que represente chacune d'elles. La trace origine indiquant un nombre indefini de bases de donnees primaires representees par exemple par un bit dedie quand l'adresse examinee a ete reconnue, leur appartenir signifie une simple egalite des cle-adresses. Le controle par un operateur central agree par toute s le s parties mais independent de s pouvoirs tent politique que legal paralt necessaire au bon fonction nement du systeme envisage. Aux Etats-Unis, un fichier centralise des changements d'adresses (NCOA) existe depuis plusieurs annees. Il est gratuit et l' information y est conserve trots annees dans un fichier de 140 millions d' entrees. La crainte de faire des demenagements par la seule informatique limite entre 85 et 92% le taux de detection et de transfert de l' information de peremption concernant des adresses vraiment perimees. Le risque de les actualiser a tort suite aux faiblesses de reconnaissance des logiciels de comparaison d'adresse est l' unique frein actuel. Le concept d'unicite de l'adresse corrigee ou des cle-adresses qui les representent permet d'en etendre le domaine a la circulation d' information de changement dadresse. La prevention d'envois vers des adresses perimees, done condamnees a faire retour, devrait etre facilement adoptee a condition que l' application de l' information soit securisee, comme dans le cas des nouvelles adresses. L' unique condition du developpement international des cle-adresses reste que la langue doit disposer d'un alphabet, ce qui exclut les langues a ideogrammes. La survie des services postaux nationaux depend de l'automatisation du traitement des envois, done de la generalisation des codes-barrel aux adresses individuelles. I1 sera interessant de creer une base de cle-adresses pour chaque pays geree en temps reel avec l'automatisation securisee et mutualisee des changements d'adresses. FIGURES 1. Onze intitules differents recus par une meme personne desservie par le m8me bureau de posse. Seule l'adresse encadree est correcte; 2. Le rapprochement de fichiers permet d'obtenir un enrichissement de l'adresse. .. et de dedoublonner le fichier final ainsi enrich); 3. Dix exemples d'adresses a corriger (colonne de gauche): les adresses corrigees vent a droite. Wiles font ressortir l'anarchie structurelle de certaines d'entre elles et la difficulte de reconstituer l'adresse originale propre; -, - '. d'entre elles et la difficulte de reconstituer l'adresse originale propre; 4. Dix autres exemples d'adresses a corriger. L'une d'entre elle a impose a la formule SAT une situation gelee: l'adresse est alors rejetee. A noter un exemple d'erreur frequent dans les progiciels classiques de correction d' adresses: > devient RDC, c' est a-dire rez-dechaussee, a cause de son positionnement dans lienvironnement spatial de la personne donnee; lO 5. Huit exemples de cle-adresses permettant de voir la finesse de concordance de deux adresses lors d'un processus de dedoublonnage apres un passage des deux adresses dans l'algorithme heuristique cnfs a formule 6-SAT; lS 6. Overkills: essai de reconnaissance de la vraisemblance d'adresses afin de supprimer les elements redondants. Dans notre cas 1, l'homonymie ne suffit pas a identifier un doublon; dans le cas 2, le nom de famille identique n'a pas non plus suffit a creer l'unicite des elements compares. REVENDICATIONS 1 - Procede pour la correction automatique d'adresse postale comprenant une succession de mots et de liens pouvant consister en des groupes homogenes de lettres ou de chiffres et, eventuellement, de signes auxquels les mots vent lies, ce procede mettant en oeuvre un systeme informatique comportant des moyens de contr81e et/ou de correc t ion automat ique apses a reconnal t re une adres se erronee, des moyens permettant de corriger l'adresse et de substituer l'adresse corrigee a l'adresse initiale erronee et, le cas echeant, des moyens permettant d' adapter l'adresse initiale a des conventions locales, lesdits moyens de contrdle et/ou de correction comprenant un referential contenant l 'ensemble des mots et des fonctions associees a ces moss, servant a decrire une adresse, ces mots etant commune a une division physique sur une carte dont la dimension va en decroissant (de la region au departement, a la voie, au code postal, a la localite, au lieu-dit, a l 'ensemble immobilier et au batiment), ainsi que des rout ines de comparai son des mot s contenus dans l'adresse avec les mots du referential, caracterise en ce qu'il met en oeuvre un algorithme heuristique de type SAT effectuant un nettoyage selon un processus comprenant la recherche d'une adresse a corriger en comparant les mots de l'adresse avec les mots contenus dans le referential, et en reconnaissant et/ou corrigeant l'adresse si les liens semantiques entre ses composants ne vent pas ignores par le systeme informatique; 2 - Procede selon la revendication 1 caracterise en ce qu'il comprend les etapes suivantes: l'identification des elements de l'adresse a contrGler, par la detection des mots auxquels chaque element peut etre lie par l'emploi d'une logique semantique, - la reconnaissance des elements identifies dans l'adresse et qui se trouvent done dans le referential, grace a une routine de comparaison, etant entendu que chaque element de l'adresse a corriger a une correspondence avec un element du referential et un seul et que si, dans l'adresse, un element est lie a un (ou plusieurs) mot(s) non reconnu(s) identique(s) ou egaux a leur forme dans le referential, le mot non reconnu doit etre egal au mot lie du referential, - la substitution de l'adresse initiale par une adresse utilisant les mots reconnus dans le referential et presentee sous une forme appropriee aux conditions locales; 3 - Procede selon la revendication 2 caracterise en ce que la susdite phase d/identification comprend: - la compilation des mots groupes par fonction logique selon les trots niveaux suivants: À la typologie des lieux (voies - ensemble de groupes d'immsubles, domiciles, elements divers de l'adresse); À les identifiants specifiques (prenoms, titres de personnel morales et/ou physiques, mots specifiques aux intitules d'adresses militaires, qualificatifs par groupe de fonction); À les expressions courantes composees de groupes de mots classiquement lies dans les adresses ainsi que des mots dont les liens semantiques ont disparus avec l' evolution des dialectes. - un balayage en recherche de structures par la consultation de tables pour reconnaltre les liens logiques et semantiques entre les mots qui engendrent des groupes de moLG possibles pour les coparer ensuiLe a ceux du rAfArenLiel; - la ralisaLion d'hypoLhses de dAcoupe en volets logiques pour le code postal, la localitA, le principal de voie, le secondaire de vois, les ditfArents niveaux de domicile, les majeurs de domicile, les qualiticaLits personneIs, les inLiLulAs, les parasites supposAs; - une rechercbe de critAres majeurs sur les codes postaux; - une recherche sur les dApartements, les Atats et les localitAs; - une recherche sur les lAments d'adresses rotessionnelles; 4 - ProcAdA selon l'une des revendications 2 et 1 caractArisA en ce que la susdite phase d'identitication comprend: - un appel rAtArentiel voies, localitA supposde; - un premier esai d'identitication du segment supposA vole en mono-mot ou mulLi-moLs avec usage de routines d'erreurs sur voleL logigue disjoint, mdL disjoint, mot fusionnA, accAs par masque, accAs par segment, non-dAcision; - un essai d'idenLiticaLion du segment supposA secondaire de vole l'identique de ladite coutine; - l'analyse des AlAments de domicile; - les analyses des majeurs de domicile selon lej rAgles d'environnement; - les analyses des Al6ments personnels; - les analyses des intitulAs avec repArage du cas des protessionnels, des multi-destinataires, des parasistes intitulAs; - une recherche pour determiner si tous les mots vent identifies avec, dans ['affirmative, une restructuration suivant loption choisie (sortie normalisee ou selon une convention d'abreviation prealablement definie) et, dans la negative, appel au traitement des parasites non reconnus par usage des clef adresses, avec rejet final; - l'appel repete aux susdites routines d'erreur lors d'une absence de correspondence trouvee ou un douse sur plusieurs choix possibles impose un rejet sur echec d' identification; - Procede selon l'une quelconque des revendi cat ions precedentes caracterise en ce que la logique de la reconnaissance- con/role-correction de l'existant est telle que si l'environnement d'un mot deforme a ete identifie, alors les variables vent de nature et d'une amplitude reconnues experimentalement possibles, et la forme ne peut etre rapprochee que d'une seule et unique forme de l'environnement suscite; 6 - Procede selon l'une quelconque des revendi cat ions precedentes caracteri se en ce que l e referential comprend des mots connus, des groupes homogenes de lettres et de chiffres, et des signes auxquels un mot a examiner sera lie, ce lien etant logique, physique ou semantique; 7 - Procede selon l'une quelconque des 3 0 revendi cat ions precedentes caracterise en ce que la reconnaissance globale de l'adresse est la somme des reconnaissances de chaque element, chaque combinaison d'elements de l'adresse a corriger ayant une correspondence avec un element correspondent du referential et un seulement; 8 - Procede selon l'une quelconque des revendications precedentes caracterise en ce que la reconnaissance dans l'adresse a contrdler de mots reconnus dans le referential lie de fac,on biunivoque a un mot forme d'un groupe de lettres, de signes, de nombres ou de caracteres, implique legalite entre le mot auquel les mots reconnus vent lies dans le referential et le ou les element(s) non reconnu(s) de l'adresse a corriger; 9 - Procede selon l'une quelconque des revendications precedentes caracterise en ce que la recherche d'egalite entre adresses individuelles (doublons) n'est faite qu'apres avoir reconstitue l'egalite de toutes les composantes de l'adresse physique; - Procede selon l'une quelconque des revendications precedentes caracterise en ce que le susdit algorithme heuristique procede par successions d'essais et de corrections d'erreurs generalement representes sous la forme d'un arbre de recherche qui croft a mesure que l'on resout la formule, chaque noeud representant une variable associee au nocud d'ou elle est issue; 11 - Procede selon la revendication 10 caracterise en ce que le susdit algorithme cherche dans la formule n-SAT a resoudre les variables gelees en determinant de queue fa,con une variable est une contrainte; 12 - Procede selon l'une quelconque des revendications precedentes caracterise en ce qu'il comprend l'optimisation du referential par etude des retours postaux et mise en place d'une base de donnees des cle-adresses creed au debut de l'approche heuristique n- SAT et geree dans un fichier national selon les regles