# Algorithms to compare None-Binary Trees

• 07-24-2012, 01:56 PM
Algorithms to compare None-Binary Trees
Hi, every body
it's of my pleasure to be with you in this great forum ,Especially with existence of experienced people.
Actually I wonder if anyone can help me because I'm facing a problem in comparing trees in java as your excellency know there is little information about the Algorithms of comparing None-binary trees in Data structure articles and books, Especially comparing trees gained from a natural language parser .
I'm sorry to get to my aim directly without explaining the whole idea of my work.
My graduation project is to build a software that take or read a requirement document (as a text file) and parse it using the Stanford dependency parser (a Natural language parser) to extract the syntactic and semantics knowledge from it then compare it with a predefined knowledge ,Actually I want to compare parse trees gained from the parser with other predefined trees which represents a small knowledge base of templates (which are all of the type Tree in java) to find the most similar template to the entered text or the degree of difference between two trees.
as an example the following template and the entered text respectively.
1-the sentence (which represents the template ) is "if the element is a member of the set" and its parse tree as follows
(ROOT
(SBAR (IN if)
(S
(NP (DT the) (NN element))
(VP (VBZ is)
(NP
(NP (DT a) (NN member))
(PP (IN of)
(NP (DT the) (NN set))))))))

2-the entered is "if the car is a member of the rent car set" and its parse tree as follows
(ROOT
(SBAR (IN if)
(S
(NP (DT the) (NN car))
(VP (VBZ is)
(NP
(NP (NN member))
(PP (IN of)
(NP
(NP (DT the) (NN rent) (NN car))
(VP (VBN set)))))))))

the best help that anyone can offer is to give my any code to compare such type of trees
and i will be so Grateful to explain the comparison algorithm as well. because I'm out of time and should submit my
project as soon as possible less than a month. I'm really embarrassed of the short period given to me.