Author: Vincent Diepeveen
Date: 12:25:11 04/06/03
Go up one level in this thread
On April 06, 2003 at 10:34:14, Dan Andersson wrote: >>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. I have written my own huffman compression several times, as well as some experiments with fractal compression, arithmetic compression and the copyrighted LZ compression i took a look at of course too. The last being not as good as some might tell you it is. You are not getting the point. Not even within a mile accuracy. Compression you cannot see as a tree at all. That implementation of the symbols in huffman is in tree format, it has nothing to do with that. Further of all you know your domain and you have to scan (in your words probably 'search') the entire domain. In chess you try to prevent searching the whole domain. You try to skip positions. Hashtables do not compress at all. They give transpositions. That gives as a result an exponential speedup. Only those who know very little from search will say compression is equal to search in chess. >(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.