System and method for the automatic mining of acronym-expansion pairs patterns and formation rules

• US 6,385,629 B1
• Filed: 11/15/1999
• Issued: 05/07/2002
• Est. Priority Date: 11/15/1999
• Status: Expired due to Term

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Sundaresan, Neelakantan, Yi, Jeonghee
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Kindred, Alford W.
• Application Number:
  US09/440,625
• Time in Patent Office: 904 Days
• Field of Search: 707/1-7, 707/101-104, 707/203, 707/500-510, 707/526, 707/517, 707/515-516, 709/201-204, 709/217, 345/594, 345/650, 345/700
• US Class Current: 715/235
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A computer program product is provided as an automatic mining system to identify a set of related information on the World Wide Web using the duality concept. The mining system addresses iteratively refines mutually dependent approximations to their identifications. Specifically, the mining system iteratively refines (i) pairs of phrases related in a specific way; (ii) the patterns of their occurrences in web pages; and (iii) the formation rules. In one embodiment, the automatic mining system identifies (acronym, expansion) pairs in terms of the patterns of their occurrences in the web pages and their formation rules. The automatic mining system includes a formation rule identifier that derives the formation rules, an acronym-expansion pair identifier that derives the (acronym, expansion) pairs, and a pattern identifier that derives the patterns. The database stores the (acronym, expansion) pairs, patterns, and formation rules. Initially, the database begins with small seed sets of (acronym, expansion) pairs, patterns, and formation rules that are continuously and iteratively broadened by the automatic mining system.

Claims

1. A system for automatically and iteratively mining acronyms and expansion in a document d_i through patterns of occurrences and formation rules, comprising:

a database for storing previously identified acronym-expansion pairs R<sub>i−

1</sub>, patterns P<sub>i−

1</sub>, and formation rules E<sub>i−

1</sub>;

a formation rule identifier that uses the acronym-expansion pairs R<sub>i−

1</sub> for deriving a formation rule E_i;

an acronym-expansion pair identifier that uses the document d_i and the patterns P<sub>i−

1</sub> for deriving an acronym-expansion pair R_i;

a pattern identifier that uses the document d_i, the derived formation rule E_i, the derived (acronym, expansion) pairs R_i, and the patterns P<sub>i−

1</sub>, for deriving a pattern P_i;

wherein the pattern P<sub>i−

1</sub> defines a format in which the acronym and the expansion occur in the document d_i; and

wherein the pattern P<sub>i−

1</sub> is a tuple which is expressed in the following format;

(acronym_prefix, acronym_suffix, expansion_prefix, formation_rule, expansion_suffix), where the acronym_prefix and the acronym_suffix are surrounding characters of the acronym, and the expansion_prefix and the expansion_suffix are surrounding characters of the expansion.

2. A system for automatically and iteratively mining acronyms and expansion in a document d_i through patterns of occurrences and formation rules, comprising:

a database for storing previously identified acronym-expansion pairs R<sub>i−

1</sub>, patterns P<sub>i−

1</sub>, and formation rules E<sub>i−

1</sub>;

a formation rule identifier that uses the acronym-expansion pairs R<sub>i−

1</sub> for deriving a formation rule E_i;

an acronym-expansion pair identifier that uses the document d_i and the patterns P<sub>i−

1</sub>, for deriving an acronym-expansion pair R_i;

a pattern identifier that uses the document d_i, the derived formation rule E_i, the derived acronym-expansion pairs R_i, and the patterns P<sub>i−

1</sub>, for deriving a pattern P_i;

wherein the pattern P<sub>i−

1</sub> defines a format in which the acronym and the expansion occur in the document d_i; and

wherein the pattern P<sub>i−

1</sub> includes a set of individual patterns p_n and is expressed as follows;

3. A system for automatically and iteratively mining acronyms and expansion in a document d_i through patterns of occurrences and formation rules, comprising:

a database for storing previously identified acronym-expansion pairs R<sub>i−

1</sub>, patterns P<sub>i−

1</sub>, and formation rules E_i;

a formation rule identifier that uses the (acronym-expansion) pairs R<sub>i−

1</sub> for deriving a formation rule E_i;

an acronym-expansion pair identifier that uses the document d_i and the patterns P<sub>i−

1</sub> for deriving an (acronym-expansion) pair R_i;

a pattern identifier that uses the document d_i, the derived formation rule E_i, the derived (acronym-expansion) pairs R_i, and the patterns P<sub>i−

1</sub>, for deriving a pattern P_i;

wherein the pattern P<sub>i−

1</sub> defines a format in which the acronym and the expansion occur in the document d_i; and

wherein the acronym-expansion formation rule E<sub>i−

1</sub> defines a format in which the acronym is associated with the expansion.

4. A system for automatically and iteratively mining acronyms and expansion in a document d_i through patterns of occurrences and formation rules, comprising:

a database for storing previously identified (acronym-expansion) pairs R<sub>i−

1</sub>, patterns P<sub>i−

1</sub>, and formation rules E<sub>i−

1</sub>;

a formation rule identifier that uses the (acronym-expansion) pairs R<sub>i−

1</sub> for deriving a formation rule E_i;

an acronym-expansion pair identifier that uses the document d_i and the patterns P<sub>i−

1</sub> for deriving an (acronym-expansion) pair R_i;

a pattern identifier that uses the document d_i, the derived formation rule E_i, the derived (acronym expansion) pairs R_i, and the patterns P<sub>i−

1</sub>, for deriving a pattern P_i;

wherein the pattern P<sub>i−

1</sub> defines a format in which the acronym and the expansion occur in the document d_i; and

wherein the formation rule E<sub>i−

1</sub> includes asset of individual formation rules e_n and is expressed as follows;

5. The system according to claim 4, wherein each individual formation rule e_n includes a sequence of replacement rules that are interspersed with an intermediate.

6. The system according to claim 5, wherein the intermediate includes a string of characters between words in the expansion that are not a part of the acronym.

7. The system according to claim 6, wherein a replacement rule is a tuple expressed as:

(substring_beginPosition, substring_endPosition, replacee, replacer), where the substring_beginPosition is the position of a leading character of the expansion to be placed in the acronym, the substring_endPosition is the position of an ending character of the expansion to be placed in the acronym, the replacee is a substring to be replaced by another substring referred to as the replacer, if any, in the acronym.

8. A computer program product for automatically and iteratively mining acronyms and expansion in a document d_i through patterns of occurrences and formation rules, comprising:

a database for storing previously identified (acronym-expansion) pairs R<sub>i−

1</sub>, patterns P<sub>i−

1</sub>, and formation rules E<sub>i−

1</sub>;

a formation rule identifier that uses the (acronym-expansion) pairs R<sub>i−

1</sub> for deriving a formation rule E_i;

an acronym-expansion pair identifier that uses the document d_i and the patterns P<sub>i−

1</sub> for deriving an (acronym-expansion) pair R_i;

a pattern identifier that uses the document d_i, the derived formation rule E_i, the derived (acronym-expansion) pairs R_i, and the patterns P<sub>i−

1</sub>, for deriving a pattern P_i;

wherein the pattern P<sub>i−

1</sub> defines a format in which the acronym and the expansion occur in document d_i;

wherein the pattern P<sub>i−

1</sub> is a tuple which is expressed in the following format;

(acronym_prefix, acronym_suffix, expansion_prefix, formation_rule, expansion_suffix), where the acronym_prefix and the acronym_suffix are surrounding characters of the acronym, and the expansion_prefix and the expansion_suffix are surrounding characters of the expansion; and

wherein the pattern P<sub>i−

1</sub> includes a set of individual patterns p_n and is expressed as follows;

9. The computer program product according to claim 8, wherein the database stores the derived formation rule E_i, (acronym-expansion) pair R_i, and pattern P_i.

10. A computer program product for automatically and iteratively mining acronyms and expansion in a document d_i through patterns of occurrences and formation rules, comprising:

a database for storing previously identified (acronym-expansion) pairs R<sub>i−

1</sub>, patterns P<sub>i−

1</sub>, and formation rules E<sub>i−

1</sub>;

a formation rule identifier that uses the (acronym-expansion) pairs R<sub>i−

1</sub> for deriving a formation rule E_i;

an acronym-expansion pair identifier that uses the document d_i and the patterns P<sub>i−

1</sub> for deriving an (acronym-expansion) pair R_i;

a pattern identifier that uses the document d_i, the derived formation rule E_i, the derived (acronym-expansion) pairs R_i, and the patterns P<sub>i−

1</sub> for deriving a pattern P_i;

wherein the acronym-expansion formation rule E<sub>i−

1</sub> defines the format in which the acronym is associated with the expansion; and

wherein the formation rule E<sub>i−

1</sub> includes a set of individual formation rules e_n and is expressed as follows;

11. The computer program product according to claim 10, wherein each individual formation rule e_n includes a sequence of replacement rules that are interspersed with an intermediate;

wherein the intermediate includes a string of characters between words in the expansion that are not a part of the acronym; and

wherein a replacement rule is a tuple, expressed as;

(substring_beginPosition, substring_endPosition, replacee, replacer), where the substring_beginPosition is the position of a leading character of the expansion to be placed in the acronym, the substring_endPosition is the position of an ending character of the expansion to be placed in the acronym, the replacee is a substring to be replaced by another substring referred to as the replacer, if any, in the acronym.

12. A method for automatically and iteratively mining acronyms and expansion in a document d_i through patterns of occurrences and formation rules, comprising:

storing previously identified (acronym-expansion) pairs R<sub>i−

1</sub>, patterns P<sub>i−

1</sub>, and formation rules E<sub>i−

1</sub>;

using the (acronym-expansion) pairs R<sub>i−

1</sub> for deriving a formation rule E_i;

using the document d_i and the patterns P<sub>i−

1</sub>for deriving an (acronym-expansion) pair R_i;

using the document d_i, the derived formation rule E_i, the derived (acronym-expansion) pairs R_i, and the patterns P<sub>i−

1</sub>, for deriving a pattern P_i;

further including defining the pattern P<sub>i−

1</sub> by a format in which the acronym and the expansion occur in the document d_i; and

wherein defining the pattern P<sub>i−

1</sub> includes expressing the pattern P<sub>i−

1</sub> by a tuple in the following format;

(acronym_prefix, acronym_suffix, expansion_prefix, formation_rule, expansion_suffix), where the acronym_prefix and the acronym_suffix are surrounding characters of the acronym, and the expansion_prefix and the expansion_suffix are surrounding characters of the expansion.

13. The method according to claim 12, further including storing the derived formation rule E_i, (acronym-expansion) pair R_i, and pattern P_i.

14. The method according to claim 12, further including defining the acronym-expansion formation rule E_i−

1 as a format in which the acronym is associated with the expansion.

15. The method according to claim 14, wherein the formation rule E_i−

1 includes a set of individual formation rules e_n and is expressed as follows;

16. The method according to claim 15, wherein each individual formation rule e_n includes a sequence of replacement rules that are interspersed with an intermediate.

17. The method according to claim 16, wherein the intermediate includes a string of characters between words in the expansion that are not a part of the acronym.

18. The method according to claim 17, wherein a replacement rule is a tuple expressed as:

(substring_beginPosition, substring_endPosition, replacee, replacer), where the substring_beginPosition is the position of a leading character of the expansion to be placed in the acronym, the substring_endPosition is the position of an ending character of the expansion to be placed in the acronym, the replacee is a substring to be replaced by another substring referred to as the replacer, if any, in the acronym.