LZSS v0.01 is here!

[encode]

OK, a very DRAFT version of my LZSS variant has been released!

Details:
Block size: 32M
Window size: 256K
Min.Match = 3
Max.Match = 66 (63+Min.Match)
Literals stored in 8-bits
Match lengths stored in 6-bits
Match offsets in 18-bits
Each literal/match flag requires one bit
i.e. all sizes are fixed
Storer&Szymanski parsing scheme was used on the entire 32 MB block
The max. mode (ex) differs from the Normal mode (e) only in much more deeper string search.

So anyways, enjoy!

[Intrinsic]

acutimer lzss e calgary.tar calgary-e.lzss
AcuTimer v1.4
Copyright (c) 2007 by LovePimple

lzss v0.01 by encode
optimizing 3079k block...
encoding...
done

Elapsed Time: 00 00:00:01.322 (1.322 Seconds)
Compressed Size: 1,430,672 bytes

acutimer lzss ex calgary.tar calgary-ex.lzss
AcuTimer v1.4
Copyright (c) 2007 by LovePimple

lzss v0.01 by encode
optimizing 3079k block...
encoding...
done

Elapsed Time: 00 00:00:55.004 (55.004 Seconds)
Compressed Size: 1,137,453 bytes

[encode]

...don't forget, the goal IS the decompression speed!

[LovePimple]

Thanks Ilia!

[Intrinsic]

ex used a LOT of memory, over 512mb!

Decompression times for above test:

calgary e and ex: 0.120 seconds.

Also compressed SFC, will do the decompression on em now

It would make life a million times easier if your program mentioned what file it was currently working on ;p makes it a nightmare todo large batches of files to a single log file ;p

[Intrinsic]

Here is SFC, e, ex and d sizes and times.

Decompression is super fast as i'm sure you know ;p

[pat357]

How does it compare in decompression speed to Thor e1/e2, Nanozip -cf/cd, Tor 0.4a -1/-2, 6pack, Quick LZ, LZOP, ... ?

[encode]

It should be faster than all programs listed due to the simplest decoder. Even QuickLZ has more complex coding scheme...

Later, will did some measurements...

[pat357]

It should be faster than all programs listed due to the simplest decoder. Even QuickLZ has more complex coding scheme...

Later, will did some measurements...

For accurate measurements, you'll need a ram-disk en write the output to nul.
Thor e1, QuickLZ, tor.. are already faster in decompression. then most HD's can handle.

[nimdamsk]

The best result will be if LZSS would be tested in-memory using QuickLZ's testing framework.
Question about exe compressor - what is the goal? Fastest and smallest decompressor? If so - good luck, otherwise i don't see how your packer would compete with FSG and MEW without filters and so on

[Bulat Ziganshin]

It should be faster than all programs listed due to the simplest decoder. Even QuickLZ has more complex coding scheme...

Later, will did some measurements...

compare it to "tor -11 -c1" which is also lzss

[encode]

Okay...

Some testing results with ENWIK9:

THOR 0.96, e1: 488,397,982 bytes, decomp. in 34 sec. (pr.time 20 sec.)
QUICKLZ 1.31, -3: 411,493,051 bytes, decomp. in 38 sec. (pr.time 7 sec.)
THOR 0.96, e2: 411,416,252 bytes, decomp. in 43 sec. (pr.time 21 sec.)
LZOP 1.01, -9: 366,349,786 bytes, decomp. in 37 sec. (pr.time 7 sec.)
LZSS 0.01, ex: 337,565,308 bytes, decomp. in 23 sec. (pr.time 5 sec.)
TOR 0.4, -11 -c1: 303,178,654 bytes, decomp. in 36 sec. (pr.time 11 sec.)

Just as I expected - my LZSS has the fastest decompression with a nice compression ratio.

It's interesting to compare it with TORNADO. TORNADO has a really large dictionary, but my LZSS has an optimal parsing, thus it really wins on relatively small files, for example, some testing results with 'book1':
TOR 0.4, -11 -c1: 351,892 bytes
LZSS 0.01, ex: 330,293 bytes

[LovePimple]

Quick test with ENWIK8 on my old Intel Pentium 3 @750 MHz, 512 MB RAM, Windows 2000 SP4 machine...

LZSS [e]

Compressed Size: 48,615,051 bytes

Compression Time: 1037.37 Seconds

Decompression Time: 7.77 Seconds

LZSS [ex]

Compressed Size: 38,254,303 bytes

Compression Time: 5518.26 Seconds

Decompression Time: 7.85 Seconds

[Matt Mahoney]

lzss squeezed into the pareto frontier for decompression speed.
http://cs.fit.edu/~mmahoney/compression/text.html

[joerg]

@encode - your new lzss-compressor looks very good
very good in decompression speed
thank you very much for this good work!

but

ask 1: have you test (i think you have done this)
your program with double the ram-requirements?
(because in the most of new computers we have 2 x 625 mbytes)
would this increase the compression ratio?

ask 2: what about
to implement a command to process a whole directory inclusive subdirectories ?

ask 3: may be it would possible to implement it
in a way like "qpress" from www.quicklz.com ?
or would it be more usefull
to test the compressor via a zip-file in "store"-mode
(it means zip without own compression)?

[lunaris]

lzss squeezed into the pareto frontier for decompression speed.
http://cs.fit.edu/~mmahoney/compression/text.html

Hey Matt update Infozip for actual 3.0 version.


Thanks

[encode]

ask 1: have you test (i think you have done this)
your program with double the ram-requirements?
(because in the most of new computers we have 2 x 625 mbytes)
would this increase the compression ratio?

Yes, I did. Processing large files like ENWIKs by 64 MB blocks will lead a few KB compression gain. Note that the dictionary size is just 256 KB, so a large block not really helps. Using 512 KB dictionary instead really helps, especially with text files, but usually hurts with executables.

ask 2: what about
to implement a command to process a whole directory inclusive subdirectories ?

ask 3: may be it would possible to implement it
in a way like "qpress" from www.quicklz.com ?
or would it be more usefull
to test the compressor via a zip-file in "store"-mode
(it means zip without own compression)?

Well, the archiving features is not really needed in just draft and DEMO compressor. The purpose of such things is just to test a new compression algorithm.

BTW, it would be fun if create something like kzip but compatible with super fast compressors. For example, compatible with QuickLZ, but providing a higher compression at the cost of compression time and memory use.

[Sami]

Yes, I did. Processing large files like ENWIKs by 64 MB blocks will lead a few KB compression gain. Note that the dictionary size is just 256 KB, so a large block not really helps. Using 512 KB dictionary instead really helps, especially with text files, but usually hurts with executables.

How about calculating both results, for 512kb and 256kb window, and choosing what works best. Perhaps 1mb window would work with 4bits for match length (if we want to pack to 3 bytes). You could also go much further by blocking and try splitting a block in half and compress the parts with 256 and 512 windows again and keep splitting until we gain compression, choosing the optimal configuration. With this executables may gain and testing 2 byte packed offset/matchlen may improve exes also. All this would keep the decompression time and complexity the same, making only shift/masking variable (which should not be a problem). But you can have several decompressors if this is not ok (when not optimizing for decoder size).

[encode]

Actually, the idea that will work much better than variable dictionary size is variable length offset coding. With just small complexity penalty. i.e. we may organize byte aligned coding as I described in some posts.
Anyway, like I said, here the main goal is extreme simplicity. If I will need compression I easily may add the arithmetic coder, etc.

[Sportman]

...don't forget, the goal IS the decompression speed!

LZSS had the second fastest decompression time and used the lowest CPU decompression time for test file1 (http://www.metacompressor.com/uploads.aspx)

Because the test system was doing some other tests not listed it took some time before your submit was proceeded. Tests run always dedicated no other processes then archiver and time/cpu/memory monitor software is running.

[encode]

Thanks for testing!

[Intrinsic]

LZSS doesn't like spaces in file names ;p even when passed to it using " "

[encode]

LZSS doesn't like spaces in file names ;p even when passed to it using " "

On my system, all worked OK:

D:\>lzss e "mp track.exe" "mp track.zx"
lzss v0.01 by encode
optimizing 1132k block...
encoding...
done

[Intrinsic]

Yeah sorry it just went over it again and it's the way it was setting the log output. It was trying to use ">lzss-GI MP-e.log" instead of > "lzss-GI MP-e.log" which was causing lzss to freak out IE it doesn't like more than the expected parameters, maybe an idea to either omit any trailing additions to the command line or give an error like "too many parameters" ? maybe show which ones it doesn't like to give people a hint what's going wrong?

[Lasse Reinhold]

Just a note - even ram drives are too slow here, I've tested a few ramdrives and the results are completely misleading. WAY too much driver and OS overhead at these speeds! Decompression to nul is slightly better.

VS2008 implementation of memcpy() on my Athlon64 6400+ with very cheap memory (very skewed system, I admit) is ~1292 MiB/s whereas decompression speed for some .tar mix of different kinds of files that I have is 519 MiB/s for QuickLZ level 3.

So feel free to use the QuickLZ/qpress benchmark function instead

[Cyan]

Hello

I'm a newly registered member of encode.su, so sorry for asking questions which may sound "newbye" to the knowledgeable ones.

I've been very interested in your LZSS scheme, because it seems to share common objectives with my little time-waster.
I am currently playing with my first code (ever) for compression. The target system is a handheld programmable calculator from the 90's (HP48 serie).
Should anyone be interested, or willing to verify, it can be downloaded here :
http://ScanZ.Webhop.Org

So you can guess there are pretty harsh limitations compared with a modern desktop PC, on both available memory and processing power.
On the other end, it also means the objects to compress are relatively "small", so i'm not in the multi-mega(giga)byte race.

Anyway, all this translates into : any compressor program has to be really simple, in order to become reasonably fast and small. Well, this is exactly what LZSS has been created for in the first place.

So now for the question (at last !)

Storer&Szymanski parsing scheme was used on the entire 32 MB block

That's where i'm getting lost.
Parsing, what for ? Filling a Dictionnary ?
LZSS, like LZ77, seems to refer to a previous repeated sequence through the use of "Offset". So this is not a dictionnary index.

Are you building a dictionnary for improved compression speed ?
Could dictionnary size impact compression rate (on top of sliding window size) ? I noticed you said a word about that, regarding another of your program (Balz).

Once again, sorry if all this seems trivial for you guys

Regards

Yann

[encode]

Hello
I'm a newly registered member of encode.su, so sorry for asking questions which may sound "newbye" to the knowledgeable ones.

Welcome!

Parsing, what for ? Filling a Dictionnary ?

Optimized parsing is about building a more efficient literal/match sequence. As you know, there is a bunch of available combinations of different matches/literals at each position. For example, instead of a match length of three bytes long you may drop three literals, or if bunch of matches available, it might be that better to cut down current match in favor to get the longest one right after current match. So, with S&S parsing we find ALL possible matches at EACH position. After, we go backwards from the end of the buffer to build the optimal PATH inductively - i.e. we get the best match/literal for each position. Even in it's simplest form such thing is very resource and time consumptive.

LZSS, like LZ77, seems to refer to a previous repeated sequence through the use of "Offset". So this is not a dictionnary index.

Yep, it's a [match length, match position] pair. In other words, it's something like "Copy From" directive.

Are you building a dictionnary for improved compression speed ?
Could dictionnary size impact compression rate (on top of sliding window size) ? I noticed you said a word about that, regarding another of your program (Balz).

The goal of LZSS is a simplest and fastest decoder. My LZSS encoder is really slow, indeed. However, we may do a very fast compression at the cost of low compression ratio.
Well, the larger dictionary should improve compression ratio in most cases. However, with such fixed-sized LZ-codes as I use with LZSS, we may loose compression - since we must limit the max match length. Anyway, a larger dictionary mainly benefits on text files, not on binaries. For binaries, an efficient coding of smallest matches are really important.

Hope this helps...

[Cyan]

thank you very much for your answer. This open up quite some new perspective for me.

if bunch of matches available, it might be that better to cut down current match in favor to get the longest one right after current match

Yes, i was vaguely aware of something like that, but really unsure on how to deal with it and how much it would offer. And to be fair, i'm still struggling to find a scenario where it would be worthwhile to shorten the current matchlength in favor of the following one.

Maybe it could be the consequence of choosing an unsuitable format. I've dropped the flags in favor of a sequence model. Consequently, 2 matches are necessarily separated by a null-literal-length descriptor. I've not seen this methodology selected in other compressors, so maybe it was not a wise choice.

For example, let's imagine the following sequence :
MMMMMMMM LLL MMMM --> 3(M) 1(D) 3(L) 3(M) = 10 symbols
and let's imagine it could be rearranged this way :
MMMMMMM MMMM MMMM --> 3(M) 1(D) 3(M) 1(D) 3(M) = 11 symbols
Result : i'm losing one symbol.

Note that this seems different with a Flag-based format. Here we would have :
Scenario 1 : F+3(M) + 3x F+1(L) + F+3(M) = 9 symbols + 5 flags
Scenario 2 : F+3(M) + F+3(M) + F+3(M) = 9 symbols + 3flags
Result : it saves 2 flags (=2 bits).

So either i'm not considering the right scenario, or the format is forbidding this kind of optimisation...

So, with S&S parsing we find ALL possible matches at EACH position. After, we go backwards from the end of the buffer to build the optimal PATH inductively - i.e. we get the best match/literal for each position

OK, so that looks like ""finding shortest path" algorithm, and i guess the "length" of each segment is the length of encoded format.

But still, i guess i must find at least one scenario in which the basic "forward search and encode" is outclassed.

Currently, i'm using an unintelligent "brute force search" algorithm to find the longest match from a given position.Should this best matchlength be large enough (at least 4 symbols), i reference it with the "offset/match" sequence. Then skipping the sequence, and starting again.

Really down to the basics. Given this is my first compressor, i guess this can considered as an exercise. So this model is only willing to be improved.

[Cyan]

Nevermind,
i think i've got one scenario where delaying the Match decision does pay off :

Let's imagine this sequence :

LLL MMMMM MMMMM --> 1(D) 3(L) 3(M) 1(D) 3(M) --> 11 symbols
Maybe it could re-arranged this way :
LLLL MMMMMMMMM --> 1(D) 4(L) 3(M) --> 8 symbols
This one does save 3 symbols !

Does it really happen ?
Yes, this is exactly what happens with a long sequence of Zero for example.
So giving a more precise shape to above example :

Scenario 1 : 00000 (...) 123 00000 00000
Scenario 2 : 00000 (...) 1230 000000000

I guess the beauty of the "shortest path" methodology is that you don't have to worry about enumerating all the possibles subcases, it just gets the shortest path, whatever is in between.

[encode]

OK, check this out:

buffer position: longest match available

100: 5
101: 50

If we will grab the first match, we loose a very long match at next position. Here, we should drop one literal, plus the real good match of 50 bytes long.

The example above is about how Lazy Matching or Lazy Evaluation works. We check the next one or two bytes ahead for a longer match. If longer match found, we output one literal and a followed longer match - in other words it's about dropping current match.