System for automatically organizing data in accordance with pattern hierarchies therein

• US 6,185,560 B1
• Filed: 04/15/1998
• Issued: 02/06/2001
• Est. Priority Date: 04/15/1998
• Status: Expired due to Term

• Current Assignee: Fidelity Information Services, LLC (Fidelity National Information Services Incorporated)
• Original Assignee: Sungard Eprocess Intelligence LLC (Fidelity National Information Services Incorporated)
• Inventors: Chandy, Vidya S., Young, Kai W., Wu, Aiqun, Steinhart, Eric C.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/060,655
• Time in Patent Office: 1,028 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/101, 707/102, 370/252, 382/227, 702/168
• US Class Current: 707/776
• CPC Class Codes: F25B 2309/06 Compression machines, plants or systems characterised by the refrigerant being carbon dioxide
• CPC Class Codes: F25B 2341/0681 the sensor is heated
• CPC Class Codes: F25B 40/00 Subcoolers, desuperheaters or superheaters
• CPC Class Codes: F25B 49/02 for compression type machines, plants or systems
• CPC Class Codes: F25B 5/02 arranged in parallel
• CPC Class Codes: F25B 9/008 the refrigerant being carbon dioxide
• CPC Class Codes: F25D 17/02 for circulating liquids, e.g. brine
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• 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

Abstract

An information retrieval system processes a report-based data stream which includes report data having text lines comprised of fields, wherein each field is described by the type of data in the field. The system automatically abstracts the text line patterns from the report data by automatically classifying the text lines into species representative of text lines having a predetermined relationship to one another, automatically creating a definition of each species in terms of the species'"'"' constituent fields and automatically creating a virtual table definition specifying the hierarchical relationships among species based on functional type. The system automatically creates tables listing for each text line in the report, the species which the text line best matches, links entries in the list based on relationships specified in the virtual table, and then utilizes the linked list to generate virtual records in response to user-generated queries.

Claims

1. In a system of the type including a computer with associated storage media and a user interface coupled thereto for retrieving information from a report-based stream of data which includes data from a report, the improvement comprising:

a routine executed by the computer, including;

(a) a first portion automatically identifying and defining patterns in data from a report and a hierarchy among such patterns; and

(b) a second portion using the patterns and the hierarchy to automatically extract information from the data to permit creation of virtual records in response to queries.

2. The system of claim 1, wherein the data from a report is arranged in text lines comprised of fields, wherein each field is described by the type of data in it, the patterns identified by the first portion of the routine species of text lines in a report.

3. The system of claim 2, wherein the first portion of the computer routine includes a first sub-portion automatically classifying the text lines into text line species, wherein each species is representative of text lines having a predetermined relationship to one another, and a second sub-portion automatically creating a definition of each species in terms of the constituent fields of the species to form defined species.

4. The system of claim 3, wherein each field is a region of a text line including contiguous characters, and the second sub-portion of the computer routine includes a further sub-portion optimizing the boundaries of each field in a defined species by attempting to expand the left and right boundaries of the field as much as possible without encroaching on adjacent fields.

5. The system of claim 3, wherein the second sub-portion of the routine includes a further sub-portion deleting covered defined species, wherein one defined species is covered by another if all possible text lines which satisfy the definition of the one defined species also satisfy the definition of the other.

6. The system of claim 3, wherein the second sub-portion of the computer routine includes a sub-portion merging all similar defined species and creating a new definition for the merged defined species.

7. The system of claim 2, wherein the second portion of the routine includes a sub-portion automatically scanning a report line-by-line and determining for each line the defined species which the line best matches, and a sub-portion creating a list showing for each text line of the report the defined species which the text line best matches.

8. The system of claim 7, wherein the second portion of the routine further includes a sub-portion automatically generating a virtual table classifying each defined species by functional type based upon the location and frequency of occurrence of that species in the list.

9. The system of claim 8, wherein the second portion of the routine further includes a sub-portion establishing links among defined species in the list based upon functional relationships derived from the virtual table.

10. In a system of the type including a computer with associated storage media and a user interface coupled thereto for retrieving information in a report-based stream of data which includes data from a report arranged in text lines comprised of fields, wherein each field is described by the type of data in the field, the improvement comprising:

a routine executed by the computer, including;

(a) a first portion automatically classifying the text lines into text line species, wherein each species is representative of text lines having a predetermined relationship to one another; and

(b) a second portion automatically creating a definition of each species in terms of the constituent fields of the species to form an inventory of defined species.

11. The system of claim 10, wherein the first portion of the routine includes a first sub-portion creating an initial text line species made up of a first text line, and a second sub-portion comparing each subsequent text line to existing text line species and determining the relationships of the text line to the species.

12. The system of claim 11, wherein the second sub-portion of the routine determines that a text line has one of three possible relationships to existing species:

(a) the text line is already included in a species in that the text line would not alter the species definition;

(b) the text line is related to a species and is added as a member of the species to alter the species definition;

or

(c) the text line is unrelated to an existing species and is used to create a new species.

13. The system of claim 12, wherein a text line is already included in a species if the text line has a degree of membership to the species within a predetermined threshold and corresponds to the species as to field data type and inter-field space regions, wherein the degree of membership of a text line to a species is determined by the average similarity of character types at each character position.

14. The system of claim 11, wherein the first portion of the routine includes a sub-portion constructing for each species a template which is a listing of the most predominant character class for each character position in the collection of lines making up the species.

15. The system of claim 14, wherein said third sub-portion of the routine includes a portion constructing an initial template using a first text line in a collection of text lines, and a portion adjusting the template after each text line is added as a member of the species by comparing all current members of the species to the template for conformance with the predominant character class representation at each character position and, if more than half the current members fail to conform to the template, using all the members to find the character class with the maximum frequency at each character position and replacing the template at that position with the new character class representation.

16. The system of claim 10, wherein the routine includes a third portion automatically generating a virtual table classifying each species by functional type based upon the location and frequency of occurrence of that species in a list of species best matched by each text line in the report.

17. The system of claim 16, wherein the third portion of the routine includes a portion sorting the line species in the virtual table in the order of header species, detail species and trailer species, wherein detail species are species with high occurrence frequency and high variation on location, header species are species which occur before the first detail species and trailer species are species which occur after the last detail species.

18. The system of claim 10, wherein the defined species make up an inventory, the routine further including a portion for improving the inventory by applying the inventory to a stream of data and automatically adjusting the inventory to include every text line in the stream.

19. The system of claim 18, wherein the third portion of the routine includes a portion which classifies each text line in the data stream to determine whether the text line matches a defined species definition exactly, partially or not at all, creates a collection of unmatched text lines and automatically classifies the collection into new species;

and a portion determining whether any partially matched text line more closely matches the defined species definition which the partially matched text line partially matches or the definition of a new species and, if the former, adds the text line to the partially matched defined species and rebuilds the species definition accordingly and, if the latter, includes the text line in the collection of unmatched text lines and adds the text line to an existing new species or creates an additional new species for the text line.

20. In a system of the type including a computer with associated storage media and a user interface coupled thereto for retrieving meaningful information from a report-based stream of data which includes data from a report arranged in text lines, wherein there exists a classification of the text lines into species such that each species is representative of text lines having a predetermined relationship to one another, the improvement comprising:

a routine executed by the computer, including;

(a) a first portion automatically scanning data from a report line-by-line and determining for each text line the species which the text line best matches; and

(b) a second portion creating a list showing for each text line of the report the species which the text line best matches.

21. The system of claim 20, wherein the routine further includes a third portion establishing links among species in the list based upon functional relationships.

22. A computer-implemented method for retrieving meaningful information from a report-based stream of data which includes data from a report, the method comprising:

automatically identifying and defining patterns in data from a report and a hierarchy among such patterns; and

utilizing the patterns and the hierarchy to automatically extract information from the data to permit creation of virtual records in response to queries.

23. A computer-implemented method for retrieving information in a report-based stream of data which includes data from a report arranged in text lines comprised of fields, wherein each field is described by the type of data in the field, the method comprising:

automatically classifying the text lines into text line species, wherein each species is representative of text lines having a predetermined relationship to one another; and

automatically creating a definition of each species in terms of the species'"'"' constituent fields to form defined species.

24. A computer-implemented method for obtaining meaningful information from a report-based stream of data which includes data from a report arranged in text lines, wherein there exists a classification of the text lines into species such that each species is representative of text lines having a predetermined relationship to one another, the method comprising:

automatically scanning data from a report line-by-line and determining for each text line the species which the text line best matches; and

creating a list showing for each text line of the report the species which the text line best matches.