본 문서는 러시아어로 쓰인 http://habrahabr.ru/post/132128/의 내용의 구글 번역한 후 내용을 이해할 수 있도록 편역한 것이다.
1. 개요
최근에 나는 쉬프트-OR(http://en.wikipedia.org/wiki/Bitap_algorithm) 알고리즘을 이해해야만 했다. 이 알고리즘은 문자열의 부분 문자열을 찾도록 해준다. 이 알고리즘에 대한 분석 결과에 따라서, 나는 이 알고리즘이 어떻게 나의 알고리즘보다 빠르게 동작하는 지 누군가 이해하는데 도움을 줄거라는 기대하에 이 알고리즘에 대해서 쓰려고 마음먹었다. 실제로, "평범한 비교"와 비교하여 이 알고리즘의 주요한 차이점은, 이 알고리즘이 논리 연산에 기반을 두고 있다는 점이다. 소위 말하는 논리 곱(http://en.wikipedia.org/wiki/Logical_conjunction, 쉽게 말해서, 그것은 AND 비트 연산을 말한다)에 기반을 두고 있다.
2. 알고리즘을 위해서 무엇이 필요한가?
먼저 당신은 몇가지 표기법에 대해 알아야 한다. 우리가 P - 이것은 우리가 문자열에서 찾으려고 하는 패턴, T - 찾아지는 대상 문자열 두 정의를 먼저 가지고 있다고 가정하자. P는 길이 n을 가지고 있고, T는 길이 m을 가지고 있고, 두 문자열 간의 처리 단계를 표현하는 행렬 M(어떻게 학계에서 표현되는 지는 모르겠다)을 생성하는 알고리즘이 있다. 이 행렬은 기본적으로 간단한 이진 배열이다(즉 0과 1만을 값으로 가지고 있다). M은 nx(m+1)의 크기를 가지고 있다. 이 행렬에서, 우리는 i 색인 번호를 1부터 n까지 가지고 있고, j 색인 번호를 0부터 m까지 가지고 있다. 형식적으로 말하자면, 정의에 의해서 "M(i, j) = 1인 요소는 P의 i번째 문자가 j에서 끝나는 T의 기호와 정확하게 일치할 때를 뜻한다". 그에 따라서, 하나의 이진 배열로써, 모든 다른 경우의 요소들은 0의 값을 가지낟. 더 쉽게 이해하기 위해서 M의 예를 보자. 문자열 T = «CALIFORNIA»이고, 우리는 예제 문자열인 P = «FOR»를 찾으려고 한다고 하자.(물론 이렇게 간단한 문자열 T를 선택한 것은 간단히 설명하기 위함이다.) 우리는 문자열 «CALIFORNIA»에 10개의 문자가 있음을 알고 있다. 그러므로 m = 10이다. 그리고 패턴 P는 3개의 문자를 가지고 있다. 그러므로 n = 3이다. 그에 따라서 행렬 M은 3x11의 크기를 가지게 된다. 그래서, 여기에 우리는 다음의 표를 가지게 된다. 당신은 또한 우리에게 가장 중요한 것이 표의 가장 마지막 줄이라는 것을 알 수 있을 것이다. 패턴 P가 완전히 문자열 T에서 찾아지게 되면 다음과 같게 될 것이다.
3. 그래서 어떻게 이 행렬 M을 생성하는가?
그러한 행렬을 프로그램으로 생성하기 위해서, 당신은 두개의 연산을 더 수행해야 한다.
3.1. 이진 벡터 U(x)
이 벡터는 단순히 n의 길이를 가진 이진 문자열(패턴 P와 같이)이다. 벡터에서 P의 문자 중 x와 같은 곳의 위치가 1로 표기된다.
예를 들어, 우리가 P = «ABACDEAB»를 가지고 있다고 하자. 이 경우에, 벡터 U(A) = 10100010이다.
3.2. Bit-Shift(j) 연산
이 연산은 이진 열 j에 대해서 수행된다. 이것은 매우 단순하고, 아래쪽 방향으로 한 열의 쉬프트와 상위 문자로 1이 한 개씩 넘어가는 것만을 포함한다. 열의 길이는 변경되지 않으며, 그에 따라서 마지막 열의 값은 잃게 된다.
예를 들어, 우리가 10의 길이를 가진 열을 가진 0011010101을 가지고 있다고 하자. Bit-Shift연산을 세 번 취하게 되면 어떻게 될까? 아래쪽 그림에서 연한 청록색으로 표기된 벡터의 값들은 원래 열에서 그대로 전달된 값들이고, 노랑색으로 표기된 값들은 Bit-Shift 연산 결과 추가된 값들이다. 실제로 이 두 연산들은 앞으로도 계속 가장 단순하지만 가장 중요한 부분이 된다. 즉 실제 행렬의 생성에 있어서 말이다. 이것은 매우 쉽게 계산된다.
그리고 생성에 대한 다른 예제를 하나 더 들겠다.
우리가 패턴 P = «ABAAC»(n=5)와 T = «XABXABAAXA»(m=10)을 가지고 있다고 하자. 먼저 초기 값으로 0번째 열을 0의 값들로 채운다.
모든 이후의 열들은 이전의 열의 값에 의해서 계산되게 된다. 우리는 다음으로 0번째 열에 대해서 Bit-Shift 연산을 수행하고, 다음의 값을 얻게 된다.
첫 번째 열(j=1)의 U(x)의 계산하자. 여기에서 «x»는 문자열 T의 첫 문자인 'X'이다. 패턴 P에는 «'X'»가 없기 때문에, 모두가 0으로 채워진 열(00000)을 얻게 된다. 우리는 다음으로 이 열들에 대한 AND 논리 곱을 수행한다.
이제 우리는 다음의 행렬을 가지게 된다.
이후의 행렬을 채우는 과정은 완전히 동일하다. 두번째 열에 대한 U 벡터 값의 계산은 U(A) = 10110이고, Bit-Shift(1) = 10000이다(이것이 이해가 되지 않으면 3.2절을 참고하자). 이제 우리가 10000등과 같은 값을 구하면서 알게 된 사실은 바로 이것이다. 각 현재의 열의 값은 이전의 열의 값에 기반을 두고 계산된다는 것이다. 그러므로 행렬 M의 j번째 열을 채우기 위한 일반적인 수식은 다음과 같다.
우리가 이전에 설명한 내용대로 모든 열에 대해 처리를 수행한다면 마침내 다음과 같은 행렬 M을 얻게 된다.
패턴 P를 T에 대해 전부 입력한 상태에서 볼 수 있듯이, 행렬의 마지막 행은 1을 가지고 있지 않기 때문에 완전한 일치를 가지고 있지는 않다. 하지만, 거기에는 부분 일치가 있다.(만약 우리가 그런 결과를 필요로 한다면).
결론
이 알고리즘의 복잡도는 O(mn)이다. 현실적으로 이것은 작지 않다. 하지만, 이 알고리즘은 다른 장점을 가지고 있다. 첫째로, 이것은 구현하기 매우 쉬우며, 어떻게 동작하는 지 쉽게 이해할 수 있다. 둘째로, 행렬 M의 각 열이 이전의 열에 의해서 계산되기 때문에, 우리는 전체 행렬에 대한 메모리를 저장할 필요가 없고, 오직 두 열에 대한 정보만 저장하면 충분하다. 현실적으로, 이 알고리즘은 가령 영어 단어와 같은 작은 길이의 패턴을 찾는데 매우 적합하다. 이 알고리즘의 약간 수정된 버전의 유닉스 구현 유틸리티인 agrep(http://en.wikipedia.org/wiki/Agrep)은 에러를 포함한 패턴을 문자열 내에서 검색한다.
후기
그렇다. 사실 난 같은 내용을 다루는 이 주제(http://habrahabr.ru/post/114997/)를 보았다. 하지만, 그의 글에서, 단순히 설명만 있기 때문에, 나는 예제를 가지고 주제에 대한 더 나은 설명을 하려고 노력했다. 왜냐하면, 내가 생각하기에 몇몇 경우에 어떻게 그것이 동작하는지 보이는 것이 단순히 말하는 것보다 낫다고 생각하기 때문이다.
참고
- 댄 가스필드(Dan Gasfild), 알고리즘에서의 문자열, 트리, 그리고 시퀀스(Strings, tress, and sequences in the algorithms), 2003
- Bitap(http://en.wikipedia.org/wiki/Bitap)
- 구글(Google)
댓글