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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Q&A

解決済

1回答

3633閲覧

deflate圧縮の解読について

biggieboo

総合スコア12

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

0グッド

1クリップ

投稿2018/11/30 03:55

編集2018/12/08 02:14

前提

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

生のdeflate抽出ソースコード

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

python3

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

解読結果

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

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

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

解読結果 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 07:58

argparse

総合スコア1017

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

biggieboo

2018/12/09 09:29

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問