Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!mips!spool.mu.edu!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!mcsun!ukc!warwick!mauls
From: mauls@warwick.ac.uk (The Chief Slime Monster)
Newsgroups: comp.compression
Subject: Chain functions for compression
Message-ID: <TJ-_MT~@warwick.ac.uk>
Date: 11 Apr 91 18:45:22 GMT
Sender: news@warwick.ac.uk (Network news)
Organization: Computing Services, Warwick University, UK
Lines: 41
Nntp-Posting-Host: lily


With all this talk of finding strings in infinite expansions I thought I 
would mention something a colleague and I thought of. I don't spose it is
original, in fact, you've probably all read it before in this newsgroup,
but here goes.

A chain function is just a function that generates a finite number of unique
values and then cycles:

i.e.   f(n) = f(1), for some n, otherwise all f(i) != f(j)   1<=i<j<n.

The postulation was this:

Consider file as binary string length L. There exists a chain function
which will step uniquely through every possible binary string of length L
before repeating. Then, if the file string is equal to f(N), where f is
the chain function, and N is a number, replace the string with the binary
representation of N. To decompress, just calculate f(N).

Not surprisingly, the representation of N is not, on average, smaller than
the file string.

Slime