Buscador de Duplicados de Texto: Algoritmo
Otros idiomas: English Français Deutsch 日本語 한국어 Português 中文
En la publicación anterior, definimos los requisitos y la interfaz para nuestro buscador de duplicados. Ahora es momento de proceder al algoritmo. En este artículo, recorreré las ideas centrales y proporcionaré demostraciones interactivas para experimentar directamente en el navegador.
Concepto central
Para encontrar fragmentos de texto similares de manera eficiente, necesitamos resolver dos problemas:
- Representación – ¿cómo representamos el texto para que textos similares tengan representaciones similares?
- Búsqueda – ¿cómo encontramos rápidamente elementos similares sin comparar cada par?
El enfoque que usaremos se basa en n-gramas (grupos de caracteres consecutivos). Específicamente, usaremos trigramas, o n-gramas de longitud 3. La intuición es simple: textos similares comparten muchas de las mismas secuencias cortas de caracteres.
División en n-gramas
Un trigrama es una secuencia de tres caracteres consecutivos. Para generar trigramas a partir del texto, deslizamos una ventana de tamaño 3 a través de la cadena:
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 ejemplo, el texto "hello"
produce los siguientes trigramas: "hel" ,
"ell" ,
"llo" .
Pruébalo tú mismo:
Esta representación tiene una propiedad útil: si dos textos son similares, compartirán muchos trigramas. Incluso si los textos difieren ligeramente, la mayoría de los trigramas permanecerán iguales.
Construyendo un índice invertido
Comparar cada fragmento de texto contra todos los demás sería demasiado lento – la complejidad temporal de tal operación es O(n²), lo cual es impracticable para conjuntos de datos grandes. En su lugar, construiremos un índice invertido que mapea cada trigrama a los fragmentos que lo contienen:
// 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);
});
}Intenta añadir algunos fragmentos de texto para ver cómo se indexan:
Observa cómo los fragmentos con contenido similar comparten muchas entradas de índice. Esto es lo que hace la búsqueda eficiente: podemos usar el índice para encontrar rápidamente fragmentos que comparten trigramas con una consulta dada.
Calculando la similitud
A continuación, necesitamos una forma de medir cuán similares son dos textos. Como métrica, usaremos la superposición de sus 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;
}La fórmula es:
donde A y B son los tamaños de los conjuntos de trigramas. Esto nos da un valor entre 0 (completamente diferentes) y 1 (idénticos).
Experimenta con diferentes textos para ver cómo cambia la similitud:
Observa que:
- Los textos idénticos puntúan 100%
- Los textos con diferencias menores aún puntúan alto
- Los textos completamente diferentes puntúan cerca del 0%
Encontrando duplicados
Pongamos las piezas juntas. El algoritmo funciona de la siguiente manera:
- Indexar todos los fragmentos – para cada fragmento, generar trigramas y añadirlos al índice invertido (se hace una vez por conjunto de datos)
- Encontrar candidatos – para un fragmento dado, usar el índice para encontrar fragmentos con conjuntos de trigramas superpuestos
- Calcular similitud – para cada candidato, calcular la puntuación de similitud
- Filtrar por umbral – mantener solo los pares por encima de la similitud mínima
Una implementación simplificada en JavaScript se vería algo así:
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;
}Aquí hay una demostración interactiva. Añade tus propios fragmentos de texto y ajusta el umbral de similitud para ver duplicados detectados en tiempo real:
Próximos pasos
El código JavaScript en este artículo demuestra el algoritmo central. En las próximas publicaciones, veremos la implementación real de la herramienta en Kotlin y exploraremos la ejecución paralela y otras optimizaciones que utiliza.
¡Nos vemos la próxima vez!
