Burrows-Wheeler変換は、イギリスのコンピュータ科学者であるマイク・バロウズ氏とデビッド・ウィーラー氏によって考案された文字列変換アルゴリズムで、圧縮アルゴリズムなどで使われています。GoogleがこのBurrows-Wheeler変換を解説する動画を公開しており、その中では考案者であるバロウズ氏も登場します。
Burrows-Wheeler Transform (Ep 4, Compressor Head) Google – YouTube
Burrows-Wheeler変換は、データを直接圧縮するアルゴリズムではなく、データを他の圧縮アルゴリズムがより効率的に処理できるように並べ替える、可逆的なデータ変換手法です。Linuxなどで広く利用されている圧縮ツール「bzip2」の中核技術としても知られています。
一般的な情報量の指標であるエントロピーは、データに含まれる記号の種類と出現頻度のみに着目するため、記号の「順序」を考慮しません。
しかし、圧縮アルゴリズムでは、データの順序やパターンを利用して圧縮率を高めています。Burrows-Wheeler変換は、この「順序」を圧縮に有利な形に整えることを目的としたアルゴリズムです。具体的には、入力されたデータ(文字列)を並べ替え、同じ文字が連続して出現する「クラスター」を形成します。これにより、後続の圧縮処理が非常に効率的になります。Burrows-Wheeler変換の最大の特徴は、この複雑な並べ替えが、元の文字列の行インデックスというごくわずかな追加情報だけで完全に元に戻せる可逆性にあります。
動画では「BANANA」という単語を例に説明されています。
元の文字列「BANANA」を1行目に置き、2行目以降は1文字ずつ末尾の文字を先頭に移動させる巡回シフトを、文字列の長さと同じ行数だけ繰り返してテーブルを作成します。
作成したテーブルの各行を辞書順、すなわちアルファベット順に並べ替えます。並べ替えたテーブルの最終列の文字列「NNBAAA」がBurrows-Wheeler変換による変換結果となります。
また、ソート後のテーブルで元の文字列「BANANA」が何行目にあったかというインデックスを別途保持します。この2つの情報がエンコード結果となります。なぜ最終列が選ばれるのかというと、この列が元のテーブル全体を復元できるという数学的な特性を持っているためです。
デコードは、エンコードで得られた最終列の文字列と行インデックスを使います。まず、変換後の文字列(最終列)を1列に並べます。
この列を辞書順にソートすると、エンコード時にソートしたテーブルの先頭列が復元できます。
次に、元の変換後の文字列(最終列)を、復元した先頭列の前に結合します。そして、この2列になったテーブルの各行を再度辞書順に並べます。
このプロセスを元の文字列の長さ分繰り返すと、エンコード時に作成したソート済みテーブルが完全に復元されます。
最後に、エンコード時に保持しておいた行インデックスを使い、その行にある文字列を読み取ることで、元の文字列「BANANA」が復元されるというわけ。
Burrows-Wheeler変換はデータを変換するだけであり、それ自体では圧縮を行いません。Burrows-Wheeler変換によってクラスター化されたデータは、「Move-to-Front変換」という別の手法で処理されるのが一般的です。Move-to-Front変換は、出現した文字をリストの先頭に移動させることで、連続する同じ文字を「0」や「1」のような小さな数値に変換します。この結果、非常に偏った数値の並びが生成され、これを最終的にハフマン符号化や算術符号化といったエントロピー符号化アルゴリズムで圧縮することで、高い圧縮率が実現されます。
ムービーの途中で、解説者の背後から近寄ってきた人物が、考案者であるバロウズ氏本人です。
「genius(天才)」という肩書きで紹介されたバロウズ氏が語るところによると、Burrows-Wheeler変換はウィーラー氏が着想を得たものですが、当時はコンピューターの処理速度が遅く、実用的なアルゴリズムと考えられなかったとのこと。その後、ウィーラー氏の教え子であったバロウズ氏が重要性に気づき、高速な実装を考案して論文として発表したという経緯があるそうです。
バロウズ氏の論文は一度データ圧縮の学会で却下された後、技術レポートとして公開され、雑誌記事をきっかけに広く知られるようになりました。特に、DNAの塩基配列解析の分野で断片化されたデータを効率的につなぎ合わせるために利用されるなど、予想外の分野でも大きな成果を上げているそうです。
この記事のタイトルとURLをコピーする
ソース元はコチラ
この記事は役に立ちましたか？
もし参考になりましたら、下記のボタンで教えてください。