All
보이어-무어 알고리즘 Boyer-Moore
패턴을 뒤에서부터 검사하고, 불일치 발생 시 멀리 점프할 수 있도록 전처리 테이블을 활용해 매칭 속도를 높이는 알고리즘
핵심 개념
•
텍스트의 첫 위치에서 패턴의 뒷부분부터 문자 비교
•
비교 중 불일치가 발생하면 불일치 문자 방법, 일치 접미부 정보를 활용해 멀리 점프
•
패턴 이동 결정은 두 규칙 중 더 멀리 이동할 수 있는 쪽 선택
불일치 문자 bad character
•
불일치가 발생한 텍스트의 문자가
◦
패턴 안에 있다면 그 문자가 마지막으로 나온 위치까지 패턴을 이동
◦
패턴 안에 없다면, 패턴 전체 길이만큼 통째로 건너뛰기 가능
예시
T: ... a b c [x] ...
P: a b c [d] (불일치: x ≠ d)
→ x는 패턴 P에 없음 → 패턴 전체 길이만큼 오른쪽으로 점프
•
또는 x가 P에 있다면, x의 마지막 등장 위치까지 P를 이동
일치 접미부 good suffix
•
불일치가 발생했을 때 맞았던 접미사를 살펴봄
◦
그 접미사가 패턴 앞쪽에도 있다면 그쪽과 정렬해서 점프
◦
앞쪽에도 없고 접두사랑 일치하는 부분이 있다면 그쪽에 맞춰 정렬
◦
그것도 없다면 패턴 전체를 1칸 오른쪽으로 이동
•
KMP 알고리즘과 유사하면서도 다름
예시
T: ... a b [c d e]
P: f g [c d e] (e까지 일치 → d에서 불일치 발생)
→ 접미부 [d e]가 패턴의 앞부분에도 존재하면,
→ 그 위치까지 패턴을 이동
•
또는 [d e] 자체가 P의 접두사라면 그 위치에 맞춰 정렬
구현(스켈레톤)
def boyer_moore(text, pattern):
# 1. 전처리: bad character 테이블, good suffix 테이블 만들기
bad_char = preprocess_bad_character(pattern)
good_suffix = preprocess_good_suffix(pattern)
n, m = len(text), len(pattern)
i = 0 # 텍스트에서의 시작 위치
while i <= n - m:
j = m - 1 # 패턴 끝부터 비교
while j >= 0 and pattern[j] == text[i + j]:
j -= 1
if j < 0:
print(f"Pattern found at index {i}")
i += good_suffix[0] # 전체 패턴이 일치한 경우 점프
else:
bc_shift = j - bad_char.get(text[i + j], -1)
gs_shift = good_suffix[j]
i += max(bc_shift, gs_shift)
Python
복사
성능
•
최악의 시간 복잡도: O(nm)
◦
패턴 반복되고 점프가 거의 안될때
•
최선의 시간 복잡도: O(n/m)
◦
패턴이 길고 점프가 자주 발생할때
•
대부분 실데이터에서는 매우 효율적으로 동작
문자열 기반 데이터 압축
데이터 압축의 정의
•
데이터를 더 적은 공간으로 표현하여 저장/전송 비용을 줄이는 기법
•
문자열뿐 아니라 이미지, 음성, 영상 등 다양한 형태의 데이터에 적용됨
압축의 종류
무손실 압축
•
압축된 데이터로부터 원래의 데이터를 완벽하게 복원할 수 있는 압축방법
•
데이터의 내용 하나하나가 모두 중요한 경우에 사용
•
대표 알고리즘
◦
RLE, 허프만 코딩, LZ77 등
손실 압축
•
압축된 데이터로부터 원래의 데이터를 완벽하게 복원할 수 없는 압축 방법
•
데이터의 내용이 약간 변형되어도 무방한 경우에 사용
•
주로 멀티미디어에 사용
•
대표 알고리즘
◦
JPEG 표준, MPEG 표준 등
데이터 압축 기본 용어
인코딩
•
원래의 데이터를 압축된 데이터로 변환하는 것
디코딩
•
압축된 데이터를 압축되지 않은 데이터로 변환하는 것
•
손실 압축의 경우 디코딩 결과가 인코딩 이전 데이터와 동일하지 않을 수 있음
RLE Run Length Encoding
같은 문자가 연속으로 반복될 때, 그 문자와 반복 횟수로 표현
•
bbbbb → (b, 5)
RLE 인코딩
•
주어진 스트링을 차례로 보며 문자가 달라질 때까지 횟수 셈
•
aaabbbbbaaccccbaaaaaaa → (a, 3) (b, 5) (a, 2) (c, 4) (b, 1) (a, 7)
def RLE_encoding(s):
result = []
n = len(s)
idx = 0
while idx < n:
count = 1
while idx + 1 < n and s[idx] == s[idx + 1]:
count += 1
idx += 1
result.append((s[idx], count))
idx += 1
return result
Python
복사
RLE 디코딩
•
압축된 데이터를 차례로 보며 각 문자를 횟수만큼 반복
•
(a, 3) (b, 5) (a, 2) (c, 4) (b, 1) (a, 7) → aaabbbbbaaccccbaaaaaaa
def RLE_decoding(encoded):
result = ""
for char, count in encoded:
result += char * count
return result
Python
복사
성능
•
시간 복잡도: O(n)
◦
인코딩과 디코딩 모두 이중 루프로 보이지만 실제로는 스트링 길이(n)만큼 수행
•
장점
◦
구현이 간단하고 직관적
◦
동일 문자 반복이 많은 데이터에서 압축률이 뛰어남
•
단점
◦
문자가 자주 바뀌는 경우 압축률이 오히려 떨어질 수 있음