Segmenting text for searching

• US 8,423,350 B1
• Filed: 05/21/2009
• Issued: 04/16/2013
• Est. Priority Date: 05/21/2009
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Chandra, Sunil, Chopra, Harshit, Shanmugam, Siddaarth
• Primary Examiner(s): COLUCCI, MICHAEL C
• Application Number:
  US12/470,394
• Time in Patent Office: 1,426 Days
• Field of Search: 707/768, 707/999.101, 707/742, 706/45, 435/5, 704/1, 704/704, 704/8, 704/9, 704/2, 715/206, 715/256, 725/35
• US Class Current: 704/9
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

Methods, systems, and apparatus, including computer program products, for segmenting text for searching are disclosed. In one implementation, a method is provided. The method includes receiving text; segmenting the text into one or more unigrams; filtering the one or more unigrams to identify one or more core unigrams; and generating a searchable resource, including: for each of the one or more core unigrams: identifying a stem, indexing the stem, and associating one or more second n-grams with the indexed stem. Each of the one or more second n-grams is derived from the text and includes a core unigram that is related to the indexed stem.

Claims

1. A computer-implemented method comprising:

receiving, at a computer system comprising a processor, text;

segmenting, at the computer system, the text into one or more unigrams;

filtering, at the computer system, the one or more unigrams to identify one or more core unigrams; and

generating, at the computer system, a searchable data structure, wherein the generating includes, for each specific unigram of the one or more core unigrams;

identifying a stem of the specific unigram,

indexing the stem,

obtaining (i) grammar information for the specific unigram, (ii) language information for the specific unigram, and (iii) description information for the specific unigram, and

associating one or more n-grams with the indexed stem,

wherein each of the one or more n-grams is derived from the text, the grammar information for the specific unigram, the language information for the specific unigram, and the description information for the specific unigram, and

wherein each of the one or more n-grams includes a core unigram that is related to the indexed stem.

2. The computer-implemented method of claim 1, further comprising:

associating, at the computer system, a content with the one or more n-grams, wherein the content includes an image, audio, video, text, or a document.

3. The computer-implemented method of claim 1, wherein the grammar information includes information for distinguishing between different lexical categories that the specific unigram belongs to,

wherein the language information includes information indicative of a language of the specific unigram, and

wherein the description information includes at least one of (i) user-generated information describing the specific unigram and (ii) information generated by the computer system that describes the specific unigram.

4. The computer-implemented method of claim 1, wherein the searchable data structure includes first and second distinct data structures,

wherein the first data structure includes, for each specific unigram of the one or more core unigrams, (i) the grammar information for the specific unigram, (ii) the language information for the specific unigram, and (iii) the description information for the specific unigram,

wherein the second data structure includes the indexes for the stems of the one or more core unigrams and is used as an index for the first data structure.

5. The computer-implemented method of claim 1, further comprising:

receiving, at the computer system, a first n-gram and a request to search the searchable data structure using the first n-gram;

searching, at the computer system, the searchable data structure to obtain one or more second n-grams related to the first n-gram; and

outputting, at the computer system, the one or more second n-grams.

6. A computer-implemented method comprising:

receiving, at a computer system comprising a processor, text;

segmenting, at the computer system, the text into one or more unigrams;

filtering, at the computer system, the one or more unigrams to identify one or more core unigrams, wherein the filtering includes, for each specific unigram of the one or more core unigrams;

identifying a stem of the specific unigram,

searching an index to identify one or more n-grams that are related to the stem, wherein the index includes (i) grammar information for the specific unigram, (ii) language information for the specific unigram, and (iii) description information for the specific unigram, and

comparing the one or more n-grams to the text to identify a group of the one or more n-grams that are included in the text;

searching, at the computer system, a searchable data structure for each n-gram in the group; and

providing, at the computer system, a content associated with each of the n-grams found in the searchable data structure, wherein the content includes an image, audio, video, text, or a document.

7. The computer-implemented method of claim 6, further comprising:

stemming, at the computer system, the text before comparing the one or more n-grams to the text; and

removing, at the computer system, duplicates of each of the one or more n-grams before comparing the one or more n-grams to the text.

8. The computer-implemented method of claim 6, wherein the grammar information includes information for distinguishing between different lexical categories that the specific unigram belongs to,

wherein the language information includes information indicative of a language of the specific unigram, and

wherein the description information includes at least one of (i) user-generated information describing the specific unigram and (ii) information generated by the computer system that describes the specific unigram.

9. A computer program product, encoded on a tangible program carrier, operable to cause a data processing apparatus to perform operations comprising:

receiving text;

segmenting the text into one or more unigrams;

filtering the one or more unigrams to identify one or more core unigrams; and

generating a searchable data structure, wherein the generating includes, for each specific unigram of the one or more core unigrams;

identifying a stem of the specific unigram,

indexing the stem,

obtaining (i) grammar information for the specific unigram, (ii) language information for the specific unigram, and (iii) description information for the specific unigram, and

associating one or more n-grams with the indexed stem,

wherein each of the one or more n-grams is derived from the text, the grammar information for the specific unigram, the language information for the specific unigram, and the description information for the specific unigram, and

wherein each of the one or more n-grams includes a core unigram that is related to the indexed stem.

10. The computer program product of claim 9, operable to cause the data processing apparatus to perform operations further comprising:

associating a content with the one or more n-grams, where the content includes an image, audio, video, text, or a document.

11. The computer program product of claim 9, wherein the grammar information includes information for distinguishing between different lexical categories that the specific unigram belongs to,

wherein the language information includes information indicative of a language of the specific unigram, and

wherein the description information includes at least one of (i) user-generated information describing the specific unigram and (ii) information generated by the data processing apparatus that describes the specific unigram.

12. The computer program product of claim 9, wherein the searchable data structure includes first and second distinct data structures,

wherein the first data structure includes, for each specific unigram of the one or more core unigrams, (i) the grammar information for the specific unigram, (ii) the language information for the specific unigram, and (iii) the description information for the specific unigram,

wherein the second data structure includes the indexes for the stems of the one or more core unigrams and is used as an index for the first data structure.

13. The computer program product of claim 9, wherein the operations further include:

receiving a first n-gram and a request to search the searchable data structure using the first n-gram;

searching the searchable data structure to obtain one or more second n-grams related to the first n-gram; and

outputting the one or more second n-grams.

14. A computer program product, encoded on a tangible program carrier, operable to cause a data processing apparatus to perform operations comprising:

receiving text;

segmenting the text into one or more unigrams;

filtering the one or more unigrams to identify one or more core unigrams, wherein the filtering includes, for each specific unigram of the one or more core unigrams;

identifying a stem of the specific unigram,

searching an index to identify one or more n-grams that are related to the stem, wherein the index includes (i) grammar information for the specific unigram, (ii) language information for the specific unigram, and (iii) description information for the specific unigram, and

comparing the one or more n-grams to the text to identify a group of the one or more n-grams that are included in the text;

searching a searchable data structure for each n-gram in the group; and

providing a content associated with each of the n-grams found in the searchable data structure, wherein the content includes an image, audio, video, text, or a document.

15. The computer program product of claim 14, operable to cause the data processing apparatus to perform operations further comprising:

stemming the text before comparing the one or more n-grams to the text; and

removing duplicates of each of the one or more n-grams before comparing the one or more n-grams to the text.

16. The computer program product of claim 14, wherein the grammar information includes information for distinguishing between different lexical categories that the specific unigram belongs to,

wherein the language information includes information indicative of a language of the specific unigram, and

wherein the description information includes at least one of (i) user-generated information describing the specific unigram and (ii) information generated by the data processing apparatus that describes the specific unigram.

17. A computer-implemented method, comprising:

receiving, at a computer system including a processor, a training data including a plurality of n-grams, wherein each of the plurality of n-grams includes one or more words;

filtering, at the computer system, the training data by removing stop-words to obtain a modified training data;

generating, at the computer system, a first data structure using the modified training data, the data structure including one or more sets of n-grams, each having one or more subsets of n-grams, wherein the data structure further includes, for each specific n-gram;

(i) a stem of the n-gram,

(ii) grammar information for the specific n-gram,

(iii) language information for the specific n-gram, and

(iv) description information for the specific n-gram;

indexing, at the computer system, the first data structure according to the stems of the n-grams to obtain a searchable data structure;

receiving, at the computer system, a first n-gram and a request to search the searchable data structure using the first n-gram;

searching, at the computer system, the searchable data structure to obtain one or more second n-grams related to the first n-gram; and

outputting, at the computer system, the one or more second n-grams.

18. The computer-implemented method of claim 17, wherein the first data structure includes one or more rows, each having one or more columns,

wherein each of the one or more rows corresponds to an n-gram set and is indexed by a row key that includes a string of text generated and indexed by a hash technique, and

wherein each of the one or more columns includes a protocol buffer that is associated with a single language.

19. The computer-implemented method of claim 18, wherein the searchable data structure is a second data structure that is distinct from the first data structure, and wherein searching the searchable data structure to obtain the one or more second n-grams related to the first n-gram includes using the second data structure as an index for the first data structure to reverse map the first n-gram to one or more row keys of the first data structure to obtain the one or more second n-grams.

20. The computer-implemented method of claim 17, wherein the grammar information includes information for distinguishing between different lexical categories that the specific n-gram belongs to,

wherein the language information includes information indicative of a language of the specific n-gram, and

wherein the description information includes at least one of (i) user-generated information describing the specific n-gram and (ii) information generated by the computer system that describes the specific n-gram.