패턴 매칭 알고리즘(Brute Force, KMP, 보이어 무어)

두 String의 패턴을 비교할 때 사용하는 알고리즘들을 정리해보자!!

 

1. Brute Force 알고리즘

: 처음부터 끝까지 차례대로 순회하면서 일일이 비교

- 문자가 일치한다면 : 두 String의 index를 한 칸씩 ++

- 문자가 일치하지 않는다면 : 비교 대상의 index를 다시 처음으로

public int BruteForce(String[] p, String[] t){ //p : 패턴, t : 전체 텍스트
    int i = 0; int j = 0;
    while(i < t.length && j < p.length()){
        if(t[i] != p[j]){
            i = i - j;
            j = -1;
        }
        i++; j++;
    }
    if(j == p.length()) return i-p.length(); //패턴 찾음 -- 패턴 시작 index를 return
    else	return i; //패턴 찾지 못하고 끝
}

- 시간 복잡도 : 최악의 경우 O(MN) (M : 패턴 길이, N : 전체 텍스트)

 

 

 

2. KMP 알고리즘

: 불일치가 발생한 String의 앞 부분에 어떤 문자가 있는지 알고 있음

→ 불일치가 발생한 앞 부분은 비교과정을 생략해 시간복잡도를 줄인다.

- 시간복잡도 : O(N+M) (M : 패턴 길이, N : 전체 텍스트)

 

(1) 원리

- 접두사와 접미사가 같은 경우 불필요한 비교를 생략할 수 있다.

KMP의 원리

위 원리대로 알고리즘을 구현하려면 아래 두 과정이 필요하다!!

① pi 배열 : 각 문자에 대해 '접두사==접미사'의 최대 길이 즉, 매칭이 실패했을 때 돌아갈 곳을 미리 계산한 배열

(이런 알고리즘을 "실패 함수"라고도 한다.)

② KMP 알고리즘 : pi배열을 이용해 각 경우에 대한 비교 알고리즘 구현

 

(2) pi 배열 구하기

[변수 설명]

- p : pattern의 char 배열

- j : 접두사의 기준점. 0에서부터 시작

- i : p의 각 char를 check할 때 사용할 인덱스

- pi : '접두사==접미사'의 최대 길이, 실패 시 돌아갈 인덱스를 저장할 배열

 

[알고리즘]

① p[i] == p[j]

: '접두사==접미사'의 길이를 증가시켜준다. 즉, pi[i] = ++j

② j > 0 && p[i] != p[j]

: 현재 접두사와 일치하지 않으므로, 접두사의 기준점을 앞으로 당겨줘야 한다.

즉, j = pi[j-1]

ex> pi[3]을 정하는 과정

A (0)	A (1)	A (2)	B	A	B
	A	A	A
	0	1	2(j)

→ 접두사 AAA와 일치하지 않음. 접두사 기준점을 pi[1]로 조정한다.

 

A (0)	A (1)	A (2)	B	A	B
		A	A
		0	1(j)

→ 접두사 AA와 일치하지 않음. 접두사 기준점을 pi[0]으로 조정한다.

 

A (0)	A (1)	A (2)	B (0)	A	B
			A
			0(j)

→ 접두사 A와도 일치하지 않으므로 pi[3] = 0이 된다.

 

[코드]

public static int[] getPi(String pattern) { //실패함수
	int m = pattern.length();
	int j = 0;
	char[] p = new char[m];
	int[] pi = new int[m];
		
	p = pattern.toCharArray();
	for(int i = 1; i < m; i++) {
		while(j > 0 && p[i] != p[j]) {
			j = pi[j-1];
		}
		if(p[i] == p[j]) {
			pi[i] = ++j;
		}
	}
	return pi;
}

 

(3) KMP 패턴 매칭

[변수 설명]

- p : pattern의 char 배열

- s : str의 char 배열

- j : 현재 비교 중인 p의 index → pi배열을 이용해 조정할 것

- i : 현재 비교 중인 s의 index → 차례대로 증가하면 된다.

- n : str의 길이

- m : pattern의 길이

- pi : (2)를 통해 구한 실패함수 배열

 

[알고리즘]

① s[i] == p[j]

- 일치하므로 pattern의 비교 index j를 1 증가시킨다.

- 단, 모든 pattern의 index를 비교완료했을 때(j == m-1),

    - 결과 ArrayList에 pattern이 시작되는 str의 index를 담는다. → list.add(i-m+1)

    - 다음 pattern을 찾기 위해 j를 pi[j]로 조정한다(jump).  즉, j = pi[j]

② j > 0 && p[i] != p[j]

: pattern이 일치하지 않으므로 j를 pi[j-1]로 조정하여 비교를 수행한다(jump).  즉, j = pi[j-1]

※ 원리는 (2) [알고리즘] - ②와 같다!!

 

[코드]

public static ArrayList<Integer> kmp(String str, String pattern){
	ArrayList<Integer> list = new ArrayList<>();
	int[] pi = getPi(pattern);
	int n = str.length(), m = pattern.length(), j = 0;
	char[] s = str.toCharArray();
	char[] p = pattern.toCharArray();
	
	for(int i = 0; i < n; i++) {
		while(j > 0 && s[i] != p[j]) { //다음 pattern 찾기 시작. j를 재조정
			j = pi[j-1]; //j일때 불일치했으므로 j-1해서!!
		}
		if(s[i] == p[j]) {
			if(j == m-1) {
				list.add(i-m+1); //pattern이 시작하는 str의 index를 추가. 여러경우가 있을 수 있음
				j = pi[j]; //다음 pattern을 찾을 때 시작할 j(실패함수 적용)
			}
			else {
				j++;
			}
		}
		//j == 0이고 s[i] != p[j]일 때는 다음 character로 넘어가고 pattern의 첫번째부터 시행
	}
	return list;
}

 

 

3. 보이어 무어(Boyer-Moore) 알고리즘

: 오른쪽에서 왼쪽 방향으로 비교를 진행하는 알고리즘.

앞쪽보다 뒤쪽에서 불일치가 일어날 가능성이 높다는 발상에서 비롯되었으며, 대부분의 상용 소프트웨어에서 채택하고 있다.

- 시간복잡도 : 최악의 경우에는 O(MN) (M : 패턴 길이, N : 전체 텍스트) / 평균적으로는 텍스트를 모두 보지 않고 넘어가기에 시간 단축을 이끌어 낼 수 있다.

 

(1) 원리

: 오른쪽에서 왼쪽방향으로 비교를 진행한다.

- 문자가 일치할 경우 : str과 pattern 모두 index를 한 칸 앞으로

- 문자가 불일치한 경우

    - str의 문자가 pattern 내에 존재할 경우 : pattern의 해당 문자와 같은 위치를 가질 수 있는 만큼만 skip

    - str의 문자가 pattern 내에 존재하지 않는 경우 : pattern의 길이만큼 skip

→ 'pattern내 문자들의 skip 거리를 담은 자료구조'가 필요하다!

 

(2) pattern 내 문자들의 skip 거리를 담은 자료구조 pi

- 마지막 문자 기준으로 떨어져 있는 거리만큼 skip하면 된다!

ex> pattern = "rithm"

r	i	t	h	m
4	3	2	1	0

- 자료구조 : 해당 문자의 skip 거리를 빠르게 찾기 위해서 HashMap 구조를 사용하는 것이 좋다!

 

보이어-무어 알고리즘 프로세스

 

[코드]

import java.util.*;

public class BoyerMoore {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str = "amptmternomatchingrithmalgorithm";
		String pattern = "rithm";
		ArrayList<Integer> result = boyermoore(str, pattern);
		for(int a : result)	System.out.println(a + str.substring(a, a+1));
	}
	
	public static ArrayList<Integer> boyermoore(String str, String pattern){
		ArrayList<Integer> list = new ArrayList<>();
		HashMap<Character, Integer> hash = makePI(pattern);
		char[] s = str.toCharArray();
		char[] p = pattern.toCharArray();
		int n = str.length(); int m = pattern.length();
		int index = m-1; //str의 인덱스
		while(index < n) {
			for(int i = m-1; i >= 0; i--) {
				//System.out.println(index +" " + s[index] + " " + i + " "+ p[i]);
				if(s[index] == p[i]) { //일치하는 경우
					if(i==0) {
						list.add(index);
						index += m;
						break;
					}
					index--;
				}
				else if(hash.containsKey(s[index])) { //pattern에 있는 문자인 경우
					index += hash.get(s[index]);
					break;
				}
				else { //불일치 & pattern에 없는 문자
					index += m;
					break;
				}
			}
		}
		return list;
	}
	
	public static HashMap<Character, Integer> makePI(String pattern){
		HashMap<Character, Integer> hash = new HashMap<>();
		int m = pattern.length();
		char[] p = pattern.toCharArray();
		for(int i = 0; i < m; i++) {
			hash.put(p[i], m-1-i);
		}
		return hash;
	}
}