How does one identify common subexpressions in a tree?

awerman@panix.com (Aaron Werman)
Sun, 17 Jan 1993 04:05:33 GMT

          From comp.compilers
Related articles
How does one identify common subexpressions in a tree? awerman@panix.com (1993-01-17)
Re: How does one identify common subexpressions in a tree? preston@dawn.cs.rice.edu (1993-01-17)
| List of all articles for this month |
Newsgroups: comp.programming,comp.compilers,comp.ai
From: awerman@panix.com (Aaron Werman)
Organization: PANIX Public Access Unix, NYC
Date: Sun, 17 Jan 1993 04:05:33 GMT
Keywords: theory, design

In a project that I am working on, much of the data comes in tree form
where most of the data is duplicated many times over. It would
tremendously simplify the task of analysing the data if common subtrees
could be extracted.


This seems to be a common problem. The most direct association seems to me
to be with subexpression extraction in a compiler, pattern matching (or
pruning algorithms) in AI, or some sparse matrix reductions in OR.


The size of the input sets should be in the thousands of symbols. There
are no needs for perfect reduction or fast reduction. I'm curious to see
how others have dealt with similar problems. Code or algorithm pointers
would be great.


Thanks in advance,
--
Aaron Werman awerman@panix.com
--

Post a followup to this message

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