bzip2を読む MTF1

こんにちは、junkawaです。

本記事では、Move To Front (MTF) 変換について紹介します。

目次

MTF変換について
BWT変換の特性
BWT変換とMTF変換の相性
ゼロランレングス符号化について
ゼロランレングス符号化とMTF変換の相性

これまでの記事

https://note.mu/junkawashima/m/m3adbdc56f010

前回までのおさらい

前回までに、ブロックソート (BWT) 変換について紹介しました。

bzip2 の圧縮では、BWT 変換の後に、MTF 変換+ランレングス符号化(RLE)を行います。

「bzip2を読む MTF」の連載では、図中の「MTF変換+RLE」の部分を紹介します。

MTF変換について

MTF変換では、シンボルの値を、同じシンボルが前回出現してからの間隔に変換します。

参考： https://ja.wikipedia.org/wiki/Move_To_Front

説明を簡単にするために、シンボルは0〜9とします。実際のシンボルは0〜255です。

入力データと、シンボル数に対応するリストを用意します。
リストは、MTF変換するための補助に使用します。

入力
8,1,4,2,3,9,2,1,1,1

リスト
[ 0,1,2,3,4,5,6,7,8,9 ]

図は入力 8 をMTF変換した例です。

まず、入力 8 をリストから探します。リスト中で見つかった場所の、先頭からの位置が出力となります。

図の例では先頭からの位置が8となっています。

次に、リストを更新します。入力である8を、リストの先頭へ移動します。
次回のMTF変換では、この更新したリストを使用します。

このように、リストの「先頭へ移動」(Move To Front)することから、MTF変換と呼ばれます。

図は2番目の入力 1 をMTF変換した例です。

まず、入力 1 をリストから探します。リスト中で見つかった場所の、先頭からの位置が出力となります。図の例では先頭からの位置が2となっています。

次に、リストを更新します。入力である1を、リストの先頭へ移動します。

図は10番目の入力 1 をMTF変換した例です。
リストの先頭に1がるので、先頭からの位置が0として、出力します。
前回の入力と今回の入力が同じ場合、出力は0となります。また、リストも更新されません。

このように、MTF変換ではシンボルが出現した順番にリストが更新されます。

MTF変換の特性については後述します。

BWT変換の特性について

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 岡野原 大輔 著
より引用

上記の図では、英文をブロックソートした結果、同じ文字が連続して出現しやすい形になっているのが分かります。

このように、ブロックソートでは入力データを並び替え、出現順序に偏りが出るように変換します。

参考： http://d.hatena.ne.jp/naoya/20090612/1244761902

MTF変換とBWT変換の相性

MTF変換では、シンボルの値を、同じシンボルが前回出現した位置に変換します。

例えば入力の先頭が、1,1,1,100,100,1 だった時、MTF変換後は、1,0,0,100,0,2 となります。

また、入力の先頭が、200,200,200,250,250,200 だった時、MTF変換後は、200,0,0,250,0,2 となります。

これから分かることは、シンボルが1のように小さい値であっても、200のように大きい値であっても、出現間隔が短い場合は、同様に小さな値に変換される、ということです。

BWT変換によって同じシンボルが連続するようになると、シンボルの出現間隔が小さくなります。BWT変換の後にMTF変換を行うと、小さな値の出現頻度が増えシンボルの出現頻度に偏りが出ます。

シンボルの出現頻度の偏りが大きい場合、ハフマン符号化による圧縮率が高くなり、大変うれしいです。

ゼロランレングス符号化の特性

bzip2では、MTF変換時にランレングス符号化を併用します。

ランレングス符号化とは、連続するシンボルを「シンボル+連続した回数」に変換する符号化です。

参考： https://ja.wikipedia.org/wiki/%E9%80%A3%E9%95%B7%E5%9C%A7%E7%B8%AE

bzip2では、ランレングス符号化の一種であるゼロランレングス符号化を使用しています。

参考： http://www.geocities.jp/m_hiroi/light/pyalgo29.html

ランレングス符号化では一般に、任意のシンボルを対象として、連続するシンボルを「シンボル+連続した回数」に変換します。

一方、ゼロランレングス符号化では、シンボル0 だけを対象として、連続するシンボルを2進値へ変換します。

具体的な変換方法については、別の記事で紹介します。

ゼロランレングス符号化とMTF変換の相性

BWT変換では同じシンボルが連続するので、MTF変換と組み合わせると、連続するシンボル0の頻度が増えます。

この場合、通常のランレングス符号化より、ゼロランレングスの方が適しているようです。

これについては、具体的な根拠を見つけることができませんでした。

まとめ

本記事では、MTF変換について紹介しました。

bzip2では、BWT変換、MTF変換、ランレングス符号化(ゼロランレングス)、ハフマン符号化を組み合わせることで、高い圧縮率を実現しています。

次回からは、MTF変換とランレングス符号化のソースコードを紹介します。