卒研のようなもの 圧縮ちーむ ２００８．６．２４ 鴫原、山本、齋藤.

Presentation on theme: "卒研のようなもの 圧縮ちーむ ２００８．６．２４ 鴫原、山本、齋藤."— Presentation transcript:

1 卒研のようなもの 圧縮ちーむ ２００８．６．２４ 鴫原、山本、齋藤

2 ・ブロックソート（符号化）実装 (bzip2のメインアルゴリズム) ・実行してみるテスト
今日やること ・ブロックソート（符号化）実装 (bzip2のメインアルゴリズム) ・実行してみるテスト

3 ブロックソートってなんだっけ？ → 入力例：cacao 手順１：巡回シフトさせながら以下の行列をつくる 手順２：abc順に行をソート
手順３：行列の末尾の列と、元データが何行目かを出力 → ↑3行目が元データ 出力：ccoaa , 3 長いデータを処理すると、特にデータが偏りやすくなる （圧縮はされない）

4 実装を考える 解決策 前ページの表をそのまま実装するとn^2のメモリーが必要 →1MBのデータを処理するには1TBのメモリーが必要に
入力データを２つ繋げたデータを用意する 例： cacao → cacaocacao 　インデックスとデータ数を保持しておけば ブロックが再現可能

5 実装を考える その２ Javaでの実装を考える 理由：今はまってるから ■１つのブロックを保持するクラス クラス名：Block
実装を考える　その２ Javaでの実装を考える 　理由：今はまってるから ■１つのブロックを保持するクラス クラス名：Block 親クラス：Comparable (大小比較のため) メンバ変数：インデックス、データ数、元データの参照 メンバ関数：大小比較、保持データを返す　等

6 実装を考える その３ ■ブロックデータの持ち方 LinkedListにインデックスを１ずつずらした Blockオブジェクトを一周分挿入する
実装を考える　その３ ■ブロックデータの持ち方 LinkedListにインデックスを１ずつずらした Blockオブジェクトを一周分挿入する ■ソート Collections.sort() を利用 ここでComparableが生きる

7 実装を考える その４ ■おおまかな処理の流れ データを読み込んでbyte型の配列に入れる ↓ データを２つ繋げた配列にする
実装を考える　その４ ■おおまかな処理の流れ データを読み込んでbyte型の配列に入れる ↓ データを２つ繋げた配列にする ByteオブジェクトのLinkedListをつくる LinkedListをソートする ソート結果の各オブジェクトの末尾のデータを出力 元のデータがLinkedListの何番目に現れているか出力

8 実行してみた ■入力データが小さいとあんまり面白い結果がでない ■14kBのテキストデータ (適当な英文章)
→実行時間 約14秒 , 使用メモリー 約 8.5MB ■30kBのテキストデータ (うちの鯖のログ) →実行時間 約70秒 , 使用メモリー 約 9.5MB ■300kBのデータを突っ込んでみたら１時間たっても終わりませんでした…。 (Core2Duo E6750) ■LinkedListをソートするのはよくないかも。

9 今後の予定 元に戻せるようにしてきます

10 ＥＮＤ ・・・どうした？ ／￣￣＼ ／ ⌒ ⌒＼ ＿＿＿_ |::::::（●）（●） ｜ ／ ＼
　　・・・どうした？ 　　　　　　　 ／￣￣＼　　　 　　　　　　／　⌒　　⌒＼ 　　　　　＿＿＿_ 　　　 　 　|::::::（●）（●） ｜　　　／　　 　 　＼ 　　　 　 |:::::::::::（__人__）｜　 ／　 ⌒　　⌒　 ＼ 　　　　 　 |::::::::::::::｀ ⌒´ ｜／ 　 （●）　（●） 　 ＼ 　さっきからこっち見てる奴がいるお・・・ 　　　　 　 |::::::::::::::　　　　} |　　　　 （__人__）　　　　|　 　　　　　　 ヽ:::::::::::::: 　　 }　＼　　　 ｀ ⌒´　　　_／　 　　　　　　　 ヽ::::::::::　　ノ　　　|　　　　　　　　　　 ＼ 　　　　　　　　/ヽ三＼´　　　　|　|　　　　　　　　 | 　| -―――――|:::::::::::::::: ＼-―┴┴―――――┴┴――