質問: "{: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
回答: 解読結果 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"`