Free-Traversing Syntactic and Semantic Comparison on Semi-Structured Languages

Tree traversing for syntactic and semantic comparison causes expensive time and space consumption. Internet, heterogeneous computing environments, and ubiquitous computing technologies all cause an explosive increase of Web data, and most Web data is written in semi-structured language format. With the growth of Web data usage and the importance of the management, comparison techniques such as similarity detection are more and more needed for efficient information and database management. This paper introduces a free-traversing technique without tree traversing on parse trees generated by the corresponding language parser to analyze its syntactic and semantic meaning. This free-traversing technique uses DIES (direct invariant encoding scheme) encoding method and has similar results with DFS (depth first search) of parse tree traversing. We use XML schema DTDs to evaluate our free-traversing technique. We adopt some of ontological technologies, and apply LCS (longest common string) and LNS (longest nesting common string) structure extraction methods. With this free-traversing technique, semi-structured Web data management can be much easier and faster than existing tree traversing methods.