Page 1 of 3 123 LastLast
Results 1 to 30 of 68

Thread: LZSS v0.01 is here!

  1. #1
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts

    Cool LZSS v0.01 is here!

    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!
    Attached Files Attached Files

  2. #2
    Member
    Join Date
    May 2008
    Location
    England
    Posts
    325
    Thanks
    18
    Thanked 6 Times in 5 Posts
    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

  3. #3
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    ...don't forget, the goal IS the decompression speed!

  4. #4
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Thumbs up

    Thanks Ilia!

  5. #5
    Member
    Join Date
    May 2008
    Location
    England
    Posts
    325
    Thanks
    18
    Thanked 6 Times in 5 Posts
    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
    Last edited by Intrinsic; 1st August 2008 at 00:50.

  6. #6
    Member
    Join Date
    May 2008
    Location
    England
    Posts
    325
    Thanks
    18
    Thanked 6 Times in 5 Posts
    Here is SFC, e, ex and d sizes and times.

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

  7. #7
    Member
    Join Date
    May 2008
    Location
    Antwerp , country:Belgium , W.Europe
    Posts
    487
    Thanks
    1
    Thanked 3 Times in 3 Posts
    How does it compare in decompression speed to Thor e1/e2, Nanozip -cf/cd, Tor 0.4a -1/-2, 6pack, Quick LZ, LZOP, ... ?

  8. #8
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    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...

  9. #9
    Member
    Join Date
    May 2008
    Location
    Antwerp , country:Belgium , W.Europe
    Posts
    487
    Thanks
    1
    Thanked 3 Times in 3 Posts
    Quote Originally Posted by encode View Post
    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.
    Last edited by pat357; 1st August 2008 at 20:15.

  10. #10
    Member
    Join Date
    Jan 2007
    Location
    Moscow
    Posts
    239
    Thanks
    0
    Thanked 3 Times in 1 Post
    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

  11. #11
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,511
    Thanks
    746
    Thanked 668 Times in 361 Posts
    Quote Originally Posted by encode View Post
    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

  12. #12
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    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


  13. #13
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Quick test with ENWIK8 on my old Intel Pentium 3 @750 MHz, 512 MB RAM, Windows 2000 SP4 machine...

    Code:
    LZSS [e]
    
    Compressed Size: 48,615,051 bytes
    
    Compression Time: 1037.37 Seconds
    
    Decompression Time: 7.77 Seconds

    Code:
    LZSS [ex]
    
    Compressed Size: 38,254,303 bytes
    
    Compression Time: 5518.26 Seconds
    
    Decompression Time: 7.85 Seconds

  14. #14
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    lzss squeezed into the pareto frontier for decompression speed.
    http://cs.fit.edu/~mmahoney/compression/text.html

  15. #15
    Member
    Join Date
    May 2008
    Location
    Germany
    Posts
    410
    Thanks
    37
    Thanked 60 Times in 37 Posts
    @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)?

  16. #16
    Member
    Join Date
    May 2008
    Location
    brazil
    Posts
    163
    Thanks
    0
    Thanked 3 Times in 3 Posts
    Quote Originally Posted by Matt Mahoney View Post
    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

  17. #17
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Quote Originally Posted by joerg View Post
    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.

    Quote Originally Posted by joerg View Post
    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.

  18. #18
    Programmer
    Join Date
    Jul 2008
    Location
    Finland
    Posts
    102
    Thanks
    0
    Thanked 1 Time in 1 Post
    Quote Originally Posted by encode View Post
    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).

  19. #19
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    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.

  20. #20
    Member
    Join Date
    Aug 2008
    Location
    Planet Earth
    Posts
    789
    Thanks
    64
    Thanked 274 Times in 192 Posts

    Thumbs up

    Quote Originally Posted by encode View Post
    ...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.

  21. #21
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Thanks for testing!

  22. #22
    Member
    Join Date
    May 2008
    Location
    England
    Posts
    325
    Thanks
    18
    Thanked 6 Times in 5 Posts
    LZSS doesn't like spaces in file names ;p even when passed to it using " "

  23. #23
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Quote Originally Posted by Intrinsic View Post
    LZSS doesn't like spaces in file names ;p even when passed to it using " "
    On my system, all worked OK:
    Code:
    D:\>lzss e "mp track.exe" "mp track.zx"
    lzss v0.01 by encode
    optimizing 1132k block...
    encoding...
    done

  24. #24
    Member
    Join Date
    May 2008
    Location
    England
    Posts
    325
    Thanks
    18
    Thanked 6 Times in 5 Posts
    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?

  25. #25
    Programmer
    Join Date
    May 2008
    Location
    denmark
    Posts
    94
    Thanks
    0
    Thanked 2 Times in 2 Posts
    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
    Last edited by Lasse Reinhold; 8th August 2008 at 12:56.

  26. #26
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    865
    Thanks
    463
    Thanked 260 Times in 107 Posts

    Thumbs up Newbye question

    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
    Last edited by Cyan; 2nd September 2008 at 17:21.

  27. #27
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Quote Originally Posted by Cyan View Post
    Hello
    I'm a newly registered member of encode.su, so sorry for asking questions which may sound "newbye" to the knowledgeable ones.
    Welcome!

    Quote Originally Posted by Cyan View Post
    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.

    Quote Originally Posted by Cyan View Post
    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.

    Quote Originally Posted by Cyan View Post
    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...

  28. #28
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    865
    Thanks
    463
    Thanked 260 Times in 107 Posts

    Smile

    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.
    Last edited by Cyan; 3rd September 2008 at 12:49.

  29. #29
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    865
    Thanks
    463
    Thanked 260 Times in 107 Posts
    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.

  30. #30
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    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.


Page 1 of 3 123 LastLast

Similar Threads

  1. LZSS with a large dictionary
    By encode in forum Data Compression
    Replies: 31
    Last Post: 31st July 2008, 22:15

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •