Burrow Wheeler Transformation1 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 다음
