wavelet tree2 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 part3. Wavelet Tree SEAL(Search Engines with Autoregressive LMs) 에 필요한 FM-index의 wavelet tree를 설명합니다. What is Wavelet Tree? wavelet tree 란 이진 트리의 형태로 문자열을 저장하기 위한 데이터 구조입니다. access, rank, select 3가지 형태의 함수(query)가 존재합니다. wavelet tree 만들기 먼저 문자열을 0, 1 로 partition 합니다. 예제에서는 m,i 는 0 으로, p,s는 1로 적당히 partition 합니다. 1에서의 partition을 바탕으로 0 은 left node, 1은 right node로 분할합니다. leaf node가 하나의 문자로만 나타날때까지 1 과 2 을 반복합니다. left .. 2022. 9. 19. 이전 1 다음
