11. 문자열 찾기 (String Matching Algorithm)

  앞서 배운 Space-time trade off 알고리즘의 응용해여 장문에서 특정 문자열을 찾는 프로그램을 구현해보자. 보기가 되는 텍스트를 보고 내가 찾고자 하는 단어가 몇번째에 행에 나오는지 찾는 과정이다.

An automaton is a self-operating machine or a machine or control mechanism designed to automatically follow a predetermined sequence of operations, or respond to predetermined instructions.

  위 문장은 영문 위키백과에 나온 오토마타(자동기계)에 관한 정의이다. 위 텍스트에서 우리가 찾고자 하는 단어는 sequence이다. 이 단어를 아래 알고리즘들이 얼마나 빨리 찾아내는지 분석 해볼것이다. 물론 자바 Collection을 이용한다면 아래와 같은 복잡한 알고리즘 없이 충분히 위치를 찾아 낼 수 있다. 하지만 알고리즘을 풀어 내는것이 가능한지 살펴 보기 위해 다소 불편한 작업을 거쳐서 소개할것이다.

1. Brute-Force Algorithm

  우선 문장 전체를 하나하나 읽어가며 찾아내는 Brute-Force 알고리즘으로 단어를 찾아 볼 것이다. 원리는 매우 간단하다. 위에 있는 텍스트의 모든 위치에서 해당 단어가 있는지 찾아보는 방법이다. 예를 들자면, A 위치에서 sequence를 찾고, n 위치에서 다시 찾고 다시 공백위치에서 찾는 과정을 계속 반복하게 된다. 만약 self-operating에 위치에 도달 할때는 시작 단어가 s로 같으므로 해당 위치에서 그대로 있는 채 e,l을 확인해 나간다. l에 도달하면 단어가 아니라고 판단이 되므로, 다시 그 다음 위치인 e로 연결이 된다. 해당 알고리즘을 코드로 구현하면 아래와 같다. 

import java.util.Scanner;
 
public class Solution {
    
    public static String Text;
    public static String Pattern;
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        getText();
        getPattern();
        
        // 이곳에 함수명을 변경하여 사용한다.
        long startTime = System.nanoTime();
        System.out.println(BruteForce(Text,Pattern));
        long endTime = System.nanoTime();
        
        System.out.println("Time :"+(endTime - startTime));
    }
    
    // 알고리즘이 작성 되는 부분
    public static int BruteForce(String text, String pattern){
        int answer;
        
        // 알고리즘
        for(int i=0;i<(text.length()-pattern.length());i++){
            int j=0;
            while((j<pattern.length())&&text.charAt(i+j)==pattern.charAt(j)){
                j++;
                if(j==pattern.length()){
                    answer=i;
                    return answer;
                }
            }
        }
        return -1;
        
    }
    
    public static void getText(){
        Scanner sc = new Scanner(System.in);
        
        System.out.println("Enter the Text :");
        Text=sc.nextLine();
        System.out.println("Text_length: "+Text.length());    
    }
    
    public static void getPattern(){
        Scanner sc = new Scanner(System.in);
        
        System.out.println("Enter the Pattern :");
        Pattern=sc.nextLine();
        System.out.println("Pattern_length: "+Pattern.length());
    }
 
}
 

  코드가 매우 직관적이라서 프로그래밍하기 매우 쉽고, 별도의 공간도 필요 없는 알고리즘이다. 다만 텍스트의 길이가 n이라면 총 n번의 비교를 실시하고, 해당 위치에서 동일한 단어가 존재한다면 패턴의 길이 m만큼 비교를 수행해야한다. 따라서 Brute-Force 알고리즘의 시간 복잡도는 O(mn)으로 나온다.

  하지만 텍스트안에 패턴이 존재한다면 패턴과 정확히 모든 알파벳이 일치해야한다. 가령 sequence라는 단어를 찾는 다면, 패턴의 마지막 위치인 7 (0~7)을 기준으로 비교를 실시하고, 텍스트의 7번위치에 패턴에 해당되는 알파벳이 없다면 0~7번째 위치에서는 패턴이 존재하지 않는다. 이런 방식으로 줄여 나간다면 더 효율적인 알고리즘을 개발할 수 있다.

2. Horspool's Algorithm

  Horspool's Algorithm은 앞서 말한 개념을 적용해 텍스트에서 패턴을 찾아내는 알고리즘이다. 텍스트 상에서 패턴의 길이 만큼 뒤로 간 다음 패턴 상에 해당 알파벳이 존재하는지 확인한다. 위 방식은 총 4가지 케이스로 구분 할 수 있다.

- Case 1 : 텍스트에 존재하는 알파벳이 패턴 상에 존재하지 않는 경우

  1번 케이스에서는 패턴의 길이 만큼 뒤로 가서 다시 탐색하면 된다.

- Case 2 : 검사하는 텍스트 상의 알파벳이 패턴 마지막 알파벳인 경우

  2번 케이스에서는 앞으로 이동하면서 패턴과 텍스트가 일치하는지 확인한다.

*

- Case 3 : 2번 케이스에 따라 검사하다가 패턴 안에 있는 알파벳과 텍스트 안에 있는 알파벳이 서로 다른경우 

  처음 검사했던 위치를 기준으로 다시 패턴을 뒤로 보내면 된다.

- Case 4 : 패턴의 마지막 글자가 패턴 상에서 2개 이상인 경우

  텍스트와 일치하는 지 검사를 하는 도중 패턴 상의 글자가 다르게 되면 중복되는 알파벳이 있는 위치로 이동한다.

  만약 4개의 케이스를 매번 검사하게 된다면 Brute Force 보다 안좋은 성능의 알고리즘이 나오게 된다. 패턴에 있는 알파벳을 보고 Shift Table을 만들어 텍스트 상의 알파벳을 검사하면서 이동 할 거리를 미리 계산해야 한다. 만약 sequence라는 패턴에 대한 Shift Table은 아래와 같이 만들어진다.

  즉, 검사할 위치에서 해당 알파벳이 발견 된다면 검사할 위치를 테이블에 입력된 숫자 만큼 이동 시킨다. 텍스트를 검색하는데 알파벳 a가 발견된다면은 검사 위치를 8칸 뒤로 이동시킨다. 위에 표시된 Case1과 같은 경우이다. 하지만 c라는 알파벳이 발견 되었다면 검사 위치를 1만 이동시켜 다시 검색한다. 위에 표시된 Case2와 같은 경우이다.

  Horspool's Algorithm으로 구현 한다면 아래와 같은 코드를 구할 수 있다.

import java.util.HashMap;
import java.util.Hashtable;
import java.util.Scanner;
 
public class Solution {
    
    public static String Text;
    public static String Pattern;
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        getText();
        getPattern();
        
        // 이곳에 함수명을 변경하여 사용한다.\ 
        long startTime = System.nanoTime();
        System.out.println(Hospool(Text, Pattern));
        long endTime = System.nanoTime();
        
        System.out.println("Time :"+(endTime - startTime));
    }
    
    // 알고리즘이 작성 되는 부분
    public static int Hospool(String text, String pattern){
        
        HashMap<Character, Integer> hashmap = getShifttable(pattern);
        
        int textLength = text.length();
        int patternLength = pattern.length();
        
        int i, j;
        Integer shift;
        for (i = patternLength - 1; i < textLength; shift =hashmap.get(text.charAt(i)),  i += shift != null? shift: patternLength ) {
            for (j = 0; (j < patternLength) && (text.charAt(i - j) == pattern.charAt(patternLength - 1 - j)); j++) ;
            if (j == patternLength)
                return i - patternLength + 1;
        }
        return -1;
        
    }
    
    private static HashMap<Character, Integer> getShifttable(String pattern) {
        // TODO Auto-generated method stub
        HashMap<Character, Integer> hashmap = new HashMap<>();
        int len = pattern.length();
        for (int i = 0; i < len - 1; i++)
            hashmap.put(pattern.charAt(i), len - 1 - i);
        
        return hashmap;
    }
 
    public static void getText(){
        Scanner sc = new Scanner(System.in);
        
        System.out.println("Enter the Text :");
        Text=sc.nextLine();
        System.out.println("Text_length: "+Text.length());    
    }
    
    public static void getPattern(){
        Scanner sc = new Scanner(System.in);
        
        System.out.println("Enter the Pattern :");
        Pattern=sc.nextLine();
        System.out.println("Pattern_length: "+Pattern.length());
    }
 
}
 

  Horspool's Algorithm은 Shift table이 존재하므로 패턴의 길이 만큼의 추가 공간이 필요합니다. 따라서 공간 복잡도는 O(m)이 된다. 시간 복잡도는 O(m+n/m) 이 된다. m은 패턴의 길이를 뜻하고, Shift table을 만드는 데 걸리는 시간이다. n은 텍스트의 길이를 의미하고, 위 알고리즘을 사용하게 된다면, 검색 횟수를 n/m만큼 줄일 수 있다. 물론, n/m은 best Case이다. Worst Case의 시간복잡도는 BruteForce와 동일한 O(mn)이 된다. 

  텍스트 길이가 월등히 길고 패턴의 길이가 짧아 Pattern의 Shift table이 작을 수록 유리한 알고리즘이다.

3. Boyer-Moore Algorithm

  Horspool's Algorithm은 Shift table이라는 추가 공간을 활용해 더 빠른 속도로 문자열을 찾는 알고리즘이다. Boyer Moore 역시 두개의 Shift table을 이용해 더욱 빠른 문자열을 찾는 알고리즘이다. 

Boyer-Moore Algorithm은 총 2개의 테이블이 필요하다. Bad-symbol table과 Good-suffix table이다.

 - Bad-symbol table

  매칭되지 않은 텍스트의 문자를 기반으로 이동 거리를 계산한다.

 - Good-symbol table

  패턴의 매칭된 부분을 기반으로 이동 거리를 계산한다.

  Horspool's algorithm에서는 good-symbol table이 존재하지 않아 패턴에서 나오는 부분을 기반으로 움직이지는 않는다. 예를 들어 abcbab라는 알파벳을 찾는 가정할 때, AB가 텍스트 상에서 보여지면 B를 발견하면 2칸 앞으로 이동하게 된다. 하지만, Boyer-Moore Algorithm을 적용하면 AB가 존재하게 되면 Good-symbol table에 따라 한번에 4칸을 이동하게 된다. 이 점을 이용해 Horspool보다 너 나은 성능의 알고리즘을 만들 수 있다.

import java.util.HashMap;
import java.util.Scanner;
 
public class Solution {
    
    public static String Text;
    public static String Pattern;
 
    private final static int SIZE = 256;
    private static int lastOccurrence[] = new int[SIZE];
    
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        getText();
        getPattern();
        
        // 이곳에 함수명을 변경하여 사용한다.
        long startTime = System.nanoTime();
        System.out.println(BoyerMoore(Text,Pattern));
        long endTime = System.nanoTime();
        
        System.out.println("Time :"+(endTime - startTime));
    }
    
    private void buildIndex(String pattern) {
        
        int length = pattern.length();
        
        for (int i = 0; i < SIZE; i++)
            lastOccurrence[i] = -1;
        
        for (int i = 0; i < length; i++)
            lastOccurrence[pattern.charAt(i)] = i;
    }
    
    private static int findLast(char aChar) {
        
        return lastOccurrence[aChar];
    }
    
    // 알고리즘이 작성 되는 부분
    public static int BoyerMoore(String text, String pattern){
        
        int start = pattern.length() - 1;
        int end = text.length();
        int position, j;
        
        // search from left to right
        while (start < end) {
            
            position = start;
            
            for (j = pattern.length() - 1; j >= 0; j--) {
                
                // if not match a character
                if (pattern.charAt(j) != text.charAt(position)) {
                    
                    // check the last occurrence index
                    if (findLast(text.charAt(position)) != -1) {
                        
                        if (j - findLast(text.charAt(position)) > 0)
                            // case 1
                            start += j - findLast(text.charAt(position));
                        else
                            // case 2
                            start += 1;
                        
                    } else {
                        
                        // case 3
                        start += j + 1;
                    }
                    
                    break;
                }
                
                if (j == 0) {
                    
                    // found pattern
                    return position;
                }
                
                position--;
            }
        }
        
        // not found
        return -1;
    }
    
    public static void getText(){
        Scanner sc = new Scanner(System.in);
        
        System.out.println("Enter the Text :");
        Text=sc.nextLine();
        System.out.println("Text_length: "+Text.length());    
    }
    
    public static void getPattern(){
        Scanner sc = new Scanner(System.in);
        
        System.out.println("Enter the Pattern :");
        Pattern=sc.nextLine();
        System.out.println("Pattern_length: "+Pattern.length());
    }
 
}
 

  Boyer-Moore 알고리즘의 공간복잡도는 O(2m)이다. 그리고 시간복잡도는 최고의 케이스와 최악에 케이스에서 차이가 많이 발생한다. Best Case에서는 O(m+n/m)의 알고리즘이 가능하다. 반면 최악의 경우는 Brute Force와 동일한 O(nm)이다.

  텍스트에서 일정한 문자열 패턴을 찾는 알고리즘 3가지를 보았다. 코드의 결과로만 본다면 가장 좋은 알고리즘은 Brute Force이지만, 단 한 문장의 텍스트 만을 가지고 테스트를 했기 때문에 사전 작업이 긴 Horspool이 가장 길게 나오게 된 것이다. 실제로 긴 문장과 테스트 케이스가 증가하게 된다면 분명 결과는 달라 질 것이다. 문자열 찾기의 기본 매커니증은 공간을 활용하여 시간을 단축시키는 방법이다. Shift table을 이용해 더 나은 결과의 알고리즘을 도출 할 수 있다.

- 코드 참조

https://github.com/shengzhouzhang/Boyer-Moore

https://github.com/vinyasns/pattern_matching_horspool