Results 1 to 10 of 10

Thread: LZ77 with 12 bit hash table: what I do wrong?

  1. #1
    Member lz77's Avatar
    Join Date
    Jan 2016
    Location
    Russia
    Posts
    46
    Thanks
    14
    Thanked 11 Times in 7 Posts

    Question LZ77 with 12 bit hash table: what I do wrong?

    Here's an algorithm for LZ77 compression. function LZ4_compress_generic in lz4.c uses such algorithm:
    U32 calcHash(U32 s) { return s*2654435761U >> 20; }

    function compress(char* source, char* dest, int source_size)
    { Fill in hash_table[4096] with 0xFFFFFFFF;

    anchor=source;
    // Main loop
    while (rest of source_size > 3)
    { hash=calcHash(U32 *source);
    if (hash_table[hash] == 0xFFFFFFFF) || (source-hash_table(hash) > 65535) || (U32 *source != U32 *hash_table[hash])
    { hash_table[hash]=source++;
    continue;
    }
    match_num=4;
    Calculating additional number of matched bytes both from left and right of source:
    match_num=number of total matched bytes
    Coding llllmmmm oooooooo oooooooo [l]...[l] [literals] [m]...[m]:
    number_of_literals=source-anchor;
    match_num;
    offset=source-hash_table[hash];

    hash_table[hash]=source;
    source+=match_num;
    anchor=source;
    hash_table[calcHash(U32 *(source-2)]=source-2;
    }

    last_literals:
    ...
    }


    lz4 on level=1 shows compression ratio of enwik8 ~ 53%. But if I run my code similar to the above algorithm, it shows ratio = 56.9%.
    My code shows ratio ~ 53% if size of hash_table = 32768 cells. What I do wrong?

    Thanks for your patience.
    Last edited by lz77; 31st July 2017 at 13:43.

  2. #2
    Member
    Join Date
    Feb 2015
    Location
    United Kingdom
    Posts
    154
    Thanks
    20
    Thanked 66 Times in 37 Posts
    Compression ratio in lz77 isn't just about finding the longest match, it's about the ratio of how much data can be represented using the least bytes. You can easily generate a float containing this ratio as 'complen/len', the bigger the value the better the match is. With this you can add thresholds for minimum ratios, this is what I use in my lz77 code, typically a ratio of 1.35 or higher allows for better indirect parsing (due to thresholds preventing bad matches from being encoded). Also a look-ahead should be taken into consideration, it's usually better to look forward at least 3 to 4 bytes for the algorithm to consider a different match. These two changes will offer better compression without having to change the size of the hash-table, though it might slow it down a little bit.

  3. The Following User Says Thank You to Lucas For This Useful Post:

    lz77 (3rd August 2017)

  4. #3
    Member lz77's Avatar
    Join Date
    Jan 2016
    Location
    Russia
    Posts
    46
    Thanks
    14
    Thanked 11 Times in 7 Posts
    Thanks, but at this time I'm interesting in compression "on the fly" or at least "on the run". I'm going to rewrite my code in asm, so I want to know whether the algorithm contains a little bug that worsens the compression ratio...

    With naive search I can do without hash table at all.

    By the way: what ratio & time shows your lz77 code on enwik8 as compared with lz5 level 1?

  5. #4
    Member
    Join Date
    Feb 2015
    Location
    United Kingdom
    Posts
    154
    Thanks
    20
    Thanked 66 Times in 37 Posts
    Oof that's a comparison I'm not looking forward to, lz5 is a beast but I typically use mine to detect structures and help bwt compress better, so they are quite different in terms of their innards.

    Here's the closest compression times to ratio I could get:
    enwik8 to 42,568,137 in 8.7 sec. [lizard v1.0.0 -25]
    enwik8 to 42,558,854 in 10.5 sec. [Jam 0.71 (unreleased, lz77 codec only)]

    And for the fastest modes:
    enwik8 to 52,988,350 in 0.4 sec. [lizard v1.0.0 -20]
    enwik8 to 47,249,341 in 3 sec. [Jam 0.71 (unreleased, lz77 codec only)]

    Lizard is a monster at decode speed (+800MB/s) whereas mine decodes at 300MB/s. There's so many trade-offs with lz77 that it's becoming harder and harder to get any faster than some of the current implementations. I guess your implementation really just depends on your use-case. For extremely fast compression (which is what you're looking for) the density library should be a good place for ideas on how to go faster: https://github.com/centaurean/density.

    Another trick you could use is how lizard contains multiple streams for decoding, this allows for multiple pointers to decode data (literal, match, and offset streams) out-of-order and achieve a decent speed boost.

    Hopefully this helps.
    Last edited by Lucas; 2nd August 2017 at 10:15.

  6. The Following User Says Thank You to Lucas For This Useful Post:

    lz77 (3rd August 2017)

  7. #5
    Member lz77's Avatar
    Join Date
    Jan 2016
    Location
    Russia
    Posts
    46
    Thanks
    14
    Thanked 11 Times in 7 Posts
    Thanks a lot. Some questions:
    1. Does Jam 0.71 use something more complicated than simple hash to get ratio 47% and 42%?
    2. Suppose I develop a code that on fast level compresses data 10% better than lz5/lizard with the same speed. Do I have any chance to sell my algorithm to developers commercial archivers/backup software etc.?
    3. Do developers get a benefit as a result of publications like github.com/centaurean/density?
    4. Where can I download sources (Delphi, FPK, C) of free for commercial use archiver to simply replace the compression/decompression functions with my own functions in asm?
    Last edited by lz77; 3rd August 2017 at 19:33.

  8. #6
    Member
    Join Date
    Feb 2015
    Location
    United Kingdom
    Posts
    154
    Thanks
    20
    Thanked 66 Times in 37 Posts
    1) Jam 0.71 uses a hash chain with a 2MB hash, hash chains are links from a hash function that mark positions of hash collisions, it requires up to 4n space + the hash but can be reduced down to 4n/k with a smaller window. Match finding varies from 1 byte look-ahead to 4 byte look-ahead with a heuristic for searching the chain; if we don't find a match within the first 8 comparisons then we move on. But if we have found at least 1 good match with the first 8 comparisons then we keep searching deeper up to 32 positions deep. The indirect parsing helps increase compression by about 3% which translates into about 1MB increase in compression on enwik8. The format is lz4 style token packing but with leb128 with carry of lower byte ranges, this theoretically allows distances up to 32GB large but realistically it's limited to 4GB. That's pretty much all there is to it.

    2) Supposing you do make the fastest encoding lz77 algorithm for a given ratio, it may be attractive if the license you give it is fairly permissive and unobtrusive with regards to how customers use it. I wouldn't recommend adding clauses that could be used as an exploit to obtain rights to other people's work (*cough https://encode.ru/threads/2780-ZSTD-license). If you distribute your code as a dll then you should be able to release it in a way such that your code is completely separate of any customer's compiled project, this is usually a safe bet for commercial applications. As for sales it really depends how you market it, personally I'd let the work speak for itself rather than trying to push hard. It's fine to write articles or blog posts comparing it to other solutions, but being bias is never really a good thing for your image, especially if you intend to make money off of it

    3) The benefit of devs publishing their work is that it gains the author recognition and can potentially inspire other programmers on how to improve their own code.

    4) I'm not too sure, if you're trying to replace closed-source solutions decoders with a speedier asm version that might be breaking their license if they don't want people reverse engineering it. You could possibly write your own decoder for something like winrar but the license says you need written permission from the creators of winrar to modify their decoder, and it would only apply to non-commercial use. As for sources it depends what you're looking to modify, no one can be stopped from reverse engineering code but you can release it as open source under such a restrictive license that no one can use it commercially, https://github.com/powzix/kraken/ is a great example of this. I guess it's really down to you weather you'd want to write it.

  9. The Following User Says Thank You to Lucas For This Useful Post:

    lz77 (4th August 2017)

  10. #7
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    lz77, you can develop your compressor as plugin to freearc or 7-zip. CLS API supported by freearc is extremely simple to implement, so i suggest you to start with it

    https://encode.ru/threads/2718-Stand...on-library-API

  11. The Following User Says Thank You to Bulat Ziganshin For This Useful Post:

    lz77 (16th August 2017)

  12. #8
    Member lz77's Avatar
    Join Date
    Jan 2016
    Location
    Russia
    Posts
    46
    Thanks
    14
    Thanked 11 Times in 7 Posts
    Thanks, but what happens, if my code will be so good (for example, 10% faster, and ratio 10% better than Lizard) that it can be used by companies like Yandex, Aсronis, E. Roshal?.. Could I make some money on this? Or it's useless to dream about it?

    By the way: why members of this forum do not have inventions/patents like Shindlers transform, and publications on arxiv.org?

  13. #9
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    > if my code will be so good (for example, 10%
    > faster, and ratio 10% better than Lizard) that

    You can add your codec to some open-source projects (basically ones which use LZ4),
    linux utilities, etc. If its actually good, people might start using it.

    > it can be used by companies like Yandex, Aсronis, E. Roshal?..

    Winrar is unlikely (they always used their own codecs before),
    but you might get a job offer from some big company.

    Don't expect anybody to just pay you for already existing sources, though.
    Just that if your codec is good, you'd be obviously the best person to maintain it.

    > Could I make some money on this? Or it's useless to dream about it?

    It may be possible to sell a codec to some game studio - modern games are
    basically self-extracting archives of various resources,
    so using some compression is necessary, and backward compatibility doesn't matter much.

    > By the way: why members of this forum do not have inventions/patents like
    > Shindlers transform, and publications on arxiv.org?

    Do you expect patents assigned to encode.ru nicknames? :)
    Well, some actually do have them.
    Just keep in mind that you'd spend like $15k (and a lot of work) to get a US patent
    for a codec remotely (non-US patents basically don't matter unless you work for government).
    And then the only use for it would be showing your name in patents.google.com to people.
    Well, or if you want to be a patent troll.

    As to publications, they're only needed when you work at a university.
    Its the best way if you only have a theory, complexity analysis of some algorithm, etc.
    While for a programmer, its usually best to show off a working program -
    in fact, any detailed algorithm descriptions would be bad, because somebody else
    might patent it, etc. - https://encode.ru/threads/2648-Publi...t-by-Storeleap

    For an example of how to sell codecs you can look at http://www.radgametools.com/oodle.htm

  14. The Following User Says Thank You to Shelwien For This Useful Post:

    lz77 (16th August 2017)

  15. #10
    Member lz77's Avatar
    Join Date
    Jan 2016
    Location
    Russia
    Posts
    46
    Thanks
    14
    Thanked 11 Times in 7 Posts

    Smile

    Quote Originally Posted by Lucas View Post
    Here's the closest compression times to ratio I could get:
    enwik8 to 42,568,137 in 8.7 sec. [lizard v1.0.0 -25]
    enwik8 to 42,558,854 in 10.5 sec. [Jam 0.71 (unreleased, lz77 codec only)]
    He-he, see results of my old (not yet optimized for speed) code in comparison with lizard v1.0.0:

    >timer mycode.exe enwik8

    Timer 3.01 Copyright (c) 2002-2003 Igor Pavlov 2003-07-10
    Source file:
    Source size = 100000000, packed size = 42195352, ratio = 0,42195

    Kernel Time = 0.328 = 00:00:00.328 = 7%
    User Time = 3.671 = 00:00:03.671 = 83%
    Process Time = 4.000 = 00:00:04.000 = 90%
    Global Time = 4.406 = 00:00:04.406 = 100%

    >timer mycode.exe enwik8.flz

    Timer 3.01 Copyright (c) 2002-2003 Igor Pavlov 2003-07-10

    Kernel Time = 0.375 = 00:00:00.375 = 16%
    User Time = 0.812 = 00:00:00.812 = 35%
    Process Time = 1.187 = 00:00:01.187 = 52%
    Global Time = 2.281 = 00:00:02.281 = 100%
    ===============================

    >timer lizard32.exe -25 -B7 --no-frame-crc enwik8 enwik8.liz

    Timer 3.01 Copyright (c) 2002-2003 Igor Pavlov 2003-07-10
    using blocks of size 262144 KB
    Compressed 100000000 bytes into 42164371 bytes ==> 42.16%

    Kernel Time = 0.437 = 00:00:00.437 = 1%
    User Time = 25.968 = 00:00:25.968 = 96%
    Process Time = 26.406 = 00:00:26.406 = 98%
    Global Time = 26.844 = 00:00:26.844 = 100%

    >timer lizard32.exe -d enwik8.liz

    Timer 3.01 Copyright (c) 2002-2003 Igor Pavlov 2003-07-10
    Decoding file enwik8
    enwik8.liz : decoded 100000000 bytes

    Kernel Time = 0.593 = 00:00:00.593 = 8%
    User Time = 0.500 = 00:00:00.500 = 7%
    Process Time = 1.093 = 00:00:01.093 = 15%
    Global Time = 7.000 = 00:00:07.000 = 100%
    ========================================

    My code compresses enwik8 7 times faster than lizard...

    After I rewrite my code in asm it will work ~ 40% faster.

Similar Threads

  1. Fast CRC table construction and rolling CRC hash calculation
    By Bulat Ziganshin in forum Data Compression
    Replies: 10
    Last Post: 27th May 2018, 03:32
  2. 32 bit or 64 bit Windows usage case
    By necros in forum The Off-Topic Lounge
    Replies: 10
    Last Post: 18th August 2016, 08:57
  3. Perfect Hash Function to Hash Strings
    By joey in forum Data Compression
    Replies: 18
    Last Post: 22nd March 2016, 10:59
  4. Filling a large Zobrist hash table
    By Earl Colby Pottinger in forum Data Compression
    Replies: 5
    Last Post: 11th October 2013, 13:05
  5. Compression benchmarking: 64 bit images and 24 bit codecs
    By m^2 in forum The Off-Topic Lounge
    Replies: 6
    Last Post: 30th November 2011, 17:01

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
  •