Rabin-Karp

라빈-카프 문자열 검색 알고리즘은 텍스트에서 특정 패턴을 찾는 데 사용된다.

이 알고리즘의 실제 응용 사례로 표절 검출을 들 수 있다. 주어진 원본 자료를 바탕으로, 이 알고리즘은 문서를 빠르게 검색해 원본 자료에 있는 문장이 포함된 부분을 찾아낸다. 이때 대소문자나 구두점과 같은 세부 사항은 무시한다. 찾아야 할 문자열이 많기 때문에 단일 문자열 검색 알고리즘은 비효율적이다.

예제

"큰 개가 여우 위로 뛰어넘었다"라는 텍스트와 "ump"라는 검색 패턴이 주어졌을 때, 이 알고리즘은 13을 반환한다. 먼저 "ump"의 해시 값을 계산한 후, "The"의 해시 값을 계산한다. 두 해시 값이 일치하지 않으면, 윈도우를 한 문자씩 이동시켜 (예: "he ") 이전 해시 값에서 "T"의 해시 값을 빼는 방식으로 진행한다.

알고리즘

라빈-카프 알고리즘은 검색 패턴 크기의 슬라이딩 윈도우를 사용한다. 먼저 검색 패턴의 해시 값을 계산한 후, 텍스트 문자열의 처음 x개 문자(x는 검색 패턴의 길이)의 해시 값을 계산한다. 그런 다음 윈도우를 한 문자씩 이동시키고, 이전 해시 값을 활용해 새로운 해시 값을 빠르게 계산한다. 검색 패턴의 해시 값과 일치하는 해시 값을 발견한 경우에만 두 문자열을 비교해 실제로 일치하는지 확인한다(해시 충돌로 인한 오탐지를 방지하기 위함).

코드 구현

주요 검색 메서드는 다음과 같다. 더 자세한 구현 내용은 rabin-karp.swift 파일에서 확인할 수 있다.

public func search(text: String , pattern: String) -> Int {
    // 문자열을 정수 배열로 변환
    let patternArray = pattern.flatMap { $0.asInt }
    let textArray = text.flatMap { $0.asInt }

    if textArray.count < patternArray.count {
        return -1
    }

    let patternHash = hash(array: patternArray)
    var endIdx = patternArray.count - 1
    let firstChars = Array(textArray[0...endIdx])
    let firstHash = hash(array: firstChars)

    if (patternHash == firstHash) {
        // 해시 충돌이 아닌지 확인
        if firstChars == patternArray {
            return 0
        }
    }

    var prevHash = firstHash
    // 검색할 텍스트를 따라 윈도우를 슬라이드
    for idx in 1...(textArray.count - patternArray.count) {
        endIdx = idx + (patternArray.count - 1)
        let window = Array(textArray[idx...endIdx])
        let windowHash = nextHash(prevHash: prevHash, dropped: textArray[idx - 1], added: textArray[endIdx], patternSize: patternArray.count - 1)

        if windowHash == patternHash {
            if patternArray == window {
                return idx
            }
        }

        prevHash = windowHash
    }

    return -1
}

이 코드는 플레이그라운드에서 다음과 같이 테스트할 수 있다.

  search(text: "The big dog jumped"", "ump")

"ump"는 0 기반 문자열에서 13번째 위치에 있으므로 13을 반환한다.

라빈-카프 문자열 검색 알고리즘

예제

알고리즘

코드 구현

추가 리소스