Results 1 to 19 of 19

Thread: Future-LZ as last-step compression scheme

  1. #1
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts

    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. #2
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    863
    Thanks
    461
    Thanked 257 Times in 105 Posts
    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. #3
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    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. #4
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    863
    Thanks
    461
    Thanked 257 Times in 105 Posts
    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).
    Last edited by Cyan; 2nd December 2011 at 03:20.

  5. #5
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    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. #6
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    863
    Thanks
    461
    Thanked 257 Times in 105 Posts
    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...
    Last edited by Cyan; 2nd December 2011 at 03:20.

  7. #7
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,377
    Thanks
    215
    Thanked 1,024 Times in 545 Posts
    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).

    Example: abracadabra

    <match:len=4,dist=7-4>abra<literals:len=3>cad

    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. #8
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    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.
    Last edited by Piotr Tarsa; 2nd December 2011 at 03:19.

  9. #9
    Member
    Join Date
    Jun 2008
    Location
    G
    Posts
    372
    Thanks
    26
    Thanked 22 Times in 15 Posts
    hm maybe i misunderstand something but futurelz is a kind of lz78 right?

  10. #10
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    863
    Thanks
    461
    Thanked 257 Times in 105 Posts
    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. #11
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,377
    Thanks
    215
    Thanked 1,024 Times in 545 Posts
    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. #12
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    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. #13
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,377
    Thanks
    215
    Thanked 1,024 Times in 545 Posts
    > 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. #14
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    863
    Thanks
    461
    Thanked 257 Times in 105 Posts
    Well, overlapping matches are still an issue for "multiple independant writes", whatever the method (future or normal LZ)

  15. #15
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,507
    Thanks
    742
    Thanked 665 Times in 359 Posts
    with flz, we know that destinations can't overlap. we just need to ensure that sources are ready. it seems a bit easier

  16. #16
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    863
    Thanks
    461
    Thanked 257 Times in 105 Posts
    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. #17
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,507
    Thanks
    742
    Thanked 665 Times in 359 Posts
    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
    Last edited by Bulat Ziganshin; 2nd December 2011 at 16:21.

  18. #18
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    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. #19
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,507
    Thanks
    742
    Thanked 665 Times in 359 Posts
    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)
    Last edited by Bulat Ziganshin; 3rd December 2011 at 12:54.

Similar Threads

  1. BCM's future
    By encode in forum Data Compression
    Replies: 17
    Last Post: 9th August 2009, 02:00
  2. Sugestion compression scheme
    By KammutierSpule in forum Data Compression
    Replies: 11
    Last Post: 2nd February 2009, 13:15
  3. Future Bandwidth.
    By Tribune in forum The Off-Topic Lounge
    Replies: 9
    Last Post: 10th October 2008, 23:56
  4. LZPM's future
    By encode in forum Forum Archive
    Replies: 129
    Last Post: 3rd March 2008, 20:23

Posting Permissions

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