FM-index part4. Wavelet Tree in FM-index

앞선 3개의 포스트를 통해 BWT, FM-index, 그리고 wavelet tree에 대해 살펴보았습니다.
이 포스트에서는 마지막으로 wavelet tree 가 어떻게 FM-index에 사용되는지 알아보겠습니다.

FM-index 에서의 Wavelet Tree 아래와 같은 활용법이 있습니다.

• 첫번째로 BWT 의 결과를 Wavelet Tree 로서 저장합니다.
• Wavelet Tree 의 통해 FM-index 에서 필요한 LF-Mapping (Matrix) 를 사용하지 않아도 됩니다.

e.g.) s = "abaaba", BWT(S) = abba$aa 를 Wavelet tree 표시

• FM-index part3. Wavelet Tree 에서 설명했듯이, 적당한 형태로 abba&aa 를 partition 해 주어서 나타내 줍니다.

e.g.) Wavelet tree 활용한 원복

• F(irst Column)의 첫번째 원소(F[0])은 '$' 입니다. 따라서 L[0]은 원래 문자열의 마지막 원소임을 나타냅니다.
• L[0] = 'a' 가 마지막 문자임을 알 수 있습니다.
• 이때 BWT 의 특성(F 의 i번째 문자는 L의 i 번째 문자와 같다)을 이용하여 해당 a에 대응하는 a를 F 에서 찾습니다.
• 이때 wavelet tree 의 함수(rank) 를 사용할 수 있습니다.
• $WT(L).ran{k}_a(0)=0$ 즉 L 에서 offset 0까지, a 가 몇개 있는지를 계산합니다. 당연하게도 해당 offset은 0 이므로 a는 0번 등장합니다.
• 다음으로 Skip를 계산해줍니다.
• Skip 이란 a 보다 순서가 낮은 문자가 텍스트에서 총 몇번 출현하는지를 나타냅니다. a 보다 낮은 문자는 $ 하나이고, L에서 1개만 존재함으로 Skip = 1 입니다.
• $NextRow=WT(L).ran{k}_a(0)+Skip=1$ 이므로 F[1] 이 L[0] 과 일치하는 문자입니다.
• 그러므로 다음 문자는 L[1] 이며 이는 원래 문자열의 마지막에서 바로 앞의 원소를 나타냅니다.
• 위의 과정을 문자 $ 가 나올때까지 (n번 반복) 반복합니다.

e.g.) Wavelet tree 활용한 쿼리 매칭

• FM-index part2. FM-index 에서 'aba'를 쿼리하는 과정과 같습니다.
• 다만 이전 포스트 에서는 LF-mapping matrix 를 사용하여, Next Range 를 계산하였지만
• 바로전 예제와 유사하게 rank 함수를 사용하여 range 를 도출합니다.

Reference

FM Index, part 1: efficient reversal
FM Index, part 2: efficient matching