Natural language processing system and method

• US 9,152,623 B2
• Filed: 11/04/2013
• Issued: 10/06/2015
• Est. Priority Date: 11/02/2012
• Status: Active Grant

• Current Assignee: Samurai Labs SP Z OO
• Original Assignee: Fido Labs, Inc.
• Inventors: Krupa, Tomasz, Leliwa, Gniewosz, Wiacek, Piotr, Wroczyski, Michal, Staczyk, Michal
• Primary Examiner(s): SPOONER, LAMONT M
• Application Number:
  US14/071,631
• Publication Number:
  US 20140136188A1
• Time in Patent Office: 701 Days
• Field of Search: 704/1, 704/9, 704/10, 707706-708, 707/1, 707/9, 707/10
• US Class Current: 1/1
• 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/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06F 40/55 Rule-based translation
• CPC Class Codes: G06F 40/56 Natural language generation

Abstract

A natural language processing system is disclosed herein. Embodiments of the NLP system perform hand-written rule-based operations that do not rely on a trained corpus. Rules can be added or modified at any time to improve accuracy of the system, and to allow the same system to operate on unstructured plain text from many disparate contexts (e.g. articles as well as twitter contexts as well as medical articles) without harming accuracy for any one context. Embodiments also include a language decoder (LD) that generates information which is stored in a three-level framework (word, clause, phrase). The LD output is easily leveraged by various software applications to analyze large quantities of text from any source in a more sophisticated and flexible manner than previously possible. A query language (LDQL) for information extraction from NLP parsers'"'"' output is disclosed, with emphasis on its embodiment implemented for LD. It is also presented, how to use LDQL for knowledge extraction on the example of application named Knowledge Browser.

Claims

1. A system for natural language processing comprising:

a processor configured to execute a natural language processing method, the method comprising,

the processor receiving input data from one or more data sources, wherein the input data comprises one or more of plain text, and tokenized text;

the processor tokenizing the text;

the processor aggregating tokens into a three-level structure comprising a word level, a phrase level, and a clause level wherein,

tokens are aggregated into words, words are aggregated into phrases, and phrases are aggregated into clauses;

each element on a higher level comprises one or more elements of a lower level;

tokens that are one or more of coordinating and subordinating words within a phrase are aggregated into one or more words that are separate from respective, coordinated or subordinated words, and the one or more of coordinating and subordinating words and their respective, coordinated or subordinated words are aggregated into one phrase;

words that are one or more of coordinating and subordinating phrases within a clause are aggregated into one or more phrases that are separate from respective, coordinated or subordinated phrases, and the one or more of coordinating and subordinating phrases and their respective, coordinated or subordinated phrases are aggregated into one clause; and

phrases that are one or more of coordinating and subordinating clauses are aggregated into one or more clauses that are separate from their respective coordinated or subordinated clauses;

the processor determining syntactic connections between at least,

every clause and its syntactically superior clause in the same sentence;

every clause and its syntactically superior phrase, if they exist within the same sentence;

every phrase and its syntactically superior phrase within the same clause; and

every word and its syntactically superior word within the same phrase; and

wherein,

an element without its syntactically superior element becomes a root element;

if one or more coordinated elements have a common syntactically superior element, the coordinated elements are connected to their respective coordinating element, and the coordinating element is connected to the element which is syntactically superior to the respective coordinated elements; and

if one or more coordinated elements are all syntactically superior to an element, the syntactically subordinated element is connected to the element coordinating its respective syntactically superior elements; and

the processor classifying each word, phrase and clause, wherein

classification reflects a syntactic function of the word, the phrase and the clause; and

phrases and clauses share a partially common set of possible syntactic functions comprising at least subject, object, complement and attribute function.

2. The system of claim 1, wherein the natural language processing method comprises executing a plurality of functional modules for performing a natural language processing function, and wherein the processor is further configured to execute a clause divider module of the plurality of functional modules comprising:

the processor receiving text divided into words from one or more of, another of the plurality of modules, and input data, wherein input data comprises data from a system external to the natural language processing system;

the processor grouping the words into clauses;

the processor determining connections between the clauses; and

the processor classifying the clauses.

3. The system of claim 2, wherein grouping the words into clauses comprises the processor considering sequences of one or more words to be grouped into clauses, wherein:

the sequences of words are aggregated into clauses in an order in which they appear in the input data; and

the decision to aggregate the sequence of one or more words into particular clauses is influenced by decisions regarding previous sequences, and a current state of the clauses at the time of considering the sequence.

4. The system of claim 3, wherein grouping the words into clauses comprises the processor first preliminarily choosing words that are probable to divide clauses.

5. The system of claim 3, wherein the clause divider module comprises a correctness evaluator configured to continually assess the correctness of the clause division process and wherein the clause divider module employs a set of rules for dividing words into clauses, the rules comprising:

default instructions; and

alternative instructions used when default instructions cause an error detected by the correctness evaluator.

6. The system of claim 1, wherein the natural language processing method comprises executing a plurality of functional modules for performing a natural language processing function, and wherein the processor is further configured to execute an accommodation module of the plurality of functional modules comprising:

the processor receiving text divided into words from one or more of, another of the plurality of modules, and input data, wherein input data comprises data from a system external to the natural language processing system;

the processor grouping the words into phrases;

the processor determining connections between the phrases; and

the processor classifying the phrases.

7. The system of claim 6, wherein:

determining connections between the phrases comprises considering the phrases in an order in which they appear in the input data;

determining connections is influenced by the decision regarding connections of previous phrases.

8. The system of claim 6, wherein one or more of determining connections between the phrases and classification of phrases comprises using a semantic n-gram database.

9. The system of claim 6, wherein determining connections between the phrases comprises performing a test to determine the most probable of different possible connections.

10. The system of claim 9, wherein the test comprises evaluating whether replacement of certain phrases changes the sense of other phrases in a context of the input data.

11. The system of claim 10, wherein the test uses a semantic n-gram database to evaluate whether replacement of certain phrases changes a sense of other phrases in a context of the input data.

12. The system of claim 1, wherein one or more of aggregation into groups, determining connection between elements, and classifying the elements.

13. A computer-implemented method for processing text, the method comprising:

a processor configurable to execute a natural language processing application receiving input data from one or more data sources, wherein the input data comprises one or more of plain text, and tokenized text;

the processor tokenizing the text;

the processor aggregating tokens into three-level structure comprising word level, phrase level and clause level, wherein,

tokens are aggregated into words, words into phrases and phases into clauses;

each element on lower level is assigned to exactly one element of higher level;

each element on higher level comprises one or more elements of lower level;

tokens that are coordinating or subordinating words within a phrase are aggregated into one or more words that are separate from their respective coordinated or subordinated words, and both the coordinating or subordinating words and their respective coordinated or subordinated words are aggregated into one phrase;

words that are coordinating or subordinating phrases within a clause are aggregated into one or more phrases that are separate from their respective coordinated or subordinated phrases, and both the coordinating or subordinating phrases and their respective coordinated or subordinated phrases are aggregated into one clause; and

phrases that are coordinating or subordinating clauses are aggregated into one or more clauses that are separate from their respective coordinated or subordinated clauses;

the processor determining syntactic connections between at least

every clause and its syntactically superior clause at the same sentence;

every clause and its syntactically superior phrase if exists within the same sentence;

every phrase and its syntactically superior phrase within the same clause; and

every word and its syntactically superior word within the same phrase, and wherein;

element without its syntactically superior element becomes root element;

if one or more coordinated elements have common syntactically superior element, the coordinated elements are connected to their respective coordinating element, and the coordinating element is connected to the element which is syntactically superior to the respective coordinated elements; and

if one or more coordinated elements are all syntactically superior to an element, the syntactically subordinated element is connected to the element coordinating its respective syntactically superior elements; and

the processor classifying each word, phrase and clause, wherein,

classification reflects syntactic function of the word, the phrase and the clause; and

phrases and clauses share partially common set of possible syntactic functions comprising at least subject, object, complement and attribute function.

14. The method of claim 13 further comprising the processor executing a plurality of modules for performing a natural language processing function, wherein the method further comprises executing a clause divider module of the plurality of modules comprising:

the processor receiving text divided into words from one or more of, another of the plurality of modules, and input data, wherein input data comprises data from a system external to the natural language processing system;

the processor grouping the words into clauses;

the processor determining connections between the clauses; and

the processor classifying the clauses.

15. The method of claim 14, wherein grouping the words into clauses comprises considering sequences of words to be grouped into clauses, wherein:

the sequences of words are aggregated into clauses in an order in which they appear in the input data; and

the decision to aggregate the sequence of one or more words into a particular clause is influenced by decisions regarding previous sequences and a current state of clauses at the time of considering the sequence.

16. The method of claim 15, wherein grouping the words into clauses comprises first preliminarily choosing words that are probable to divide clauses.

17. The method of claim 15, wherein the clause divider module comprises a correctness evaluator for continually assessing the correctness of the clause division process, and wherein the clause divider module employs a set of rules for dividing words into clauses, the rules comprising:

default instructions; and

alternative instructions used when default instructions cause an error detected by the correctness evaluator.

18. The method of claim 13, further comprising the processor executing an accommodation module of the plurality of modules comprising:

the processor receiving text divided into words from one or more of, another of the plurality of modules, and input data, wherein input data comprises data from a system external to the natural language processing system, and;

the processor grouping words into phrases;

the processor determining connections between the phrases; and

the processor classifying the phrases.

19. The method of claim 18, wherein determining connections between the phrases comprises considering the phrases in an order in which they appear in the input data;

and

the decision regarding determining connection is influenced by decision regarding the connections of previous phrases.

20. The method of claim 18, wherein one or more of determining connections between phrases and classification of phrases comprises using a semantic n-gram database.

21. The method of claim 18, wherein determining connections between phrases comprises the processor performing a test to determine the most probable of different possible connections.

22. The method of claim 21, wherein the test comprises evaluating whether replacement of certain phrases changes the sense of other phrases in a context of the input data.

23. The method of claim 22, wherein the test uses a semantic n-gram database to evaluate whether replacement of certain phrases changes the sense of other phrases in a context of the input data.

24. The method of claim 13, wherein one or more of aggregation into groups, determining connection between elements, and classifying the elements, is based on rules comprising rules that are not generated using machine learning techniques.