본 문서는 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번째 문자들이 j번째 문자에서 끝나는 T의 i번째 문자와 완전히 일치할 때만 1이다. 그렇지 않으면 요소는 0이다.
다시 말하자면, M(i, j)는 만약 P[1..i]가 T[j - i + 1..j]과 완전히 일치할 때만 1이다. 예를 들어, 만약 T=california이고 P=for라면, M(1, 5) = M(2, 6) = M(3, 7) = 1 이다. 반면, 이와 다른 i, j 값의 조합에 대해서 M(i, j)=0이다. 기본적으로, 1의 값을 가지는 M의 i번째 행은 P[1..i]가 끝나는 T의 모든 위치를 보여주고, 1의 값을 가지는 M의 열 j는 T의 j 위치에서 끝나는 모든 P의 접두사를 보여준다.
명백히, T의 j에서 P가 일치되는 것이 끝나게 되면, M(n, j)=1이다.그렇기 때문에 M의 마지막 행을 처리하는 것은 완전 일치 검색을 수행하는 것과 마찬가지이다. M을 계산하기 위해서 먼저 주어진 문자 집합에서 각 문자 x에 대해서 n 길이의 이진 벡터 U(x)를 모두 구한다. U(x)는 P에서 문자 x가 나타날 때 1로 설정된다. 예를 들어, 만약 P=abacdeab 일 때, U(a)=10100010이다.
정의 Bit_Shift(j-1)은 열 j-1 번째의 벡터에 쉬프트를 수행하여 얻어지는 벡터로써, 비트를 한 칸 아래로 이동시키고, 다음 비트에 1을 설정한다. 그리고 n의 위치에 있는 이전의 비트는 사라지게 된다. 다른 말로 하면, Bit-Shift(j-1)은 j-1 번째 열의 첫 n-1 개의 비트와 함께 마지막 비트에 1을 가지도록 한다.
예를 들어, 다음은 비트-쉬프트를 수행한 전후의 열 j - 1의 값을 보인다.
Bit-Shift(j - 1) 전후의 j-1 번째 열
Bit-Shift(j-1) 전 | Bit-Shift(j-1) 전 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
배열 M의 생성
배열 M은 다음과 같이 열의 순서대로 생성하게 된다. 만약 T(1)≠P(1)이면, M의 1 번째 열은 모두 0인 요소로 초기화 된다. 아니면, T(1) = P(1)일 때, 그것의 첫 요소가 1이고 나머지 요소는 0으로 초기화 된다. 그 다음에 j > 1보다 큰 열의 요소들이 j -1 번째 열과 문자 T(j)를 이용하여 구한 U 벡터로 부터 얻어지게 된다. 더 자세히 말하자면, 열 j에 대한 벡터는 Bit-Shift(j - 1)의 백터와 문자 T(j)를 이용하여 구한 U 벡터의 비트 AND 연산에 의해서 얻어진다. 좀더 형식적으로 말하자면, 만약 우리가 M(j)를 M의 j 번째 열을 표현하기 위해 사용한다면, M(j) = Bit-Shift(j - 1) AND U(T(j))가 된다. 예를 들어, 만약 P=abaac이고 T=xabxabaaxa일 때, M의 8번째 열은 다음과 같다.
1 |
0 |
1 |
0 |
0 |
왜냐하면, 1과 3의 길이를 가진 P의 접미사는 T의 7번째 위치와 일치 되기 때문이다. T의 8 번째 문자는 a이고, 이것의 U 벡터는 다음과 같다.
1 |
0 |
1 |
1 |
0 |
M의 8 번재 열이 한 칸 쉬프트 되고 AND가 U(a)와 수행되면 결과는 다음과 같다.
1 |
0 |
0 |
1 |
0 |
이것은 정확히 M의 9 번째 열이다.
일반적으로 왜 Shift-And 방식이 정확한 배열 요소를 생성하는 지 알기 위해서 다음을 알 수 있다. 요소 (i, j)에 대한 i > 1인 모든 배열 요소에 대해서 P의 첫 i -1의 문자들이 문자 j - 1에서 끝나는 T의 i - 1 문자들과 일치해야 하고, 문자 P(i)는 T(j)와 일치해야 한다. 첫째 조건은, 요소(i - 1, j - 1)에 대한 배열 요소가 1일 때, 참이고, 둘째 조건은 문자 T(j)를 이용하여 만든 U 벡터의 i 번째 비트가 1일 때 참이다. j - 1 번째 열을 먼저 쉬프트하고, 알고리즘은 j - 1번째 열의 (i -1, j - 1)의 요소를 U(T(j)) 벡터의 i 번째 요소와 AND 비트 연산을 수행하게 된다. 그래서 알고리즘은 배열 M에 대한 정확한 요소를 계산하게 된다.
하지만, 책의 설명은 무엇인지 모르지만 잘 이해가 되지 않게 써져 있다. 그런 이유로 stackoverflow의 답변(http://stackoverflow.com/questions/11317973/string-similarity-how-exactly-does-bitap-work) 중 하나를 추가로 번역하여 정리해둔다. 참고적으로 T 테이블은 이전 설명에서 U 벡터에 해당한다. 다만, 논문에서는 실제의 비트 순서에 따라서 작성된 것으로 보인다.
T는 약간 헷갈리는 개념인데 우리는 보통 패턴에 있는 위치 번호를 왼쪽에서 오른쪽으로 매기기 때문이다.
0 1 2 3 4
a b a b c
반면, 비트들은 일반적으로 오른쪽에서 왼쪽으로 번호가 매겨진다. 그래서 패턴을 반대 방향으로 진행하면서 비트들을 생성하는 것은 논문의 내용을 명확하게 해준다.
bit: 4 3 2 1 0
c b a b a
T[a] = 1 1 0 1 0
c b a b a
T[b] = 1 0 1 0 1
c b a b a
T[c] = 0 1 1 1 1
c b a b a
T[d] = 1 1 1 1 1
T[x]의 n번째 비트는 x가 해당 위치에 나타나면 0의 값이고, 아니면 1의 값을 가진다.
이것은 다음과 같이 생각할 수 있다. 만약 우리가 문자열에서 현재 문자의 위치를 x라고 한다면, T[x]의 n 번째 위치는 0이고, 패턴에 대한 매칭이 n 문자들 앞에서 시작되었을 때만 매칭을 시킬 수 있게 된다.
이제 매칭 순서에 대해서 살펴보자. 상태 비트에서 n번째 비트의 0이라는 값은 우리가 패턴에 대한 매칭을 n 개의 문자 전에 시작했다는 것을 의미한다(0은 현재의 문자를 나타낸다.) 초기 값으로는 아무것도 매칭되지 않은 상태 비트를 보인다.
[start]
1 1 1 1 1
매칭하기 위해서 문자들을 진행해 나갈 때, 상태 비트는 왼쪽으로 쉬프트하고(최하위 비트, 즉, 0번째 비트에 0을 쉬프트 한다), 현재 문자에 대한 테이블 요소와 OR을 수행한다. 첫 문자는 a이다. 왼쪽으로 한 칸 쉬프트 하고, T[a]와 OR을 수행하게 되면 다음의 결과가 나타난다.
a
1 1 1 1 0
쉬프트된 0번째 비트는 여전히 0으로 변함이 없다. 왜냐하면, 현재의 문자 a는 패턴의 매치를 시작할 수 있는 문자이기 때문이다. 만약 다른 문자였다면, 0번째 비트는 1로 설정되었을 것이다.
정리하면, 현재의 상태 비트에서 0번째 비트가 0이라는 사실은 현재의 문자에서 패턴에 대한 매칭을 시작한다는 의미이다. 계속 진행해 보자.
a b
1 1 1 1 0 1
왜냐하면 0번째 비트가 왼쪽으로 쉬프트 되었고(이것을 1개의 문자 전에 패턴에 대한 매칭을 시작했다고 말하고 있다고 생각하도록 하자), T[b]는 같은 위치에 0을 가지고 있기 때문에, 1개의 문자 전에 매칭을 시작했다면 현재의 위치에 b가 있다는 것은 매칭이 이뤄지고 있다는 것을 의미한다.
a b d
1 1 1 1 1
d는 아무 곳에도 매칭될 수 없다. 그래서 모든 비트들이 1로 설정되어 버렸다. 더 진행해 보자.
a b d a
1 1 1 1 0
이전과 마찬가지로 다시 매칭이 가능한 값인 a가 나오자 상태 비트에 0이 등장했다.
a b d a b
1 1 1 0 1
마찬가지로 한 개의 비트를 왼쪽으로 이동했지만 0의 값은 유지된다.
b d a b a
1 1 0 1 0
a는 2개의 문자 전에 매칭을 시작했거나 혹은 현재 문자에서 매칭을 시작하더라도 괜찮다라고 상태 비트는 설명될 수 있다.
d a b a b
1 0 1 0 1
상태 비트에서 현재의 문자 b는 매칭이 1 또는 3개의 문자 전에 시작되었을 것이라고 말한다. 3번째 비트에서 0의 값의미는 우리는 전체 패턴의 대부분을 매칭했다는 것을 의미한다.
a b a b a
1 1 0 1 0
하지만, 다음의 문자는 a이다. 이 문자는 매칭이 4개의 문자 전에 시작되었다면 매칭되지 않는 문자이다. 하지만, 짧은 매칭은 여전히 가능하다.
b a b a b
1 0 1 0 1
여전히 매칭이 진행 중임을 알 수 있다.
a b a b c
0 1 1 1 1
마침내, c문자가 나타나고 현재의 상태 비트는 4개의 문자 전에 매칭이 시작되었다면 매칭이 성립됨을 나타낸다. 최상위 비트에 0이 있다는 것은 우리가 매칭되는 결과를 찾았다는 것을 의미한다.
댓글