라빈-카프 알고리즘이란?
문자열 검색에 사용되는 알고리즘 중 하나로, 특정한 문자열이 다른 긴 문자열 안에 존재하는지를 효율적으로 찾는 데 사용됩니다. 이 알고리즘은 미리 지정된 문자열(패턴)을 텍스트 내에서 찾는 데 중점을 둡니다.
동작방식
- 해시 함수 사용: 우선 패턴 문자열의 해시 값을 계산합니다. 해시 함수는 문자열을 숫자로 변환하는 함수로, 같은 입력에 대해서 항상 같은 출력 값을 반환합니다. 이 때, 해시 함수를 선택하는 것은 충돌이 적게 발생하며 계산이 빠른 함수가 좋습니다.
- 해시 계산: 텍스트 내에서 패턴의 길이만큼의 문자열에 대한 해시 값을 계산합니다.
- 비교: 계산된 해시 값과 패턴의 해시 값을 비교합니다. 만약 두 해시 값이 일치한다면, 실제 문자열도 같을 확률이 높기 때문에 해당 위치에서 패턴과 텍스트를 직접 비교합니다.
- 이동: 패턴이 텍스트와 일치하지 않는 경우, 패턴을 한 칸씩 오른쪽으로 이동시키면서 새로운 문자열에 대한 해시 값을 계산하고 비교합니다. 이 과정을 텍스트의 끝까지 반복합니다.
장점
-
해시 기반 검색: 라빈-카프 알고리즘은 해시 함수를 사용하여 패턴을 텍스트와 비교하는데, 해시 값을 미리 계산하면 실제 문자열 비교보다 훨씬 빠른 비교가 가능합니다. 따라서 검색 속도가 빠르고 효율적입니다.
-
패턴 이동: 패턴을 한 칸씩 이동하면서 검색을 수행하므로, 일치하지 않는 위치에서도 부분적으로 일치하는 경우에도 문자열 검색을 계속할 수 있습니다. 이로 인해 유연한 검색이 가능합니다.
-
대량 텍스트 검색: 라빈-카프 알고리즘은 대량의 텍스트에서 특정 패턴을 검색하는 데 뛰어난 성능을 보입니다. 해시 값을 사용하므로 텍스트의 크기에 크게 영향받지 않으면서도 효율적인 검색이 가능합니다.
단점
-
해시 충돌: 해시 함수의 충돌이 발생할 수 있습니다. 다시 말해, 다른 패턴이 동일한 해시 값으로 매핑되는 경우가 발생할 수 있습니다. 이 경우 실제 문자열 비교를 통해 정확한 일치를 확인해야 하므로 성능이 저하될 수 있습니다.
-
해시 함수 선택: 적절한 해시 함수를 선택하는 것이 중요합니다. 해시 함수의 성능과 충돌 가능성이 알고리즘의 효율성에 직접적인 영향을 미치므로, 적절한 함수 선택과 최적화가 필요합니다.
-
패턴 길이: 패턴 길이가 길어질수록 해시 값 계산이 복잡해지고 충돌 가능성이 높아집니다. 이로 인해 알고리즘의 효율성이 감소할 수 있습니다.
-
최악의 경우 성능: 일부 특정한 상황에서는 해시 충돌이 잦아져서 최악의 경우 성능이 저하될 수 있습니다.
구현
def rabin_karp_search(text, pattern):
prime = 101 # 선택한 소수
text_len = len(text)
pattern_len = len(pattern)
pattern_hash = sum(ord(pattern[i]) * (prime ** (pattern_len - i - 1)) for i in range(pattern_len))
for i in range(text_len - pattern_len + 1):
text_hash = sum(ord(text[i + j]) * (prime ** (pattern_len - j - 1)) for j in range(pattern_len))
if text_hash == pattern_hash and text[i:i+pattern_len] == pattern:
print("Pattern found at index", i)
# 해시 충돌 방지를 위해 다음 해시 계산을 위해 이전 해시 값을 활용
if i < text_len - pattern_len:
text_hash = (text_hash - ord(text[i]) * (prime ** (pattern_len - 1))) * prime + ord(text[i + pattern_len])
text_hash %= prime
text = "ABABCABABABCABABABC"
pattern = "ABABC"
rabin_karp_search(text, pattern)