simpletreematching.java

使用java实现的简单树匹配算法

package xx1;

import java.io.File;

import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;

import org.w3c.dom.Document;
import org.w3c.dom.Node;



public class SimpleTreeMatching
{
	public boolean Matching()
	{
		try
		{			
			DocumentBuilderFactory dbf;
			DocumentBuilder db;
			Document doc;		
			dbf = DocumentBuilderFactory.newInstance();
			db = dbf.newDocumentBuilder();
			doc=db.parse(new File("xx11.xml"));		
			Node root1=doc.getDocumentElement();		
			doc=db.parse(new File("xx12.xml"));		
			Node root2=doc.getDocumentElement();		
			int result=recursion(root1,root2);
			System.out.println("Common nodes:"+result);
			StatisticAllNodes s1=new StatisticAllNodes("xx11.xml");
			int s1c=s1.computeNodesNumber();
			System.out.println("SampleURLNodesNumber():"+s1c);
			StatisticAllNodes s2=new StatisticAllNodes("xx12.xml");
			int s2c=s2.computeNodesNumber();
			System.out.println("RoughURLNodesNumber():"+s2c);
			
			System.out.println("(double)result/s1c:"+(double)result/s1c);
			System.out.println("(double)result/s2c:"+(double)result/s2c);
			
			if((double)result/s1c>=0.6&&		//这里可以调整阈值
				(double)result/s2c>=0.6			//
				)								//
				return true;			
			else
				return false;
		}
		catch (Exception e)
		{			
			e.printStackTrace();
			return false;
		}		
	}
	public int recursion(Node root1, Node root2)
	{		
		if(!root1.getNodeName().equals(root2.getNodeName()))
			return 0;		
		int m=root1.getChildNodes().getLength();
		int n=root2.getChildNodes().getLength();
		int M[][]=new int [m+1][n+1];
		int W[][]=new int [m+1][n+1];
		for(int i=0;i<=m;i++)
			M[i][0]=0;
		for(int j=0;j<=n;j++)
			M[0][j]=0;
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
			{
				W[i][j]=recursion(root1.getChildNodes().item(i-1), root2.getChildNodes().item(j-1));
				M[i][j]=M[i][j-1]>M[i-1][j]?(M[i][j-1]>M[i-1][j-1]+W[i][j]?M[i][j-1]:M[i-1][j-1]+W[i][j]):(M[i-1][j]>M[i-1][j-1]+W[i][j]?M[i-1][j]:M[i-1][j-1]+W[i][j]);			
				
			}
		return M[m][n]+1;
	}
	public static void main(String[] args)
	{
		try
		{
			new SimpleTreeMatching().Matching();
		}
		catch (Exception e)
		{			
			e.printStackTrace();
		}

	}
}