Re: Pacbyte data compression patent


boo@xxxxxxxxxxxxxxxx wrote:
Matt Mahoney wrote:
This is yet another patent on random data compression.

It claims to work like this: divide the input into 300 byte segments.
Assume that each of the 256 possible byte values occurs at least once.
Record the positions of the first occurence of each value. This takes
ceil(lg(300 choose 256)) = 178 bits. Also, record the order in which
these values occur. This takes ceil(lg(256!)) = 1684 bits for a total
of 1862 bits, which is less than the 2400 original bits.


I looked at the patent. First I should say I have very little
experience looking at patents. I found the purposely obtuse
description annoying. The patent is now nearly two
years old and since there's yet to be an implementation
that I'm aware of I've got to assume it's flawed.

At first glance it seems like an interesting idea. Purposely
'massaging' the data being compressed in hopes being
able to use a compact descriptor.

I don't see how it could work though. The desciptor layout
does indeed consume less bits than what it replaces, but
I don't see how it could be used to reconstruct the orginal
300 bytes. What about the information for the redundant
40 bytes?

It is possible that the 300 input bytes do not have all 256 different
values. In that case, apply one of 64K transforms by adding (mod 256)
a random 300 byte mask from a library until this requirement is met.
This adds 16 bits to record which mask was chosen, for a total 1878
bits. If none of these masks results in 256 unique values, then try
variations of this method on segments of 152 7-bit sequences or 77
6-bit sequences.

Assuming this works the process may be very slow. And I
don't see how this would gurantee getting the needed # of
unique values. The patent also claims a range of compression
ratios ("savings") depending on the number of bytes in the string.
Apparently 300 bytes was about optimal when using 8-bit (byte)
quantities, but it could vary up to 377 (?) bytes with a greatly
reduced compression ratio (more bits consumed by decsciption
index). The patent also states that higher compression ratios can
be obtained using greater than 8-bit quanities (9, 10... whatever).



Since this method works on arbitrary data, it can be applied
recursively (or so the patent claims).

I don't see how this could be done recursively.


The flaw in this method seems pretty obvious, but it has apparently
escaped the notice of patent examiners during the 2 years it has been
on file so far.

What is the flaw if you don't mind me asking?

Eric B

One obvious flaw, as you already pointed out, is that there is no way
to reconstruct the 44 non-unique bytes.

The other (less obvious) flaw is that the scheme requires each of the
256 possible byte values to occur at least once in the 300 byte
sequence. The number of such sequences is (300!*256^44)/44! out of a
possible 256^300 sequences, or one in 2.806 * 10^56. So applying one
of 64K transforms is unlikely to put the input in the right form. You
would need 187.5 bits to encode enough transforms to guarantee the
required form for all possible inputs. When you add this plus the 44
bytes, you end up with exactly the same size as you started with, 300
bytes.

The "obvious" flaw is that any random or recursive compression scheme
violates the counting argument. You can't compress all n-bit strings
because there are 2^n of them, but only 2^n - 1 possible compressed
codes shorter than n bits. Yet it is amazing how many people there are
who can't understand this simple proof. Invariably, they have a weak
understanding of mathematics. Just like the perpetual motion designers
of the last century who didn't think conservation of energy applied to
them too, they build incredibly complicated mechanisms, making it
harder and harder for themselves and others to find the inevitable
error buried in their logic. People will spend years of effort in this
fruitless approach, forming companies, hiring programmers, working 16
hour days, filing patents, etc. and the result is always the same.
Such a waste...

-- Matt Mahoney

.

Relevant Pages

  • Re: How can an individual license out a compression method, or codec?
    ... I am working on a lossless compression algorithm for fun and I did to myself the same questions (well, I also answered to myself: Hey man, first of all you need a working one... ... So I red about Unisys and GIF patent, and I think that there are 3 main strategies to make money in this way: ...
    (comp.compression)
  • Re: compression - insights into infinite
    ... in fact it requires zero extra bytes to ... One of the book's routines "stats" accepts a buffer and produces three ... patent the method. ... work (my compression work,) will not survive me. ...
    (comp.compression)
  • Re: How can an individual license out a compression method, or codec?
    ... compression methods are developed by corporations and they have the ... and effective method of data compression that hasn't been seen. ... and once you have applied for a patent you ... The sad truth is, however, that not many people make money off data ...
    (comp.compression)
  • Re: TRM - Morbidity has set in, or not?
    ... clever permutation and inverse permutation index, ... But, unlike TRM, values will appear in ... compression algorithms are not patentable. ... My layman's understanding is that patents are about method rather than outcomes so if the TRM is unique in that regard its patent will stand. ...
    (comp.databases.theory)
  • Re: Pacbyte data compression patent
    ... It claims to work like this: divide the input into 300 byte segments. ... I looked at the patent. ... a random 300 byte mask from a library until this requirement is met. ... reduced compression ratio (more bits consumed by decsciption ...
    (comp.compression)