- 다양한 주제에 대해 자유롭게 글을 작성하는 게시판입니다.
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 31986 7
15180 정치해외도박사이트의 윤석열 4월 이전 탄핵확률 추이 5 + kien 25/01/01 496 0
15178 일상/생각2024년 취미 활동 결산 메존일각 24/12/31 189 4
15176 생활체육2024년 내란모의 GOAT 운동 결산 4 danielbard 24/12/30 568 2
15175 도서/문학마르크스가 본 1848년부터 1851년까지의 프랑스 정치사 3 카페인 24/12/30 464 4
15174 일상/생각지옥길을 걷고 있다면, 7 호미밭의파스꾼 24/12/30 698 36
15173 스포츠[MLB] 코빈 번스 6년 210M 애리조나행 김치찌개 24/12/30 84 0
15172 스포츠[MLB] 폴 골드슈미트 1년 12.5M 양키스행 김치찌개 24/12/30 103 0
15171 음악[팝송] 카일리 미노그 새 앨범 "Tension II" 1 김치찌개 24/12/30 91 0
15170 여행[2024 나의 이탈리아 여행기] 1. To Rome 2 Omnic 24/12/29 224 7
15169 방송/연예오겜2 짧은 후기 3 Leeka 24/12/29 335 0
15168 도서/문학밀란 쿤데라가 보는 탄핵정국 sisyphus 24/12/28 600 1
15167 정치한강과 이영도: 사랑보다 증오가 쉬운 세상에서 2 meson 24/12/28 489 7
15166 음악[팝송] 더 스크립트 새 앨범 "Satellites" 김치찌개 24/12/28 115 0
15165 오프모임내란 수괴가 만든 오프모임(3) 14 노바로마 24/12/28 720 1
15164 일상/생각공부가 그리워서 적는 대학 첫 강의의 기억 4 골든햄스 24/12/27 494 12
15163 정치검찰 김용현 구속기소 보도자료.jpg 21 매뉴물있뉴 24/12/27 1150 1
15162 일상/생각외줄과 그물 2 호미밭의파스꾼 24/12/27 331 4
15161 의료/건강코로나19 실험실 유출설 11 토비 24/12/27 703 0
15160 육아/가정산타할아버지는 알고 계신대 후기 2 Picard 24/12/27 364 1
15159 정치10월 유신 간단정리 4 매뉴물있뉴 24/12/27 656 2
15157 IT/컴퓨터AI가 점점 무서워지고 있습니다. 7 제그리드 24/12/26 839 0
15156 오프모임정자역 금일 저녁 급 벙개.. 13 Leeka 24/12/26 570 6
15155 일상/생각청춘을 주제로 한 중고생들의 창작 안무 뮤비를 촬영했습니다. 2 메존일각 24/12/24 552 9
15154 문화/예술한국-민족-문화의 정체성에 대한 소고 meson 24/12/24 399 3
목록

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

댓글