- 회원들이 추천해주신 좋은 글들을 따로 모아놓는 공간입니다.
- 추천글은 매주 자문단의 투표로 선정됩니다.
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) 같은 다른 방법도 공부해봐야겠습니다. 시간이 있다면 말이죠…
 

* 수박이두통에게보린님에 의해서 티타임 게시판으로부터 게시물 복사되었습니다 (2016-10-17 09:22) * 관리사유 : 추천 게시판으로 복사합니다.



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


목록
번호 제목 이름 날짜 조회 추천
1376 기타삶의 의미를 찾는 단계를 어떻게 벗어났냐면 8 골든햄스 24/03/14 907 18
1375 기타소수 사막은 얼마나 넓을까? 4 + Jargon 24/03/06 862 4
1374 기타민자사업의 진행에 관해 6 서포트벡터 24/03/06 813 8
1373 기타노무사 잡론 13 당근매니아 24/03/04 1518 16
1372 기타2024 걸그룹 1/6 2 헬리제의우울 24/03/03 605 13
1371 기타소회와 계획 9 김비버 24/03/03 846 20
1370 기타터널을 나올 땐 터널을 잊어야 한다 20 골든햄스 24/02/27 1553 56
1369 정치/사회업무개시명령의 효력 및 수사대응전략 8 김비버 24/02/21 1399 16
1368 체육/스포츠(데이터 주의)'자율 축구'는 없다. 요르단 전으로 돌아보는 문제점들. 11 joel 24/02/19 951 8
1367 역사 AI를 따라가다 보면 해리 포터를 만나게 된다. 4 코리몬테아스 24/02/18 1047 11
1366 체육/스포츠(데이터 주의)'빌드업 축구'는 없다. 우루과이전으로 돌아보는 벤투호의 빌드업. 13 joel 24/02/12 1322 30
1365 기타자율주행차와 트롤리 딜레마 9 서포트벡터 24/02/06 1182 7
1364 영화영화 A.I.(2001) 18 기아트윈스 24/02/06 1114 23
1363 정치/사회10년차 외신 구독자로서 느끼는 한국 언론 32 카르스 24/02/05 2542 12
1362 기타자폐아이의 부모로 살아간다는건... 11 쉬군 24/02/01 2148 69
1361 일상/생각전세보증금 분쟁부터 임차권 등기명령 해제까지 (4, 完) 6 양라곱 24/01/31 2809 37
1360 기타텃밭을 가꿉시다 20 바이엘(바이엘) 24/01/31 998 10
1359 일상/생각한국사회에서의 예의바름이란 18 커피를줄이자 24/01/27 6530 3
1358 일상/생각전세보증금 분쟁부터 임차권 등기명령 해제까지 (3) 17 양라곱 24/01/22 6160 22
1357 일상/생각전세보증금 분쟁부터 임차권 등기명령 해제까지 (2) 17 양라곱 24/01/17 5686 14
1356 요리/음식수상한 가게들. 7 심해냉장고 24/01/17 1251 20
1355 일상/생각전세보증금 분쟁부터 임차권 등기명령 해제까지 (1) 9 양라곱 24/01/15 2670 21
1354 기타저의 향수 방랑기 31 Mandarin 24/01/08 3292 2
1353 의료/건강환자의 자기결정권(autonomy)은 어디까지 일까? 7 경계인 24/01/06 1274 21
1352 역사정말 소동파가 만들었나? 동파육 이야기. 13 joel 24/01/01 1305 24
목록

+ : 최근 6시간내에 달린 댓글
+ : 최근 12시간내에 달린 댓글

댓글