Author: Ratko V Tomic
Date: 17:38:08 02/28/06
Go up one level in this thread
> Could you please e-mail me, as I think this has
> wandered off topic for CCC.
I just updated my CCC email in the profile (the old one
was receiving too much spam).
> I'm intrigued as to how you think this could be utilised
> for compression algorithms.
This algorithm would fall under combinatorial generation
(all subsets of a subset). There is neat online book by
Ruskey with lots of related, practically oriented material:
F. Ruskey "Combinatorial Generation"
CSC-425/520 Univ. of Victoria CA,2003
http://www.1stworks.com/ref/RuskeyCombGen.pdf
http://www.cs.uvic.ca/~ruskey/Publications/
See also [8a] (Brak's AMSI lectures), [21] (Knuth4 on bits &
boolean manipulations), and [25] (Ruskey on permutations) on the
QI Ref. Lib. page: http://www.1stworks.com/ref/RefLib.htm .
There is also interesting series of papers on arXiv which uses bit
pattern manipulations to compute roots of integers & polynomials:
http://arxiv.org/find/math/1/au:+Mittal_A/0/1/0/all/0/1 .
I have used similar 'carry ripple across' techniques many times,
but your variant is a particularly elegant one which I
didn't see before (and it didn't occur to me). It is clear
that one can extend it to bit arrays/sets of any size. One
possibility for using it in compression might be as an
interpolation for the ranking. In combinatorial compression
you compute rank (eg. lexicographic) of a given specific bit
pattern within the larger set of patterns satisfying some
constraints (e.g. specified bit counts or number of runs etc).
But you can also compute rank for a set of bit patterns (which
may be easier or use smaller tables). The subset generation
would then be used to interpolate witin the decoded smaller
set of patterns.
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.