Phrase identification in a sequence of words

• US 8,892,422 B1
• Filed: 07/09/2012
• Issued: 11/18/2014
• Est. Priority Date: 07/09/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kumar, Shailesh
• Primary Examiner(s): PULLIAS, JESSE SCOTT
• Application Number:
  US13/544,323
• Time in Patent Office: 862 Days
• Field of Search: 704/1, 704/9, 704/10
• US Class Current: 704/9
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

Methods and apparatus related to phrase identification. Methods are provided for determining co-occurrence consistencies for positional word pairings of a plurality of sequences of words in a corpus that may be utilized in identifying a phrase; determining a phrase coherence of a sequence of words based on the co-occurrence consistencies for positional word pairings in the sequence of words; and determining one or more phrase boundaries in a sequence of words.

Claims

1. A computer implemented method of identifying a phrase weighting of a sequence of words as a function of the position of words present in the sequence of words, comprising:

identifying a sequence of words;

determining, utilizing one or more processors, a centrality value for each of a plurality of identified words in the sequence of words, the centrality value for each of the identified words based on a co-occurrence consistency with other of the identified words in their respective relative positions in the sequence of words; and

determining, utilizing one or more processors, a phrase weighting of the sequence of words based on the determined centrality value for each of the identified words, wherein the phrase weighting provides an indication of the likelihood that the sequence of words is a phrase.

2. The method of claim 1, wherein the step of determining the phrase weighting of the sequence of words includes combining the centrality value for each of the identified words.

3. The method of claim 2, wherein the step of determining the phrase weighting of the sequence of words includes determining a weighted average of the centrality value for each of the identified words.

4. The method of claim 2, wherein the step of determining the phrase weighting of the sequence of words includes determining a minimum centrality value from the centrality value for each of the identified words.

5. The method of claim 1, further comprising identifying the sequence of words for indexing as a phrase when the phrase weighting is greater than a threshold phrase weighting.

6. The method of claim 1, wherein the step of determining a centrality value for each of the identified words includes performing an auto-associative analysis for each of the identified words with all other of the identified words in their respective relative positions in the sequence of words.

7. The method of claim 1, wherein the step of determining a centrality value for each of the identified words includes performing a link analysis for each of the identified words with all other of the identified words in their respective relative positions in the sequence of words.

8. The method of claim 1, wherein the co-occurrence consistency for each of the identified words with other of the identified words in their respective relative positions in the sequence of words is extracted from a plurality of positional matrices, each of the positional matrices containing co-occurrence consistency values for a plurality of word pairs in a given positional relation to one another.

9. The method of claim 1, wherein the co-occurrence consistency for each of the identified words with other of the identified words in their respective relative positions in the sequence of words factors in how much more likely than incidental it is for each of the identified words to co-occur with other identified words in their respective relative positions.

10. The method of claim 1, further comprising parsing a document to create the sequence of words.

11. The method of claim 1, further comprising receiving a search query and identifying the sequence of words from the search query.

12. The method of claim 1, wherein the sequence of words is part of a larger sequence of words and further comprising:

identifying a second sequence of words from the larger sequence of words, wherein the second sequence of words contains the same words as the identified words and one additional word;

determining, utilizing one or more processors, an additional centrality value for the additional word, the additional centrality value based on the co-occurrence consistency of the additional word with other of the identified words in their respective relative positions in the second sequence of words; and

determining, utilizing one or more processors, a second phrase weighting of the second sequence of words based on the determined additional centrality value, wherein the second phrase weighting provides an indication of the likelihood that the second sequence of words is a phrase; and

comparing the phrase weighting to the second phrase weighting to identify which is more likely to be a phrase.

13. The method of claim 1, wherein the sequence of words is part of a larger sequence of words and further comprising:

identifying additional sequences of words from the larger sequence of words; and

determining, utilizing one or more processors, additional phrase weightings of each of the additional sequences of words that provide an indication of phrase likelihood.

14. The method of claim 13, further comprising comparing a plurality of the additional phrase weightings and the phrase weighting to one another to identify at least one phrase in the larger sequence of words.

15. The method of claim 14, wherein the comparing includes identifying at least one local extrema among the additional phrase weightings and the phrase weighting.

16. A system, comprising:

memory storing instructions; and

one or more processors operable to execute the instructions stored in the memory;

wherein the instructions comprise instructions to;

identify a sequence of words;

determine a centrality value for each of a plurality of identified words in the sequence of words, the centrality value for each of the identified words based on a co-occurrence consistency with other of the identified words in their respective relative positions in the sequence of words; and

determine a phrase weighting of the sequence of words based on the determined centrality value for each of the identified words, wherein the phrase weighting provides an indication of the likelihood that the sequence of words is a phrase.

17. The system of claim 16, wherein the instructions to determine the phrase weighting of the sequence of words include instructions to combine the centrality value for each of the identified words.

18. The system of claim 17, wherein the instructions to determine the phrase weighting of the sequence of words include instructions to determine a weighted average of the centrality value for each of the identified words.

19. The system of claim 16, wherein the instructions to determine a centrality value for each of the identified words include instructions to perform an auto-associative analysis for each of the identified words with all other of the identified words in their respective relative positions in the sequence of words.

20. The system of claim 16, wherein the co-occurrence consistency for each of the identified words with other of the identified words in their respective relative positions in the sequence of words is extracted from a plurality of positional matrices, each of said positional matrices containing co-occurrence consistency values for a plurality of word pairs in a given positional relation to one another.

21. The system of claim 16, wherein the co-occurrence consistency for each of the identified words with other of the identified words in their respective relative positions in the sequence of words factors in how much more likely than incidental it is for each of the identified words to co-occur with other identified words in their respective relative positions.

22. The system of claim 16, wherein the sequence of words is part of a larger sequence of words and further including instructions to:

identify additional sequences of words from the larger sequence of words; and

determine, utilizing one or more processors, additional phrase weightings of each of the additional sequences of words that provide an indication of phrase likelihood.

23. The system of claim 16, further comprising instructions to compare a plurality of the additional phrase weightings and the phrase weighting to one another to identify at least one phrase in the larger sequence of words.

24. The system of claim 23, wherein the instructions to compare a plurality of the additional phrase weightings and the phrase one another to identify at least one phrase in the larger sequence of words include instructions to identify at least one local extrema among the additional phrase weightings and the phrase weighting.

25. A non-transitory computer readable storage medium storing computer instructions executable by a processor to perform a method comprising:

identifying a sequence of words;

determining, utilizing one or more processors, a centrality value for each of a plurality of identified words in the sequence of words, the centrality value for each of the identified words based on a co-occurrence consistency with other of the identified words in their respective relative positions in the sequence of words; and

determining, utilizing one or more processors, a phrase weighting of the sequence of words based on the determined centrality value for each of the identified words, wherein the phrase weighting provides an indication of the likelihood that the sequence of words is a phrase.