문자열 탐색 알고리즘은 주어진 문자열에서 특정 패턴을 찾는 데 사용되는 알고리즘입니다. 이 알고리즘들은 대량의 텍스트에서 문자열을 효율적으로 검색하는 방법을 제공하여 많은 응용 분야에서 활용됩니다. 이번 글에서는 가장 널리 알려진 두 가지 문자열 탐색 알고리즘인 KMP(Knuth-Morris-Pratt)와 보이어-무어 알고리즘에 대해 알아보겠습니다.
1. KMP (Knuth-Morris-Pratt) 알고리즘
KMP 알고리즘은 문자열 검색에 사용되는 알고리즘으로, 문자열의 부분 일치를 활용하여 비효율적인 탐색을 효율적으로 건너뛰는 기법입니다. KMP 알고리즘의 핵심은 실패 함수(failure function) 이라는 개념으로, 이 함수를 통해 비교 중인 문자열의 일치 여부에 따라 비교 위치를 조정합니다.
KMP 알고리즘의 핵심 아이디어는 패턴 내에서 접두사와 접미사의 일치를 빠르게 찾아서 이를 활용하는 것입니다. 이를 위해 실패 함수를 사용하여 패턴의 접두사와 접미사의 일치 길이를 저장하여 매칭 시간을 최소화합니다.
예시 코드:
def build_failure_function(pattern):
failure = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
if pattern[i] == pattern[j]:
j += 1
failure[i] = j
else:
if j > 0:
j = failure[j-1]
i -= 1
else:
failure[i] = 0
return failure
def kmp_search(text, pattern):
failure = build_failure_function(pattern)
match_indices = []
i, j = 0, 0
while i < len(text):
if text[i] == pattern[j]:
if j == len(pattern) - 1:
match_indices.append(i - j)
j = failure[j]
i += 1
else:
i += 1
j += 1
else:
if j > 0:
j = failure[j-1]
else:
i += 1
return match_indices
# Example usage
text = "ABABACABAABCABABCABACAB"
pattern = "ABABCABAC"
matches = kmp_search(text, pattern)
print("Pattern found at indices:", matches)
위의 예시에서 build_failure_function 함수는 패턴의 실패 함수를 구성하는 함수입니다. kmp_search 함수는 KMP 알고리즘을 사용하여 주어진 텍스트에서 패턴을 찾은 뒤, 매칭된 인덱스들을 반환합니다.
2. 보이어-무어 (Boyer-Moore) 알고리즘
보이어-무어 알고리즘은 문자열 검색에 사용되는 다른 방법론입니다. KMP 알고리즘과 마찬가지로 검색 시간을 줄이기 위해 패턴의 일치 여부를 기반으로 비교 위치를 조정합니다.
보이어-무어 알고리즘은 오른쪽에서 왼쪽으로 검색하는 특징을 가지며, 패턴 내에서 오른쪽 끝의 문자와 텍스트 상 위치하는 문자의 일치 여부에 따라 이동 거리를 결정합니다. 이를 통해 비교해야 할 문자들을 최소화하여 효율적인 문자열 탐색을 수행합니다.
예시 코드:
def build_bad_character_table(pattern):
table = {}
for i in range(len(pattern)-1):
table[pattern[i]] = len(pattern) - 1 - i
return table
def boyer_moore_search(text, pattern):
table = build_bad_character_table(pattern)
match_indices = []
i = len(pattern) - 1
while i < len(text):
j = len(pattern) - 1
while j >= 0 and text[i] == pattern[j]:
i -= 1
j -= 1
if j == -1:
match_indices.append(i + 1)
i += len(pattern) * 2 - 1
else:
shift = table.get(text[i], len(pattern))
i += shift
return match_indices
# Example usage
text = "ABABACABAABCABABCABACAB"
pattern = "ABABCABAC"
matches = boyer_moore_search(text, pattern)
print("Pattern found at indices:", matches)
위의 예시에서 build_bad_character_table 함수는 패턴의 나쁜 문자 테이블을 구성하는 함수입니다. boyer_moore_search 함수는 보이어-무어 알고리즘을 사용하여 주어진 텍스트에서 패턴을 찾은 뒤, 매칭된 인덱스들을 반환합니다.
마무리
KMP 알고리즘과 보이어-무어 알고리즘은 문자열 탐색에 널리 사용되는 효율적인 알고리즘들입니다. 이들 알고리즘을 활용하면 대량의 텍스트에서 원하는 패턴을 빠르게 찾을 수 있습니다. Python과 같은 프로그래밍 언어에서는 이러한 알고리즘들을 구현하기 위한 다양한 라이브러리가 존재하며, 개발자는 이를 활용하여 문자열 검색에 시간을 절약할 수 있습니다.