- 다양한 주제에 대해 자유롭게 글을 작성하는 게시판입니다.
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) 같은 다른 방법도 공부해봐야겠습니다. 시간이 있다면 말이죠…
 




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


목록
번호 제목 이름 날짜 조회 추천
공지 티타임 게시판 이용 규정 [2] Toby 15/06/19 7471 4
5292 정치<피로사회>와 안철수 [1] 三公179 17/03/26 179 3
5291 일상/생각차 사자 마자 지옥의 (고속)도로연수 [45] + SCV355 17/03/26 355 1
5290 일상/생각케이크를 즐기는 남자들. [15] + 숲과바위그리고선363 17/03/25 363 1
5289 사회페다고지와 안드라고지 사이 [7] 호라타래291 17/03/25 291 5
5288 도서/문학인간에 대한 단언적 시선 - 박민규, <그렇습니까? 기린입니다>에 대하여 [36] + 三公597 17/03/25 597 2
5287 기타오래 전 이니그마를 듣다가 [7] 왈츠307 17/03/25 307 1
5286 스포츠170324 오늘의 메이저리그(박병호 1타점 적시타) 김치찌개94 17/03/25 94 0
5285 과학명왕성이 행성 지위를 상실한 이유와 복귀 가능성 [15] 곰곰이449 17/03/24 449 13
5284 일상/생각딸기 케이크의 추억 [54] 열대어658 17/03/24 658 19
5283 사회화장실을 엿본 그는 왜 무죄판결을 받았나 [13] + 烏鳳685 17/03/24 685 26
5282 게임e스포츠 분석 전문 사이트 <eSports Pub>을 소개합니다. [12] 그대지킴이446 17/03/24 446 1
5280 스포츠170323 오늘의 메이저리그(김현수 1타점 적시타) 김치찌개135 17/03/23 135 0
5279 스포츠2017 월드 베이스볼 클래식 미국 우승 [5] 김치찌개194 17/03/23 194 1
5278 경제미세먼지가 많으면 주가가 하락한다? [16] 난커피가더좋아440 17/03/23 440 2
5277 도서/문학안녕하세요, 얼마전 책 나눔판을 벌인 이입니다 [27] 서흔504 17/03/23 504 12
5276 스포츠국내 축구 이야기들 : 2017-1 (1) [12] 별비171 17/03/23 171 2
5275 창작사생연 - 만남 [2] 살찐론도114 17/03/23 114 2
5274 문화/예술지금까지 써본 카메라 이야기(#02) – Konica-Minolta Dynax 7D [22] + *alchemist*184 17/03/23 184 4
5273 IT/컴퓨터애플 시총 7300억 달러 돌파.. 꿈의 1조를 달성할까? [2] Leeka183 17/03/23 183 0
5272 일상/생각누구를 위해 정치에 참여해야 하는가? [2] 뜻밖의317 17/03/23 317 0
5271 영화이번 주 CGV 흥행 순위 홍차봇279 17/03/23 279 0
5270 IT/컴퓨터아이패드 새 모델이 공개되었습니다 [6] Leeka526 17/03/23 526 0
5269 게임 [LOL] 서포터로 바론스틸에 쿼드라킬까지! MVP VS KT 전 후기 [6] Leeka193 17/03/23 193 0
5268 일상/생각친구만들기 [8] 기아트윈스342 17/03/23 342 7
목록 이전 다음
댓글

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

포럼형 정렬 On