WORD PROBABILITY DETERMINATION

• US 20080319738A1
• Filed: 10/10/2007
• Published: 12/25/2008
• Est. Priority Date: 06/25/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Liu, Tang Xi, Ge, Xianping
• Granted Patent: US 8,630,847 B2
• Time in Patent Office: Days
• US Class Current: 704/10
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

A word corpus is identified and a word probability value is associated with each word in the word corpus. A sentence is identified, candidate segmentations of the sentence are determined based on the word corpus, and the associated probability value for each word in the word corpus is iteratively adjusted based on the probability values associated with the words and the candidate segmentations.

Claims

1. A computer-implemented method, comprising:

identifying a word corpus;

associating a word probability value with each word in the word corpus;

identifying a sentence;

determining candidate segmentations of the sentence based on the word corpus; and

iteratively adjusting the associated word probability value for each word in the word corpus based on the associated word probability values and the candidate segmentations.

2. The method of claim 1, comprising storing a portion of the word corpus defined by words having the highest associated word probability values in an input method editor dictionary.

3. The method of claim 1 wherein the word probability values correspond to a probability of associated words appearing in the sentence.

4. The method of claim 1 wherein determining candidate segmentations of the sentence comprises determining all possible segmentations of the at least one sentence based on the word corpus.

5. The method of claim 1, comprising determining a segmentation probability value for each candidate segmentation of the sentence.

6. The method of claim 5 wherein determining a segmentation probability value for each candidate segmentation of the sentence comprises determining the segmentation probability value for each candidate segmentation based on the word probability values associated with the words in the candidate segmentation.

7. The method of claim 5 wherein iteratively adjusting the associated word probability value for each word in the word corpus based on the associated word probability values and the candidate segmentations comprises iteratively adjusting the associated word probability value for each word based on the segmentation probability values for the candidate segmentations of the sentence.

8. The method of claim 1 wherein iteratively adjusting the associated word probability value for each word comprises, for each iteration,

determining the segmentation probability value for each candidate segmentation of the sentence based on the word probability values associated with the words in the candidate segmentation, and

adjusting the associated word probability value for each word based on the segmentation probability values for the candidate segmentations that include the word.

9. The method of claim 1 wherein determining a refined probability value of a word in the sentence comprises multiplying (a) a sum of the probability values of candidate segmentations of a substring before the word, (b) the probability value of the word, and (c) a sum of the probability values of candidate segmentations of a substring after of the word.

10. The method of claim 1 wherein determining candidate segmentations of the sentence comprises determining candidate segmentations of a plurality of sentences in a document.

11. The method of claim 1, comprising identifying sentences in a plurality of documents, and for each sentence, determining candidate segmentations of the sentence based on the word corpus.

12. The method of claim 11 wherein sentences in different types of documents are given different weights in determining the word probability values.

13. The method of claim 11 wherein the documents are accessible over a public network, the Internet, or provided by a plurality of third parties.

14. The method of claim 1 wherein the words comprise at least one of Chinese, Japanese, and Korean characters.

15. The method of claim 1 wherein the words comprise Hanzi characters.

16. A computer-implemented method comprising:

determining word probability values associated with words of a word corpus;

determining candidate segmentations of sentences of documents in a document corpus;

iteratively determining a segmentation probability value for each candidate segmentation of each sentence based on the word probability values associated with the words in the candidate segmentation; and

iteratively adjusting the word probability value for each word based on the segmentation probability values for the candidate segmentations that include the word.

17. The method of claim 16, comprising:

identifying document types for the documents;

assigning weights to sentences in the documents based on the identified document type; and

determining one of the segmentation probability values or the word probability values based on the weights.

18. The method of claim 16, comprising accumulating a count for each word based on the segmentation probability values of the segmentations that include the word.

19. The method of claim 18 wherein accumulating the count for each word comprises determining a sum of the segmentation probability values of the segmentations that include the word.

20. The method of claim 18, comprising determining the word probability value for each word by normalizing the count for the word based on a normalization factor.

21. The method of claim 20, comprising determining the normalization factor by determining a sum of the counts of all the words.

22. A method, comprising:

establishing a dictionary that includes words and associated word probability values that are determined using an iterative process, the iterative process including iteratively determining segmentation probability values for candidate segmentations of sentences of documents, and iteratively adjusting the word probability values for the word based on the segmentation probability values; and

providing an input method editor which is configured to select words from the dictionary.

23. A system, comprising:

a data store to store a word corpus and a document corpus;

a processing engine stored in computer readable medium and comprising instructions executable by a processing device that upon such execution cause the processing device to;

associate a word probability value with each word in the word corpus;

determine candidate segmentations of each sentence of each document in the document corpus based on the word corpus; and

iteratively adjust the associated word probability value for each word in the word corpus based on the associated word probability values and the candidate segmentations.

24. The system of claim 23 wherein the processing device determine candidate segmentations of each sentence by iteratively determining a segmentation probability value for each candidate segmentation of each sentence based on the word probability values associated with the words in the candidate segmentation.

25. A system, comprising:

means for associating a word probability value with words in a word corpus;

means for identifying sentences in a plurality of documents;

means for determining candidate segmentations of each of the sentences based on the word corpus; and

means for iteratively adjusting the associated word probability value for each word in the word corpus based on the associated word probability values and the candidate segmentations.