Re: Fixpoint for LZH

From: hack (hack_at_watson.ibm.com)
Date: 07/15/04 

Date: 15 Jul 2004 22:05:05 GMT

In article <1089923101.955081@athnrd02.forthnet.gr>,
Ioannis <morpheus@olympus.mons> wrote:
>dev_null wrote:
>
>>
>> And what is about RLE( 12345) = 12345 or RLE( 4321) = 4321 and so on?
>>
>> Regards
>> Luc
>
>Yes, that's theoretically correct. Any string of data that does not
>contain repeating substrings, will be a "fixed point" of RLE.

You're forgetting that you need to be able to *decode* the thing, so you
have to be able to tell a repetition count from an unrepeated value.

Your original example suggested a strict alternation of count and symbol,
so that RLE(12345) would in fact expand to 1112131415. That's ok -- any
lossless compression method must expand some inputs, and the point of the
compression is that, in a given application domain, the objects of interest
have patterns that are mostly compressible.

Once the need for decodability is is taken into account, it becomes a bit
more difficult to find a realistic example.

Michel.

Relevant Pages

  • Re: =?iso-8859-1?q?Re:_Kolmorgorov_Complexity_and_Kim_=D8yhus?=
    ... >>>of the string. ... >> universal computing device, say an universal Turing machine, which IS ... K.C. is defined to require an universal computer, ... >These are different forms of potential compression. ...
    (talk.origins)
  • =?iso-8859-1?q?Re:_Kolmorgorov_Complexity_and_Kim_=D8yhus?=
    ... >>of the string. ... These are different forms of potential compression. ... >>functional system may not be able to sustain such sequence compression ... Chaos theory is about DETERMINISTIC systems which amplify small ...
    (talk.origins)
  • Re: Attention Sean - question about CSI
    ... Maybe the degree of compression can serve as a measure ... If I am allowed to choose the compression algorithm *after* ... which compresses that string to a single bit. ... If you are allowed to transmit the data separately, ...
    (talk.origins)
  • Re: Just for fun...
    ... complexity in practical scenarios... ... corresponding complexities for a given string can differ at most by a constant ... When I first learned about the concept of compression, ... surprise in the questions/issues being discussed, ...
    (comp.lang.ruby)
  • Re: compression
    ... years has had compression on it.. ... It can vary attack time.. ... It gives you a more even output from string to string.. ... without digging entirely into the tubes.. ...
    (alt.guitar)