データを加工して圧縮率を高めよう：コーディングに役立つ！ アルゴリズムの基本（9）（4/5 ページ）

[山下寛人，オイシックス株式会社]

MTF（Move To Front）

　ブロックソーティングと併せてデータ圧縮で使われるアルゴリズムがMTF（Move To Front）です。ブロックソーティング同様に圧縮そのものは行いませんが、より圧縮率を高めるような変換を行うものです。

　「babbbbbccc」という文字列をMTFで変換してみます。まず、文字の種類のリストを作ります。左から文字の種類を拾っていくと「bac」というリストができます。

元の文字列	babbbbbccc
文字リスト	bac
変換後の文字列

　元の文字列の1文字目は「b」です。「b」は文字リストの中の0番目です。従って、変換後の文字列の最初の文字を「0」にします。

元の文字列	babbbbbccc
文字リスト	bac
変換後の文字列	0

　元の文字列の2文字目は「a」です。「a」は文字リストの中の1番目なので、変換後の文字列の2番目の文字を「1」にします。ここで、文字リストの中で「a」を先頭に移動させます。ここがMove To Front、前へ移動しているところです。

元の文字列	babbbbbccc
文字リスト	bac → abc
変換後の文字列	01

　次の文字はbで、文字リストの1番目なので変換後は1になります。文字リストのbを先頭に移動します。

元の文字列	babbbbbccc
文字リスト	abc → bac
変換後の文字列	011

　以後、同様に繰り返します。

元の文字列	babbbbbccc
文字リスト	bac → bac
変換後の文字列	0110

　最終的に以下のようになります。

元の文字列	babbbbbccc
文字リスト	cba → cba
変換後の文字列	0110000200

　文字が連続しているところはbでもcでも0に変換されます。全体として「0」の出現頻度が高くなります。このためハフマン符号でより圧縮できるようになります。

MTFによる復元

　MTFでも変換後の文字列から元の文字列に復元することができます。この復元についてはそれほど難しくありません。ただし、最初の状態の文字リストが必要です。

　先ほどの例で手順を紹介します。変換後の文字列と文字リストがあります。

変換後の文字列	0110000200
文字リスト	bac
元の文字列

　変換後の文字列の最初の文字は「0」です。文字リストの0番目は「b」です。従って、元の文字列の最初の文字は「b」になります。文字リストの中で「b」を先頭に移動します。もともと先頭なので変化はありません。

変換後の文字列	0110000200
文字リスト	bac → bac
元の文字列	b

　2文字目は「1」で、1番目は「a」なので元の2文字目は「a」です。文字リストの「a」を先頭に移動します。

変換後の文字列	0110000200
文字リスト	bac → abc
元の文字列	ba

　3文字目は「1」で、1番目は「b」なので元の3文字目は「b」です。文字リストの「b」を先頭に移動します。

変換後の文字列	0110000200
文字リスト	abc → bac
元の文字列	bab

　以後、同様に繰り返すことで元の文字列が得られます。

変換後の文字列	0110000200
文字リスト	cba → cba
元の文字列	babbbbbccc