문자열 검색 알고리즘: KMP와 Boyer-Moore 알고리즘

문자열 검색 알고리즘은 긴 텍스트 내에서 특정 문자열(패턴)을 빠르고 효율적으로 찾는 데 사용됩니다. 이는 텍스트 처리, 데이터 검색, DNA 분석 등 다양한 분야에서 활용됩니다. 이번 글에서는 대표적인 문자열 검색 알고리즘인 KMP(Knuth-Morris-Pratt)와 Boyer-Moore 알고리즘의 작동 원리, 구현 방법, 그리고 실무 활용 사례를 살펴보겠습니다.

1. 문자열 검색 문제란?

• 문제 정의:

• 주어진 텍스트 T에서 패턴 P를 검색하여 해당 위치를 찾는 문제.

• 기본 접근법:

• Brute Force: 텍스트의 모든 위치에서 패턴을 비교.

• 시간 복잡도: O(n × m) (n: 텍스트 길이, m: 패턴 길이).

• 비효율적이며, 실무에서 사용되지 않음.

2. KMP 알고리즘

KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 검색에서 불필요한 비교를 줄이기 위해 접두사-접미사 테이블(Prefix Table)을 사용합니다. 이 테이블은 패턴 내부의 중복을 활용하여 검색 속도를 높입니다.

작동 원리

1. Prefix Table 생성:

• 패턴의 각 위치에서 접두사와 접미사의 최대 일치 길이를 기록.

2. 검색 단계:

• 텍스트와 패턴을 비교하며 불일치가 발생하면 Prefix Table을 참조해 비교 위치를 이동.

시간 복잡도

• Prefix Table 생성: O(m)

• 검색: O(n)

KMP 구현 (Python)

def compute_prefix_table(pattern):
    m = len(pattern)
    prefix_table = [0] * m
    j = 0
    for i in range(1, m):
        if pattern[i] == pattern[j]:
            j += 1
            prefix_table[i] = j
        else:
            if j != 0:
                j = prefix_table[j - 1]
                i -= 1
            else:
                prefix_table[i] = 0
    return prefix_table

def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    prefix_table = compute_prefix_table(pattern)
    i = j = 0
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
        if j == m:
            print(f"패턴 발견: 인덱스 {i - j}")
            j = prefix_table[j - 1]
        elif i < n and text[i] != pattern[j]:
            if j != 0:
                j = prefix_table[j - 1]
            else:
                i += 1

# 사용 예제
kmp_search("ababcabcabababd", "ababd")

3. Boyer-Moore 알고리즘

Boyer-Moore 알고리즘은 문자열 검색에서 텍스트와 패턴을 뒤에서부터 비교하는 방식으로 동작합니다. 이는 Bad Character Rule과 Good Suffix Rule을 활용하여 검색 속도를 극대화합니다.

작동 원리

1. Bad Character Rule:

• 불일치 발생 시, 패턴 내 해당 문자 위치를 기준으로 텍스트를 이동.

2. Good Suffix Rule:

• 일치하는 접미사가 다른 위치에서도 나타나면 그에 맞춰 패턴을 이동.

시간 복잡도

• 평균: O(n / m) (텍스트 길이가 길수록 효율적)

• 최악: O(n × m) (모든 문자가 같을 때)

Boyer-Moore 구현 (Python)

def bad_character_table(pattern):
    table = {}
    m = len(pattern)
    for i in range(m):
        table[pattern[i]] = i
    return table

def boyer_moore_search(text, pattern):
    m, n = len(pattern), len(text)
    bad_char_table = bad_character_table(pattern)
    s = 0
    while s <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[s + j]:
            j -= 1
        if j < 0:
            print(f"패턴 발견: 인덱스 {s}")
            s += (m - bad_char_table.get(text[s + m], -1)) if s + m < n else 1
        else:
            s += max(1, j - bad_char_table.get(text[s + j], -1))

# 사용 예제
boyer_moore_search("ABAAABCD", "ABC")

4. KMP와 Boyer-Moore 알고리즘 비교

특성	KMP 알고리즘	Boyer-Moore 알고리즘
작동 원리	Prefix Table 사용	Bad Character Rule 및 Good Suffix Rule 사용
시간 복잡도	O(n + m) 평균	O(n / m), 최악 O(n × m)
비교 방향	왼쪽에서 오른쪽	오른쪽에서 왼쪽
효율성	중복 패턴에 강함	긴 텍스트와 작은 패턴에서 강력
실제 활용	텍스트 처리 도구, DNA 분석	검색 엔진, 대규모 텍스트 처리

5. 활용 사례

1. 검색 엔진:

• 웹 페이지에서 키워드 검색.

2. DNA 분석:

• 유전자 서열에서 특정 패턴 검색.

3. 텍스트 편집기:

• 문자열 검색 및 치환 기능 구현.

4. 보안:

• 텍스트 기반 악성 코드 탐지.

결론

 

KMP와 Boyer-Moore 알고리즘은 문자열 검색 문제를 해결하는 강력한 도구입니다. KMP는 중복 패턴 처리에 적합하며, Boyer-Moore는 긴 텍스트와 작은 패턴의 검색에서 뛰어난 성능을 발휘합니다. 두 알고리즘을 이해하고 적절히 활용한다면 텍스트 처리와 검색 효율성을 크게 향상시킬 수 있습니다.