Record boundary identification and extraction through pattern mining

• US 7,606,816 B2
• Filed: 07/28/2005
• Issued: 10/20/2009
• Est. Priority Date: 06/03/2005
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Kulkarni, Parashuram
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): SMITH, GARRETT A
• Application Number:
  US11/192,620
• Publication Number:
  US 20070027882A1
• Time in Patent Office: 1,545 Days
• Field of Search: 715/234, 715/237, 715/239
• US Class Current: 1/1
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/8373 Query execution
• CPC Class Codes: G06F 40/131 Fragmentation of text files, e.g. creating reusable text-blocks; Linking to fragments, e.g. using XInclude; Namespaces
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Techniques for identifying discrete records within a multi-record document are provided. According to one technique, a document is encoded based on some combination of visual tag encoding, text category encoding, and text content encoding that produces hash values based on the contents of portions of the document. According to one technique, repeating candidate patterns are identified in a document so encoded. The candidate patterns may be identified in a “fuzzy” manner that allows for some inconsistencies in the individual pattern instances. According to one technique, the identified candidate patterns are validated based on specified factors to determine a “best” pattern. According to one technique, the boundaries of discrete records in a multi-record document are marked based on the portions of the document that correspond to an identified repeating pattern.

Claims

1. A method of encoding data, the method comprising:

locating, by a computer in a set of data, one or more primary data items that match one or more patterns in a set of specified patterns, wherein the patterns in the set of specified patterns correspond to symbols;

for each primary data item of the one or more primary data items, performing steps comprising;

determining the symbol that is associated with the pattern that the primary data item matches, and

replacing the primary data item in the set of data with the symbol;

after performing the replacing, locating, in the set of data, one or more secondary data items that existed in the set of data prior to the replacing;

for each secondary data item of the one or more secondary data items, performing particular steps comprising;

generating a hash value based on the secondary data item; and

replacing the secondary data item in the set of data with a symbol that is associated with the hash value;

wherein the set of data corresponds to a first document that contains multiple records; and

determining boundaries for each record in the first document based on symbols that have replaced the secondary data items in the set of data.

2. The method of claim 1, further comprising:

extracting the records from the first document based on the boundaries, and

compiling the records with additional records that are contained in a second document to form a third document that contains records from the first document and records from the second document.

3. The method of claim 1, wherein:

at least one of the primary data items is an HTML tag; and

determining the symbol that is associated with the pattern that the primary data item matches comprises determining a symbol that is associated with a type of the HTML tag.

5. The method of claim 1, wherein determining the symbol that is associated with the pattern that the primary data item matches comprises:

determining a category to which the primary data item belongs; and

determining a symbol that is associated with the category.

14. A volatile or non-volatile computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

15. A volatile or non-volatile computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

16. A volatile or non-volatile computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

18. A volatile or non-volatile computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

4. A method of encoding data, the method comprising:

locating, by a computer in a set of data, one or more primary data items that match one or more patterns in a set of specified patterns, wherein the patterns in the set of specified patterns correspond to symbols;

for each primary data item of the one or more primary data items, performing steps comprising;

determining the symbol that is associated with the pattern that the primary data item matches, and

replacing the primary data item in the set of data with the symbol;

after performing the replacing, locating, in the set of data, one or more secondary data items that existed in the set of data prior to the replacing;

for each secondary data item of the one or more secondary data items, generating a hash value based on the secondary data item;

determining whether a particular primary data item is an HTML tag;

in response to determining that the particular primary data item is an HTML tag, determining whether a type of the HTML tag is a type that is included in a specified set of HTML tag types; and

in response to determining that the type is not included in the specified set of HTML tag types, removing the particular primary data item from the set of data.

17. A volatile or non-volatile computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

6. A method of identifying patterns, the method comprising:

locating, by a computer in a primary sequence of symbols, one or more secondary sequences, each of which consists of two or more consecutive occurrences of a particular symbol;

for each secondary sequence of the one or more secondary sequences, replacing the secondary sequence in the primary sequence with a single occurrence of a symbol that occurs within the secondary sequence;

after performing the replacing for each secondary sequence of the one or more secondary sequences, locating, in the primary sequence, one or more tertiary sequences, each of which consists of two or more consecutive occurrences of a particular two-symbol sequence; and

for each tertiary sequence of the one or more tertiary sequences, replacing the tertiary sequence in the primary sequence with a single occurrence of a two-symbol sequence that occurs within the tertiary sequence;

for each different secondary sequence of the one or more secondary sequences, adding, to a list of candidate repeating patterns, a single occurrence of a symbol that occurs within the different secondary sequence; and

for each different tertiary sequence of the one or more tertiary sequences, adding, to the list of candidate repeating patterns, a single occurrence of a two-symbol sequence that occurs within the different tertiary sequence;

determining boundaries for each record in the first document based on one or more candidate repeating patterns in the list of candidate repeating patterns;

extracting the records from the first document based on the boundaries, and compiling the records with additional records that are contained in a second document to form a third document that contains records from the first document and records from the second document; and

wherein the primary sequence of symbols corresponds to a first document that contains multiple records.

7. The method of claim 6, further comprising:

before performing the replacing for each secondary sequence of the one or more secondary sequences, removing, from the primary sequence, symbols that occur only once in the primary sequence.

8. The method of claim 6, further comprising:

for each particular sequence of one or more symbols in the list of candidate repeating patterns, determining whether the particular sequence satisfies one or more criteria, and if the particular sequence does not satisfy the one or more criteria, then removing the particular sequence from the list of candidate repeating patterns.

9. The method of claim 8, wherein at least one criterion of the one or more criteria is based on a number of times that the particular sequence occurs within the primary sequence.

10. The method of claim 8, wherein at least one criterion of the one or more criteria is based on a length of the particular sequence.

11. The method of claim 8, wherein at least one criterion of the one or more criteria is based on a consistency of sizes of records that are determined based on the particular sequence.

12. The method of claim 8, wherein at least one criterion of the one or more criteria is based on an extent to which records that are determined based on the particular sequence comprise the entirety of the first document.

13. The method of claim 6, further comprising:

after performing the replacing for each tertiary sequence of the one or more tertiary sequences, locating, in the primary sequence, one or more quaternary sequences, each of which consists of two or more consecutive occurrences of a particular three-symbol sequence; and

for each quaternary sequence of the one or more quaternary sequences, replacing the quaternary sequence in the primary sequence with a single occurrence of a three-symbol sequence that occurs within the quaternary sequence.

19. A volatile or non-volatile computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

20. A volatile or non-volatile computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

21. A volatile or non-volatile computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

22. A volatile or non-volatile computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

23. A volatile or non-volatile computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

24. A volatile or non-volatile computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

25. A volatile or non-volatile computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

26. A volatile or non-volatile computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.