# Thread: Future-LZ as last-step compression scheme

1. ## Future-LZ as last-step compression scheme

Maybe I don't remember correctly, but Bulat said something like future-lz is equivalent to normal-lz. I am not very convinced. With normal-lz we need to only tell about incoming literal/ literal sequence length or about incoming repetition. After that we move past that literal/ literals/ match and continue. With future-lz we need to tell about repetitions of recent subsequence in further places in the stream or about literals. That would be pretty equivalent to normal-lz overhead-wise, but with future-lz we then need to explicitly say how much bytes we need to skip every time.

Eg, with string "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES" with normal-lz we can output:
(0, "SIX.M"), (4, 2), (0, "ED.P"), and so on
With future-lz we need to say how much we have to skip, eg:
(0, "SIX", 3), (18, 3, 0) - (future reference to beginning of "SIXTY"), (2, 2, 0) - (future reference to "IX" in "MIXED"), and so on

What do you think about that? With future-lz we have disadvantage of having to tell how much we have to skip over every time, but we have an advantage, because we can use delta coding for offsets, eg instead of outputting (a1, b1, 0), (a2, b2, 0), (a3, b3, 0) and so on we can then output (a1, b1, 0), (a2 - a1, b2, 0), (a3 - a2, b3, 0) and so on.

2. The "delta" advantage doesn't work, since normal-LZ already does it "by default" (since the 3rd occurrence of a sequence will likely point to the 2nd occurrence instead of the 1st one).

I guess an advantage of future-LZ is that you don't need to take into account in the distance offset the bytes that are already written.
This has the potential to reduce the distance more and more as the file get filled.
But that requires to maintain a kind of "fill map", which probably costs some memory and CPU cycles to maintain.

3. The "delta" advantage doesn't work, since normal-LZ already does it "by default" (since the 3rd occurrence of a sequence will likely point to the 2nd occurrence instead of the 1st one).
Thanks for pointing it out. I missed that trivial point.

I guess an advantage of future-LZ is that you don't need to take into account in the distance offset the bytes that are already written.
This has the potential to reduce the distance more and more as the file get filled.
With normal-lz first matches have small offsets, so it's done "by default" (analogously to your description )

It now seems to me that future-lz has no advantages to normal-lz. With normal-lz we can decode the offsets without decoding the data (provided that either we have decoupled matches from literals or if there will be efficient way to skip literals) and then use them to prefetch data. That would be analogous to write buffer in future-lz. With very big windows, say at least five times bigger than CPU cache size such prefetching scheme maybe can lead to improved performance.

4. With normal-lz first matches have small offsets, so it's done "by default" (analogously to your description )
Not really.
Let's give an example.

Suppose we have the following sequence

ABC 12 ABC X 12

Normal LZ :
Lit 5 (ABC12)
Copy3 @ Off 5 (ABC)
Lit 1 (X)
Copy2 @ Off 6 (12)

Future LZ :
LitCopy 3 (ABC) @ Off 2
LitCopy 2 (12) @ Off 1
Lit 1 (X)
(Automatically move cursor to end of stream since it gets contiguous )

Notice that the second "future offset" is shorter : we don't have to take into account the second ABC because it's already written. So only 1 position separate us from the copy destination (X).

5. Okay. But that's a little saving. We still need to transmit the number of bytes to skip almost every time.

Consider an example:

ABCDEF 1 GHIJKL 2 ABCDEFGHIJKL 3 <lots of thing here> 4 DEFGHI

It would be logical to transmit DEFGHI as one match.

6. That's correct. For overlapping sequences, there is a need to tell where they start.
So skip values are necessary.
Taking your example, it becomes

ABCDEF 1 GHIJKL 2 ABCDEFGHIJKL 3 X 4 DEFGHI

LitCopy 6 (ABCDEF) @ Off 8
Lit 1 (1)
LitCopy 6 (GHIJKL) @ Off 1
Lit 1 (2)
(Automatically move cursor to end of ABCDEFGHIJKL, since it gets contiguous )
Copy 6 @ Skip 3 @ Off 3 (DEFGHI)
Lit 3 (3X4)
(Automatically move cursor to end of stream since it gets contiguous )

So yes, each time we "jump forward", there is a need to provide a "skip" value to locate the start of the copy operation.
This effectively may nullify the "short offset" advantage of future-lz.

At least, that's were i dropped my experiment with this method some time ago.

But i think we are no longer talking about what Bulat implemented into SuperRep...

7. Afaik,

1. There're no extra counts. You just have to store the match distance/length before (or after) match data,
which is the same as normal LZ, and, in fact, can be further improved by excluding known matches from distances
(similar to Distance Coding from BWT postcoders).

2. Its not a speed optimization.

3. The main point is the fact that with forward references you only need to keep in memory the actual match data,
instead of the whole window, so the effective window size can be many times larger than in a normal LZ77.

8. But i think we are no longer talking about what Bulat implemented into SuperRep...
I don't know, but I'm interested in how Bulat has implemented future-lz

There're no extra counts.
Then how would you handle my case?

Its not a speed optimization.
It could be. Modern CPU can do many writes simultaneously and asynchronously to random memory locations. That's not the case with random memory reads, at least without prefetching.

9. hm maybe i misunderstand something but futurelz is a kind of lz78 right?

10. No. LZ78 fills in a dictionary, irrespective of what will be done with it later on.
Future LZ tells exactly what will be copied and where.

11. Here's an implementation: http://codepad.org/YP0bC1wc
Code:
```SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
SI<15;2>X<2;2>.M<4;2>E<33;2>D.PIE<12;6>S.<2;3>FTXTY.DUST.BOS```

> don't know, but I'm interested in how Bulat has implemented future-lz

http://svn.freearc.org/freearc/trunk/Compression/SREP/

>> There're no extra counts.
> Then how would you handle my case?

Well, extra offsets are necessary if there's really a need to reference
parts of previously copied strings.
But its not a fact, as my implementation kinda demonstrates.

Also its not a problem to either add these offsets, or use some other workaround,
for example, instead of removing matched strings, we can subtract them
(thus a usual match would be replaced with a string of zeroes of the same length),
and wrap it all with some kind of zero-RLE.
As a side effect this would also allow for fuzzy matches, like what bsdiff uses
(and its very helpful for exes)

> It could be. Modern CPU can do many writes simultaneously and
> asynchronously to random memory locations. That's not the case with
> random memory reads, at least without prefetching.

I don't see how "my" kind of code can be decoded asynchronously.

Also I guess it can be faster due to the same "window compression" effect.

12. Your code seems to be broken. It produces broken output on my second case: http://codepad.org/uYeOAlRD

I don't see how "my" kind of code can be decoded asynchronously.
I meant that if eg in some point in code there are a few independent writes at random locations then modern CPUs can do those writes asynchronously.

13. > Your code seems to be broken

Its just a quick hack. In this case it likely loses some of multiple marks at the same pos (different length, same end offset).
It can be fixed, but would require more complicated data structures, do you really need that?

> independent writes at random locations

Ok, now I understand, but storing full distances there is kinda redundant.
Instead, it can be written as a number of match/literal spans or something like that.

Also that kind of optimization ("independent writes") is probably also applicable to the normal LZ77.
We can decode the LZ token array first, then copy the matches at multiple points in the token array.
I mean, source and destination offsets for matches can be computed without actually decoding matches, right?..

14. Well, overlapping matches are still an issue for "multiple independant writes", whatever the method (future or normal LZ)

15. with flz, we know that destinations can't overlap. we just need to ensure that sources are ready. it seems a bit easier

16. In SuperRep implementation, this is correct, since i far as i understand, it's all about keeping into memory only the data blocks which will be useful for later copy, and data blocks have fixed sizes and fixed boundaries, so they cannot overlap.

Now, in a kind of "generic" future LZ, it doesn't hold true, since there are some possible overlap.

Consider the following sequence :
00000000

It's an obvious RLE sequence. How will future LZ deal with it ?

Well, one possible sequence (but not the best) is :
Lit 1 (0)
Copy 1 @ skip 0 @ offset 0 (0)
Copy 2 @ skip 0 @ offset 0 (00)
Copy 4 @ skip 0 @ offset 0 (0000)

We have avoided the "overlapping issue" by only relying on already written data, but it results in many "copy" orders. Moreover, i don't see here any way to do some "multiple independant write", since each write depends on the previous one being completed.

Normal-LZ would be much more straighforward :
Lit 1 (0)
Copy 7 @ offset 1 (0000000) <== Overlapping copy

Emulating this behavior might be possible with Future LZ, at the expense of extending the syntax, such as :
Literal 1 (0)
Copy 7 @ skip -6 @ offset 0

Now, it requires the capability to write negative skips, which is bound to cost quite some bandwidth for the many many situations where it's not necessary. But on the other hand, a single copy operation is enough, which will save some bits for overlapping copy situations. Is it a net gain ? Well that's not so sure, i wouldn't bet that.

17. you misunderstood srep. it has arbitrary len/dist pairs with only limit: len>=L

flz is implemented simply as usual lz that gathers ALL matches across entire file and then sorts them by src (while naturally they are sorted by dst). then srep saves compressed data in the usual lzss way, only placing matches in the place where their src lives, rather than dst

so aaaaa would be compressed as match(4,+1)+"a". on decompression, matches are temporarily stored in ordered heap and executed when their dst is reached

what i mean is that we can gather matches with src in previous blocks and dst in next blocks and then run them all in parallel with decoding of current block

18. So SREP cannot compose matches from parts of previous matches? Without skip values that would be impossible.

Consider the example (spaces are for better readability only and X is a very long incompressible sequence): ABCDEF 1 GHIJKL 2 ABCDEFGHIJKL 3 X 4 DEFGHI
With usual LZ coders we will end up with:
Literal <ABCDEF 1 GHIJKL 2>
Match <14, 6>
Match <13, 6>
Literal <3 X 4>
Match <11 + length(X), 6>

How would you transform that to future-lz without increasing the number of matches and without adding skip values?

matches are temporarily stored in ordered heap
Match is a triple (offset, length, data) here?

19. oh, it seems that it's me who forgot srep internals

srep just stores list of all matches, sorted by src, each in the form (lit_len==skip,length,offset), where dst[i+1]=dst[i]+lit_len. and separate "composed literal" that stores all the literal data in the block. on decompression, each match transformed into (src,dst,length) triple and placed in the heap ordered by dst. then going through the heap, i find "holes" not filled by any match and copy missing data from the "composed literal"

since srep even in normal-lz mode uses lz77 style encoding (literal+match+literal+match+...), it has the same compression format: (skip,length,offset) for each match plus combined literal (where "skip" denotes number of bytes to copy from combined literal aka literal length)

so going from normal-lz to future-lz doesn't change anything in srep, only matches are stored in another order

ADDED: actually for normal-lz dst[i+1]=dst[i]+length[i]+lit_len, and for future-lz it's the same (look at decompress and decompress_reversed_LZ)

#### Posting Permissions

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