Author: Dann Corbit
Date: 13:05:04 03/01/06
Go up one level in this thread
On February 28, 2006 at 20:38:08, Ratko V Tomic wrote: >> 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. I agree that this simple, elegant algorithm is a significant, mathematical discovery. I think it would be good to let people know about it. It might be worthwhile to write a paper on the algorithm. Even a one-pager, just so people can find out about it when it gets into the Citeseer database.
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.