fm-index2 FM-index part4. Wavelet Tree in FM-index 앞선 3개의 포스트를 통해 BWT, FM-index, 그리고 wavelet tree에 대해 살펴보았습니다. 이 포스트에서는 마지막으로 wavelet tree 가 어떻게 FM-index에 사용되는지 알아보겠습니다. FM-index 에서의 Wavelet Tree 아래와 같은 활용법이 있습니다. 첫번째로 BWT 의 결과를 Wavelet Tree 로서 저장합니다. Wavelet Tree 의 통해 FM-index 에서 필요한 LF-Mapping (Matrix) 를 사용하지 않아도 됩니다. e.g.) s = "abaaba", BWT(S) = abba$aa 를 Wavelet tree 표시 FM-index part3. Wavelet Tree 에서 설명했듯이, 적당한 형태로 abba&aa 를 partition 해 주어서.. 2022. 9. 21. 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. 이전 1 다음
