Methods and systems for improving text segmentation

• US 8,078,633 B2
• Filed: 03/15/2010
• Issued: 12/13/2011
• Est. Priority Date: 09/30/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Elbaz, Gilad Israel, Mandelson, Jacob L.
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): Le, Hung D
• Application Number:
  US12/724,344
• Publication Number:
  US 20100174716A1
• Time in Patent Office: 638 Days
• Field of Search: None
• US Class Current: 707/771
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

Methods and systems for improving text segmentation are disclosed. In one embodiment, at least a first segmented result and a second segmented result are determined from a string of characters, a first frequency of occurrence for the first segmented result and a second frequency of occurrence for the second segmented result are determined, and an operable segmented result is identified from the first segmented result and the second segmented result based at least in part on the first frequency of occurrence and the second frequency of occurrence.

Claims

1. A computer-implemented method, comprising:

receiving, at a computer system, a string of characters that includes no word-delineating breaks;

generating, by the computer system from the string of characters, a plurality of candidate word groups that are portions of the string of characters;

determining, by the computer system, frequencies with which all or a portion of each of the candidate word groups occur in a corpus; and

selecting, by the computer system using the determined frequencies, one or more of the candidate word groups for submission to an entity, wherein the one or more candidate word groups are selected based on each of the one or more candidate word groups having a determined frequency that is greater than determined frequencies for at least a threshold number of other candidate word groups.

2. The method of claim 1, wherein a frequency with which a candidate word group occurs in the corpus is based upon a combination of frequencies of one or more of the words from the candidate word group in the corpus.

3. The method of claim 2, wherein the combination of frequencies comprises an aggregation of the frequencies of the one or more of the words from the candidate word group in the corpus.

4. The method of claim 2, wherein the combination of frequencies comprises a combination of values produced by a logarithmic function applied to the frequencies of the one or more of the words from the candidate word group in the corpus.

5. The method of claim 1, wherein the string of characters comprises a uniform resource locator (URL).

6. The method of claim 1, wherein a frequency with which a candidate word group occurs in the corpus is determined by submitting all or a portion of the word group to a search engine.

7. The method of claim 1, wherein a frequency with which a candidate word group occurs in the corpus is determined based upon a number of documents in the corpus containing one or more of the words in the candidate word group.

8. The method of claim 1, wherein a frequency with which a candidate word group occurs in the corpus is determined based upon a number of previously received search queries containing one or more of the words in the candidate word group.

9. The method of claim 1, wherein the selected one or more of the candidate word groups have the greatest determined frequencies among the generated candidate word groups.

10. The method of claim 1, wherein the entity comprises a computer device configured to select an advertisement for display in relation to the string of characters based upon the selected one or more of the candidate word groups.

11. The method of claim 1, wherein the entity comprises a computer device configured to use the selected one or more of the candidate word groups in conducting a search related to the string of characters.

13. The method of claim 1, wherein the entity comprises a data repository configured to store the selected one or more of the candidate word groups in association with the string of characters.

14. The method of claim 1, wherein a candidate word group is generated by inserting one or more word-delineating breaks into the string of characters to form the words of the candidate word group.

12. A computer-implemented method, comprising:

receiving, at a computer system, a string of characters that includes no word-delineating breaks;

generating, by the computer system from the string of characters, a plurality of candidate word groups that are portions of the string of characters;

determining, by the computer system, frequencies with which all or a portion of each of the candidate word groups occur in a corpus; and

selecting, by the computer system using the determined frequencies, one or more of the candidate word groups for submission to an entity, wherein the entity comprises a computer device configured to use the selected one or more of the candidate word groups in determining whether to apply a filter with regard to the string of characters.

15. A computer program product encoded on a tangible and non-transitory computer-readable medium, operable to cause a data processing apparatus to perform operations comprising:

receiving a string of characters that includes no word-delineating breaks;

generating, from the string of characters, a plurality of candidate word groups that are portions of the string of characters;

determining frequencies with which all or a portion of each of the candidate word groups occur in a corpus; and

selecting, using the determined frequencies, one or more of the candidate word groups for submission to an entity, wherein the one or more candidate word groups are selected based on each of the one or more candidate word groups having a determined frequency that is greater than determined frequencies for at least a threshold number of other candidate word groups.

16. The computer program product of claim 15, wherein a frequency with which a candidate word group occurs in the corpus is based upon a combination of frequencies of one or more of the words from the candidate word group in the corpus.

17. The computer program product of claim 16, wherein the combination of frequencies comprises an aggregation of the frequencies of the one or more of the words from the candidate word group in the corpus.

18. The computer program product of claim 16, wherein the combination of frequencies comprises a combination of values produced by a logarithmic function applied to the frequencies of the one or more of the words from the candidate word group in the corpus.

19. The computer program product of claim 15, wherein the string of characters comprises a uniform resource locator (URL).

20. A system for segmenting a string of characters, the system comprising:

one or more server devices;

an interface to the one or more server devices that is configured to receive a string of characters that includes no word-delineating breaks;

a segmentation processor of the one or more server devices that is configured to from the string of characters, a plurality of candidate word groups that are portions of the string of characters; and

means for selecting one or more of the combinations of words, wherein the means for selecting is configured to determine frequencies with which all or a portion of each of the candidate word groups occur in a corpus, and wherein the means for selecting is further configured to select, using the determined frequencies, one or more of the candidate word groups for submission to an entity, wherein the one or more candidate word groups are selected based on each of the one or more candidate word groups having a determined frequency that is greater than determined frequencies for at least a threshold number of other candidate word groups.