圧縮アルゴリズムBWTの性能確認実験

日本大学 文理学部 情報システム解析学科

5401080番

松田 賢幸

Takayuki MATSUDA

目次

研究の概要

BWT圧縮の概略

BWT圧縮の特徴

実験結果

まとめ

目次

研究の概要

BWT圧縮の概略

BWT圧縮の特徴

実験結果

まとめ

研究の概要

本研究ではbzipに使われているアルゴリズム，Burrows-Wheeler Transform(以下 BWT)圧縮

の紹介と，その性能確認実験を行う

目次

研究の概要

BWT圧縮の概略

BWT圧縮の特徴

実験結果

まとめ

BWT圧縮とは

Losslessな圧縮アルゴリズムのひとつである

bzipなどのツールで使われている

losslessとは可逆変換が可能ということ

花

花

つまり……

入力文字列

ブロックソート

MTFアルゴリズム

entropy符号化

（今回はHuffmanアルゴリズム）

出力

BWT圧縮

BWT圧縮の流れ

ブロックソート符号法

入力文字列： mississippi

1.入力文字列の末尾に特異な記号を加える
mississippi●

2.1.の文字列を１文字づつ巡回シフトした文 字列を縦に並べる

mississippi●
ississippi●m
ssissippi●mi
sissippi●mis
issippi●miss
ssippi●missi
sippi●missis
ippi●mississ
ppi●mississi
pi●mississip
i●mississipp
●mississippi

ブロックソート符号法

入力文字列： mississippi

3. 2.で作られた文字列を辞書順に並べ替える

mississippi●
ississippi●m
ssissippi●mi
sissippi●mis
issippi●miss
ssippi●missi
sippi●missis
ippi●mississ
ppi●mississi
pi●mississip
i●mississipp
●mississippi

●mississippi

i●mississipp

ippi●mississ

issippi●miss

ississippi●m

mississippi●

pi●mississip

ppi●mississi

sippi●missis

sissippi●mis

ssippi●missi
ssissippi●mi

4. 3.のそれぞれの文字列の末尾を出力する

出力文字列： ipssm●pissii

ブロックソート復号法

入力文字列： ipssm●pissii

1. 入力文字列を二次配列の末尾として縦に並べる

i

p

s

s

m

●

p

i

s

s

i

i

2. 入力文字列を辞書順にソートしたものを二次配列
の先頭として縦に並べる

● i

i p

i s

i s

i m

m ●

p p

p i

s s

s s

s i

s i

●

i

i

i

i

m

p

p

s

s

s

s

ブロックソート復号法

入力文字列： ipssm●pissii

3. 先頭の文字列と末尾の文字列を見比べながら復号
していく

● i

i p

i s

i s

i m

m ●

p p

p i

s s

s s

s i

s i

●

i

i

i

i

m

p

p

s

s

s

s

①

i

s

s

i

s

s

i

p

p

i

②

③

④

⑤

⑥

⑦

⑧

⑨

⑩

目次

研究の概要

BWT圧縮の概略

BWT圧縮の特徴

実験結果

まとめ

BWT圧縮の特徴

高い圧縮率

多大な実行時間

ブロックソートの特徴が大きく反映される

"Any elections which include half of the eligible voters should be considered a successful process," he said.

Al-Yawar said he expects the number of foreign troops in Iraq will decrease by the year's end.

In a separate news conference, Iraq's interim Defense Minister Hazem Sha'alan warned against an immediate pullout of U.S. forces.

...mrn,emfnddtdeselyese.fed"nshseetrflereasafsynensqe,arqeslsddSU

" . - h ssg'h lrrwepweriYH mi unrocin eeeeeliinu iessbhhdththlhcyrdlprnmDr zr fstbdfttcccn ooloen saiicS t t twsdghaaslewr Ma tnluAaubeaeiulcieumiiIagaeier oioeoii Ar cicroffvhlex o aaeeaaIIaoceoeeaptew'p'rtnse na s neeni suaasno c cslfopno a eenb a

BWT圧縮の特徴

高い圧縮率

多大な実行時間

ブロックソートの特徴が大きく反映される

mississippi●
ississippi●m
ssissippi●mi
sissippi●mis
issippi●miss
ssippi●missi
sippi●missis
ippi●mississ
ppi●mississi
pi●mississip
i●mississipp
●mississippi

●mississippi

i●mississipp

ippi●mississ

issippi●miss

ississippi●m

mississippi●

pi●mississip

ppi●mississi

sippi●missis

sissippi●mis

ssippi●missi
ssissippi●mi

ソートに時間がかかる

目次

研究の概要

BWT圧縮の概略

BWT圧縮の特徴

実験結果

まとめ

実験方法

ブロックソート + MTF + Huffman (BWT)

MTF + Huffman

Huffman

以下の３つのアルゴリズムでファイルを圧縮し，それぞれの圧縮率，圧縮時間，解凍時間を比較する

実験結果

ブロックソート + MTF + Huffman (BWT)

MTF + Huffman

Huffman

圧縮率単位：％ 時間単位：秒

圧縮率 =
(圧縮後のファイルサイズ /元のファイルサイズ ) *100

目次

研究の概要

BWT圧縮の概略

BWT圧縮の特徴

実験結果

まとめ

まとめ

今回の実験でBWT圧縮が理論上だけではなく

実際に適応される場合においても，その特

性を維持していることが確認できた

現在もBWT圧縮の特性を活かした応用利論が

様々な人々によって研究されているが，そ

れらが決して無駄でないことの裏付けにな

るだろう

完

2005-02-05T02:27:47