18 Jul 2006 16:10:04 -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: | alpanad@gmail.com |

Newsgroups: | comp.compilers |

Date: | 18 Jul 2006 16:10:04 -0400 |

Organization: | Compilers Central |

Keywords: | parse, question |

Posted-Date: | 18 Jul 2006 16:10:04 EDT |

Hi,

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.

For example suppose we have two trees as follows

A A

/ \ / | \

A A A A A

/ \ / \ / /\ \

t1 t2 t3 t4 t1 t2 t3 t4

The parenthesis structures imposed from above two tress are string1:

((t1 t2) (t3 t4)) and

string2: ( t1 (t2 t3) t4). In order to convert the string2 to string1

we need at least three operations; i.e. a deletion of a pair of

parenthesis (t2 t3) and addition of two pairs of parenthesis (t1 t2)

and (t3 t4).

Any good pointer which discusses the computaion of edit distance

between two parenthesis structures to solve the above problem will be

of much help.

Thanks in advance,

Alpana

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.