Brevet FR2899708A1 — publié le 20071012

PROCEDE DE DE-DOUBLONNAGE RAPIDE D'UN ENSEMBLE DE DOCUMENTS OU D'UN ENSEMBLE DE DONNEES CONTENUES DANS UN FICHIER La présente invention concerne notamment un procédé de dédoublonnage rapide d'un ensemble de documents contenus dans une base de données. Elle s'applique aussi à un ensemble de données contenues dans un fichier. Ces données peuvent être de tout type, telles que des données lo multimédia, des données numériques, etc. Elle fait notamment partie des techniques de traitement automatique de l'information textuelle et peut être utilisée dans les chaînes de traite-ment de flux documentaires. Le problème technique posé est d'être capable de retrouver des 15 documents ou des données identiques avec un certain pourcentage de ressemblance dans une base de données ou dans un fichier de taille importante. Par exemple, dans le cas d'une grande base de données textuelles, ce problème se décompose en deux sous-problèmes : 1) dans une base de documents existante, il faut trouver l'ensemble des do- 20 cuments similaires, avec un taux de similarité fixé par l'utilisateur, 2) pour un document à insérer dans une base de données, on doit être capable de trouver tous les documents similaires (à un taux de similarité fixé) parmi l'ensemble des documents constituant l'historique. Par exemple, dans un flux documentaire, comparer un nouveau document aux documents plus 25 anciens pour détecter s'il d'agit ou non d'une reprise de l'information. Ce traitement est nécessaire dans toute chaîne de traitement textuel car les documents dupliqués entraînent un biais important dans toutes les analy- ses futures, par exemple la classification automatique, les tableaux de contingences, les croisements OLAP ou procédé analytique en ligne (abrégé anglo-saxon de On Line Analytical Process). Par biais , on peut entendre dans la présente invention, un poids surévalué donné aux textes en s question, au niveau de l'importance d'une thématique à laquelle ces textes peuvent se référer ou inversement, une sur-représentation de leurs vocabulaires descriptifs dans l'univers du vocabulaire global décrivant le corpus . Il existe des méthodes dites naïves qui consistent à comparer tous les documents deux à deux et à leur appliquer une mesure de similarité pour ~o détecter s'il s'agit d'une copie ou non. Ces méthodes nécessitent des puissances de calcul très importantes (puisqu'elles ont un nombre d'itérations proportionnel à N2). Ainsi, une base de 10.000 documents nécessite 100 mil-lions de comparaisons, rendant ces approches inutilisables de manière industrielle et opérationnelle. 15 L'art antérieur divulgue différentes méthodes de dé-doublonnage fonctionnant sur des bases de données relationnelles, parmi lesquelles on peut citer les deux demandes de brevets : US 2004 0220955 Information Processing System And Method de Kevin MCKEE et US 2005 0182780 de George H. FORMAN et al. 20 La demande de brevet US 2004 0039933 divulgue un procédé de dé-doublonnage avec une fonction de hachage MD5. Une telle approche n'est toutefois pas performante. En effet, il suffit d'un simple espace présent en plus dans un des documents comparés, pour que ce dernier soit considéré comme différent des documents de la base. De plus, il n'est pas expliqué 25 comment rechercher une clé rapidement parmi une grande liste de clés. En ce qui concerne les approches utilisant une base de connaissances, elles fonctionnent uniquement sur la langue de la base et dépendent de la richesse de celle-ci. Ces méthodes donneront des résultats approximatifs et même inexacts si la base n'est pas complète ou si elle ne prend pas en compte le vocabulaire spécifique à un métier. Ces approches déportent toute la complexité du problème sur la base de connaissances et nécessitent une base par langue. La plupart des solutions de dé-doublonnage actuellement utilisées ne comparent que quelques critères comme la source, la date, l'auteur, le titre, etc. Il n'existe pas à ce jour de méthode rapide, non supervisée, prenant en compte (l'intégralité du document et permettant de définir un pourcentage de ressemblance entre le document à insérer et les documents déjà o présents dans la base de données. Par non supervisé, on sous-entend que le procédé ne possède pas de connaissances a priori sur le contexte lié au problème de dé-doublonnage à traiter. L'invention concerne un procédé pour comparer un ensemble de données au contenu d'un fichier de données existant, caractérisé en ce qu'il Is comporte au mains les étapes suivantes : • attribuer un identifiant li à l'ensemble de données Di, • découper l'ensemble de données en plusieurs blocs Bij, • pour chaque bloc Bij, lui associer une clé unique Eij, puis rechercher la clé Eij dans un automate à états finis afin de déterminer quels 20 sont les éléments du fichier de données qui contiennent ce bloc, • calculer une similarité entre les éléments du fichier de données et le nouvel ensemble de données formé par les blocs Bij, • déterminer l'ensemble des éléments du fichier de données qui contient au moins un pourcentage fixé de blocs du nouvel ensemble 25 de données. Selon une autre variante, l'invention concerne un procédé pour comparer un document textuel à une base existante de documents, caractérisé en ce qu'il comporte au moins les étapes suivantes : • attribuer un identifiant li à ce nouveau document Di, s • découper le document en blocs Pij, tel que des phrases, • pour chaque phrase Pij, lui associer une clé unique Eij puis rechercher cette clé Eij dans un automate à états finis afin de déterminer quel sont les documents de la base de documents qui contiennent la phrase Pij, io calculer une similarité entre les éléments de la base existante de don- nées et l'ensemble des données formé par les phrases Pij, • déterminer l'ensemble des anciens documents contenus dans la base de données existante qui contient au moins un pourcentage fixé X% de phrases du document à comparer, 15 • décider de l'intégration du document Di dans la base de documents existante en fonction du degré de similarité qu'il présente avec les autres documents de la base existante. On peut comparer un document existant dans une base de don-nées aux autres documents de la même base de données. 20 Il est aussi possible de comparer un document à insérer dans une base de données existante. L'analyse d'un document peut comporter au moins les étapes sui-vantes : • supprimer l'ensemble des caractères non significatifs de la phrase, • calculer la clef associée à cette phrase contenant uniquement les caractères significatifs, en utilisant un algorithme de hachage, • récupérer l'entier associé à la clef, dans un automate à états finis et déterministe, l'automate retourne un entier i, à la position i se trouve s l'ensemble des indices des phrases des documents ayant la phrase ana-lysée, i correspond à un indice dans un vecteur V, • si la phrase n'existe pas dans le document, ajouter un nouvel identifiant de phrase noté j, ajouter l'indice du document en cours de traitement dans le vecteur V à la position j et ignorer l'étape de mise à jour des lo compteurs, • mettre à jour la liste des compteurs des phrases identifiées dans les anciens documents, ajouter l'indice du document courant à la position i du vecteur V pour effectuer les analyses d'autres documents. L'invention concerne aussi un dispositif pour comparer un ensem- 15 ble de données au contenu d'une base initiale de données, caractérisé en ce qu'il comporte un processeur adapté à exécuter les étapes du procédé selon l'une des revendications 1 à 5, à déterminer un degré de similarité du document analysé avec les documents présents dans la base initiale et une sortie générant une décision d'intégration du document analysé dans la base 20 initiale en fonction de son degré de similarité. La présente invention offre notamment les avantages suivants : • une méthode automatique qui s'appuie sur la théorie des automates, notamment des automates à états finis et déterministes et les techni- 25 ques de calcul de hachage assurant habituellement l'intégrité des fichiers (algorithmes MD5, SHA1, SHA256, RIPEMD160, TIGER, SHA384, SHA512, etc.). • une complexité de recherche qui ne dépend pas du nombre de documents déjà existant dans la base de données, par suite de l'utilisation de la théorie des automates. • une occupation mémoire réduite, même pour de très grandes bases s de données, grâce aux techniques de hachage. • elle offre l'avantage d'être indépendante d'une source de connaissances, ce qui lui permet de fonctionner sur tout type de documents textuels. • La possibilité de : lo o prendre en compte un degré de ressemblance entre les documents correspondant au pourcentage de phrases que deux documents partagent, o calculer le pourcentage de ressemblance entre un document et une base entière de document. II est ainsi possible de savoir 15 quel est le pourcentage de reprise dans un nouveau document par rapport à un stock représentant l'art antérieur (Brevets, articles scientifiques, etc.), • la comparaison des documents paramétrables, on peut par exemple ignorer les dates pour ne pas détecter comme différents un documen- 20 taire identique publié à deux dates différentes les espaces, la ponctuation seront considérés comme non significatifs pendant la comparai-son, • la mise en oeuvre possible sur des grandes bases de données textuel-les; plusieurs millions de documents. 25 D'autres caractéristiques et avantages de la présente invention apparaîtront mieux à la lecture de la description d'un exemple de réalisation, donné à titre illustratif et nullement limitatif, annexé des figures qui représentent : • La figure 1, une mise en oeuvre du procédé pour détecter les documents partiellement ou complètement dupliqués dans une base de 5 données textuelles, • La figure 2, l'utilisation du procédé pour détecter si un nouveau document contient une partie ou la totalité des documents contenus dans une base de données textuelles, • La figure :3, un exemple d'analyse de document selon la méthode, io La figure 4, un exemple d'analyse d'une phrase d'un document utilisant le procédé selon l'invention, • La figure 5, un exemple de dispositif permettant de mettre en oeuvre le procédé selon l'invention. Afin de mieux faire comprendre le principe de l'invention, is l'exemple qui suit concerne la recherche rapide de documents éventuelle-ment en double dans une base de données. Elle peut être utilisée pour des bases de documents textuels en mode stock ou flux. Le procédé peut s'étendre, sans sortir du cadre de l'invention, à 20 toutes données ou ensemble de données contenues dans un fichier. De manière générale, le procédé selon l'invention peut être utilisé pour résoudre au moins l'une ou les deux problématiques citées ci-dessous: 1) comparer les doublons sur un ensemble de documents ou de données figés, permettant par exemple d'aboutir à une nouvelle base sans doublon ou 25 simplement de découvrir les reprises de documents, 2) comparer un nouveau document ou un ensemble de données à une base existante, pour déterminer si ce document ou ces données ne sont pas déjà présents dans la base. La figure 1 schématise globalement les étapes mises en oeuvre pour déterminer, à partir d'une base documentaire 1, quels sont les documents partiellement ou complètement dupliqués. Le procédé vérifie, 2, si un document contenu dans la base est complètement ou partiellement présent dans la base documentaire, en appliquant les étapes décrites à la figure 3, par exemple. io Pour que le procédé soit capable de déterminer quel document duplique l'autre, on trie, 3 les documents présents dans la base de données. On utilise, par exemple, un tri par date, de la plus ancienne à la plus récente, afin de considérer que les documents les plus anciens servent de références. Le tri peut aussi être effectué sur d'autres critères en fonction de la base do- 15 cumentaire. Toute méthode de tri connue de l'Homme du métier peut être utilisée. Le choix du tri aura uniquement une influence sur l'ordre de la relation que le procédé va détecter (un document A reprend un document B ou un document B reprend un document A). 20 Une fois les documents triés, il reste à parcourir les documents, par exemple, du plus ancien au plus récent et de les soumettre un à un aux étapes du procédé illustré par la figure 3. Le procédé produit, 4, la liste des documents partiellement ou complètement dupliqués. Cette liste se présente sous la forme d'un fichier 25 qui peut être utilisé ensuite par un programme de prise de décision, les documents sont-ils à conserver dans la base ? ou encore, ce fichier peut être utilisé par un programme d'analyse plus approfondie du degré de ressemblance des documents contenus dans ce fichier avec les documents présents dans la base de données. La figure 2 représente un exemple d'application du procédé per-mettant de comparer un nouveau document, 5, à insérer dans une base de données, aux documents déjà présents dans une base de données 6. La base de données, par exemple, a été analysée en mettant en oeuvre les éta- l pes décrites à la figure 1. Le procédé analyse le nouveau document afin de déterminer s'il contient une partie ou la totalité de documents existants, 7. Pour effectuer cette analyse, le procédé met en oeuvre les étapes décrites à la figure 3. Le procédé détermine, 8, la liste des documents qui contiennent lo une partie ou la totalité du nouveau document. Puis il exécute, 9, une étape de prise de décision sur le nouveau document concernant sa conservation dans la base ou non. La figure 3 décrit différentes étapes mises en oeuvre par le procédé pour traiter un document déjà présent dans une base de données ou un is nouveau document à ajouter à cette base, comme il a été explicité aux figures 1 et 2. Le procédé associe, à un document à traiter Di, un identificateur li, par exemple, un entier unique 31. Cet identifiant restera le même tout au long de l'analyse. On utilise, par exemple, un compteur commençant à zéro 20 que l'on incrémente à chaque nouveau document. Ce compteur sert d'indice dans un vecteur T qui contient le nombre de phrases du document. Le document est ensuite converti, 32, en texte brut (par exemple au format ASCII, Unicode ...), ce qui revient à supprimer les informations de formatage du document source pour ne garder que le texte ou les données 25 utiles. Une fois cette conversion faite, le processus effectue un découpage du document textuel en un ensemble de phrases Pij, 33. io Ce découpage peut être effectué par un transducteur de reconnaissance des fins de phrases, comme celui du projet Unitex accessible par l'adresse Internet http://www-igm.univ-mlv.fr/-unitex/ ou par tout autre type de détection de phrases. Sur chacune des phrases du document, le procédé effectue, 34, une analyse des phrases qui est décrite en détail dans la figure 4. A la fin de l'analyse des phrases, le procédé calcule les similarités du document avec tous les anciens documents de la base 35. Pour cela, on utilise, par exemple, le rapport entre le nombre de io phrases détectées identiques entre un ancien et un nouveau document divisé par le nombre de phrases de cet ancien document (contenu dans le vecteur T). Il n'est pas nécessaire de calculer ce rapport pour tous les anciens documents de la base. On peut le calculer uniquement pour les documents 15 ayant au moins une phrase en commun avec le nouveau document. Le procédé peut stocker la liste des documents ayant au moins une phrase en commun au moyen de la structure algorithmique arbre rouge et noir (décrit, par exemple, dans le livre Introduction à l'algorithmique de T.Cormen, C.Leiserson, R.Rivest, chapitres 13 et 14) afin de ne pas 20 contenir plusieurs fois les indices de documents (par exemple, ne pas conte- nir deux fois l'indice d'un document ayant deux phrases en commun). Ces similarités correspondent aux pourcentages de phrases que partage le nouveau document avec les anciens documents. Il y a donc autant de similarité que d'anciens documents ayant au moins une phrase en corn- 25 mun avec le nouveau document. On peut ainsi considérer comme similaire deux documents qui ont en commun, plus de X % de phrases. Le seuil X sera en pratique fixé par l'utilisateur du procédé. 2899708 Il La figure 4 détaille un exemple d'étapes mises en oeuvre pour analyser un document par rapport aux documents contenus dans une base de données. Le processus a pour entrée une phrase du document. Les étapes exécutées sont, par exemple, les suivantes : 5 • supprimer l'ensemble des caractères non significatifs de la phrase, 41, pour l'exécution de l'étape de comparaison (par exemple la ponctuation, les espacements, les chiffres, etc.). La nouvelle phrase obtenue contient uniquement les caractères significatifs, par exemple, le pro-cédé transforme voici un exemple de transformation en io voiciunexempledetransformation . • à calculer la clef Eij associée à cette phrase Pij contenant uniquement les caractères significatifs, 42, en utilisant par exemple un algorithme de hachage (tel que l'algorithme MD5 inventé par Ronald L. Rivest, la famille des SHA-x tel que SHA-256 et SHA-512 conçue par la Natio- 15 nal Security Agency des Etats-Unis, RIPEMD-160 inventé par H. Dobbertin, A. Bosselaers et B. Preneel. Le choix de l'algorithme mis en oeuvre dimensionnera surtout l'occupation mémoire nécessaire pour le procédé. En effet, plus la clef est grande et plus les besoins de mémoire seront importants. Les collisions que 20 peuvent entraîner ces algorithmes, c'est-à-dire deux phrases différentes ayant la même clef, ne sont pas un problème. II faudrait, en effet, que les deux documents aient les mêmes conflits sur l'ensemble de leurs phrases pour être considérés comme similaires en ne l'étant pas, ce qui est extrêmement improbable en pratique. 25 • à récupérer l'entier associé à la clef, 43, dans un automate à états finis et déterministe. Ceci permet notamment d'avoir une recherche dont la complexité est indépendante du nombre de phases dans l'automate. Soit i l'entier retourné par l'automate, i correspond à l'indice dans un vecteur V. Ce vecteur V contient à la position i, l'ensemble des indices des documents ayant la phrase analysée. Si la phrase n'existe pas dans l'automate, on l'ajoute avec un nouveau identifiant de phrase que l'on notera j, on ajoute l'indice du document en cours de traitement dans le vec- teur V à la position j et on ignore l'étape 44. En d'autres termes, le tableau V permet d'établir, pour chaque phrase, le lien entre celle-ci et les documents qui la contienne. • à mettre à jour la liste des compteurs des phrases identifiées dans les anciens documents, 44. Ces compteurs indiquent, pour chaque ancien document, le nombre de phrases actuellement identifiées comme étant en commun avec le nouveau document. Les compteurs sont initialisés à zéro au début de l'analyse d'un document, et on va incrémenter de un tous les compteurs associés aux documents contenant la phrase en cours d'analyse (c'est à dire la liste des documents Is trouvés à l'indice i du vecteur V). En effet, ces documents contiennent la phrase que le procédé est en train d'analyser. Il est donc nécessaire de rnettre à jour le nombre de phrases qui ont été trouvées identiques avec le document en cours d'analyse ou sensiblement identiques. 20 Enfin, avant de passer à l'étape suivante (analyse d'un nouveau document par exemple), le procédé ajoute l'indice du document courant à la position i du vecteur V pour les prochaines analyses de documents. Etant donné que le document actuel contient la phrase i , il est nécessaire de l'ajouter au tableau V à l'indice i pour établir la correspondance entre la 25 phrase et le document. A l'issue du procédé, on dispose de plusieurs compteurs, chaque compteur Ci étant associé à un document de la base initiale et contenant un nombre qui correspond au nombre de phrases du document analysé qui sont apparues comme étant identiques aux phrases présentes dans un document de la base initiale. On dispose par exemple des liens suivants : document D1-- compteur Cl = nombre de phrases du document à analyser qui sont identiques aux phrases contenues dans le document de la base initiale. On définit un seuil de ressemblance X fixé en fonction de 5 l'application, pour décider si un document analysé est à considérer comme un doublon des documents formant la base de données initiale. Si le document analysé est considéré comme n'étant pas identique ou sensiblement identique (avec un degré de similarité donné) à un document existant dans la base de données initiale, alors il est ajouté dans la ~o base de données. Dans le cas contraire (le document analysé est considéré comme déjà présent dans la base de données) alors on peut soit le supprimer, soit l'envoyer à un procédé d'analyse plus fine de son contenu. 15 Les étapes du procédé décrit ci-dessus peuvent être utilisées pour les applications suivantes : Le dé-doublonnage de documents dans un flux ou un stock de documents dans le but d'améliorer la qualité des analyses de ces documents. 20 L'identification des reprises de l'information lorsque les documents sont identiques et que seule la source change (une source en a copié une autre). - L'identification de reprise d'une partie d'un document (par exemple un document qui intègre un copier/coller d'une partie d'un autre docu-25 ment). L'identification de documents n'étant que l'intégration de documents antérieurs dans un flux documentaire (par exemple les dépêches "point sur l'information" d'AFP qui contiennent l'ensemble des dépêches de la journée) Ce procédé peut être utilisé par exemple, pour suivre les modifications des dépêches d'agence. II est courant de voir sur un sujet particulier plusieurs modifications entre la première dépêche et la version finale. De plus, les dépêches reprennent très souvent le contenu de précédentes dépêches sans pour autant les citer. Le système permet de détecter automatiquement que la dépêche reprend la totalité ou une partie de précédentes dépêches et les présentes comme liens en plus de celle-ci. La figure 6 représente un exemple de système comprend, par exemple, un serveur d'analyse 50 recevant un document 51 à analyser. Le serveur comprend une base documentaire 52, en liaison avec un processeur 53 sur lequel s'exécute le procédé selon l'invention. La sortie du processeur génère un sous-ensemble 54 de la base contenant les documents repris par le document à analyser. Le fichier contenant l'ensemble des documents qui sont repris ainsi que le pourcentage de reprise est utilisé, par exemple, pour décider de l'ajout des documents ou de leur suppression dans le cas où l'on cherche les doublons dans une base de données existante. Le fichier peut aussi être injecté dans un programme d'analyse plus fine. Une sortie 55 du serveur d'analyse génère un document 56 enrichi avec des liens vers les documents repris qui permettent ainsi d'avoir accès au contenu du document. L'entrée au lieu d'être un document à analyser peut aussi se présenter sous la forme d'une acquisition de documents classiques (http, mail, etc) et la sortie par un écran ou une imprimante. REVENDICATIONS 1 ù Procédé pour comparer un ensemble de données au contenu d'un fi-chier de données existant, caractérisé en ce qu'il comporte au moins les étal pes suivantes : • attribuer un identifiant li à l'ensemble de données Di, • découper l'ensemble de données en plusieurs blocs Bij, • pour chaque bloc Bij, lui associer une clé unique Eij, puis rechercher la clé Eij dans un automate à états finis afin de déterminer quels ~o sont les éléments du fichier de données qui contiennent ce bloc, • calculer une similarité entre les éléments du fichier de données et le nouvel ensemble de données formé par les blocs Bij, • déterminer l'ensemble des éléments du fichier de données qui contient au moins un pourcentage fixé de blocs du nouvel ensemble 15 de données. 2 ù Procédé pour comparer un document textuel à une base existante de documents, caractérisé en ce qu'il comporte au moins les étapes suivantes : • attribuer un identifiant li à ce nouveau document Di, 20 • découper le document en blocs Pij, tel que des phrases, • pour chaque phrase Pij, lui associer une clé unique Eij puis rechercher cette clé Eij dans un automate à états finis afin de déterminer quel sont les documents de la base de documents qui contiennent la phrase Pij, • calculer une similarité entre les éléments de la base existante de don-nées et l'ensemble des données formé par les phrases Pij, • déterminer l'ensemble des anciens documents contenus dans la base de données existante qui contient au moins un pourcentage fixé X% de phrases du document à comparer, • décider de l'intégration du document Di dans la base de documents existante en fonction du degré de similarité qu'il présente avec les autres documents de la base existante. 3 û Procédé selon l'une des revendications 1 et 2, caractérisé en ce que l'on compare un document déjà existant dans une base de données aux autres documents contenues dans la même base de données. 4 û Procédé selon l'une des revendications 1 et 2, caractérisé en ce que l'on 1s compare un document à insérer dans une base de données existante. 5 û Procédé selon l'une des revendications 2 à 4, caractérisé en ce que l'analyse d'un document comporte les étapes suivantes : • supprimer l'ensemble des caractères non significatifs de la phrase (41), 20 • calculer la clef associée à cette phrase contenant uniquement les caractères significatifs, (42) en utilisant un algorithme de hachage, • récupérer l'entier associé à la clef, (43), dans un automate à états finis et déterministe, l'automate retourne un entier i, à la position i se trouve l'ensemble des indices des phrases des documents ayant la phrase ana- 25 lysée, i correspond à un indice dans un vecteur V,• si la phrase n'existe pas dans le document, ajouter un nouvel identifiant de phrase noté j, ajouter l'indice du document en cours de traitement dans le vecteur V à la position j et ignorer l'étape (44), • mettre à jour la liste des compteurs des phrases identifiées dans les an-5 Giens documents, (44), • ajouter l'indice du document courant à la position i du vecteur V pour effectuer les analyses d'autres documents. 6 û Dispositif pour comparer un ensemble de données au contenu d'une io base initiale de données, caractérisé en ce qu'il comporte un processeur adapté à exécuter les étapes du procédé selon l'une des revendications 1 à 5, à déterminer un degré de similarité du document analysé avec les documents présents dans la base initiale et une sortie générant une décision d'intégration du document analysé dans la base initiale en fonction de son 15 degré de similarité.