- 다양한 주제에 대해 자유롭게 글을 작성하는 게시판입니다.
Date 16/10/04 00:21:55
Name   April_fool
Link #1   http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.63.3421&rep=rep1&type=pdf
Link #2   https://www.youtube.com/watch?v=PHXAOKQk2dw
Subject   컴퓨터는 어떻게 빠르게 검색을 할까 - 보이어-무어-호스풀 알고리즘

황금 같은 주말을 투자해서 업무에 도움이 될 간단한 프로그램 하나를 작성했습니다. 여러 개의 전자도면 파일들 중 원하는 단어가 있는 파일을 찾아내는 프로그램이지요. 그런데 프로그램을 작성하면서, 문득 컴퓨터는 어떤 식으로 주어진 문장 중 원하는 것이 있는 부분을 찾아낼 수 있을까 하는 점이 궁금해졌습니다.
 

제가 프로그램을 만든다면서 왜 그걸 모르느냐고요? 보통 프로그램을 만들 때는 맨 밑바닥에서부터 모든 것을 만드는 것이 아니라, 이미 만들어져서 제공되는 아주 작은 프로그램의 조각을 조합하여 만들게 됩니다. 이 경우는 주어진 문장 속에서 원하는 단어가 있는지 검색하는 함수를 제가 갖다쓴 것이지요. 마치 전자제품을 만들 때 미리 기존에 만들어진 전자부품을 사다가 조립해서 쓰는 것과 같은 이치입니다. 말하자면 저는 라디오를 조립하다가 트랜지스터의 원리가 궁금해진 셈이라고나 할까요.
 

여기서부터는 주어진 문장을 스트링(String), 찾을 단어를 패턴(Pattern)이라고 부르겠습니다. 스트링 속에서 패턴을 찾는 것은 정말 여러 곳에서 쓰입니다. 워드프로세서에서 단어를 찾을 때도, 인터넷에서 뭔가 검색할 때도, 심지어는 과학자들이 DNA를 연구할 때도 쓰이지요. 그래서 이런 분야에 관한 내용은 1970~1980년대에 많이 연구된 것으로 보입니다. 왜 그걸 연구씩이나 하냐고요?
 

컴퓨터가 패턴을 찾는 가장 단순무식한 방법은 바로 한 글자씩 일일히 비교하는 겁니다. 이걸 우직한(주먹구구식) 문자열 검색법(Naïve string search)이라고 합니다. 가장 확실하지만, 아무래도 비효율적이라 시간이 많이 걸립니다. 스트링이나 패턴의 길이가 짧다면 아무 문제가 없겠지만 요즘이 무슨 시대입니까. 바로 빅데이터의 시대가 아니겠습니까. 만약에 수십억 자나 되는 글자를 한 글자씩 일일히 비교하라고 하면, 아무리 컴퓨터가 빨라도 시간이 오래 걸리는 것은 어쩔 수가 없습니다. 그래서 머리 좋은 사람들은 수십 년 전부터 이런 것을 더 효율적으로 할 수 있는 방법을 연구했던 것이죠. 그 중 하나가 이번에 소개하고자 하는 방법인 “보이어-무어-호스풀 알고리즘”(Boyer-Moore-Horspool algorithm)입니다.
 

이 방법의 핵심은 ‘스트링에서 건너뛸 수 있는 만큼은 모두 건너뛴다’는 것입니다. 무슨 소리냐고요?
예를 들어 봅시다. “The quick brown fox jumps over the lazy dog.”라는 스트링에서 “brown”라는 패턴을 검색하려 한다고 하겠습니다. 가능하다면 관련없는 글자들은 그냥 휙휙 지나쳐 버리는 것이 좋을 것입니다. 하지만 원하는 패턴 근처에 가면 신중하게 검색해야겠지요. 이게 바로 이 방법의 핵심입니다.
 

이 방법은 스트링에서 패턴의 맨 마지막 문자를 먼저 찾기 시작하되, 스트링에서 지금 찾고 있는 위치가 관련이 없다 싶은 문자라고 판단하면 패턴의 길이(이 경우는 5글자)만큼 뒤로 점프합니다. 하지만 관련이 있다 싶은 문자다 싶으면 조금만 뒤로 점프하고, 마침내 패턴의 맨 마지막 문자와 일치하는 글자를 찾으면 그 앞부분을 확인하여 패턴과 일치하는지 확인합니다. 만약에 맞으면 원하는 패턴을 찾았다고 보고하고, 아니면 다시 검색을 계속하는 겁니다.
 

그런데, 어떻게 지금 있는 위치의 문자가 패턴과 관련이 있나 없나를 판단하는 걸까요? 또, 패턴과 관련이 있는 문자가 있으면 얼마만큼 뒤로 점프해야 하는 걸까요? 그건 검색을 시작하기 전에 먼저 패턴을 보고 만들어둔 간단한 표를 보고 판단하는 것입니다. “brown”라는 패턴으로 표를 만들면, 맨 뒷글자인 n은 비교 대상이니까 빠집니다. 그리고 패턴의 역순으로 차례대로 숫자를 매깁니다. w는 1, o는 2, r은 3, b는 4가 되지요. 만약 패턴에 같은 문자가 2번 이상 나올 경우, 숫자는 작은 것을 사용합니다. 표에 있는 문자는 패턴과 관련이 있는 것이고, 그 문자에 매겨진 숫자만큼만 뒤로 점프하면 패턴을 찾을 확률이 높은 것입니다.
 

The quick brown fox jumps over the lazy dog.
----n
---------n
--------------n
----------brown

이해가 잘 안 되신다면, 다음 유튜브 동영상을 보시기 바랍니다. 영어로 되어 있지만, 영상만 봐도 이해가 가능합니다.

위에서 한 설명을 파이썬 프로그래밍 언어로 서술하면 다음과 같은 모양새가 됩니다.

  1. # Boyer-Moore-Horspool 알고리즘 예제 - Python3 구현
  2.  
  3. def stringSearch(string, pattern):
  4.     sLength = len(string)
  5.     pLength = len(pattern)
  6.     badMatchTable = {key: pLength - pattern.rindex(key) - 1
  7.                     for key in pattern[:-1]}
  8.     i = pLength - 1
  9.     last = pattern[i]
  10.     while i < sLength:
  11.         char = string[i]
  12.         if char == last:
  13.             first = i - pLength + 1
  14.             if string[first:i+1] == pattern:
  15.                 return first
  16.         i += badMatchTable.get(char, pLength)
  17.     return False

눈치빠른 분들은 눈치채셨을지도 모릅니다만, 이 방법은 패턴의 길이가 길면 길수록 효율이 올라간다는 특징이 있습니다. 또, 스트링이 아니라 패턴을 전처리하는 방법이기 때문에, 일반적으로 여러 번 검색하지 않을 텍스트를 대상으로 적용하는 것이 더 효과적이라고 합니다.
 

사실 이 방법은 1977년에 나온 “보이어-무어 알고리즘”(Boyer–Moore algorithm)을 당시 캐나다 맥길대학 교수인 니겔 호스풀이 간략하게 바꾼 것입니다. 보이어-무어 알고리즘은 성능이 뛰어나기 때문에 GNU grep을 비롯한 여러 곳에 사용되며 문자열 검색 알고리즘 성능 비교의 표준으로 쓰이고 있지만, 비교적 복잡하다는 단점이 있습니다. 그것을 가장 중요한 부분만 남긴 것이 바로 이 방법인 것이죠. 이것 외에도 문자열을 빠르게 검색하는 알고리즘은 많이 있지만, 비교적 단순하여 이해하기 쉬운 것을 고르다 보니 이 방법을 골라 공부하게 되었네요. 다음에는 크누스-모리스-프랫 알고리즘(Knuth–Morris–Pratt algorithm) 같은 다른 방법도 공부해봐야겠습니다. 시간이 있다면 말이죠…
 




7
  • 컴공컴공하네요 ㅊㅊ
  • 춫천


목록
번호 제목 이름 날짜 조회 추천
공지 티타임 게시판 이용 규정 [2] Toby 15/06/19 10651 4
7134 일상/생각나의 커피 컵 이야기 [8] + Liebe195 18/02/18 195 0
7133 방송/연예9년을 봐온 무한도전의 끝. [6] + 은우390 18/02/18 390 0
7132 철학/종교나무꾼이 성범죄자인가요? [24] 신내림676 18/02/17 676 0
7131 영화마이클 베이의 트랜스포머 유니버스가 리부트 됩니다. [2] 키스도사160 18/02/17 160 0
7130 과학/기술인공지능 로봇 소피아의 방한 행사 소동 [3] 맥주만땅287 18/02/17 287 0
7129 역사작전과 작전 사이 (4) - 무신불립 호타루57 18/02/17 57 2
7128 게임젤다의 전설 플레이 도중 1차 후기 (스포 없음) [4] Leeka238 18/02/16 238 1
7127 음악'그리부예'의 2017년 선곡 리스트 [2] 발타자르176 18/02/16 176 5
7126 오프모임이태원 올댓재즈 [32] 반짝반짝904 18/02/16 904 2
7125 일상/생각어제, 오늘 국도로 부산-대구를 왕복한 이야기 [5] 맥주만땅421 18/02/16 421 0
7124 과학/기술카팩 고장난 문제 해결한 썰 [10] Toby440 18/02/16 440 5
7123 의료/건강백신과 antibody dependent enhancement moneyghost175 18/02/16 175 6
7122 도서/문학니체가 눈물을 흘릴 때 [3] 알료사295 18/02/16 295 0
7120 스포츠180215 케빈 듀란트 50득점 7리바운드 6어시스트.swf 김치찌개90 18/02/15 90 1
7119 게임[데이터/브금 주의] 클라이언트의 의뢰에 맞추어 스1맵을 만들어보자 [5] 유자농원209 18/02/15 209 2
7118 육아/가정셀프 도배 하는 법 [7] Toby520 18/02/15 520 1
7117 영화이번 주 CGV 흥행 순위 홍차봇209 18/02/15 209 0
7116 도서/문학별의 계승자 / 제임스 P. 호건 [14] 임아란345 18/02/14 345 6
7115 일상/생각화를 다스리는게 어렵습니다. [8] 알료사556 18/02/14 556 1
7114 스포츠180214 르브론 제임스 37득점 8어시스트 7리바운드.swf 김치찌개63 18/02/14 63 1
7113 게임RTS 신작 노스가르드 소개(얼리억세스) Weinheimer200 18/02/14 200 6
7112 요리/음식떡볶이 부터 시작된 정크푸드에 대한 진영싸움 [14] 맥주만땅775 18/02/14 775 2
7111 스포츠180213 스테판 커리 22득점 9리바운드 7어시스트.swf 김치찌개78 18/02/13 78 1
7110 스포츠180212 오늘의 NBA(르브론 제임스 24득점 10어시스트 8리바운드) 김치찌개50 18/02/13 50 1
목록 이전 다음
댓글

+ : 최근 2시간내에 달린 댓글
+ : 최근 4시간내에 달린 댓글