4.6 Rabin-Karp’s algorithm(라빈-카프 알고리즘)

CS - 4. String Search and Manipulations - 4.6. Rabin-Karp's algorithm

Rabin-Karp’s algorithm

Rabin-Karp algorithm is a string searching algorithm that uses hashing to find any one of a set of pattern strings in a text. For strings of average length n, it performs in O(n+m) time with O(m) space, where m is the length of the pattern. It is often used in bioinformatics to search for DNA patterns.

라빈-카프 알고리즘은 해싱을 사용해 텍스트에서 패턴 문자열 세트 중 하나를 찾는 문자열 검색 알고리즘입니다. 평균 길이가 n인 문자열의 경우, O(m) 공간에서 O(n+m) 시간 내에 수행되며, 여기서 m은 패턴의 길이입니다. 생물 정보학에서 DNA 패턴을 검색하는 데 자주 사용됩니다.

 

 

라빈-카프 알고리즘(Rabin-Karp's algorithm)은 문자열 검색 알고리즘 중 하나로, 주로 두 개의 문자열에서 특정 패턴이 어디에 위치하는지 찾는데 사용됩니다. 이 알고리즘이 특별한 이유 중 하나는 해싱을 사용하여 빠르고 효율적인 문자열 비교를 가능하게 한다는 점입니다.

 

라빈-카프 알고리즘의 작동과정은 이렇습니다.

1. 패턴 문자열의 해시 값을 계산합니다. 이 값은 고정된 길이의 숫자로, 패턴 문자열을 대표합니다.
2. 텍스트 문자열의 첫 부분에서 시작하여, 패턴 문자열과 같은 길이의 부분 문자열의 해시 값을 계산합니다.
3. 두 해시 값이 일치하면, 해당 위치에서 문자 단위로 패턴과 부분 문자열을 비교합니다. 이는 해시 충돌로 인해 다른 문자열이 동일한 해시 값을 가질 수 있기 때문입니다.
4. 만약 문자열이 일치하지 않으면, 텍스트의 부분 문자열을 한 문자 씩 이동하면서, 이전 해시 값을 업데이트하고 다시 비교합니다. 이 과정은 텍스트의 끝에 도달할 때까지 반복됩니다.

 

라빈-카프 알고리즘의 성능은 해시 함수와 해시 충돌 처리 방법에 크게 의존합니다. 좋은 해시 함수는 충돌을 최소화하며, 충돌이 발생하더라도 효율적으로 처리할 수 있어야 합니다. 이 알고리즘의 시간 복잡도는 최악의 경우에는 O(nm)이지만, 평균적으로는 O(n+m)입니다.

 

 

시간복잡도를 좀더 자세히 설명해보겠습니다.

O(nm)에서 n은 텍스트 길이, m은 패턴의 길이입니다. 이는 패턴의 해시를 계산하는데 O(m), 텍스트를 도는데 O(n)이 걸립니다. 따라서 패턴의 해시를 한번 계산한 후, 텍스트를 한 번만 훑어도 되므로, 평균 시간복잡도는 O(n+m)입니다.

 

그럼 최악의 경우는 어떨까요?

모든 텍스트의 부분 문자열이 패턴과 해시 값이 같을 경우, 각 부분 문자열에 대해 문자 단위로 비교를 수행해야 하므로 시간 복잡도는 O(nm)이 됩니다.

 

예시로 텍스트가 'AAAAAA...'와 같이 모든 문자가 'A'로 구성되어 있고, 검색 패턴이 'AAA' 이라고 가정하겠습니다. 이 경우, 모든 텍스트의 부분 문자열의 해시 갑싱 패턴의 해시 값과 동일합니다. 따라서 각 부분 문자열에 대해 문자 단위로 비교를 수행해야 하므로, 이 경우의 시간 복잡도는 O(nm)이 됩니다.

(최악의 경우는 드물긴합니다.)

 

 

In Python

def search(pattern, text):
    pattern_length = len(pattern)
    text_length = len(text)
    pattern_hash = hash(pattern)
    text_hash = hash(text[:pattern_length])
    indices = []

    for i in range(text_length - pattern_length + 1):
        if pattern_hash == text_hash:  # 해시 값이 일치하면 문자열 비교
            if text[i:i+pattern_length] == pattern:
                indices.append(i)  # 패턴이 일치하는 경우 시작 인덱스 추가
        if i < text_length - pattern_length:  # 텍스트를 한 문자씩 이동하며 해시 업데이트
            text_hash = hash(text[i+1:i+pattern_length+1])

    return indices if indices else -1  # 패턴이 문자열에 없는 경우 -1 반환