Buscador de Duplicatas de Texto: Algoritmo

Esta postagem é sobre o desenvolvimento da ferramenta de busca de duplicados. Para downloads e instruções sobre como usá-la, veja esta página

Na publicação anterior, definimos os requisitos e a interface para nosso buscador de duplicatas. Agora é hora de prosseguir para o algoritmo. Neste artigo, vou percorrer as ideias centrais e fornecer demonstrações interativas para experimentar diretamente no navegador.

Conceito central

Para encontrar fragmentos de texto similares de forma eficiente, precisamos resolver dois problemas:

1. Representação – como representamos o texto para que textos similares tenham representações similares?
2. Busca – como encontramos rapidamente itens similares sem comparar cada par?

A abordagem que usaremos é baseada em n-gramas (grupos de caracteres consecutivos). Especificamente, usaremos trigramas, ou n-gramas de comprimento 3. A intuição é simples: textos similares compartilham muitas das mesmas sequências curtas de caracteres.

Dividindo em n-gramas

Um trigrama é uma sequência de três caracteres consecutivos. Para gerar trigramas a partir do texto, deslizamos uma janela de tamanho 3 através da string:

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;
}

Por exemplo, o texto "hello" produz os seguintes trigramas: "hel" , "ell" , "llo" .

Experimente você mesmo:

Esta representação tem uma propriedade útil: se dois textos são similares, eles compartilharão muitos trigramas. Mesmo que os textos difiram ligeiramente, a maioria dos trigramas permanecerá a mesma.

Construindo um índice invertido

Comparar cada fragmento de texto contra todos os outros seria muito lento – a complexidade de tempo de tal operação é O(n²), o que é impraticável para grandes conjuntos de dados. Em vez disso, construiremos um índice invertido que mapeia cada trigrama para os fragmentos que o contêm:

// 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);
    });
}

Tente adicionar alguns fragmentos de texto para ver como são indexados:

Observe como fragmentos com conteúdo similar compartilham muitas entradas de índice. Isso é o que torna a busca eficiente: podemos usar o índice para encontrar rapidamente fragmentos que compartilham trigramas com uma consulta dada.

Calculando a similaridade

Em seguida, precisamos de uma forma de medir quão similares são dois textos. Como métrica, usaremos a sobreposição de seus conjuntos de trigramas:

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;
}

A fórmula é:

onde A e B são os tamanhos dos conjuntos de trigramas. Isso nos dá um valor entre 0 (completamente diferentes) e 1 (idênticos).

Experimente com diferentes textos para ver como a similaridade muda:

Observe que:

• Textos idênticos pontuam 100%
• Textos com diferenças menores ainda pontuam alto
• Textos completamente diferentes pontuam perto de 0%

Encontrando duplicatas

Vamos juntar as peças. O algoritmo funciona da seguinte forma:

1. Indexar todos os fragmentos – para cada fragmento, gerar trigramas e adicioná-los ao índice invertido (feito uma vez por conjunto de dados)
2. Encontrar candidatos – para um fragmento dado, usar o índice para encontrar fragmentos com conjuntos de trigramas sobrepostos
3. Calcular similaridade – para cada candidato, calcular a pontuação de similaridade
4. Filtrar por limite – manter apenas os pares acima da similaridade mínima

Uma implementação simplificada em JavaScript seria algo assim:

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;
}

Aqui está uma demonstração interativa. Adicione seus próprios fragmentos de texto e ajuste o limite de similaridade para ver duplicatas detectadas em tempo real:

Próximos passos

O código JavaScript neste artigo demonstra o algoritmo central. Nas próximas publicações, veremos a implementação real da ferramenta em Kotlin e exploraremos execução paralela e outras otimizações que ela usa.

Até a próxima!

• Feito por Igor Kulakov. Divirta-se!
• Localizador de duplicados

• Inscreva-se

• 
• 
• 
•