본 문서는 http://www.alexbowe.com/fm-indexes-and-backwards-search-32172의 내용을 편역 하였다. 또한, 위키피디아(http://en.wikipedia.org/wiki/FM-index)의 내용을 일부 번역하였다. BWT에 대한 내용은 다음글(http://juggernaut.tistory.com/entry/%EB%B2%84%EB%A1%9C%EC%9A%B0%EC%A6%88%ED%9C%A0%EB%9F%AC-%EB%B3%80%ED%99%98BWT-BurrowsWheeler-transform)을 참고하기 바란다.
FM-색인
FM 색인은 문자열에 대해서 BWT를 수행함으로써 얻어질 수 있다. BWT를 수행하게 되면, 행렬의 열은 기본적으로 정렬된 문자열의 접미사가 되고, 행렬의 첫째 열인 F는 접미사 배열의 특성을 가진다. 첫째(F)와 마지막 컬럼(L)에 대한 매핑은 LF(i)로 표현되고, L[i]과 F[j]의 문자로부터 표 C[c], 함수 Occ(c, k)를 통해서 정의된다. C[c]는 문자열에 나타나는 문자 c 보다 앞에 있는 문자들의 발생 빈도를 담고 있는 표이다. 함수 Occ(c, k)는 접미서 L[1..k]에서 특정 문자 c의 발생 빈도를 나타낸다. FM은 상수 시간에 계산될 수 있다. LF 매핑은 다음과 같이 정의된다.
예를 들어 보자. T = "abracadabra"일 때, BWT="ard$rcaaaabb"이고, 변환은 아래와 같은 모양으로 진행된다.
버로우즈-윌러 변환
F |
|
|
|
|
|
|
|
|
|
|
L |
$ |
a |
b |
r |
a |
c |
a |
d |
a |
b |
r |
a |
a |
$ |
a |
b |
r |
a |
c |
a |
d |
a |
b |
r |
a |
b |
r |
a |
$ |
a |
b |
r |
a |
c |
a |
d |
a |
b |
r |
a |
c |
a |
d |
a |
b |
r |
a |
$ |
a |
c |
a |
d |
a |
b |
r |
a |
$ |
a |
b |
r |
a |
d |
a |
b |
r |
a |
$ |
a |
b |
r |
a |
c |
b |
r |
a |
$ |
a |
b |
r |
a |
c |
a |
d |
a |
b |
r |
a |
c |
a |
d |
a |
b |
r |
a |
$ |
a |
c |
a |
d |
a |
b |
r |
a |
$ |
a |
b |
r |
a |
d |
a |
b |
r |
a |
$ |
a |
b |
r |
a |
c |
a |
r |
a |
$ |
a |
b |
r |
a |
c |
a |
d |
a |
b |
r |
a |
c |
a |
d |
a |
b |
r |
a |
$ |
a |
b |
여기에서 노랑색으로 칠해진 9번째 행을 보자. 여기에서 주의할 점은 행이나 열은 1부터 시작한다. 여기에서 분홍색인 L열을 보면 이 때의 L 값은 a임을 알 수 있다. 마찬가지로 연두색으로 칠해진 F 열에서 같은 a를 찾아 보면 이는 5번째 행에 있음을 알 수 있다. 이것이 왜 같은 a인지 헷갈릴 수가 있으니 조금 부연을 하겠다. 5번과 9번행의 같은 값들을 연필로 연결해 보면 5번째 행을 오른쪽에서 왼쪽으로 한 칸씩 밀면 9번째 행이 됨을 알 수 있다. 그러므로 9번째 행의 L의 a와 5번째 행의 F의 a는 같은 a이다. 그러므로 LF(9)라고 함수를 실행하면 5라는 값이 나와야 한다. 정의가 맞는지 조금더 확인해 보자. 여기에서 L[9]=a이다. 그리고 C[a]는 무엇인가? 이것은 a보다 앞에 있는 문자의 갯수이다. 다른 관점으로 이 값은 F열은 이미 정렬된 상태이므로 F열에서 a가 나타난 첫 행 - 1의 값이다. 즉, a는 2번째 행에서 처음 나타났으므로 2-1=1이다. 그리고 이것은 a보다 앞선 문자인 $가 1개 있다는 말과 동일하다. 정리하면, C[a]=1이다. 다만, 프로그래밍을 할 때는 모든 숫자가 0부터 시작하므로 1을 뺄 필요가 없다. 다음으로 Occ(a, 9)는 무엇인가? 이것은 L열에서 a가 몇 번 나왔는지를 나타내므로 Occ(a, 9)=4이다. 결국 정의에 따라서 LF(9)=5임을 알 수 있다.
이에 덧붙여서, 문자열 T에서 살펴보면, 모든 행 i에 대해서, 마지막 열 L[i]의 문자는 첫째 열 F[i]의 문자보다 한 칸 앞에 있는 문자이다. 예를 들어서, L[1]인 a는 T=abracadabra$에서 보면 F[1]인 $의 바로 앞의 문자 임을 알 수 있다. 그러므로 다음 정의를 통해서 L에서 T를 복원할 수 있다.
C(F열에서 c문자가 처음 나타난 행 - 1, 행렬이 1부터 시작하는 경우)
c |
$ |
a |
b |
c |
d |
r |
C[c] |
0 |
1 |
6 |
8 |
9 |
10 |
Occ(c, k) 함수(L열에서 해당 행까지의 문자 c의 갯수)
c/k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
$ |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
a |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
3 |
4 |
5 |
5 |
5 |
b |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
c |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
d |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
r |
0 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
이제 위의 정의와 C표와 Occ를 이용하여 L로부터 T를 복원해 보자. L="ard$rcaaaabb" 이다.
- L[0] = $, C($) = 0, Occ($, 0) = 1, LF(0) = 1, k = 1, T[12] = $
- L[1] = a, C(a) = 1, Occ(a, 1) = 1, LF(1) = 2, k = 2, T[11] = a
- L[2] = r, C(r) = 10, Occ(r, 2) =1 LF(2) = 11, k = 11, T[10] = r
- L[11] = b, C(b) = 6, Occ(b, 11) = 1, LF(11) = 7, k = 7, T[9] = b
- L[7] = a, C(a) = 1, Occ(a, 7) = 2, LF(7) = 3, k = 3, T[8] = a
- L[3] = d, C(d) = 9, Occ(d, 3) = 1, LF(3) = 10, k = 10 , T[7] = d
- L[10] = a, C(a) = 1, Occ(a, 10) = 5, LF(10) = 6, k = 6, T[6] = a
- L[5] = c, C(c) = 8, Occ(c, 5) = 0, LF(5) = 8, k = 8, T[5] = c
- L[8] = a, C(a) = 1, Occ(a, 8) = 3, LF(8) = 4, k = 4, T[4] = a
- L[4] = r, C(r) = 10, Occ(r, 4) = 1, LF(2) = 11, k = 11, T[3] = r
- L[11] = b, C(b) = 6, Occ(b, 11) = 1, LF(11) = 7, T[2] = b
- L[7] = a, C(a) = 1, Occ(a, 7) = 2, LF(7) = 3, k = 3, T[1] = a
가장 오른쪽 편에 있는 문자들을 조합하여 보면 역순으로 원래의 문자열이 복원된 것을 알 수 있다. 전체 단계는 k를 0부터 시작해서 원래 문자열의 길이만큼 수행한다. 구해진 LF(k) 값을 다음 단계에서 이용할 k값으로 정한다. 현재 단계의 k 값을 문자열 길이 - 단계 번호 + 1의 복원 문자열 위치에 둔다.
역방향 검색
원래 문자열 S에 있는 모든 패턴 P는 하나의 접두사 혹은 접미사 문자열이다. 그리고 접미사는 사전식 순서의 오름차순으로 정렬되어 있기 때문에, 패턴 P에 대한 검색의 모든 결과는 접미사 배열의 연속된 부분에 있게 된다. 우리의 검색 어구에서 집중적으로 관심을 가져야 하는 것은 연속적인 이진 검색이다.
역방향 검색은 일련의 쌍으로된 랭크 질의(예를 들어, 웨이블릿 트리에서 사용될 수 있는)에서 BWT를 활용하고, 이는 획기적으로 질의 성능을 향상시킨다. 역방향 검색은 p 쌍의 랭크 질의를 생성하고, 여기에서 p는 패턴 P의 길이를 나타낸다. 쌍으로된 랭크 질의들은 다음과 같이 표현된다.
여기에서 s는 질의 범위의 시작을, e는 질의 범위의 끝을 나타낸다. 초기값으로 s=1, e=N을 가지며, N은 주어진 문자열의 길이이다. 어떤 단계에서라도 e < s가 되면 패턴은 주어진 문자열 S 안에 없게 된다. 랭크 함수는 다음과 같이 정의된다.
rank(i, c) : 문자열에서 i위치 이전에 문자 c가 나타나는 횟수
이전의 내용에서 보았듯이 BWT의 원래 텍스트를 복원하려면 역순으로 값을 찾아갔었다. 그런 까닭에 패턴을 찾기 위해서도 역순의 과정으로 검색을 해야할 필요가 있다. 즉, 복원시 사용했던 k와 대응되게 i라는 변수를 사용한다고 하면, i는 찾으려는 패턴의 길이인 |P|부터 시작하여 1까지 감소하게 된다. 접미사 배열 SA[s..e]는 찾으려고 하는 검색 어구 P[i..|P|]를 모두 포함하고 있을 것임을 가정하고 있고, 이런 가정이 성립하는 한 검색 어구 P[i..|P|]는 주어진 문자열 어디에나 존재하게 된다. 이제 문자열 S=mississippi에서 검색 패턴 iss를 찾는 과정을 살펴보자.
위에서 보이는 것은 역방향 검색의 가장 첫 단계이다. 회색으로 보이는 문자들은 메모리 상에 존재하지 않는다. 그리고 FM인덱스의 F 역시 저장하지 않지만 C는 저장한다. 여기에서 C는 위의 BWT 변환에서 설명한 것처럼 F열에서 C가 처음 나타난 행 번호 혹은 해당 문자보다 앞에 나타난 문자들의 총 갯수를 나타낸다. 현재 상태는 s=1, e=12이고 c의 값은 검색 문자인 iss의 가장 뒤에 있는 문자인 s(P[3])이다.
C를 확인할 때는 가장 왼쪽에 있는 숫자를 이용하고, F에서 해당 문자가 나타나기 직전의 숫자 값을 읽으면 된다. s의 경우는 8임을 알 수 있다. 랭크 함수의 경우 i가 0인 경우는 0번 위치까지의 해당 문자 갯수를 나타내므로 0이 되고, 12인 경우 문자열 길이와 같으므로 모든 s의 갯수가 더해져서 4의 값을 가진다. 그리고 다음으로 s와 c를 갱신하게 된다.
갱신된 s와 e의 값에 따라 그려보면 위와 같이 된다. 모든 s 접두사 문자열은 접미사 배열 SA[9..12]에 있게 된다. 이제, s=9, e=11, c는 뒤에서 두 번째 문자인 s(P[2])가 된다.
이제 모든 ss 접두사 문자열은 접미사 배열 SA[11..12]에 있게 된다. 이제 s=11, e=12, 그리고 c는 최종적으로 i(P[1])이다. 최종 랭크 질의는 다음과 같다.
이제 iss 접두사 문자열은 접미사 배열 SA[4..5]에 있게 된다. 역방향 관련 라이브러리는 libdivsufsort(http://code.google.com/p/libdivsufsort/)가 있다. 또한 BWT를 위한 랭크 자료 구조를 제공하는 라이브러리에는 libcds(http://libcds.recoded.cl/)가 있다.
댓글