Discussion :

[Gnolls]

Bonjour à tous,

Je suis actuellement sur un projet où j'ai besoin de vérifier le pourcentage de duplication entre plusieurs textes. Le but c'est de se rapprocher un maximum du traitement de la duplication de Google.

Après avoir fait de nombreuses recherches j'ai statué que Simhash était le plus adapté à ça. Il existe de nombreuses librairies et de nombreux paramètres.

Avec la librairie de https://github.com/nicolaichuk/SimHashPhp dont je me suis inspirés, utilise ce code pour calculer l'indice :

Code php :

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
17
18
19
20
21
22
23
    /**
     * Similarity index
     *
     * @param int $countDifferences
     * @return float
     */
    protected function computeSimilarityIndex($countDifferences)
    {
        return $this->gaussianDensity($countDifferences) / $this->gaussianDensity(0);
    }
    /**
     * Guassian distribution density
     *
     * @param int $x
     * @return float
     */
    protected function gaussianDensity($x)
    {
        $y = - (1 / 2) * pow($x / $this->deviation, 2);
        $y = exp($y);
        $y = (1 / sqrt(2 * pi())) * $y;
        return $y;
    }

Après avoir récupéré mes fingerprints de mes deux textes, j'aimerais connaître le pourcentage de similarité entre les deux textes.

Sauf que lors que je passe d'un SIMHASH 64bits, à 128 ou 256, le nombre de bit différent augmente et mon indice devient de plus en plus petit (avec des xxxxxE-19, xxxxE-40).

Sur l'article du concepteur de la librairie (https://web.archive.org/web/20150227...-05-29-simhash) , il explique une formule plus simple : 1 - (diffCount / nbBit)

Sauf que si j'applique cette formule au lieu du gaussianDensity, les résultats ne sont pas cohérents par rapport d'autres outils sur internet et donne des valeurs très fausses.

Donc je suis un peu bloqué ... Quelqu'un aurait une idée pour me sortir de ce problème avec Simhash ou aurait une autre idée pour checker la similarité entre plusieurs textes ?

Merci et très bonne journée !

[tbc92]

Regarde étape par étape ce qui se passe.
Tu prends 2 phrases, avec une forte ressemblance (critère humain) ; 2 phrases où tu considères que la ressemblance est à 95%.
Tu calcules les simhash de ces 2 phrases. Tu obtiens 2 chaines de 256 bits.
Tu peux compter à la main le nombre de bits similaires. Est-ce qu'on est aux environs de 240 , 250 ... ou pas

Tu peux refaire l'expérience avec 2 autres phrases, où tu considères que la ressemblance est à 60%.

Personnellement, en lisant l'algorithme sur le lien que tu as donné, je ne suis pas convaincu par cet algorithme.

Si a partir de phrases très ressemblantes, le Simhash donne 2 chaines de bits très différentes, il y a un problème.

Et par ailleurs, si je comprends bien, si on a une chaine de 256 bits, on compte au final le nombre de bits identiques. Et donc la ressemblance est un nombre de la forme N/256. La plus petite valeur possible est donc d'environ 0.004, et pas 1E-40.

[Guesset]

Bonjour,

Indépendamment du bien fondé de l'algorithme, l'extrait de code exprime les limites de la démarche purement analytique. On perd la vue d'ensemble ce qui peut conduire à des calculs superfétatoires.

Je ne sais pas si la fonction gaussianDensity($x) sert ailleurs mais si ce n'est pas le cas il semble plus pertinent de la retirer et d'écrire :

Code php :

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

1
2
3
4
protected function computeSimilarityIndex($countDifferences)
 {
        return = exp(- pow($countDifferences / $this->deviation, 2) / 2);
 }

En effet, appeler $this->gaussianDensity(0) implique beaucoup de calculs pour finalement se contenter de faire disparaître (2PI)^-1/2.

Salutations

[anadoncamille]

Si j'ai bien compris le problème, tu cherches à tester la similarité entre deux chaînes de caractères, exercice délicat s'il en est.

Tu as choisi de passer par la comparaison des hash des chaines de caractères à tester.
Note dans un premier temps qu'il existe moins de hash que de chaines de caractères. Donc un même hash peut apparaître pour deux chaines radicalement différentes.
Par ailleurs deux chaines de caractères identiques à un caractère près vont générer deux hash radicalement différents.
Il en résulte que comparer les hash des chaines de caractères donne des résultats indépendants de la similitude des chaînes de caractères.

Je ne connais pas l'algorithme de google dont tu parles mais je doutes que ce soit celui que tu essayes d'implémenter.
N'oublie pas que google a des calculateurs très performants et que le calcul massif ne les effraie pas.
Renseignes-toi sur l'algorithme en question, si tu peux.

Note qu'évaluer la similitude entre deux textes est un exercice très délicat.
A titre d'exemples :
- quelle est la similitude entre "aaaaabaaaaaa" et "aaaaacaaaaaa" ?
- quelle est la similitude entre "aaaaabaaaaaa" et "aaaaaabaaaaa" ?
- quelle similitude est la plus grande des deux précédentes ?
- la similitude entre "a" et "e" est-elle différente de la similitude entre "a" et "b" ?
- quelle est la similitude entre "o" et "eau" ? entre "eau" et "haut" ? entre "eau" et "eaux" ?
- la similitude entre deux synonymes est-elle plus grande que la similitude entre deux homonymes ?
- la similitude entre "abonder" et "aborder" est-elle plus grande que la similitude entre "clavier' et "keyboard" ?

Je réfléchis depuis longtemps à ce problème et je n'ai pas encore trouvé d'algorithme efficace et fiable.
Pour ce que j'en sais, l'algorithme ne question serait une véritable usine à gaz.
Finalement l'algorithme le plus simple à implémenter pourrait être un réseau de neurones.
Mais il reste alors le problème de créer le set d'apprentissage, ce qui n'est pas une mince affaire.
Le problème le plus important à mon avis est d'attribuer une valeur de similitude entre deux chaînes de caractères.
Il importe de bien distinguer les cas limites.

En tout cas, bon courage !

[Guesset]

Bonjour,

Dans le questions à se poser, il y a éventuellement la phonétique. La distance entre phrases est différente si elles doivent sonner pareils ou avoir un taux de séquences identiques fort. Dans le premier cas le passage par un soundex (différent selon les langues) peut être une première étape.

Salutations