브루트 포스법, KMP법, 보이어·무어법

Preface

 

이번 장에선 문자열 검색 알고리즘을 공부했다.

 

코드 자체는 어렵지 않았지만, 각 방법의 작동 방식이 복잡하게 설명되어 있어 이해하기 어려웠다.

 

처음 책을 읽을 때부터 코드를 작성하면서까지 계속 이상하다고 생각했던 부분이 있다.

 

대부분의 ide나 브라우저에서 이미 문자열 검색 기능을 제공하는데, 왜 굳이 검색 알고리즘을 사용할까?

 

나는 번거롭게 코드를 작성하는 것 보다 기존의 기능을 사용하는 것이 훨씬 효율적일 것 같다고 생각한다.

---

 

1. 브루트 포스법

 

 

- 문자열 검색 : 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 그 위치를 찾아내는 작업

1) 텍스트 : 검색되는 쪽의 문자열

2) 패턴 : 찾아내는 문자열

 

 

- 브루트 포스법(단순법) : 선형 검색을 단순 확장한 알고리즘

→ 이미 검사한 위치를 기억하지 못하므로 비효율적이다.

 

 

- 브루트 포스법 코드

def bf_match(txt: str, pat: str) -> int:
    pt = 0
    # txt 를 따라가는 커서
    pp = 0
    # pat 을 따라가는 커서

    while pt != len(txt) and pp != len(pat):
        if txt[pt] == pat[pp]:
            pt += 1
            pp += 1
        else:
            pt = pt - pp + 1
            pp = 0

    return pt - pp if pp == len(pat) else -1


if __name__ == '__main__':
    s1 = input('텍스트를 입력하세요.: ')
    s2 = input('패턴을 입력하세요.: ')

    idx = bf_match(s1, s2)

    if idx == -1:
        print('텍스트 안에 패턴이 존재하지 않습니다.')
    else:
        print(f'{(idx + 1)}번째 문자가 일치합니다.')

 

 

- 맴버십 연산자로 구현하기

1) ptn in txt

2) ptn not in txt

→ 위치는 알 수 없다.

 

 

- find, index, with 계열 함수는 p.308~309 참고

 

---

 

2. KMP법

 

 

- KMP법 : 텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 재시작할 위치를 구하여 패턴의 이동을 크게 하는 알고리즘

→ 검사했던 결과를 버리지 않으므로 브루트 포스법보다 효율이 좋지만, 복잡하여 실제 프로그램에서 잘 사용하지 않는다.

 

 

- KMP법 코드

def kmp_match(txt: str, pat: str) -> int:
    pt = 1
    pp = 0
    skip = [0] * (len(pat) + 1)

    skip[pt] = 0
    while pt != len(pat):
        if pat[pt] == pat[pp]:
            pt += 1
            pp += 1
            skip[pt] = pp
        elif pp == 0:
            pt += 1
            skip[pt] = pp
        else:
            pp = skip[pp]

    pt = pp = 0
    while pt != len(txt) and pp != len(pat):
        if txt[pt] == pat[pp]:
            pt += 1
            pp += 1
        elif pp == 0:
            pt += 1
        else:
            pp = skip[pp]

    return pt - pp if pp == len(pat) else -1


if __name__ == '__main__':
    s1 = input('텍스트를 입력하세요.: ')
    s2 = input('패턴을 입력하세요.: ')

    idx = kmp_match(s1, s2)

    if idx == -1:
        print('텍스트 안에 패턴이 존재하지 않습니다.')
    else:
        print(f'{(idx + 1)}번째 문자가 일치합니다.')

 

---

 

3. 보이어·무어법

 

 

- 보이어·무어법 : 패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사를 수행하는 알고리즘

 

 

- 패턴 문자열의 길이가 n일 때 이동량

1) 패턴에 포함되지 않는 문자를 만난 경우 : 패턴 이동량이 곧 n

2) 패턴에 포함되는 문자를 만난 경우 : 마지막에 나오는 위치의 인덱스가 k이면, 이동량은 n - k - 1

 

 

- 보이어·무어법 코드

def bm_match(txt: str, pat: str) -> int:
    skip = [None] * 256

    for pt in range(256):
        skip[pt] = len(pat)
    for pt in range(len(pat)):
        skip[ord(pat[pt])] = len(pat) - pt - 1

    while pt < len(txt):
        pp = len(pat) - 1
        while txt[pt] == pat[pp]:
            if pp == 0:
                return pt
            pt -= 1
            pp -= 1
        pt += skip[ord(txt[pt])] if skip[ord(txt[pt])] > len(pat) - pp \
            else len(pat) - pp

    return -1


if __name__ == '__main__':
    s1 = input('텍스트를 입력하세요.: ')
    s2 = input('패턴을 입력하세요.: ')

    idx = bm_match(s1, s2)

    if idx == -1:
        print('텍스트 안에 패턴이 존재하지 않습니다.')
    else:
        print(f'{(idx + 1)}번째 문자가 일치합니다.')