Page 1 of 2 12 LastLast
Results 1 to 30 of 46

Thread: QUAD 1.11 overview

  1. #1
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Okay, the development in progress. What's already done:
    + Added circular table to compressor
    + Improved Lazy Matching (Normal mode)
    As a result with Normal mode QUAD has a higher compression and speed!

    Some testing results with Normal mode:

    PAK0.PAK, 183,997,730 bytes:
    QUAD 1.11: 94,049,672 bytes, 224 sec
    QUAD 1.10: 94,056,511 bytes, 240 sec

    ENWIK8, 100,000,000 bytes:
    QUAD 1.11: 29,649,604 bytes, 46 sec
    QUAD 1.10: 29,731,541 bytes, 53 sec

    Actually, the improvement is vary from file to file. Also I'm not finish improving Normal mode. The Max mode will be next...


  2. #2
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,565
    Thanks
    220
    Thanked 146 Times in 83 Posts
    Good improvement!

  3. #3
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    fp.log packed down to 602 KB:

    fp.log.quad

    Some notes about optimal parsing with QUAD. Actually, the Flexible Parsing which currently used with Max mode achieves optimality but only with static encodings. The main thing I understood yesterday:
    With static encodings, match lengths 3 + 7 is equal to 4 + 6 or any other combination, since to encode each match we need, say 15 bits, and in both cases we jump to equal position. With adaptive encodings that's not true – 3 + 7 may not be equal to 4 + 6, since each choice has own cost based on statistics, usually a shortest match can be coded in fewest bits.

    Well, actually QUAD already use some kind of weight emulation – some choices has a higher priority than others – for example, matches with large index has lower priority than matches with small index. In addition, literal + match combination has a higher priority compared to match + match combination, and so on.

    So, what can be done with QUAD is adding some kind of price function – to test each variant and choose the shortest path.

    At each step, we can produce a large number of matches:
    We have 64 match indexes. Assume that at each index we can get the match, also each match can be cut-downed to MINMATCH.

    For example, we got a match length of 9 with index 3:
    We can produce at this index match lengths of:
    9
    8
    7
    6
    5
    4
    3

    And this goes on at each index.

    Okay, assume we always look one step ahead. We must check ALL combination of matches to find the best one.

    Current-max-value = current-match-length + followed-match-length (a match that can be found if we choose current one)

    This is the path – we can jump from current position to max-value.

    Now check for all combinations within current match.

    For example if current match length is 9, then we check all position that this match can reach and all followed matches:

    current position + 1 ... current position + match length – 1

    This is the baseline flexible parsing. However, naturally at this loop we must get the real cost of each choice:

    Bits needed to encode literal
    Bits needed to encode match length + bits needed to encode match index
    And using such weights or costs we must make decisions. So, naturally max-value must not represent the number of bytes to jump, but some kind of weight or compression ratio – i.e. bytes to jump vs. bits needed to do this jump.

    By the way, with QUAD 1.11 I changed some parts of code to more readable form (spaces are deleted by crazy forum engine):

    int len = maxLen;
    int maxValue = maxLen + getMatch((i + maxLen), n);

    if (maxValue < ((MAXMATCH * 2) - 1)) {
    for (int j = 1; j < len; j++) {
    int temp = (j + (j == 1)) + getMatch((i + j), n);

    if (temp > maxValue) {
    maxValue = temp;
    maxLen = j; // optimize match length
    }
    }
    ...

    Well, all people keep silence about future improvements... Ask Igor Pavlov again?


  4. #4
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    In addition, truly optimal parsing must give less benefit to QUAD's engine compared to the original ROLZ2 or say LZ77 (LZMA).

    Why?

    QUAD is more context based than ROLZ2 or LZ77. As a result QUAD can work faster, but optimal parser has a really lower number of choices - as a result small compression improvement.

    For example, with LZP (LZPXJ / PIM) the flexible parsing gives very small improvement.

    Malcolm said that this optimal cost-based parsing leads to some fantastic results...


  5. #5
    Member
    Join Date
    Mar 2007
    Posts
    34
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi Ilia,

    you posted information about optimal parsing in another thread - there is not much more to say about. With adaptive coding you will not find any reasonable fast way to get the real optimum. So usual approach is to do optimal parsing for small block only and assume static stats for it (based on current state of adaptive stats).

    My proposals for next steps: add Price function to coder class. Use price function for match choices in current scheme. Should give some [small] gain in most cases. If this works, you may extend optimal parsing to some larger block checking for best path.

    Uwe

  6. #6
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Hi Uwe! Thank you for reply!

    Indeed, in previous post I collect many information about Oprimal Parsing.

    Quote Originally Posted by Uwe Herklotz
    My proposals for next steps: add Price function to coder class. Use price function for match choices in current scheme. Should give some [small] gain in most cases.
    Thit is about I want to add.

    The question is how to use these prices?

    Price functions can be something like these:

    class TPPM:
    //...
    int GetPrice(int s, int x) {
    if (counter2[x].cnt[s]) { // i.e. 0...4095 - price or bigger - better, also we can invert this assumption
    return ((counter2[x].cnt[s] * 4096) / counter2[x].total)
    }
    return (z); // some tiny value, to avoid Set() call to get the real price
    }

    int GetIndexPrice(int m) { // same, but without ESCAPE extra case
    return ((counterX.cnt[m] * 4096) / counterX.total)
    }

    I tried these and other functions with some tricks - no improvements so far - looks like I was wrong...


  7. #7
    Member
    Join Date
    Mar 2007
    Posts
    34
    Thanks
    0
    Thanked 0 Times in 0 Posts
    int logtab[N];

    array logtab holds bit costs for probabilities from 0..1 mapped to range N,
    bit costs are scaled by value N to cover small coding costs as well (<1bit)

    initialization using float/double functions:
    logtab[i] = (-log(i/N)/log(2))*N; // e.g. N=4096

    usage for example:
    return (logtab[(counter2[x].cnt[s] * N) / counter2[x].total])

  8. #8
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 153 Times in 18 Posts
    Quote Originally Posted by encode
    int GetPrice(int s, int x) {
    ... return ((counter2[x].cnt[s] * 4096) / counter2[x].total);
    ...
    In this price-function the cost is equal to the probability.
    But you must look at this in the following way. Lets say we have 3 symbols a,b and c. Assume P(a)=1/256, P(b)=31/256 and P(c)=224/256.
    If we code sequence ac the total price is ~8.193 bits. Coding sequence bb costs ~6.092 bits. So, coding sequence bb is cheaper than coding ac.
    Quote Originally Posted by encode
    // i.e. 0...4095 - price or bigger - better
    If you sum probabilities of ac you get 225/256. For bb you get 62/256. Although the cumulative probability of ac is bigger than the one from bb, bb is cheaper in terms of bits. If youd base the decision on cum. prob., the decision would obviously be wrong.
    Therefore the price-function Uwe proposed which is based on real bit-cost should give better results.

  9. #9
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Thank you Uwe, thank you Cristian. Will make some tests...

  10. #10
    Member
    Join Date
    Jun 2008
    Location
    G
    Posts
    372
    Thanks
    26
    Thanked 22 Times in 15 Posts
    Do you plan to release a Quad version with selectable memory usage? Like 7z?

    Iam interesting in test results for large test sets and big memory usage.

  11. #11
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Quote Originally Posted by thometal
    Do you plan to release a Quad version with selectable memory usage? Like 7z?
    I dont. In addition, current QUAD file format not allows such thing. Also QUAD not in this race for super compression, I know its very seductive for any data compression author to enlarge memory usage to 2 GB and make other things - IMHO its lame. I prefer to make it simple, reliable and not memory hungry. As a result we can see high decompression speed (25+ MB/sec). The thing with super optimal parsing is just to maximize compression or reduce the redundancy of the QUAD compression format. Upcoming QUAD 1.11 has notable higher compression speed with normal mode - this thing make QUAD more usable. The goal of this project - a data compression tool, i.e. - its not for benchmarking and this is the main difference between QUAD and many others...


  12. #12
    Member
    Join Date
    Dec 2006
    Posts
    611
    Thanks
    0
    Thanked 1 Time in 1 Post
    Quote Originally Posted by encode
    Some testing results with Normal mode:
    ...
    Sounds very good!

  13. #13
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    After some crazy digging, I finally found an improvement!

    Without any price functions. Actually, I've found two improvements:

    1. Improvement can be regarded as a fix for current weight emulation. In some cases this gives some tiny compression improvement, in others some tiny loss. However, in most cases it's useful.

    2. Some nice idea about replacement for "bad" matches. For example, if current match length is 3 and match index is 32 or higher this is called bad match and in current scheme this one will have lower priority - i.e. this match must be replaced, when it is possible...



    Continue experimenting...

    P.S.
    Now I get the real understanding what's going on and how to use the trick which I called "weight emulation"...


  14. #14
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Well, new parsing scheme is more "balanced":

    ENWIK8
    29,152,166 bytes -> 29,122,295 bytes

    world95.txt
    596,084 bytes -> 595,598 bytes

    mptrack.exe
    506,919 bytes -> 506,641 bytes

    bible.txt
    937,624 bytes -> 936,701 bytes

    However, with some "weird" files we can see some compression loss:
    fp.log
    619,437 bytes -> 620,060 bytes

    english.dic
    829,268 bytes -> 830,557 bytes


  15. #15
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    ENWIK9
    256,486,470 bytes -> 256,213,412 bytes


  16. #16
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Quote Originally Posted by Uwe Herklotz
    logtab[i] = (-log(i/N)/log(2))*N; // e.g. N=4096
    By the way, something wrong with this function:

    class TProbMap {
    private:
    enum {
    N = 4096
    };
    int tab[N];

    public:
    TProbMap() {
    for (int i = 0; i < N; i++) {
    tab[i] = (-log(i/N)/log(2))*N; // e.g. N=4096

    //printf("%d: %d
    ", i, tab[i]);
    }

    }

    int operator()(int i) {
    return (tab[i]);
    }
    };

    BCC32:
    ambiguity between std:log(double) and std:log(long double)

    Changing code to:
    for (int i = 0; i < N; i++) {
    tab[i] = (-log(double(i/N))/log(double(2)))*N; // e.g. N=4096

    Fix that, but during execution:

    log: SING error

    I compile this code with VC++ 6.0, again each tab[i] will contain some strange value...


  17. #17
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 153 Times in 18 Posts
    Quote Originally Posted by encode
    tab[i] = (-log(i/N)/log(2))*N;
    Maybe this works:

    tab[i] = (int)(-log(i*1.0/N)*N/log(2.0));

  18. #18
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 153 Times in 18 Posts
    Quote Originally Posted by encode
    for (int i = 0; i < N; i++)
    You shouldnt start at 0, but at 1. log(0) isnt defined.

  19. #19
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Quote Originally Posted by Christian
    tab[i] = (int)(-log(i*1.0/N)*N/log(2.0));
    Yepp! Thank you very much!

  20. #20
    Member
    Join Date
    Mar 2007
    Posts
    34
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by encode
    logtab[i] = (-log(i/N)/log(2))*N; // e.g. N=4096
    By the way, something wrong with this function:
    My quick notice should demonstrate principle only. Of course parameters for log functions have to be float/doubles. Using integer division by N will always give zero.
    Quote Originally Posted by Christian
    tab[i] = (int)(-log(i*1.0/N)*N/log(2.0));
    Yep, this should work. Or use explicit type conversion.
    Quote Originally Posted by Christian
    You shouldnt start at 0, but at 1. log(0) isnt defined.
    Again right. IIRC I defined logtab[0] explicitely to zero outside the loop. This should not be used anyway.

  21. #21
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Thank you Uwe!

    By the way, do you used a price function with your excellent ALZ algorithm?

  22. #22
    Member
    Join Date
    Mar 2007
    Posts
    34
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by encode
    By the way, do you used a price function with your excellent ALZ algorithm?
    Yes. However, ALZ does not include optimal parsing in terms of checking the optimal sequence of matches to encode. But if a match is chosen by simple heuristics (similar to QUAD normal mode) then price function is used to determine if the found match should be omitted and coded as sequence of literals instead. Thats sometimes important with multimedia data where coding delta-filtered literals is often better than short matches.

    The consequence of described ALZ price checks is that usally much more literals are coded as done for example with LZMA. As result decoding is considerably slower.

  23. #23
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts


    Okay, let me describe the new scheme:

    Pseudo code

    getMatch(i)
    getMatch(i) - actually returns not the real match length which can be foud at i'th position:

    first, we find the actual max match length and its match index, exactly the same routine as with encode()

    if match length is less than min match - return 1

    else

    return - match length minus (index >=

    i.e. if best match has index equal or above eight, decrease match lenght by one - this represents some kind of penalty or "weight" adjustment or some kind of weight emulation

    main parsing loop
    get the max value for current position

    max value = current match length + followed match length (followed match length computed by getMatch(i) - i.e. includes penalties)

    if current match length is minimum allowed match and current match index is >= 8 - decrease max value by one - again make some penalty, so we probably will able to reject this match later in loop

    for check all position within current match length

    compute current value or temp

    if current position within match is equal to one increase temp by one - add more priority to literal + match sequence

    temp = (j + (j ==1) + getMatch(i + j);

    As a result, the max value, is not the sum of match lengths as with original flexible parsing, it's some kind of weights...

    and if temp > max value, replace:
    max value = temp
    final match length = j; // optimize match length (cutdown, in favor to get the better one at next step)

    end

    I have an idea to improve the max value computation - probably we can compute the max value as some kind of ratio() function - i.e. bytes saved vs. bits needed... However, I already broke my head and this generalized weight emulation scheme seems to be will be the last and final one...


  24. #24
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    also QUAD uses "post processing" - i.e. if we cutdown match at current step, we will check the lower indexes for the same match. - i.e. we will replace an index of current cutdowned match to lower number.


  25. #25
    Member
    Join Date
    Mar 2007
    Posts
    34
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by encode
    also QUAD uses "post processing" - i.e. if we cutdown match at current step, we will check the lower indexes for the same match. - i.e. we will replace an index of current cutdowned match to lower number.
    Actually all this matches are checked during initial match search (at current position). If you keep this information, you can use optimal indexes of each cutdown match during parsing (for weighting/pricing) and post processing is not needed.

  26. #26
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    I know, I know. But at some point we must make the init match search as simple as it possible, since this search is also used with normal mode.

    My latest tests shown:
    1. Actually, at each step we have not so many matches available - I mean at each match index theoretically we can find the match (64 matches), however, in practive we usually can find from 1 to 3 matches in average.

    2. I tried to implement some kind of recursive flexible parsing:
    maxvalue = matchlen + getoptimum(i + matchlen)
    // ...
    temp = j + getoptimum(i + j)

    e.g. getoptimum() performs one step lookahead, as with original parsing

    This scheme is dead slow and gives no improvement, however with some further testing and tuning this may give some compression improvement.

    Probably, current scheme is pretty close to the optimal parsing. And it is possible that any true weighing scheme will give no serious compression improvement, or even give no improvement.


  27. #27
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Looks like QUAD has much faster decompression speed than ALZ, and about the same speed as ROLZ2.

    http://uclc.info/decompression_speed.htm

    Not bad...

    However, at Large Text Benchmark, QUAD has about the same speed as ALZ.

    Again not bad, taking into account that QUAD has PPM with Full Exclusion.

  28. #28
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Quote Originally Posted by Uwe Herklotz
    Actually all this matches are checked during initial match search (at current position). If you keep this information, you can use optimal indexes of each cutdown match during parsing (for weighting/pricing) and post processing is not needed.
    Okay, I implement that - we remember all processed matches, and at each match cut down were trying to find the optimal index.

    So, Ill try to make some kind of weighing for all found mathes. Until now, encoder "know" only current or best match, with new scheme we can control all good matches (with small index and/or large lengths).

    To be continued...

    P.S.
    Im working really hard on the new version - like with no other version of QUAD...


  29. #29
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Quote Originally Posted by encode
    Im working really hard on the new version - like with no other version of QUAD...
    I expect that the next version will be something really special!

  30. #30
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Quote Originally Posted by LovePimple
    I expect that the next version will be something really special!
    At least for me it is!

    Okay, check out some testing results for current modification of QUAD 1.11:

    SFC
    A10.jpg: 853,520 bytes
    acrord32.exe: 1,492,973 bytes
    english.dic: 828,018 bytes
    FlashMX.pdf: 3,823,899 bytes
    fp.log: 619,701 bytes
    mso97.dll: 1,906,649 bytes
    ohs.doc: 842,299 bytes
    rafale.bmp: 1,003,856 bytes
    vcfiu.hlp: 680,623 bytes
    world95.txt: 595,545 bytes

    Total: 12,647,083 bytes
    Large Text
    ENWIK8: 29,110,519 bytes
    ENWIK9: 256,145,858 bytes

Page 1 of 2 12 LastLast

Similar Threads

  1. lzpm 0.03 overview
    By encode in forum Forum Archive
    Replies: 3
    Last Post: 28th April 2007, 22:16
  2. lzpm overview
    By encode in forum Forum Archive
    Replies: 4
    Last Post: 14th April 2007, 23:30
  3. QUAD 1.10 overview
    By encode in forum Forum Archive
    Replies: 10
    Last Post: 19th March 2007, 15:21
  4. QUAD v1.08 overview
    By encode in forum Forum Archive
    Replies: 40
    Last Post: 12th March 2007, 02:15
  5. Quad 1.05a overview
    By encode in forum Forum Archive
    Replies: 47
    Last Post: 21st February 2007, 21:16

Posting Permissions

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