CHANGEL
SOLID BASICS
CHANGEL

공지사항

  • DEV.CHANGEL PROFILE
  • SOLID BASIC (289)
    • 공부 STUDY (115)
      • JAVA (57)
      • C | C++ (34)
      • CS (11)
      • MySQL (2)
      • ALGORITHM (1)
      • HTML (2)
      • CSS (2)
      • JS (2)
      • CODING (0)
      • MINI PROJECT (3)
    • 스프링 SPRING (21)
      • [SPRING] 김영한 스프링 입문 (11)
      • [SPRING] 남궁성 스프링의 정석 (1)
      • [SPRING] 스프링 핵심원리 (9)
    • 전공 수업 CS (65)
      • Computer Network (13)
      • algorithms (21)
      • Computer Architecture (7)
      • Software Engineering (4)
      • Data Structure (2)
      • DataBase (1)
      • Digital Engineering (14)
      • Discrete Mathematics (3)
      • Introduction to programming (0)
      • Mobile Software (0)
      • Intelligence and Informatio.. (0)
    • 대외활동 (35)
      • 신한은행 대학생 홍보대사 34기 (8)
      • SKT T프렌즈 5기 (13)
      • SK DEVOTION YOUNG 1기 (9)
      • 성균관 대학교 공학교육혁신센터 수강 (3)
      • 수상 기록 (1)
    • 솝트 33기 안드로이드 (7)
      • [솝트 33기] 회고록 (0)
      • [솝트 33기] 안드로이드 왕초보 스터디 (2)
      • [솝트 33기] 코틀린 스터디 (0)
      • [솝트 33기] Git을 털어보자 깃털 스터디 (4)
    • 멋쟁이사자처럼 11기 (6)
      • 멋사 회고록 (4)
      • 백엔드 세션 (1)
      • 기획 세션 (1)
      • 연합해커톤 운영단 (기획팀) (0)
    • 백준 BAEKJOON (16)
    • 독서 BOOK (10)
    • 자격증 CERTIFICATE (1)
    • 준비 서류 및 회고록 MEMOIR (7)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기

최근 댓글

인기 글

CHANGEL

SOLID BASICS

[알고리즘] 스트링 처리 알고리즘 | 보이어 무어 알고리즘
전공 수업 CS/algorithms

[알고리즘] 스트링 처리 알고리즘 | 보이어 무어 알고리즘

2022. 11. 10. 16:19

● 1. 보이어-무어 알고리즘(Boyer-Moore algorithm)

보이어-무어 알고리즘은 문자열 검색에 사용되는 것으로, 이전 포스팅에서 살펴본 KMP 알고리즘의 목적과 유사합니다. 불필요한 것은 건너뛰고, 검색을 빠르게 하자는 것이 주 목표입니다.

보이어-무어 알고리즘은 보통 상황에서 문자열은 앞부분보다는 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용합니다. 그래서 오른쪽 끝부터 비교하게 됩니다.


○ 1-1. 보이어-무어 알고리즘의 예

패턴의 오른쪽 끝에 있는 문자(e)와 본문(z)을 비교하여 일치 여부를 판단합니다. 불일치하고, 이 문자(z)가 패턴(apple)에 존재하지 않는다면, 패턴의 길이만큼 패턴을 이동시킵니다.

만일 패턴의 오른쪽 끝에 있는 문자(e)가 본문(p)와 비교해서 불일치하지만, 본문 문자(p)가 패턴(apple)에 존재한다면, 패턴의 오른쪽 끝에서부터 그 문자(p)까지의 칸 수를 세서 그만큼 이동시킵니다.

즉, 패턴 내에 존재하는 문자에 대하여 오른쪽 끝에서부터 차례대로 한 칸씩 증가하여 이동하게 됩니다.

  • 예를 들어, n a t u r e 라는 패턴을 찾을 경우
    • 패턴의 오른쪽 끝과 본문을 비교한 뒤 본문이 e 였다면 -> 0칸 이동(패턴의 오른쪽 끝에서 두번 째와 본문을 재 비교 → … )
    • 패턴의 오른쪽 끝과 본문을 비교한 뒤 본문이 r 이었다면 -> 패턴을 1칸 이동
    • 패턴의 오른쪽 끝과 본문을 비교한 뒤 본문이 u 이었다면 -> 패턴을 2칸 이동
    • …
    • 패턴의 오른쪽 끝과 본문을 비교한 뒤 본문이 n 이었다면 -> 패턴을 6칸 이동

이렇게 이동시키는 기준을 삼기 위한 테이블을 만들어야 합니다. 여기서는 skip 테이블이라 하겠습니다.

  • skip 테이블의 값은 위 그림처럼 만들 수 있습니다.

본문에서 n a t u r e 를 찾으려고 합니다.

  • 패턴의 e와 본문의 s는 불일치하며, s는 패턴(n a t u r e)에 없는 다른 문자이므로, skip 테이블의 ‘다른 문자’ 를 보고 6칸 이동시킵니다.
  • 이동 결과


  • 패턴의 e와 본문의 n은 불일치하며, n는 패턴(n a t u r e)에 있는 문자이므로, skip 테이블의 ‘n’을 보고 5칸 이동시킵니다.
  • 이동 결과


  • 패턴의 e와 본문의 e는 일치하므로, skip 테이블의 ‘e’를 보고 이동시키지 않습니다. (0칸 이동)
  • 이렇게 오른쪽 끝과 본문이 일치했을 경우, 패턴의 오른쪽 그 다음 끝부터 차례로 본문과 비교합니다.


  • 본문의 문자와 패턴을 차례로 다 비교해서 모두 일치했을 경우 검색이 완료됩니다.
  • 본문이 뒤에 더 있을 경우, 검색 완료 후에도 패턴의 길이만큼 다시 점프해서 검색을 진행합니다.

만약 위처럼 모두 일치하지 않고, 중간에 문자가 달랐다면, 또다시 skip 배열을 보고 점프해 주면 됩니다.

이처럼 보이어-무어 알고리즘은 오른쪽 끝의 문자열과만 비교하여 점프를 진행하므로, 빠르게 검색 효율을 높일 수 있습니다.

 

또한, 이 경우에 모든 문자를 훑어보지 않아도 되므로 시간 복잡도는 O(n) (본문의 문자열의 길이가 n이라 할 때) 보다 대체로 적다고 할 수 있습니다. (최악의 경우에는 O(mn), m은 패턴의 길이)

평균적으로 KMP 알고리즘보다 보이어-무어 알고리즘이 더 높은 성능을 보인다고 알려져 있습니다.

 

 

 

만약 끝 문자열을 포함해 몇 개가 일치하다가 중간에서 불일치 문자를 만나면 어떻게 될까요?

ACBBBCA에서 BBB를 검색해봅시다.

이 때 skip 테이블은 아래와 같습니다.  B가 여러 개 이므로 최소값인 0이 됩니다.

 

0 3

 

'전공 수업 CS > algorithms' 카테고리의 다른 글

[알고리즘] 스트링 처리 알고리즘 | 화일 압축 알고리즘 | 허프만 인코딩  (0) 2022.11.16
[알고리즘] 스트링 처리 알고리즘 | 패턴 매칭 알고리즘  (0) 2022.11.10
[알고리즘] 스트링 처리 알고리즘 | KMP 알고리즘  (0) 2022.11.10
[알고리즘] 쉘 정렬 알고리즘  (1) 2022.10.11
[알고리즘] 삽입 정렬 알고리즘  (1) 2022.10.11
    '전공 수업 CS/algorithms' 카테고리의 다른 글
    • [알고리즘] 스트링 처리 알고리즘 | 화일 압축 알고리즘 | 허프만 인코딩
    • [알고리즘] 스트링 처리 알고리즘 | 패턴 매칭 알고리즘
    • [알고리즘] 스트링 처리 알고리즘 | KMP 알고리즘
    • [알고리즘] 쉘 정렬 알고리즘
    CHANGEL
    CHANGEL
    NOT GIVING UP | SOLID BASICS

    티스토리툴바