SimHash : trouver les pages qui se ressemblent

Il y a quelques semaines, j’ai eu besoin de détecter du contenu dupliqué dans le crawler de redirection.io. Pas du dupliqué à la virgule près, ça c’est facile, mais du dupliqué « en gros, c’est la même page ». J’aurais pu utiliser des embeddings avec un LLM, mais il me fallait quelque chose de rapide et de gratuit. J’ai finalement utilisé SimHash, un algorithme qui date de 2002 et qui tient en trente lignes de PHP.

Dans cet article, nous allons voir pourquoi md5() ne peut pas nous aider, comment fonctionne SimHash, comment l’implémenter en PHP sans aucune dépendance, et surtout comment faire tourner la comparaison en base de données quand on a des millions de pages.

Section intitulée le-problemeLe problème

Le crawler de redirection.io parcourt un site et récupère toutes ses pages. À la fin, on veut prévenir l’utilisateur : ces pages ont le même contenu.

Commençons par le cas facile. Deux pages strictement identiques :

$hashA = md5($contenuA);
$hashB = md5($contenuB);

Mais dans la vraie vie, les pages ne sont jamais strictement identiques. Prenez une boutique en ligne avec une fiche produit déclinée par ville :

Toutes nos paires sont expédiées sous 24 heures depuis notre entrepôt de Lyon.

Toutes nos paires sont expédiées sous 24 heures depuis notre entrepôt de Bordeaux.

Trois cents mots identiques, un seul mot qui change. Pour un moteur de recherche, ce sont des doublons. Pour md5(), ce sont deux pages qui n’ont rien à voir.

Section intitulée pourquoi-les-fonctions-de-hachage-habituelles-ne-nous-aident-pasPourquoi les fonctions de hachage habituelles ne nous aident pas

Le premier réflexe serait de se dire que deux contenus proches donnent deux hash proches. Vérifions :

echo md5('Bonjour le monde'), "\n";
echo md5('Bonjour le Monde'), "\n";

9cbfb998c9c4f8966d0df57e0065383a
1dacb65f3f3799ba5643cb3409e3aeec

Une seule lettre change, un m devenu M, et les deux empreintes n’ont plus rien en commun. Ce n’est pas un bug, c’est exactement ce qu’on demande à une fonction de hachage. Ça porte un nom : l’effet avalanche. Changer un seul bit en entrée doit faire basculer, en moyenne, la moitié des bits en sortie.

C’est indispensable en cryptographie et pour les tables de hachage. Pour notre problème, c’est l’inverse de ce qu’on veut.

Il nous faudrait une fonction de hachage qui préserve la ressemblance : deux textes proches doivent produire deux empreintes proches. Ça existe, ça s’appelle du locality sensitive hashing (hachage sensible à la localité), et SimHash en est le représentant le plus connu.

L’algorithme vient d’un article de Moses Charikar publié en 2002. Google l’a popularisé en 2007 dans un papier intitulé « Detecting Near-Duplicates for Web Crawling », où il explique comment dédupliquer 8 milliards de pages avec des empreintes de 64 bits. La méthode a donc été éprouvée.

Section intitulée le-principe-faire-voter-les-morceaux-du-texteLe principe : faire voter les morceaux du texte

Imaginez une élection avec 64 questions, chacune n’admettant que deux réponses : oui ou non. Question n°0 : oui ou non ? Question n°1 : oui ou non ? Et ainsi de suite jusqu’à la question n°63.

Les électeurs, ce sont les petits morceaux du texte. Chaque morceau a un avis sur les 64 questions, et cet avis vient de son propre hash : le bit n°0 de son hash est sa réponse à la question n°0, le bit n°12 sa réponse à la question n°12.

On dépouille ensuite question par question. Si les « oui » l’emportent, on note 1, sinon 0. On obtient 64 bits, et c’est l’empreinte du document.

Prenons maintenant un document de 300 mots, donc environ 300 électeurs, et changeons un mot. Seuls 2 ou 3 électeurs changent d’avis. Sur la plupart des questions, la majorité était assez large pour que ces quelques voix ne changent rien au résultat. L’empreinte reste presque la même : un ou deux bits basculent, sur les questions où le vote était serré.

À l’inverse, deux documents qui n’ont rien à voir ont des électeurs complètement différents. Les votes n’ont aucune raison de coïncider, et les deux empreintes diffèrent sur environ la moitié des bits.

La question « ces deux textes se ressemblent-ils ? » devient donc « ces deux entiers de 64 bits diffèrent-ils sur peu de bits ? ». Et ça, une base de données sait le faire très vite.

Section intitulée etape-1-decouper-le-texte-en-shinglesÉtape 1 : découper le texte en shingles

Il faut d’abord fabriquer les électeurs. La solution évidente serait de prendre les mots un par un. C’est une mauvaise idée.

Avec des mots isolés, le document devient un sac de mots et l’ordre disparaît complètement. Ces deux phrases auraient exactement la même empreinte :

le chat mange la souris puis le chien attrape une balle rouge dans le jardin…
attrape balle chat chien dans jardin la le le le mange puis rouge souris une…

Avec des électeurs d’un seul mot, la distance entre ces deux textes est de 0. Ils sont considérés comme identiques, alors que le second n’a aucun sens.

La parade s’appelle un shingle (« bardeau », comme les tuiles d’un toit qui se chevauchent). Au lieu de prendre les mots un par un, on prend des groupes de mots consécutifs, en avançant d’un mot à chaque fois. Avec des shingles de 3 mots, la phrase le chat mange la souris donne :

le chat mange
   chat mange la
        mange la souris

Les groupes se chevauchent, donc l’ordre des mots est capturé : si on mélange les mots, tous les shingles changent. Sur le même test, la distance passe de 0 à 36 bits sur 63. On est passé de « identiques » à « rien à voir », ce qui est bien le résultat attendu.

Voici le code :

use function Symfony\Component\String\u;

function shingles(string $text, int $size = 3): array
{
    $words = u($text)->lower()->collapseWhitespace()->split(' ');

    if (\count($words) < $size) {
        return [];
    }

    $shingles = [];

    for ($i = 0, $max = \count($words) - $size; $i <= $max; ++$i) {
        $shingles[] = u(' ')->join(\array_slice($words, $i, $size))->toString();
    }

    return $shingles;
}

var_dump(shingles('le chat mange la souris'));

array(3) {
  [0] => string(13) "le chat mange"
  [1] => string(13) "chat mange la"
  [2] => string(15) "mange la souris"
}

Deux détails comptent :

• ->lower() évite que « Livraison » et « livraison » soient comptés comme deux électeurs différents ;
• ->collapseWhitespace() normalise les espaces. Sans lui, un simple retour à la ligne dans le HTML suffirait à créer un shingle bidon.

Notez enfin qu’un document de N mots produit N – 2 shingles avec $size = 3. Chaque mot apparaît dans 3 shingles au plus, donc changer un mot ne modifie que 3 électeurs.

Section intitulée etape-2-hacher-chaque-shingleÉtape 2 : hacher chaque shingle

Chaque shingle doit maintenant produire ses 64 réponses. On lui applique une fonction de hachage classique (ici l’effet avalanche nous arrange : il garantit que deux shingles différents ont des avis indépendants), puis on lit les bits du résultat.

J’utilise xxh3, disponible nativement depuis PHP 8.1. Ce n’est pas une fonction cryptographique, mais on ne cherche pas à se défendre contre un attaquant : on veut une bonne dispersion, et surtout de la vitesse, puisqu’on l’appelle des centaines de fois par page.

$hash = unpack('J', hash('xxh3', 'le chat mange', true))[1];

printf("%064b\n", $hash);

Le troisième argument de hash() à true demande une sortie binaire (8 octets bruts) plutôt qu’hexadécimale. unpack('J', …) interprète ensuite ces 8 octets comme un entier 64 bits non signé, en Big-endian.

1101000100000011111000001000010101011010001111100011111100000011

Voilà les 64 réponses de ce shingle : oui à la question n°0 (le bit le plus à droite vaut 1), oui à la n°1, non à la n°2, etc.

Section intitulée pourquoi-pas-pas-code-hexdec-codePourquoi pas pas hexdec() ?

Le réflexe naturel serait plutôt d’écrire ceci :

$hash = hexdec(hash('xxh3', $shingle)); // ✗ NON

Et ça ne marche pas :

var_dump(hash('xxh3', 'le chat mange'));       // string(16) "d103e0855a3e3f03"
var_dump(hexdec('d103e0855a3e3f03'));         // float(1.5061128442206372E+19)

hexdec() renvoie un float dès que la valeur dépasse PHP_INT_MAX. Or un float sur 64 bits n’a que 53 bits de mantisse : les 11 bits de poids faible sont perdus. Vos électeurs répondent alors n’importe quoi aux 11 dernières questions, et vous passez la soirée à chercher pourquoi l’algorithme marche mal.

Avec unpack('J', …), on récupère un vrai int. Il sera parfois négatif, PHP n’ayant pas d’entiers non signés, mais ce n’est pas grave : c’est la configuration des bits qui nous intéresse, pas la valeur numérique. Et ($hash >> $bit) & 1 lit correctement n’importe quel bit, même quand le nombre est négatif.

Section intitulée etape-3-compter-les-votesÉtape 3 : compter les votes

On tient un compteur par question, initialisé à zéro. Chaque électeur qui répond « oui » l’incrémente, chaque « non » le décrémente.

$bits = 63;
$votes = array_fill(0, $bits, 0);

foreach ($shingles as $shingle) {
    $hash = unpack('J', hash('xxh3', $shingle, true))[1];

    for ($bit = 0; $bit < $bits; ++$bit) {
        if (1 === (($hash >> $bit) & 1)) {
            ++$votes[$bit];
        } else {
            --$votes[$bit];
        }
    }
}

Le +1 / -1 n’est pas un détail de style. Si on se contentait de compter les « oui », il faudrait ensuite comparer à la moitié du nombre d’électeurs. Avec +1 / -1, le seuil est simplement zéro : un compteur positif signifie que les « oui » l’emportent. C’est plus simple à écrire et à lire.

C’est aussi ici qu’on pourrait pondérer les électeurs. Rien n’oblige à voter par pas de 1 : on peut donner plus de poids aux shingles rares (à la TF-IDF), ou à ceux qui apparaissent dans un <h1>. C’est la version pondérée de SimHash, et c’est une extension naturelle de ce ++$votes[$bit]. Dans notre cas, le vote uniforme suffisait largement.

Section intitulée etape-4-construire-l-empreinteÉtape 4 : construire l’empreinte

Il ne reste qu’à convertir les compteurs en bits :

$fingerprint = 0;

for ($bit = 0; $bit < $bits; ++$bit) {
    if ($votes[$bit] > 0) {
        $fingerprint |= 1 << $bit;
    }
}

1 << $bit fabrique un masque avec un seul bit à 1, à la position voulue, et le |= l’allume dans l’empreinte. Les compteurs négatifs ou nuls laissent le bit à 0.

Section intitulée la-classe-completeLa classe complète

Assemblons tout ça. Voici, à quelques détails près, ce qui tourne en production chez nous. Nous n’utilisons pas symfony/string dans la version finale pour des raisons de performances, je m’en suis servi plus haut pour la lisibilité.

<?php

final class SimHash
{
    public function compute(string $content, int $shingleSize = 3, int $bits = 63): ?int
    {
        $words = preg_split('/\s+/', mb_strtolower(trim($content)), -1, PREG_SPLIT_NO_EMPTY);

        if (\count($words) < $shingleSize) {
            return null;
        }

        $votes = array_fill(0, $bits, 0);

        for ($i = 0, $max = \count($words) - $shingleSize; $i <= $max; ++$i) {
            $shingle = implode(' ', \array_slice($words, $i, $shingleSize));

            $hash = unpack('J', hash('xxh3', $shingle, true))[1];

            for ($bit = 0; $bit < $bits; ++$bit) {
                if (1 === (($hash >> $bit) & 1)) {
                    ++$votes[$bit];
                } else {
                    --$votes[$bit];
                }
            }
        }

        $fingerprint = 0;

        for ($bit = 0; $bit < $bits; ++$bit) {
            if ($votes[$bit] > 0) {
                $fingerprint |= 1 << $bit;
            }
        }

        return $fingerprint;
    }
}

Trente lignes, zéro dépendance, un seul int en sortie. On peut le stocker dans une colonne BIGINT et l’oublier.

Le ?int mérite un mot. Si le texte est plus court que la taille d’un shingle, il n’y a aucun électeur, donc pas d’élection, donc pas d’empreinte. On renvoie null plutôt qu’un 0 qui ressemblerait à une vraie valeur et polluerait toutes nos comparaisons.

Section intitulée comparer-deux-empreintes-la-distance-de-hammingComparer deux empreintes : la distance de Hamming

Nous savons fabriquer des empreintes. Reste à mesurer à quel point deux d’entre elles se ressemblent.

La mesure qui nous intéresse est simple : on compte le nombre de bits qui diffèrent. C’est la distance de Hamming.

A     = 1 0 1 1
B     = 1 0 0 1
        ✓ ✓ ✗ ✓   →  distance = 1

Deux opérations suffisent pour la calculer :

• un XOR (^), qui met à 1 exactement les bits où les deux nombres diffèrent ;
• un décompte des bits à 1 du résultat, opération qu’on appelle popcount.

Section intitulée trois-facons-de-compter-des-bits-en-phpTrois façons de compter des bits en PHP

PHP n’expose pas de popcount natif, contrairement au processeur qui a une instruction dédiée. Il y a donc plusieurs options, et le classement m’a surpris.

// 1. La boucle naïve : on regarde le bit de poids faible, on l'ajoute au total,
//    on décale d'un cran vers la droite, et on recommence jusqu'à épuisement.
function hamming(int $a, int $b): int
{
    $xor = $a ^ $b;
    $distance = 0;

    while (0 !== $xor) {
        $distance += $xor & 1;
        $xor >>= 1;
    }

    return $distance;
}

// 2. Kernighan : $x & ($x - 1) efface le bit à 1 le plus à droite.
//    On ne boucle donc qu'autant de fois qu'il y a de bits à 1.
function hammingKernighan(int $a, int $b): int
{
    $xor = $a ^ $b;
    $distance = 0;

    while (0 !== $xor) {
        $xor &= $xor - 1;
        ++$distance;
    }

    return $distance;
}

// 3. Le tricheur : on délègue tout au moteur.
function hammingSubstr(int $a, int $b): int
{
    return substr_count(decbin($a ^ $b), '1');
}

Sur 200 000 itérations :

Implémentation	Temps
Boucle naïve	0,752 s
Kernighan	0,378 s
substr_count(decbin(...))	0,084 s

Le « tricheur » gagne largement, et c’est logique : les deux autres exécutent leur boucle dans la VM PHP, alors que decbin() et substr_count() sont du C compilé. En PHP, la boucle la plus rapide est celle qu’on n’écrit pas.

Cela dit, dans notre code de production, cette fonction ne sert qu’aux tests unitaires.

Section intitulée est-ce-que-ca-marcheEst-ce que ça marche ?

Vérifions sur un cas réaliste. Prenons une fiche produit de 300 mots environ, et fabriquons quatre variantes :

• promo : la même page, avec une phrase de bandeau promotionnel en plus (28 mots) ;
• ville : la même page, où « Lyon » devient « Bordeaux » (1 mot) ;
• femme : la déclinaison femme du produit (4 expressions changées) ;
• autre : une recette de gâteau au chocolat, qui n’a rien à voir.

Voici les distances de Hamming obtenues, sur 63 bits :

	base	promo	ville	femme	autre
base	0	5	2	5	27
promo	5	0	5	10	22
ville	2	5	0	7	27
femme	5	10	7	0	28
autre	27	27	28	28	0

Le cas qui nous intéressait au départ, un seul mot de différence sur 300, donne une distance de 2. Pour rappel, md5() aurait donné deux empreintes totalement étrangères l’une à l’autre.

Les variantes plus substantielles, une phrase ajoutée ou une déclinaison produit, se situent entre 5 et 10. Elles se ressemblent, mais moins.

Le document sans rapport est à 27, soit un peu moins de la moitié de 63. C’est la valeur théorique attendue : deux documents indépendants ont une chance sur deux de tomber d’accord sur chaque question. Sur 300 paires de textes aléatoires, la moyenne est de 30,8 bits, avec des valeurs entre 20 et 45.

On obtient donc une grille de lecture assez nette :

Distance (sur 63 bits)	Interprétation
0	Même contenu, ou différences infimes
1 à 3	Quasi-doublon
4 à 10	Documents apparentés
~31	Aucun rapport

Section intitulée bien-choisir-ses-parametresBien choisir ses paramètres

Section intitulée la-taille-des-shinglesLa taille des shingles

C’est un arbitrage entre sensibilité et robustesse. Un shingle de 1 mot ignore complètement l’ordre, nous l’avons vu : deux textes aux mots mélangés donnent une distance de 0. Un shingle de 8 mots est si spécifique que la moindre reformulation fait tout basculer.

3 mots est la valeur qu’on retrouve un peu partout dans la littérature, et c’est ce que nous utilisons. Ça capture les tournures de phrase sans être hypersensible.

Section intitulée la-longueur-minimale-du-documentLa longueur minimale du document

C’est le paramètre qu’on oublie, et c’est le plus important. Reprenons l’élection : à 300 votants le résultat est stable, à 5 votants il bascule dès qu’une personne change d’avis.

Même modification, un mot changé, sur des documents de longueur croissante :

Longueur du document	Distance après un mot changé
20 mots	8
50 mots	3
100 mots	5
200 mots	4
500 mots	1
1 000 mots	1
2 000 mots	0

SimHash n’est fiable que sur des textes longs. Sur 20 mots, changer un mot déplace l’empreinte de 8 bits, bien au-delà du seuil que nous allons fixer, alors que les deux textes sont presque identiques. Sur 2 000 mots, la même modification est complètement absorbée.

C’est pour ça que notre code refuse de calculer une empreinte en dessous de 20 mots. En dessous, le résultat est du bruit, et un faux positif dans un rapport SEO coûte plus cher qu’une détection manquée.

Section intitulée le-seuil-de-decisionLe seuil de décision

Reste à trancher : à partir de quelle distance déclare-t-on un quasi-doublon ?

Nous avons retenu 3, la même valeur que dans le papier de Google. Le tableau plus haut montre pourquoi c’est raisonnable : à 3 bits sur 63, on attrape « un mot a changé » (distance 2) sans attraper « c’est une variante du produit » (distance 5). Et on reste très loin des 31 bits du hasard.

Ce seuil dépend de vos données et de ce que vous préférez rater. Montez-le pour ratisser plus large, descendez-le si les faux positifs vous coûtent cher. C’est un réglage empirique, il faut le mesurer sur votre corpus.

Section intitulée 63-bits-pas-6463 bits, pas 64

Vous avez peut-être tiqué sur le $bits = 63 par défaut, alors que je vous parle de 64 bits depuis le début. C’est volontaire :

printf("%d\n", 1 << 62); //  4611686018427387904
printf("%d\n", 1 << 63); // -9223372036854775808  ← aïe

PHP n’a pas d’entiers non signés. Le bit 63 est le bit de signe : l’allumer rend l’empreinte négative. Ça ne casse pas l’algorithme en soi, le XOR et le popcount se moquent du signe, mais ça complique tout le reste de la chaîne :

• le décalage à droite >> propage le bit de signe ;
• la sérialisation JSON devient bizarre ;
• le stockage en base échoue si la colonne est un UNSIGNED BIGINT.

En se limitant aux bits 0 à 62, l’empreinte reste dans [0, PHP_INT_MAX]. Elle rentre sans discussion dans un BIGINT signé, un UInt64 ClickHouse ou un bigint PostgreSQL. On perd un bit sur 64, soit 1,5 % de précision, et on s’épargne toute une catégorie de bugs.

Section intitulée comparer-a-l-echelleComparer à l’échelle

Nous savons calculer des empreintes, mais nous n’avons pas encore trouvé les doublons.

Pour trouver toutes les paires de pages proches, il faut comparer toutes les paires. Avec N pages, ça fait N × (N-1) / 2 comparaisons. Sur un crawl de 1 000 pages, c’est 500 000 comparaisons et PHP s’en sort. Sur 100 000 pages, c’est 5 milliards, et c’est mort.

Il n’y a pas non plus d’astuce d’indexation évidente, parce que la distance de Hamming n’est pas un ordre. Deux empreintes voisines peuvent être numériquement très éloignées : il suffit que ce soit le bit de poids fort qui diffère. Un BETWEEN ou un index B-tree classique ne servent à rien.

Notre solution tient en une phrase : on ne le fait pas en PHP. On laisse la base de données s’en charger. Elle sait faire du XOR et du popcount nativement, sur des colonnes entières, en parallèle, sans jamais rapatrier une ligne en mémoire PHP.

Section intitulée chaque-base-a-sa-fonctionChaque base a sa fonction

Toutes les bases sérieuses savent compter des bits, même MySQL. Il faut juste connaître le nom local de la fonction. Chacune de ces requêtes renvoie exactement les mêmes distances que notre code PHP.

MySQL / MariaDB : BIT_COUNT() fait le popcount, et ^ le XOR.

SELECT a.url, b.url, BIT_COUNT(a.simhash ^ b.simhash) AS distance
FROM page a
JOIN page b ON a.url < b.url
WHERE BIT_COUNT(a.simhash ^ b.simhash) <= 3;

PostgreSQL (14 et plus) : bit_count() existe, mais travaille sur des chaînes de bits, d’où le cast. Attention, le XOR sur les entiers s’écrit # et non ^, qui est l’exponentiation.

SELECT a.url, b.url, bit_count((a.simhash # b.simhash)::bit(64)) AS distance
FROM page a
JOIN page b ON a.url < b.url
WHERE bit_count((a.simhash # b.simhash)::bit(64)) <= 3;

ClickHouse : bitCount() et bitXor(), tout en camelCase.

SELECT a.url, b.url, bitCount(bitXor(a.simhash, b.simhash)) AS distance
FROM page a
JOIN page b ON a.crawlId = b.crawlId
WHERE bitCount(bitXor(a.simhash, b.simhash)) <= 3;

SQLite : c’est le seul de la bande à n’avoir aucun popcount intégré. Il faut enregistrer une fonction utilisateur depuis PHP.

$pdo->sqliteCreateFunction('hamming', static function (int $a, int $b): int {
    return substr_count(decbin($a ^ $b), '1');
}, 2);

Ça fonctionne, mais on repasse par la VM PHP à chaque ligne, et on perd tout l’intérêt de la manœuvre. Pour ce genre de travail, SQLite n’est pas le bon outil.

Section intitulée ce-que-nous-faisons-en-productionCe que nous faisons en production

Chez nous, les données de crawl vivent dans ClickHouse et la détection tourne à la fin du crawl. Le code ressemble à ça :

$sql = <<<'SQL'
    SELECT DISTINCT a.url AS url
    FROM crawl_urls a
    INNER JOIN crawl_urls b ON a.crawlId = b.crawlId
    WHERE
        a.projectId = :projectId
        AND a.crawlId = :crawlId
        AND a.contentSimhash IS NOT NULL
        AND b.contentSimhash IS NOT NULL
        AND a.url != b.url
        AND bitCount(bitXor(a.contentSimhash, b.contentSimhash)) <= :threshold
    SQL;

Trois remarques sur cette requête :

• a.url != b.url évite qu’une page soit son propre doublon. Sa distance à elle-même vaut 0, elle passerait tous les seuils du monde ;
• le IS NOT NULL des deux côtés, c’est notre ?int de tout à l’heure qui revient. Les pages trop courtes n’ont pas d’empreinte, et elles ne doivent pas participer ;
• le SELECT DISTINCT et l’absence de a.url < b.url : ici nous ne cherchons pas les paires, nous voulons marquer les pages concernées d’un drapeau contentNearDuplicated. Chaque page qui a au moins un voisin proche est signalée.

Section intitulée le-garde-fouLe garde-fou

Cette requête reste un produit cartésien. ClickHouse est rapide, mais N² finit toujours par gagner. Nous avons donc mis une limite très bête, mais très efficace :

if ($eligibleCount > CrawlConstants::MAX_URLS_FOR_NEAR_DUPLICATE_DETECTION) {
    $this->logger->info('Skipping near-duplicate content detection: too many eligible URLs.', [
        'crawlId' => $crawl->id,
        'eligibleCount' => $eligibleCount,
    ]);

    return;
}

Au-delà de 5 000 pages, nous ne faisons pas la détection de quasi-doublons. C’est un compromis assumé : cette analyse tourne sur le chemin critique de fin de crawl, et il vaut mieux une fonctionnalité absente qu’un crawl qui ne se termine jamais. La détection de doublons exacts, elle, n’est qu’un GROUP BY : elle continue de tourner quel que soit le volume.

Section intitulée aller-plus-loin-le-principe-des-tiroirsAller plus loin : le principe des tiroirs

Et si 5 000 pages ne suffisaient pas ? Il existe une astuce, décrite dans le papier de Google, qui permet d’indexer les recherches par distance de Hamming.

Le principe des tiroirs dit que si vous rangez 3 chaussettes dans 4 tiroirs, au moins un tiroir est forcément vide.

Appliquons-le. On découpe nos 63 bits en 4 blocs. Si deux empreintes diffèrent d’au plus 3 bits, alors ces 3 bits se répartissent dans au plus 3 blocs, donc au moins un bloc est strictement identique entre les deux empreintes. Et un bloc identique, un index B-tree classique sait le trouver instantanément.

On stocke donc les 4 blocs dans 4 colonnes indexées :

CREATE TABLE page (
    url     text,
    simhash bigint,
    b0 int GENERATED ALWAYS AS ((simhash >> 48) & 32767) STORED,
    b1 int GENERATED ALWAYS AS ((simhash >> 32) & 65535) STORED,
    b2 int GENERATED ALWAYS AS ((simhash >> 16) & 65535) STORED,
    b3 int GENERATED ALWAYS AS (simhash & 65535) STORED
);

CREATE INDEX ON page (b0);
CREATE INDEX ON page (b1);
CREATE INDEX ON page (b2);
CREATE INDEX ON page (b3);

La recherche se fait ensuite en deux temps : un filtrage par index pour récupérer une poignée de candidats, puis une vérification exacte sur ce petit paquet.

SELECT p.url, bit_count((p.simhash # :target)::bit(64)) AS distance
FROM page p
WHERE (
       p.b0 = (:target >> 48) & 32767
    OR p.b1 = (:target >> 32) & 65535
    OR p.b2 = (:target >> 16) & 65535
    OR p.b3 = :target & 65535
  )
  AND bit_count((p.simhash # :target)::bit(64)) <= 3;

Le WHERE avec les OR passe par les index et ne remonte qu’un nombre réduit de lignes. La dernière condition, coûteuse, ne s’applique plus qu’à ces candidats. On est passé d’un balayage complet à une recherche indexée.

Un point mérite d’être souligné : ce filtrage n’a aucun faux négatif. Ce n’est pas une heuristique, c’est une garantie mathématique. Toute paire à distance ≤ 3 partage forcément au moins un bloc. Sur 5 000 paires d’empreintes générées à distance ≤ 3, les 5 000 partagent au moins un bloc identique.

En contrepartie, la méthode ne marche que pour le seuil pour lequel on l’a dimensionnée. Pour un seuil de 3 il faut 4 blocs, pour un seuil de 7 il en faudrait 8, avec 8 index. Le coût en stockage et en écriture grimpe vite. C’est le genre d’optimisation qu’on met en place quand on l’a mesurée nécessaire, pas avant.

Section intitulée ce-que-simhash-ne-sait-pas-faireCe que SimHash ne sait pas faire

Il y a des limites, autant les connaître :

• Ce n’est pas une mesure de similarité fine. SimHash répond « proche » ou « pas proche », pas « similaire à 73 % ». La distance de Hamming approxime la similarité cosinus, mais l’approximation est grossière dans les valeurs intermédiaires. Si vous avez besoin d’un vrai score, il vous faut autre chose ;
• Ça ne comprend rien au sens. Deux textes qui disent la même chose avec des mots différents auront des empreintes sans rapport. SimHash compare des suites de mots, pas des idées. Pour de la similarité sémantique, il faut regarder du côté des embeddings vectoriels, avec un autre budget ;
• Ce n’est pas cryptographique. SimHash est conçu pour que des entrées proches donnent des sorties proches, c’est-à-dire l’inverse des propriétés qu’on attend d’une fonction de hachage sécurisée. Fabriquer une collision est trivial. Ne l’utilisez jamais pour de la sécurité.

Il existe enfin une alternative sérieuse : MinHash, qui approxime la similarité de Jaccard plutôt que la similarité cosinus. Elle donne un score plus exploitable, mais elle demande de stocker plusieurs dizaines de valeurs par document, là où SimHash tient dans un seul entier. Pour poser un drapeau booléen sur des pages web, l’entier unique gagne largement.

Section intitulée conclusionConclusion

SimHash tient en une idée : faire voter les morceaux d’un document, bit par bit. Quelques électeurs qui changent d’avis ne renversent pas le scrutin, donc deux textes proches produisent deux empreintes proches. Le problème du « contenu presque identique » se ramène alors à compter des bits qui diffèrent.

C’est cette réduction qui rend la chose utilisable. Un document devient un BIGINT. La question « ces pages se ressemblent-elles ? » devient BIT_COUNT(a ^ b) <= 3, une expression que MySQL, PostgreSQL et ClickHouse évaluent nativement, sans jamais remonter une ligne jusqu’à PHP.

Chez nous, ça représente trente lignes de PHP à l’écriture, une requête SQL à la lecture, et un garde-fou à 5 000 URL pour dormir tranquille. Ce n’est ni sophistiqué ni parfait, mais ça fonctionne, ça se relit, et ça détecte effectivement les fiches produit qui ne diffèrent que par le nom d’une ville.

Un algorithme de 2002 qui fait toujours le travail. Pas mal non ?