FM-index part1. BWT (Burrows Wheeler Transformation)

SEAL(Search Engines with Autoregressive LMs) 에 필요한 BWT

What is BWT?

Michael Burrows, David Wheeler in 1994 while Burrows 가 1994년에 고안한 압축 기법이다. 

하지만 단순히 압축기법에 그치지 않고, 긴 seqeunce 에 대해, sub-string 빠르게 query 할수 있는 FM-index 기법에 중요한 개념이다.

 

생성 방법)

    1. 'BANANA$' 를 cyclic shift 를 통해 n(텍스트의 크기)개 생성

    2. 알파벳 순으로 정렬 (이때 $ 가장 낮은 순위)

    3. 정렬를 하고 나서 마지막 column을 L(ast), 첫번째 column을 F(irst)라고 할때, L column 이 BWT(string)의 결과

 

특징)

a.  압축 가능 

    - BWT는 같은 연속된 단어를 모아주는 경향이 있다. (하지만 모든 경우에 대해 해당하지는 않는다)

    - bzip 가 이 방법에 기반한고 있다.

b. 복원 가능

    - 위와 같이 BWT를 append&sorting 을 n번 시행함으로써 시퀀스를 다시 복원할 수 있다.

    - LF mapping 을 통해 더욱 빨리 복원이 가능하다.

c. ith occurence of character c in L is equal to ith occurence of charace c in F.

   - BWT의 핵심 요소이다. 이후 LF mapping, LF mapping Matrix 에서  활용된다

   - 예를 들어, L column 에서 2번째 'N' 은 3rd Row 에 있다. 이때 F column 에서 2번째 'N' 은 7th Row 에 있다.

     해당 'N' 은 BANANA 에서 3번째 을 나타내므로 같다. 

d. LF(r) 함수 : L -> F 을 mapping 하는 함수이다. 

- L column 에서 2번째 'N' 은 3rd Row 에 있다. 이때 F column 에서 2번째 'N' 은 7th Row 에 있다 그러므로 LF(3) = 7 이다. 

- 3번째 -> 7번째 row 의 관계는 3번째 row 를 오른쪽으로 1 번 shift 한 것이다. 

- input : row number, output : row number 이고  mapping 방법으로 alphabet 의 rank(ith occurence) 를 사용하는 것이다. 

- 계산방법

     - F 는 alphabet 순서로 정렬된 값 계산 방법은 쉽다. 

     - LF(7)으로 예를 보면, 7th row L 값(7번째 L 값)은 3번째 'A' 이다. 이때 F 는 정렬되어 있으므로

            3번째 'A' 보다 앞선 값들(3번째 'A' 포함) 은 1) $가 1개 있고, 2) 1,2,3번째 'A' 3개가 있다. 그러므로 LF(7) = 1 + 3 = 4 이다. 

 

e. LF(r) 을 활용하면 효율적 복원가능하다

    - 시작값 : $

    - \$ 으로 시작하는 row 의 마지막 character 는 $BANANA 이다.

    - LF(1) = 1($) + 1('A') = 2nd row

    - 2nd row 의 마지막 character 는 A$BANAN 이다.  

    - LF(2) = 1($) + 3('A','A','A') + 1('B) + 1('N') = 6th row

    - 6th row 의 마지막 character 는 NA$NABA 이다.  

    - LF(6) = 1($) + 2('A','A')  = 3rd row

    - 3rd row 의 마지막 character 는 ANA$BAN 이다. 

위 과정을 거치면 $ANANAB 가 나오며, reverse 시 BANANA$ 로 복원 된다. 

 

다음 번에는 FM-index를 설명할 예정입니다.