質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.58%

deflate圧縮の解読について

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,284

biggieboo

score 12

前提

勉強のためにdeflate圧縮されたデータを解読しようとしております。
まずは理解のために目で解読しようと試みているところです。
実際に解読した内容が合っているのか確認したいのと、他いくつかの質問がございます。
もし、間違っている箇所がございましたらご指摘いただきたくお願いします。

生のdeflate抽出ソースコード

下記のページを参考にして以下のように生のdeflateデータを抽出しました。

import zlib
a = zlib.compress(b"aaaaaa")[2:-4]
for c in a:
    c = "{:08}".format(int(bin(c)[2:]))
    print("{}".format(c[::-1]), end="")
print("")

解読結果

まず、上記の結果が以下になりました。

1101001000110010001000001000000000000000


解読してみた結果は以下です。

"aaaaaa"
110 10010001 10010001 0000010 00000 0000000 00

BFINAL:   1                         # 最終ブロック
BTYPE:    01(10)                    # 固定ハフマン
data:     10010001-00110000(0x61=a) # 8bit読み込み, base=00110000
data:     10010001-00110000(0x61=a) # 8bit読み込み, base=00110000
length:   0000010(0x103=259=5)      # 7bit読み込み
distance: 00000(0x0=1)              # 5bit読み込み
data:     0000000(0x0=end of block) # 7bit読み込み
data:     00                        # 余り

解読過程

解読した過程が以下です。

110 10010001 10010001 0000010 00000 0000000 00

ブロック情報の3ビットが110で
1:      最終ブロック
01(10): 固定ハフマン

続く8bit(10010001)を読み込みます。
参照ページの固定ハフマンの符号表より00110000を0としているので、実際の値を10010001-00110000から0x61を算出し、"a"だと分かりました。
その次の8bitも同様に"a"でした。
続く7bitを一致した長さとし、参照ページの一致した長さの対応表から実際の長さは5だと分かりました。
続く5bitを距離とし、参照ページの距離の表から実際の距離は1だと分かりました。
続く7bitはブロックの終端でした。
その次の2bitは不明です。
追記:
単純に最後8bitの余りでした。失礼しました。

質問

  1. 解読結果の認識は合っておりますでしょうか。
  2. 一致した長さや距離は表を参照して実際の値を求めるのが正解なのでしょうか。それとも何か計算で求めるのでしょうか。
  3. 距離はbit単位でしょうか。また、どの位置からみた距離なのでしょうか。
  4. 最後の2bitはどんな意味があるのでしょうか。(下記の"aaaaaabbbaaaaaa"で試した場合、後ろの不明なbitが00000になりました。)
    追記:
    単純に最後8bitの余りでした。失礼しました。

追加の解読結果

"aaaaaabbbaaaaaa"
110 10010001 10010001 0000010 00000 10010010 10010010 10010010 0000011 00101 1 10010001 0000000 00000
BFINAL:   1                         # 最終ブロック
BTYPE:    01(10)                    # 固定ハフマン

data:     10010001-00110000(0x61=a) # 8bit読み込み, base=00110000
data:     10010001-00110000(0x61=a) # 8bit読み込み, base=00110000
length:   0000010(0x103=259=5)      # 7bit読み込み
distance: 00000(0x0=1)              # 5bit読み込み
data:     10010010-00110000(0x62=b) # 8bit読み込み, base=00110000
data:     10010010-00110000(0x62=b) # 8bit読み込み, base=00110000
data:     10010010-00110000(0x62=b) # 8bit読み込み, base=00110000
length:   0000011(0x104=260=6)      # 7bit読み込み
distance: 00101+1(0x110=6)          # 5bit読み込み
data:     10010001-00110000(0x61=a) # 8bit読み込み, base=00110000
data:     0000000(0x0=end of block) # 7bit読み込み
data:     00000                     # 余り

上記結果の追加質問

  1. "aaaaaabbb"の解読後、次がdataの"a"ではなく一致した長さから始まっているのはどうしてでしょうか。今回の場合ではブロックの終端前にdataの"a"がきています。

参照ページ

https://www.slideshare.net/7shi/deflate
http://darkcrowcorvus.hatenablog.jp/entry/2016/09/23/195644
http://d.hatena.ne.jp/n7shi/20110719/1311093479
https://www.futomi.com/lecture/japanese/rfc1951.html

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+2

解読結果 1 について

1) 解読結果の認識が合っているか?

続く7bitを一致した長さとし、参照ページの一致した長さの対応表から実際の長さは5だと分かりました。

ここが誤っていますね。符号 0b0000010 は固定ハフマン符号の表を参照すると 256 を起点とする値なので、アルファベット 256 + 2 == 258 を意味します。さらにこのアルファベットを長さの表から探すと、 LZSS の 繰り返し長さは 4 である ことが分かります。 5 ではありません。

以上の解釈に基づくと、次の 3 つの要素により元の 6 バイト長ある "aaaaaa" が圧縮されていることが分かります。

  1. リテラルバイト 0x61 による "a"
  2. リテラルバイト 0x61 による "a"
  3. 戻り距離 1, 長さ 4 より 直前の 1 バイトの 4 回繰り返し となり "aaaa"

2) 長さ / 距離のアルファベットからの変換方法は?

一致した長さや距離は表を参照して実際の値を求めるのが正解なのでしょうか。それとも何か計算で求めるのでしょうか。 

そうですね、基本的には表を参照する形になると思います。

実際、 zlib でも このように 、 表に基づく定数値の集合から参照テーブルを生成 しています。毎回計算を行うとデータ長が長いほどに無駄が生じるため、こうした単純な実装が良い、といった都合もあるかとは思われますが。

3) 距離の単位と起点は?

1 で述べた通り、 現在の処理位置を起点に、展開済みのリテラルバイト単位 かと思います。つまり、距離 1 は直前に展開されたリテラルバイトを、距離 2 はさらにその直前に展開されたリテラルバイトを示すという事です。

解読結果 2 について

1) "aaaaaabbb" の後が "a" リテラルではなく長さ・戻り距離のペアである理由は?

単純に、 zlib がそのように圧縮したというだけ の事です。解読結果 1 についての回答で述べた通り、 LZSS でコピーしてくるのは 展開済みのリテラル列を後ろより数えた任意の位置 (但し最大 32,768) から なので、コピーしたいリテラル列がコピー位置の直前に現れる必要はありません。

解読結果 2 でも、解読結果 1 と同様に 長さアルファベットの変換が 1 大きい という誤解をなさっているようなので、そこが原因で混乱が生じているものと思われます。解読結果 1 の回答 1 と同じようにして要素分解すると、解読結果 2 は次のような構成になっています。

  1. リテラルバイト 0x61 による "a"
  2. リテラルバイト 0x61 による "a"
  3. 戻り距離 1, 長さ 4 より 直前の 1 バイトの 4 回繰り返し となり "aaaa"
  4. リテラルバイト 0x62 による "b"
  5. リテラルバイト 0x62 による "b"
  6. リテラルバイト 0x62 による "b"
  7. 戻り距離 8, 長さ 5 より 8 バイト前 (出力全体の 2 バイト目) からの 5 バイトコピー となり "aaaaa"
  8. リテラルバイト 0x61 による "a"

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/12/09 18:29

    argparse様
    大変解りやすい回答と正解の解読過程まで添えていただきありがとうございました。
    本当に助かりました。これでやっと前へ進めます。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.58%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る