Discussion :

[teddyalbina]

Bonjour à tous je voudrais savoir s’il existe un algo ou une technique pour comparer des milliers de documents sans indexer deux documents identique.

L'application que je développe en ce moment index de énormément de texte, et mon problème est qu'il arrive assez souvent d'indexer deux fois le même texte. Donc je cherche une méthode pour garder une signature de chaque document indexé pour la comparer avec les documents qui entre dans le système et si deux signature sont identique ou fortement similaire je n'index pas le document.

Merci

[Jedai]

Généralement on utilise un hash comme MD5 pour créer les signatures des documents. En pratique la probabilité que deux documents différents aient la même signature est infime et ainsi il est aisé de vérifier qu'un nouveau document n'est pas déjà dans la base en comparant simplement sa signature à l'ensemble des signatures des documents déjà dans la base. S'il y a concordance, il suffit de comparer les deux documents qui ont la même signature, le coût est ainsi énormément minimisé par rapport à une comparaison avec chaque document déjà dans la base.

As-tu besoin de plus de détails ? (Tous les langages décents ont des librairies pour calculer le hash MD5 d'un document)

--
Jedaï

[teddyalbina]

Merci Jedai pour ta réponse, mon programme est écrit en C# je vais donc utiliser Security.Cryptography pour générer une signature md5 de chacun des documents.

[droggo]

Goe,

Généralement on utilise un hash comme MD5 pour créer les signatures des documents. En pratique la probabilité que deux documents différents aient la même signature est infime et ainsi il est aisé de vérifier qu'un nouveau document n'est pas déjà dans la base en comparant simplement sa signature à l'ensemble des signatures des documents déjà dans la base. S'il y a concordance, il suffit de comparer les deux documents qui ont la même signature, le coût est ainsi énormément minimisé par rapport à une comparaison avec chaque document déjà dans la base.

As-tu besoin de plus de détails ? (Tous les langages décents ont des librairies pour calculer le hash MD5 d'un document)

--
Jedaï

On peut même plutôt calculer les hash de ces 2 documents avec un autre algorithme (crcXX, shaXX...), littéralement aucune chance qu'ils donnent également la même signature.

Mais il n'est pas sûr que ce soit plus rapide que faire la comparaison directe des documents, le premier test à faire étant de comparer les tailles, qui éliminera au moins une partie des cas à traiter.

[teddyalbina]

Je pense que la solution de jedai est mieux dans mon cas, je doit indexer des millers voir millions de document (je bosse sur un moteur de recherche d'entreprise). Donc comparer les tailles permet certes d'éliminer une bonne partie des cas à traiter mes ceux restant sont encore trop nombreux . Il me faut une comparaison directe donc l'approche par signature md5 ou autre est meilleur selon moi.

[alex_pi]

Après, il faut bien se rendre compte que la signature MD5 ne convient que pour détecter *rigoureusement* le même texte, à la virgule pres. Si l'un est stocké en HTML et l'autre en texte brut, tu n'as quasiment aucune chance d'extraire du texte brut depuis l'HTML et d'obtenir le même hash. Je pense qu'il doit quand même y avoir des méthodes plus résistantes à de petits changement pour détecter des textes très similaires.

[Veovis]

Si tu cherches à êtrte moins rigoureux tu peux utiliser le cosinus entre 2 phrases...

[icer]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Si tu cherches à êtrte moins rigoureux tu peux utiliser le cosinus entre 2 phrases...

Qu'est-ce que c'est? ... une blague...

[pseudocode]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Si tu cherches à êtrte moins rigoureux tu peux utiliser le cosinus entre 2 phrases...

Qu'est-ce que c'est? ... une blague...

Non, meme pas. Ca revient a calculer la cross-correlation entre 2 séries.

[Graffito]

Bonjour,

Si l'indexation est faite pour un moteur de recherche en texte libre (genre google):

• on entre, avant indexation, le nouveau document comme question,
• on regarde, pour les meilleures réponses, le nombre de termes communs,
• on calcule la proportion relative des termes communs entre ceux de la question et ceux de la réponse
• quand une des proportions est "grande", c'est qu'un document peut être considéré comme un extrait de l'autre.
• quand les 2 proportions sont "grandes", c'est que les documents sont semblables.

[Tommy31]

Si tu cherches à êtrte moins rigoureux tu peux utiliser le cosinus entre 2 phrases...

Non, meme pas. Ca revient a calculer la cross-correlation entre 2 séries.

C'est la covariance pas le cosinus ou je rate quelque chose ?

[Veovis]

Tu rates quelque choses c'est le cosinus et pas la covariance.

[pseudocode]

C'est la covariance pas le cosinus ou je rate quelque chose ?

Normalized cross-correlation

Avec énormément d'abus de langage mathématique (), on peut assimiler une suite de valeurs aux coordonnées d'un vecteur:

suite de 26 valeurs S = {a,b,c,d,...,z} --> Vecteur de dimension 26 V(a,b,c,d,...,z)

Cross-Correlation:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
 
                      Somme{ (f-mean(f))*(g-mean(g)) }
Cross(f,g) = ---------------------------------------------------
             sqrt(Somme{(f-mean(f))²})*sqrt(Somme{(g-mean(g))²})
 
F=f-mean(f)
G=g-mean(g)
 
                       Somme{ F*G }       
Cross(f,g) = -------------------------------
             sqrt(Somme{F²})*sqrt(Somme{G²})
 
                       Somme{ F*G }     
           = ------------------------------
                      ||F|| * ||G||

Produit scalaire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
<F.G> = Somme{ F*G } = ||F|| * ||G|| * cos(F,G)

Remplacement:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
                 <F.G>
Cross(f,g) = -------------
             ||F|| * ||G||
 
             ||F|| * ||G|| * cos(F,G)
           = ------------------------ 
                  ||F|| * ||G||
 
           = cos(F,G)

[teddyalbina]

Merci a tous de votre aide, j'ai finalement décider d'utilise la méthode du cosinus