Bitap2 쉬프트-OR 문자열 검색 알고리즘의 설명(Shift OR Algorithm) 본 문서는 러시아어로 쓰인 http://habrahabr.ru/post/132128/의 내용의 구글 번역한 후 내용을 이해할 수 있도록 편역한 것이다. 1. 개요 최근에 나는 쉬프트-OR(http://en.wikipedia.org/wiki/Bitap_algorithm) 알고리즘을 이해해야만 했다. 이 알고리즘은 문자열의 부분 문자열을 찾도록 해준다. 이 알고리즘에 대한 분석 결과에 따라서, 나는 이 알고리즘이 어떻게 나의 알고리즘보다 빠르게 동작하는 지 누군가 이해하는데 도움을 줄거라는 기대하에 이 알고리즘에 대해서 쓰려고 마음먹었다. 실제로, "평범한 비교"와 비교하여 이 알고리즘의 주요한 차이점은, 이 알고리즘이 논리 연산에 기반을 두고 있다는 점이다. 소위 말하는 논리 곱(http://en.wiki.. 2012. 12. 29. Shift-And 문자열 검색 본 문서는 Algorithms on Strings Trees and Sequences의 내용을 일부 번역한 것이다. Shift-And 문자열 검색 R. Baeza-Yates와 G. Gonnet 씨는 상대적으로 짧은 패턴(예를 들어, 전형적인 영어 단어의 길이)의 완전 일치 검색을 매우 효율적으로 해결하는 비트 기반의 방법을 고안하였다. 그들은 이 방법을 Shift-Or 방식이라고 불렀지만, 이것은 Shift-And라고 부르는 것이 더 적절할 것 같다. 패턴 P가 n의 길이를 가지고 있고, 참조 문자열 T가 m의 길이를 가지고 있다고 하자. 정의 M은 (n)X(m+1)의 행렬이고, 행 순서 i는 1부터 n의 길이를 가지고, 열 순서 j는 1부터 m까지라고 하자. 한 요소 M(i, j)는 P의 첫 i번째 문.. 2012. 11. 28. 이전 1 다음
