19 Jul 2006 14:34:22 -0400

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) |

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.