Duplikatfinder für Text: Algorithmus
Andere Sprachen: English Español Français 日本語 한국어 Português 中文
Im vorherigen Beitrag haben wir die Anforderungen und die Schnittstelle für unseren Duplikatfinder definiert. Jetzt ist es an der Zeit, zum Algorithmus überzugehen. In diesem Artikel werde ich die Kernideen durchgehen und interaktive Demos zum Experimentieren direkt im Browser bereitstellen.
Kernkonzept
Um ähnliche Textfragmente effizient zu finden, müssen wir zwei Probleme lösen:
- Darstellung – wie stellen wir Text dar, sodass ähnliche Texte ähnliche Darstellungen haben?
- Suche – wie finden wir schnell ähnliche Elemente, ohne jedes Paar zu vergleichen?
Der Ansatz, den wir verwenden werden, basiert auf N-Grammen (Gruppen aufeinanderfolgender Zeichen). Genauer gesagt werden wir Trigramme verwenden, also N-Gramme der Länge 3. Die Intuition ist einfach: Ähnliche Texte teilen viele der gleichen kurzen Zeichenfolgen.
Aufteilen in N-Gramme
Ein Trigramm ist eine Sequenz von drei aufeinanderfolgenden Zeichen. Um Trigramme aus Text zu generieren, schieben wir ein Fenster der Größe 3 über die Zeichenkette:
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;
}Zum Beispiel erzeugt der Text "hello"
die folgenden Trigramme: "hel" ,
"ell" ,
"llo" .
Probier es selbst aus:
Diese Darstellung hat eine nützliche Eigenschaft: Wenn zwei Texte ähnlich sind, werden sie viele Trigramme teilen. Selbst wenn sich die Texte leicht unterscheiden, bleiben die meisten Trigramme gleich.
Aufbau eines invertierten Index
Jeden Textblock mit jedem anderen zu vergleichen wäre zu langsam – die Zeitkomplexität einer solchen Operation ist O(n²), was für große Datensätze unpraktisch ist. Stattdessen werden wir einen invertierten Index erstellen, der jedes Trigramm den Blöcken zuordnet, die es enthalten:
// 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);
});
}Versuch, einige Textblöcke hinzuzufügen, um zu sehen, wie sie indiziert werden:
Beachte, wie Blöcke mit ähnlichem Inhalt viele Indexeinträge teilen. Das macht die Suche effizient: Wir können den Index verwenden, um schnell Blöcke zu finden, die Trigramme mit einer gegebenen Abfrage teilen.
Ähnlichkeit berechnen
Als Nächstes brauchen wir eine Möglichkeit zu messen, wie ähnlich zwei Texte sind. Als Metrik werden wir die Überlappung ihrer Trigramm-Mengen verwenden:
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;
}Die Formel lautet:
wobei A und B die Größen der Trigramm-Mengen sind. Dies gibt uns einen Wert zwischen 0 (völlig unterschiedlich) und 1 (identisch).
Experimentier mit verschiedenen Texten, um zu sehen, wie sich die Ähnlichkeit ändert:
Beachte, dass:
- Identische Texte 100% erzielen
- Texte mit geringen Unterschieden immer noch hoch punkten
- Völlig unterschiedliche Texte nahe 0% erzielen
Duplikate finden
Lass uns die Teile zusammenfügen. Der Algorithmus funktioniert wie folgt:
- Alle Blöcke indizieren – für jeden Block Trigramme generieren und zum invertierten Index hinzufügen (einmal pro Datensatz durchgeführt)
- Kandidaten finden – für einen gegebenen Block den Index verwenden, um Blöcke mit überlappenden Trigramm-Mengen zu finden
- Ähnlichkeit berechnen – für jeden Kandidaten den Ähnlichkeitswert berechnen
- Nach Schwellenwert filtern – nur Paare über der Mindestähnlichkeit behalten
Eine vereinfachte JavaScript-Implementierung würde ungefähr so aussehen:
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;
}Hier ist eine interaktive Demo. Füg deine eigenen Textblöcke hinzu und pass den Ähnlichkeits- Schwellenwert an, um Duplikate in Echtzeit erkannt zu sehen:
Nächste Schritte
Der JavaScript-Code in diesem Artikel demonstriert den Kernalgorithmus. In den nächsten Beiträgen werden wir uns die tatsächliche Implementierung des Tools in Kotlin ansehen und die parallele Ausführung und andere Optimierungen erkunden, die es verwendet.
Bis zum nächsten Mal!
