String Matching Algorithms: Everything About Efficient Pattern Search
Contents
1️⃣문자열 매칭 (String Matching)
2️⃣원시적 매칭 (Naive Matching Algorithm)
3️⃣오토마타 이용 매칭 (Automata Theory)
4️⃣라빈-카프 알고리즘(Rabin-Karp Algorithms)
5️⃣KMP 알고리즘과 실패 함수 (KMP Algorithm and Failure Function)
6️⃣보이어-무어 알고리즘(Boyer-Moore Algorithm)
1️⃣문자열 매칭 (String Matching)
문자열 매칭 (String Matching)이란 텍스트 문자열에 주어진 **패턴 문자열 (Pattern)**이 나타나는 위치를 찾아내는 과정을 말한다. 일반적으로 패턴 문자열은 텍스트보다 매우 짧은 경우가 많다.
문자열 매칭 알고리즘은 다양한 분야에서 활용된다.
문서 작업: 특정 문자열을 검색하는 알고리즘
인터넷 검색: 키워드 검색
데이터베이스: 항목 값 비교 또는 검색
백신 프로그램: 악성코드 패턴 탐지
2️⃣원시적 매칭 (Naive Matching Algorithm)
원시적 매칭은 텍스트에서 패턴 문자열을 찾기 위해 **순차적으로 하나씩 비교 (Sequential Comparison)**하는 방식이다. 이는 실무에서 거의 사용되지 않지만, 다른 문자열 매칭 알고리즘을 이해하기 위해 기본적으로 알아야 하는 개념이다. 시간 복잡도 (Time Complexity)는 O(mn) 패턴 길이 m, 텍스트 길이 n로 모든 위치를 하나씩 검사하기 때문에 효율이 떨어질 수 있다.
✅ 작동 과정 (How it Works)
첫 번째 위치부터 비교 (Compare from the first position)
텍스트의 첫 번째 문자부터 패턴의 첫 번째 문자까지 하나씩 비교한다.매칭에 실패하면 패턴을 한 칸 뒤로 이동한다.
이 과정을 텍스트 끝까지 반복한다.
패턴이 매칭되었을 경우 (When the pattern matches)
패턴의 모든 문자가 텍스트의 해당 위치에서 일치하면 해당 위치를 출력하게 된다.
✅원시적 매칭의 작동 원리(Principal Work of Native Matching Algorithms)
텍스트: bobycatsoaropt, 패턴: soar
텍스트의 처음부터 soar를 비교:
b와 s 비교 → 실패
o와 s 비교 → 실패
...
패턴을 한 칸씩 이동하며 비교:
s와 s → 성공
o와 o → 성공
a와 a → 성공
r와 r → 성공 (완전 매칭)
💡중요한 포인트 (Key Points)
순차적 비교 (Sequential Comparison): 문자 하나씩 비교
패턴 이동 (Pattern Shift): 매칭 실패 시 한 칸 이동
응용 분야 (Applications): 인터넷 검색, 데이터베이스 검색, 백신 프로그램 등
단점 (Disadvantages): 시간 복잡도가 높아 대규모 데이터에는 비효율적
원시적 매칭 의사코드 (Pseudocode for Naive String Matching Algorithm)
텍스트 탐색 범위 설정 (Set search range in text):
반복문은
i = 1부터i = n−m + 1까지 진행된다.이는 패턴의 길이 m만큼 텍스트에서 잘라 비교할 수 있도록 범위를 제한하는 것이다.
비교 조건 (Comparison condition):
현재 텍스트의 i번째부터
i + m − 1번째까지의 문자열을 패턴과 비교한다.모든 문자가 동일할 경우 매칭이 발견된다.
시간 복잡도 (Time Complexity):
- n은 텍스트의 길이, m은 패턴의 길이로, 최악의 경우 O(mn)만큼의 연산이 필요하다.
💡중요한 포인트 (Key Points)
탐색 범위 조정 (Adjust search range): 패턴이 텍스트 끝을 초과하지 않도록
n−m+1까지만 탐색조건 검사 (Condition check): 텍스트의 특정 부분이 패턴과 동일한지 비교
시간 복잡도 (Complexity): 비효율적이지만 개념 이해에 중요
원시적 매칭의 비효율적인 사례 (Inefficiency of Naive String Matching)
💡요약: 원시적 문자열 매칭은 순차적으로 모든 위치에서 비교하기 때문에, 특히 패턴의 대부분이 매칭되다가 마지막에 불일치가 일어나는 경우, 이미 비교한 부분까지 모두 반복해야 하므로 비효율적이다. 이러한 문제를 개선하기 위해 패턴 문자열의 앞부분과 뒷부분의 일치 여부를 활용하는 고급 알고리즘이 필요하다.
1번째 시도:
abcdabcd는 매칭되지만d와w에서 불일치 발생.2번째 시도: 패턴을 한 칸 이동, 처음부터 다시 비교 → 실패.
3~4번째 시도: 반복적으로 비교 → 실패.
5번째 시도: 최종적으로 완전한 매칭 성공
이 과정에서 이미 일치했던 abc를 계속 비교하며 연산이 낭비된다 (파란색 박스)
✅ 비효율적인 사례 설명 (Example of Inefficiency):
패턴 문자열과 텍스트의 일부가 매칭되더라도, 마지막 문자에서 불일치가 발생하면 앞서 비교했던 모든 연산이 무의미해진다.
텍스트에서 패턴을 한 칸씩 이동하며 처음부터 다시 비교를 시작해야 한다.
✅ 첨부 예제와 연결된 설명 (Example Analysis):
- 텍스트 (Text):
...abcdabcdabcwz, 패턴 (Pattern):abcdabcwz
✅문제점 (Problem): 매칭 실패 시 매번 처음부터 다시 비교하고 불필요한 연산이 많아 시간 효율성이 떨어진다.
💡 중요한 포인트 (Key Points)
마지막 문자 불일치 (Mismatch at the last character): 불필요한 반복 연산 발생.
패턴의 앞/뒤 일치 정보 활용 (Use pattern prefix/suffix): 효율적인 매칭 가능.
비효율성의 해결 (Resolving inefficiency): 오토마타(automata)이용 매칭
3️⃣오토마타 이론 (Automata Theory)
오토마타는 수학적이고 추상적인 기계로, 현재 상태를 기반으로 입력에 따라 상태를 변화시키며 출력을 생성한다. 이는 컴퓨터 과학에서 알고리즘과 문제를 해결하는 데 매우 유용하며, 문자열 매칭에서도 활용될 수 있다.
✅ 오토마타 이론이란? (What is Automata Theory)
어원 (Etymology): 오토 (Auto): 자동, 마토 (Mata): 기계
정의 (Definition): 오토마타는 문제를 해결하기 위해 유한한 상태를 정의하고, 특정 규칙에 따라 상태를 전환하며 출력을 생성하는 **추상적 기계 (Abstract Machine)**이다. 이는 실제 컴퓨터가 아닌 수학적으로 모델링된 개념이다.
✅오토마타의 예(Example of Automata Theory)
현재 컴퓨터의 상태와 입력에 따라 생성되는 결과가 정의되어 있고 특정규칙에 따라 출력 결과가 달라지는 오토마타 이론의 좋은 예제이다.
상태 (States):
off 상태절전 상태on 상태
전이 (Transitions):
전원 스위치를 켜면
off → 절전 상태입력(키보드/마우스)이 있으면
절전 상태 → on 상태일정 시간 입력이 없으면
on 상태 → 절전 상태전원 스위치를 끄면 모든 상태에서
off 상태로 복귀
✅ 원시적 매칭과 오토마타 이용 매칭 비교(Comparison of Naive Matching and Automata-Based Matching)
원시적 매칭 vs. 오토마타 이용 매칭 (Naive Matching vs. Automata-Based Matching):
원시적 매칭은 패턴의 문맥을 고려하지 않아 불필요한 연산이 많다.
오토마타는 상태와 문맥을 활용하여 효율적으로 비교 연산을 줄이게 된다.
오토마타 이론 #1: 구성요소 (Components of Automata)
오토마타는 아래 5가지 구성 요소로 정의된다:
Q (상태 집합, Set of states): 시스템이 가질 수 있는 모든 상태의 집합.
q₀ (시작 상태, Initial state): 입력 처리를 시작하는 초기 상태.
A (목표 상태의 집합, Set of accept states): 입력을 받아들이는 종료 상태(들).
Σ (입력 알파벳, Input alphabet): 시스템이 처리할 수 있는 입력의 집합.
δ (상태 전이 함수, Transition function): 특정 상태에서 특정 입력을 받을 때 이동할 다음 상태를 정의하는 함수.
오토마타 이론 #2: 상태 전이 함수 다이어그램 표현(Example of Transition Function Diagram)
시작 상태 (State 0):
아무 문자도 처리하지 않은 초기 상태이다.
첫 번째 입력이
a라면 상태 1로 이동한다.
상태 1:
입력이
b라면 상태 2로 이동한다.만약 다른 문자가 오면 상태 0으로 돌아간다.
이유: 패턴이
ababaca로 시작하므로b가 와야 다음으로 진행된다.
상태 2 → 상태 6:
- 올바른 입력이 계속되면 상태가 차례로 증가하게 된다.
예: 상태 2에서a→ 상태 3, 상태 3에서b→ 상태 4...
- 올바른 입력이 계속되면 상태가 차례로 증가하게 된다.
상태 7:
입력된 문자가
ababaca와 완전히 매칭되면 최종 상태 7에 도달한다.이는 패턴을 성공적으로 찾았다는 뜻이다.
잘못된 입력 처리:
예: 상태 5에서
b가 오면 전 단계 상태 4로 되돌아간다.이는 이미 매칭된 일부 정보를 재사용하여 불필요한 비교를 줄이기 위함이다.
원시적 매칭이었다면 처음부터 돌아가지만 오토마타는 중간 단계로 이동하기 때문에 비교연산을 줄일 수 있는 것이다.
상태 전이 함수는 위에서 언급된 예제처럼 다이어그램도 표시할 수 있고 이번 예제와 같이 테이블로도 구성할 수 있다.
오토마타 #2: 상태 전이 함수 테이블 구성 (Automata Transition Function Table Representation)
✅ 상태 전이 함수란? (What is Transition Function): 상태 전이 함수는 현재 상태에서 입력 문자를 기반으로 다음 상태를 결정한다.
예: 상태 0에서 입력이
a이면 상태 1로 이동.이는 문자열 매칭 과정을 구조적으로 표현하는 방법이다.
✅ 테이블 구성 (Table Representation): 상태 전이 다이어그램을 테이블 형태로 변환한다.
행 (Row): 현재 상태.
열 (Column): 입력 문자.
값 (Value): 다음 상태.
왼쪽 기본 테이블 (Full Table): 모든 알파벳에 대해 상태를 정의한다.
압축된 테이블 (Compressed Table): 패턴에 등장하는 문자(a, b, c)만 고려하고, 나머지 문자(기타)는 한 열로 압축하여 테이블을 단순화하고 시간을 절약하였다.
💡중요포인트:
기존 방식: 모든 알파벳에 대해 상태를 정의 → 테이블이 복잡
개선 방식: 패턴에 등장하는 문자만 고려 → 테이블이 단순화되고 연산 효율 증가
오토마타 #3: 의사코드 표현 (Pseudocode in Automata)
오토마타를 활용해 문자열 매칭을 수행하는 과정을 의사코드로 확인해보자.
δ(delta) 오토마타에서 상태 전이 함수 (Transition Function)를 의미한다. 오토마타가 현재 상태에서 특정 입력을 받았을 때 어디로 이동해야 하는지를 결정하는 역할을 한다.
δ(delta)그리스 문자의 이름으로, 수학과 컴퓨터 과학에서 함수나 변화(transition)를 나타낼 때 자주 사용한다.
FA-Matcher (A[], δ[][], f):
▷ f : 목표 상태 (Final state),
▷ n : 텍스트 A의 길이,
▷ m : 패턴 길이
q ← 0 ▷ q는 현재 상태를 나타냄
for i ← 1 to n: ▷ 텍스트의 각 문자를 처리
q ← δ(q, A[i]) ▷ 현재 상태와 입력 문자에 따라 상태 전이
if (q = f): ▷ 현재 상태가 최종 상태라면
A[i - m + 1]에서 매칭이 발생했음을 알린다.
변수 정의 (Variables):
q: **현재 상태 (Current state)**를 나타낸다. 시작 상태는 0이다.
δ: **상태 전이 함수 (Transition function)**이다. 현재 상태와 입력 문자에 따라 다음 상태를 반환한다.
f: **최종 상태 (Final state)**로, 패턴 매칭이 완료되었음을 나타낸다.
작동 과정 (How It Works):
q ← 0: 시작 상태에서 시작한다.
for루프는 텍스트의 각 문자를 차례로 처리한다.q ← δ (q, A[i]): 현재 상태와 입력 문자 A[i]를 상태 전이 함수에 넣어 다음 상태로 이동한다.if (q = f): 현재 상태가 최종 상태에 도달하면 매칭이 발생했음을 출력한다.- 매칭이 발생한 위치는
i − m+1이다.
- 매칭이 발생한 위치는
오토마타 #4: 수행 시간 분석 (Time Complexity of String Matching Using Automata)
오토마타를 이용한 문자열 매칭의 수행 시간은 크게 두 부분으로 나눌 수 있다:
매칭 수행 시간: 텍스트의 길이에 비례.
오토마타 상태 전이 함수 준비 시간: 패턴과 알파벳 크기에 비례.
✅ 매칭 수행 시간 (Matching Time)
for 루프: 텍스트의 각 문자에 대해 한 번씩 상태 전이를 수행 → O(n)
상태 전이 함수 실행: 한 번의 전이가 O(1)이므로 효율적.
매칭 수행 시간은 텍스트의 길이 n에 선형적으로 비례합니다.
✅상태 전이 함수 준비 시간 (Setup Time for Transition Function)
입력 알파벳의 개수: ∣Σ∣ 사용 가능한 문자(예: 영어 소문자 26개).
패턴 길이: m
준비 시간:
O(∣Σ∣m)모든 문자와 패턴의 길이에 대해 전이 상태를 정의.
✅총 수행 시간: Θ(n+∣Σ∣m)
- n: 텍스트의 길이
✅예제 수행 시간 계산 (Example Calculation)
입력 데이터:
텍스트 길이 n=1000
패턴 길이 m=10
알파벳 크기 ∣Σ∣=26
계산:
매칭 수행 시간: O(n) = O(1000)
상태 전이 함수 준비 시간: O(∣Σ∣m) = O(26⋅10) = O(260).
총 수행 시간: O(1000+260) = O(1260)
💡중요포인트:
오토마타 기반 매칭은 텍스트 길이에 선형적으로 비례하여 효율적이다.
상태 전이 함수 준비 시간이 추가로 필요하지만, 이는 매칭 단계의 효율성을 보장하는 투자이다.
입력 데이터의 특성(텍스트 길이, 패턴 길이, 알파벳 크기)에 따라 성능이 결정된다.
4️⃣라빈 - 카프 알고리즘(Rabin-Karp Algorithms)
문자열 매칭 알고리즘으로 라빈 카프 알고리즘에 대해서 배워본다. 문자열 패턴을 숫자로 변환하여 비교하는 효율적인 알고리즘이다.
라빈 카프 알고리즘(Rabin-Karp Algorithms): 가능한 문자들에 대해 숫자를 대응하고 패턴을 하나의 진수로 표현해서 만약 121 이라는 숫자가 있을 때, 문자로 하면 3개의 문자가 되듯이, 어떤 문자의 패턴이 있을때 그것을 각각의 문자로 할당해서 진수 표현하는 것이다. 이것을 “수치화 과정”이라고 한다.
수치화 (Numerical Transformation): 문자열의 각 문자를 숫자로 매핑하고, 해당 숫자를 특정 진수(base)로 표현하여 문자열을 숫자로 변환하는 과정
이 과정을 통해 빠르게 문자열의 패턴을 비교할 수 있게 된다.
✅수치화의 예 (Example of Numerical Transformation)
주어진 데이터: 알파벳 집합 Σ={a,b,c,d,e}, 크기 ∣Σ∣=5
- 매핑:
a=0,b=1,c=2,d=3,e=4
진수로 변환:
c =
2⋅5^2:2×25= 50a =
0 ⋅ 5^1:0×5= 0d =
3 ⋅ 5^0:3×1= 3
합산:
- 50 + 0 + 3 = 53
💡라빈-카프 알고리즘의 중요포인트
문자열을 숫자로 변환하여, 숫자 비교로 문자열 패턴 매칭을 수행한다.
효율성: 숫자 비교는 문자열 비교보다 빠르며, 해시 값을 이용하여 중복 계산을 줄일 수 있게된다.
✅수치화 계산 방법 기본 개념 (Basic Numerical Calculation)
문자를 숫자로 변환 (Mapping Characters to Numbers): 문자열의 각 문자를 고유한 숫자로 매핑한다.
진수로 표현 (Representing in Base ddd): 문자열의 각 문자를 진수 기반으로 표현하여 수치화한다.
예) 10진수(기본 진수 d=10)를 사용하여 P[m] 다음과 같이 표현:
p=P[m] + 10⋅P[m−1] + 102⋅P[m−2] + ⋯ + 10m−1⋅P[1]P[1]: 가장 왼쪽 문자 → 가장 큰 자리수.
P[m]: 가장 오른쪽 문자 → 가장 작은 자리수.
일반적인 계산 방식 (Basic Calculation): 텍스트에서 부분 문자열 A[i⋯i+m−1]를 수치화하는 계산:
시간 복잡도 O(m): 각 문자마다 10을 곱하면서 반복 계산.
전체 텍스트에 대해 비교: n개의 부분 문자열에 대해 계산 → 총 O(mn)
- 문제점: 원시적 매칭과 성능 차이가 없음.
✅수치화 계산의 개선 방법 (Optimization in Calculation)
- 점화식 사용 (Using Recursive Formula):
이전 계산값
ai−1을 재활용하여 다음 값ai를 계산에 활용한다.첫 번째 문자 영향 제거:
−10m−1 ⋅ A[i−1]새로운 문자 추가:
+A[i + m−1]
💡🤔최적화 효과가 있을까? 그렇다.
각 부분 문자열 계산이 O(1)로 줄어듦.
전체 텍스트 비교 시간: O(n)
미리 계산된
10m−1는 반복 사용 가능.
💡중요 포인트:
수치화 개념 (Numerical Transformation): 문자열을 숫자로 변환해 효율적으로 비교한다.
기본 계산 방식의 한계 (Limitations of Basic Calculation): 시간 복잡도 O(mn)으로 원시적 매칭과 동일한 점
점화식을 통한 개선 (Optimization Using Recursive Formula): 이전 계산값을 활용하여 불필요한 연산 제거한다. O(n)시간 복잡도로 최적화하였다.
효율성 (Efficiency): 덧셈과 곱셈 각각 2회로 계산 가능 → 이뜻은 실행 속도가 대폭 증가되었다는 뜻이다.
✅라빈-카프 알고리즘 수치화를 이용한 매칭 예제 (Example of Matching Using Numerical Transformation in the Rabin-Karp Algorithm)
💡 요약 (Summary)
수치화 계산 방법 (Numerical Calculation):
문자열의 각 문자를 진수로 변환하여 수치값을 계산한다.
P[]: 패턴 문자열 → 고유 수치값 계산.
A[]: 텍스트의 부분 문자열 → 고유 수치값 계산 후 패턴과 비교.
점화식을 사용한 계산 (Using Recursive Formula):
이전 계산값을 활용해 현재 값을 효율적으로 계산한다.
수치값이 같으면 문자열 매칭 성공하였다는 뜻이다
효율성: 점화식을 통해 한 칸씩 이동하며 효율적으로 비교할 수 있다.
❤️ P[] 패턴 문자열의 수치화 (Numerical Transformation of Pattern): eeaab
각 문자에 고유한 값을 부여한다.
e=4,a=0,b=1e=4, 5^4=625,a = 0,b = 1결과:p=300
❤️A[] 텍스트 문자열의 수치화 (Numerical Transformation of Text): acebb
처음 5개의 문자를 가져와 수치 계산.
결과:
a1 = 356매칭 실패 (Does not match p = 3001)
❤️문자열의 수치화 대신 점화식을 사용한 효율적 계산 (Efficient Calculation Using Recursive Formula)
ai−1: 이전 계산값.5m−1⋅A[i−1]: 빠지는 첫 번째 문자.A[i+m−1]: 추가되는 마지막 문자.
❤️ 계산 과정 (Calculation Process)
a2: cebbc
결과: a2 = 1782
매칭 실패 (Does not match p=3001).
a3: ebbce
결과: a3 = 2664
매칭 실패 (Does not match p=3001).
a7: eeaab
결과: a7 = 3001
매칭 성공 (Matches p=3001).
💡중요한 포인트 (Key Points)
수치화의 효율성 (Efficiency of Numerical Transformation):
점화식을 통해 이전 계산값을 재활용한다.
계산 복잡도를 O(mn)에서 O(n)으로 줄였다.
정확성 (Accuracy):
동일한 문자열은 동일한 수치값을 가진다.
수치값이 일치하면 문자열 매칭 성공하게 된다.
효율적 매칭 (Efficient Matching):
- 한 칸씩 이동하며 계산 → 빠르고 정확한 비교가 가능하다.
💡왜 수치화를 하는 걸까? (Why Use Numerical Transformation?)
문자열 비교는 한 문자씩 순서대로 확인해야 하므로 시간이 오래 걸리게 된다.
라빈-카프는 문자열을 숫자로 변환하고 숫자끼리 비교하므로 더 빠르게 매칭 여부를 확인할 수 있다.
✅라빈-카프 알고리즘 수치화를 이용한 의사코드 표현 (Pseudocode for Rabin-Karp Algorithm Using Numerical Transformation)
💡요약: 아래 예제 코드는 **패턴 문자열 P[]**를 텍스트 문자열 A[]에서 찾아내는 과정을 보여준다. 문자열을 숫자로 변환(수치화)하고, 이 숫자값을 비교하여 매칭 여부를 확인한다.
1. 초기화 (Initialization)
p ← 0; a₁ ← 0
p: 패턴 문자열 P[]의 수치값을 저장하는 변수이다.
a₁: 텍스트의 첫 번째 부분 문자열의 수치값을 저장하는 변수이다.
2. 패턴과 첫 번째 부분 문자열의 수치값 계산
for i ← 1 to m:
p ← d * p + P[i]
a₁ ← d * a₁ + A[i]
i: 현재 패턴과 텍스트의 문자를 계산하는 위치.
패턴 수치값 계산:
p = d⋅p+P[i]: 기존 값에 d를 곱하고 현재 문자의 값을 더한다.예:
eeaab→ p = 4⋅5^4 + 4⋅5^3 + 0⋅5^2 + 0⋅5^1 + 1⋅5^0 = 3001
첫 번째 텍스트 부분 문자열 수치값 계산:
a1 = d⋅a1+A[i]- 예:
acebb→ a1 = 0⋅5^4 + 2⋅5^3 + 4⋅5^2 + 1⋅5^1 + 1⋅5^0 = 356
- 예:
3. 나머지 부분 문자열의 수치값 계산 (점화식 사용)
for i ← 1 to n - m + 1:
if (i ≠ 1):
aᵢ ← d * (aᵢ₋₁ - dᵐ⁻¹ * A[i-1]) + A[i+m-1]
i≠1: 두 번째 부분 문자열부터 계산한다.
점화식 설명:
aᵢ: 새로운 부분 문자열의 수치값.aᵢ₋₁: 이전 부분 문자열의 수치값.dm−1: 패턴 길이에 따라 계산된 상수.A[i−1]: 빠지는 문자.A[i+m−1]: 추가되는 문자.
예제 계산:
a1 = 356
a2 = 5⋅(a1−0⋅625)+2 = 1782
a3 = 5⋅(a2−2⋅625)+4 = 2664
4. 매칭 여부 확인
if (p = aᵢ): A[i] 자리에서 매칭이 되었음을 알린다.
패턴의 수치값 p와 현재 부분 문자열의 수치값 aᵢ를 비교.
값이 같다면 패턴이 텍스트의 해당 위치에서 매칭됨을 의미.
예제:
패턴 p=3001
a₇ = 3001 → 매칭 성공
💡중요포인트
수치화: 문자열을 숫자로 변환하여 비교한다.
점화식: 이전 계산값을 재활용해 효율적 계산을 한다.
매칭 성공 조건: 패턴 수치값 p와 부분 문자열 수치값 aᵢ가 같으면 매칭이 성공된다.
효율성: 반복 계산을 줄이고 O(n) 시간 안에 패턴 매칭을 완료한다.
✅라빈-카프 알고리즘 수치화를 이용한 매칭의 문제점
💡요약: 문자열 패턴과 텍스트의 수치화 과정에서 계산 결과가 너무 커져 **오버플로우 (Overflow)**가 발생할 수 있다. 이를 해결하기 위해 **모듈러 연산 (Modulo operation)**을 사용하여 값을 제한한다.
라빈-카프 알고리즘 (Rabin-Karp Algorithm):
문자열 패턴과 텍스트를 **해시값 (Hash value)**으로 변환한 뒤, 빠르게 비교한다.
모듈러 연산을 적용하여 효율적으로 수치화된 값 비교 수행할 수 있게 된다.
장점: 빠른 매칭 가능하고 모듈러 연산을 통해 값의 크기를 제한하여 오버플로우 방지한다.
❤️ 문제점과 해결책 (Challenges and Solutions)
문제점:
문자 집합 Ω와 패턴 길이 m에 따라 ai가 매우 커질 수 있음.
예:a_i = d(a_{i-1} - d^{m-1}A[i-1]) + A[i+m-1]너무 큰 숫자는 레지스터의 크기를 초과해 **오버플로우 (Overflow)**가 발생한다.
해결책: **모듈러 연산 (Modulo operation)**을 적용하여 값을 제한한다.
식 변경:
bi = (d(bi−1−(dm−1 modq) ⋅ A[i−1]) + A[i+m−1])q 값: 충분히 큰 소수를 선택해 충돌을 최소화한다.
이 방법은 해시테이블의 해시값 계산과 유사하다.
❤️ 라빈-카프 알고리즘의 작동 원리 (How Rabin-Karp Works)
패턴 해시값 계산 (Hash Calculation for Pattern):
P[]=e,e,a,a,b
계산:
p = (4⋅5^4+4⋅5^3+0⋅5^2+0⋅5^1+1) mod 113 = 63
원문 해시값 계산 (Hash Calculation for Text):
원문 A[]: a, c, e, b, b, c, e, e, a, b, c, e, e, d, b…
처음 5개의 해시값
a1 = 17슬라이딩 윈도우 방식으로 다음 해시값 계산:
a2 = 87
매칭 과정 (Matching Process): 패턴 해시값 p=63 과 원문 해시값 ai를 비교하여 해시값이 같으면 실제 문자열을 확인하여 매칭 여부 판단한다.
결과:
a7 = 63에서 매칭 성공하였다.
💡중요포인트: 라빈-카프 알고리즘은 빠르고 효율적인 문자열 매칭 알고리즘이다.
문제: 문자열 수치화 값이 커져 오버플로우 발생 가능.
해결: 모듈러 연산으로 값 크기를 제한하여 문제 해결.
라빈-카프 알고리즘 작동 원리:
패턴과 텍스트를 해시값으로 변환해 비교.
해시값이 같으면 매칭 성공(문자열도 추가 확인).
효율성: 슬라이딩 윈도우 방식으로 이전 계산 재활용 → 빠른 연산.
결과: 패턴 해시값 p와 텍스트 해시값 ai가 동일한 경우 매칭 확인하게 된다.
❤️ 라빈-카프 알고리즘 의사코드 요약 (Rabin-Karp Algorithm Pseudocode Summary)
모듈러 연산 사용 (Use of Modulo Operation):
해시값 계산 중 값이 커지는 것을 방지하기 위해 모든 계산에 모듈러 연산이 적용되었다.
p, bi, h 계산 시 mod q를 사용한다.
시간복잡도 (Time Complexity):
- 전체 비교에 O(n + km), 평균적으로 O(n)의 복잡도를 갖는다.
작동 원리 (How it Works):
패턴 P의 해시값 p와 텍스트 A의 해시값 bi를 계산한다.
해시값이 일치하면, 실제 문자열도 비교하여 매칭 여부 확인하게 된다.
**💡중요포인트: 모듈러 연산 (Modulo Operation)**을 통해 수치화 과정에서 값이 너무 커지지 않도록 계산마다 사용하여 오버플로우를 방지한다. 패턴 해시값 p와 텍스트 해시값 bi를 비교하여 매칭 여부를 빠르게 판단하고 슬라이딩 윈도우를 사용하여 효율적으로 계산한다. 문자열 매칭을 빠르게 수행이 가능하고 큰 데이터를 처리할때 효율적이다. 또한 해시값 충돌 가능성 때문에 해시값이 같을 경우 문자열을 추가로 비교하여 정확성을 보장한다.
5️⃣KMP 알고리즘과 실패 함수 (KMP Algorithm and Failure Function)
💡 요약 (Summary)
KMP 알고리즘의 핵심 (Core Idea of KMP):
- 매칭 실패 시 처음으로 돌아가지 않고, 중간 지점으로 복귀하여 이전 비교 결과를 활용한다. 이를 통해 비교 연산 횟수가 감소하게 된다.
실패 함수 (Failure Function):
매칭 실패 시 돌아갈 중간 지점을 미리 계산하고 저장하는 함수이다.
패턴의 중복 정보를 활용하여 불필요한 연산을 줄일 수 있다.
KMP vs. 오토마타: 오토마타와 유사한 방식으로 동작하지만, 준비 작업이 더 단순하고 빠르다는 장점이 있다. (오토마타는 상태함수 준비시 좀 복잡하다)
✅ KMP 알고리즘 vs. 오토마타 매칭 비교 (KMP Algorithm vs. Automata Matching)
원시적 매칭과의 차이 (Compared to Naive Matching):
원시적 매칭: 매칭 실패 시 처음으로 돌아가 다시 비교.
오토마타와 KMP: 실패 시 중간 상태로 이동해 이전 결과를 재활용.
KMP와 오토마타의 공통점 (Similarities):
- 둘 다 문맥 활용: 매칭 실패 시 중간 상태로 이동해 불필요한 연산 제거.
KMP와 오토마타의 차이점 (Differences):
오토마타: 상태 전이 함수를 상태 다이어그램으로 정의. 준비 과정이 복잡하지만 체계적이다.
KMP: 실패 함수를 이용해 중간 지점을 계산한다. 준비 과정이 단순하고 빠르다.
✅KMP 알고리즘 작동 원리 (How KMP Works)
패턴 매칭:
텍스트와 패턴을 비교하면서 실패 시 중간 지점으로 이동한다.
실패 함수 π[i]를 사용하여 복귀 지점을 결정한다.
실패 함수의 역할 (Role of Failure Function):
매칭 실패 시 처음으로 돌아가지 않고, 이미 매칭된 부분을 활용해 비교를 이어간다.
예: π[8] = 4 → 8번째 자리에서 실패하면 4번째 자리로 복귀하게 된다.
실패 함수 계산 (Failure Function Calculation):
패턴 내에서 부분 문자열의 중복 정보를 활용하여 재활용한다.
패턴의 각 위치에서 실패 시 복귀할 위치를 저장한다.
✅예제 분석 (Example Analysis)
매칭 실패 예시: 텍스트: A[], 패턴: P[] = abcdabcwz
텍스트에서
abcdabcd까지 매칭 후d≠w에서 실패가 발생하였다.실패 함수로 인해 중복된 abc를 살리고, d부터 비교를 재개한다.
실패 함수 예시: P [1:9] = abcdabcwz
π[8]=4: 8번째 자리에서 실패 시 4번째 자리 d로 이동한다.
결과적으로 4칸 점프하여 불필요한 연산 제거하게 된다.
✅KMP의 장점 (Advantages)
효율적 비교: 실패 함수로 중복 비교를 줄여 평균적으로 O(n+m)시간 복잡도를 가진다.
중복 활용: 패턴 내부 중복을 활용해 이전 결과를 재활용한다.
실제 응용: 텍스트 검색, 네트워크 패턴 매칭, 데이터 분석 등에 사용된다.
✅ KMP 알고리즘과 실패 함수 준비 의사코드 (KMP Algorithm and Failure Function Pseudocode)
💡 요약 (Summary)
실패 함수 준비 (Failure Function Preparation):
목적: 패턴 내 중복 정보를 활용해 매칭 실패 시 돌아갈 위치를 미리 계산.
시간복잡도: Θ(m), 패턴의 길이 m에 비례.
KMP 알고리즘 (KMP Algorithm):
매칭 실패 시 실패 함수 π[j]를 이용해 중간 지점으로 점프.
원문의 각 문자에 대해 비교 진행 → Θ(n) 시간 소요.
전체 시간복잡도: Θ(n+m)
k: 패턴의 접두사 길이를 나타냄.
π[j]: 매칭 실패 시 복귀 위치를 저장.
if (k = 0 or A[j] = P[k]) j++, k++;k = 0이거나 원문의 값이A[j] = P[k]패턴의 값과 일치하면 계속 증가하다가π[j] <- k실패함수 값을 업데이트해준다.
else j <-π[j]매칭 실패 시 j를 π[j]로 업데이트하여 중간 지점으로 복귀한다.매칭 성공 시, 매칭된 위치를 출력하고 다시 π[j]를 이용해 다음 비교 시작.
먼저 패턴에 대한 실패 함수를 준비한다.
preprocessing(p)그다음엔 while문을 돌며 실패가 일어났을 경우에 해당 지점으로 점프를 해나가게 된다.else j <-π[j]그러다가 전체적으로 매칭이 일어나면 매칭이 되고 처음으로 다시 돌아가게된다.j <-π[j]
✅시간복잡도 분석 (Time Complexity Analysis)
실패 함수 준비: Θ(m), 패턴의 길이에 비례
KMP 알고리즘: Θ(n), 원문의 길이에 비례.
전체 시간복잡도: Θ(n + m), 효율적 문자열 매칭 가능.
실패 함수를 준비하는데 패턴의 길이만큼의 시간이 필요해서
preprocessing() = Θ(m)이고 while 루프는 원문의 문자를 하나씩 보기때문에Θ(n)이다.
6️⃣보이어-무어 알고리즘(Boyer-Moore Algorithm)
기존의 라빈 카프 알고리즘이나 kmp알고리즘은 텍스트 문자열을 처음부터 적어도 1번씩은 검색하기 때문에 세타n의 수행시간이 필요한다. 텍스트를 왼쪽에서 오른쪽으로 비교하기때문에 최선의 경우에도 n만큼의 시간이 필요하다. 보이어 무어는 생각의 전환을 하였다. 텍스트 문자열을 전부 보지 않고 점프를 하며 일부만 보는것이다 또한 패턴을 왼쪽이 아닌 오른쪽부터 비교하게 된다. 긴문자열의 패턴이 5개라면 5번째부터 본다. 매칭이 되지 않는다면 앞에있는 4개는 보지 않고 뛰어넘게된다. 이렇게 반복하는 방식이다. 실무적으로 높은 성능을 보이는 알고리즘으로 많이 사용되고 있다.
✅ 보이어-무어 알고리즘 작동 원리 (How it Works)
비교 방향: 전체 텍스르로 보면 앞으로 진행하지만 패턴으로 보면 반대방향으로 진행한다.
패턴: 오른쪽에서 왼쪽으로 비교.
텍스트: 여전히 왼쪽에서 오른쪽으로 진행.
불일치 처리:
KMP알고리즘이 실패함수를 사용하는 것처럼 보이어무어 함수도 불일치 시 “점프 테이블”을 참고해 특정 칸 수를 건너뛴다.
검색하는 텍스트보다 패턴이 훨씬 짧고 여러번 찾을 때 유리하다.
실무적으로 문자열 매칭 알고리즘을 사용할때 보이어 무어 알고리즘이 벤치 마크 표준으로 사용될 정도로 많이 사용되고 있다.
✅ 예제 분석 (Example Analysis)
텍스트: A[] =
...btiger.., 패턴: P[] =tiger비교 과정:
마지막 문자 r부터 비교 → 불일치 (b ≠ r).
점프 테이블에 따라 5칸 점프 → 다음 비교 시작.
텍스트: A[]=
...tigertiger...패턴: P[]="tiger"비교 과정:
i ≠ r에서 불일치 발생.
패턴에서 i가 세 번째 위치에 있으므로 3칸 점프.
앞의 2개 문자는 재활용하여 비교 연산 감소.
✅점프 테이블 1 (Jump Table in Boyer-Moore Algorithm)
💡요약 (Summary)
점프 테이블이란? (What is a Jump Table?)
패턴의 각 문자에 대해 매칭 실패 시 몇 칸 점프할지를 정의한 테이블이다.
패턴의 오른쪽에서 왼쪽으로 비교하기 때문에 점프 테이블도 반대 방향으로 정의한다.
점프 테이블의 목적 (Purpose of Jump Table):
매칭 실패 시 효율적으로 불필요한 비교를 건너뛰기 위해 사용한다.
특정 문자가 패턴에 없는 경우 패턴 길이만큼 점프한다.
"heyhibyez"에서 "bye"를 매칭.
y ≠ e: 점프 테이블에 따라 1칸 점프.
h ≠ e: 기타 문자 → 3칸 점프.
y ≠ e: 다시 1칸 점프.
마지막 문자 e일치 → 매칭 성공.
문자별 이동 거리 계산:
패턴의 각 문자에 대해 끝에서의 거리를 기준으로 이동 거리를 설정.
패턴에 없는 문자 → 패턴의 길이만큼 점프.
동일한 문자가 여러 번 나타나면 가장 작은 이동 거리 선택.
마지막으로 b, y, e 순서로 비교 → 모두 매칭 → 매칭 성공.
✅점프 테이블 2 (Jump Table in Boyer-Moore Algorithm)
❤️ 패턴: tiger의 점프 테이블
오른쪽 끝 문자 기준으로 이동 거리 계산:
t: 마지막에서 4번째 → 이동 거리 = 4i: 마지막에서 3번째 → 이동 거리 = 3g: 마지막에서 2번째 → 이동 거리 = 2e: 마지막에서 1번째 → 이동 거리 = 1r: 마지막에서 0번째 → 이동 거리 = 0기타 문자: 패턴 길이(5)만큼 점프
❤️패턴: rational의 점프 테이블
같은 문자가 여러 번 나타나는 경우:
가장 오른쪽의 위치를 기준으로 이동 거리를 계산하지만, 가장 작은 이동 거리를 선택.
예:
a는 1번째와 6번째에 나타남 → 이동 거리 = 1 (6번째 기준).
오른쪽 끝 문자 기준으로 이동 거리 계산:
r: 마지막에서 7번째 → 이동 거리 = 7a: 마지막에서 6번째 → 이동 거리 = 1 (작은 값 선택)t: 마지막에서 5번째 → 이동 거리 = 5i: 마지막에서 4번째 → 이동 거리 = 4o: 마지막에서 3번째 → 이동 거리 = 3n: 마지막에서 2번째 → 이동 거리 = 2l: 마지막에서 1번째 → 이동 거리 = 0기타 문자: 패턴 길이(8)만큼 점프.
✅원시적 매칭 vs. 개선된 매칭 의사코드 비교 (Naive Matching vs. Improved Matching Pseudocode)
원시적 매칭 의사코드와 비교하면 크게 다른점은 없다. 하나 다른 점은 computeJump(P, jump) 점프하는 테이블을 준비하는 것과 실제 점프시 점프테이블을 이용해 점프한다는 점이다. i<- i + jump[A[i+m-1]]
공통점 (Similarities):
텍스트와 패턴을 비교하며 매칭 여부 확인.
while 루프를 통해 텍스트를 순차적으로 탐색.
차이점 (Differences):
원시적 매칭 (Naive Matching):
- 매칭 실패 시 무조건 한 칸씩 이동.
개선된 매칭 (Improved Matching):
점프 테이블을 사용하여 불일치 시 여러 칸 점프.
점프 테이블은
computeJump(P,jump)를 통해 미리 생성.
✅보이어-무어-호스풀 알고리즘 (Boyer-Moore-Horspool Algorithm)
개선된 매칭 알고리즘의 확장된 형태를 보이어-무어-호스풀 알고리즘이라고 한다. 개선된 매칭은 단순한 점프 방식을 따르고, 보이어-무어-호스풀은 점프 전략이 더 정교하다. 따라서 두 알고리즘은 유사하지만, 비교 방식과 점프 전략에서 차이가 있다.
- computejum(P.jump) 점프 테이블을 만들고 그 자리에서 매칭이 발견되지 않았을때는 점프 테이블에 저장된 위치만큼 점프하며 문자열매칭을 수행하게 된다.
✅ 수행시간 분석
최악의 경우: Θ(mn)
텍스트 전체가 동일한 문자로 구성된 경우, 한 칸씩만 점프 → 원시적 매칭과 동일.
이 경우가 실제적인 상황은 거의 없고 실무적으로 보았을땐 매우 빠르게 동작한다.
일반적인 경우:
- 실제 텍스트와 패턴이 다양한 경우에는 불필요한 비교를 줄이므로, 평균적으로 Θ(n)보다 빠름.
최선의 경우: Θ(n/m)
긴 텍스트에서 패턴이 나타나지 않는 경우, 패턴 길이만큼 점프.
예: 패턴 길이가 20인 경우, 한 번의 비교 후 20칸 점프 가능.
