보이어 무어 알고리즘

Boyer Moore

• 오른쪽에서 왼쪽으로 비교
• 대부분의 상용 소프트웨어에서 채택하고 있는 알고리즘
• 보이어-무어 알고리즘은 패턴에 오른쪽 끝에 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우, 이동거리는 무려 패턴의 길이만큼
• 앞의 두 매칭 알고리즘의 공통점 텍스트 문자열의 문자를 적어도 한번씩 훑는다.
• 보이어 무어 알고리즘은 텍스트 문자를 다 보지 않아도 됨
• 최악의 경우 수행시간 O(MN)
• 입력에 다라 다르지만 일반적으로 O(n) 보다 시간이 덜 소요됨

# T : target / P : pattern


def pre_process(P):
    from collections import defaultdict

    M = len(P)    

    # skip 배열 대신 딕셔너리
    PI = defaultdict(int)

    # 실 사용은 M - value로 할 예정.
    for i in range(M-1):
        PI[P[i]] = 1 + i
    return PI


def boyer_moore(T, P, PI):

    N = len(T)
    M = len(P)

    i = 0
    # 실패할 경우 -1 return
    pos = -1

    while i <= N - M:
        # skip 잘 되고있나 확인
        print(i)

        # 
        # M번째 인덱스
        j = M - 1
        k = i + M - 1

        # 비교할 j가 남아있고, text와 pattern이 같으면 1씩 줄여 왼쪽 비교
        while j >= 0 and P[j] == T[k]:
            j -= 1
            k -= 1
        # 비교 성공
        if j == -1:
            pos = i
            break
        # i를 M - value만큼 스킵
        i = i + M - PI[T[i + M - 1]]

    return pos




# Target 문자
T = "a pattern matching algorithm"

# Pattern 문자
P = "rithm"

# skip 배열을 만들어줌
PI = pre_process(P)
print(PI)

# target, pattern, skip배열을 인자로 넘김
pos = boyer_moore(T, P, PI)
print(pos)

#BoyerMooer algorithm
#불필요한 탐색 스킵
def skip(pattern, char):
    for i in range(len(pattern)-2, -1, -1):
        if pattern[i] == char:
            return len(pattern)-i-1
    return len(pattern)
#BM 본 함수
#text안에 pattern과 일치하는 문자열 있으면 1반환 바로 종료
#끝까지 탐색했는데 pattern과 일치하는 문자열이 없으면 0반환
def boyer(pattern, text):
    cnt = 0
    patternlen = len(pattern)
    textlen = len(text)
    i = 0
    while i <= textlen - patternlen:
        j = patternlen - 1
        while j >= 0:
            if pattern[j] != text[i+j]:
                move = skip(pattern, text[i + patternlen - 1])
                break
            j = j - 1
        if j == -1:
            cnt += 1
            return 1
        else:
            i += move
    return 0