Trouver des fichiers dupliqués dans un grand jeu de données

Dans un grand jeu de données, il y a de fortes chances d’avoir des fichiers dupliqués. Trouver ces fichiers dupliqués permet de les lier, afin qu’une modification de l’une des copies ou de ses métadonnées soit indiquée sur les autres copies. Cela permet un partage plus pratique et une meilleure réutilisation des données.

Pour des fichiers qui sont exactement les mêmes, les copies peuvent être détectées en s’appuyant sur le md5 des fichiers. On peut considérer que deux fichiers avec le même md5 ont une probabilité très élevée d’être identiques.

Mais nous sommes aussi intéressés par les fichiers dupliqués de manière moins évidente:

  • Deux fichiers avec le même contenu mais différents formats, par exemple un fichier word exporté en PDF
  • Différentes versions du même fichier

De tels fichiers ont un contenu très similaire, mais un md5 différent.

Solr More Like This

Apache Solr (http://lucene.apache.org/solr/) est une plateforme logicielle de recherche basée sur Apache Lucene. Chez Dexstr, nous utilisons déjà Solr pour ses capacités d’indexation et de recherche.

La fonctionnalité de Solr qui nous intéresse pour notre besoin est le “More Like This (MLT)”. Cette fonctionnalité permet de requêter Solr pour obtenir des documents similaires, avec un score de similarité associé à chaque document résultant de la requête.

Dans un premier temps, cette fonctionnalité paraissait répondre parfaitement à nos besoins, sachant que nous indexons déjà le contenu des fichiers dans un index Solr (le contenu des fichiers est extrait par Tika, un autre outil d’Apache – https://tika.apache.org/).

Notre première approche a été la suivante:

  • Requêter Solr pour obtenir des fichiers similaires
  • Prendre tous les documents au dessus d’un certain seuil de similarité

Les premiers résultats n’ont pas été aussi bons qu’espéré. En effet, Solr retourne des scores proches pour des documents avec seulement quelques mots qui diffèrent et pour des documents portant sur le même sujet.

Pour comprendre ces résultats, nous avons regardé plus attentivement le fonctionnement du MLT.

Le MLT est basé sur les “mots intéressants”, qui sont des termes (des mots dans notre cas) qui sont très fréquents dans le document requêté et peu fréquents dans l’ensemble du jeu de données. Ces fréquences permettent de calculer un score par terme, et les termes avec les meilleurs scores vont être utilisés dans la requête Solr.

Matrice de similarité du MLT

Pour obtenir plus de détails sur le fonctionnement du MLT, qui n’est pas très bien documenté dans la documentation Solr ou Lucene, vous pouvez lire ce post: http://cephas.net/blog/2008/03/30/how-morelikethis-works-in-lucene/

Dans notre cas, nous rencontrons deux problèmes avec l’utilisation du score de similarité du MLT:

  • Le score est relatif entre les documents retournés par une même requête, il n’est pas comparable entre les résultats de deux requêtes. Il est donc difficile de trouver un seuil au-dessus duquel deux documents peuvent être considérés comme suffisamment similaires pour être des versions d’un même document. D’après la FAQ de Lucene, le score n’est pas significatif à cause de la façon dont il est calculé (https://wiki.apache.org/lucene-java/LuceneFAQ#Can_I_filter_by_score.3F)
  • La similarité est calculée en se basant uniquement sur quelques termes considérés comme intéressants: deux documents très différents mais traitant du même sujet pourront avoir un score de similarité élevé, surtout s’ils traitent d’un sujet rare dans le jeu de données.

Le MLT de Solr est donc très adapté pour trouver des documents traitant d’un même sujet, mais dans notre cas ne sera pas assez différenciant entre des documents similaires et des versions d’un même document.

Pourtant, même si il retourne beaucoup de faux positifs pour notre problème, les documents similaires sont bien retournés par Solr.

Nous avons donc eu l’idée d’utiliser Solr pour trouver des candidats potentiels pour les dupliqués, ce qui est rapide étant donné que l’index Solr est utilisé. Puis d’utiliser une autre méthode de calcul de similarité pour ne garder que les documents que l’on considère comme suffisamment similaires.

Calcul de similarité

Nous avons étudié différentes méthodes de similarité. Voici une liste non exhaustive de ces méthodes:

  • Similarité de Cosine: cette méthode est largement utilisée dans les calculs de similarité. Elle est basée sur des mesures de distances entre vecteurs, les vecteurs représentant des fréquences de termes (souvent on utilise le TF-IDF, qui est un ratio entre la fréquence des termes dans un document et dans le jeu de données). Dans notre cas, cette méthode a été testée et n’est pas satisfaisante, car si deux documents possèdent à peu près les mêmes termes dans les mêmes proportions, le score sera élevé. La conséquence sera la même que pour le MLT de Solr, avec des documents traitant du même sujet qui auront un score de similarité élevé.
  • Les méthodes de similarité basées sur les caractères , par exemple les méthodes Levenshtein ou Needleman-Wunsch. Ces méthodes vont comparer les textes caractère par caractère (les mots et ponctuation peuvent être utilisés à la place des caractères). Ils prennent en compte toutes les différences entre les textes (deux mots inversés seront considérés comme une transformation par exemple). Quelques tests ont été faits avec nos données, mais ces méthodes sont très lourdes en terme de calculs, et ne sont pas suffisamment performantes pour être utilisés sur un grand jeu de données.
  • Coefficient de Dice: il s’agit d’un ratio entre le nombre de termes communs aux deux documents comparés et le nombre total de termes des deux documents. Cette méthode compare la similarité d’un « sac de mots », en prenant en compte le nombre d’occurences de chaque terme mais pas leur ordre.
  • Overlap: cette métode est proche du coefficient de Dice, mais prend en compte les chevauchements. Le score de similarité sera maximum si l’un des documents est un sous-ensemble de l’autre. Cette méthode paraissait intéressante dans notre cas, parce qu’une nouvelle version d’un document consiste souvent en de l’ajout ou du retrait de texte, mais il y a un biais en fonction de la taille des documents: si un petit document a le même sujet qu’un grand, presque tous les termes du petit document seront contenus dans l’autre, et le score de similarité sera très élevé.

Dans notre cas, le coefficient de Dice permet d’obtenir les meilleurs résultats pour un temps de calcul raisonnable. La simplification de ne pas considérer l’ordre des mots dans le calcul de similarité semble acceptable en vue des exemples testés.

Nous avons calculé le coefficient de Dice de deux documents en les divisant en termes en utilisant Lucene et en comptant le nombre de termes entre deux documents.

Algorithme pour trouver les dupliqués

L’algorithme implémenté pour trouver les versions d’un même document est le suivant:

  • Trouver des documents intéressants grâce au MLT de Solr
  • Pour les n documents avec les meilleurs scores, calculer le coefficient de Dice
  • Comme nous avons déjà les métadonnées techniques des fichiers, y compris les titres des fichiers, extraits par Tikka, nous ajoutons un score “bonus” si deux documents ont le même titre
  • Prendre les documents avec un score de similarité plus grand qu’un seuil (configurable)
  • Pour les documents retenus, refaire la même chose

→ Nous obtenons ainsi un groupe de documents similaires

Nous avons donc un groupe de documents que l’on considère comme des dupliqués ou comme des versions différents d’un même fichier. L’étape suivante est de retrouver l’historique du fichier, et nous utilisons pour cela des métadonnées techniques comme la date de dernière sauvegarde, la date de dernière modification…

Limitations

Dans cette première version de notre outil, il y a quelques limitations sur lesquelles nous travaillons actuellement:

  • Si deux versions d’un même fichier sont vraiment différentes, il n’est pas possible de les détecter, nous cherchons à donner plus d’importance aux métadonnées techniques des fichiers.
  • Le score pour déterminer si deux documents sont suffisamment similaires est le même pour tout le jeu de données. Il pourrait être intéressant de définir différents seuils en fonction de règles sur les fichiers.
  • Il est difficile de connaître l’historique des versions. Sur certains formats de fichiers, par exemple les fichiers Office, les métadonnées techniques comme la date de dernière modification permettent de deviner l’historique, mais pour d’autres formats cela n’est pas possible. Nous nous appuyons alors sur la date d’insertion des fichiers dans notre système.

Résultats

Nous avons testé notre algorithme avec différentes versions et formats des mêmes fichiers, et l’algorithme a trouvé tous les fichiers dupliqués. Après des tests fructueux sur des jeux de données contrôlés, nous avons déployé notre outil pour tourner sur un jeu de données réel et de grande taille chez un de nos clients, et les résultats sont très prometteurs.

Charlotte, Back End Lead Developer.

Share on LinkedInTweet about this on Twitter