[Caml-list] "super-compaction" of values

[Thorsten Ohl <ohl@hep.tu-darmstadt.de>]

Markus Mottl writes:

> has anybody already attempted to implement some kind of
> "super-compaction" [...] 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 (2n-1)!! = (2n-1)(2n-3)(2n-5)... if represented as
trees, but can be rewritten as DAGs of size 10**(n/2) [see
http://heplix.ikp.physik.tu-darmstadt.de/~ohl/omega/ and in particular
the chapter Directed Acyclical Graphs in
http://heplix.ikp.physik.tu-darmstadt.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.tu-darmstadt.de
http://heplix.ikp.physik.tu-darmstadt.de/~ohl/ [<=== PGP public key here]
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr