LZ法で圧縮したデータの解凍について

2010/07/09 19:38

このQ&Aのポイント

LZ法で圧縮したデータの中に連続したFFの連なりが見つかり、その性質に疑問を抱いています。また、ソフトが吐き出したLZ圧縮データの情報が不明なため、解凍に困っています。
LZ77で圧縮したデータをバイナリエディタで解析中ですが、中間辺りに多量のFFの連なりが見つかりました。LZ法のアルゴリズムの性質上、同じデータが連なることはありえないので、疑問を感じています。
LZ法で圧縮したデータを解凍するためのプログラムを作成しています。しかし、ソフトが出力したLZ圧縮データの詳細情報が不明であり、スライド窓の大きさなどが分からず、解凍に苦労しています。

MiMino2
お礼率33% (1/3)

C・C++・C#
回答数1
ありがとう数1

みんなの回答 （1）
専門家の回答

質問者が選んだベストアンサー

ベストアンサー

beefisdead
ベストアンサー率63% (92/145)

2010/07/11 19:54 回答No.1

いや…おっしゃるように、そりゃかなり無茶じゃないですか？LZ77は圧縮方式というよりはアルゴリズムでしかないわけですし、LZSSやLZMAもLZ77の一種とも言えるわけで、特定の実装を示していない。おまけに圧縮後のヘッダサイズや圧縮のデータ構造も示していないわけですから…。ただ、非常に単純なLZ77で圧縮した場合、FFが連続するようなことは考えられますよね。ウィンドウサイズ限界の何倍かまで同じ文字列が繰り返し表れるような場合であれば、X文字前よりX文字分一致、というパターンが繰り返し出てくる可能性はあります。ハフマン符号化をした場合はそういうパターンはむしろ残りにくいはずです。（文字列繰り返しがウィンドウサイズを超えているパターンが一部分にだけ固まっているということになるので、やや不自然）また、圧縮前のファイル形式が分かっていれば、先頭付近のLZ77で圧縮されない部分のデータ形式から圧縮形式の一部を推定することは可能かも知れません。余談というか、確信のない案のひとつになりますが…。もっとも単純な方式として考えられるのは、1Byteで区切って一致位置・一致長を表すケースですよね。FFが連続するというところからは、4bitか8bitで区切っていそうに思えます。 LZ77であるなら、FFという文字のためのエスケープと言うことはないので、圧縮後にこれが連続するようなケースを考えると良いのではないでしょうか。

質問者

お礼 2010/07/15 12:37

詳しく有難うございます！！確かに単純なLZ法ですと、同じデータが連続していればffの塊があっても不思議ではないですね。文字列の先頭から生のデータと思われる物を見ていったりしましたが複数を出力すると、どうも何かのヘッダのようだと思われ、正直解凍は困難を極めています。今回は恐らく見送る方になるかと思いますが、色々と試したという実績が必要でしたので beefisdeadさんの案も大変参考になりました。有難うございました。