LZSSとは、直近Xバイトのデータを辞書とし、その辞書中の位置と長さの形で表現する事で圧縮を行うアルゴリズム。
理解しやすく実装が簡単ながらそれなりに効果が高いアルゴリズムだと有名で、様々な方面で取り入れられているのを見る事が出来る。
個人的な感想として、LZSSの弱点はビット演算が必須な所だと思う。
そういう意味では、表のブログで解析した某アプリで使われていたバイト単位で処理できるLZSS実装は非常に優れていたと思う。
ただ、あれは辞書位置と長さの合計が8の倍数ビットで無ければいけない制約があり、辞書サイズが制限される問題があったように見えた。
そこで、位置と長さをバイト単位に制限せずに、他は出来る限りバイト単位で入出力できるLZSS実装を考えてみる。
まず最初に思いつくのが、実データおよびフラグと、位置長さデータの分離案。
例えば、最初に位置長さデータをまとめて持っておき、実データの先頭アドレスも持っておく
一致不一致フラグは8個分まとめて1byteとして実データ上に配置する。
そして実データ先頭アドレスから不一致フラグ1bitごとに1byteずつ展開していき、一致フラグがあったら位置長さデータの先頭から順に参照していく。
この方法の利点は、位置長さデータのbit数は制限されず、しかし実データは必ずバイト単位で扱えるので余分な演算が発生しない事。
欠点は、位置長さデータが完全に別の位置にあるので、まとめてメモリー上に読んでおけるサイズを超えていた場合にランダムアクセスが発生する事と
圧縮結果を出力しつつ圧縮といった手法が非常にとり辛いこと(位置長さデータが全て判明しないと、実格納位置が判明しない。 逆に位置長さデータを後ろ側においても同じ)
欠点では無いがある意味でのデメリットとして、実データが他の圧縮方式に比べてかなり生に近い形で配置されるので、解析行為に弱いこと
(現に自分はバイト単位LZSS実装において、バイナリエディタだけにも関わらず非常に短時間で展開コードまで辿りつけている)
位置長さデータを全てメモリー上に展開できるサイズならって条件付なら、バイト単位LZSSと同等の速度で位置長さデータの制限からは開放されると思う。
他には、位置長さデータ長を変動させるのはどうだろう。
一致不一致フラグを8個まとめるなどバイト単位LZSSを元にするのは同じ。
その上で、位置長さデータが現れるたびにバイト数を変えてやる。
具体的には、位置長さデータが合計18bitであれば3,2,2,2バイト、といったようにだ。
要するに、位置長さデータにおいてバイト単位にならなかった場合は、その余白に次の位置長さデータを格納していく形で表現するわけだ。
利点は、上記と同じく位置長さデータのbit数が制限されない事と、上記案の欠点であったランダムアクセスも発生しない事。
欠点は、圧縮時にメモリー上に保持しておけるバイト数を超えるぐらい一致せずにいた場合に、位置長さデータを書き込むためのランダムアクセスが必須である事。
それと、上記に比べると多少はマシだが、やはり解析に弱いこと。
圧縮に問題があるのは上の案でも同じだし、こちらの問題の方が遥かにどうにかなるので、たぶんこちらの方が優秀。
展開性能は条件なしでバイト単位LZSSとほぼ同じコスト、圧縮は上記のとおり若干高コスト。
うーん、これぐらいしか思いつかん(一応、一致不一致フラグと同じように8個まとめるとかも考えたけど、明らかに下位互換なので)
ぶっちゃけ、展開コードだけで圧縮コードは書いた事無いし(dat作成コードでは全て不一致フラグという暴挙に出ている)
一度真面目に組んでみれば、もっと色々見えてくるものがあるかもしれないなー