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

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

現在LZ法(LZ77)で圧縮したデータをバイナリエディタで見ております。
そのデータを解凍しなければならないため、とりあえずLZ法の圧縮/解凍プログラムを組みました。

とあるソフトが出力したデータなのですが、そこのドキュメントにはLZ77で圧縮しているという記述があります。

しかしバイナリエディタで中身を見ると、中間辺りにFF FF FF FFというFFの連なりが多量に見つかりました(20~30Byte)
LZ法のアルゴリズムの性質上、同じデータが連なるというのはありえないと思うのですが、認識違いでしょうか？
私はLZ77+huffmanを使っているのでは無いかと思っています。(しかしドキュメントにはLZ77の記述しかありません)


更にLZ法は圧縮情報の持ち方に規定が無い(RFC規定に準じた圧縮アルゴリズムを除く(gzip等))為
そのソフトが吐き出したLZ圧縮が掛かっていると思われるデータについての情報が無く
スライド窓の大きさのビット数などが分からないため、解凍に手を焼いています。

これはLZ法で圧縮したデータだよと言われて、只そのデータのみを渡されて
それを解凍するというのは可能なのでしょうか？

No.1 ベストアンサー 回答者： beefisdead 回答日時： 2010/07/11 19:54

いや…おっしゃるように、そりゃかなり無茶じゃないですか？LZ77は圧縮方式というよりはアルゴリズムでしかないわけですし、LZSSやLZMAもLZ77の一種とも言えるわけで、特定の実装を示していない。

おまけに圧縮後のヘッダサイズや圧縮のデータ構造も示していないわけですから…。

ただ、非常に単純なLZ77で圧縮した場合、FFが連続するようなことは考えられますよね。
ウィンドウサイズ限界の何倍かまで同じ文字列が繰り返し表れるような場合であれば、X文字前よりX文字分一致、というパターンが繰り返し出てくる可能性はあります。
ハフマン符号化をした場合はそういうパターンはむしろ残りにくいはずです。（文字列繰り返しがウィンドウサイズを超えているパターンが一部分にだけ固まっているということになるので、やや不自然）

また、圧縮前のファイル形式が分かっていれば、先頭付近のLZ77で圧縮されない部分のデータ形式から圧縮形式の一部を推定することは可能かも知れません。


余談というか、確信のない案のひとつになりますが…。
もっとも単純な方式として考えられるのは、1Byteで区切って一致位置・一致長を表すケースですよね。FFが連続するというところからは、4bitか8bitで区切っていそうに思えます。
LZ77であるなら、FFという文字のためのエスケープと言うことはないので、圧縮後にこれが連続するようなケースを考えると良いのではないでしょうか。

この回答へのお礼

詳しく有難うございます！！

確かに単純なLZ法ですと、同じデータが連続していればffの塊があっても不思議ではないですね。
文字列の先頭から生のデータと思われる物を見ていったりしましたが
複数を出力すると、どうも何かのヘッダのようだと思われ、正直解凍は困難を極めています。

今回は恐らく見送る方になるかと思いますが、色々と試したという実績が必要でしたので
beefisdeadさんの案も大変参考になりました。
有難うございました。

お礼日時：2010/07/15 12:37