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를를통해텍스트의크기개생성알파벳순으로정렬이때′를cyclicshift를통해n(텍스트의크기)개생성2.알파벳순으로정렬(이때 가장 낮은 순위) 3. 정렬를 하고 나서 마지막 column을 L(ast), 첫번째 column을 F(irst)라고 할때, L column 이 BWT(string).. 2022. 9. 15. 이전 1 다음
