Re: Edit distance between two unlabeled parse trees

haberg@math.su.se (Hans Aberg)
19 Jul 2006 14:34:22 -0400

          From comp.compilers

Related articles
Edit distance between two unlabeled parse trees alpanad@gmail.com (2006-07-18)
Re: Edit distance between two unlabeled parse trees haberg@math.su.se (2006-07-19)
| List of all articles for this month |

From: haberg@math.su.se (Hans Aberg)
Newsgroups: comp.compilers
Date: 19 Jul 2006 14:34:22 -0400
Organization: Mathematics
References: 06-07-044
Keywords: parse

  alpanad@gmail.com wrote:


> Can anyone shed some light on the problem of finding out the distance
> between two unlabeled parse trees (these trees are built by parsing a
> sentence with two different grammars). Ths problem can be very well
> mapped to the problem of finding out the edit distance between the
> paranthesis structures imposed by the parse tree on the input
> sentence.


> Any good pointer which discusses the computaion of edit distance
> between two parenthesis structures to solve the above problem will be
> of much help.


It is not clear to me exactly what kind of edit changes you want to admit.
For example, you seem to admit operators of different arity to be
equivalent.


But one idea: rewrite the strings into Lukasiewicz or RPN notation, which
do not require parenthesizes, and then apply some kind of Levenshtein
distance. See
    http://en.wikipedia.org/wiki/Jan_Lukasiewicz
    http://en.wikipedia.org/wiki/Polish_notation
    http://en.wikipedia.org/wiki/Reverse_Polish_notation
    http://en.wikipedia.org/wiki/Levenshtein_distance


--
    Hans Aberg


Post a followup to this message

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