Vérification des doublons de documents et de documents similaires dans une application de gestion des documents

Question

Mise à jour: J'ai maintenant écrit une extension PHP appelé php_ssdeep pour l'API ssdeep C pour faciliter hachage flou et des comparaisons de hachage dans PHP en mode natif. Plus d'informations peuvent être trouvées over at my blog. J'espère que cela aidera les gens.

Je suis impliqué dans l'écriture d'une application de gestion de documents personnalisée en PHP sur une machine Linux qui stockera divers formats de fichiers (potentiellement 1000 de fichiers) et nous devons être en mesure de vérifier si un document texte a déjà été téléchargé duplication dans la base de données. Essentiellement, lorsqu'un utilisateur télécharge un nouveau fichier, nous aimerions pouvoir lui présenter une liste de fichiers qui sont en double ou qui contiennent un contenu similaire. Cela leur permettrait ensuite de choisir l'un des documents préexistants ou de continuer à télécharger le leur.

Des documents similaires seraient déterminés en regardant dans leur contenu pour des sentances similaires et peut-être une liste générée dynamiquement de mots-clés. Nous pouvons ensuite afficher un pourcentage de correspondance avec l'utilisateur pour l'aider à trouver les doublons.

Pouvez-vous recommander des packages pour ce processus et des idées sur la façon dont vous auriez pu le faire dans le passé?

Le double directe, je pense que peut être fait en obtenant tout le contenu du texte et

• Décapage des espaces
• Suppression des signes de ponctuation
• Convertir en minuscule ou en majuscule

forment alors une MD5 hash à comparer avec tous les nouveaux documents. L'extraction de ces éléments devrait aider à éviter que des dupes ne soient trouvés si l'utilisateur édite un document pour ajouter des sauts de paragraphe supplémentaires, par exemple. Des pensées? Ce processus pourrait également s'exécuter en tant que travail nocturne et nous pourrions informer l'utilisateur de tous les doublons lors de la prochaine connexion si l'exigence de calcul est trop grande pour fonctionner en temps réel. Le temps réel serait préféré cependant.

Answer 1

Mise à jour: J'ai maintenant écrit une extension PHP appelé php_ssdeep pour l'API ssdeep C pour faciliter les comparaisons et hachage floue hachage en PHP natif. Plus d'informations peuvent être trouvées over at my blog. J'espère que cela aidera les gens.

J'ai trouvé un programme qui fait ce que son créateur, Jesse Kornblum, appelle "Fuzzy Hashing". Très fondamentalement, il fait des hachages d'un fichier qui peut être utilisé pour détecter des fichiers similaires ou des correspondances identiques.

La théorie sous-jacente est documentée ici: Identifying almost identical files using context triggered piecewise hashing

ssdeep est le nom du programme et il peut être exécuté sous Windows ou Linux. Il était destiné à être utilisé en informatique légale, mais il semble assez adapté à nos objectifs. J'ai fait un petit test sur une vieille machine Pentium 4 et il faut environ 3 secondes pour passer par un fichier de hachage de 23 Mo (hachage pour un peu moins de 135 000 fichiers) à la recherche de correspondances avec deux fichiers. Ce temps comprend la création de hachages pour les deux fichiers que je cherchais aussi.

Answer 2

Je travaille sur un problème similaire dans web2project et après avoir demandé autour et creuser, je suis arrivé à la conclusion de "l'utilisateur s'en fout". Avoir des documents en double n'est pas importe à l'utilisateur tant qu'ils peuvent trouver leur propre document par son propre nom.

Cela étant dit, voici l'approche que je prends:

• permet à un utilisateur de télécharger un document associant à des projets/tâches quel que soit qu'ils veulent;
• Le fichier doit être renommé pour empêcher quelqu'un d'y accéder via http .. ou mieux stocké en dehors de la racine web. L'utilisateur verra toujours son nom de fichier dans le système et s'il le télécharge, vous pouvez définir les en-têtes avec le nom de fichier "correct";
• À un moment donné dans le futur, traitez le document pour voir s'il y a des doublons ... à ce stade cependant, nous sommes et non en modifiant le document.Après tout, il pourrait y avoir des raisons importantes de changer l'espace ou la capitalisation;
• S'il existe des doublons, supprimez le nouveau fichier, puis liez-le à l'ancien;
• S'il n'y a pas de dupes, ne faites rien;
• Indexer le fichier pour les termes de recherche - en fonction du format de fichier, il y a beaucoup d'options, même pour les documents Word;

Tout au long de tout cela, nous ne disons pas à l'utilisateur qu'il s'agissait d'un doublon ... ils s'en fichent. C'est nous (développeurs, admins db, etc) qui s'en soucient.

Et oui, cela fonctionne même s'ils téléchargent une nouvelle version du fichier plus tard. Tout d'abord, vous supprimez la référence au fichier, puis - comme dans le garbage collection - vous ne supprimez l'ancien fichier que s'il n'y a aucune référence.