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

» 2009年04月02日 00時00分 公開
[山下寛人オイシックス株式会社]

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

Copyright © ITmedia, Inc. All Rights Reserved.

スポンサーからのお知らせPR

注目のテーマ

AI for エンジニアリング
「サプライチェーン攻撃」対策
1P情シスのための脆弱性管理/対策の現実解
OSSのサプライチェーン管理、取るべきアクションとは
Microsoft & Windows最前線2024
システム開発ノウハウ 【発注ナビ】PR
あなたにおすすめの記事PR

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。