Edit distance between two unlabeled parse trees

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