[Camllist] "supercompaction" of values

Markus Mottl
 Thorsten Ohl
 Alexander V. Voinov
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Thorsten Ohl <ohl@h...> 
Subject:  [Camllist] "supercompaction" of values 
Markus Mottl writes: > has anybody already attempted to implement some kind of > "supercompaction" [...] If this worked for arbitrary > datastructures, one could exploit this to produce very compact > representations of values by maximizing the amount of sharing > between them. I'm sure that one can not beat the combinatorial complexity of the general case. For example, I work with algebraic expressions that grow in size like (2n1)!! = (2n1)(2n3)(2n5)... if represented as trees, but can be rewritten as DAGs of size 10**(n/2) [see http://heplix.ikp.physik.tudarmstadt.de/~ohl/omega/ and in particular the chapter Directed Acyclical Graphs in http://heplix.ikp.physik.tudarmstadt.de/~ohl/omega/omega.pdf]. In my experience, one can beat the combinatorial complexity only if one understands the genesis of such values with high sharing potential. Then one can construct algorithms that start from building all possible combinations in a highly condensed representation and select the interesting ones later. This will be much more efficient than building only the interesting ones and searching for shared nodes later. But this is never a general solution, because it requires a good unterstanding of the structure of possible terms.  Thorsten Ohl, Physics Department, TU Darmstadt  ohl@hep.tudarmstadt.de http://heplix.ikp.physik.tudarmstadt.de/~ohl/ [<=== PGP public key here]  Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr