Associative memory processing method for natural language parsing and pattern recognition

• US 5,619,718 A
• Filed: 11/13/1995
• Issued: 04/08/1997
• Est. Priority Date: 05/08/1992
• Status: Expired due to Fees

• Current Assignee: Nelson Correa
• Original Assignee: Nelson Correa
• Inventors: Correa, Nelson
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): HARRITY, JOHN E
• Application Number:
  US08/557,729
• Time in Patent Office: 512 Days
• Field of Search: 395/800, 395/700, 395/435, 364/253, 364/DIG. 1
• US Class Current: 704/9
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique

Abstract

An associative memory processor architecture is disclosed for the fast and efficient execution of parsing algorithms for natural language processing and pattern recognition applications. The architecture consists of an associative memory unit for the storage of parsing state representations, a random access memory unit for the storage of the grammatical rules and other tables according to which the parsing is done, a finite state parsing control unit which embodies the chosen parsing algorithm, and a communications unit for communication with a host processor or external interface. The use of associative memory for the storage of parsing state representations allows the architecture to reduce the algorithmic time complexity of parsing algorithms both with respect to grammar size and input string length, when compared to standard software implementations on general purpose computers. The disclosed architecture provides for a fast and compact computer peripheral or system, particularly when physically realized in one or a small number of integrated circuit chips, and thus contributes to the technical feasibility, of real time applications in speech recognition, machine translation, and syntactic pattern recognition.

Claims

1. A method of executing parsing algorithms on an associative memory processing system against a given grammar and input string, the grammar being comprised of a plurality of grammar rules, each of which has one left-hand side symbol, and zero or more right-hand side symbols, said method comprising the steps of:

storing a plurality of grammar rules in a memory, according to numeric codes for the symbols of each grammar rule, and in an order of the grammar rules;

defining a predetermined parsing algorithm, and a numeric encoding of each of the parsing states used by the parsing algorithm, so that each such encoding, referred to as a parsing state representation, may be stored in one associative memory word so as to allow retrieval by multiple access patterns;

storing the parsing state representations generated by the algorithm in the associative memory means, and distinguishing unprocessed parsing states from those parsing states already processed by the algorithm;

accessing the associative memory means with a first retrieval condition for retrieval of unprocessed parsing states;

using parsing control means for the processing of unprocessed parsing states retrieved from the associative memory means, such processing including marking the current unprocessed parsing state as processed, and yielding potentially new unprocessed parsing states;

accessing the associative memory means with a second retrieval condition for testing the presence of a potentially new unprocessed parsing state in the associative memory, and if such is the case, inhibiting the writing of the potentially new unprocessed parsing state into the associative memory; and

accessing the associative memory means with further retrieval conditions for retrieving parsing states that meet certain criteria, required for processing of unprocessed parsing states and for optimizations of the processing to be performed.

2. The method of executing parsing algorithms as claimed in claim 1, wherein each retrieval from the associative memory means is performed in a parallel manner, in an amount of time which is independent of the number of parsing state representations stored in the associative memory means.

3. The method of claim 1, further comprising the step of ordering the grammar rules in the memory according to the left-hand symbol.

4. The method of claim 1, further comprising the step of assigning a unique numeric code to each grammar symbol and a separate numeric code to each grammatical rule according to an order selected for grammatical rules.