상수 공간 비교 기반 버로우즈 휠러 변환

원 논문의 제목은 A Constant-Space Comparison-Based Algorithm for Computing the Burrows–Wheeler Transform이다. 원문 내용의 2절의 일부는 다음과 같다. 다음 내용은 0-index 기반이다. 즉, 문자열에서 첫 문자는 index 0을 가진다. 가령, T='temp'에서 T[0] == 't'이고, T[3] == 'p'이다.

 

Given the input text T = T [0 ..n−1] where T [n−1] = $, moving a single character inside T can change the content of many suffixes. The idea to circumvent this difficulty without using storage for the suffix sort is to proceed by induction from right to left in T, while maintaining the BWT of the current suffix Ts, denoted by BWT(Ts). We assume 0 ≤ s ≤ n−3, since the last two suffixes of T are equal to their respective BWT. To compute BWT(Ts), suppose that BWT(Ts+1) has been already computed and stored in the last positions of T, i.e. T[s+1 .. n−1]. Consider the current symbol c = T[s]: if we look at the content of T[s .. n−1], we no longer find Ts, but the symbol c followed by the permutation BWT(Ts+1) of Ts+1. Nevertheless, we still have enough information as we will show in the proof of Theorem 1 that the position of$ inside BWT(Ts+1) is related to the rank of Ts+1 among the suffixes Ts+1, ... , Tn−1. We exploit this fact in the following steps.

 

1. Find the position p of the $in T[s+1 .. n−1]: note that p−s is the (local) rank of the suffix Ts+1 that originally was starting at position s+1. 2. Find the rank r of the suffix Ts (originally in position s) using just symbol c. To this end, scan T [s+1 .. n−1] and count how many symbols are strictly smaller than c and how many occurrences of c appear in T[s+1 .. p] (and add s as an offset to obtain r). 3. Store c into T[p] (thus replacing the$).
4. Insert the symbol $ in T[r] by shifting T[s+1 .. r] by one position left.

 

 

해석하면 다음과 같다.

입력 문자열 T = T[0..n-1]이 있고, T[n-1] = $일 때, T 안의 단일 문자열을 이동시키는 것은 많은 접미사들의 내용을 바꿀 수 있다. 접미사 정렬을 위해 공간을 사용하는 어려움을 극복하기 위한 아이디어는 현재 접미사 Ts의 BWT(BWT(Ts)로 표기함)를 유지하면서 T에서 오른쪽에서 왼쪽으로 유도하면서 진행하는 것이다. 우리는 0 ≤ s ≤ n−3를 가정하는데, 이는 T의 마지막 두 접미사가 그들의 관련 BWT와 같기 때문이다.

BWT(Ts)를 계산하기 위해서, BWT(Ts+1)이 이미 계산되었고, T의 마지막 위치에, 가령 T[s+1 .. n-1]에 저장되었다고 하자. 현재 문자 c = T[s]를 고려하자: 만약, 우리가 T[s .. n-1]의 내용을 살펴보면, 우리는 더 이상 Ts를 찾을 수 없다. 하지만, 이 때 기호 c를 발견할 수 있고 기호 c 다음에는 Ts+1의 순열 BWT(Ts+1)이 따라온다. 그럼에도 불구하고, 이론 1의 증명에서 보이듯이 우리는 충분한 정보를 가지고 있다. 이론 1의 증명은 BWT(Ts+1)의 내부에 있는 $의 위치는 Ts+1, ... , Tn-1 중에서 Ts+1의 랭크와 관련이 있다. 우리는 다음 단계들에서 이 사실을 이용한다.

 

1. T[s+1 .. n-1]에서 $의 위치를 찾는다: p-s는 원래 s+1위치에서 시작하는 접미사 Ts+1의 (지역) 랭크임을 명심하자.

2. 기호 c만을 이용해서 접미사 Ts (원래 s 위치에 있었던)의 랭크 r을 찾는다. 이것을 위해서, 얼마나 많은 문자들이 T[s+1 .. n-1] 범위에서는 엄밀하게(<) c 문자값 보다 작은지와 얼마나 많은 c가 T[s+1 .. p] 범위에서 나타났는지 센다. (그리고 r을 계산하기 위해서 s를 i의 초기값에 오프셋으로서 더한다.)

3. c를 T[p]에 저장한다. (그래서 $을 대체한다).

4. T[s+1 .. r]을 왼쪽 방향으로 한 칸 옮김으로써 T[r]에 기호 $를 넣는다.

 

 

다음은 그 아래 부분에 있는 내용을 해석한 것이다.

 

T = mississippi$이고 s = 4 이라고 할 때, 우리는 마지막 T 위치에서 부분적으로 완성된 BWT를 대문자로 표기했다. 우리가 마지막 7자에 대한 BWT를 이미 계산했다고 하면, 우리는 missiIPSPIS$를 가진다. 우리는 이제 p = 11을 가진다. 그리고 위치 p보다 작은 위치에 있는 기호 중 이미 처리된 BWT에는 현재의 문자 c(='i') 보다 작은 기호가 하나('$')만있고, c(='i')와 같은 두 기호가 있기 때문에, 우리는 r = s + 3 = 7을 가지게 된다. 이 말은 우리가 '$'를 기호 c(='I')로 교체하고, IPS를 왼쪽으로 한칸 옮겨야 한다는 뜻이며, 이는 '$'를 위치 r에 넣는 것을 의미한다. 다음의 문자열 상태는 missIPS$PISI가 되며, 이는 Ts의 BWT이다.

 

 

이제 좀 더 쉽게 설명을 하겠다. 위의 푸른 부분의 내용을 순서대로 설명하자면, 현재 T는 missiIPSPIS$이다. 여기에서 p는 '$'의 위치이며 11의 값을 가진다. 이미 처리된 BWT 부분인 IPSPIS$에서 현재의 기호 'i' 보다 작은 값을 가지는 기호는 '$' 한 개가 있고, '$'위치보다 작은 위치의 BWT 부분인 IPSPIS에서 'i'는 2개가 있다. 그러므로 r은 원래 s 값보다 3만큼 큰 값인 7을 가지게 된다. 여기에서 크다 작다의 기준은 ASCII 코드 값을 기준으로 하며, '$'는 36의 값을 가지며, 각각 i(105), m(109), p(112), 그리고 s(115)의 값을 가진다.

 

step 1은 s + 1보다 큰 위치에서 END_MARKER의 위치를 찾는다. step 2에서는 s의 위치보다 크고 전체 문자 길이보다 작은 위치[s+1 .. n]의 문자들을 c와 비교하면서 c보다 엄밀하게 작을 경우(<)에 r을 1씩 증가시킨다. s의 위치보다 크고 END_MARKER의 위치보다 작은 위치[s+1 .. p]의 문자 중에 c인 경우 r을 1씩 증가시킨다. 그런 이유로 첫번째 loop에서 <= 기호를 사용한다. END_MARKER의 위치에 현재 문자 c를 넣는다. '$'를 r위치에 넣는다.

 

다음은 관련 c 코드이다. 실험과 들여쓰기로 인한 불명확함을 제거하기 위해서 약간 수정했다. 또한 개별 단계에 맞게 주석을 수정했다. 가령 string을 매개변수로 받고, 중괄호를 명시적으로 사용했다. END_MARKER는 논문에서는 주로 '$'로 표기된다. 이는 sentinel이라고도 불리며, c나 cpp에서는 보통 '\0'이다.

 

#include <iostream>
#include <string>
#include <boost/format.hpp>
using namespace std;
const char END_MARKER = '$';
void inplaceBWT(string& T, int n) {
 int i, p, r, s;
 unsigned char c;
 int count = 0;
 cout << "step " << ++count << ": " << T << endl;
 for (s = n - 3; s >= 0; s--) {
  c = T[s];

 

  /* steps 1 and 2 */
  r = s;

  // step 1: find the position of END_MARKER and store the position in p variable

  for (i = s + 1; T[i] != END_MARKER; ++i) {

   // count the occurrence of c in T[s+1 .. p]

   if (T[i] <= c) {
    ++r;
   }
  }

  p = i;

  // step 2: count the number of characters strictly smaller than c in T[s+1 .. n]
  while (i < n) {
   if (T[i++] < c) {
    ++r;
   }
  }

  // step 4: insert '$' at T[r]
  T[p] = c;

 

  /* step 4 */
  for (i = s; i < r; ++i) {
   T[i] = T[i + 1];

  }
  T[r] = END_MARKER;
  cout << "step " << ++count << ": " << T << endl;
 }
}
int main() {
 string test = "mississipi$";
 inplaceBWT(test, test.size());
 return 0;
}

 

n은 전체 문자열 길이이다. s는 알고리즘을 진행할 때, 처리되는 문자의 위치이다. i는 END_MARKER의 위치를 찾는데 사용되는 변수이다. p는 END_MARKER의 위치를 저장하는데 사용되는 변수이다.