Re: Compact transition matrix storage schemes

Praki Prakash wrote:


> Can anybody point me to some published literature on the various schemes
> for storing transition matrix? I have done a bibliographic search but
> did not see any.


> [There's a little bit in the Dragon Book, but the approaches I've seen are
> all rather ad-hoc. -John]


This has come up from time to time in the code generation world.
There's the smash-out-equal-columns-and-rows stunt that has been
around for a long time. I had a paper in the 1987 POPL that described
a way to automatically construct pre-smashed tables for bottom-up tree
pattern matching (this was considered interesting because the
unsmashed tables can be extravagantly large, even on today's hardware,
never mind what we were using ten years ago). Fraser and Henry (?)
had a paper in Software Practice and Experience that explored several
heuristics for further reducing the space taken by these table while
still generating code very quickly.


I once tinkered with a run-length-encoded form of table storage; the
idea here is to permute columns so that the least number of equal runs
are created over all the rows; that is, it is better to have


    0 0 0 0 0 0 1 1 1 1 1 1


than


    0 1 0 1 0 1 0 1 0 1 0 1




Life gets more interesting when you have more than one row.


Turns out that finding the optimal permutation is an NP-complete
problem. It's relatively easy to turn it into a weird version of
traveling salesperson, where each column corresponds to a city and the
distance between two cities is the number of unequal elements.
Finding a shortest-cost route (using that definition of distance)
gives you your permutation. This is useful, since people have spent a
fair amount of time trying to get good heuristics for TS. (I don't
recall the other half of the NP-completeness proof, but I think you
can see it isn't hard). I think I used a heuristic described in Garey
and Johnson that involved a min-cost spanning tree plus some sort of a
matching heuristic, and I think it worked well, but this was never
published.
--
David Chase, chase@world.std.com
--

Return to the comp.compilers page.
Search the comp.compilers archives again.