カレンダー最新コメント最新記事(03/29)
(11/09)
(06/29)
(02/10)
(09/19) 最新トラックバックプロフィールブログ内検索最古記事アクセス解析忍者アナライズ |
ブログ日記のようなものPAGE | 2188 2187 2186 2185 2184 2183 2182 2181 2180 2179 2178 | ADMIN | WRITE 2009.11.02 Mon 19:28:02 れっつlzhエンコード実装姐になにやら質問されたので、マジメに考える。 内容は、LZ78というデータ圧縮アルゴリズムの実装方法について。 まぁ、ようはlzh形式のデータをどうやって作るかって話。 軽く調べてみたところ、LZ77とかいう方法もあるらしく、 そっちはスライド窓なんていう方法を使ってるらしいが、 LZ78はそれを改良したアルゴリズムなんだとか。 ふ〜ん。 本題。 とりあえず、辞書なるものを作るようで。 圧縮したいデータをはじめから見ていって、辞書になかったら登録。 簡単に言えばそうなんだけども・・・ 登録の仕方が変わってて、どう実装するのやら、と。 たとえば。 abcababc・・・とでも行きましょうか。 とりあえず最初の文字、aを登録。0a。 残りはbcababc。 次の文字、bはまだ辞書に登録してないから、登録。0a,0b。 残りはcababc。 更に次の文字、cも登録してないから登録。0a,0b,0c。 残りはababc。 問題はここから。 aは登録してある。登録してあるのは1番目。 じゃあ次のbを足したabだったら? これは登録してない。だから登録する。 どうやって? 『辞書に登録してある1番目の文字列+b』ということで、1b。 結果的には0a,0b,0c,1b。 残りはabc。 aは1番目に登録してある。abも4番目に登録してある。 でもabcは登録してない。だから登録。 『辞書に登録してある4番目の文字列+c』ということで、4cでOK。 0a,0b,0c,1b,4c。 圧縮完了。 abcababcという8文字は0a0b0c1b4cという10文字に・・・ って増えとるやん!!? いやいや、たまたまっすよ。 同じような文字列がだらだら続けば断然短くなるでしょうよ。 例えばaaaaaaaaaaaaaaa、とか? a,aa,aaa,aaaa,aaaaa・・・0a1a2a3a4a? 15文字が10文字に。2/3ですか。そうですか。 なんか無駄に一色だけの画像がなんで軽いのか垣間見た気がするね。 とりあえず、ようはこんなかんじ。 これを実装しようとするとどうすればいい? 我思うに。 1文字目の時点で辞書に登録されていない場合、 次の文字と合わせた2文字は辞書の中には絶対ない。 つまり。 aが登録されてないのに、abが登録されてるはずがない。 と、いうことは。 1文字目が見つけられなかった時点で、その文字は登録すればいい。 1文字目を見つけたのなら、2文字目も引っ付けて探す。 探す文字は1文字目の辞書番号がついたもの。 つまり。 aが辞書で2番目に登録されていたのなら、 2がついたものを辞書から探せばいい。2aとか2bとか2cとか。 なければ登録。あったら次を探す。 これの繰り返し。 ・・・まてよ。 これ、ひょっとして木構造にできたりするのか? む。できなくはない。 ただ、これだと辞書の番号を別で管理しなきゃならん気がする。 まあ登録するデータの属性を文字データとインデックスの2つにすりゃいいか。 ・・・いやまて。 これでエンコードはできたとしてもデコードが超不便・・・だよな。 ぬぬぬ? デコードしていくと辞書データを蓄積しつつ解凍するわけで・・・ 蓄積していく際には後で出てくる変な文字列は関係ない。 後から出てくる文字列は新しく蓄積されるべきデータなんだし。 ・・・いやいやいやちょっとまて!! そういう問題じゃないぞこれは!! そもそも木構造として考えた理由は「検索しやすく」であって、 デコード時には検索なんて必要ないじゃん! 必要なのは何番目のデータを使うかってだけ。 「2個目のデータ使ってね」的な。「2ページ目を見てね」的な。 そう。そうだ。 辞書は引いた後なんだ。引く作業はやった後なんだ。 引くのは大変だけど、引いた後はしおりを挟めばいいだけ。 次に見るときは時間をかけて探す必要はない。 数字はしおり。そういうことですね。 ということで。 姐にそれっぽいことを言ってみた。 すると。 どうやら最終的にしなきゃいけない作業は、 辞書に登録してある内容を順番に表示する、だそうだ。 つまり。 木構造のままじゃアウトですが何か(爆) う〜ん・・・ エンコードしながら別の配列にデータをブッコんでいけば?(投げやり) TrackbacksTRACKBACK URL : CommentsComment Form |