Computer implemented example-based concept-oriented data extraction method

• US 7,107,524 B2
• Filed: 05/21/2003
• Issued: 09/12/2006
• Est. Priority Date: 12/24/2002
• Status: Expired due to Fees

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Chiu, Chung-Jen, Lin, Yi-Chung
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): RUTLEDGE, AMELIA L
• Application Number:
  US10/442,300
• Publication Number:
  US 20040123237A1
• Time in Patent Office: 1,210 Days
• Field of Search: 715/513, 706/55, 707/6
• US Class Current: 715/234
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

The present invention relates to an example-based concept-orietned data extraction method. In an example labeling phase, the exemplary data string is converted into an exemplary token sequence, in which the target concepts and filler concepts are labeled to be tuples for use as an example, and thus an exemplary concept graph is constructed. In the data extraction phase, the untested data string is converted into an untested token sequence to be processed, and, based on the associated concept recognizers defined by the tuples in the example labeling phase, it is able to detect the concept candidates and establish the composite concepts and aggregate concepts, thereby constructing a hypothetical concept graph. After comparing the exemplary concept graph with the hypothetical concept graph, the optimal hypothetical concept sequence in the hypothetical graph is determined, so as to extract the targeted data from the matched target concepts.

Claims

1. A computer implemented example-based concept-oriented data extraction method, comprising:

a first procedure for labeling an exemplary data string, comprising the steps of;

capturing an exemplary data string;

tokenizing the exemplary data string into a plurality of tokens as an exemplary token sequence, each token having an index;

specifying the exemplary token sequence as a plurality of specific concepts, each being labeled to be a tuple and consisting of at least one token, the specific concept being selected from the group of a target concept and a filler concept, the target concept pointing to the targeted data of interest, the filler concept pointing to the contextual data of the targeted data, each tuple having a format including a concept type, a concept name, a beginning index of the first token in the specific concept, an ending index of the last token in the specific concept, and an associated concept recognizer of the specific concept, wherein the associated concept recognizer is provided to recognize the possible token sequence of the specific concept; and

constructing an exemplary concept graph of the exemplary data string according to the tuples; and

a second procedure for extracting targeted data from an untested data string, comprising the steps of;

capturing an untested data string;

tokenizing the untested data string into a plurality of tokens as an untested token sequence;

using the associated concept recognizers defined by the tuples for detecting a plurality of concept candidates, wherein each concept candidate has a format including the beginning index and the ending index of the corresponding token sequence, and the concept name of the concept candidate;

constructing a preliminary concept graph of the untested token sequence according to the concept candidates; and

determining an optimal hypothetical concept sequence by comparing the exemplary concept graph with the preliminary concept graph and capturing at least one matched target concept from the optimal hypothetical concept sequence for extracting the targeted data.

2. The method as claimed in claim 1, wherein the exemplary data string and the untested data string are HTML source codes.

3. The method as claimed in claim 2, wherein in the step of tokenizing the exemplary data string into a plurality of tokens, the tokens comprise HTML tags and text segments between HTML tags.

4. The method as claimed in claim 1, wherein the exemplary data string and the untested data string are articles.

5. The method as claimed in claim 4, wherein in the step of tokenizing the exemplary data string into a plurality of tokens, each token is a word.

6. The method as claimed in claim 1, wherein in the step of determining an optimal hypothetical concept sequence, a dynamic programming technique is applied for comparing the exemplary concept graph with the preliminary concept graph for determining the optimal hypothetical concept sequence.

7. The method as claimed in claim 6, wherein the dynamic programming technique uses a cost function for calculating the cost of an edit operation which is selected from the group of insertion, deletion, and substitution, and the cost function is as follows:

where x is a hypothetical concept, y is an exemplary concept, and x=y means x and y have the same concept name.

8. The method as claimed in claim 6, wherein the dynamic programming technique uses a cost function for calculating the cost of an edit operation which is selected from the group of insertion, deletion, and substitution, and the cost equation is as follows:

where n_x is the number of tokens in the hypothetical concept x, n_y is the number of tokens in the hypothetical concept, and ∈

is a variable to control the sensitivity of cost on the difference between n_x and n_y.

9. The method as claimed in claim 1, wherein in the step of specifying the exemplary token sequence as a plurality of specific concepts, at least one concept rule is used for specifying a composite concept composed of a plurality of specific concepts, and the associated concept recognizer of the composite concept is provided for defining the corresponding relation between the composite concept and the specific concepts being composed.

10. The method as claimed in claim 9, wherein the concept rule is a context-free rule.

11. The method as claimed in claim 9, wherein the step of constructing a preliminary concept graph of the untested token sequence according to the concept candidates further comprises:

constructing a preliminary concept graph of the untested token sequence according to the concept candidates; and

converting the preliminary concept graph into a hypothetical concept graph according to the concept rules.

12. The method as claimed in claim 11, wherein in the step of determining an optimal hypothetical concept sequence, the matched target concept is the composite concept.

13. The method as claimed in claim 12, wherein the step of determining an optimal hypothetical concept sequence further comprises:

determining an optimal hypothetical concept sequence by comparing the exemplary concept graph with the preliminary concept graph;

capturing at least one matched target concept from the hypothetical concept sequence; and

extracting the targeted data by respectively analyzing specific concepts of each matched target concept.

14. The method as claimed in claim 1, wherein in the step of specifying the exemplary token sequence as a plurality of specific concepts, the target concept is specified by the user.

15. The method as claimed in claim 1, wherein, after the step of specifying the exemplary token sequence as a plurality of specific concepts, the tokens are automatically specified as filler concepts if there are tokens that still have not been specified as specific concepts.

16. The method as claimed in claim 1, wherein the associated concept recognizer is dynamically generated.

17. The method as claimed in claim 1, wherein the associated concept recognizer is predetermined.

18. The method as claimed in claim 1, wherein the associated concept recognizer is provided by a user.