Text analysis using phrase definitions and containers

• US 8,433,559 B2
• Filed: 03/24/2009
• Issued: 04/30/2013
• Est. Priority Date: 03/24/2009
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Madan, Umesh
• Primary Examiner(s): Shah, Paras D
• Assistant Examiner(s): Sharma, Neeraj
• Application Number:
  US12/410,456
• Publication Number:
  US 20100250235A1
• Time in Patent Office: 1,498 Days
• Field of Search: 707/1, 704/3, 704/4, 704/9
• US Class Current: 704/9
• CPC Class Codes: G06F 16/332 Query formulation
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

In one example, a phrase analyzer may analyze a text input stream to identify phrases contained in the text input stream. The phrase analyzer may receive a specification, which includes dictionaries of phrases and synonyms, and a specification of the phrases, or sequences of phrases to be matched. The phrase analyzer may compare the input stream to the specification and may produce, as output, an identification of which phrases appear in the input stream, and where in the input stream those phrases occur.

Claims

1. One or more computer-readable storage devices that store executable instructions that, when executed by a computer, cause the computer to perform acts comprising:

receiving a specification of a text pattern to be matched in an input stream, said specification comprising one or more data expressions and one or more code expressions, the data expressions defining one or more phrase sets, a first one of the code expressions comprising a first container that comprises a first phrase set, a second phrase set, and a second container that comprises a third phrase set and a fourth phrase set, said specification further comprising a map set and an equivalence set that maps a plurality of phrases to a first phrase based on misspellings and equivalent phrases, said first container comprising a switch that branches between a plurality of match labels;

comparing words in said input stream with said first container, said comparing act converting, based on said map set, any of said plurality of phrases to said first phrase when any of said plurality of phrases is encountered in said input stream;

determining that a context in said input stream matches said first container based on a finding that said context matches either said first phrase set or said second phrase set, said first phrase set, said context being labeled as a first label if said context matches said first phrase set, or being labeled as a second label if said context matches said second phrase set; and

generating a report indicating that said container matches a sequence of words in said input stream.

wherein a container represents the various ways in which possible phrase sets may be combined as part of a text pattern to be matched such that the context moves forward after a match has been found between the container and a sequence of words in the input stream and a next container is processed after a location of the matching sequence of words.

2. The one or more computer-readable storage devices of claim 1, wherein said generating of said report comprises:

creating a file that identifies one or more ordinal positions in said input stream in which a match for said container is found, and a label that identifies said match.

3. The one or more computer-readable storage devices of claim 1, wherein second container comprises either:

an AND container that specifies that said context matches said second container when said context comprises an instance of said third phrase set and an instance of said fourth phrase set;

or

an OR container that specifies that said context matches said second container when said context comprises an instance of said third phrase set or an instance of said fourth phrase set.

4. The one or more computer-readable storage devices of claim 1, wherein said second container comprises an ALL container that specifies that said context matches said second container when (a) said context comprises an instance of said third phrase set and an instance of said fourth phrase set, and (b) there are no more words to be consumed in said context after words corresponding to all elements in said second container have been consumed.

5. The one or more computer-readable storage devices of claim 1, wherein said second container comprises a REPEAT container, wherein said context starts at a first ordinal position in said input stream, and wherein said acts further comprise:

determining whether said input stream contains instances of elements in said second container starting at said first ordinal position; and

determining whether said input stream contains instances of elements in said second container starting at successive ordinal positions following said first ordinal position.

6. The one or more computer-readable storage devices of claim 1, wherein said determining of whether said context matches said container comprises determining whether said context comprises an instance of said first phrase set, an instance of said second phrase set, and an instance of said second container.

7. The one or more computer-readable storage devices of claim 1, wherein said second container comprises a LIST container, and wherein said determining comprises:

determining that said context comprises an instance of said third phrase set; and

after determining that said context comprises an instance of said third phrase set, determining whether said context comprises instances of all other elements in said second container, said context matching said first container as long as said context comprises an instance of said first phrase set, said second phrase set, and at least one of the elements in said second container.

20. The one or more computer-readable storage devices of claim 1, said specification further comprising an equivalence set that comprises a plurality of phrases, said determining act finding that all of said plurality of phrases in said equivalence set are found in said context when any one of said phrases is found in said context.

8. A system comprising:

one or more processors;

one or more data remembrance components;

a specification that is stored in said one or more data remembrance components, said specification comprising;

a data expression that defines a plurality of phrase sets;

a code expression that defines a first container that specifies a combination that comprises a first one of said phrase sets, a second one of said phrase sets, and a second container that comprises a third one of said phrase sets and a fourth one of said phrase sets; and

a map set and an equivalence set that maps a plurality of phrases to a first phrase based on misspellings and equivalent phrases, said phrase analyzer encountering one of said plurality of phrases in said input stream and, based on said map set, converting said one of said plurality of phrases to said first phrase when determining whether said input stream matches said first container; and

a phrase analyzer that executes on said one or more processors, that receives said specification and an input stream, that compares words in said input stream to said first container, and that generates a report that identifies where, in said input stream, a match between said first container and said input stream is found, said first container comprising a switch that branches between a plurality of match labels, said phrase analyzer labeling a portion of said input stream that matches said first container as a first label if said portion matches said first phrase set, or being labeled as a second match if said context matches said second phrase set,

wherein a container represents the various ways in which possible phrase sets may be combined as part of a text pattern to be matched such that the context moves forward after a match has been found between the container and a sequence of words in the input stream and a next container is processed after a location of the matching sequence of words.

9. The system of claim 8, wherein said specification further comprises:

an equivalence set that comprises a plurality of phrases, said phrase analyzer finding that all of said plurality of phrases in said equivalence set are found when any one of said phrases is found in said input stream.

10. The system of claim 8, wherein second container comprises either:

an AND container that specifies that said input stream matches said second container when a context in said input stream comprises an instance of said third one of said phrase sets and an instance of said fourth one of said phrase sets;

or

an OR container that specifies that said input stream matches said second container when a context in said input stream comprises an instance of said third one of said phrase sets or an instance of said fourth one of said phrase sets.

11. The system of claim 8, wherein said second container comprises an ALL container that specifies that said input stream matches said second container when (a) a context in said input stream comprises an instance of said third one of said phrase sets and an instance of said fourth one of said phrase sets, and (b) there are no more words to be consumed in said context after words corresponding to all elements in said ALL container have been consumed.

12. The system of claim 8, wherein said second container comprises a REPEAT container, and wherein said phrase analyzer determines that a sequence of a plurality of words starting at a first ordinal position in said input stream matches said second container, and subsequently compares said second container to a sequence of words that starts one ordinal position ahead of said first ordinal position, and after a word that appears one ordinal position ahead of said first ordinal position has already been consumed.

13. The system of claim 8, and wherein said phrase analyzer determines whether said input stream matches said first container by determining whether a context in said input stream comprises an instance of said first one of said phrase sets, an instance of said second one of said phrase sets, and an instance of said second container.

14. The system of claim 8, wherein said second container comprises a LIST container, wherein said phrase determines that input stream comprises a context that comprises an instance of said third one of said phrase sets and subsequently determines whether said context comprises instances of all other elements in said second container, said context matching said first container as long as said context comprises said first phrase set, said second phrase set, and an instance of at least one of the elements in said second container.

15. A method of performing an action based on input text, the method comprising:

using a processor to perform acts comprising;

receiving a map set and an equivalence set that maps a first plurality of phrases to a first phrase based on misspellings and equivalent phrases;

converting occurrence of any one of said first plurality of phrases in an input text to said first phrase;

comparing words in said input text to a first container that describes a combination that comprises a first phrase set, a second phrase set, and a second container, said first phrase set comprising a first plurality of phrases, said second phrase set comprising a second plurality of phrases, said second container comprising a third phrase set and a fourth phrase set;

determining that a sequence of words in said input text matches said first container, said match being found based on a match between said sequence of words and said first phrase, said first phrase occurring in said text due to having been converted from one of said first plurality of phrases by said converting act, said first container comprising a switch that branches between a plurality of match labels, said sequence of words being labeled as a first label if said context matches said first phrase set, or being labeled as a second label if said context matches said second phrase set;

generating a report that indicates where, in said input text, said sequence of words occurs; and

taking a tangible action based on said report,

wherein a container represents the various ways in which possible phrase sets may be combined as part of a text pattern to be matched such that the context moves forward after a match has been found between the container and a sequence of words in the input stream and a next container is processed after a location of the matching sequence of words.

16. The method of claim 15, further comprising:

using a processor to perform acts comprising;

creating a text file that identifies one or more ordinal positions in said input text in which a match for said container is found, and a label that identifies said match.

17. The method of claim 15, wherein said second container comprises either:

an AND container that specifies that a context in said input text matches said second container when said context comprises an instance of said third phrase set and an instance of said fourth phrase set;

or

an OR container that specifies that a context in said input set matches said second container when said context comprises an instance of said third phrase set or an instance of said fourth phrase set.

18. The method of claim 15, further comprising:

using a processor to perform acts comprising;

receiving a specification that comprises;

data expressions that comprise said first phrase set and said second phrase set; and

code expressions that comprise said first container.

19. The method of claim 18, wherein said specification further comprises:

said map set; and

an equivalence set that comprises a second plurality of phrases;

and wherein the method further comprises;

using a processor to perform acts comprising;

indicating that all of said second plurality of phrases have occurred in said input text when any one of said second plurality of phrases occurs in said input text.