문자열 검색

브루트-포스법

💬  주어진 텍스트에 검색하고자하는 패턴 문자열이 포함되어 있는지를 확인하는 문자열 검색 방법

💬  텍스트와 패턴에 문자열을 하나씩 검색하는 포인터를 설정하여 하나씩 이동하면서 같은지 검사한다.

💬  검사할 때마다 문자열이 다를 경우, 텍스트 포인터를 하나씩 늘려가며 검사한다.

💬  하지만, 검사를 진행한 위치를 기억하지 못하므로 효율이 좋지 않은 알고리즘이다.

class BFmatch {
    // 브루트-포스법으로 문자열을 검색하는 메서드
    static int bfMatch(String txt, String pat) {
        int pt = 0;                // txt 커서
        int pp = 0;                // pat 커서
        
        while (pt != txt.length() && pp != pat.length()) {
            if (txt.charAt(pt) == pat.charAt(pp)) {
                pt++;
                pp++;
            } else {
                pt = pt - pp + 1;  // 포인터를 되돌리고 한 칸 앞으로 이동
                pp = 0;
            }
        }
        
        if (pp == pat.length())    // 검색 성공
            return pt - pp;
        return -1;                 // 검색 실패

 

Boyer_Moore 법

💬  패턴의 마지막 문자부터 역순으로 검사를 진행하면서 일치하지 않는 문자가 나타나면 미리 준비된 테이블 (skip table)에 따라 건너 뛸 칸 수를 정하는 문자열 검색 알고리즘이다.

💬  알고리즘을 적용시킨 시나리오를 이해해 보도록 하자.

  ◽  위의 표와 같은 텍스트와 패턴이 주어졌다고 가정하자. 텍스트는 검사할 문자열이며, 패턴은 텍스트 안에서 찾고자 하는 문자열이다.

  ◽  첫 번째 비교 케이스를 보도록 하자.

  ◽  해당 알고리즘은 문자열 패턴을 뒤에서부터 앞으로 역순으로 검사하는 알고리즘이다.

  ◽  그림에서 보는 바와 같이 첫 비교인 X와 C는 서로 다른 값을 갖는다.

  ◽  이에 따라, 텍스트 포인터를 오른쪽으로 이동시켜 새로운 위치에서 비교를 진행해야 한다.

  ◽  앞서 다뤘던 브루트 포스법처럼 한 칸만 뒤로 이동시키는 것이 아닌, 일정 규칙 (skip table)을 만들어서 상황에 따라 텍스트 포인터를 이동시키는 값을 다르게 한다.

  ◽  일정 규칙을 정의하기 전에 다른 케이스도 살펴보도록 하자.

  ◽  검사를 진행하는 뒤에서부터 첫 번째 인덱스에서 서로 다른 값을 가지지만, 뒤로 한 칸만 이동했다.

  ◽  즉, 검사를 진행하다가 서로 다른 값을 가지는 위치에서의 텍스트의 종류(A)에 따라 뒤로 이동시켜야 하는 칸의 수가 달라지는 것을 알 수 있다.

  ◽  왜냐하면 브루트 포스법처럼 한 칸씩만 일관되게 이동시킬 경우 코드가 비효율적이되며, 아무런 비교도 하지 않고 틀린 부분을 발견했다고 패턴의 수만큼 뒤로 미뤄버리면 중간에 놓치는 경우가 생기기 때문이다.

 

  ◽  이제 위에서 언급했던 일정 규칙 (skip table)을 정의해보자. 테이블은 패턴에 있는 문자에 따라 달라진다.

      ◽  테이블 char 형으로 나타낼 수 있는 문자의 전체인 Character.MAX_VALUE 크기를 갖는 배열로 생성한다.

      ◽  패턴에 들어 있지 않은 문자의 경우, 값을 모두 패턴의 길이 (n)로 초기화한다.

      ◽  패턴에 들어가 있는 문자 중에서, 마지막 인덱스에 해당하는 문자도 마찬가지로 값을 n으로 초기화한다.

      ◽  나머지 패턴에 들어가 있는 문자들은 패턴에서의 문자의 인덱스가 k일 경우 값을 n - k - 1로 초기화한다.

      ◽  패턴 속에서 중복된 문자가 존재할 경우, 가장 뒤에 있는 문자를 기준으로 테이블의 값을 초기화한다.

  ◽  따라서, 위의 A B A C의 패턴을 갖는 문자열의 A, B, C의 테이블 값은 각각 1, 2, 4가 된다.

  ◽  주의해야 할 점은, 테이블의 값의 의미는 "검사가 마무리되지 못하고 문자가 서로 다른 부분이 발견된 지점의 텍스트 포인터에서부터 오른쪽으로 이동시킬 칸의 수"이다.

 

  ◽  그렇다면 왜 지정된 패턴의 마지막 포인터가 아닌, 서로 다른 부분이 발견된 지점에서부터 이동시키는 것일까?

  ◽  만약 위와 같이 검사를 성공한 부분을 무시하고 패턴의 마지막 위치로부터 칸을 이동시키게 되면 놓치고 가는 케이스가 생긴다.

 

  ◽  위에서 설명한 부분을 토대로 전체적인 시나리오를 이해해보자.

  ◽ 테이블 값 ( A, B, C ) = ( 1, 2, 4 )

  ◽  첫 번째 케이스 ( A B C X )

      ◽  첫 번째 비교 : X != C

      ◽  이동 여부 반영 대상 : X

      ◽  X : 패턴 문자열에 포함되어 있지 않음 -> 테이블 값 : 4

      ◽  현재 검사하고 있는 포인터 (3)로부터 4칸을 오른쪽으로 이동한 7로 포인터를 변경

 ◽  두 번째 케이스 ( D E Z C )

      ◽  첫 번째 비교 : C == C

      ◽  두 번째 비교 : Z != A

      ◽  Z :  패턴 문자열에 포함되어 있지 않음 -> 테이블 값 : 4

      ◽  현재 검사하고 있는 포인터 (6)로부터 4칸을 오른쪽으로 이동한 10으로 포인터를 변경

 ◽  세 번째 케이스 ( C A C A )

      ◽  첫 번째 비교 : A != C

      ◽  A :  패턴 문자열에 포함되어 있음 -> 테이블 값 : 1

      ◽  현재 검사하고 있는 포인터 (10)로부터 1칸을 오른쪽으로 이동한 11으로 포인터를 변경

 ◽  네 번째 케이스 ( A C A C )

      ◽  첫 번째 비교 : C == C

      ◽  두 번째 비교 : A == A

      ◽  세 번째 비교 : C != B

      ◽  C :  패턴 문자열에 포함되어 있음 -> 테이블 값 : 4

      ◽  현재 검사하고 있는 포인터 (9)로부터 4칸을 오른쪽으로 이동한 13으로 포인터를 변경

◽  다섯 번째 케이스 ( A C A B )

      ◽  첫 번째 비교 : B != C

      ◽  B :  패턴 문자열에 포함되어 있음 -> 테이블 값 : 2

      ◽  현재 검사하고 있는 포인터 (13)로부터 2칸을 오른쪽으로 이동한 15으로 포인터를 변경

◽  마지막 케이스 ( A B A C )

      ◽  첫 번째 비교 : C == C

      ◽  두 번째 비교 : A == A

      ◽  세 번째 비교 : B == B

      ◽  네 번째 비교 : A == A

      ◽  검사 종료

 

 코드

// Boyer-Moore법으로 문자열을 검색
static int bmMatch(String txt, String pat) {
    int pt;                     // txt 커서
    int pp;                     // pat 커서
    int txtLen = txt.length();  // txt의 문자 개수
    int patLen = pat.length();  // pat의 문자 개수
    int[] skip = new int[Character.MAX_VALUE + 1];  // 건너뛰기 표
    
    // 건너뛰기 표 만들기
    for (pt = 0; pt <= Character.MAX_VALUE; pt++)
        skip[pt] = patLen;
    for (pt = 0; pt < patLen - 1; pt++)
        skip[pat.charAt(pt)] = patLen - pt - 1;  // pt == patLen - 1
    
    
    // 검색
    while (pt < txtLen) {
        pp = patLen - 1;    // pat의 끝 문자에 주목
        
        while (txt.charAt(pt) == pat.charAt(pp)) {
            if (pp == 0)
                return pt;  // 검색 성공
            pp--;
            pt--;
        }
        pt += (skip[txt.charAt(pt)] > patLen - pp) ? skip[txt.charAt(pt)] : patLen - pp;
    }
    return -1;              // 검색 실패
}

 

참고 자료

https://devwooks.tistory.com/12

문자열 검색 (Boyer-Moore 알고리즘)