Dec 12, 2025

all posts ->

在上一篇文章中， 我们定义了重复检测工具的需求和接口。 现在是时候进入算法部分了。 在本文中， 我将介绍核心思想，并提供可在浏览器中直接实验的交互式演示。

核心概念

要高效地找到相似的文本片段，我们需要解决两个问题：

1. 表示 – 如何表示文本，使相似的文本具有相似的表示？
2. 搜索 – 如何在不比较每对文本的情况下快速找到相似项？

我们将使用基于N-gram （连续字符组）的方法。具体来说，我们将使用三元组，即长度为3的N-gram。 直觉很简单：相似的文本共享许多相同的短字符序列。

分割为N-gram

三元组是三个连续字符的序列。 要从文本生成三元组，我们在字符串上滑动一个大小为3的窗口：

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

例如，文本 "hello" 产生以下三元组： "hel" 、 "ell" 、 "llo" 。

自己试试：

这种表示有一个有用的特性： 如果两个文本相似，它们将共享许多三元组。 即使文本略有不同，大多数三元组仍将保持相同。

构建倒排索引

将每个文本块与其他所有块进行比较太慢了 – 这种操作的时间复杂度是 O(n²)，对于大型数据集来说不切实际。 相反，我们将构建一个倒排索引， 将每个三元组映射到包含它的块：

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

尝试添加一些文本块，看看它们是如何被索引的：

注意具有相似内容的块共享许多索引条目。 这就是使搜索高效的原因：我们可以使用索引快速 找到与给定查询共享三元组的块。

计算相似度

接下来，我们需要一种方法来衡量两个文本有多相似。 作为度量标准，我们将使用三元组集合的重叠：

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和B是三元组集合的大小。 这给我们一个介于0（完全不同）和1（相同）之间的值。

尝试不同的文本，看看相似度如何变化：

注意：

• 相同的文本得分100%
• 差异较小的文本仍然得分较高
• 完全不同的文本得分接近0%

查找重复

让我们把所有内容整合在一起。算法的工作原理如下：

1. 索引所有块 – 对于每个块，生成三元组并添加到倒排索引（每个数据集只执行一次）
2. 查找候选项 – 对于给定的块，使用索引查找三元组集合重叠的块
3. 计算相似度 – 对于每个候选项，计算相似度分数
4. 按阈值过滤 – 只保留高于最小相似度的配对

简化的JavaScript实现如下：

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

这是一个交互式演示。添加您自己的文本块并调整相似度 阈值，实时查看检测到的重复：

下一步

本文中的JavaScript代码演示了核心算法。 在接下来的文章中，我们将查看 Kotlin中工具的实际实现， 并探索它使用的并行执行和其他优化。

下次见！

all posts ->

---

• 由 Igor Kulakov 制作。尽情享受！
• 重复查找器

• 订阅

• 
• 
• 
•