문자열 (String)

String

문자열이란 말 그대로 문자를 나열한 것을 말합니다.  

패턴 매칭 알고리즘

- 본문이 되는 String에서 특정한 String을 패턴이라하며 이러한 패턴을 찾는 방법을 패턴 매칭이라고 합니다.

고지식한 패턴 검색(Brute Force)

- 본문 String을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식입니다.

특정 문자열에서 찾고자하는 패턴이 존재하는지 확인하려면 다음과 같은 알고리즘을 생각해볼 수 있습니다.

원본[0]과 패턴[0] 비교하여 다르면 원본의 인덱스를 증가시키고 패턴의 인덱스는 다시 0으로 이동시킵니다, 같으면 원본과 패턴의 인덱스를 서로 증가시키며 비교합니다.

고지식한 패턴 검색 구현

public class BruteForce {
    public static void main(String[] args) {
        String origin = "abc 1, 2 ABC";
        char[] originArr = origin.toCharArray();
        
        String search = "1, 2";
        char[] searchArr = search.toCharArray();
        
        System.out.println(bruteForce(originArr, searchArr));
    }
    
    private static boolean bruteForce(char[] origin, char[] search) {
        int index = 0;
        while(index + search.length <= origin.length) {
            boolean match = true;
            for(int j=0; j<search.length; j++) {
                if(origin[index+j] != search[j]) {
                    index++;
                    match = false;
                    break;
                }
            }
            
            if(match) {
                return true;
            }
        }
        
        return false;
    }
}
 

KMP 알고리즘

불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행한다. 

그림에서 보는것처럼 패턴(빨간색) 매칭 도중 E에서 매칭실패가 일어났을 때 비교 인덱스를 1만 이동하는 것이 아니라 4만큼 이동한다. 이 이동거리는 전처리 과정에서 미리 구할 수 있다. 

위의 배열은 전처리 과정으로 구한 배열이고 패턴 매칭이 실패할 경우 패턴의 인덱스를 저장하고 있다. B(1번째) 패턴 매칭이 실패했을 경우 패턴의 비교덱스를 A(0)번째로 이동한 후 다시 비교하라는 것이다. 

( 사실 인덱스0의 값이 왜 -1인지 모르겠음..)

KMP 알고리즘 구현

 
public class KMP {
    public static void main(String[] args) {
        char[] data = "zzzzabcdzzabcdabcefz".toCharArray();
        char[] pattern = "abcdabcef".toCharArray();
        int[] failIndex = {0, 0, 0, 0, 0, 1, 2, 3, 0};
        
        System.out.println(solution(data, pattern, failIndex));
    }
    
    public static int solution(char[] data, char[] pattern, int[] failIndex) {
        int patternIndex = 0 ;
        int resultIndex = -1;
        for(int i=0; i<data.length-pattern.length+1; i++) {
            boolean isMatch = true;
            for(int j=patternIndex; j<pattern.length; j++) {
                
                if(data[i+j] != pattern[j]) {
                    patternIndex = failIndex[j];
                    isMatch = false;
                    break;
                }
            }
            
            if(isMatch) {
                resultIndex = i;
                break;
            }
        }
        
        return resultIndex;
    }
}
 

보이어-무어 알고리즘

패턴을 오른쪽에서 왼쪽으로 비교하고 패턴에 오른쪽 끝에 있는 문자가 불일치하고, 이 문자가 패턴 내에 존재하지 않는 경우 이동거리는 패턴의 길이 만큼이 된다.

위의 예시는 문자열의 B와 패턴의 끝인R은 불일치하고 B는 WATER에 존재하지 않으므로 WATER의 길이인 5만큼 이동한 예시이다.  불일치하는 문자가 패턴에 존재하는 경우는 어떻게 될까?

문자열의 A와 패턴의 끝인 R은 불일치하지만 A는 WATER에 존재하므로 3칸을 이동하여 A의 위치를 일치시킨다. 

보이어-무어 알고리즘에서도 KMP 알고리즘처럼 패턴의 문자가 불일치할 경우 이동해야 할 위치를 데이터 전처리하여 저장한다.

패턴과 불일치하는 문자가 W일 경우는 패턴을 4칸 이동, A일 경우 3칸이동 W, A, T, E, R 외의 모든 문자는 5칸을 이동하면 된다. 

보이어-무어 알고리즘 구현

import java.util.HashMap;
import java.util.Map;
 
public class 보이어_무어 {
    public static void main(String[] args) {
        char[] data = "a pattern matching algorithm".toCharArray();
        char[] pattern = "rithm".toCharArray();
        Map<Character, Integer> failIndex = new HashMap<>();
        failIndex.put('r', 4);
        failIndex.put('i', 3);
        failIndex.put('t', 2);
        failIndex.put('h', 1);
        failIndex.put('m', 0);
        System.out.println(solution(data, pattern, failIndex));
    }
    
    public static int solution(char[] data, char[] pattern, Map<Character, Integer> failIndex) {
        
        int patternIndex = pattern.length-1;
        
        for(int i=0; i<data.length-pattern.length+1; i=i+patternIndex) {
            boolean match = true;
            for(int j=pattern.length-1; j>=0; j--) {
                if(data[i+j] != pattern[j] ) {
                    char failChar = data[i+j];
                    Integer index = failIndex.get(failChar);
                    if(index == null) {
                        patternIndex = pattern.length;
                    } else {
                        patternIndex  = index;
                    }
                    match = false;
                    break;
                }
            }
            
            if(match) {
                return i;
            }
        }
        return -1;
    }
}