[C++]コンパクトなBWT

今更FM-indexの勉強をしていて必要になったので。

template <
  class RandomAccessIterator1,
  class RandomAccessIterator2,
  class OutputIterator,
  class DifferenceType,
  class LexicallyLesser = default_lexically_lesser<RandomAccessIterator1>
>
void bwt (RandomAccessIterator1 in, RandomAccessIterator2 aux, OutputIterator out, DifferenceType size)
{
  for (DifferenceType i = 0; i < size; ++i) { aux[i] = i; }

  std::sort(aux, aux + size, [&] (DifferenceType l, DifferenceType r) {
    return LexicallyLesser()(in + l, in + r); }
  );

  for (DifferenceType i = 0; i < size; ++i) { out[i] = in[(aux[i] + size - 1) % size]; }
}

in - 入力文字列の最初を指すイテレータ。
aux - 補助領域を指すイテレータ。DifferenceType型を指す。
out - BWT変換した文字列を格納するイテレータ。

イテレータは全てRandomAccessIterator。
ContiguousIterator(since c++1z?)でなくても良い。
outはOutputIteratorを満たす。

終端文字も入力に含める。
終端文字もsizeに含める。

メモリ使用量はO(size)。
計算量はsortが律速。
今回はstd::sort使ってるけど、文字列の分布の偏りを想定して変なソートかけるのが通らしい。

接尾辞配列そのものが欲しい場合はSAISみたいにもっと良い方法がある。

参考

naoyaのはてなダイアリー