Discrete Wavelet Transform Method for Document Structure Similarity

• US 20140236968A1
• Filed: 10/31/2011
• Published: 08/21/2014
• Est. Priority Date: 10/31/2011
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Cong-Lei Yao, Hui-Man Hou, Jerry J. Liu, Li-Mei Jiao
• Inventors: Liu, Jerry J., Yao, Cong-Lei, Jiao, Li-mei, Hou, Hui-man
• Granted Patent: US 9,405,750 B2
• Time in Patent Office: Days
• US Class Current: 707/748
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/986 Document structures and storage, e.g. HTML extensions
• CPC Class Codes: G06F 17/148 Wavelet transforms
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/194 Calculation of difference between files

Abstract

Examples of the present disclosure may include methods, systems, and computer readable media with executable instructions. An example method for determining document structure similarity can include segmenting path sequences (206) of Document Object Model (DOM) trees (120, 462) from a number of web pages (202) into B components (561). Path signals (210) corresponding to the path sequences (206) are determined based on a count of the occurrences of particular paths in the B^th component (571), and unique path signals (210) are transformed into discrete wavelet signals (214)(572). The discrete wavelet signals (214) are analyzed at multiple DOM tree resolution levels (573).

Claims

1. A method for determining document structure similarity, comprising:

segmenting path sequences (206) of Document Object. Model (DOM) trees (120, 462) from a number of web pages (202) into B components (561);

determining path signals (210) corresponding to the path sequences (206) based on a count of the occurrences of particular paths in the B^th component (571);

transforming unique path signals (210) into discrete wavelet signals (214) (572); and

analyzing the discrete wavelet signals (214) multiple DOM ee resolution levels (573).

2. The method of claim 1, wherein transforming unique path signals further comprises transforming unique path signals into Haar wavelet signals.

3. The method of claim 2, wherein segmenting path sequences (206) further comprises:

parsing HyperText Markup Language (HTML) of the number of web pages (202) into DOM trees (120, 462);

converting the DOM trees (120, 462) of the number of web pages (202) into path sequences (206) that originate at a root node (222); and

converting the path sequences (206) into numbers with a hashing function.

4. The method of claim 1, wherein determining path signals (210) further comprises weighting the path signals (210) based on DOM tree (120, 462) and path sequence (206) characteristics, and wherein transforming unique path signals (210) into Haar wavelet signals further comprises transforming less than all unique path signals (210) of two DOM trees (120, 462) being compared based on weight of the path signals (210).

5. The method of claim 1, wherein transforming unique path signals (210) into discrete wavelet signals (214) further comprises transforming all unique path signals (210) of two DOM trees (120, 462) being compared.

6. The method of claim 1, wherein analyzing the discrete wavelet signals (214) further comprises calculating frequency information from one or more parts of the DOM trees (120, 462).

7. The method of claim 1, wherein analyzing the discrete wavelet signals (214) further comprises:

computing distance values on multiple levels of resolution; and

comparing the distance values as a measure of similarity.

8. The method of claim 7, wherein analyzing the discrete wavelet signals (214) further comprises:

computing a distance value for every common signal path of two DOM trees (120, 462); and

summing the distance values as a final tree distance for each of the two DOM trees (120, 462).

9. The method of claim 1, wherein analyzing the discrete wavelet signals (214) further comprises computing a distance value for a B^th component the discrete wavelet signals (214) of each signal path of two DOM trees (120, 462).

10. The method of claim 1, wherein analyzing the discrete wavelet signals (214) further comprises comparing different components in the discrete wavelet signals (214) of different signal paths as a proximity measure.

11. The method of claim 1, wherein analyzing the discrete wavelet signals (214) further comprises comparing Haar wavelet signals of path signals (210) from a root node (222) until the Haar wavelet signals differ.

12. The method of claim 1, wherein transforming unique path signals (210) into discrete wavelet signals further comprises reducing a Haar wavelet transform to order O(N) from order O(N2).

13. A non-transitory computer-readable medium (681, 795) having computer-executable instructions stored thereon, the computer-executable instructions comprising instructions (682) that, if executed by one or more processors (680, 794), cause the one or more processors (680, 794) to:

segment path sequences (206) of Document Object Model (DOM) trees (120, 462) of two web pages (202) into a number of equal components (561);

determine path signals (210) corresponding to the path sequences (206) based on a count of the occurrences of particular paths in at least one component (571);

transform unique path signals (210) into Haar wavelet signals; and

compare the Haar wavelet signals for similarity at multiple DOM tree (120, 462) resolution levels.

14. The non-transitory computer-readable medium of claim 13, further comprising instructions that, if executed by one or more processors, cause the one or more processors to:

compute a cumulative distance value for every common signal path of the DOM trees (120, 462); and

compare a difference between the cumulative distances against a threshold value as a measure of web page similarity.

15. A computing system for determining document structure comprising:

an HTML parser (204) to parse Document Object Model (DOM) trees from a number of web pages (202) into path sequences (206);

a path sequence segmentation module (208) to segment the path sequences (206) into B components and determine path signals (210) corresponding to the path sequences (206) based on a count of the occurrences of particular paths in the B^th component;

a Harr wavelet transformation module (212) transforming unique path signals (210) into discrete wavelet signals (214); and

an analyzer (216) to compute a cumulative distance value of the discrete wavelet signals (214) at multiple DOM tree resolution levels.