텍스트 중복 검색기: 알고리즘

이 게시물은 중복 찾기 도구 개발에 관한 것입니다. 다운로드 및 사용 방법에 대한 지침은 이 페이지

이전 게시물에서 중복 검색기의 요구 사항과 인터페이스를 정의했습니다. 이제 알고리즘으로 넘어갈 시간입니다. 이 글에서는 핵심 아이디어를 살펴보고 브라우저에서 직접 실험할 수 있는 대화형 데모를 제공합니다.

핵심 개념

유사한 텍스트 조각을 효율적으로 찾으려면 두 가지 문제를 해결해야 합니다:

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으로 된 실제 도구 구현을 살펴보고 병렬 실행 및 기타 최적화를 탐구합니다.

다음에 만나요!

• Igor Kulakov에 의해 만들어졌습니다. 즐겨주세요!
• 중복 검색기

• 구독

• 
• 
• 
•