kmp 알고리즘이란
KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 검색을 빠르게 수행하기 위한 알고리즘 중 하나로, 특히 텍스트에서 특정 패턴을 찾는데 사용됩니다. 이 알고리즘은 1977년에 Donald Knuth, Vaughan Pratt 및 James H. Morris에 의해 개발되었습니다. KMP 알고리즘은 문자열 검색의 효율성을 높이기 위해 중복되는 비교 작업을 줄이는 방법을 사용합니다.
일반적으로 문자열 검색 알고리즘은 텍스트와 패턴을 비교하면서 일치하지 않는 위치에서 검색을 다시 시작합니다. 그러나 KMP 알고리즘은 이미 비교한 일부 문자들을 재활용하여 검색을 진행하므로 중복 비교를 피할 수 있습니다.
KMP 알고리즘의 주요 아이디어는 패턴 내에서 일치하지 않는 부분 문자열을 이용하여 텍스트 검색을 어떻게 스킵할지 결정하는 것입니다. 이를 위해 "실패 함수" 또는 "접두사 함수"라 불리는 특별한 배열을 생성합니다. 이 배열은 각 위치에서 패턴의 접두사와 접미사가 일치하는 최대 길이를 저장하며, 이를 활용하여 패턴을 이동시키는데 사용됩니다.
진행과정
- 실패 함수 생성 (Compute Fail Function):
패턴 문자열 내에서 접두사와 접미사의 일치 길이를 저장하는 배열을 생성합니다. 이 배열을 "실패 함수" 또는 "접두사 함수"라고 부릅니다.
예를 들어, 패턴 문자열이 "ABAB"일 경우 실패 함수는 [0, 0, 1, 2]가 됩니다. 이는 첫 번째 문자는 접두사와 접미사가 일치하는 부분이 없으므로 0, 두 번째 문자 'A'는 접두사와 접미사가 일치하는 부분이 없으므로 0, 세 번째 문자 'B'는 접두사 'A'와 접미사 'A'가 일치하는 부분이 1, 네 번째 문자 'A'는 접두사 'ABA'와 접미사 'ABA'가 일치하는 부분이 2임을 나타냅니다.
- 텍스트와 패턴 비교:
이제 텍스트와 패턴을 한 문자씩 비교하면서 검색을 시작합니다. 비교하는 포인터는 텍스트를 순차적으로 탐색하면서 이동하고, 패턴을 일치 여부를 확인하는 포인터는 패턴을 따라 이동합니다.
- 일치하지 않는 경우 (Mismatch):
텍스트와 패턴 문자가 일치하지 않을 경우, 실패 함수를 활용하여 패턴을 어떻게 이동시킬지 결정합니다.
- 실패 함수를 이용하여 패턴 포인터를 이동시킵니다.
- 실패 함수 값이 0이 될 때까지, 패턴을 따라 이동하면서 접두사와 접미사의 일치 여부를 검사합니다.
- 이동할 때마다 실패 함수 값을 이용하여 패턴의 이동 거리를 결정합니다.
- 일치하는 경우 (Match):
텍스트와 패턴 문자가 일치할 경우, 패턴 포인터를 다음 문자로 이동시킵니다.
- 패턴 전체 일치 (Pattern Matched):
패턴 포인터가 패턴의 끝에 도달하면, 전체 패턴이 텍스트 내에서 일치한 것입니다. 이때, 패턴이 시작된 텍스트의 위치(인덱스)를 기록하거나 반환합니다.
- 검색 완료:
텍스트의 끝까지 검색을 완료할 때까지 위 과정을 반복합니다.
장점
-
시간 복잡도: KMP 알고리즘은 평균 및 최악의 경우에도 O(n+m)의 시간 복잡도를 가집니다. 여기서 n은 텍스트의 길이이고, m은 패턴의 길이입니다. 이는 브루트 포스와 비교했을 때 효율적인 성능을 제공합니다.
-
비교 횟수 감소: KMP 알고리즘은 일치하지 않는 부분 문자열을 최소화하여 텍스트와 패턴 간의 비교 횟수를 줄입니다. 이를 통해 중복된 비교를 피하고 검색 속도를 높입니다.
-
미리 계산된 테이블 사용: KMP 알고리즘은 패턴을 분석하여 패턴 내부의 접두사와 접미사를 이용해 미리 계산된 테이블을 생성합니다. 이 테이블을 사용하여 텍스트와 패턴 간의 일치 여부를 판단하며, 이는 중복 계산을 방지하고 검색 속도를 향상시킵니다.
-
일관된 성능: KMP 알고리즘은 입력 데이터의 길이에 상관없이 일관된 성능을 보입니다. 따라서 텍스트와 패턴의 크기가 크더라도 알고리즘의 효율성이 변하지 않습니다.
-
공간 복잡도: KMP 알고리즘의 추가적인 공간 복잡도는 O(m)이며, 이는 패턴의 길이에만 의존합니다. 따라서 메모리 사용량이 제한된 환경에서도 유용하게 사용될 수 있습니다.
-
효율적인 문자열 검색: 텍스트 내에서 패턴을 효율적으로 찾는 데에 사용되므로, 문자열 검색 애플리케이션에서 유용하게 활용될 수 있습니다.
-
다양한 응용 분야: KMP 알고리즘은 문자열 검색 뿐만 아니라 유사성 검사, 데이터 압축, DNA 시퀀싱 등 다양한 분야에서 활용될 수 있습니다.
단점
-
추가 공간 사용: KMP 알고리즘은 미리 계산된 테이블을 저장하기 위해 O(m)의 추가 공간을 필요로 합니다. 이는 패턴의 길이에 비례하는 공간을 추가적으로 사용하게 되므로, 메모리 제한이 있는 상황에서는 고려해야 할 사항입니다.
-
복잡성: KMP 알고리즘은 다른 간단한 문자열 검색 알고리즘(예: 브루트 포스)보다 구현이 조금 복잡할 수 있습니다. 미리 계산된 테이블을 만들고 사용하는 과정 등이 추가되기 때문입니다.
-
패턴 길이와 관련: KMP 알고리즘의 성능은 패턴의 길이에 영향을 받을 수 있습니다. 만약 패턴이 길어진다면 미리 계산된 테이블의 크기도 커지게 되어 공간 사용이 증가하게 됩니다.
-
순차적 액세스: KMP 알고리즘은 텍스트와 패턴을 순차적으로 비교하며 검색을 수행합니다. 이는 어떤 상황에서는 메모리 캐시를 활용하지 못하고 연속적인 액세스로 인해 성능이 저하될 수 있습니다.
-
비교 연산 제한: KMP 알고리즘은 문자 단위 비교 연산에 의존합니다. 따라서 텍스트와 패턴이 아스키나 유니코드 문자가 아닌 다른 형태의 데이터로 구성되어 있다면 알고리즘을 수정해야 할 수도 있습니다.
-
부분 일치에 대한 처리: KMP 알고리즘은 패턴의 부분 일치를 처리하기 위해 미리 계산된 테이블을 사용합니다. 하지만 어떤 경우에는 부분 일치를 무시하고 스킵해야 할 수도 있습니다. 이런 상황에 대한 처리가 약간 복잡할 수 있습니다.
구현
def compute_lps_array(pattern):
length = 0
i = 1
lps = [0] * len(pattern)
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
def kmp_search(text, pattern):
n = len(text)
m = len(pattern)
lps = compute_lps_array(pattern)
i = 0 # 인덱스 i는 텍스트 내 현재 비교 위치
j = 0 # 인덱스 j는 패턴 내 현재 비교 위치
while i < n:
if pattern[j] == text[i]:
i += 1
j += 1
if j == m:
print("패턴이 텍스트 내에서 발견되었습니다. 인덱스:", i - j)
j = lps[j - 1]
else:
if j != 0:
j = lps[j - 1]
else:
i += 1
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
kmp_search(text, pattern)