QUAD 1.11 is here!

[Bulat Ziganshin]

>Yes, but remember QUAD is not LZ77 - it has a different behavior - for example QUAD outputs much more literals than matches compared to the base-line LZ77. Thus tricks which work with LZ77 will not work with QUAD!

? ?????? ? ???, ??? ? deflate lazy matching ????????? ???????? ? ?? ?????? ??????????? ?? ????? ??? ??

[Bulat Ziganshin]

about OP and wieghtening - i think that i'm understand how it is implemented in cabarc (due to Igor's explanations). the only problem with quad is that it uses PPM encoding, so price of each code depends on previous codes and we don't know which codes will be output. one possible solution is to use some average price

what you need to know about OP? if you need explanation of Igor's manuscript, i can help you

[Bulat Ziganshin]

one more idea that breaks bw compatibility but may significantly increase compression - insert in tab strings at beginning and end of match. it is how this is done in my own compressor:

#if 0
p += len;
#else
h = hash(value(p+1)), HTable[h] = p+1;
h = hash(value(p+2)), HTable[h] = p+2;
p += len;
h = hash(value(p-1)), HTable[h] = p-1;
#endif

variant commented out by #if 0 is like your scheme while second variant is one actually used now by me. for my simple compresor this change made substantial improvement, about 5 or 10%

[encode]

what you need to know about OP? if you need explanation of Igors manuscript, i can help you

Actually, I guess I understand the whole idea. I tried to adopt this to the Flexible Parsing - i.e. choose the variant with which we jump to a longest distance and if we have a few variants to achieve such distance estimate the price for each variant and choose the cheapest one. This not really works... However, LZMA computes and estimates cost for many steps ahead. Original ROLZ has say 4096 bytes lookahead. For example we get all matches and prices for each position, after that we search for cheapest way to get to each position. After, we just encode our choices. Such thing is also possible with QUAD. We can hold, say 1024 bytes lookahead and find the best matches and prices for each position. Again from end to start we search for shortest path but in this case we encode just first match or literal (first element), at next step we do the same thing. This will kill the compression speed. However, currently, the compression speed with Max mode doesnt matter - were trying to get the max compression at ANY cost! I think, Im pretty close to this, but looks like something goes wrong...

The very good description of the basic idea can be found here:
http://www.cbloom.com/algs/dictionary.html

[Bulat Ziganshin]

about e8/e9 - you are right, current code should be better because ICL should "specialize" each call to performing encoding or decoding procedure. but current code isn't optimal in terms of compression ratio - it doesn't convert calls to positions in previous buffer

[encode]

The most EXE files are smaller than 16 MB in size. However, at compressing the TARred EXEs this can make a small difference... Anyway, like I said I wont break compatibility, and I'll keep attention on other things...

[Bulat Ziganshin]

i think that using small buffer may kill the entire idea. let's start to try with large window and then try to make it smaller. lzma uses somewhat about 100kb, afair

then, we go through this buffer in direct order, check all matches at each position and find that closest match at position p with a length len has index that we will store to best[p][len]. knowing match length and index we can estimate it's price in bits

[Bulat Ziganshin]

btw, e8 hurts compression of obj/lib files because they already contains relative offsets (which are patched at linking time)

[Bulat Ziganshin]

.. knowing that best price (number of bits to encode data from start of block to this pos) of our current position P is Price and having match with some Len and Index we can propose price Price+match_weight(Len,Index) for position P+Len. if this price is better than one already stored in its price slot, this slot would be updated with our "offer"

the only problem is that i don't see any use of backward scanning which i believe is essential part of OP. where is my fault?

[Bulat Ziganshin]

... of course we should also make offers to any intermediate positions. say, if we found match with len=6 after match with len=3 we should also offer reduced variants of this match to P+4..P+5 positions - it may be better than their current offers and these positions, in turn, may be a start for some long match that will win

at the last end, we stop after parsing some amount of data and go into opposite direction - got the best deal for the last position (say, 10000), say it's string with start 9997 and length 3. then we got best deal for 9997 position, say it will be string starting at pos 9990. and so on... literals are considered as matches with length=1 and they compete with regular matches for the next position (i.e. literal at pos P should be offered as one more possible encoding for position P+1)

what is most important with this scheme is that we have best parse (i.e., best price) for each position before we start to make "offers" for positions reachable from it. so we can use this knowledge to find *exact* price of each match/literal - context is known, so PPM is applicable to model the price. the only problem is that PPM model will not be updated with fresh data and this means that parsig in small blocks would be better in this respect

[Christian]

.. knowing that best price (number of bits to encode data from start of block to this pos) of our current position P is Price and having match with some Len and Index we can propose price Price+match_weight(Len,Index) for position P+Len. if this price is better than one already stored in its price slot, this slot would be updated with our "offer"

the only problem is that i dont see any use of backward scanning which i believe is essential part of OP. where is my fault?

The problem is, that youre not describing OP but a greedy algorithm.

It should be something like this:
1) for every pos. i+1...n-1 a optimal path to the end of the buffer is known
2) find optimal path from i
3) decrease i and goto 1

PS.: But OP can be done forward, too.

[Bulat Ziganshin]

i've now reread Igor's description (in english translation ) and for me it seems that i just repeated his algorithm - i.e. it first goes into direct order, searches all matches at each pos and offer price of current pos plus price of encoding string (Offset,Len) to the price of CurPos+Len position. after all, it goes into opposite direction and just "trace" the cheapest way. just look at this in Igor's algorithm:

a) For all elements set Price to Infinity

b) for(int i=0; i < Big_Value; i++)
...
c) Now, scan a[] from end, collect and code optimal match/literal sequences

where most part of algorithm is described in part b, i.e. direct scan

[Bulat Ziganshin]

It should be something like this:
1) for every pos. i+1...n-1 a optimal path to the end of the buffer is known
2) find optimal path from i
3) decrease i and goto 1

this description is from Malcolms explanations and it seems that he just omitted explanations of part b). otherwise, how we can find optimal path from pos i? by finding all possible matches at this pos and selecting smallest sum among Price(Match)+Price(Position it reaches). but because we cant (i think) find matches while going in opposite direction, we should first fill the table with all possible matches for each position in the block we consider. it will require more memory than Igors agorithm (read: this table may not fit in CPU cache) and i dont see why this may be better. also this will not allow us to calculate exact price of each match (because we dont know its history) that is also very important to selectt quasi-optimal encoding. and what the benefits?

[Christian]

.. knowing that best price (number of bits to encode data from start of block to this pos) of our current position P is Price and having match with some Len and Index we can propose price Price+match_weight(Len,Index) for position P+Len. if this price is better than one already stored in its price slot, this slot would be updated with our "offer"

Additionally, you need to store how you came here (index,len). If you only store the price youre not able to trace backwards - therefore, no OP.

after all, it goes into opposite direction and just "trace" the cheapest way.

See above.

I mean OP in theory is very easy. The problem is the implementation for a specific algorithm. You should just give Ilia more time to experiment - or try to modify QUAD yourself and share the code with Ilia.

Im off to bed. Good night everyone!

[Bulat Ziganshin]

Additionally, you need to store how you came here (index,len). If you only store the price youre not able to trace backwards - therefore, no OP.

yes, of course. you can see this structure in Igors algorithm. backtracing is very simple algorithm, it is why Igor described it in just one line

I mean OP in theory is very easy. The problem is the implementation for a specific algorithm.

what concrete problems with algorithm i described? i see the only one - we cant update statistics while doing scanning so it will be a bit odd and therefore prices a bit inexact

[Christian]

but because we cant (i think) find matches while going in opposite direction

Why shouldnt we be able to find matches when going backwards?

it will require more memory than Igors agorithm (read: this table may not fit in CPU cache) and i dont see why this may be better.

Its not better or anything. Its just a textbook-approach for OP I read a couple of years ago (not for data compression). Your description was just missing the back-tracing - which is very important for OP.

what concrete problems with algorithm i described? i see the only one - we cant update statistics so it will be a bit odd and therefore prices a bit inexact

This is the problem. Dont you think Ilia knows all this, too?
With the PPM Coder its not that easy. This takes some time and experimenting. If it would be that easy, why dont you just spend half an hour of your time and implement this into QUAD.
Im just fooling around, but I hope you get my point.

[Bulat Ziganshin]

Your description was just missing the back-tracing - which is very important for OP.

you just skipped this part: "at the last end, we stop after parsing some amount of data and go into opposite direction"

>Why shouldnt we be able to find matches when going backwards?

because tables used to find matches will include unneded information. how you will fill them?

[Christian]

because tables used to find matches will include unneded information. how you will fill them?

I dont understand the problem. Just create a table with matches before you start the backward approach. This isnt very efficient but it works.

the only problem is that i dont see any use of backward scanning

And this is the reason why I posted this classical approach.
I never said that this is the better method (I hinted that OP parsing can be done forward, too).

you just skipped this part: "at the last end, we stop after parsing some amount of data and go into opposite direction"

When I loaded the page in my browsers tab your second post wasnt visible. This is why my reply only refered to your first post in which back tracing was missing. After that I must have missed your second post (from 1:00). Im really sorry for that.

[encode]

The main idea - we try to get the shortest path with defined block with the frozen statistics - i.e. the table with offsets and PPM statistics stays untouched. The Flexible Parsing provides the optimality as much as backwards parsing, however FP works slower than later and optimality is true for static encodings only - i.e. such scheme by itself do not copes with adaptive encodings - and this is the key for success.

I think I must think more deeply about this problem far away from the compiler...

In addition, before that I'll release a few test versions with some speed improvements...

[Bulat Ziganshin]

I dont understand the problem. Just create a table with matches before you start the backward approach. This isnt very efficient but it works.

this just dont have much meaning. and probably will require 3rd scan

The main idea - we try to get the shortest path with defined block with the frozen statistics

i dont think that statistics are changed so fast that using fixed stats for pricing will be problematic. moreover, 7zip and cabarc uses stats from previous huffman block - i.e. tens of kilobytes ago and still survives

The Flexible Parsing provides the optimality as much as backwards parsing

if FP is that you currently use in max mode then it is worser than OP due to two reasins - it doesnt use pricing nor scans large block. it seems that you undervalue importance of later. just imagine, for example, a 10kb block which has optimal parsing of 2222 strings. if we will parse a 1kb block instead, we will need to use 223 phrases, i.e. whole 10kb will be parsed with a 8 phrases more than optimum. if we will use 100 byte block, the total loss will be 80 phrases and so on. when yoou look just one phrase ahead, you just dont have enough information to select best parsing. the only way is to get backward starting from far enough position

however FP works slower than later and optimality is true for static encodings only - i.e. such scheme by itself do not copes with adaptive encodings - and this is the key for success.

with current FP you probably optimize only number of phrases and its hard to use prices here - how can you decide what is better - reach position 24 with a price 6.47 bits or position 12 with a price 3.66 bits? you need to work with larger context in order to have enough information for decision

[Christian]

this just dont have much meaning. and probably will require 3rd scan

Why doesnt this have much meaning. As already stated its not very efficient, but it works! Dont you agree?

[Uwe Herklotz]

Without reading the complete thread, just some general statements.

What do we need to perform REAL optimal parsing on certain look-ahead block:
A) we need ALL possible matches for each block position
B) we need the REAL coding costs for literal/matches at any block position

This allows to find local optimum for the look-ahead block. Extending the block to a whole file would allow to find the global optimum over the whole file. Anyway, it's computationally too expensive to calulcate REAL coding costs over the look-ahead block (at least with an adpative coding scheme) or to deal with ALL possible matches. For practical purpose two assumptions are reasonable:
1) a nearer match (smaller distance/index) is assumed to be cheaper
2) the literal/match stats are assummed to be fix over the look-ahead block

Assumption 1) is usually supported by the used coding scheme, however, it's possible that this fails. Assumption 2) means that statistics known at begin of look-ahead are used for any costs calculation over the whole block, i.e. we have FIXED coding costs not depending on the optimal parsing choices. This makes optimal parsing for adaptive coding scheme as easy as for any static one. But obviously these assumptions will lead to NEAR-optimal parsing.

So let's re-phrase,
what do we need to perform NEAR-optimal parsing on certain look-ahead block:
A) we need for each block pos. the longest match + nearest one of any shorter length
B) we need the FIXED coding costs for literal/matches at any block position

The problem with Ilia's ROLZ implementation is that A) cannot be fulfilled correctly, because the available matches (and their indexes) depend on choices made during near-optimal parsing. Reason is the limitation of ROLZ index table updates - it's done only at match/literal boundaries but not within matches. This makes near-optimal parsing quite tricky IMO.

[Christian]

Very interesting read and helpful post, Uwe!

The problem with Ilias ROLZ implementation is that A) cannot be fulfilled correctly, because the available matches (and their indexes) depend on choices made during near-optimal parsing. Reason is the limitation of ROLZ index table updates - its done only at match/literal boundaries but not within matches. This makes near-optimal parsing quite tricky IMO.

I totally agree. This hits the nail on the head.

[Bulat Ziganshin]

i agree too i forget about this because my experience is mainly in pure lz77 area

anyway, this scheme works but breaks backward compatinility and make decompression slower. it is up to Ilia whether he want to try it

[encode]

btw, e8 hurts compression of obj/lib files because they already contains relative offsets (which are patched at linking time)

By the way, QUAD uses e8/e9 transformer similar to CABARC - i.e. it checks for valid offset... So it can efficiently drop the fake relative offsets...

[Bulat Ziganshin]

not exactly - cabarc does this for whole file. 7z has two modes - either to do it using actual file size (and position of current block inside file) or translate only -16m..16m offsets independent of file size. i use the last scheme