BWT2 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 에.. 2022. 9. 16. 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).. 2022. 9. 15. 이전 1 다음
