suyeonme

[Algorithm/문자열 탐색] 보이어-무어(Boyer-Moore) 알고리즘 본문

프로그래밍👩🏻‍💻/알고리즘

[Algorithm/문자열 탐색] 보이어-무어(Boyer-Moore) 알고리즘

suyeonme 2022. 6. 28. 22:49

1. 보이어-무어(Boyer-Moore) 알고리즘이란?

  • 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하며 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정하는 알고리즘이다.
  • 시간 복잡도는 O(n/m)으로 매우 빠르다.(n은 텍스트의 길이, m은 패턴의 길이)

이미지 출처: https://media.geeksforgeeks.org/wp-content/uploads/bad_match_heuristic_case_1.jpg

2. 동작 방식

문자열 탐색은 패턴의 맨 마지막 글자부터 시작한다.

2.1 Bad Character

  • 패턴의 현재 문자와 일치하지 않는 텍스트의 문자 (패턴: 찾을 문자열, 텍스트: 탐색을 수행할 문자열)
  • Bad Character가 패턴에 존재하는 경우와 패턴에 존재하지 않는 경우를 나누어 접근한다.

Bad Character가 패턴에 존재하는 경우

  1. 인덱스 2에서 불일치 발생 (C는 bad character)
  2. C는 패턴에 존재한다.
  3. 패턴에서 가장 나중에 있는 C의 위치를 현재 패턴의 텍스트 위치로 이동한다.

T G C G A C E B  

A C E                           

    A C E

 

Bad Character가 패턴에 존재하지 않는 경우

  1. 인덱스 2에서 불일치 발생 (B는 bad character)
  2. B는 패턴에 존재하지 않는다.
  3. 따라서 패턴의 위치를 인덱스 3으로 이동한다. 

T GG A C E B  

A C E                           

            A C E

 

3. 구현하기

static int bmMatch(String text, String pattern) {
  int pt; // text 커서 
  int pp; // pattern 커서
  int textLen = text.length();
  int patLen = pattern.length();
  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;
  }
  
  // 문자열 검색
  while(pt < textLen) {
    pp = patLen - 1;
    
    while(text.charAt(pt) == pat.charAt(pp)) {
      if(pp == 00) {
        return pt;
      }
      pp--;
      pt--;
    }
    pt += (skip[text.charAt(pt)] > patLen - pp) ? skip[text.charAt(pt)] : patLen - pp;
  }
  // 검색 실패
  return -1;
}
Comments