Detecteur de Doublons pour Texte : Algorithme

Autres langues : English Español Deutsch 日本語 한국어 Português 中文

Cet article traite du développement de l'outil de recherche de doublons. Pour les téléchargements et les instructions d'utilisation, voir cette page

Dans l’article precedent, nous avons defini les exigences et l’interface pour notre detecteur de doublons. Il est maintenant temps de passer a l’algorithme. Dans cet article, je vais parcourir les idees principales et fournir des demos interactives pour experimenter directement dans le navigateur.

Concept principal

Pour trouver efficacement des fragments de texte similaires, nous devons resoudre deux problemes :

Representation - comment representons-nous le texte pour que des textes similaires aient des representations similaires ?
Recherche - comment trouvons-nous rapidement des elements similaires sans comparer chaque paire ?

L’approche que nous utiliserons est basee sur les n-grammes (groupes de caracteres consecutifs). Plus specifiquement, nous utiliserons des trigrammes, ou n-grammes de longueur 3. L’intuition est simple : des textes similaires partagent beaucoup des memes courtes sequences de caracteres.

Division en n-grammes

Un trigramme est une sequence de trois caracteres consecutifs. Pour generer des trigrammes a partir d’un texte, nous faisons glisser une fenetre de taille 3 sur la chaine :

function generateTrigrams(text) {
    const trigrams = new Set();
    for (let i = 0; i <= text.length - 3; i++) {
        trigrams.add(text.substring(i, i + 3));
    }
    return trigrams;
}

Par exemple, le texte "hello" produit les trigrammes suivants : "hel" , "ell" , "llo" .

Essayez par vous-meme :

Enter text:

Trigrams

Cette representation a une propriete utile : si deux textes sont similaires, ils partageront de nombreux trigrammes. Meme si les textes different legerement, la plupart des trigrammes resteront les memes.

Construction d’un index inverse

Comparer chaque fragment de texte avec chaque autre fragment serait trop lent - la complexite temporelle d’une telle operation est O(n²), ce qui est impratique pour de grands ensembles de donnees. Au lieu de cela, nous allons construire un index inverse qui associe chaque trigramme aux fragments qui le contiennent :

// Map: trigram → list of chunk IDs containing that trigram
const index = new Map();

function addToIndex(chunkId, text) {
    const trigrams = generateTrigrams(text.toLowerCase());
    trigrams.forEach(trigram => {
        if (!index.has(trigram)) {
            index.set(trigram, []);
        }
        index.get(trigram).push(chunkId);
    });
}

Essayez d’ajouter quelques fragments de texte pour voir comment ils sont indexes :

Add a text chunk:

📄 Text Chunks

📑 Inverted Index (trigram → chunk IDs)

Remarquez comment les fragments avec un contenu similaire partagent de nombreuses entrees d’index. C’est ce qui rend la recherche efficace : nous pouvons utiliser l’index pour trouver rapidement les fragments qui partagent des trigrammes avec une requete donnee.

Calcul de la similarite

Ensuite, nous avons besoin d’un moyen de mesurer a quel point deux textes sont similaires. Comme metrique, nous utiliserons le chevauchement de leurs ensembles de trigrammes :

function calculateSimilarity(trigrams1, trigrams2) {
    // Count common trigrams
    const intersection = [...trigrams1]
        .filter(t => trigrams2.has(t));

    // Similarity = common / max(size1, size2)
    const maxSize = Math.max(trigrams1.size, trigrams2.size);
    return intersection.length / maxSize;
}

La formule est :

Similarite = intersection / max(A, B)

ou A et B sont les tailles des ensembles de trigrammes. Cela nous donne une valeur entre 0 (completement differents) et 1 (identiques).

Experimentez avec differents textes pour voir comment la similarite change :

Remarquez que :

Les textes identiques obtiennent un score de 100%
Les textes avec des differences mineures obtiennent toujours un score eleve
Les textes completement differents obtiennent un score proche de 0%

Trouver les doublons

Assemblons les pieces. L’algorithme fonctionne comme suit :

Indexer tous les fragments - pour chaque fragment, generer les trigrammes et les ajouter a l’index inverse (fait une fois par ensemble de donnees)
Trouver les candidats - pour un fragment donne, utiliser l’index pour trouver les fragments avec des ensembles de trigrammes qui se chevauchent
Calculer la similarite - pour chaque candidat, calculer le score de similarite
Filtrer par seuil - garder uniquement les paires au-dessus de la similarite minimale

Une implementation JavaScript simplifiee ressemblerait a ceci :

function findDuplicates(minSimilarity) {
    const duplicates = [];

    for (const chunk of chunks) {
        const candidates = findCandidates(chunk.id, chunk.trigrams);

        for (const candidateId of candidates) {
            const candidate = chunks[candidateId];
            const similarity = calculateSimilarity(
                chunk.trigrams,
                candidate.trigrams
            );

            if (similarity >= minSimilarity) {
                duplicates.push({
                    chunk1: chunk,
                    chunk2: candidate,
                    similarity
                });
            }
        }
    }

    return duplicates;
}

Voici une demo interactive. Ajoutez vos propres fragments de texte et ajustez le seuil de similarite pour voir les doublons detectes en temps reel :

Min similarity threshold: 50%

📄 Text Chunks

🔍 Duplicate Pairs Found

Prochaines etapes

Le code JavaScript dans cet article demontre l’algorithme principal. Dans les prochains articles, nous examinerons l’ implementation reelle de l’outil en Kotlin et explorerons l’execution parallele et d’autres optimisations qu’il utilise.

A la prochaine !

all posts ->