PROCEDE POUR IDENTIFIER UNE STRUCTURE PARMI UNE COLLECTION DE STRUCTURES APPARTENANT A UN REPERTOIRE

L'invention concerne un procédé pour identifier une structure parmi une collection de structures appartenant à un répertoire, ladite structure comportant au moins deux groupes d'atomes, chacun des groupes d'atomes étant associé à un dictionnaire.

Toute structure peut faire l'objet d'une décomposition hiérarchique, jusqu'à un niveau élémentaire qui est désigné dans le présent brevet par le terme « atome » .

Ces composants élémentaires sont regroupés pour former des groupes d'atomes qui constituent un niveau hiérarchique immédiatement supérieur. Ces groupes d'atomes eux-mêmes sont agencés pour former une structure, constituant le niveau hiérarchique supérieur.

Il est possible de construire plusieurs autres niveaux de structures intermédiaires, en fonction de la nature des informations à traiter. L'atome est la plus petite partie indivisible du groupe d'atomes.

Pour des informations de nature textuelle, le niveau élémentaire sera par exemple le caractère alphanumérique constituant dans ce cas le niveau « atome » . Ces « atomes » sont agencés pour former des groupes d'atomes. Un groupe d'atomes peut être, dans cet exemple :

- un mot ;

- ou une syllabe ; ou un phonème.

Ces groupes d'atomes sont regroupés pour former, au niveau supérieur, respectivement dans cet exemple: une adresse ou un nom de voie ou un chunk (tronçon de phrase) ; - un mot ;

- une syllabe.

En fonction de l'application et du degré de granularité, le traitement mettra en œuvre au moins trois niveaux, et souvent un nombre de niveau supérieur à trois. Lorsque le nombre de niveau est de trois, la notion de « groupe d'atomes » correspond à la notion de « groupe intermédiaire » .

Le groupe d'atome est lié à un dictionnaire.

Le groupe intermédiaire est lié, lorsqu'il est différent du groupe d'atome, à un répertoire.

Une structure composée de plusieurs groupes intermédiaires fait référence à la combinaison des répertoires respectifs.

Lorsque le nombre de niveaux est supérieur à trois, le « groupe intermédiaire » peut correspondre au niveau « groupe d'atomes ». Il peut aussi correspondre à un niveau compris entre le niveau « groupe d'atomes » et le niveau « atome » , ou encore à un niveau compris entre le niveau « structure » et le niveau « groupe d'atomes ».

Bien entendu, l'invention ne se limite pas au traitement d'informations textuelles, et les atomes ne sont pas forcément des caractères alphanumériques.

On appellera ci-après « structure textuelle» un ensemble composé de plusieurs groupes d'atomes, chaque groupe d'atomes formant une chaîne de caractères, ces derniers pouvant être des lettres, des chiffres ou des symboles appartenant à un alphabet défini.

Les groupes d'atomes sont également appelés « fingerprints » .

On appellera « dictionnaire » un ensemble de groupes d'atomes prédéterminés. On appellera « répertoire » un ensemble de structures prédéterminées .

Le procédé selon l'invention trouve notamment une application dans l'identification d'une adresse géographique parmi une pluralité d'adresses géographiques possibles qui appartiennent à un répertoire.

Dans le cadre de cette application, on peut assimiler l'adresse géographique à une structure.

Les éléments composant l'adresse géographique, comme le nom de la voie ou le type de voie par exemple, peuvent être assimilés auxdits groupes d'atomes.

Le répertoire peut être assimilé à un ensemble (ou une collection) de structures prédéfinies. Par exemple, la liste des adresses d'une ville donnée correspond à une collection de structures qui sont connues et enregistrées .

Quant aux dictionnaires associés aux groupes d'atomes, ils peuvent correspondre à un groupe de types de voies possibles, ou bien à tous les noms de voies dans une ville donnée, ou bien encore à tous les numéros de 1 à 200 par exemple.

Pour identifier une adresse géographique, il est nécessaire de renseigner des champs par une chaîne de caractères constituant un groupe d'atomes dont la séquence est potentiellement erronée, que l'on appellera -φar la suite « groupe d'atomes renseigné », chacun des champs étant associé à un dictionnaire, et lesdits caractères pouvant être des chiffres, des lettres ou des symboles.

Les adresses géographiques étant généralement associées à une personne physique ou morale, l'invention peut également aider à identifier ladite personne à partir de renseignements concernant son adresse.

Aussi, l'invention vise notamment à être mise en œuvre par les entreprises de renseignements téléphoniques pour rechercher des coordonnées postales ou téléphoniques d'une personne.

Les conditions d'échanges entre les clients qui appellent l'entreprise de renseignements et les opérateurs devant répondre au client sont à l'origine de perte de temps et d'erreurs dans la recherche.

En effet, le client peut commettre des erreurs dans l'épellation du nom de la personne recherchée, ou dans l'adresse de celle-ci. Parallèlement, l'opérateur peut commettre des erreurs de saisie ou mal comprendre la requête du client.

La méthode selon l'invention permet de retrouver plus rapidement l'information recherchée par un client, malgré les erreurs de saisie involontaires de l'opérateur, ou les

informations incomplètes ou approximatives fournies par le client.

Il existe actuellement des méthodes, mises en œuvre par des moteurs de recherche, qui permettent une recherche de structures parmi une pluralité de structures.

De manière spécifique, la structure correspondant à l'adresse géographique comporte au moins deux groupes d'atomes, par exemple le nom de la voie et le type de la voie.

Ce niveau de traitement correspond à ce qui est qualifié dans notre invention de « groupe d'atome » : un mot est un groupe d'atome, les atomes correspondant aux caractères formant le mot.

Les méthodes connues comportent une étape de renseignement préalable de champs dont le contenu est associé à un groupe d'atomes et au dictionnaire qui lui est associé. Cette étape de renseignement de champs consiste concrètement à entrer dans une case une série de lettres, de chiffres ou de symboles.

Le groupe d'atomes renseigné est alors potentiellement erroné, soit parce qu'une erreur de frappe a pu survenir, soit parce que la personne qui a renseigné les champs a mal compris ce qui lui a été dicté, soit parce que la personne qui a dicté s'est mal exprimée ou s'est trompée.

Une méthode connue de recherche d'un groupe d'atomes parmi une pluralité de groupes d'atomes est notamment décrite notamment dans le document de brevet américain US 6 879 983. Conformément à cette méthode, les groupes d'atomes renseignés sont comparés un à un avec les groupes d'atomes potentiels existants pour supprimer les groupes d'atomes potentiels qui ne comportent pas exactement les mêmes atomes ordonnés de la même manière.

En revanche, les groupes d'atomes similaires à ceux qui ont été renseignés sont retenus.

Ainsi, la recherche de structure se fait suivant une démarche hiérarchique qui donne un résultat uniquement dans le cas où les champs ont été exactement renseignés.

L'erreur potentielle de saisie par un opérateur renseignant des champs n'est donc pas prise en compte dans cette méthode.

L'opérateur ayant fait une erreur de saisie doit vérifier que tous les champs ont été correctement renseignés et doit éventuellement faire l'effort de proposer des variantes dans l'ordonnancement des atomes ou des variantes d'atomes dans les groupes d'atomes pour que la méthode délivre un résultat.

à l'extrême, une autre méthode prend en compte toutes les erreurs de frappe possibles pour un champ renseigné. Cette autre méthode est par exemple décrite dans le document de brevet américain US 7 047 493.

Cette méthode détermine toutes les combinaisons d'atomes possibles pour un groupe d'atomes à partir du champ renseigné .

Par exemple, pour le champ renseigné « physical », la méthode consiste à déterminer toutes les écritures possibles du mot « physical » en tenant compte des sons engendrés par chacun des atomes (ou chacune de lettres) ou chaque association d'atomes suivant la chaîne d'atomes distinguée dans le champ. Les résultats engendrés par une telle méthode sont extrêmement nombreux : « fisikle », « fysicle »... Aussi, la mémoire nécessaire dans un ordinateur pour mettre en œuvre une telle méthode est bien souvent insuffisante, ce qui entraîne des anomalies de fonctionnement. L'identification d'une structure à partir de cette méthode semble ainsi très difficile.

Une autre méthode est encore mise en œuvre dans les téléphones portables pour aider l'utilisateur à écrire des messages à partir des touches du clavier de son téléphone, une touche pouvant correspondre à plusieurs lettres de l'alphabet.

Cette méthode est par exemple décrite dans le document de demande de brevet américain US-2003/0234821. Elle consiste en une méthode pour prédire et proposer un mot à un utilisateur de téléphone portable écrivant un mini message (SMS), à partir de la séquence de lettres tapées par l'utilisateur.

Cette méthode consiste notamment à apparier la séquence de lettres tapées, assimilable à un groupe d'atomes ordonnés,

avec des mots mémorisés dans un dictionnaire, lesdits mots étant assimilables avec des groupes d'atomes potentiels. La méthode utilise notamment un calcul de probabilité de mots possibles auxquels peut correspondre la série de lettres tapées par l'utilisateur en fonction des mots précédemment tapés et des habitudes de cet utilisateur.

Cette méthode ne tient pas compte des éventuelles erreurs de frappe potentielles de l'utilisateur. Aussi, si l'utilisateur tape une touche plutôt qu'une autre, la méthode ne trouvera pas le mot que l'utilisateur souhaitait écrire. Il devra même effacer les lettres qu'il a tapées pour écrire de nouveau et correctement le mot qu ' il cherche .

On connaît également dans l ' état de la technique le brevet US5659771. Ce brevet concerne un correcteur orthographique, pour le traitement de mots dans un texte. Le traitement consiste à proposer, pour chaque mot d'un texte, un ensemble de mots alternatifs (les mots d'un ensemble sont les mots habituellement confondus). Le problème est que chacun des ensembles ne comprend que les confusions connues et observées préalablement. Par ailleurs, il est nécessaire d'enregistrer un dictionnaire très volumineux comprenant tous les ensembles de confusions possibles, même pour les séquences de mots pour lesquelles la probabilité de combinaison de confusions est nulle.

Dans cet ensemble, les mots qui n'ont jamais été enregistrés comme confusion, le traitement est inopérant ; en d'autre terme, le procédé selon cet art antérieur est extrêmement sensible à l'exhaustivité des ensembles de mots confondus : l'omission d'un seul mot de confusion peut rendre totalement inopérant le traitement. Cela incite donc à construire des dictionnaires très volumineux, ce qui conduit à des temps de

traitement long et des volumes de données inutilement lourds .

On connaît également le document « large scale experiments on correction of confused words » proceedings 24th Australian Computer Science Conférence, ISBN 0-7695-0963- 0 ». Ce propose un procédé de traitement similaire à celui décrit dans le brevet US5659771. Le dictionnaire est construit dans ce document à partir des confusions phonétiques ainsi que des confusions dactylographiques et comprend une phase d'entraînement amont.

L'article « Improving the performance the performance of dictionnary-based approches in protein name récognition CREST, auteur Yoshimasa Tsuroka, Jun'ichi Tsujii ; Japan Science and Technologu Agency, publié le 8 octobre 2004 sur le site www.elsevier.com/locate/yjbin » propose un traitement heuristique basé sur l'utilisation d'une fonction de distance entre deux mots. La distance est calculée en fonction d'une formule prenant en compte le coût de rapprochement de deux mots en fonction de la distance cumulée entre des ensembles de caractères.

L'invention concerne une méthode automatique pour le traitement d'informations numériques.

Il convient de rappeler que l'invention ne concerne pas simplement la recherche de mots dans un dictionnaire, comme cela est le cas pour les documents de l'art antérieur.

L'invention concerne en fait des traitements à trois niveaux :

Niveau 1 : Ensemble de « groupes d'atomes » (par exemple structure, ou enregistrement de base de données, une adresse postale complète, ...)

Niveau 2 : Groupe d'atomes (par exemple un mot, un code postal, un identifiant numérique,...)

Niveau 3 : Atomes (par exemple un caractère)

Dans les documents de l'art antérieur, le traitement s'effectue uniquement sur deux niveaux :

Niveau 1 : Mot (i.e. Groupe d'atomes) Niveau 2 : Caractères (i.e. atomes)

Les solutions proposées dans l'art antérieur ne permettent donc pas de réaliser les traitements tels que revendiqués.

Dans l'art antérieur, les traitements s'effectuent exclusivement sur le niveau du mot par rapport à un dictionnaire, et ne prennent pas en compte le contexte structurel dans lequel le mot est employé que pour la sélection ou la levée de doute, après traitement du mot.

Pour éclairer cette différence, prenons un exemple simple qui est le traitement d'une adresse dans une ville. Cette adresse, pour simplifier comprend = le numéro dans la rue le nom de la rue

Le traitement selon l'art antérieur consiste à effectuer deux traitements consécutifs, faisant appel à deux dictionnaires « spécialisés » et distincts : procéder d'abord à la reconnaissance du numéro dans la rue, à partir d'une recherche dans un dictionnaire comprenant tous les numéros de rue possibles pour retenir le candidat le plus probable procéder d'abord à la reconnaissance du nom de la rue, à partir d'une recherche dans un dictionnaire comprenant tous les noms de rue possibles pour retenir le candidat le plus probable concaténer les deux résultats pour déterminer l'adresse corrigée.

La présente invention vise à pallier les inconvénients de l'état de la technique actuelle.

Le traitement selon la présente invention consiste à procéder à un traitement global : procéder à la reconnaissance de l'adresse, à partir d'une recherche dans un répertoire comprenant l'ensemble des adresses existantes (adresses complètes sous la forme de [Numéro dans la rue + nom de la rue]).

Le répertoire constitue en quelque sorte un dictionnaire à plusieurs dimensions — deux dimensions dans l'exemple susvisé), avec une limitation des instances aux seules adresses existantes réellement. La taille de ce répertoire est donc inférieure à la taille des combinaisons des dictionnaires correspondant à chaque groupe d'atomes.

L'avantage technique qui en résulte, outre l'amélioration de la pertinence de la reconnaissance, est la réduction des temps de traitement et de la taille des mémoires nécessaires à l'enregistrement des informations et à leurs traitements.

L'invention vise dans un premier temps une méthode qui permet d'identifier une quantité N de groupes d'atomes potentiels parmi une collection de groupes d'atomes, ladite collection appartenant à un dictionnaire F, ledit dictionnaire comportant une quantité Q de groupes d'atomes, chaque groupe d'atomes étant constitué d'une séquence d'atomes qui sont ordonnés les uns par rapport aux autres et qui appartiennent chacun à un alphabet, ledit alphabet comportant une quantité déterminée P d'atomes de caractères différents.

Concrètement, dans un premier temps et dans le cadre de l'application à la recherche d'adresse dans un répertoire, la méthode selon l'invention vise à identifier, par exemple, un nom de rue, à partir d'un nom de rue saisi et potentiellement erroné, et cela parmi tous les noms de rue de la collection appartenant au dictionnaire « noms de rues » d'une ville donnée.

La méthode selon l'invention comporte, de manière connue en soi, une étape de renseignement d'un champ par un groupe d'atomes potentiellement erronés constituant un groupe d'atomes renseigné, et une étape d'identification de ladite quantité N de groupes d'atomes potentiels pouvant correspondre audit groupe d'atomes renseigné parmi ceux de ladite collection dudit dictionnaire.

Conformément à l'invention, l'étape d'identification consiste en les étapes suivantes :

- appariement dudit groupe d'atomes renseigné avec chacun des Q groupes d'atomes de ladite collection dudit dictionnaire F, pour chaque appariement, calcul d'une probabilité de similitude entre le groupe d'atomes renseigné et le groupe d'atomes du dictionnaire apparié,

- et identification des N groupes d'atomes potentiels dont la probabilité de similitude est la plus forte.

L'étape d'identification ainsi réalisée permet d'associer à plusieurs groupes d'atomes une probabilité de correspondance, ce qui permet à l'invention de fournir un ou plusieurs résultats (soit une quantité N) en fonction de paramètres établis préalablement.

Par exemple, grâce à la méthode selon l'invention, on peut retenir tous les groupes d'atomes du dictionnaire dont la probabilité d ' appariement avec le groupe d'atomes renseigné serait supérieure à un pourcentage donné, ou bien encore les 10 ou 20 groupes d'atomes du dictionnaire dont les probabilités d' appariement avec le groupe d'atomes renseigné seraient les meilleurs.

La méthode selon l'invention permet ainsi de retenir plusieurs résultats possibles, tout en restant limitatif sur la quantité de résultats pour ne pas encombrer la mémoire d'un dispositif qui mettrait en œuvre la méthode.

Dans le cadre d'un premier mode de réalisation de l'invention qui sera décrit et illustré par la suite, le calcul de probabilité de similitude est un produit de calculs de probabilités pour chaque atome du groupe d'atomes qui est renseigné. Les calculs de probabilités prennent en compte, de préférence, la position et le caractère de chaque atome dans la séquence d'atomes du groupe d'atomes qui est renseigné.

II est avantageusement prévu que les calculs de probabilités prennent en compte un facteur de confusion phonétique entre d'une part un atome de position et de caractère définis qui est identifié dans le groupe d'atomes renseigné, et d'autre part un autre atome.

Par exemple, et concrètement, ce mode de réalisation permet de calculer la probabilité de similitude entre un mot et un autre qui tient compte d'une éventuelle erreur de saisie de l'opérateur, ce dernier pouvant avoir saisi par erreur une lettre dont le son est proche de celui de la lettre qu'il aurait dû saisir.

Dans le cadre d'un mode de réalisation parallèle, on prévoit que les calculs de probabilités prennent en compte un facteur de confusion de voisinage entre d'une part deux atomes successifs dans la séquence d'atomes dudit groupe d'atomes renseigné, et d'autre part deux autres atomes.

Ce mode de réalisation tient compte d'une éventuelle erreur de saisie de l'opérateur qui aurait inversé deux lettres dans le mot .

De manière avantageuse, il peut également être prévu que les calculs de probabilités prennent en compte un facteur de confusion visuelle entre d'une part un atome dont la position et le caractère associés sont définis et qui est identifié dans le groupe d'atomes renseigné, et d'autre part un autre atome.

Ce mode de réalisation tient compte d'une éventuelle erreur de saisie de l'opérateur qui aurait confondu deux lettres qui se ressemblent.

Il peut encore être prévu de manière avantageuse que les calculs de probabilités prennent en compte un facteur de confusion géographique sur un clavier de saisie des atomes, entre

- d'une part un atome observé dans la séquence d'atomes du groupe d'atomes, l'atome observé présentant une position et un caractère qui sont définis, l'atome étant associé à une touche dudit clavier de saisie dont la position géographique sur ledit clavier est identifiée,

- et d'autre part un autre atome qui est associé à une touche voisine de la touche identifiée sur ledit clavier qui est associée à l'atome observé.

Ce mode de réalisation tient compte d'une éventuelle erreur de frappe de l'opérateur qui aurait appuyé sur la touche d'à côté de celle sur laquelle il aurait voulu appuyer.

Ainsi définie, la méthode selon l'invention permet de trouver, dans un premier temps, plusieurs résultats possibles à partir d'une séquence de caractères saisis par un opérateur, ladite séquence de caractères saisis définissant un groupe d'atomes renseigné, et chaque résultat

correspondant également à un groupe d'atomes, ces derniers groupes d'atomes appartenant à une collection de groupes d'atomes dans un dictionnaire.

Comme indiqué plus haut, l'objectif de l'invention est avant tout d'identifier une structure parmi une collection de structures, chaque structure étant composée de plusieurs groupes d'atomes.

à cet effet, l'invention concerne également, et dans un second temps, un procédé pour identifier une structure parmi une collection de structures appartenant à un répertoire, ladite structure comportant au moins deux groupes d'atomes, chacun des groupes d'atomes étant associé à un dictionnaire.

En premier lieu, le procédé selon l'invention consiste à identifier, pour chaque groupe d'atomes, une quantité N de groupes d'atomes en appliquant la méthode définie précédemment.

En second lieu, le procédé d'identification de structure selon l'invention met en œuvre les étapes suivantes :

- identification de toutes les combinaisons potentielles de structures à partir des N groupes d'atomes potentiels identifiés,

- identification de la structure la plus pertinente parmi la collection de structures du répertoire en réalisant les étapes suivantes : appariement de chacune des structures potentielles identifiées avec chacune des

structures de la collection de structures du répertoire ,

- pour chaque appariement, calcul d'une probabilité de similitude,

- et identification de la structure la plus pertinente parmi celles de la collection de structures du répertoire, dont la probabilité de similitude avec une structure du répertoire est la plus forte.

Ainsi réalisé, le procédé selon l'invention trouve la structure la plus probable dans un répertoire à partir de groupes d'atomes renseignés qui sont potentiellement erronés en tenant compte des meilleures possibilités de similitude entre les séquences d'atomes renseignées par l'opérateur et celles de dictionnaires associés, sans suivre un modèle hiérarchique qui supprime des possibilités d'erreurs de saisie.

Dans le cadre d'un mode de réalisation avantageux, on prévoit que le calcul de la probabilité de similitude entre une structure du répertoire et la structure composée de groupes d'atomes renseignés tient compte de la probabilité d'identifier un groupe d'atomes donné dans une structure connaissant le groupe d'atomes qui lui est voisin.

Parallèlement, l'invention concerne un système d'identification de structures mettant en œuvre le procédé d'identification décrit précédemment, ainsi qu'un système d'identification de groupes d'atomes mettant en œuvre la méthode d'identification décrite précédemment.

On décrira maintenant un exemple de mise en œuvre de la méthode et du procédé selon l'invention en faisant référence aux dessins annexés, parmi lesquels : la figure 1 représente un réseau bayésien mis en œuvre par la méthode selon l'invention, la figure 2 représente schématiquement un clavier « AZERTY » utilisé par un opérateur pour saisir des groupes d' atomes , la figure 3 représente un réseau bayésien mis en œuvre par le procédé selon l'invention, la figure 4 est un diagramme montrant les échanges de données générés par le procédé d'identification selon l'invention, la figure 5 est un diagramme montrant les échanges de données générés par la méthode d'identification selon l'invention,

- et la figure 6 illustre schématiquement une structure et des dictionnaires associés à chacun des groupes d'atomes composant ladite structure.

Pour mieux comprendre l'invention, la description qui va suivre ne fera référence qu'à un seul exemple d'application : une recherche d'adresse ou de personne à partir de champs remplis par un opérateur.

Il devra toutefois être entendu que cette application n'est pas limitative, et que l'invention peut s'appliquer à l'identification de données ou d'éléments dans d'autres domaines .

Le procédé et la méthode selon l'invention sont appliqués par système informatique qui est utilisé par un opérateur téléphonique de renseignements 1.

L'opérateur téléphonique 1 doit retrouver une adresse ou une personne à partir de données qui lui sont' fournies par un client.

Les données fournies par le client constituent des groupes d'atomes renseignés, et ces groupes d'atomes renseignés sont mémorisés par l'opérateur dans des champs, chaque champ étant associé à un dictionnaire.

Concrètement, l'opérateur 1 saisit dans des cases (correspondant auxdits champs), à l'aide d'un clavier 2, des séquences de caractères pouvant être une suite de lettres et/ou des chiffres et/ou de symboles. Les groupes d'atomes renseignés sont ainsi constitués d'une séquence de caractères.

La figure 6 montre schématiquement la composition d'une structure s d'une adresse.

La structure s comprend des groupes d'atomes fl, f2, f3, f4 et f5.

Chaque groupe d'atomes est associé à un dictionnaire F comportant une collection de groupes d'atomes f _± prédéfinis.

Ainsi, et dans le cadre de l'application à la recherche d'adresse, le groupe d'atomes fl est associé au dictionnaire Fl qui concerne les numéros, et qui comporte tous les numéros de 1 à 999, par exemple.

Aussi, le dictionnaire Fl comporte une quantité Q de groupes d'atomes qui est prédéterminée et qui, dans le cas présent, est égale à 999.

Le groupe d'atomes f2 est associé au dictionnaire F2 qui concerne les types de voies, et qui comporte une quantité définie d'écritures de types de voies telles que « av », « avenue » , « avenue d' », « avenue de » , « rue » , « rue de », « boulevard de »...

Le groupe d'atomes f3 est associé au dictionnaire F3 des noms de voie qui comporte tous les noms de voies d'une ville, par exemple.

Le groupe d'atomes f4 est associé au dictionnaire F4 des codes postaux qui comporte tous les codes postaux répertoriés sur le territoire français, par exemple.

Le groupe d'atomes f5 est associé au dictionnaire F5 des villes qui comporte tous les noms de villes répertoriées en France, par exemple.

Les dictionnaire F2 à F5 comportent respectivement des quantités de groupes d'atomes déterminées.

Dans le cadre de la recherche d'une personne à partir de renseignements concernant son adresse, on identifie quatre étapes qui sont schématisées par la figure 4.

Les quatre étapes sont les suivantes :

Identification 3 du nom de la voie, Identification 4 du type de la voie Identification 5 de la voie Identification 6 de la personne recherchée.

La réalisation de chacune de ces étapes fait appel à un programme bayésien.

L'opérateur 1 renseigne les champs correspondant au nom de la voie et au type de voie. Ces deux étapes de renseignement sont symbolisées par les flèches Rl et R2 sur la figure 4.

La description qui va suivre va maintenant aire référence à l'étape d'identification 3 du nom de la voie.

II convient de noter ici que cette étape d'identification 3 est réalisée de la même manière que l'étape d'identification 4 du type de voie.

L'étape d'identification 3 consiste, conformément à l'invention, à apparier le groupe d'atomes f3 renseigné par l'opérateur et associé au dictionnaire F3 « nom de voies », à chacun des groupes d'atomes f3 appartenant à la collection du dictionnaire F3.

Pour chaque appariement, on calcule alors la probabilité que le nom de voie soit f3 sachant que l'on a f3. Ce calcul de probabilité est noté P(f3/f3) sur la figure 4.

Il en va de même pour le calcul de probabilité du type de voie f2 connaissant le type de voie renseigné f2 : P(f2/f2).

Il va maintenant être fait référence à la figure 1 pour décrire la méthode selon l'invention qui est mise en œuvre pour identifier plusieurs types de voies f3 possibles à partir d'une séquence de caractères saisie par l'opérateur 1 dans le champ associé au dictionnaire F3 « nom de voies » .

De manière générale, la méthode consiste à trouver la distribution de probabilité d' appariement entre le groupe d'atomes observé f et chacun des groupes d'atomes f du dictionnaire F.

Pour définir P(f/f), la demanderesse représente un groupe d'atomes observé f par une séquence de couples : f = <1, âl> <2,a2> <3, !3>...<k,âk>

où aj est le « j-ème » atome du groupe d'atomes observé f.

Prenons l'exemple du nom de rue recherché « Saint Fergus ». L'opérateur s'est trompé dans la saisie du nom de rue et a tapé « sait jergus » .

Dans le cadre de cet exemple, on a :

f = <l , s> <2 , a> <3 , i> <4 , t> <5 , ' ' > <6 , j> <7 , e> <8 , r> <9 , g>

<10 _f u> <ll,s>

On cherche à calculer P (f / f) = P (f / <1, âl> <2,a2> <3, a3>...<k,ak>) , où k = longueur (f).

Pour calculer cette valeur pour tout élément f appartenant au dictionnaire F, il faut considérer que chaque couple (j, aj ) est un couple d'observation d'un groupe d'atomes f du dictionnaire.

La première valeur j est l'indice est l'indice observé d'un indice j de f. Les indices de f vont de 1 à longueur (f). Les longueurs des groupes d'atomes renseignés et des groupes d'atomes du dictionnaire peuvent être différentes. La seconde valeur aj est l'atome observé étant donné l'atome aj de f.

Le calcul de probabilité pour chaque appariement entre le groupe d'atomes observé et un groupe d'atomes parmi ceux du dictionnaire associé est le suivant :

P(f j j aj ij) = P (f) P(J / f) P(J / j) P(aj/ j f) P(âj/aj)

Le réseau bayésien correspondant à ce calcul de probabilité est représenté sur la figure 1.

P(f) est la distribution de probabilité de l'ensemble des groupes d'atomes dans le dictionnaire Fet elle est connue.

P(j / f) est la distribution de l'indice j connaissant le groupe d'atomes f et elle est définie comme suit :

P(j / f) = 1 / longueur (f) si j <= longueur (f) sinon, P(j / f) = 0

^p (j / J) ^est l ^a distribution de l'indice observé 3 étant donné l'indice j. Cette distribution est une distribution dite « normale » (c'est-à-dire Gaussienne) de moyenne j et d'écartement type σ.

P(j / j) = Normal (j, j, σ)

P(aj / j f) est la distribution de probabilité représentant l'obtention de l'atome aj à partir de l'indice j et du groupe d'atomes f.

P(aj / j f ) = 1 si aj est le « j-ème » atome de f, Sinon P(aj / j f) = 0

P (aj / aj ) est la distribution de probabilité d'observer l'atome aj à partir de l'atome aj . Cette distribution est normalement obtenue à partir de statistiques décrivant les fréquences de confusion et / ou de connaissance d'un expert du domaine d'application.

Dans les applications où les atomes sont les symboles d'un clavier 2 d'ordinateur, les confusions sont établies par le

voisinage des touches du clavier 2, la proximité phonétique, la ressemblance et l'orthographe parmi d'autres.

La confusion par voisinage consiste à échanger un atome par un autre. Par exemple, sur le clavier 2 AZERTY représenté sur la figure 2, il est plus probable de confondre la touche « G » avec les touches voisines « F », « R », « T », « Y », « H », « N », « B », et « V », que de confondre la touche « G » avec la touche « L ».

Dans le cas de confusion par voisinage, on prend en compte la distribution de probabilité normale avec un écart type σ et une moyenne égale à la distance entre aj et aj , c'est-à- dire :

P(aj / aj) = Normal (aj, distance (aj,aj), σ) , où distance (aj,aj) est la distance entre les deux atomes aj et aj .

La proximité phonétique consiste à confondre les atomes à cause de leur prononciation proche. Par exemple, certains interlocuteurs pourraient confondre le « e » avec le « o ».

La confusion par ressemblance consiste à confondre deux atomes à cause de leur ressemblance dans leur écriture, ou topologie. Par exemple la lettre « 1 » peut être confondue facilement avec le chiffre « 1 ».

La proximité orthographique est aussi une source de confusion.

A partir de tous les calculs de distribution, autrement dit de probabilité, qui ont été définis ci avant, on peut calculer la probabilité qu'un groupe d'atomes renseignés f corresponde à un groupe d'atomes particulier f parmi ceux d'une liste de groupe d'atomes, ou dictionnaire F.

P (f / f) = P (f / <1, al> <2,a2> <3, a3>...<k,ak>) = P (f / <1, âl> <2,â2> <3, a3>...<k-l,âk-l>) 2 _{jf a} . P(J / f) P(3 =k / j) P(aj/ j f) P(âj = âk /aj)

avec P(f / <1, Il>) = P(f) ∑ _{jf aj} P(j / f) P(3 =1 / j) P(aj/ j f) P(âj = âl /aj)

Maintenant que le calcul de probabilité a été expliqué dans le détail, il convient de revenir au problème principal à l'origine de l'invention qui consiste à trouver une adresse ou une personne à partir de données incomplètes fournies par un client à un opérateur téléphonique. Il est rappelé ici que ce problème est notamment illustré en figure 4.

En appliquant la méthode décrite ci avant, les étapes d'identifications 3 et 4 de nom de voies et de type de voies ont révélé respectivement une quantité N de résultats possibles auxquels sont associés des coefficients de probabilité.

Par exemple, la méthode selon l'invention a révélé les 3 noms de voies dont les probabilités de similitude sont les meilleures, et les 3 types de voies dont les probabilités de similitude sont les meilleures. Dans cet exemple, N est égal à 3.

N peut être une quantité de résultats préalablement définie. N n'est toutefois pas limité à cette définition. N peut également être défini comme la quantité de résultats dont la probabilité est supérieure à un pourcentage donné.

L'étape d'identification 7 de l'adresse recherchée met en œuvre le procédé d'identification de structure selon l'invention.

II convient ici de rappeler la définition du problème d' appariement : soit s une structure renseignée (ou instance observée) et ES = -{si, s2, s3...sn) une collection de structures appartenant à un répertoire. Le problème d' appariement de structures consiste à trouver l'instance ou les instances dans ES les plus similaires à s.

Il convient également de rappeler que la structure s est potentiellement erronée.

Le modèle d' appariement de structures reprend en partie le modèle d' appariement de groupes d'atomes. Trois variables additionnelles s, i et fi sont toutefois introduites.

La variable s représente une structure parmi toutes celles de la collection ES appartenant au répertoire associé.

La variable i représente l'indice d'un groupe d'atomes de s et fi est le « i-ème » groupe d'atomes de s.

Le réseau bayésien de l ' appariement de structures est schématisé sur la figure 3.

Le calcul de probabilité d' appariement de structures est le suivant :

P (s i fi fi j j aj aj) = P(s) P( i / s ) P(fi / s i) P(fi / fi) P(J / fi) P(J / j) P(aj / j fi) P(âj / aj)

P(s) est la probabilité, ou distribution, des instances de ES.

P( i / s ) est la probabilité de l'indice d'un groupe d'atomes de s. Cette probabilité est définie comme suit :

Si i>= longueur ( s ) , alors P ( i / s ) = 1 / longueur ( s ) , sinon P( i / s ) = 0

P(fi / s i) est une distribution de probabilité du i-ème groupe d'atomes étant donné s et i :

P(fi / s i) = 1 si fi est le i-ème groupe d'atomes de s, sinon P(fi / s i) = 0

P(fi / fi) est la distribution obtenue à partir du sous- modèle d' appariement de groupes d'atomes décrit précédemment. La distribution P(fi / fi) représente la probabilité d ' appariement de l'élément fi du dictionnaire F étant donné le i-ème groupe d'atomes d'une structure dans le répertoire ES. Cette distribution doit être construite à

partir du modèle bayésien d' appariement de structures en calculant la probabilité P (f / f) pour chaque structure appartenant à la collection du répertoire.

Les autres distributions P(j / fi), P(j / j), P(aj / j fi) et P(âj / aj ) sont analogues à celles présentées dans la méthode d'identification de groupes d'atomes définie précédemment.

Le calcul de probabilité détaillé qui est utilisé est le suivant :

Soit s = [l,fl], [2,f2], ... [n,fn]

La distribution de probabilité d' appariement d'une structure P(s / s) est alors calculée comme suit :

P(s / s) = P(s / [l,fl], [2,f2], ... [m,fm])

En substituant fm par la séquence de couples <j, aj> pour j≈l, ..., k, nous avons :

P(s / [l,fl], [2,f2], ... [m,fm])

= P(s / [l,fl], [2,f2], ... [m-l,fm-l] [m, <1, âlm><2, a2m>...<m, akm>])

= P(s / [l,fl], [2,f2], ... [m-l,fm-l] [m, <1, àlm><2, â2m>...<m, I(k-1 )m> ] )

P( i = m/s )

σ _f i _f i _{j aj} P (fi / S i = m) P(fi / fi) P(J /fi) P(j=k / j)

P(aj / j fi) P(âj = ikm /aj ) avec

P (s / <1, ill>) = P(s) P(i=l /s)

∑ _f i _{f j aj} P (fi / s i = 1) P(fi / fi) P(J /fi) P(J=I

/ j) P(aj / j fi) P(Ij = 111 /aj)

Maintenant que le calcul de probabilité a été détaillé, il convient de revenir au problème principal à l'origine de l'invention qui consiste à trouver une adresse ou une personne à partir de données incomplètes fournies par un client à un opérateur téléphonique.

Il est rappelé ici que ce problème est notamment illustré en figure 4.

à partir des résultats fournis par les étapes 4 et 3 respectivement d'identification de type de voie 4 et de nom de voie 3, et du procédé selon l'invention, l'étape 5 d'identification de la voie a délivré l'adresse la plus probable compte tenu des indications du client.

Par consultation du répertoire ES, le système informatique fourni à l'opérateur, le nom de la personne associée à l'adresse trouvée. C'est l'étape d'identification 6 représentée sur la figure 4.

II convient de noter que l'invention pourrait s'appliquer uniquement à la recherche d'une personne à partir de son seul nom.

Cette application est illustrée par le diagramme de la figure 5 montrant les échanges de données générés par la méthode d'identification selon l'invention.

L'opérateur 1 renseigne un champ en saisissant une séquence d'atomes f dictée par un client.

Le système appliquerait la méthode selon l'invention pour identifier une quantité donnée N de noms auxquels le nom saisi pourrait se rapporter, et ne délivrerait comme résultat uniquement le groupe d'atomes f auquel sera associé la plus grande probabilité d' appariement .

Une application particulière de l'invention concerne la recherche de doublons dans une base de données.

Pour cette application, on procède à une étape d'identification de doublons potentiels consistant à calculer, pour chaque structure enregistrée dans la base de données, une signature formée par une collection d'identifiants de sous-structures analogues, puis à constituer un sous-ensemble des structures dont les signatures sont corrélées, la fonction de corrélation étant déterminée par l'existence pour chaque groupe intermédiaire des structures comparées d'au moins un identifiant commun, puis à calculer pour les structures appariées par la fonction de corrélation, le résultat de l'application sur chacun desdites structures appariées du traitement selon la méthode de l'invention, et à affecter un indicateur de proximité fonction de la proximité desdits résultats.

La description qui suit concerne un exemple particulier de l'application de l'invention à la recherche de doublons dans une base de données par une méthode Bayésienne

Soit D une base de données1, S la structure d'une entrée dans la base D, et si, sj deux instances de S, alors sj est un doublon de si si sj est censé de représenter la même information que si et vice-versa.

Les éléments si et sj ont une structure bien définie. Nous rappelons qu'une « structure » est un ensemble composé de plusieurs groupes d'atomes également appelées « fingerprints » .

Par exemple, une base des données des institutions éducatives pourraient avoir les lignes ci-dessous.

Non de l'institution : Center for Computing Research

Adresse : Av. Juan de dios Bâtis s/n casi esq. Miguel Othon de Mendizabal

Ville : Mexico Etat ou Région : D. F. Code Postal : 07738 Pay : Mexique

Non de l'institution : Center for Computing Research (CIC);

Adresse : Av. Juan de Dios Bâtiz s/n casi esquina Miguel Othόn de Mendizabal

Ville : Mexico

Etat ou Région : Mexico D. F

Code Postal : 07738

Pay : Mexique

Non de l'institution : Center for Computing Research of the National Polytechnic Institute

Adresse : Av. Juan de Dios Bâtiz s/n, Esq. Miguel Othόn de Mendizâbal Unidad Profesional Ville : Mexico

Etat ou Région : Mexico. D. F.; Code Postal : 7738 Pay : Mexique

Les trois entrées précédentes correspondent à trois instances de la structure S de la base. Appelons ces instances si, s2 et s3 respectivement. Ces instances sont censées représenter la même information, malgré les différences de leur contenu. Nous appelons un ensemble de doublons à tout ensemble d'instances sensées de représenter la même information. Ainsi, l'ensemble ES={sl, s2, s3 } est un ensemble de doublons. Par simplicité, nous considérons qu'un ensemble de cardinalité 1 est aussi un ensemble de doublons .

Une base des donnés D est composée d'un ensemble d'instances d'une structure S :

D-{J,,J,,...,J _B }

Le dédoublonnage de D consiste à :

Trouver une partition de dédoublonnage I •' ² ' ^"' ' ^k > de D où chaque sous-ensemble A- de la partition est un ensemble de doublons .

Pour chaque sous-ensemble '' dans la partition, créer une instance ^s ι dit « propre » et représentant le sous- ensemble ^υ > . L'instance ⁵ ' est obtenue à partir d'une fonction de nettoyage f\', c'est-à-dire ^s ι ^{= J} \ ^υ i) . La fonction ^J \' pourrait simplement rendre un élément de Q _ou bien, une instance résultant d'une procédure complexe combinant les groupes d'atomes ( fingerprints ) des éléments de A.

La base de données est le dédoublonnage de D.

La problématique principale de la procédure décrite dans le paragraphe précédent est l'obtention d'une partition P de dédoublonnage. Dans ce paragraphe, nous décrivons le principe permettant d'obtenir cette partition.

Nous notons v ⁵ "P ⁾ le sous-ensemble de D défini comme suit:

D{s _i ,p)

Où '(ψλ est la distribution de probabilité d' appariement de s ^' /. à ^s ι et P J ' J est un seuil de probabilité d' appariement. L'ensemble est appelé l'ensemble d' appariement de ⁵ < dans D. Si nous obtenons l'ensemble d' appariement pour

toutes les instances de D alors nous obtenons l'ensemble D contenant les ensembles d' appariement de D :

D=[D(S ₁ ,p),D(s ₂ ,p),...,D(s _n ,p)}

Clairement, D n'est pas nécessairement une partition de D car une intersection peut exister entre deux ensembles d' appariement ^D { ^s nP) et I ¹ V/ . Cependant, à partir de l'ensemble D ₁ il est possible d'obtenir une partition P de D. Les éléments apparaissant dans plus d'un ensemble d' appariement pourraient être conservés uniquement dans l'ensemble où leur probabilité d' appariement est la plus grande. Ainsi, nous avons que V / ou ^w est la fonction transformant D dans une partition de D. Dans la suite, nous appelons D l'ensemble base de P .

La construction de l'ensemble base D peut s'avérer très lourde. En effet, D est obtenu à partir de la comparaison de (nxn-n) _paires (s,,Sj)≡DxD _{Qù i≠j} ^ _{vQ±r Eχpression (1)# Une} cardinalité n importante pourrait rendre cette tâche prohibitive. D'autre part il nous faut définir la fonction

^w. Dans les paragraphes suivants, nous expliquons comment il est possible de relaxer le calcul de l'ensemble base.

Nous rappelons qu'une instance de structure s est composée d'un groupe d'atomes (fingerprints) :

W.λ-λ

Par exemple pour l'instance suivante :

Non de l'institution : Center for Computing Research Adresse : Av. Juan de dios Bâtis s/n casi esq. Miguel Othon de Mendizabal

Ville : Mexico Etat ou Région : D.F. Code Postal : 07738 Pay : Mexico

Nous avons six groupes d'atomes:

/i = Center for Computing Research

/2 = Av. Juan de dios Bâtis s/n casi esq. Miguel Othon de Mendizabal /3 = Mexico

J ₆ = Mexique

Soit ' V ¹ '^ ²¹ ' ' ^Jn i un dictionnaire quelconque de n éléments associé à -A et une valeur de probabilité, nous définissons la caractérisation de /1 comme suit :

C,={ye{l,2,...,n}|P(/;|/,)> _λ }

où v/J/, ⁾ _est la probabilité d' appariement de f> à *J. L'ensemble ^' est l'ensemble d'identificateurs du dictionnaire ^ pour lesquels la probabilité d' appariement avec Ji est supérieure ou égale à Pc. Par exemple, si le dictionnaire ^s est défini comme suit :

F ₅ = {/, ⁵ = 07778, / ₂ ⁵ = 098535, / ₃ ⁵ = 077654, / ₄ ⁵ = 07638}

alors, pour notre exemple d'instance précèdent nous pourrions avoir que :

C ₅ = {1,4}

If ⁵ = 07778^ Autrement dit, la probabilité d' appariement de V- ⁷ ' ' et

(/ ₄ ⁵ =07638) avec U= ⁰⁷⁷³⁸ ) est supérieure ou égale à Pc.

Similairement, étant donné un ensemble de dictionnaires F ₁ F ₂ ...F _L associés à une structure S, nous définissons la caractérisation d'une instance de S comme l'ensemble des caractérisations de ses groupes d'atomes :

C(^) = (C ₁₅ C ₂ -Q)

Ainsi, la caractérisation de s pourrais être, par exemple :

C(5,p _c )=({l,5,7},{l,2,8}-{7,8}) L'obtention de l'ensemble de base réside dans le calcul des caractérisations des instances de la base des données.

Soit deux instances quelconques -V-^ ^ D alors ^s i est un doublon potentiel de ⁵ i si ^VC < ^GC ( ⁵ "O' ^C - ^{2 E 6} VvZ ⁷ J _{nQug avons que} C ₁ HC ₁ ^≠ 0 _# NOUS dénotons cet ensemble par ^D λ ^s ι) .

Par exemple, soit C{s _vPc ) = (c\ = = {l,3,5},c; = = {5,7},) , C(S ₂ , p _L ) ≈ (C ₁ ² = {2,3},C ₂ ² = {3,5,8},C ₃ ² = {2},C ² = {l,5,}) ,

C(s ₃ ,pJ = (c'≈{3},C ₂ ³ ≈{\,5},C ₃ ⁱ ={3},Cl≈{l,l},) alors ^s i est un doublon potentiel de ⁵ i. Contrairement, ⁵ 3 n'est pas un doublon potentiel de ⁵ i car C ₃ DC ₃ =O _^

L ' ensemble base D ≈ {D{s _v p),D{s ₁ ,p),...,D{s _n ,p)} _{est re} _ _{déf ini en} redéfinissant — ^υ _cornme suit :

L'invention concerne encore des applications telles que la fusion de bases de données et la constitution de grappes de structures homologues à une structure de référence.

Pour une application à la fusion de bases de données, on procède à une étape d'identification de doublons potentiels consistant à calculer, pour chaque structure enregistrée dans chacune des bases de données, une signature formée par une collection d'identifiants de groupes intermédiaires analogues, puis à constituer un sous-ensemble des structures dont les signatures sont corrélées, la fonction de corrélation étant déterminée par l'existence pour chaque groupe intermédiaire des structures comparées d'au moins un identifiant commun, puis à calculer pour les structures appariées par la fonction de corrélation, le résultat de l'application sur chacun desdites structures appariées du traitement selon la revendication 8 et à affecter un indicateur de proximité fonction de la proximité desdits résultats et à enregistrer une base de données fusionnée avec les structures uniques.

Pour l'application de constitution de grappes de structures homologues à une structure de référence, on applique la méthode objet de la revendication 1 à ladite structure de référence d'une part, et à l'ensemble des structures disponibles d'un répertoire, pour déterminer pour chacune desdites structures disponibles une probabilité de similitude et à enregistrer dans un sous-ensemble les

structures disponibles dont la probabilité de similitude est supérieure à une valeur prédéterminée.

D'autres applications sont prévues : Nettoyage de base de données marketing et commerciales

II s'agit d'une application qui rassemble l'ensemble des fonctions permettant de nettoyer une base de données avec dédoublonnement de bases, fusion de bases, normalisation, clusterisation et aide à la saisie. Le produit ciblerait en priorité les entreprises gérant des bases de prospects ou de clients.

Fonctionnalités

Les fonctionnalités vont s'aligner sur le cycle de vie des données dans les métiers marketing et vente dans les entreprises :

- Le dédoublonnage de bases de données, qui s'applique à une table existante comprenant des doublons approximatifs.

- La fusion de bases de données. Avec comme exemple, un magasin d'outillage qui rachète un concurrent, mais dont les bases produits comprennent des noms des champs et un MCD différents.

- La caractérisation de clients à partir de navigation dans le web, la chaîne de clics...

- Les rapprochements : application dans la fraude à la carte bancaire. {Bases historiques de transactions, fichiers fraude (Banque de France), Notion de rapprochement, Heures systèmes différentes, Montants pas équivalents (commissions, arrondis, taux de change, ...).

A part le numéro de carte qui est déterministe, le reste est flou. Objet complexe : chaîne de caractères. Gestion les dates rapprochées avec notion de distance entre deux dates.

- Le profilage et le clustering : Quels sont les structures qui correspondent à un profil-type ? On définit des classes avec des exemples .

Classification : Outil de segmentation multi-critères marché qui fonctionne par apprentissage et inférence.

La normalisation. A partir de plusieurs informations imparfaites, trouver l'index dans la base de données qui correspond.

- L'aide à la saisie : Taper adresses n'importe comment, et elles sont mises au bon format en fonction de base de référence. On nettoie et on choisit les bonnes occurrences. Proposition des structures existantes si une nouvelle entrée y ressemble, prévention de doublons (se rapproche de la normalisation) . - Corrections dynamiques : Modèle probabiliste des touches d'ordinateur. En fonction du champ sémantique.

- Le nettoyage et l'indexation d'une base par interrogation d'un système d'information distant.