Contact
Le dédoublonnage consiste à détecter et fusionner toutes les copies d’un même document dans une base de données. La présence de doublons complique l’indexation et est un frein à la centralisation de l’information dans une source de référence. Ce problème est récurrent dans des bases conséquentes et contenant un historique important qui facilite la perte de traçabilité. Cet article détaille un système implémenté pour détecter les doublons parmi des millions de documents scannés.
Dans ce contexte, la reconnaissance optique de caractères (ROC) permet d’extraire le texte de l’image résultante du scanner. Ensuite, il faut comparer le texte des deux documents pour décider s’ ils sont identiques. Se pose alors un problème d’échelle : pour une base de N=1000000 documents, une approche naïve testant toutes les paires de documents nécessite un total de 
millions de comparaisons. Le temps de calcul deviendrait donc prohibitif.
La solution IA mise en place par les équipes de LumenAI consiste à pré-trier les données grâce à un algorithme de clustering. Cet algorithme permet de regrouper les documents dans une structure hiérarchique appelée dendrogramme. Itérativement, les données sont séparées en groupes homogènes de plus en petits jusqu’à ce que la comparaison directe et naïve des paires de documents soit possible en un temps jugé acceptable. À chaque séparation, un document type, représentant de l’ensemble des documents des niveaux inférieurs, est conservé.
Lors de la détection d’un doublon potentiel, celui-ci est comparé uniquement avec les représentants de chaque niveau, ainsi que les documents du groupe terminal. Ceci permet d’éviter une comparaison directe avec tous les documents de la base. En pratique, cette organisation peut réduire le temps de calcul de plusieurs jours à quelques secondes pour une base de 20 millions de pages.
Dans la pratique, nous extrayons le texte de chaque document grâce à l’outil open source tesseract
, et transformons chaque page en vecteur grâce à une méthode classique de plongement lexical de type Doc2vec
. Ces modèles nous permettent d’effectuer un premier tri et d’être robuste aux erreurs de ROC ainsi qu’aux différences apparaissant entre différentes versions d’un même document. Dans la comparaison finale, des approches précises comme le MinHash
ou la comparaison directe du texte sont employées pour valider la détection. Plutôt que d’utiliser un clustering hiérarchique classique, qui requiert une matrice de distance de taille 
coûteuse à obtenir, un algorithme de type K-moyennes est utilisé afin de construire les groupes de chaque niveau de manière itérative. L’implémentation s’appuie sur un algorithme interne de LumenAI. La taille maximale des groupes finaux est fixée à 500 documents. Pour une base de 20 millions de documents, le dendrogramme obtenu contient environ 50000 groupes et sa profondeur moyenne est de 12 niveaux.
Il est utile d’observer les groupes construits automatiquement par le clustering pour mieux appréhender son fonctionnement. En général, les documents d’un groupe sont homogènes en termes de mots employés, et au fur et à mesure que l’on descend dans le dendrogramme, la variabilité des groupes sera de plus en plus faible. Ainsi, il existe des groupes qui contiennent exclusivement des documents issus d’une entreprise particulière en raison de la grande homogénéité de son format. Un autre groupe contient essentiellement des pages de titres, un autre contient des tableaux et des pages de nombres, et bien sûr, un énorme groupe contenant toutes les pages blanches est trouvé par l’algorithme.
1. https://github.com/tesseract-ocr/tesseract
2. Le et al, Distributed representations of sentences and documents, ICML 2014
3. Broder, et al. On the resemblance and containment of documents, 1997.