Author: Dan Andersson
Date: 07:34:14 04/06/03
Go up one level in this thread
>I disagree Dan.
>
>All compression i know compresses lineair. Hashtables would compress now
>exponential which is pretty funny form of compression.
Just goes to show how much you don't know. There are multiple ways to look at
it. And the different domains give different insights. Optimization theory might
yield other.
To show the resemblance to compression I will first desctibe Huffman Coding.
(1) Rank all symbols in order of probability of occurrence.
(2) Successively combine the two symbols of the lowest probability to form
a new composite symbol; eventually we will build a binary tree where
each node is the probability of all nodes beneath it.
(3) Trace a path to each leaf, noticing the direction at each node.
While not proving the sameness it nevertheless indicates a tree structure. But
this next compression technique is more revealing. Substitution Compression aka
Dictionary compression.
The basic idea behind a substitutional compressor is to replace an
occurrence of a particular phrase or group of bytes in a piece of data with a
reference to a previous occurrence of that phrase.
Sounds familiar doesn't it ;) And the LZ family of compressors are in widespread
use. Nothing stops you from using dictionary entries as new nodes thus you will
have a tree.
Thanks to the comp.compression FAQ!
MvH Dan Andersson
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.