Dec 12, 2025

all posts ->

前回の投稿では、 重複検出ツールの要件とインターフェースを定義しました。 今回はアルゴリズムに進みます。 この記事では、 核となるアイデアを解説し、ブラウザで直接試せるインタラクティブなデモを提供します。

核となるコンセプト

類似テキストフラグメントを効率的に見つけるには、2つの問題を解決する必要があります：

1. 表現 – 類似テキストが類似した表現を持つようにするには？
2. 検索 – すべてのペアを比較せずに類似アイテムを素早く見つけるには？

私たちが使用するアプローチはN-gram （連続する文字のグループ）に基づいています。具体的には、長さ3のN-gramであるトライグラムを使用します。 直感的に理解すると、類似テキストは同じ短い文字列を多く共有しています。

N-gramへの分割

トライグラムは3つの連続する文字の列です。 テキストからトライグラムを生成するには、サイズ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" 。

自分で試してみてください：

この表現には便利な特性があります： 2つのテキストが類似している場合、多くのトライグラムを共有します。 テキストがわずかに異なっていても、ほとんどのトライグラムは同じままです。

転置インデックスの構築

すべてのテキストチャンクを互いに比較するのは遅すぎます – そのような操作の時間計算量は 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);
    });
}

テキストチャンクを追加して、どのようにインデックスされるか試してみてください：

類似コンテンツを持つチャンクが多くのインデックスエントリを共有していることに注目してください。 これが検索を効率的にするものです：インデックスを使用して、 与えられたクエリとトライグラムを共有するチャンクを素早く見つけることができます。

類似度の計算

次に、2つのテキストがどれほど類似しているかを測定する方法が必要です。 メトリクスとして、トライグラムセットの重なりを使用します：

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. すべてのチャンクをインデックス化 – 各チャンクについて、トライグラムを生成し転置インデックスに追加（データセットごとに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 ->

---

• イゴール・クラコフによって作られました。楽しんでください！
• 重複検索

• 購読する

• 
• 
• 
•