METHOD FOR PARSING NATURAL LANGUAGE TEXT WITH CONSTITUENT CONSTRUCTION LINKS

• US 20180322111A1
• Filed: 07/19/2018
• Published: 11/08/2018
• Est. Priority Date: 07/10/2012
• Status: Active Grant

• Current Assignee: Robert D. New
• Original Assignee: Robert D. New
• Inventors: New, Robert D.
• Granted Patent: US 10,810,368 B2
• Time in Patent Office: Days
• 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 processor in communication with a memory storing a program which uses a parser to parse natural language text, said method comprising:

a) training said parser by accessing a corpus of labeled utterances;

b) using said parser to extract details from said corpus, where said details include at least two simple links, where a simple link consists of a source word in the utterance, a target word in the utterance that is distinct from said source word, and a link action, said link action is chosen from a set of link actions which includes at least 2 of Append, Insert Below, Insert Above, and Insert Above and Below;

c) using said parser to create a language model using said details;

d) using said language model to generate at least two new simple links for at least two source words in at least one additional utterance;

e) using said new simple links to generate a constituent tree structure that represents the sentence parse result for said additional utterance by performing determination steps and repeating the determination steps until the required nodes for each new simple link have been added to said constituent tree, where the determination steps include;

i. if this is the first new simple link for said additional utterance, create a new node for the first word of said additional utterance, also create a node and make it the parent of this new node;

ii. create a new node for the source word;

iii. find the highest node above the target node of the simple link, for which the target node is either the first child of said highest node, or for which the target node is a descendent of the first child of said highest node and is also a descendent of the first child of all intervening nodes between said highest node and the target node, and herein designate said node as the highest right most node;

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

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

vi. if the link action is Insert Above and the highest right most node DOES NOT have a parent, create a new node, make said new node the parent of the highest right most node, and make the node of the source word a child of said new node;

vii. if the link action is Insert Above and the highest right most node DOES have a parent, separate the highest right most node and its parent, create a new node, make said 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 said new node, and make the node of the source word a child of said new node;

viii. if the link action is insert Above and Below and the highest right most node DOES NOT have a parent, create a first new node, make said first new node the parent of the highest right most node, create a second new node, make said second new node a child of said first new node, and make the node of the source word a child of said second new node;

ix. if the link action is Insert Above and Below and the highest right most node DOES have a parent, separate the highest right most node and its parent, create a first new node, make said 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 said first new node, create a second new node, make said second new node a child of said first new node, and make the node of the source word a child of said second new node;

f) outputting the results of said parsing of said additional utterance as an array of simple links and said constituent tree structure with the additional utterance.

2. A non-transitory computer-readable storage medium having instructions that develop a parser for use In natural language processing, the instructions comprising:

a) training said parser by accessing a corpus of labeled utterances;

b) using said parser to extract details from said corpus, where said details include at least two simple links, where a simple link consists of a source word in the utterance, a target word in the utterance that is distinct from said source word, and a link action, said link action is chosen from a set of link actions which includes at least 2 of Append, Insert Below, Insert Above, and Insert Above and Below;

c) using said parser to create a language model using said details;

d) using said language model to generate at least two new simple links for at least two source words in at least one additional utterance;

e) using said new simple links to generate a constituent tree structure that represents the sentence parse result for said additional utterance by performing determination steps and repeating the determination steps until the required nodes for each new simple link have been added to said constituent tree, where the determination steps include;

i. if this is the first new simple link for said additional utterance, create a new node for the first word of said additional utterance, also create a node and make it the parent of this new node;

ii. create a new node for the source word;

iii. find the highest node above the target node of the simple link, for which the target node is either the first child of said highest node, or for which the target node is a descendent of the first child of said highest node and is also a descendent of the first child of all Intervening nodes between said highest node and the target node, and herein designate said node as the highest right most node;

iv. If the link action is Append, make the node for the source word a child of the highest right most node;

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

vi. If the link action is Insert Above and the highest right most node DOES NOT have a parent, create a new node, make said new node the parent of the highest right most node, and make the node of the source word a child of said new node;

vii. If the link action is Insert Above and the highest right most node DOES have a parent, separate the highest right most node and its parent, create a new node, make said 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 said new node, and make the node of the source word a child of said new node;

viii. if the link action is Insert Above and Below and the highest right most node DOES NOT have a parent, create a first new node, make said first new node the parent of the highest right most node, create a second new node, make said second new node a child of said first new node, and make the node of the source word a child of said second new node;

ix. if the link action is Insert Above and Below and the highest right most node DOES have a parent, separate the highest right most node and its parent, create a first new node, make said 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 said first new node, create a second new node, make said second new node a child of said first new node, and make the node of the source word a child of said second new node;

f) outputting the results of said parsing of the additional utterance as an array of simple links and said constituent tree structure.

3. A method for providing an improved natural language parser to a memory unit of a computer system having a system process, the method comprising the steps of:

a) training said parser by accessing a corpus of labeled utterances;

b) using said parser to extract details from said corpus, where said details include at least two simple links, where a simple link consists of a source word in the utterance, a target word in the utterance that is distinct from said source word, and a link action, said link action is chosen from a set of link actions which includes at least 2 of Append, Insert Below, Insert Above, and Insert Above and Below;

c) using said parser to create a language model using said details;

d) using said language model to generate at least two new simple links for at least two source words in at least one additional utterance;

e) using said new simple links to generate a constituent tree structure that represents the sentence parse result for said additional utterance by performing determination steps and repeating the determination steps until the required nodes for each new simple link have been added to said constituent tree, where the determination steps include;

i. if this is the first new simple link for said additional utterance, create a new node for the first word of said additional utterance, also create a node and make it the parent of this new node;

ii. create a new node for the source word;

iii. find the highest node above the target node of the simple link, for which the target node is either the first child of said highest node, or for which the target node is a descendent of the first child of said highest node and is also a descendent of the first child of all intervening nodes between said highest node and the target node, and herein designate said node as the highest right most node;

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

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

vi. if the link action is Insert Above and the highest right most node DOES NOT have a parent, create a new node, make said new node the parent of the highest right most node, and make the node of the source word a child of said new node;

vii. if the link action is Insert Above and the highest right most node DOES have a parent, separate the highest right most node and its parent, create a new node, make said 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 said new node, and make the node of the source word a child of said new node;

viii. if the link action is Insert Above and Below and the highest right most node DOES NOT have a parent, create a first new node, make said first new node the parent of the highest right most node, create a second new node, make said second new node a child of said first new node, and make the node of the source word a child of said second new node;

ix. if the link action is Insert Above and Below and the highest right most node DOES have a parent, separate the highest right most node and its parent, create a first new node, make said 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 said first new node, create a second new node, make said second new node a child of said first new node, and make the node of the source word a child of said second new node;

f) make the array of said simple links, said constituent tree structure and the user generated input, available for future requests from a service.

4. A method for accessing a language model in a data storage system of a computer system having means for reading and writing data from the data storage system, relaying information, and accepting input generated by a user;

parsing the user generated input, the method comprising the steps of;

a) training said parser by accessing a corpus of labeled utterances;

b) using said parser to extract details from said corpus, where said details include at least two simple links, where a simple link consists of a source word in the utterance, a target word in the utterance that is distinct from said source word, and a link action, said link action is chosen from a set of link actions which includes at least 2 of Append, Insert Below, Insert Above, and Insert Above and Below;

c) using said parser to create a language model using said details;

d) using said language model to generate at least two new simple links for at least two source words in at least one additional utterance;

e) using said new simple links to generate a constituent tree structure that represents the sentence parse result for said additional utterance by performing determination steps and repeating the determination steps until the required nodes for each new simple link have been added to said constituent tree, where the determination steps include;

i. if this is the first new simple link for said additional utterance, create a new node for the first word of said additional utterance, also create a node and make it the parent of this new node;

ii. create a new node for the source word;

iii. find the highest node above the target node of the simple link, for which the target node is either the first child of said highest node, or for which the target node is a descendent of the first child of said highest node and is also a descendent of the first child of all intervening nodes between said highest node and the target node, and herein designate said node as the highest right most node;

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

v. If the link action is Insert Below, create a new node, make it a child of the highest right most node and make the node for the source word a child to this new node;

vi. if the link action is Insert Above and the highest right most node DOES NOT have a parent, create a new node, make said new node the parent of the highest right most node, and make the node of the source word a child of said new node;

vii. if the link action is Insert Above and the highest right most node DOES have a parent, separate the highest right most node and its parent, create a new node, make said 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 said new node, and make the node of the source word a child of said new node;

viii. if the link action is Insert Above and Below and the highest right most node DOES NOT have a parent, create a first new node, make said first new node the parent of the highest right most node, create a second new node, make said second new node a child of said first new node, and make the node of the source word a child of said second new node;

ix. If the link action is Insert Above and Below and the highest right most node DOES have a parent, separate the highest right most node and its parent, create a first new node, make said 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 said first new node, create a second new node, make said second new node a child of said first new node, and make the node of the source word a child of said second new node;

f) relaying the resulting array of said simple links, said constituent tree structure and said user generated input, to further modules which perform specific computer operations.

5. A method for improving a processor in communication with a memory storing a program which uses a parser to parse natural language text, the method comprising:

a) training the parser by accessing a corpus of utterances, which utterances are labelled with marks which specify the constituent tree for each of the utterances;

b) using the parser to extract details from the corpus, where the details include at least one constituent construction link, where each constituent construction link consists of a source word in the utterance, a target word in the utterance that is distinct from the source word, and a link action; and

c) finding a common ancestor of the source word, a previous word, and a left-most descendent of the common ancestor which becomes the target word for the constituent construction link, and thereby defining a relationship of the source word to the target word in terms of nodes in the constituent tree and Identifying the link action based on this relationship.

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

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

8. The method of claim 5, 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.

9. The method of claim 5, further including using the trained parser to parse at least one addition utterance, where parsing is accomplished by various parsing methods.

10. The method of claim 5, wherein the relationship is defined by:

determining if a parent of the source word is also a parent of the previous word, and if so, the link action identified is Append.

11. The method of claim 5, wherein the relationship is defined by:

determining if a parent of the source word is a child of a parent of the previous word, and if so, the link action Identified is Insert Below.

12. The method of claim 5, wherein the relationship is defined by:

finding a child node of the common ancestor that Is a parent or ancestor to the source word, and determining a position of a child node, which position will be numbered sequentially, and if the position of the child is 3 or greater, the link action identified is Insert Below.

13. The method of claim 5, wherein the relationship is defined by:

determining if a parent of the source word is the same as the common ancestor and a parent of the target word is not the common ancestor, then the link action identified is Insert Above.

14. The method of claim 5, wherein the relationship is defined by:

determining if none of the following conditions exist, the link action selected is Insert Above and Below

i. determining if a parent of the source word is also a parent of the previous word, and if so, the link action Identified is Append;

ii. determining if the parent of the source word is a child of the parent of the previous word, and if so, the link action identified is Insert Below

iii. finding a child node of the common ancestor that is a parent or ancestor to the source word, and determining a position of the child node, which position will be numbered sequentially, and if the position of the child is 3 or greater, the link action identified is Insert Below; and

iv. determining if the parent of the source word is the same as the common ancestor and the parent of the target word is not the common ancestor and the parent of the target word is not the common ancestor, then the link action identified is Insert Above.

15. A method for improving a processor in communication with a memory storing a program which uses a 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;

b) using the new constituent construction links 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 the target word of the constituent construction link for which the target word is either a first child of the highest node, or for which 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 so indicated by the type of 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 type of link action of the Constituent Construction Link.

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

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

18. The method of claim 15, 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.

19. The method of claim 15, wherein the constituent tree structure is output.

20. The method of claim 15, wherein the new Constituent Construction Links are output.

21. The method of claim 15, further comprising construction steps wherein:

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

22. The method of claim 15, 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.

23. The method of claim 15, 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.

24. The method of claim 15, 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.

25. The method of claim 15, further comprising construction steps wherein:

vi. if the link action is Insert Above or Append;

(a) and if there is a node below the highest right most node with nodes for words to the right of the target word, make the node of the source word a child of the highest right most node (Append);

(b) and if there are not any nodes below the highest right most node with nodes for words to the right of the target word, and 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 (Insert Above);

(c) and if there are not any nodes below the highest right most node with nodes for words to the right of the target word, and the highest right most node DOES have a parent, then 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 (Insert Above).

26. The method of claim 15, further comprising construction steps wherein:

if the link action is Insert Above and Below or Append;

(a) and if there is a node below the highest right most node with nodes for words to the right of the target word, make the node of the source word a child of the highest right most node (Append);

(b) and if there are not any nodes below the highest right most node with nodes for words to the right of the target word, and 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, create a second new node, make this second node a child of the first new node, and make the node of the source word a child of the second new node (Insert Above and Below);

(c) and if there are not any nodes below the highest right most node with nodes for words to the right of the target word, and the highest right most node DOES have a parent, then 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, make a second new node, make this 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 (Insert Above and Below).

27. The method of claim 15, further comprising construction steps wherein:

if the link action is Insert Above or Insert Below;

(a) and if there is a node below the highest right most node with nodes for words to the right of the target word, create a new node, make the new node a child of the highest right most node, and make the node of the source word a child of the new node (Insert Below);

(b) and if there are not any nodes below the highest right most node with nodes for words to the right of the target word, and 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 (Insert Above);

(c) and if there are not any nodes below the highest right most node with nodes for words to the right of the target word, and the highest right most node DOES have a parent, then 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 (Insert Above).

28. The method of claim 15, further comprising construction steps wherein:

if the link action is Insert Above and Below or Insert Below;

(a) and if there is a node below the highest right most node with nodes for words to the right of the target word, create a new node, make the new node a child of the highest right most node, and make the node of the source word a child of the new node (Insert Below);

(b) and if there are not any nodes below the highest right most node with nodes for words to the right of the target word, and 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, create a second new node, make the second node a child of the first new node, and make the node of the source word a child of the second new node (Insert Above and Below);

(c) and if there are not any nodes below the highest right most node with nodes for words to the right of the target word, and the highest right most node DOES have a parent, then 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, 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 (Insert Above and Below).

29. The method of claim 15, further comprising construction steps wherein:

if the link action is Insert Below or Append;

(a) and if there is a node below the highest right most node with nodes for words to the right of the target word, create a new node, make the new node a child of the highest right most node, and make the node of the source word a child of the new node (Insert Below);

(b) and if there are not any nodes below the highest right most node with nodes for words to the right of the target word, make the node of the source word a child of the highest right most node (Append).