卒研のようなもの 圧縮ちーむ ２００８．６．２４ 鴫原、山本、齋藤
・ブロックソート（符号化）実装 (bzip2のメインアルゴリズム) ・実行してみるテスト 今日やること ・ブロックソート（符号化）実装 (bzip2のメインアルゴリズム) ・実行してみるテスト
ブロックソートってなんだっけ？ → 入力例：cacao 手順１：巡回シフトさせながら以下の行列をつくる 手順２：abc順に行をソート 手順３：行列の末尾の列と、元データが何行目かを出力 → ↑3行目が元データ 出力：ccoaa , 3 長いデータを処理すると、特にデータが偏りやすくなる （圧縮はされない）
実装を考える 解決策 前ページの表をそのまま実装するとn^2のメモリーが必要 →1MBのデータを処理するには1TBのメモリーが必要に 入力データを２つ繋げたデータを用意する 例： cacao → cacaocacao インデックスとデータ数を保持しておけば ブロックが再現可能
実装を考える その２ Javaでの実装を考える 理由：今はまってるから ■１つのブロックを保持するクラス クラス名：Block 実装を考える その２ Javaでの実装を考える 理由：今はまってるから ■１つのブロックを保持するクラス クラス名：Block 親クラス：Comparable (大小比較のため) メンバ変数：インデックス、データ数、元データの参照 メンバ関数：大小比較、保持データを返す 等
実装を考える その３ ■ブロックデータの持ち方 LinkedListにインデックスを１ずつずらした Blockオブジェクトを一周分挿入する 実装を考える その３ ■ブロックデータの持ち方 LinkedListにインデックスを１ずつずらした Blockオブジェクトを一周分挿入する ■ソート Collections.sort() を利用 ここでComparableが生きる
実装を考える その４ ■おおまかな処理の流れ データを読み込んでbyte型の配列に入れる ↓ データを２つ繋げた配列にする 実装を考える その４ ■おおまかな処理の流れ データを読み込んでbyte型の配列に入れる ↓ データを２つ繋げた配列にする ByteオブジェクトのLinkedListをつくる LinkedListをソートする ソート結果の各オブジェクトの末尾のデータを出力 元のデータがLinkedListの何番目に現れているか出力
実行してみた ■入力データが小さいとあんまり面白い結果がでない ■14kBのテキストデータ (適当な英文章) →実行時間 約14秒 , 使用メモリー 約 8.5MB ■30kBのテキストデータ (うちの鯖のログ) →実行時間 約70秒 , 使用メモリー 約 9.5MB ■300kBのデータを突っ込んでみたら１時間たっても終わりませんでした…。 (Core2Duo E6750) ■LinkedListをソートするのはよくないかも。
今後の予定 元に戻せるようにしてきます
ＥＮＤ ・・・どうした？ ／￣￣＼ ／ ⌒ ⌒＼ ＿＿＿_ |::::::（●）（●） ｜ ／ ＼ ・・・どうした？ ／￣￣＼ ／ ⌒ ⌒＼ ＿＿＿_ |::::::（●）（●） ｜ ／ ＼ |:::::::::::（__人__）｜ ／ ⌒ ⌒ ＼ |::::::::::::::｀ ⌒´ ｜／ （●） （●） ＼ さっきからこっち見てる奴がいるお・・・ |:::::::::::::: } | （__人__） | ヽ:::::::::::::: } ＼ ｀ ⌒´ _／ ヽ:::::::::: ノ | ＼ /ヽ三＼´ | | | | -―――――|:::::::::::::::: ＼-―┴┴―――――┴┴――