| Sebastian Gesemann 2004-10-11, 3:55 pm |
| On 11 Oct 2004, gigaflops wrote:
> I was thinking of using a sort algorithm for compression.
> Are their any compression programs with sort algorithms?
>
> The compression program will describe the sort path.
> after this it wil use something like RLE or huffman.
>
> Will it work?
It depends on your sorting algorithm and how much overhead you
need to store the "sort path". If you do a plain quick sort
of bytes store some overhead to identify the permutation and code
the sorted bvtes via RLE or DPCM this won't help you in terms of
compression.
A more advanced approach is the BWT transform. The  thing about
the BWT is: you don't need much overhead to store the permutation.
It does not sort all bytes correctly but it usually creates long runs
of the same bytes if there's strong interrelationship between bytes
(like in english text for example). No need to store a "sort path"
since this transform is reversible with _really_ small amount of
control data.
Google for BWT (Burrow Wheeler Transform)
(The BWT is used in BZIP2 for example)
HTH,
Sebastian
--
PGP-Key-ID (long): 572B1778A4CA0707
|