「Burrows Wheeler 変換」と逐次構築

今日の肉

笑点における楽太郎の座布団みたいなもの。

概要

テキスト処理方法の一つとして、Burrows Wheeler 変換というものがある。丁度手元に、その辺りを論じた本があったので、練習がてらに実装してみることにした。

はじめに

自分の書架を整理していたら、奥から『高速文字列解析の世界』という本が出てきた。「そういえば、この本、知りあいにそそのかされて買ったけど、結局のところ詳しく読んでなかったなー」と思ったので、ちゃんと勉強するべく、実装してみることにした。

Burrows Wheeler 変換って何よ

実際のところ、Burrows Wheeler変換というトピックに関しては、いまさらでもある。実際に、2008年において既にnaoyaさんが言及しているくらいだし、適切に「Burrows Wheeler」で検索すれば、このブログよりも適切な解説(例えばこことか)が得られると思う。

まず、いきなりBurrows Wheeler変換を説明するよりも、接尾辞配列について理解したほうがよい。なぜなら、Burrows Wheeler変換とは、この接尾辞配列のキーをテキストとして並べたものだからだ。要は

[元テキスト] => 
[接尾辞配列] => 
[Burrows Wheeler変換テキスト]

といった形に(誤解を怖れずに言えば)なると思う。もちろん、この接尾辞配列の作成を通さずしてBurrows Wheeler変換(以下BWT)テキストに飛ぶこともできるのだが、これは後出する。

さて、接尾辞配列の定義は『高速文字列解析の世界』によれば、「文章のすべての位置から始まる部分文字列を辞書式順序で小さい順に並べ、その位置を格納したもの」ということになる。理屈で説明してもわからないと思われるので、手っ取り早くRubyで書いてみることにする。

def define_bwt t
  (0..t.size - 1).map { |x| [x, t[x..t.size]] }
    .sort_by {|xs| xs[1]}
    .map { |y| t[y[0] - 1] }
    .join
end

要は

1. 一文字ずつずらしたテキストを用意する
2. それらをソートする
3. その先頭の文字列を取得する
4. その文字列が入力したテキストと同じなら、最後の文字列とする

上のコードでは、BWTに飛ぶため、実際の接尾辞リストについては破棄されている。

まず入力される文字列の仕様を定義する。の集合をとして表現し、この中の文字をとしよう。このとき、が末尾であり、このとき最後の文字は、を除く全ての文字列よりも小さい添字とする。例えば、esehara$などの最後の文字についている$がそうだ。

esehara$
sehara$
ehara$
hara$
ara$
ra$
a$
$

が生成され(別解としては、単純に一文字ずつ回転させた文字列のコードを使うと良い)、これをソートした結果として:

$
a$
ara$
ehara$
esehara$
hara$
ra$
sehara$

が生成されるわけである。この接尾語の前の文字はそれぞれ:

a
r
h
s
$
e
a
e

となる。

このようなテキストを作る理由としては:

1. 頻出する文字が固まって出てくるので、符号化(あるいは圧縮)がしやすくなる
2. 特殊な対応表が無くても、BWTから元のテキストを復元することが可能である

という二つの理由がある。さて、ここで問題が生じる。まず、このような構築方法は、以下の点で問題があることを確認しよう:

順番が最後の文字列を出すまで決まらない

上記に出した本の解説によれば、例えば「bbb$」の場合と、「bbbc$」の例を出している。実際に出力してみるとわかる。

まず「bbb$」を出力すると:

$
b$
bb$
bbb$

となり、そして「bbbc$」を出力すると:

$
bbbc$
bbc$
bc$
c$

といったような逆転現象が起きる。この考察結果を踏まえると、次のようなことが言えることがわかる。

メモリ使用量が膨れあがる

上記の事情を考えると、例えば、「bbbc$」の場合、少なくとも5 + 4 + 3 + 2 + 1 = 15となるわけで、そこそこのメモリ量が必要になる。

小さいテキストならば、それほど困らないのだけれども、大きいテキストだった場合、もう少しメモリ量を抑えたいということになるだろう。

解決: 逐次構築

そこで、上記書によれば、後ろから構築することによって、接頭辞配列を避けた構築方法を紹介している。とはいえ、上記書によれば、接頭辞配列を使ったほうがはるかに効率が良い、と断わりを入れている。

どういう方法か。以前の方法は、前から文字列を組み立てていた。そのため、途中の文字列によっては、順番が劇的に変化することがわかった。

しかし、これが後ろから構築していった場合、ほぼ影響を与えずに構築しているとしている。

さて、実際のコードを貼ってみよう。

def bwt t
  n = t.size
  tb = []
  point = 0
  1.upto(n) do |i|
    if i == 1
      tb = ["$"]
      next
    end
    c = t[n - i]
    point = rank(c, tb, point)
    tb[tb.index("$")] = c
    tb.insert(point, "$")
  end
  return tb.join
end

def rank c, tb, point
  (tb[0..point].select {|tx| tx == c }.size) +
    (tb.select {|tx| tx < c }.size)
end

上記書そのままのアルゴリズムを忠実に書き移したので、Rubyとしてはどんくさいコードになっているのをお許し頂きたい。

ちょっと躓いだところとしては、まず最初に、末尾文字(この場合なら$)があった場所に、新しい文字をいれる。そして、前回に挿入した部分に、末尾文字を差しこむという操作が入るということである。この操作により、逐次的な構築が可能になる、というのである。

テキストを復元する(LF-mapping)

さて、このようにBWTにする方法はわかった。今度はこのテキストを復元する。上記書で書かれていたアルゴリズムは下のようになる:

def bwti(tb)
  pi = tb.index("$")
  cd = {}
  t = []
  tb.split("").sort.each do |c|
    cd[c] = 0 if cd[c].nil?
    cd[c] += 1
  end

  sum = 0
  cd.each do |c, i|
    cur = cd[c]
    cd[c] = sum
    sum = sum + cur
  end

  f = {}
  0.upto(tb.size - 1) do |i|
    c = tb[i]
    f[cd[c]] = i
    cd[c] += 1
  end

  pi = f[pi]
  0.upto(tb.size - 1) do |i|
    t[i] = tb[pi]
    pi = f[pi]
  end
  return t.join
end

課題: Induced Sortingへの理解

さて、早足でBWTについて調べたことを書いたのだが、ここで觝れていなかった接尾辞配列の作り方がある。これは一般的にInduced Sortingと呼ばれているもので、例えばCommon Lispで書かれた実装がある。また、英語のリソースでは、Pythonで一から作るドキュメントもある。また、卒業論文として提出されたものもある。

一応、インターネットに存在するリソースを当ってみたものの、自分の頭が追いついでこなかったので、この理解に関しては宿題としたい。

まとめ

実際に専門書を読んでみて思ったのは、意外と表現が適切ではないためにちょっと混乱する部分を含んでいたり、実装するまでの道程のあいだに、それがどういうことか、という理解をする必要があった。

そして、その躓いだ部分に関して、思ったより日本語における情報リソースが少なかったので、今回メモとして、このように書き残しておこうと思った。何かの参考になれば幸い。

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)

蛇足

ちなみに、「Burrows Wheeler 変換」のトピックに関しては、Haskellで実装する方法として、以下の本に紹介されているので、のちのち、こちらの方法についても勉強をしていきたい。

関数プログラミング 珠玉のアルゴリズムデザイン