- 다양한 주제에 대해 자유롭게 글을 작성하는 게시판입니다.
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 6395 4
4655 영화이번 주 CGV 흥행 순위 [4] + 홍차봇126 17/01/19 126 0
4654 기타Filthy 15 [1] O Happy Dagger142 17/01/19 142 0
4653 IT/컴퓨터비와이패드 [9] 헬리제의우울494 17/01/18 494 0
4652 도서/문학불륜 예술의 진실을 보고 멘붕한 이야기. [17] 와인하우스690 17/01/18 690 6
4651 일상/생각무제... [12] + The Last of Us310 17/01/18 310 0
4650 일상/생각서해대교에서. [1] regentag188 17/01/18 188 0
4649 게임롤챔스 개막전 후기 [19] Leeka283 17/01/17 283 0
4648 사회뉴게(?)를 보고 몇 자 적어보는 구속수사 [8] 烏鳳344 17/01/17 344 16
4647 음악하루 한곡 003. 서진영 - 닮은 사랑 [2] 하늘깃55 17/01/17 55 0
4646 일상/생각가마솥계란찜 [6] tannenbaum224 17/01/17 224 12
4645 기타[불판] 오늘 저녁 스타크래프트 빅매치!! 이영호vs이제동 [156] 김치찌개2636 17/01/17 2636 2
4644 기타낭만닥터 김사부 [3] 김치찌개201 17/01/17 201 0
4643 일상/생각나는 글을 쓰기로 했다 [11] 고양이카페285 17/01/17 285 5
4642 방송/연예비-김태희 결혼 [10] 익금산입412 17/01/17 412 0
4641 기타as tears go by [2] O Happy Dagger122 17/01/17 122 2
4640 정치SBS인터뷰이야기, 문재인 불호 주의 [56] 은머리1179 17/01/17 1179 0
4639 음악하루 한곡 002. 茶太&霜月はるか - 一瞬のクオリア [6] 하늘깃178 17/01/16 178 1
4638 역사여요전쟁 - 6. 싸우기 전에 이긴다 [8] 눈시196 17/01/16 196 8
4637 경제달걀 수입에 대해서 소비자의 입장에서... [13] Liebe490 17/01/16 490 0
4636 사회일본의 긴 근무시간의 종말 - Japan's Rethinking Its Culture of Long Work Hours [6] Rosinante372 17/01/16 372 3
4635 기타On Reading Dictee [2] O Happy Dagger115 17/01/16 115 2
4634 음악김광진님의 노래들 [7] 베누진A140 17/01/16 140 1
4633 기타kilkelly [4] O Happy Dagger174 17/01/16 174 0
4632 게임와우를 접었습니다. [16] 쉬군385 17/01/16 385 1
목록 이전 다음
댓글

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

포럼형 정렬 On