Method for parsing natural language text with constituent construction links

• US 10,810,368 B2
• Filed: 07/19/2018
• Issued: 10/20/2020
• Est. Priority Date: 07/10/2012
• Status: Active Grant

• Current Assignee: Robert D. New
• Original Assignee: Robert D. New
• Inventors: New, Robert D.
• Primary Examiner(s): Lerner, Martin
• Application Number:
  US16/040,254
• Publication Number:
  US 20180322111A1
• Time in Patent Office: 824 Days
• Field of Search: 704 1, 704 8, 704 9, 704 10, 717143
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30

Abstract

A parser for natural language text is provided. The parser is trained by accessing a corpus of labeled utterances. The parser extracts details of the syntactic tree structures and part of speech tags from the labeled utterances. The details extracted from the tree structures include Simple Links which are the key to the improved efficiency of this new approach. The parser creates a language model using the details that were extracted from the corpus. The parser then uses the language model to parse utterances.

Claims

1. A method for improving a natural language parser to parse natural language text, the method comprising:

a) using the parser to generate at least one constituent construction link for at least one source word in at least one additional utterance;

where said constituent construction link consists of a source word, a target word, and a link action,

where said link action can be chosen from a set of link action values where said values include at least 2 values from Append, Insert Below, Insert Above and Below;

b) using the at least one constituent construction link to generate at least one constituent tree structure that represents a sentence parse result for each additional utterance by performing determination steps and repeating the determination steps, where the determination steps include;

i. if this is an initial constituent construction link for the additional utterance, create a first word node for a first word of the additional utterance, and create a new node and make it a parent of the first word node;

ii. create a source word node for the source word;

iii. find a highest node above a target word of the constituent construction link wherein the target word is either a first child of the highest node, or wherein the target word is a descendent of the first child of the highest node and is also a descendent of the first child of all intervening nodes between the highest node and the target word, and designate the highest node as a highest right most node;

iv. add one or more nodes to the constituent tree structure at locations relative to the highest right most node if directed by the link action of the Constituent Construction Link;

v. attach the source word node of the source word to the constituent tree structure at a point relative to the highest right most node based on the link action of the Constituent Construction Link.

2. The method of claim 1, including providing a non-transitory computer-readable storage medium having instructions that develop a parser for use in natural language processing.

3. The method of claim 1, including providing an improved natural language parser to a memory unit of a computer system having a system processor.

4. The method of claim 1, including providing access to a language model in a data storage system of a computer system having a reader and a writer for reading and writing data from the data storage system, relaying information, accepting input generated by a user and parsing the user generated input.

5. The method of claim 1, wherein the constituent tree structure is output.

6. The method of claim 1, wherein the at least one Constituent Construction Link is or are output.

7. The method of claim 1, further comprising construction steps wherein:

if the link action is Append, make the source word node a child of the highest right most node.

8. The method of claim 1, further comprising construction steps wherein:

if the link action is Insert Below, create a new node, make the new node a child of the highest right most node and make the node for the source word a child of the new node.

9. The method of claim 1, further comprising construction steps wherein:

if the link action is Insert Above;

(a) and if the highest right most node DOES NOT have a parent, create a new node, make the new node the parent of the highest right most node, and make the node of the source word a child of the new node;

(b) and if the highest right most node DOES have a parent, separate the highest right most node and its parent, create a new node, make the new node a child of the node that was the parent of the highest right most node, make the highest right most node a child of the new node, and make the node of the source word a child of the new node.

10. The method of claim 1, further comprising construction steps wherein:

if the link action is Insert Above and Below;

(a) and if the highest right most node DOES NOT have a parent, create a first new node, make the first new node the parent of the highest right most node, create a second new node, make the second new node a child of the first new node, and make the node of the source word a child of the second new node;

(b) and if the highest right most node DOES have a parent, separate the highest right most node and its parent, create a first new node, make the first new node a child of the node that was the parent of the highest right most node, make the highest right most node a child of the first new node, create a second new node, make the second new node a child of the first new node, and make the node of the source word a child of the second new node.