Automated learning parsing system

• US 20030144978A1
• Filed: 01/08/2003
• Published: 07/31/2003
• Est. Priority Date: 01/17/2002
• Status: Abandoned Application

• Current Assignee: Estarta Solutions
• Original Assignee: Estarta Solutions
• Inventors: Zeine, Hatem I.
• Application Number:
  US10/338,003
• Publication Number:
  US 20030144978A1
• Time in Patent Office: Days
• US Class Current: 706/47
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

An automated learning parsing system that utilizes a method for inferring context-free grammars. The automated learning parsing system utilizes two algorithms, a learning parser algorithm and a generic parser algorithm. The two algorithms are combined in such a way that the output of the first algorithm is the input to the second algorithm. The learning parser algorithm produces a grammar based on input data and the generic parser algorithm uses the induced grammar for identifying patterns depending on the application at hand.

Claims

1. An automated learning parsing system, comprising:

a computer network system having a parsing station network and a parsing subdata network for automatically learning and generating grammar and rules from at least one input data set(s), said computer network system having at least one resident data storage facility, a microprocessor and a display monitor;

a learning parser algorithm stored on said computer network system and operating under the direction of said microprocessor, the learning parser algorithm including;

an LPParse function means for parsing the input data set and constructing all possible rules;

an LPUpdateFrequency function means for updating the frequency of occurrence of each rule; and

an LPTrim function means for removing all insignificant rules;

a generic parser algorithm stored on said computer network system and operating under the direction of said microprocessor to use the induced grammar for identifying patterns depending on the application at hand; and

said input data set that is selectively retrieved from the parsing station network and the parsing subdata network, which is able to automatically read and learn the given input data and generate the grammar and rules describing the structure of said input data set.

2. The system according to claim 1, wherein every grammar or rule has a derived code, left side code, right side code, frequency of the rule and scope of the rule.

3. The system according to claim 1, wherein the grammar and rules are stored in a resident data storage facility in the form of a rule packet array.

4. The system according to claim 1, wherein the grammar and rules are searched for according to a sort packet array.

5. The system according to claim 1, wherein the grammar and rules are positioned according to a cell offset array.

6. The system according to claim 1, wherein every parse leaf is made up of an instantiated code and a terminal cell position.

7. The system according to claim 1, wherein parsing can be formulated in tabular form.

8. The system according to claim 1, wherein the learning parser algorithm is capable of automatically generating grammars for the generic parser algorithm to parse against by parsing representative samples of the input data set that conform to recognized patterns.

9. The system according to claim 1, wherein said system automatically creates, learns and detects grammar for any data, information, knowledge, language or pattern base by processing the input data set and automatically using an induced grammar to identify and recognize certain patterns without user intervention.

10. A method for inferring context-free grammars, comprising the steps of:

retrieving at least one input data set;

refining the input data set until relevant grammar and rules are developed via a loop comprising the steps of;

parsing input data set and constructing all possibilities;

updating the frequency of each grammar and rule; and

trimming all insignificant grammar and rule.