Author: GuyHaworth
Date: 00:39:14 09/19/03
Go up one level in this thread
I had a short explanation - which I don't claim to fully understand - from Andrew Kadatch in July. With some small corrections, what is below is essentially a quote from what he sent me. "Unfortunately, there is no algorithm description in Enlgish; it's a derivative (= badly simplified) version of an algorithm for efficient compression of multidimensional data described in my diploma thesis (circa 1992). Probably I have a copy somewhere but I am not sure; if anyone interested is fluent in Russian, I can try to dig it out. Or I can try to describe the algorithm quickly right here. Essentially, it can be thought of as a variant of LZ77 which transforms input string S over alphabet A into compressed representation S* by replacing substrings in S with references to previous occurrences of same substring. In this implementation, such identical occurance shall happen on one of few fixed locations relative to beginning of original substring (say, substring may start only 1, 3, 20, and 250 symbols before beginning of current substring), so the reference to previous occurance is a pair <I,L> where I is index of actual offset from beginning of replaced substring to beginning of matching substring and L is the length of substring. The choice of those few fixed locations where matching substrings could start is an interesting problem by itself; the implementation you have access [in Nalimov's code presumably: Guy] to solves the problem by looking at some randomly and uniformly distributed choosen subset of uncompressed data and evaluating all possible positions as match candidates, and then choosing only few most promising ones that will be used for actual encoding and decoding. So it's simple as piece of cake :-)." If anyone can, by example, explain what is going on here, I also would be most grateful. As advertised, anyone who wants to attempt the Russian-English translation is v welcome. I don't have a copy of the thesis itself. g
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.