String Matching Algorithm 스트링 알고리즘.01

Stiring : 문자가 연속적으로 나열된 문자열

 

알파벳 alphabet ∑ : 스트링에 사용되는 문자들의 집합

 

스트링 매칭 : 텍스트에서 패턴이 나타나는 위치를 찾는 것

• 텍스트 T : 긴 스트링, 길이n
• 패턴 P : 짧은 스트링, 길이 m
• n≥m

---

브루트-포스 스트링 매칭 알고리즘
(Brute-force algorithm 또는 Naïve algorithm)

• 텍스트의 각 위치에서부터 패턴의 길이만큼 문자를 비교하며 매치를 찾는 방법
• 시간 복잡도 : O(nm)

T : a a b a a b a a a
P : a a b a a

 

위치	0	1	2	3	4	5	6	7	8
T	a	a	b	a	a	b	a	a	a
P	a	a	b	a	a

 

위치	0	1	2	3	4	5	6	7	8
T	a	a	b	a	a	b	a	a	a
P		a	a	b	a	a

 

위치	0	1	2	3	4	5	6	7	8
T	a	a	b	a	a	b	a	a	a
P			a	a	b	a	a

 

위치	0	1	2	3	4	5	6	7	8
T	a	a	b	a	a	b	a	a	a
P				a	a	b	a	a

 

위치	0	1	2	3	4	5	6	7	8
T	a	a	b	a	a	b	a	a	a
P					a	a	b	a	a

 

 

---

 

패턴을 전처리 : 라빈-카프 알고리즘, KMP 알고리즘, 보이어-무어 알고리즘
텍스트를 전처리 : 접미부 트리, 접미부 배열

---

라빈-카프 Rabin-Karp 알고리즘
(Brute-force algorithm 또는 Naïve algorithm)

• 패턴의 해시값으모 매치 후보를 찾음 → 후보에 대해서만 문자별로 비교해서 매치를 찾음.

∑ = {a, b, c, d, e .... x, y, z}
M = 101

 

{0, 1, 2, 3, 4 .... 23, 24, 25}

 

P=a a b a a

    0 0 1 0 0

 

h(aabaa)

= (0 × 26^4 + 0 × 26^3 + 1 × 26^2 + 0 × 26^1 + 0 × 26^0) mod 101

= 70

 

즉, P=a a b a a 의 해시값은 70

위치	0	1	2	3	4	5	6	7	8
T	a	a	b	a	a	b	a	a	a
	70	3	78	70	2
P	a	a	b	a	a
P				a	a	b	a	a

 

• 단점 : 각각의 위치마다 해시값을 계산한다는 것 = 각각의 위치마다 패턴의 위치와 비교하는 것 : 이점이 없다.
• 보완
  •  직전 위치의 해시값을 이용하여 상수 시간에 계산 가능
  •  위치 0 : O(m)
    h(aabaa) = (0 × 26^4 + 0 × 26^3 + 1 × 26^2 + 0 × 26^1 + 0 × 26^0) mod 101 = 70
  • 위치 1~n-m : O(1)
    해시 함수의 특징을 이용
    위치 0에서의 첫번째 문자, 위치 1에서의 마지막 문자를 활용
    h(abaab) = (0 × 26^4 + 1 × 26^3 + 0 × 26^2 + 0 × 26^1 + 1 x 26^0) mod 101
    = (26 × h(aabaa) - 0 × 26^5 + 1 × 26^0) mod 101
    = (26 × 70 - 0 + 1)mod101 = 3

• 성능 : O(n+km) (k: 매치의 개수)
  • 전처리 : O(m)
  • 텍스트에서 해시값 계산:  O(n)
  • 후보 위치는 문자 직접 비교, 매치 후보 개수 k :  O(km)
• 매치의 개수가 상수라면 텍스트에서 해시값 계산 : O(n)
• 최악의 경우, 텍스트의 모든 위치에서 매치가 발생하면  : O(nm) 
  브루트-포스와 동일한 방식이 됨.

---

KMP 알고리즘
(Knuth-Morris-Pratt 알고리즘)

• 패턴 내의 문자들의 관계를 이용하여 매칭 시 중복된 비교를 줄임
• 텍스트의 첫 위치에서 패턴의 앞부분부터 문자 비교
• 전처리 - 일치한 서브스트링에 대한 접두부와 접미부의 최대 일치 정보

1. 접두부와 접미수의 최대 일치가 있으면

위치	0	1	2	3	4				f₄ = 1 (위치 4에서 f₄의 값은 접두부의 제일 마지막 위치인 1을 저장해둠)
P	a	a	b	a	a
				a	a 1	b	a	a	패턴의 위치 1이 현재 4의 위치에오도록 한번에 이동 (위치 1 ~ 2는 건너뜀)

 

위치	0	1	2	3	4				f₃ = 0
P	a	a	b	a	a
				a 0	a	b	a	a

 

 

2. 접두부와 접미부의 최대 일치가 없으면 -1 → f₀ = -1

위치	0	1	2	3	4				f₂ = -1
P	a	a	b	a	a
			-1	a	a	b	a	a

 

P =  a  a  b  a  a

F = -1  0 -1 0  1

•  성능
  • 전처리 : O(m)
  • 매칭 : O(n)
  • n≥m : 전체 성능 O(n)
    최악, 최선 구분없이 균일