Re: Fixpoint for LZH

From: Ioannis (morpheus_at_olympus.mons)
Date: 07/15/04 

Date: Fri, 16 Jul 2004 02:55:42 +0300

hack wrote:

> In article <1089923101.955081@athnrd02.forthnet.gr>,
[snip]
>>>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.

I was rather having in mind the insertion of a count only when there is
a repeat. Nevertheless your point still stands, although the
decompression would be undefined for RLE(12345) without additional
sentinels telling RLE how to treat the cells.

> 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.

Probably agree. I tried to think of a fixed point for a variant of RLE
which inserts a sentinel m prior to the count, but could not come up
with anything. Note that in this case the sentinel has to be outside the
range of the data, if it is to make any sense *as* an indicator for a
coming count. The later conspires highly for the non-existence of a
fixed point, although I cannot see it clearly.

> Michel. 

-- 
I. N. Galidakis
http://users.forthnet.gr/ath/jgal/
------------------------------------------
Eventually, _everything_ is understandable

Relevant Pages

  • Re: RLE & RGB to YBR_FULL
    ... "It is unusual to use an RGB colorspace for RLE compression, ... Does this mean if I RLE encode an image and do color space conversion ...
    (comp.protocols.dicom)
  • Re: JPEG2000
    ... We are in need of a compression meganism that is capable of compressing ... use larger pixels/fewer bits per pixel. ... maybe huffman and some manner of filtering "could" get it a little higher, ... huffman coder has rle. ...
    (comp.compression)
  • Re: GetThumbnailImage increases file size
    ... ResizeAndSaveToAll = ResizedImg.Size.ToString is not nessesarly the ... That your orignial image was only 42k suggests it was using rle ... compression. ... together and the length of consequative identical pixel sequences is ...
    (microsoft.public.dotnet.framework.drawing)
  • Re: Fujitsu NetCOBOL for .NET
    ... With a 69-byte "text" file, I doubt you'd get much compression, if ... from RLE; plain ASCII text (which I assume is what we're dealing ... LZ77 doesn't require much table space. ... symbols in LZ77 output refer back to earlier data: ...
    (comp.lang.cobol)
  • Re: GZIPOutputStream GZIPInputStream
    ... Steffen Heinzl wrote: ... >>DeflaterOutputStream where you can set the compression level. ... >>HTTP messages) and since I was using a buffered reader it read past the ... the reader would read until the sentinel was ...
    (comp.lang.java.programmer)