Brevet FR2905777A1 — publié le 20080314

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 s 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. On appellera ci-après structure un ensemble composé de plusieurs groupes io 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. L'atome est la plus petite partie indivisible du groupe d'atomes. 15 Les groupes d'atomes sont également appelés fingerspints . On appellera dictionnaire un ensemble de groupes d'atomes prédéterminés. 20 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 à 25 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. 2905777 2 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. s 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. io 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 par 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. 15 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. 20 Aussi, l'invention vise notamment à être mise en oeuvre 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 25 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 30 peut commettre des erreurs de saisie ou mal comprendre la requête du client. 2905777 3 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 oeuvre par des moteurs de recherche, qui permettent une recherche de structures parmi une pluralité de structures. to De manière générale, 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. Les méthodes connues comportent une étape de renseignement préalable de is 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. 20 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. 25 Une méthode connue de recherche d'une structure parmi une pluralité de structures 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 30 exactement les mêmes atomes ordonnés de la même manière. 2905777 4 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 5 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. 15 À 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. 20 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 25 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 oeuvre une telle méthode est bien souvent insuffisante, ce qui 30 entraîne des anomalies de fonctionnement. lo 2905777 5 L'identification d'une structure à partir de cette méthode semble ainsi très difficile. Une autre méthode est encore mise en oeuvre dans les téléphones portables 5 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 io 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, 15 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. 20 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. II devra même effacer les lettres qu'il a tapées pour écrire de nouveau et 25 correctement le mot qu'il cherche. La présente invention vise à pallier les inconvénients de l'état de la technique actuelle. 2905777 6 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 5 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 io 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. 15 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. 20 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, 25 - 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. 2905777 7 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. 5 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 lo 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 oeuvre la méthode. 15 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 20 caractère de chaque atome dans la séquence d'atomes du groupe d'atomes qui est renseigné. Il 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 25 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 30 é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. 5 2905777 8 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 io 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 15 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 20 - 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 25 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. 20 2905777 9 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 5 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 io 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 15 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 oeuvre les étapes suivantes : - identification de toutes les combinaisons potentielles de structures à partir des N groupes d'atomes potentiels identifiés, 25 - 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, 30 - pour chaque appariement, calcul d'une probabilité de similitude, 2905777 l0 - 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. 5 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 io 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é 15 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 oeuvre le procédé d'identification décrit précédemment, ainsi qu'un 20 système d'identification de groupes d'atomes mettant en oeuvre la méthode d'identification décrite précédemment. On décrira maintenant un exemple de mise en oeuvre de la méthode et du procédé selon l'invention en faisant référence aux dessins annexés, parmi 25 lesquels : la figure 1 représente un réseau bayésien mis en oeuvre 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, 20 2905777 11 la figure 3 représente un réseau bayésien mis en oeuvre 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, 5 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. io 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 is 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, 25 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 15 2905777 12 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 s adresse. La structure s comprend des groupes d'atomes f1, f2, f3, f4 et f5. Chaque groupe d'atomes est associé à un dictionnaire F comportant une 10 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 f1 est associé au dictionnaire FI qui concerne les numéros, et qui comporte tous les numéros de 1 à 999, par exemple. Aussi, le dictionnaire F1 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 20 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 25 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. 25 2905777 13 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 5 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 R1 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. 5 20 2905777 14 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 T3. Ce calcul de probabilité est noté P(f3/f3) sur la figure 4. II en va de même pour le calcul de probabilité du type de voie f2 connaissant le lo 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 oeuvre pour identifier plusieurs types de voies f3 possibles à partir d'une séquence de caractères saisie par l'opérateur 1 dans le 15 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/ff), la demanderesse représente un groupe d'atomes observé f par une séquence de couples : f= ... où âj 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 . 2905777 15 Dans le cadre de cet exemple, on a : f= 5 On cherche à calculer P (f / f) = P (f / ... ), où k = longueur M. Pour calculer cette valeur pour tout élément f appartenant au dictionnaire F, il faut considérer que chaque couple (j, âj) est un couple d'observation d'un 10 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 15 valeur âj 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 : 20 P(f j j aj âj) = P (f) P(j / f) P(f / 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. 25 P(f) est la distribution de probabilité de l'ensemble des groupes d'atomes dans le dictionnaire Fet elle est connue. 5 2905777 16 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 ... ) = P (f / ... ) 1, aj P(j / f) P(j =k / j) P(aj/ j f) P(âj = âk /aj) 2905777 18 avec P(f / ) = P(f) li, ai P(j / f) P(j =1 / j) P(aj/ j f) P(âj = â1 /aj) Maintenant que le calcul de probabilité a été expliqué dans le détail, il convient 5 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. io 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 is 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 20 résultats dont la probabilité est supérieure à un pourcentage donné. L'étape d'identification 7 de l'adresse recherchée met en oeuvre le procédé d'identification de structure selon l'invention. 25 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 = s1, 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. 10 20 25 2905777 19 II convient également de rappeler que la structures est potentiellement erronée. Le modèle d'appariement de structures reprend en partie le modèle s 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 15 3. Le calcul de probabilité d'appariement de structures est lesuivant : P (s i fi fi j f 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 2905777 20 P(f / s i) est une distribution de probabilité du i-ème groupe d'atomes étant donné s et j: P(fi / s i) = 1 si fi est le i-ème groupe d'atomes de s, sinon P(fi / s i) = 0 5 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 to ê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 PO / fi), P(j / j), P(aj / j fi) et P(âj / aj) sont analogues à 15 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 : 20 Soit s = [1,f l], [2,f2], ... [n,fn]. La distribution de probabilité d'appariement d'une structure P(s / s) est alors calculée comme suit : 25 P(s / s) = P(s / [1,f1 ], [2,f2], ... [m,fm]) En substituant fm par la séquence de couples pour j=1, ..., k, nous avons : 15 2905777 21 P(s / [1 f1], [2,f2], ... [m,fm]) = P(s / [1,f l], [2,f2], ... [m-1,fm-1 ] [m, ... ]) = P(s / [1,f1 ], [2,f2], ... [m-1,frn-1 ] [m, ... ]) 5 P(i = m/s) f r i ai P (fi / s i = m) P(fi / fi) P(j /fi) P(jû=k / j) P(aj / j fi) P(âj = âkm /aj) avec P (s / ) = P(s) P(i=1 /s) f fi ai P (fi / s i = 1) P(fi / fi) P(j /fi) P(jû=l / j) P(aj / j fi) P(âj = a11 /aj) 10 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. A 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 20 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 25 6 représentée sur la figure 4. 2905777 22 Il 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 s é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. io 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. 15 25 REVENDICATIONS 1 û Méthode pour identifier une quantité N de groupes d'atomes (f) potentiels parmi une collection de groupes d'atomes, ladite collection appartenant à un dictionnaire (F), ledit dictionnaire comportant une quantité déterminée Q de groupes d'atomes (f), chaque groupe d'atomes (f) étant constitué d'une séquence d'atomes (a) qui sont ordonnés les uns par rapport aux autres et qui appartiennent chacun à un alphabet, ledit alphabet comportant une quantité déterminée d'atomes de caractères différents, io ladite méthode comportant : - une étape de renseignement d'un champ par un groupe d'atomes potentiellement erronés constituant un groupe d'atomes renseigné (f), - et une étape d'identification de ladite quantité N de groupes d'atomes potentiels pouvant correspondre audit groupe d'atomes renseigné (f) parmi ceux 15 de ladite collection dudit dictionnaire (F) caractérisée en ce que ladite étape d'identification consiste en les étapes suivantes : - appariement dudit groupe d'atomes renseigné (f) avec chacun des Q groupes d'atomes (f) de ladite collection dudit dictionnaire (F), 20 - pour chaque appariement, calcul d'une probabilité P(f / f) de similitude entre le groupe d'atomes renseigné (f) et le groupe d'atomes du dictionnaire apparié (f), - et identification des N groupes d'atomes potentiels dont la probabilité de similitude est la plus forte ou dont la probabilité est supérieure à une valeur seuil. 2. Méthode d'identification selon la revendication 1, caractérisée en ce que le calcul de ladite probabilité de similitude P(f I f) est un produit de calculs de probabilités pour chaque atome du groupe d'atomes qui est renseigné M. 2905777 24 3. Méthode selon la revendication 2, caractérisé en ce que, lesdits calculs de probabilités prennent en compte la position (j, j) et le caractère (aj, âj) de chaque atome (a) dans la séquence d'atomes du groupe d'atomes qui est renseigné M. s 4. Méthode selon l'une quelconque des revendications 2 ou 3, caractérisé en ce que les calculs de probabilités prennent en compte un facteur de confusion phonétique entre d'une part un atome de position (j, j) et de caractère (aj, âj) définis qui est identifié dans le groupe d'atomes renseigné, et d'autre part un autre atome. i0 5. Méthode selon l'une quelconque des revendications 2 à 4, caractérisé en ce que les calculs de probabilités prennent en compte un facteur de confusion de voisinage dist(âj, aj) 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. 15 6. Méthode selon l'une quelconque des revendications 2 à 5, caractérisé en ce que les calculs de probabilités prennent en compte un facteur de confusion visuelle entre d'une part un atome de position (j, j) et de caractère (aj, âj) définis qui est identifié dans le groupe d'atomes renseigné, et d'autre part un autre 20 atome. 7. Méthode selon l'une quelconque des revendications 2 à 6, caractérisé en ce que les calculs de probabilités prennent en compte un facteur de confusion géographique sur un clavier de saisie des atomes, entre 25 -d'une part un atome observé dans la séquence d'atomes du groupe d'atomes renseigné, l'atome observé présentant une position (j, j) et un caractère (aj, âj) 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 30 touche identifiée sur ledit clavier qui est associée à l'atome observé. 2905777 25 8 - Procédé pour identifier une structure (s) parmi une collection de structures appartenant à un répertoire (ES), ladite structure (s) comportant au moins deux groupes d'atomes (fi, f2), chacun des groupes d'atomes (fi, f2) étant associé à 5 un dictionnaire (FI, F2), ledit procédé consistant à identifier, pour chaque groupe d'atomes (fi, f2), une quantité N de groupes d'atomes (f) en appliquant la méthode selon l'une quelconque des revendications précédentes, ledit procédé d'identification de structure étant caractérisée en ce qu'il comporte io 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 (s) avec chacune des structures (s) de la collection de structures du répertoire (ES), - pour chaque appariement, calcul d'une probabilité de similitudes P(s / s), - et identification de la structure (s) la plus pertinente parmi celles de la collection de structures (s) du répertoire (ES), dont la probabilité de similitude P(s / s) avec une structure (s) du répertoire est la plus forte. 9 ù Procédé d'identification selon la revendication 8, caractérisé en ce que le 25 calcul de ladite probabilité de similitude P(s / s) tient compte de la probabilité P(fi/f[) d'identifier un groupe d'atomes donné dans une structure connaissant le groupe d'atomes qui lui est voisin. ù Système d'identification de structures mettant en oeuvre le procédé 30 d'identification selon l'une quelconque des revendications 8 ou9. 20 2905777 26 11 ù Système d'identification de groupes d'atomes mettant en oeuvre la méthode d'identification selon l'une quelconque des revendications 1 à 7.