보이어 무어 알고리즘
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
Author And Source
이 문제에 관하여(보이어 무어 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@holawan/보이어-무어-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)