태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.

String matching

Tech 2007. 10. 31. 21:19
까먹지 않기 위해 간단하게 정리

Text.length = N
String.length = M
N > M

Goal: Text에 String의 출현을 찾고싶다.
ex: Text = "Computer Organization & Design" , String = "tion" 인 경우 17(0부터 시작하여 Text에 tion의 t가 등장하는 인덱스)을 찾고싶음.

1. Brute force
  - O(NM)
  - Text의 i 번째 문자와 string의 j 번째 문자를 비교해서 일치하면 i++, j++ / 일치하지 않으면 i = i - j + 1 => j == M - 1 이면 Bingo!

2. Knuth-Morris-Pratt (KMP)
  - String을 오토마타로 표현 -> Text를 넣고 final state에 도달하면 Bingo!

3. Boyer-Moore
  - String의 오른쪽부터 비교 + 일치하지 않은 경우 Text의 문자가 String에 없으면 whole skipping, 있으면 그 문자와 align 시킴.
  - Text의 i 번째 문자와 string 의 j 번째 문자를 비교해서 일치하면 i--, j-- / 일치하지 않으면 Text의 i 번째 문자가 string의 몇 번째(k) 문자인가 확인 => k가 존재하면 i = i + M - k, j = M - 1

 4. Rabin-Karp
  - String을 한번에 넣어 숫자를 내보내는 hash function 준비 => Text[i..i+M-1], 0 <= i < N - M 에 대한 hash를 모두 계산 => String 의 hash value와 동일한 녀석을 찾음


String이 regex로 표현된 패턴인 경우 -> 2번 KMP method를 일반화시켜 오토마타 생성 => 텍스트 넣음 방식 ㄱㄱ


2, 3, 4 번은 모두 O(N+M) 으로 얼추 선형시간에 나옴.

'Tech' 카테고리의 다른 글

Fib(n) = Fib(n-1) + Fib(n-2), Fib(1) = Fib(2) = 1  (4) 2007.11.02
Nutch Crawler, briefly  (1) 2007.10.31
String matching  (3) 2007.10.31
SSH Key distribution  (2) 2007.10.24
C++: stringstream  (2) 2007.10.23
USB 2.0 Interface activated with External HDD  (0) 2007.09.07
Trackbacks 0 : Comments 3
  1. Favicon of http://etnalry.tistory.com etnalry 2007.11.01 13:35 신고 Modify/Delete Reply

    음.. 정말 비교되게 빠를까?

    • Favicon of http://deisys.net deisys 2007.11.01 14:39 Modify/Delete

      해볼까? ㅎㅎㅎ

    • Favicon of https://deisys.tistory.com 가난한 d-goon 2007.11.02 23:31 신고 Modify/Delete

      Rabin-Karp 빼고 나머지 세개 해봤음.

      반지의제왕1,2,3권+호빗+1984+타임머신 의 영문 텍스트를 모두 더한 녀석으로 이것저것 실험... 결과는,

      BruteForce >= KMP >>>>>>> BM

      결론은 BM 쓰자.

Write a comment