FM-index part2. FM-index

SEAL(Search Engines with Autoregressive LMs) 에 필요한 FM-index

What is FM-index?

• FM index는 Burrows-Wheeler Transformation 을 기반으로 하는 압축된 전체 텍스트 하위 문자열 인덱스입니다.
• 쉽게 풀어쓰자면, 주어진 시퀀스에서 sub-string를 빠르게 search 해주는 방법입니다.

중요 index = First & Last Column of BWT

• 사실 First Column은 Last Colmn 을 정렬한 값과 동일합니다. (BWT의 정의에 의해)
• 하지만 First Column 의 경우 연속된 문자들의 값이기 때문에 integer 로서 표현하여, 저장공간을 줄일 수 있는 관계로 따로 생성해줍니다.

BANANA 에서 NA(찾기)

• 위의 예제에서 볼수 있듯이 BWT matrix 에서 NA suffix 로 시작하는 row 를 찾아주면 됩니다.

Basic Idea

• 주어진 쿼리를 뒤부터 찾아줍니다. ('abc') 경우 c -> b -> a 순으로 찾아줍니다.
• c 로 시작하는 row(들)에서 'b'로 끝나는 row range를 찾아줍니다.
• LF 를 통해 해당 'b' 로 시작하는 row(들)에서 a로 끝나는 row range를 찾아줍니다.
• 예제) "abaaba"에서 query("aba") 를 참고해 주세요

Using LF-MAPPING MATRIX

• Rank(ith occurence) 를 계산하려면 오래 걸립니다. LF-MAPPING MATRIX 를 사용하시면 O(1)에 검색하실 수 있습니다.

Checkpoint

• LF Matrix의 경우 크기게 sequence에 비래합니다.
• checkpoint 와 L 을 사용하여 저장 공간을 줄일 수 있습니다.

Suffix Array

• Suffix Array을 통하여, 해당 sub-string이 어디에 위치한지 알 수 있습니다.

Suffix Arrays Sampling

• Suffix Array 경우도 크기를 줄일 수 있습니다.
• Suffix Arrays Sampling, F, L 을 통해 값들을 유추가능합니다.

Extra Info

• SEAL FM-index 는 LF-mapping matrix 를 사용하지 않고 Wavelet Tree 를 사용합니다.
• 다음시간에는 Wavelet Tree에 대해 알아보고, FM-index 에서 사용법을 알아보겠습니다.

Reference

Burrows-Wheeler_Transform(Standford)
Burrows-Wheeler Transform(CMU)
FM Index
FM Index, part 1: efficient reversal
FM Index, part 2: efficient matching