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 만들기

1. 먼저 문자열을 0, 1 로 partition 합니다. 예제에서는 m,i 는 0 으로, p,s는 1로 적당히 partition 합니다.
2. 1에서의 partition을 바탕으로 0 은 left node, 1은 right node로 분할합니다.
3. leaf node가 하나의 문자로만 나타날때까지 1 과 2 을 반복합니다.
   • left node 의 경우, i->0, m->1 로 분할합니다. 이때 left child node는 0로 i를 나타내며, right child node 1로 m을 나타냅니다.
   • right node 의 경우, p->0, s->1로 분할합니다. 이때 left child node는 0로 p를 나타내며, right child node 1로 s을 나타냅니다.

• 모든 internal 노드들은 0과 1로 이루어진 bitvector 표현됩니다. + leaf 노드들은 character을 의미합니다.

wavelet tree queries(functions)

• wavelet tree 는 아래와 같은 함수들을 제공합니다. S 는 bitvector로 표현된 string 을 나타냅니다.

1. S.access(i) : i번째 offset의 문자를 return 합니다. (offset은 0 부터 시작합니다.)
2. S.rank_c(i) : i번째 offset 까지 character c가 몇번 등장하는지 return 합니다.
3. S.select_c(i) : i번째 character c가 몇번째 offset인지 return 합니다.

 

Access

• S.access(i) : i번째 offset의 문자를 return 합니다.

S.access(4) : 00110110110 에서 4번째 offset의 character는?

step1. S.access(4)를 root에 적용합니다. 00110110110.access(4) = 0.

• 4번째 offset은 0 을 의미하고, left node에 해당 문자가 존재하는 것을 의미합니다.

step2. left node 에서 해당 0의 offset 을 찾기 위해, 첫번째 노드에서 해당 0 이 몇번째 위치하는지 rank를 통해 찾아주고, left node에 적용해줍니다.

• leftnode.access(parent.rank₀(4))
• parent.rank₀(4) = 00110110110.rank₀(4) = 2
• leftnode.access(parent.rank₀(4)) = leftnode.access(2) = 100000.access(2) = 0
• 해당 0 은 left node 에서의 2번째 0 을 의미합니다. 즉 left node 의 left child node에 해당 0이 존재하는 것을 의미합니다.

step3. leaf node에 도달할때까지 step2를 실시힙니다.

• 즉 left node 의 left child node의 경우 leaf node 입니다.

step4. leaf node의 character를 return 합니다.

• 즉 left node 의 left child node는 i 를 나타내는 leaf node이기에 i를 return 합니다.

Shape of the Tree

• 앞서 wavelet tree 를 만들때 적당히 partition을 했지만, Huffman Coding을 적용해 볼수 있습니다.
  • frequency 가 높은 순서로 bitvector 를 만들어 줍니다.
  • 주어진 mississippi 의 경우 i : 4, s : 4, p : 2, m : 1 이므로 해당 순서에 따라 bitvector를 생성힙니다.
• Huffman Coding 적용한 Tree 의 경우, 매우 빠르게 character를 유추할 수 있습니다.
  • 10110110110.access(4) = 0 -> return i
• Prefix Code ?
  • prefix code 란 wavelet tree 에서 root node에서 leaf node 로 까지의 경로를 의미합니다.
  • Huffman Coding 적용한 Tree 의 경우 Prefix Code of 'i' : Code('i') = 0 을 의미합니다.
    • Code('s') = 10, Code('p') = 110, Code('m') = 111

Rank

• S.rank_c(i) : i번째 offset 까지 character c가 몇번 등장하는지 return 합니다.

S.rank_i(6) : 00110110110 에서 6번째 offset 까지 'i'가 등장하는 횟수는?

step1. 'i' 의 Prefix Code 를 확인합니다.

• C(i) = 00, C(m) = 01, C(p) = 10, C(s) = 11 에서 C(i) = 00 입니다.

step2. C(i) = 00 을 바탕으로 경로을 확인합니다.

• C(i) = 00 이므로 root node -> left node -> left node(leaf node) 입니다.
• 00 에서 첫번째 0 은 i 가 root node 에서 0 이라는 것을 뜻하며
• 00 에서 두번째 0 은 i 가 left node 에서 0 이라는 것을 의미합니다.

step3. step2의 경로를 바탕으로 S.rank_i(6) 계산해줍니다.

• 00 에서 첫번째 0 은 i 가 root node 에서 0 이라는 것을 뜻 하므로
  • S.rank_i(6) = 00110110110.rank₀(6) = 3
• 00 에서 두번째 0 은 i 가 left node 에서 0 이라는 것을 의미 하므로
  • S.rank_i(3) = 10000.rank₀(3) = 2
• 즉 S.rank_i(6) = 10000.rank₀(00110110110.rank₀(6)) = 2 이며, 이는 6번째 offset 까지 i 가 2번 등장함을 의미합니다.

Select

• S.select_c(i) : i번째 character c가 몇번째 offset인지 return 합니다.

S.rank_s(3) : 00110110110 에서 3번째 s의 offset은?

step1. 's' 에 해당하는 leaf node를 확인하고, 해당 Prefix 코드를 활용하여, select를 적용합니다.

• C(i) = 00, C(m) = 01, C(p) = 10, C(s) = 11 에서 C(s) = 11 입니다.
• 해당 leaf node 에서 s 의 코드는 C(s) = 11 의 2번째(마지막 자리)의 1 입니다.
• 111100.select₁(3) = 3

step2.위의 과정을 root node 에 도달할때까지 반복합니다.

• 111100.select₁(3) = 3
• 해당 root node 에서 s 의 코드는 C(s) = 11 의 1번째(첫번째 자리)의 1 입니다.
• 00110110110.select₁(3) = 6
• 즉, S.rank_s(3) = 00110110110.select₁(111100.select₁(3)) = 6

Info

wavelet tree를 설명했습니다만, 정작 글이 길어져 FM-index 에서 wavelet tree 사용법에 대해 기술하지 못했습니다.
다음 포스팅에서는 FM-index의 wavelet tree 사용법에 대해 알아보겠습니다.

Reference

Wavelet trees, part 1
Wavelet trees, part 2