Brevet FR2970100A1 — publié le 20120706

L'invention concerne le domaine des procédés de génération de carnets d'adresses consolidés comportant plusieurs contacts consolidés. ARRIERE PLAN DE L'INVENTION De nombreuses applications utilisent ou génèrent des carnets d'adresses. Par exemple un utilisateur possède fréquemment . - un carnet d'adresses pour chacun de ses comptes de messagerie électronique ; - un carnet d'adresses enregistré sur son téléphone portable ; - des carnets d'adresses distincts enregistrés chez chacun de ses fournisseurs de services téléphoniques ; - des carnets d'adresses distincts enregistrés pour chaque profil des forums Internet auxquels est inscrit l'utilisateur.... Un carnet d'adresses comporte généralement plusieurs contacts sources et chacun de ces contacts comporte : - plusieurs champs chacun formé de caractères ; et - certains au moins de ces champs sont typés par une information de typage de champ. Une information de typage de champ est censée indiquer le type d'information contenu dans le champ comme un nom, un prénom, une adresse de messagerie électronique,un numéro de téléphone, de fax, ou une adresse postale, etc.. Il est la plupart du temps difficile pour l'utilisateur de retrouver un contact donné dans tous ses carnets d'adresses qui sont bien souvent non cohérents. Pour cette raison, les opérateurs téléphoniques ou Internet proposent fréquemment de regrouper des carnets d'adresses provenant de sources différentes pour générer un seul carnet d'adresses contenant les contacts issus desdits carnets d'adresses. Toutefois, il reste toujours difficile pour l'utilisateur de retrouver un contact donné dès lors que son carnet d'adresses regroupe un grand nombre de contacts qui peuvent être des doublons. La taille de ces carnets d'adresses oblige à disposer d'une mémoire relativement importante et rend leur consultation difficile ou à tout le moins peu pratique, en particulier lorsque l'écran dont dispose l'utilisateur a lui-même une petite taille. OBJET DE L'INVENTION Un objet de la présente invention est de fournir un procédé de génération d'un carnet d'adresses consolidé comportant plusieurs contacts consolidés et permettant à l'utilisateur de gagner du temps dans l'identification de doublons potentiels. RESUME DE L'INVENTION A cet effet il est proposé un procédé de génération d'un carnet d'adresses consolidé comportant plusieurs contacts consolidés, comprenant : - l'obtention et la mémorisation de carnets d'adresses sources provenant de sources distinctes, chacun de ces carnets d'adresses sources comportant plusieurs contacts sources, chacun desdits contacts sources et desdits contacts consolidés comportant plusieurs champs chacun formé de caractères et certains au moins de ces champs étant associés à une information de typage de champ ; - la détermination et la mémorisation d'une liste de mots à partir de chacun des carnets d'adresses sources, chaque dit mot comportant : - une chaîne de caractères déterminée à partir d'une chaîne de caractères d'un champ donné d'un contact source donné ; et - une information de typage du mot. Le procédé comporte en outre : - une opération de détermination et de mémorisation de paramètres représentatifs de degrés de similarité entre certaines au moins des chaînes de caractères de certains au moins des mots de la liste de mots ; et - une opération de détermination et de mémorisation de paramètres représentatifs de degrés de similarité entre des contacts sources en fonction desdits degrés de similarité entre mots ; - une opération de classement des contacts sources en groupes, chaque contact source classé étant classé dans un seul des groupes en utilisant les paramètres représentatifs des degrés de similarité entre les contacts sources ; et - une opération de fusion de contacts sources consistant à générer un contact consolidé à partir d'au moins deux contacts sources classés dans un même groupe de contacts sources. Un avantage de l'invention est qu'en déterminant une liste de mots et en calculant la distance entre des chaînes de caractères de ces mots, on évite de devoir comparer les chaînes de caractères des contacts sources deux à deux, puisque l'on compare des mots deux à deux et puisque chaque mot comporte une chaîne de caractères qui peut appartenir à plusieurs contacts source. Grâce à ce procédé, on supprime avantageusement, efficacement et aisément les frontières « potentielles » ce qui permet de comparer «tous» les champs d'un contact avec «tous» les champs d'un autre contact. Le «composant» qui sert à la comparaison étant bien de préférence ici le mot et non le couple (Valeur, Champ), les mots étant avantageusement comparés, de manière imagée, après avoir été puisés dans un réservoir de mots. Ainsi, on fournit à l'utilisateur des groupes de contacts sources classifiés en fonction de leurs similarités sans avoir à comparer directement les caractères d'un champ d'un contact source avec les caractères d'un autre champ d'un autre contact source. L'invention peut permettre de réduire grandement le nombre de comparaisons à réaliser entre des champs de contacts sources distincts, ce qui réduit d'autant le temps de calcul nécessaire au regroupement des contacts sources. En particulier plus le nombre de contacts sources à classer et plus le nombre de champs composant ces contacts sources sont importants et plus l'invention permet un gain de temps dans le classement en groupes de ces contacts. Dès lors que l'on identifie des mots similaires entre eux chacun lié à plusieurs contacts sources, on constate un gain de temps dans le classement. Par exemple, le fait d'identifier des mots de type nom, ayant des chaînes de caractères similaires entre elles, permet de savoir que tous les contacts sources à partir desquels ont été formés ces mots sont potentiellement des doublons, et cela sans devoir comparer entre elles les chaînes de caractères des champs des contacts sources et leurs chaînes de caractères respectives. Comme on le verra par la suite, le classement des contacts sources dans les groupes de contacts sources est réalisé de manière que chaque contact source d'un groupe donné ait un degré de similarité avec au moins un des autres contacts sources de ce même groupe qui est supérieur à son degré de similarité vis-à-vis d'au moins un des contacts sources des autres groupes de contacts sources. Pour la mise en oeuvre du procédé selon l'invention, on peut aussi faire en sorte qu'à chaque mot on associe au moins un pointeur, chaque pointeur désignant un contact source à partir duquel le mot a été déterminé. Le pointeur permet de lier un mot au contact source à partir duquel il a été formé. Chaque pointeur désigne un contact source contenant une chaîne de caractères à partir de laquelle on peut générer la chaîne de caractère contenue dans le mot. Ainsi, lorsqu'un mot est associé à plusieurs pointeurs, cela signifie que ce même mot peut être généré à partir de chacun des contacts sources auxquels il est associé car ces contacts sources ont des chaînes de caractères similaires. L'étude du degré de similarité de deux mots chacun associé à plusieurs pointeurs permet de réaliser une étude de similarité entre les contacts sources auxquels sont liés ces mots et cela sans avoir à comparer tous ces contacts entre eux. Pour la mise en oeuvre du procédé selon l'invention, on peut aussi faire en sorte que, pour déterminer chaque mot, on analyse une chaîne de caractères d'un champ d'un contact source et, en fonction de paramètres d'analyse prédéterminés, on détermine une information de typage associée à cette chaîne de caractères du contact source puis, en fonction de cette information de typage et selon les paramètres d'analyse prédéterminés, on génère une chaîne de caractères du mot qui est soit identique à la chaîne de caractères du champ du contact source, soit normalisée selon des paramètres de normalisation prédéterminés. Le fait de normaliser la chaîne de caractères issue du champ du contact source afin de générer le mot et le fait que cette chaîne de caractères soit normalisée en fonction de l'information de typage de cette chaîne permet de supprimer des chaînes de caractères pouvant être des doublons au motif qu'elles auraient une légère différence. Ainsi on réduit le nombre de mots créés et on réduit par conséquent le nombre de comparaisons de ces mots à réaliser. Il en résulte encore un gain de temps dans la comparaison et une pré-détection des contacts sources potentiellement doublons. Pour la mise en oeuvre du procédé selon le précédent mode de réalisation de l'invention, on peut faire en sorte que chaque chaîne de caractères de chaque mot soit normalisée de manière que : - les caractères composant cette chaîne aient un seul type de casse, préférentiellement une casse minuscule ; et/ou - que des caractères de délimitation de cette chaîne, tels que des espaces en double ou des guillemets en fin ou début de chaîne de caractères, soient supprimés ; et/ou - que chaque caractère accentué de cette chaîne soit remplacé par un caractère correspondant non accentué. Cette normalisation est particulièrement avantageuse car elle permet d'éviter de générer des mots inutiles car issus de contacts sources formant vraisemblablement des doublons. En effet, si deux contacts sources diffèrent l'un de l'autre uniquement parce qu'ils ont des différences de casse et/ou d'accentuation et/ou comportent des délimitations inutiles (double espace ou guillemet), la normalisation va permettre la création d'un mot unique pour ces deux contacts sources au lieu de deux mots désignant chacun un seul des contacts sources. Ceci réduit encore le nombre de comparaisons entre mots à effectuer pour détecter les contacts similaires (c'est-à-dire des doublons potentiels) et les regrouper en vue de les fusionner. Comme on le verra par la suite dans la description détaillée (Voir chapitres « CONSTITUTION DU CORPUS » et « PRE-TRAITEMENT »), outre ce prétraitement consistant à normaliser des chaînes de caractères, on peut avantageusement réaliser d'autres sortes de prétraitements en fonction de l'information de typage associée à la chaîne de caractères à traiter. Par exemple si la chaîne de caractères à traiter est de type adresse de messagerie électronique (ci-après appelée « mail »), on peut lui appliquer un traitement particulier. Une adresse de messagerie comporte obligatoirement : - un caractère « placé entre un identifiant de l'utilisateur (à gauche du caractère « @ »), et un nom de domaine (placé à droite du caractère « @ ») comprenant un caractère « . » séparant une extension (par exemple « com ») d'un préfixe de nom de domaine (par exemple « SFR »). Ainsi un paramètre d'analyse consiste à détecter dans la chaîne de caractères analysée (par exemple : « utilisateur@sfr.com ») la présence d'un caractère « et d'un caractère « . ». Si le caractère « est placé entre un premier groupe de caractères placés à gauche (en l'occurrence « utilisateur ») et un second groupe de caractères placés à droite (en l'occurrence « sfr ») et si ce second groupe de caractères est suivi à droite d'un caractère « . » lui-même suivi d'un troisième groupe de caractères (en l'occurrence « .com »), alors on crée un mot comprenant uniquement le premier groupe de caractères de la chaîne de caractères (en l'occurrence « utilisateur ») et on lui attribue l'information de typage « SOME MAIL » signifiant qu'il est issu d'une adresse de messagerie ou «SOME EXTRACTED NAME» signifiant qu'il s'agit d'un nom, au sens large, extrait d'une chaîne de caractères. Ce mot comportant uniquement le premier groupe de caractères (« utilisateur ») est intéressant car il est fréquent qu'il puisse être comparé avec des chaînes de caractères de mots de type nom ou prénom ou surnom. En cas de similarité entre ce mot comprenant ce premier groupe de caractères avec un autre mot, on peut alors déduire que les contacts sources utilisés pour déterminer ces mots sont des contacts sources sensiblement similaires et susceptibles d'être regroupés dans un même groupe pour être éventuellement fusionnés. D'autres exemples de prétraitements des chaînes de caractères pour constituer des mots seront donnés ci-après dans le cadre de la description détaillée. En particulier on verra d'autres types de paramètres d'analyses prédéterminés spécifiquement utilisés pour traiter des chaînes de caractères de type « numéro de téléphone » et « adresse ». Pour la mise en oeuvre du procédé selon l'invention, on peut aussi faire en sorte que l'information de typage d'un mot soit déterminée : - en fonction de l'information de typage du champ du contact source qui a servi pour déterminer le mot ; et/ou - en fonction d'une détection selon des paramètres d'analyse prédéterminés de la chaîne de caractères ayant servi à déterminer ce mot et/ou de la chaîne de caractères constituant ce mot. Ainsi on peut déterminer l'information de typage d'un mot : en donnant à ce mot l'information de typage directement importée du contact source, dans ce cas on fait confiance au typage du champ du contact source (par exemple parce qu'il provient d'une source connue pour normaliser ses contacts sources de façon fiable) ; et/ou en détectant dans la chaîne de caractères correspondante du contact source ou dans la chaîne de caractères correspondante du mot le type de cette chaîne de caractères. Grâce à cette manière de faire, on fiabilise l'information de typage du mot ce qui est utile pour affiner le regroupement automatisé des contacts sources. L'utilisateur voulant consolider ses différents carnets d'adresses sources et mettant en oeuvre le procédé selon l'invention obtient en retour, de manière automatisée, des groupes de contacts sources. Chacun de ces groupes comprend les contacts sources pouvant être éventuellement fusionnés. Il en résulte un gain de temps pour l'opération de détection de doublons potentiels et aussi pour l'utilisateur consolidant ses différents carnets d'adresses sources. A la fin du traitement, le typage le moins précis est retenu si, pour un même mot, les différentes sources ont donné des typages différents. Pour la mise en oeuvre de l'invention on peut aussi faire en sorte de : - créer un arbre de classement comprenant une racine portant des branches, chacune des branches étant soit portée par un même noeud de la racine, soit portée par un noeud d'une autre branche, l'ensemble des mots étant classé dans l'arbre de manière que chaque noeud porte uniquement les mots dont les chaînes de caractères sont strictement composées d'un même jeu de caractères et de manière que chaque noeud enfant porte uniquement les mots composés d'un jeu de caractères formant un sous-ensemble strict du jeu de caractères des mots portés par le noeud parent ; et - déterminer des familles de mots chacune strictement constituée par les seuls mots portés par un noeud enfant et le ou les noeuds parents placés entre le noeud enfant et le noeud racine ; et - réaliser ladite opération de détermination et de mémorisation de paramètres représentatifs de degrés de similarité entre certaines au moins des chaînes de caractères de certains au moins des mots de la liste de mots, uniquement pour les chaînes de caractères appartenant à des mots d'une même famille. L'utilisation d'un arbre portant les mots au niveau de ses noeuds est utile pour sélectionner des familles de mots qui ont en commun un même jeu de caractères. On limite ainsi l'opération de détermination et de mémorisation uniquement aux mots d'une même famille. On évite ainsi de devoir rechercher une similarité entre des chaînes de caractères clairement non similaires puisque n'appartenant pas à des mots d'une même famille de mots. Un exemple d'arbre sera donné ci-après dans la description détaillée au chapitre « INSERTION DANS L'ARBRE ». Pour la mise en oeuvre de ce mode de réalisation de l'invention, il est envisageable, pour créer l'arbre de classement, d'associer à chaque mot : - une information de nombre de caractères présents dans la chaîne de caractères de ce mot ; et - une information de jeu de caractères regroupant le jeu de caractères composant la chaîne de caractères du mot. Cette opération permet de créer l'arbre de classement en une seule passe, sans avoir à en modifier la structure puisque l'on sait que seront placés à un même noeud de l'arbre tous les mots ayant strictement un même jeu de caractères, et les mots sont placés de manière que la longueur des chaînes de caractères des mots aille en diminuant du noeud racine vers les noeuds de branche les plus éloignés du noeud racine. Ce mode de réalisation permet de réduire le temps nécessaire pour la création de l'arbre et réduire le temps de calcul nécessaire à l'obtention de groupes de contacts sources délivrés à l'utilisateur. Pour la mise en oeuvre de l'un quelconque des modes de réalisation précités de l'invention, on prévoit, pour réaliser l'opération de détermination et de mémorisation de paramètres représentatifs de degrés de similarité entre certaines au moins des chaînes de caractères de certains au moins des mots de la liste de mots, de mesurer ladite similarité entre les chaînes de caractères à l'aide de la méthode de Levenshtein. La méthode des distances de Levenshtein est une méthode bien connue de mesure de similarité entre deux chaînes de caractères. Cette mesure est égale au nombre minimal de caractères qu'il faut supprimer, insérer ou remplacer pour passer d'une chaîne de caractères à l'autre. Cette distance est d'autant plus grande que le nombre de différences entre les deux chaînes est grand. Bien entendu il serait aussi possible d'utiliser la méthode de Damereau-Levenshtein qui comprend en plus des opérations de suppression, d'insertion et de remplacement, une opération de transposition. Les méthodes de Levenshtein et de Damereau-Levenshtein permettent chacune de détecter une majorité des fautes d'orthographe humaines en mesurant la distance entre des chaînes de caractères de mots. Pour la mise en oeuvre de l'un quelconque des modes de réalisation précités de l'invention, on peut faire en sorte que, pour déterminer les paramètres représentatifs de degrés de similarité entre des contacts sources : - soit sélectionné un premier contact source lié à un premier groupe de mots déterminés à partir de ce premier contact source ; et - soit sélectionné un second contact source lié à un second groupe de mots déterminés à partir de ce second contact source ; - soient définies des paires de mots chacune constituée d'un mot du premier groupe de mots et d'un mot du second groupe de mots ; - soit vérifié, à l'aide de paramètres d'analyse prédéterminés S, et pour chacune des paires de mots ainsi définies, si l'on doit ou non utiliser le degré de similarité entre les chaînes de caractères des mots de la paire pour l'opération de détermination du paramètre représentatif de degrés de similarité entre ces premier et second contacts sources. Ce mode de réalisation, grâce au paramètre « S » (voir ci-après le paramètre « S » dans les matrices), permet de prendre en compte le degré de similarité entre des chaînes de caractères de mots différents uniquement si les types respectifs des mots comprenant ces chaînes de caractères sont compatibles entre eux. On évite ainsi de devoir comparer des distances entre des chaînes de caractères appartenant à des mots dont les types ne sont pas compatibles entre eux. Par exemple on verra ci-après en référence au chapitre « RAPPROCHEMENT DES ENREGISTREMENTS PAR PAIRES » qu'on ne va pas utiliser la distance / similarité entre des chaînes de caractères de mots de type « adresse courriel personnelle » (correspondant au type « some personal mail » ou au type « some mail ») avec des chaînes de caractères de mots de type « téléphone portable » (correspondant au type « some mobile phone » ou au type « some phone »). Par contre on constate toujours dans les matrices du chapitre « RAPPROCHEMENT DES ENREGISTREMENTS PAR PAIRES » que l'on va utiliser la distance / similarité entre des chaînes de caractères de mots de type « adresse courriel personnelle » (correspondant au type « some personal courriel » ou au type « some mail ») avec des chaînes de caractères de mots du même type ou de types considérés comme voisin comme « le nom du contact » (correspondant dans les matrices au type « Some Name ») ou comme le type « adresse courriel professionnelle » (correspondant dans les matrices au type « some work mail »). En l'occurrence, le paramètre d'analyse prédéterminé « S » (voir les matrices de la description détaillée) est, selon les types des mots à comparer, fixé à 0, ou 1, ou 2. Par convention, et à titre d'exemple : - « S » est fixé à 0 lorsque l'on souhaite que des chaînes de caractères des mots ne soient pas prises en compte pour la détermination du paramètre représentatif de degrés de similarité entre ces premier et second contacts sources ; - « S » est fixé à 1 lorsque l'on souhaite que des chaînes de caractères des mots soient prises en compte (pour la détermination du paramètre représentatif de degrés de similarité entre ces premier et second contacts sources) UNIQUEMENT si ces chaînes de caractères sont exactes (c'est-à-dire identiques entre elles) ; et - « S » est fixé à 2 lorsque l'on souhaite que des chaînes de caractères des mots soient prises en compte (pour la détermination du paramètre représentatif de degrés de similarité entre ces premier et second contacts sources) si ces chaînes de caractères sont similaires ou exactes. Pour la mise en oeuvre du précédent mode de réalisation du procédé selon l'invention, il est envisageable, pour chacune desdites paires de mots Cn et Lp dont le degré de similarité D(cn Lp) entre les chaînes de caractères des mots Cn, Lp doit être utilisé pour l'opération de détermination du paramètre représentatif de degrés de similarité entre ces premier et second contacts sources, de calculer un premier terme propre à cette paire de mots selon la formule . ter Terme = (BONUS (cn Lp) ) similarité dans laquelle : - BONUS est une valeur prédéterminée et fonction des informations de typage des mots Cn, Lp dont les chaînes de mots sont comparées ; et - Similarité = 2 * (tolérance - D(cn Lp) + 0.5) / tolérance ; sachant que : - la « tolérance » est égale au tiers du nombre de caractères (arrondi au nombre entier immédiatement inférieur) de la chaîne de caractères la plus courte entre les chaînes de caractères de la paire de mots ; et que - D (cn,Lp) est la distance de Levenshtein calculée entre les chaînes de caractères de la paire de mots (Cn,Lp) . Pour la compréhension de ce mode particulier de réalisation de l'invention, on note que la distance de Levenshtein est au minimum égale à 1 car les chaînes de caractères des mots sont différentes. Ainsi cette similarité converge vers 2 qui est la limite pour des chaînes de caractères identiques entre elles. Le BONUS est une valeur prédéterminée représentative de l'importance à donner à la paire de mots de types donnés, pour déterminer le paramètre représentatif de degrés de similarité entre ces premier et second contacts sources. Par convention, le BONUS est une valeur choisie pour être supérieure à 0 et inférieure ou égale à 1. Ainsi plus la valeur du BONUS est faible et plus la valeur de Similarité sera prépondérante dans le calcul du degré de similarité, ci-après noté valeur Score, entre deux contacts sources. Des exemples des valeurs du BONUS à appliquer en fonction des types de mots à comparer sont indiqués dans les matrices ci-après, la valeur de BONUS à appliquer est la valeur indiquée en partie droite de chacune des cases des matrices. Pour la mise en oeuvre du précédent mode de réalisation du procédé selon l'invention, on peut faire en sorte que, pour chacune desdites paires de mots Cn, Lp dont le degré de similarité D(cn Lp) entre les chaînes de caractères de ces mots Cn, Lp ne doit pas être utilisé pour l'opération de détermination du paramètre représentatif de degrés de similarité entre ces premier et second contacts sources : on définit un 2nd Terme qui est égal à une valeur de Sélectivité prédéterminée, supérieure à 1 et préférentiellement égale à 1,2 ; et dans lequel - on calcule une valeur SCORE représentative du degré de similarité entre lesdits premier et second contacts sources, ci-après notée valeur Score qui est égale à 1 fois le produit de tous lesdits fers Termes calculés multiplié par le produit de tous les 2nds Termes définis ; et - pour chaque couple de contacts sources, on réitère le calcul d'une valeur SCORE propre à ce couple et représentative du degré de similarité entre les contacts sources de ce couple. Le calcul d'une telle valeur SCORE est un moyen simple de comparer le degré de similarité entre des contacts sources ayant plusieurs champs. Pour la mise en oeuvre du précédent mode de réalisation du procédé selon l'invention, on peut prévoit, pour réaliser l'opération de classement des contacts sources en plusieurs groupes de contacts sources, de : - former un groupe de contacts sources dès lors que la valeur SCORE obtenue pour ces contacts sources est inférieure à une valeur seuil de SCORE prédéterminée, nommée « Cutoff », cette valeur seuil de SCORE étant préférentiellement égale à 1 (Cutoff=l) ; - génèrer, pour chaque groupe formé, un pseudo contact A' en combinant les contacts sources compris dans ce groupe ; sélectionner un contact source isolé ne faisant pas partie d'un groupe de contacts sources et de calculer une valeur SCORE représentative du degré de similarité entre ce contact source isolé et ledit pseudo contact associé au groupe considéré ; - intégrer ce contact source isolé dans le groupe donné si la valeur SCORE calculée avec ce contact source isolé et ledit au moins un pseudo contact est inférieure à une valeur SCORE calculée entre un contact source du groupe donné et ce contact source isolé ; et - regrouper des groupes de contacts sources si on constate qu'il existe une valeur SCORE calculée avec les pseudo contacts de chacun de ces groupes qui est inférieure à une valeur SCORE calculée entre deux contacts sources appartenant chacun à un desdits groupes. Une illustration de l'opération de classement des contacts en plusieurs groupes de contacts sources est donnée au chapitre « STRATEGIE DE CLUSTERING » (le terme Clustering est bien connu du domaine technique et désigne des opérations de classement et regroupement). Il est à noter que, lorsque deux contacts sources ont une valeur de SCORE inférieure au seuil, en l'occurrence inférieure à 1, on dit que ces contacts sources sont rapprochés. Préférentiellement, lorsque l'on veut comparer deux contacts, on balaie les champs du contact qui possède le moins de champs et on essaie de retrouver les similarités avec les champs de l'autre contact qui est comparé. Préférentiellement, dès que l'on modifie un groupe de contacts, on recalcule un pseudo contact représentatif de ce groupe. Après avoir classé les différents contacts sources dans des groupes de contacts, on indique à l'utilisateur la liste des contacts sources appartenant à un même groupe et on lui propose de fusionner ces contacts. La fusion consiste à créer un nouveau contact consolidé en regroupant des informations contenues dans des contacts sources du groupe de contacts qui est présenté à l'utilisateur. Par exemple si un contact source comporte un numéro de téléphone qui n'est pas dans un autre contact source rapproché alors l'utilisateur peut intégrer tous ces numéros de téléphone dans un seul contact consolidé. De même, si deux noms distincts apparaissent dans les contacts sources rapprochés, l'utilisateur pourra décider de créer le contact consolidé en ne retenant qu'un seul des noms ou en retenant un nom reformulé. L'invention facilite la détection de contacts sources constituant potentiellement des doublons et apporte une solution de classement automatisée de ces contacts sources potentiellement doublonnés pour que l'utilisateur puisse les fusionner entre eux sous forme de contacts consolidés. BREVE DESCRIPTION DES DESSINS D'autres caractéristiques et avantages de l'invention ressortiront clairement de la description qui suit, donnée à titre indicatif et nullement limitatif, et faisant référence aux dessins annexés, parmi lesquels: - la figure 1 représente schématiquement deux exemples de carnets d'adresses sources comprenant chacun plusieurs contacts sources et un carnet d'adresses consolidé comprenant plusieurs contacts consolidés fusionnant chacun des informations provenant d'un ou plusieurs contacts sources ; - la figure 2 représente schématiquement les opérations importantes pour la mise en oeuvre du procédé selon l'invention ; la figure 3 représente schématiquement un exemple de matrice de croisements de types de mots présentant les paramètres d'analyse « S » et BONUS à utiliser lorsque l'on veut comparer un mot ayant son propre type (issu d'un premier contact source) avec un mot ayant aussi son propre type (issu d'un second contact source). DESCRIPTION DETAILLEE DE L'INVENTION L'algorithme permettant la mise en oeuvre du procédé est présenté à la figure 2. Il prend en entrée : - la liste des enregistrements du carnet d'adresses centrali- sé BDD à dédoublonner (en l'occurrence cette liste BDD com- prend la liste de contacts sources provenant de plusieurs carnets d'adresses sources 1, 2, n) ; - un jeu de paramètres permettant d'ajuster le fonctionnement et les résultats du rapprochement (cf. le chapitre « DEFINITION ET INFLUENCE DES PARAMETRES). L'algorithme produit en sortie une liste des groupes de contacts qui ont été rapprochés et regroupés en fonction de leurs similarités, dans le but de proposer à l'utilisateur de fusionner, conserver tel quel ou supprimer lesdits contacts de chaque groupe. Les différentes étapes de l'algorithme sont présentées ci-après. 'Constitution du corpus L'algorithme constitue le corpus en une passe. Ce corpus consiste en : Une liste de « mots », de type dictionnaire, où le mot (au sens chaîne de caractères) indexe un jeton (aussi nommé « token »), qui est essentiellement une chaîne de caractères dotée d'un type (mail, téléphone, prénom, etc.), et qui contient aussi d'autres informations liées au corpus, telles que fréquence d'apparition et pointeurs vers les enregistrements (ou les contacts sources) où il 35 apparaît, et des informations caractéristiques telles que 30 le jeu de caractères constitutif. Un arbre comportant une racine, des noeuds et des branches sur lesquels sont répartis ces mots. Chaque noeud contient une liste de mots qui ont en commun le jeu de caractères qui les constitue. La relation parent - descendant dans l'arbre est une inclusion stricte du jeu de caractères. De la sorte, les mots d'un même noeud sont de bons candidats pour les fautes de frappe (lettres répétées, inversions), et plus généralement, on trouve verticalement une majorité des candidats similaires, que ce soit au sens de la faute de frappe ou de l'abréviation. Il faut retenir que cet arbre a la propriété de naturellement classer les mots de manière à éviter les comparaisons superflues. IPré trai temen t Pour chaque champ de chaque enregistrement (c'est-à-dire chaque champ de chaque contact source), on effectue les traitements suivants . 1 normaliser les caractères (s'assurer du bon encodage, imposer la casse minuscule, enlever les délimiteurs inutiles du champ). Par exemple " Chombier, Gérard " devient chombier, gerard (sans les guillemets, sans les espaces du début et de la fin, sans les accents) ; 2 idem pour le type supposé du lorsqu'on importe un fichier de champ qu'on importe (utile contacts quelconque tel un (les fichiers csv fichier csv connus : le colonne) ; 3 analyser le champ pour motifs caractéristiques ont des formats de contacts du champ est l'intitulé de la y détecter de manière ad-hoc certains de types bien identifiés. Ces tests type supposé sont exclusifs (on s'arrête au premier type détecté, car on considère qu'il y a peu d'informations à perdre et un facteur d'accélération non négligeable à gagner) et effectués dans l'ordre suivant : a mail (extraction d'informations annexes), b téléphone (dont mobile), c adresse (code postal / adresse générique), d url (site perso), e date (anniversaire), f autres (noms) ; 4 fusion du type détecté (précédemment) avec le type supposé (fourni à l'import du contact source) ; 5 import dans le corpus du ou des mots (tokens typés) ainsi extraits. On s'est aperçu que l'analyse concernant l'url et la date peut être succincte car statistiquement ces champs sont peu efficaces pour effectuer des rapprochements. Ainsi, on a peu à perdre en ne mettant pas en oeuvre leur détection exhaustive. Normalisation On effectue les traitements suivants : 1 encodage en UTF-8 (UTF-8 est une norme de caractères connue), 2 conversion de la casse (tout en minuscules), 3 suppression des espaces et guillemets au début et à la fin du champ, 4 conversion des caractères accentués en caractères non- accentués. Extraction d'un mail A base d'une expression régulière, on reconnaît exhaustivement toute adresse mail bien formée. Ensuite, on en extrait : - les mots constitutifs du nom de domaine (pour utilisateur@sfr.com, sfr sera extrait) qui sont ajoutés au corpus. Dans le cas où le nom de domaine est considéré comme non pertinent pour le rapprochement, il n'est pas ajouté au corpus ou en sera éliminé ultérieurement (voir ci-après l'élimination des occurrences) ; - le(s) nom(s) supposés du propriétaire de l'adresse mail (utilisateur dans l'exemple précédent). Extraction d'un numéro de téléphone A base d'une expression régulière, on reconnaît de manière ad hoc connue en elle-même tout numéro de téléphone français, avec préfixe international ou non, sous diverses mises en forme courantes. Dans le cas d'un numéro de téléphone commençant par (0)6 ou (0)7, on reconnaît un téléphone mobile français. Extraction d'une adresse A base d'une expression régulière, on reconnaît et extrait les codes postaux à 5 chiffres. Tout champ contenant un tel code postal est considéré comme une adresse. Extraction d'une url De préférence, cette extraction n'est pas utilisée pour le cas général. Extraction d'une date De préférence, cette extraction n'est pas utilisée pour le cas général. Extraction de champs quelconques Cette extraction ayant lieu en dernier, on sait que le champ ne contient aucun des motifs précédents. On peut avantageusement appliquer une stratégie peu coûteuse, consistant à : - compter le nombre de mots, si l'on découpait la chaîne de caractères de manière standard (caractères non alphabétiques et quelques cas particuliers, tels les tirets), - si ce nombre est inférieur à un certain seuil (« too many words » signifiant trop de mots), considérer que le champ contient des « noms » et les extraire (en découpant), - sinon, importer le champ en entier sans le découper, avec un type « quelconque ». Pré-typage des mots On peut accorder une certaine confiance au typage antérieur des champs que l'on importe. Une stratégie paramétrable simple est : - utiliser une liste blanche de champs. Leur type est importé sans détection, leur contenu traité de manière minimale (normalisation et découpage des mots) ; - sinon, détecter le type du champ (extractions comme vues précédemment), puis fusionner les deux informations de la manière suivante : - si le typage antérieur est dans la même catégorie que le typage détecté, prendre le plus « fin » des deux au sens de la confiance (cet ordre est celui donné pour les paramètres implicites à la fin du document), - sinon, appliquer le typage détecté si on lui fait suffisamment confiance (tout sauf les noms « quelconques », voir plus haut), - enfin dégrader le typage en « quelconque » (maybe some name ou something suivant le cas) si l'on n'a pas résolu le conflit ou trouvé de type. Création des mots Les « mots » du corpus sont de petites structures contenant dif- férentes informations que l'on calcule à leur création, et que l'on modifie très peu par la suite, ce qui permet d'accélérer les comparaisons . - chaîne de caractères (le mot proprement dit, par exemple «arma»), - taille du mot (ici 4) - type du mot (par exemple « SOME EXTRACTED NAME » s'il provient d'un mail), - fréquence du mot dans le corpus, c'est-à-dire le nombre de contacts où il apparaît, - le jeu de caractères constitutifs (ici « an » soit deux caractères uniques), - une tolérance fonction de la taille, approximée par le tiers de la taille du mot (ici 1). En effet, plus le mot est court, moins cela a d'intérêt de calculer sa distance au-delà du seuil de tolérance. On notera que le prétraitement et la constitution du dictionnaire se font au fur et à mesure (champ par champ sur les enregistrements), en une passe. 'Import dans le corpus Les prétraitements précédents prennent en entrée un champ d'enregistrement (champ d'un contact source contenant une chaîne de caractères) et renvoient une liste de « mots », à savoir des tokens (ou jetons) typés contenant une chaîne de caractères et des informations additionnelles. Le corpus maintient une simple liste de mots (dictionnaire) et une structure plus complexe (arbre). Gestion des mots dupliqués et de leur type La liste simple sert essentiellement à calculer la fréquence d'un mot. Toute chaîne de caractères exactement dupliquée de-vient donc partagée par les contacts sources concernés. On a choisi de ne pas admettre de types multiples pour les mots (pour des raisons de rapidité et de limitation de l'empreinte mémoire), il convient donc d'implémenter une stratégie de fusion, quand un même mot apparaît dans deux contacts différents (ou le même contact parfois), avec des types différents. Le compromis résulte d'une simple comparaison au moyen d'une technique semblable à celle utilisée pour la fusion des types issus du prétraitement (type détecté versus type supposé), à une différence près : en cas de conflit au sein de la même catégorie, on n'affine pas, mais on dégrade. Ainsi, un même mot détecté en tant que prénom et en tant que nom (exemple : Matthieu) deviendra un nom quelconque (some name). Un même mot détecté en tant qu'adresse et en tant que prénom (exemple : France) devien- dra une adresse quelconque avec une confiance encore moindre (maybe some address). Autrement dit : - Si même catégorie mais type différent, on dégrade en some category, - Si catégories différentes, on dégrade en maybe some category (catégorie la plus précise). On pour-rait prendre le parti inverse et dégrader en la catégorie la moins précise, voire traiter au cas par cas (le cas général, comme pour la fusion précédente, serait une matrice). Nettoyage du corpus On dispose de deux leviers supplémentaires pour diminuer la combinatoire des comparaisons : - enlever les mots trop fréquents, car considérés comme non pertinents ; - enlever les mots dont les types sont considérés comme non pertinents. On effectue ce nettoyage a posteriori, ce qui coûte un peu plus cher en temps que de le faire au fur et à mesure, mais permet de détecter des occurrences multiples à travers la fusion des types : sfr.com sera détecté comme nom de domaine, et importé bien que destiné à être effacé plus tard. Grâce à cela, les occurrences de sfr en tant que nom de société seront nettoyées aussi (par le biais du type ou de la fréquence). Paramètres . - fonction de seuillage = min(freqMin, nContacts) + freqCoeff * nContacts freqPow - types ignorés dans la MAGIC MATRIX, à savoir les types dont la tolérance est 0 avec eux-mêmes (diagonale de la ma- trice). Insertion dans l'arbre Chaque mot est inséré dans l'arbre à la place qui lui convient. La racine de l'arbre a pour jeu de caractères tous les caractères disponibles. Chaque noeud descendant en a un sous-ensemble strict et contient les mots constitués de ces caractères. Afin d'accélérer l'insertion dans l'arbre en supprimant toute manipulation de sa structure, on préclasse le corpus après son nettoyage au moyen d'un « quicksort » (optimal) - c'est-à-dire une fonction de classement rapide bien connue - utilisant comme fonction de comparaison la taille du jeu de caractères constitutif du mot. A titre d'illustration est décrit ci-après un arbre généré à partir d'une série de chaînes de caractères appartenant à différents mots : anna, anh, nguyen, dom, domicile, dominique. Pour chaque chaîne de caractères d'un mot donné on génère un jeu de caractères utilisés pour former ce mot. Le jeu de caractères est généré de manière qu'un caractère apparaissant plusieurs fois dans la chaîne de caractères d'un mot ne soit mentionné qu'une seule fois dans le jeu de caractères correspondant. Ainsi, pour l'exemple précédent on obtient les jeux de caractères inscrits entre parenthèses après chacune des chaînes de caractères correspondantes : anna (an), anh (ahn), hanna (ahn), nguyen (egnuy), dom (dmo), domicile (cdeilmo), dominique (deimnoqu), dominiquecollin (cdeilmnoqu). On préclasse les mots par ordre décroissant de la taille de ce jeu de caractères et on obtient la liste des jeux mentionnés ci-après entre parenthèses : dominiquecollin (cdeilmnoqu), dominique (deimnoqu), domicile (cdeilmo), nguyen (egnuy), dom (dmo), hanna (ahn), anh (ahn), anna (an). On génère le noeud racine de l'arbre contenant tous les caractères de tous les jeux de caractères ainsi obtenus. Ensuite, on insère les mots dans l'arbre au moyen d'une fonction récursive, qui descend dans l'arbre en prenant un chemin parmi les noeuds ayant un jeu de caractères incluant les jeux de caractères de la chaîne de caractères du mot. Enfin, s'il n'y a pas équivalence stricte, on crée un noeud fils ayant le bon jeu de caractères. Par cette méthode, on obtient l'arbre ci-après : Noeud Racine (tous les caractères, aucun mot, fils: cdeilmnoqu, egnuy, ahn) Noeud cdeilmnoqu (cdeilmnoqu, mots: dominiquecollin, fils: cdeilmo, deimnoqu) Noeud deimnoqu (deimnoqu, mots: dominique, fils: dom) Noeud cdeilmo (cdeilmo, mots: domicile, fils: dom) Noeud egnuy (egnuy, mots: nguyen, fils: aucun) Noeud dmo (dmo, mots: dom, fils: aucun) Noeud ahn (ahn, mots: hanna, ahn, fils: an) Noeud an (an, mots: anna, fils: aucun) Il est à noter qu'il existe un code connu sous le terme « WordTree » dans le domaine du classement et de la génération d'arbres. Ce code de la classe « WordTree » peut ainsi être utilisé pour générer un arbre dans le procédé selon l'invention. La fonction récursive de construction de l'arbre est également connue sous le nom de « addWord ». Temps d'exécution Le temps d'insertion et de suppression dépend de la profondeur de l'arbre (insertion récursive à partir de la racine), donc de la variété de mots du corpus, et suivant leur ordre d'insertion, on réalise plus ou moins d'opérations de réorganisation de l'arbre. Le coefficient dépend donc fortement du corpus, mais on est en O(NlogN) où N est le nombre de mots. Expérimentalement, on gagne un facteur d'au moins 2 sur le coefficient en effectuant le nettoyage et le préclassement au lieu d'insérer dans l'arbre au fur et à mesure de la constitution du dictionnaire (et de plus on n'effectue aucune opération de suppression dans l'arbre au cours du nettoyage). 'Parcours de l'espace des distances mot à mot Une fois le corpus précédent constitué, on a « gratuitement » tous les rapprochements potentiels dus aux mots exactement dupliqués. Il nous reste à rapprocher les mots de manière approximative. On obtient un gain d'ordre de grandeur, à savoir O(NlogN) avec un petit coefficient au lieu de 0 (N2) et un coef- ficient en ne comparant que les mots qui se ressemblent au sens de la distance ou similarité utilisée. Distance / similarité entre mots Les cas triviaux des doublons exacts ont été traités : les chaînes de caractères sont différentes. Chaque mot connaît sa tolérance. La tolérance d'un mot est fonction de sa taille, comme on l'a expliqu » précédemment, d'après des paramètres explicites codés en dur. La plus petite tolérance commune donne un seuil pour la distance à calculer entre les deux mots. On a déjà détecté tous les mots exactement dupliqués, il ne reste plus que des mots différents (mais potentiellement semblables). On propose d'utiliser une distance hybride D, utilisant la mé- thode de Levenshtein (de mise en oeuvre standard et aux bonnes performances) dans les cas où l'on n'aura pas trivialement ac- cepté ou rejeté la similarité : - si les mots ont des types non comparables, ou des types ne tolérant que le rapprochement exact, on rejette la similarité ; - si les mots ont des tailles trop différentes, ils sont considérés comme différents, à moins que le plus petit ne soit inclus dans le plus grand (abréviation potentielle). Le plus petit mot appartient donc nécessairement à un noeud descendant du noeud auquel appartient le mot long ; - si les mots ont des tailles similaires, la méthode de Levenshtein mesure très rapidement le nombre d'opérations d'édition nécessaires pour les faire correspondre. Les fautes de frappe sont essentiellement des inversions de lettres, des suppressions et des insertions, les mots appartiennent donc soit au même noeud de l'arbre, soit sont proches parents. On vérifie donc que l'arbre couvre tous les candidats au sens de la distance tout en faisant baisser la combinatoire aux seuls noeuds ayant une relation de descendance. En sortie, on obtient : - similarité de 0 pour deux mots considérés comme différents, - similarité de 1 (arbitraire) pour deux mots dont l'un est strictement inclus dans l'autre (abréviation potentielle), - similarité calculée en fonction de la distance d de 2 (tolérance - d + 0.5) / tolérance, sachant que d est au minimum égal à 1 (les mots sont différents). Cette similarité converge vers 2 (limite pour des mots identiques dans la présente métrique). Espace des liens entre mots En parcourant récursivement l'arbre, on teste tous les candidats possibles, et l'on finit de constituer l'espace des rapprochements de mots, contenant les enregistrements suivants : - mot exactement dupliqué dans le corpus = valeur seuil de similarité (2), - mati_ rapproché du mot2 = valeur de similarité fournie par la fonction distance (strictement inférieure à 2 mais convergeant vers 2). Ce faisant, on a constitué également l'espace des rapprochements potentiels entre enregistrements, car chaque mot connaît les contacts où il apparaît. En résumé . - On itère sur les enregistrements à importer, o on itère sur les champs, ^ pour chaque champ hors liste noire, on effectue un certain nombre de prétraitements (normalisation, typage), ^ on crée les tokens lui correspondant, - en les insérant dans le dictionnaire, on traite les occurrences multiples (conflits de types, fréquence d'apparition), o donc on enrichit la liste des dou- blons potentiels parmi les enregis- trements (qui partagent des mots identiques) - On nettoie le corpus (pour l'instant limité au dictionnaire), - On constitue l'arbre des mots pour ce corpus nettoyé et classé, - On parcourt l'arbre des mots pour compléter la liste des doublons potentiels avec les paires d'enregistrements partageant des mots similaires. Rapprochement des enregistrements contacts sources par paires par calcul de SCORE 25 30 35 De manière générale, on a maintenant pour chaque paire potentielle de contacts sources, deux vecteurs à comparer, dans l'espace des liens entre mots. De cette comparaison, on attend les résutats suivants : - identifier les inclusions strictes, - classer les autres cas non triviaux suivant la probabilité qu'il s'agisse d'un doublon. On démontre de manière immédiate que le score d'un tel rapprochement ne peut être une distance (B inclus dans A = distance AB nulle, C inclus dans A = distance AC nulle, et distance BC non nulle si ce sont des sous-ensembles disjoints de A). On utilise alors l'algorithme de calcul de score ad-hoc suivant . - identifier le contact source ayant le plus petit nombre de champs et initialiser le score à 1. On va maintenant itérer sur cette liste de champs ; - ceux d'entre eux ayant un rapprochement avec une chaîne de caractères d'un champ dans l'autre contact source ont déjà été précalculés. Multiplier le score par une valeur bonus inférieure à 1, dépendant de l'exactitude du rapprochement et du type du mot ; le bonus est élevé à la puissance similarité précédemment calculée. - pour les autres champs (sans rapprochement), multiplier le score par une valeur handicap (i.e. sélectivité de 1,2) supérieure à 1 ; - s'il n'y a que des rapprochements exacts, le score vaut 0 (inclusion totale). On a les propriétés attendues de séparation pour un coût de cal-cul quasi nul (tous les rapprochements ont été précalculés). Le calcul du SCORE c'est-à-dire du paramètre représentatif de la distance entre deux contacts est réalisé selon les formules présentées à la figure 3 et avec les paramètres d'analyse prédéterminés présentés dans la matrice de la figure 3 (donnée à titre d'exemple général) ou plus précisément présentés dans la matrice détaillée donnée au chapitre ci-après « Jeux de paramètres par défaut fournis par la matrice de croisement de types ». Des paramètres d'analyse prédéterminés de comparaison de mots sont ici classés dans une matrice. Sur la même ligne supérieure de la matrice sont listés plusieurs types des mots connus pouvant être rencontrés, en l'occurrence il s'agit d'informations de typage utilisées pour typer des mots. Sur la même colonne de gauche de la matrice sont listées les mêmes informations de typage de mots que celles listées à la ligne supérieure de la matrice. Chaque ligne de la matrice croise une colonne de la matrice et forme une case d'intersection ligne - colonne. Dans chaque case donnée de la matrice sont indiquées des données d'analyse prédéterminée ou facteurs à prendre en compte pour comparer une chaîne de caractères d'un mot ayant un type donné (indiqué dans la colonne) avec une autre chaîne de caractères d'un autre mot ayant un type donné (indiqué sur la ligne). En l'occurrence on utilise selon le procédé deux types de facteurs prédéterminés pour comparer des chaînes de caractères de différents mots : le paramètre d'analyse prédéterminé S apparaissant à gauche dans chaque case de matrice et le paramètre prédéterminé BONUS apparaissant à droite dans chaque case de la matrice. On compare les chaînes de caractères de deux mots s'il est mentionné dans la case correspondante de la matrice que S = 1 ou 2. Si la valeur S = 0, alors on ne compare pas les chaînes de caractères de ces mots car leurs types respectifs ne l'autorisent pas. Pour définir la valeur SCORE entre deux contacts sources A et B, on utilise la méthode suivante conforme aux formules de la figure 3. Contact Contact 1' Terme 2°d Terme source A source B «Utilisate « On ne le calcule pas car N'ayant pas de ur» type Papa» « utilisateur » est différent premier terme, Nom type nom on génère terme de « papa » et car la valeur le 2nd « S » de de 2 = à une pas de sont le la matrice est signifiant qu'on ne calcule sélectivité le 1er terme si les champs 1,2 (il s'agit non similaires d'une constante cas (ce qui est puise « utilisateur » ne donnée ressemble pas à « papa ». « Pierre » Pas de comparaison possible N'ayant pas de type entre les chaînes -> on ne on Prénom 2nd = de 1er terme génère le terme calcule pas le 1er terme similarité 1,2 « (0) 6 18 « (0) 6 xx On calcule le premier » de terme car on ne génère pas xx xx xx » la la matrice de 2nd Terme car est qu'on ne on a réussi à 1er terme 1' champs sont 18 xx valeur « S xx » type de 1 signifiant téléphone portable type calcule pas le calculer le téléphon uniquement les si Terme. e exacts, ce qui est ici le cas. Pas de second portable puissance 2 terme. 1' terme =0.82(la correspond à la similarité qui est de 2 puisque les chaînes sont identiques) « utilisa- « utili- La matrice permet de trouver teur@sfr.c sa « S om » teur@sfr type adresse mail »= 1 pour des types adresse .com » mail croisés. On calcule donc type ce ler terme adresse des contacts mail car les chaînes A et B sont identiques. 1' terme = Bonus de 0.8 2 On calcule donc le SCORE entre les contacts A et B en multipliant les ter et 2nd Termes calculés précédemment et on obtient : SCORE de A et B = 1.2*1.2*0.82*0.82 = 0,5898 'Stratégie de regroupement des contacts source : clustering I A partir des valeurs SCORE calculées selon la méthode du chapitre précédent (rapprochements d'enregistrements), il faut créer des groupements de contacts, avec la propriété que chaque contact apparaît dans au plus un groupe (et que les groupes gardent une taille raisonnable, c'est-à-dire restent discriminants). L'algorithme proposé effectue cette classification en une seule passe, avec pour avantage la rapidité, mais est en fait la version dégradée de l'algorithme générique récursif, qui traite chaque groupe créé comme un nouveau contact (on recalcule alors tous les rapprochements potentiels sur la nouvelle liste de contacts). Le principe en est : - deux contacts rapprochés n'appartenant pas déjà à un groupe forment un nouveau groupe ; - lorsque l'un des deux appartient déjà à un groupe, le contact isolé ne rejoint le groupe que si sa distance au groupe est inférieure à sa distance au contact seul ; - lorsque les contacts appartiennent à deux groupes différents, on fusionne les groupes seulement si la distance entre groupes est inférieure à la distance entre les contacts pris isolément. Ainsi en partant de l'exemple donné au tableau précédent où l'on avait le SCORE entre les contacts A et B égal à 0.58, et par conséquent inférieur à la valeur de Cutoff de 1. On considère que ces contacts sources A et B sont similaires et doivent être regroupés dans un même groupe. Ces contacts A et B sont effectivement similaires car les numéros de téléphones et adresses de courriel sont les mêmes. On regroupe donc ces contacts dans un même groupe pour que l'utilisateur puisse décider s'il fusionne ou non ces contacts pour générer un contact consolidé. A la création de ce groupe, on génère un pseudo contact A' à l'aide des contacts A et B, le pseudo contact fusionnant ces contacts A et B. On utilisera alors ce pseudo contact pour calculer le SCORE entre le groupe comprenant A et B et un autre contact isolé C ou un éventuel autre pseudo contact représentant un autre groupe de contacts. En fonction des valeurs de SCORE on va par itération regrouper des contacts dans des groupes en fonction de leurs degrés de similarité. Définition et Influence des paramètres Paramètres explicites Valeurs par défaut too short = 2 (trop court) Limite inférieure de la taille des mots (en caractères). A par-tir de ce seuil, on ignore, car non significatif. Toujours appliqué ! too many words = 5 (trop de mots) Limite supérieure au découpage des champs en mots. A partir de ce seuil, on ne découpe pas en mots, on importe la chaîne de caractères telle quelle. Permet d'approximativement distinguer les noms des champs non identifiés, et évite l'explosion combinatoire. Selectivity = 1.2 (valeur de Sélectivité) Handicap pour un mot non rapproché : c'est bien la sélectivité de l'algorithme. Cutoff = 1 (Seuil de coupure) Seuil pour le score de pseudo-distance au-delà duquel on ignore 30 le rapprochement. trustedTypes (Type de confiance) Liste blanche des types de confiance (on importe le contenu directement) ignoredTypes (Type ignoré) Liste noire des types dont on n'importe pas le contenu. Essentiellement utilisé pour des raisons techniques (champs internes dont le contenu généré n'apporte aucune information). freqPow = 0.6 Puissance de la fonction seuil de nettoyage en fonction de la fréquence d'apparition du mot dans le corpus. fregCoeff = 1.0 Coefficient linéaire pour cette même fonction. freqMin = 6.0 Coefficient constant pour cette même fonction. Matrice de paramètres d'analyse prédéterminés Table de croisement des types. A chaque intersection, on donne deux valeurs . - Le paramètre d'analyse « S » est égal à : - 0 pour deux types non comparables, - 1 si l'on exige une correspondance exacte (mot dupliqué). - 2 si l'on accepte un flou (variable en fonction de la taille des mots puisque chaque mot connaît sa tolérance en termes de distance maximale). - le bonus (sensibilité de l'algorithme) calcul réduit) tout en fournissant des résultats intéressants notamment grâce : - aux prétraitements (essentiellement le typage et l'extraction automatique des noms à partir du mail), - au traitement des types et fusion des types multiples (gar- der some name en ignorant maybe some name permet des rap- prochements fins avec la stratégie de fusion adoptée), - au poids important mais non démesuré (0.4 et non 0) accordé à certaines valeurs (téléphone mobile). too short too_many_words selectivity cutoff freqMin freqCoeff freqPow some personal website some domain some personal mail some work mail some mail some mobile phone some personal phone some work phone some fax some phone some birthday some date some zip code some home address some work address some address some last name some first name some extracted name some name maybe some name maybe some birthday maybe some address maybe some mail maybe some phone maybe some url something Bien entendu, l'invention n'est pas limitée au mode de mise en oeuvre décrit mais englobe toute variante entrant dans le champ de l'invention telle que définie par les revendications. 2 5 1.2 0.95 6 1.0 0.6 REVENDICATIONS1) Procédé de génération d'un carnet d'adresses consolidé comportant plusieurs contacts consolidés, le procédé comprenant : - l'obtention et la mémorisation de carnets d'adresses sources provenant de sources distinctes, chacun de ces carnets d'adresses sources comportant plusieurs contacts sources, chacun desdits contacts sources ou consolidés comportant plusieurs champs chacun formé de caractères et certains au moins de ces champs étant associés à une information de typage de champ ; - la détermination et la mémorisation d'une liste de mots à partir de chacun des carnets d'adresses sources, chaque dit mot comportant : - une chaîne de caractères déterminée à partir d'une chaîne de caractères d'un champ donné d'un contact source donné ; et - une information de typage du mot ; le procédé comportant en outre : une opération de détermination et de mémorisation de paramètres représentatifs de degrés de similarité entre certaines au moins des chaînes de caractères de certains au moins des mots de la liste de mots ; et - une opération de détermination et de mémorisation de paramètres représentatifs de degrés de similarité entre des contacts sources en fonction desdits degrés de similarité entre mots ; - une opération de classement des contacts source en plusieurs groupes de contacts sources, chaque contact source classé étant classé dans un seul des groupes en utilisant les paramètres représentatifs des degrés de similarité entre les contacts sources ; - une opération de fusion de contacts sources consistant àgénérer un contact consolidé à partir d'au moins deux contacts sources classés dans un même groupe de contacts sources. 2) Procédé de génération d'un carnet d'adresses consolidé selon la revendication 1, dans lequel à chaque mot on associe au moins un pointeur, chaque pointeur désignant un contact source à partir duquel le mot a été déterminé. 3) Procédé de génération d'un carnet d'adresses consolidé selon la revendication 1, dans lequel pour déterminer chaque mot on analyse une chaîne de caractères d'un champ d'un contact source et en fonction de paramètres d'analyse prédéterminés on détermine une information de typage associée à cette chaîne de caractères du contact source puis en fonction de cette information de typage et selon les paramètres d'analyse prédéterminés on génère une chaîne de caractères du mot qui est soit identique à la chaîne de caractère du champ du contact source soit normalisée selon des paramètres de normalisation prédéterminés. 4) Procédé de génération d'un carnet d'adresses consolidé selon la revendication 3, dans lequel chaque chaîne de caractères de chaque mot est normalisée de manière que : - les caractères composant cette chaîne aient un seul type de casse, préférentiellement une casse minuscule ; et/ou - des caractères de délimitation de cette chaîne soient supprimés ; et/ou - que chaque caractère accentué de cette chaîne soit remplacé par un caractère correspondant non accentué. 5) Procédé de génération d'un carnet d'adresses consolidé selon l'une quelconque des revendications précédentes, dans lequel l'information de typage d'un mot est déterminée : - en fonction de l'information de typage du champ ducontact source qui a servi pour déterminer le mot ; et/ou en fonction d'une détection selon des paramètres d'analyse prédéterminés de la chaîne de caractères ayant servie à déterminer ce mot et/ou de la chaîne de caractères constituant ce mot. 6) Procédé de génération d'un carnet d'adresses selon l'une quelconque des revendications précédentes, dans lequel : - on crée un arbre de classement comprenant une racine portant des branches, chacune des branches étant soit portée par un même noeud de la racine, soit portée par un noeud d'une autre branche, l'ensemble des mots étant classés dans l'arbre de manière que chaque noeud porte uniquement les mots dont les chaînes de caractères sont strictement composées d'un même jeu de caractères et de manière que chaque noeud enfant porte uniquement les mots composés d'un jeu de caractères formant un sous-ensemble strict du jeu de caractères des mots portés par le noeud parent ; et - on détermine des familles de mots chacune strictement constituée par les seuls mots portés par un noeud enfant et le ou les noeuds parents placés entre le noeud enfant et le noeud racine ; et - on réalise ladite détermination et de mémorisation de paramètres représentatifs de degrés de similarité entre certaines au moins des chaînes de caractères de certains au moins des mots de la liste de mots uniquement pour les chaînes de caractères appartenant à des mots d'une même famille. 7) Procédé de génération d'un carnet d'adresses selon la revendication précédente, dans lequel pour créer l'arbre de classement, on associe à chaque mot : - une information de nombre de caractères présents dans la chaîne de caractères de ce mot ; et - une information de jeu de caractères regroupant le jeu decaractères composant la chaîne de caractères du mot. 8) Procédé de génération d'un carnet d'adresses selon l'une quelconque des revendications précédentes, dans lequel pour réaliser l'opération de détermination et de mémorisation de paramètres représentatifs de degrés de similarité entre certaines au moins des chaînes de caractères de certains au moins des mots de la liste de mots, on mesure ladite similarité entre les chaînes de caractères à l'aide de la méthode de Levenshtein. 9) Procédé de génération d'un carnet d'adresses selon l'une quelconque des revendications précédentes, dans lequel pour déterminer les paramètres représentatifs de degrés de similarité entre des contacts source : - on sélectionne un premier contact source lié à un premier groupe de mots déterminés à partir de ce premier contact source ; et - on sélectionne un second contact source lié à un second groupe de mots déterminés à partir de ce second contact source - on définit des paires de mots chacune constituée d'un mot du premier groupe de mots et d'un mot du second groupe de mots ; - on vérifie, à l'aide de paramètres d'analyse prédéterminés (S), et pour chacune des paires de mots ainsi définies si l'on doit ou non utiliser le degré de similarité entre les chaînes de caractères des mots de la paire pour l'opération de détermination du paramètre représentatif de degrés de similarité entre ces premier et second contacts sources. 10) Procédé de génération d'un carnet d'adresses selon les revendications 8 et 9, dans lequel pour chacune desdites paires de mots (Cn, Lp) dont le degré de similarité(D(cn,Lp)) entre les chaînes de caractères de ces mots (Cn, Lp) DOIT ETRE utilisé pour l'opération de détermination du paramètre représentatif de degrés de similarité entre ces premier et second contacts sources, on calcule un premier terme propre à cette paire de mots selon la formule : ter Terme = (BONUS (cn L) similarité p) et dans laquelle : - le BONUS est une valeur prédéterminée et fonction des informations de typage des mots (Cn, Lp) dont les chaînes de mots sont comparées ; et - la Similarité = 2 * (tolérance - D(cn Lp) + 0.5) / tolérance sachant que : - la tolérance est égale au tiers du nombre de ca- ractères, arrondi au nombre entier immédiatement inférieur, de la chaîne de caractères la plus courte entre les chaînes de caractères de la paire de mots ; et que - D (cn,Lp) est la distance de Levenshtein calculée entre les chaînes de caractères de la paire de mots (Cn, Lp) . 11) Procédé de génération d'un carnet d'adresses selon la revendication 10, dans lequel : - pour chacune desdites paires de mots (Cn, Lp) dont le degré de similarité (D(cn Lp)) entre les chaînes de caractères de ces mots (Cn, Lp) NE DOIT PAS être utilisé pour l'opération de détermination du paramètre représentatif de degrés de similarité entre ces premier et second contacts sources, on définit un 2nd Terme qui est égal à une valeur de Sélectivité prédéterminée, supérieure à 1 et préférentiellement égale à 1,2 ; et dans lequel - on calcule une valeur SCORE représentative du degré de similarité entre lesdits premier et second contacts sources, ci-après noté valeur Score, en utilisant la formule :SCORE = 1 fois le produit de tous lesdits 'ers Termes calculés fois le produit de tous les 2nds Termes définis ; et - pour tout couple de contacts sources donné on réitère le calcul d'une valeur SCORE propre à ce couple et représentative du degré de similarité entre les contacts source de ce couple donné. 12) Procédé génération d'un carnet d'adresses selon la revendication 11, dans lequel, pour réaliser l'opération de classement des contacts sources en plusieurs groupes de contacts sources . - on forme un groupe de contacts sources donné dès lors que la valeur SCORE obtenue pour ces contacts sources donnés est inférieure à une valeur seuil de SCORE prédéterminée (Cutoff), cette valeur seuil de SCORE étant préférentiellement égale à 1 (Cutoff=l) ; - pour chaque groupe formé on génère un pseudo contact (A') en combinant les contacts sources compris dans ce groupe ; - on sélectionne un contact source isolé ne faisant pas partie d'un groupe de contacts sources et on calcule une valeur SCORE représentative du degré de similarité entre ce contact source isolé et ledit pseudo contact associé à un groupe donné ; - si la valeur SCORE calculée avec ce contact source isolé et ledit au moins un pseudo contact associé à un groupe donné est inférieure une valeur SCORE calculée entre un contact source du groupe donné et ce contact source isolé, alors ce contact source isolé est intégré dans le groupe donné ; et - on regroupe des groupes donnés de contacts sources si on constate qu'il existe une valeur SCORE calculée avec les pseudo contacts de chacun de ces groupes donnés qui est inférieure à une valeur SCORE calculée entre deux contacts sources sélectionnés dans ces groupes donnés de contacts 42sources respectifs.