라빈 카프(Rabin-Karp) 알고리즘

1. 라빈 카프 알고리즘이란?

특이한 문자열 매칭 알고리즘으로, 항상 빠르진 않으나 일반적인 경우 빠르게 작동하는 간단한 문자열 매칭 알고리즘이다. 해시(Hash) 기법을 사용하는데, 이 해시란 일반적으로 긴 데이터를 그것을 상징하는 짧은 데이터로 바꾸는 기법이다. 상징하는 데이터로 바꾸어 처리한다는 점에서 단순 해시 알고리즘의 경우 연산 속도가 O(1)에 달한다는 장점이 존재한다.

 

단순히 문자열을 비교하는 Native Search의 경우, 시간 복잡도가 O(NM)이 발생하나, 라빈 카프 알고리즘을 사용하면 평균적으로 O(N)으로 시간 복잡도를 단축시킬 수 있다.

 

2. 구현방식

우선, 해시 계산법은 다음과 같다.

문자열 AACBDDABC에서 패턴 ACB가 발견되는지를 라빈카프 알고리즘을 통해 탐색한다.

 

검색 대상	A	A	C	B	D	D	A	B	C
패턴	A	C	B

 

검색대상 AAC의 해시 값 = 65 * (3 ^ 2) + 65 * (3 ^ 1) + 67 * (3 ^ 0) = 847

패턴 ACB의 해시 값 = 65 * (3 ^ 2) + 67 * (3 ^ 1) + 66 * (3 ^ 0) = 852

해시 값에 차이가 나기 때문에 틀렸다.

 

검색 대상	A	A	C	B	D	D	A	B	C
패턴		A	C	B

 

검색대상 ACB의 해시 값 = 852

패턴 ACB의 해시 값 = 852

해시 값이 같기에 맞았다.

 

검색대상 문자열의 해시 값은 지정한 수 * (검색대상 문자열 해시 값 - 맨 앞 문자열 값 * 지정한 수 * 제곱수) + 새로 탐색된 문자열 값이다.

 

 

여기서 지정한 수는 자신이 임의로 정의한 수 x이다. 뭐든 상관없지만 보통 2를 사용한다고는 한다. 라빈카프 알고리즘을 정리한 글마다 달라서 혼동이 올 수 있지만 이 임의로 지정한 수는 무엇을 넣든간에 자신이 지정한 것으로 자신이 작성한 알고리즘 내에서 변경되지만 않으면 되는 것 같다.

 

처음 검색대상은 AAC, 이후 ACB였는데 이 경우엔 다음과 같이 보면 된다.

AAC -> ACB 해시값 구하는 법 = 3 * (847 - 65 * 3 ^ 2) + 66 = 852

 

빠지는 A와 추가되는 B를 제외한 AC는 기존에 이미 계산한 값이기 때문에 빠지고, 추가되는 값만 연산하면 된다는 원리 때문에 문자열을 빠르게 탐색하기 좋은 알고리즘이라고 한다.

 

물론 해시값으로 사용하기 때문에 다른 문자열임에도 같은 해시값이 나올 수 있다. 이런 현상을 충돌(Collision)현상이라고 한다.

 

또한, 해시 값을 구하는 과정에서 패턴문자열이 길어짐에 따라 자료형의 범위를 넘어가 오버플로우 날 수도 있는데 이를 방지하기 위해 MOD(모듈러 연산)을 활용한다. MOD없이 진행해도 동일한 간격으로 음수, 양수를 왔다갔다하므로 해시 값 자체는 동일하다고 한다.

 

3. 동작 순서

1. 탐색 대상 문자열은 M이고 M의 길이가 ML, 패턴 문자열이 N이고 N의 길이가 NL이라고 하자.
2. M의 첫 인덱스부터 NL만큼 문자열을 잘라서 해시 값을 계산한다.
3. N의 해시 값을 계산한다.
4. 두 해시 값을 비교하고 만약 같다면 N이 M에 존재하는 것으로 간주한다.
5. 만약 같지 않다면 M의 인덱스를 증가시켜 해시 값을 다시 계산하고 4번 과정으로 돌아가 반복한다.
6. M을 끝까지 탐색했음에도 N이 존재하지 않는다면 N이 M에 존재하지 않는 것으로 간주한다.

 

4. 특징

1. Rolling Hash를 사용하여 이전에 구했던 값을 재사용한다.
2. 해시값을 빠르게 계산하기 위해 사용하는 해시 함수는 Rabin fingerprint

 

5. 코드

위에서도 설명했듯이 코드는 MOD를 사용하냐 안하느냐 두 방식으로 짜여질 수 있다.

 

MOD 연산을 사용하지 않는 경우

fun main() {
    val text = "AABDCDABD"
    val pattern = "ABD"
    val idx = rabinKarp(text, pattern)

    println(idx)
    for (cur in idx) {
        println(text.slice(cur - 1 .. cur - 2 + pattern.length))
    }
}

fun rabinKarp(text: String, pattern: String): List<Int> {
    var textHash = 0
    var patternHash = 0
    var power = 1

    val textLen = text.length
    val patternLen = pattern.length

    // 패턴이 일치하는 위치를 저장할 리스트
    val idxList = mutableListOf<Int>()

    for (i in 0..textLen - patternLen) {
        if (i == 0) {
            // 전체 문자열에 첫 파트의 Hash 코드 구하기, 패턴 문자열 Hash 코드 구하기
            for (j in 0 until patternLen) {
                // charAt안의 숫자는 둘 다 동일해야 하므로 patterLen을 써줘야 하는 것에 주의하자.
                // 또한 오른쪽 숫자부터 왼쪽으로 power를 높게 적용해야 아랫식이 적용되므로 이 또한 유의하자.
                textHash += text[patternLen - 1 - j].code * power
                patternHash += pattern[patternLen - 1 - j].code * power

                // power: 가장 앞에 있는 문자의 해시 값을 구할 때의 power 값으로 고정
                if (j < patternLen - 1) power *= 2
            }
        } else {
            // 긴글 Hash 값 = 2 * (이전 파트 Hash 값 - 이전 파트에서 가장 앞에 있는 문자) + 새롭게 들어운 문자
            textHash = (textHash - text[i - 1].code * power) * 2 + text[i + patternLen - 1].code
        }

        // Hash 코드 일치
        if (textHash == patternHash) {
            var found = true

            // 다시 한번 문자열이 맞는지 검사
            for (j in 0 until patternLen) {
                if (text[i + j] != pattern[j]) {
                    found = false
                    break
                }
            }
            if (found) {
                idxList.add(i + 1)
            }
        }
    }
    return idxList
}

 

코드 실행시 결과는 다음과 같이 도출된다.

[2, 7]
ABD
ABD

 

val idx =  rabinKarp(text, pattern)

은 해당 함수의 마지막을 보면 idxList로 반환하므로 list형태이다. 이 idxList는 패턴이 일치하는 위치의 idx를 저장하기 때문에 이 idx를 잘 사용하면 text에서 slice 했을때 pattern의 시작과 끝 idx를 살펴볼 수 있다.

 

 

MOD 연산을 사용하는 경우

fun main() {
    val text = "AABDCDABD"
    val pattern = "ABD"
    val idx = rabinKarp(text, pattern)

    println(idx)
    for (cur in idx) {
        println(text.slice(cur - 1 .. cur - 2 + pattern.length))
    }
}

const val mod = 100000007

fun rabinKarp(text: String, pattern: String): List<Int> {
    var textHash = 0L
    var patternHash = 0L
    var power = 1L

    val textLen = text.length
    val patternLen = pattern.length

    val idxList = mutableListOf<Int>()

    for (i in 0..textLen - patternLen) {
        if (i == 0) {
            for (j in 0 until patternLen) {
                textHash = (textHash + (text[patternLen - 1- j].code * power)) % mod
                patternHash = (patternHash + (pattern[patternLen - 1 - j].code * power)) % mod

                if (j < patternLen - 1) power = (power % mod * 31) % mod
            }
        } else {
            textHash = (31 * textHash % mod - 31 * text[i - 1].code * power % mod + text[i + patternLen - 1].code) % mod
        }

        if (textHash == patternHash) {
            var found = true

            for (j in 0 until patternLen) {
                if (text[i + j] != pattern[j]) {
                    found = false
                    break
                }
            }

            if (found) idxList.add(i + 1)
        }
    }

    return idxList
}