1
$\begingroup$

Let's take the zip compression for example, from what scraps I can gather on the Internet, the 2 major simplified ways it works is by looking for arrangements of bits that repeat throughout the file, and by compressing certain bit orders.

So for example, we have 010111111111110101

A zip file would look something like:

x = 0101

x|repeat(1,8)|x

So the zip compression creates its own table of arrangements that it finds.

But, is there anything that already uses a predetermined table? For example you'd have a table like:

x = 010101010101010101010110010101010101010101010101...
y = 10101...
... 

And then I'd download a file that follows this compression table, without having to download the table because you already have it.

So my question is, is this method used anywhere, and why or why not?

$\endgroup$
1
  • 1
    $\begingroup$ "looking for arrangements of bits that repeat throughout the file, and by compressing certain bit orders" -- that is very vague, and probably describes every (lossless) compression method. Note that there are several versions of Lempel-Ziv compression -- at least LZ77, LZ78 and LZW -- and you don't say which you want to talk about. (Fixed dictionaries make no sense at all with LZ77, for instance.) $\endgroup$
    – Raphael
    Jun 18, 2015 at 16:10

1 Answer 1

2
$\begingroup$

The big advantage of Lempel-Ziv-style compression is that

  • it creates its own dictionary on the fly and
  • tailors it to the data. Therefore, they are
  • general-purpose compression algorithms which
  • can be used without having to keep dictionaries in sync; all you need for decoding is the encoded file and the algorithm.

If you fix a dictionary, this is going to perform well for some inputs. For instance, you can order all English words by frequency in some corpus, number them and store a sequence of these numbers instead of the words themselves. This will then work very well for English texts similar to your corpus, worse for other texts, and not well at all for weather data or images.

Note that LZ-style compression is used in popular formats such as (g)zip, PNG and GIF.

FLAC is one noteable format that uses something different, namely linear predictors. In a certain sense, you can view this as a fixed (though conceptually infinite) dictionary; the method estimates parameters of a certain model and represents bits of data by these parameters (plus some error information). This works well because the model fits the kind of data (apparently) very well, and the representatives are significantly smaller than the data itself. However, the decoder only knows the model; there is no fixed set of parameters everybody uses. So I don't think this fits your idea, either.

$\endgroup$
1
  • $\begingroup$ It would be interesting to see by how much suitable LZ variants can be improved for structured text (HTML, Java code, ...) by seeding the dictionary with a data-specific dictionary (popular tags, keywords, ...). $\endgroup$
    – Raphael
    Jun 18, 2015 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.