Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #1502 > unrolled thread

Re: Employing a set of data files guaranteed to be available at the time of decompression

Back to article view | Back to comp.compression

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Employing a set of data files guaranteed to be available at the time of decompression David <davidcary2@gmail.com> - 2012-09-03 19:03 -0700
    Re: Employing a set of data files guaranteed to be available at the time of decompression Industrial One <industrial_one@hotmail.com> - 2012-09-09 09:23 -0700
    Re: Employing a set of data files guaranteed to be available at the time of decompression Jim Leonard <MobyGamer@gmail.com> - 2012-09-18 14:25 -0700
      Re: Employing a set of data files guaranteed to be available at the time of decompression Willem <willem@turtle.stack.nl> - 2012-09-19 08:54 +0000

#1502 — Re: Employing a set of data files guaranteed to be available at the time of decompression

On Thursday, July 12, 2007 11:51:13 PM UTC-5, Reality Handbook wrote:
...
> But what if both the compressor and decompressor had read-only access
> to a large archive of data files that are *known* to be in the target
> domain.  So let's say for example you are trying to compress EXE
> files...you would just round up a bunch of common EXE files and number
> them from 1 to 10000 and stick them on a DVD-R.  If both the
> decompressor and compressor were guaranteed to have that particular
> DVD-R on hand, are there any generalized algorithms for employing this
> added data to increase the compression ratio for future inputs?
...
> Anyone know of prior work in this area?  Does this concept have an
> existing name?

Yes, I think the most general name for this kind of algorithm is "data differencing"
http://en.wikipedia.org/wiki/data_differencing

You might also be interested in "data deduplication" and "shared dictionary compression" and the "rsync" algorithm.
http://en.wikipedia.org/wiki/Shared_Dictionary_Compression_Over_HTTP

As Josiah Carlson pointed out,

> Very few compression algorithms have really substantial sliding windows.

In particular, gzip has a sliding window of 32KB, and bzip2 has a sliding window of 900KB.

However, there are a few algorithms with a much larger window ("large window compression").

Here is some prior work in this area:

* rzip has a 900 MB window (1000 times larger than bzip2) http://en.wikipedia.org/wiki/Rzip
* Lrzip and SuperREP has "infinite" window (not limited by available RAM)
* Information Zipping Optimizer (izo) also has a window not limited by available RAM https://www.usenix.org/conference/lisa-08/izo-applications-large-window-compression-virtual-machine-management
* xdelta http://en.wikipedia.org/wiki/xdelta

[toc] | [next] | [standalone]

#1505

On Tuesday, September 4, 2012 2:03:14 AM UTC, David wrote:
> On Thursday, July 12, 2007 11:51:13 PM UTC-5, Reality Handbook wrote:
> 
> ...
> 
> > But what if both the compressor and decompressor had read-only access
> 
> > to a large archive of data files that are *known* to be in the target
> 
> > domain.  So let's say for example you are trying to compress EXE
> 
> > files...you would just round up a bunch of common EXE files and number
> 
> > them from 1 to 10000 and stick them on a DVD-R.  If both the
> 
> > decompressor and compressor were guaranteed to have that particular
> 
> > DVD-R on hand, are there any generalized algorithms for employing this
> 
> > added data to increase the compression ratio for future inputs?
> 
> ...
> 
> > Anyone know of prior work in this area?  Does this concept have an
> 
> > existing name?
> 
> 
> 
> Yes, I think the most general name for this kind of algorithm is "data differencing"
> 
> http://en.wikipedia.org/wiki/data_differencing
> 
> 
> 
> You might also be interested in "data deduplication" and "shared dictionary compression" and the "rsync" algorithm.
> 
> http://en.wikipedia.org/wiki/Shared_Dictionary_Compression_Over_HTTP
> 
> 
> 
> As Josiah Carlson pointed out,
> 
> 
> 
> > Very few compression algorithms have really substantial sliding windows.
> 
> 
> 
> In particular, gzip has a sliding window of 32KB, and bzip2 has a sliding window of 900KB.
> 
> 
> 
> However, there are a few algorithms with a much larger window ("large window compression").
> 
> 
> 
> Here is some prior work in this area:
> 
> 
> 
> * rzip has a 900 MB window (1000 times larger than bzip2) http://en.wikipedia.org/wiki/Rzip
> 
> * Lrzip and SuperREP has "infinite" window (not limited by available RAM)
> 
> * Information Zipping Optimizer (izo) also has a window not limited by available RAM https://www.usenix.org/conference/lisa-08/izo-applications-large-window-compression-virtual-machine-management
> 
> * xdelta http://en.wikipedia.org/wiki/xdelta

How did you reply to a 5-year-old thread?

[toc] | [prev] | [next] | [standalone]

#1517

On Monday, September 3, 2012 9:03:14 PM UTC-5, David wrote:
> In particular, gzip has a sliding window of 32KB, and bzip2 has a sliding window of 900KB.

To clarify, bzip2 has a 900KB block size, not a 900KB sliding window.  Each block is independent, which was by design as the author wanted file damage to be limited to the area of damage, and not bork everything from that point forward.

[toc] | [prev] | [next] | [standalone]

#1518

Jim Leonard wrote:
) On Monday, September 3, 2012 9:03:14 PM UTC-5, David wrote:
)> In particular, gzip has a sliding window of 32KB, and bzip2 has a sliding window of 900KB.
)
) To clarify, bzip2 has a 900KB block size, not a 900KB sliding window.
) Each block is independent, which was by design as the author wanted file
) damage to be limited to the area of damage, and not bork everything from
) that point forward.

The fact that each block is independent is inherent in the underlying
algorithm (block-sorting).

The choice for 900KB was a bit arbitrary, it seems.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web