Method and system for autocompletion for languages having ideographs and phonetic characters

• US 9,443,035 B2
• Filed: 09/24/2013
• Issued: 09/13/2016
• Est. Priority Date: 11/12/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gibbs, Kevin A.
• Primary Examiner(s): CHEEMA, AZAM M
• Application Number:
  US14/035,831
• Publication Number:
  US 20140089285A1
• Time in Patent Office: 1,085 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G06F 40/53 Processing of non-Latin text kana-to-kanji conversion G06F40/129; vowelisation G06F40/232

Abstract

A set of ordered predicted completion strings including strings of ideographs are presented to a user as the user enters text in a text entry box (e.g., a browser or a toolbar). The user entered text may include zero or more ideographs followed by one or more phonetic characters, or the entered text may be one or more. The predicted completion strings can be in the form of URLs or query strings. The ordering may be based on any number of factors (e.g., a query'"'"'s frequency of submission from a community of users). URLs can be ranked based on an importance value of the URL. The sets of ordered predicted completion strings are obtained by matching a fingerprint value of the user'"'"'s entry string to a fingerprint to table map which contains the set of ordered predicted completion strings. The generation of the ordered prediction strings takes into account multiple phonetic representations of certain strings of ideographs.

Claims

1. A method for suggesting search query completions for a language having ideographs and phonetic characters, comprising:

on a search engine having one or more processors and memory storing programs executed by the one or more processors;

receiving a partial search query from a search requestor, the partial search query comprising one or more ideographs followed by at least one phonetic character that forms an incomplete phonetic sequence consistent with a first ideograph distinct from the one or more ideographs, and the partial search query comprises a portion of a complete search query, wherein the one or more ideographs of the partial search query include one or more Asian language ideographs, and the first ideograph corresponding to the at least one phonetic character comprises a respective Asian language ideograph; and

automatically, in response to receiving the partial search query from the search requestor, prior to the search requestor signaling completion of a search query, and prior to the search requester entering any text beyond the one or more ideographs followed by at least one phonetic character;

in accordance with both the one or more ideographs and the at least one phonetic character, obtaining a set of predicted complete search queries corresponding to the partial search query from search queries submitted by a community of users, the set of predicted complete search queries ordered in accordance with a ranking criteria, including the search engine making a prediction of the first ideograph, based on the at least one phonetic character, and obtaining the set of predicted complete search queries corresponding to the one or more ideographs in the partial search query and the predicted first ideograph; and

conveying the set of ordered predicted search queries to the search requestor;

wherein each search query of the set of the predicted complete search queries includes both the one or more Asian language ideographs of the partial search query and the respective Asian language ideograph consistent with the incomplete phonetic sequence.

2. The method of claim 1, wherein obtaining the set of predicted complete search queries includes obtaining two or more sets corresponding to the partial search query and merging the sets;

and

wherein a first one of the sets is obtained from a client and a second one of the sets is obtained from a server.

3. The method of claim 1, further comprising:

generating search results relevant to at least one of the predicted search queries, and

conveying the search results to the requestor.

4. The method of claim 1, further including:

after conveying the set of ordered predicted search queries;

obtaining a subsequent set of predicted complete search queries; and

transmitting, to the search requestor, the subsequent set of predicted complete search queries ordered in accordance with the ranking criteria.

5. The method of claim 1, further comprising:

obtaining a set of historical search queries previously submitted by a community of users, wherein each of the queries in the set of historical search queries has a frequency of submission and includes at least one Asian language ideograph;

mapping strings of one or more Asian language ideographs from the plurality of historical search queries into one or more representations that include a string of one or more phonetic characters; and

generating a plurality of ordered subsets from the identified set of historical search queries, wherein each ordered subset includes one or more historical search queries from the identified set of historical search queries ordered in accordance with the respective frequency of submission.

6. A search engine system for suggesting query completions for a language having ideographs and phonetic characters, comprising:

one or more processors; and

memory storing one or more programs to be executed by the one or more processors, the one or more programs including instructions for;

receiving a partial search query from a search requestor, the partial search query comprising one or more ideographs followed by at least one phonetic character that forms an incomplete phonetic sequence consistent with a first ideograph distinct from the one or more ideographs, and the partial search query comprises a portion of a complete search query, wherein the one or more ideographs of the partial search query include one or more Asian language ideographs, and the first ideograph corresponding to the at least one phonetic character comprises a respective Asian language ideograph; and

automatically, in response to receiving the partial search query from the search requestor, prior to the search requestor signaling completion of a search query, and prior to the search requester entering any text beyond the one or more ideographs followed by at least one phonetic character;

in accordance with both the one or more ideographs and the at least one phonetic character, obtaining a set of predicted complete search queries corresponding to the partial search query from search queries submitted by a community of users, the set of predicted complete search queries ordered in accordance with a ranking criteria, including the search engine making a prediction of the first ideograph, based on the at least one phonetic character, and obtaining the set of predicted complete search queries corresponding to the one or more ideographs in the partial search query and the predicted first ideograph; and

conveying the set of ordered predicted search queries to the search requestor;

wherein each search query of the set of the predicted complete search queries includes both the one or more Asian language ideographs of the partial search query and the respective Asian language ideograph consistent with the incomplete phonetic sequence.

7. The search engine system of claim 6, wherein obtaining the set of predicted complete search queries includes obtaining two or more sets corresponding to the partial search query and merging the sets;

and

wherein a first one of the sets is obtained from a client and a second one of the sets is obtained from a server.

8. The search engine system of claim 6, the one or more programs further including instructions for:

generating search results relevant to at least one of the predicted search queries, and

conveying the search results to the requestor.

9. The search engine system of claim 6, the one or more programs further including instructions for:

after conveying the set of ordered predicted search queries;

obtaining a subsequent set of predicted complete search queries; and

transmitting, to the search requestor, the subsequent set of predicted complete search queries ordered in accordance with the ranking criteria.

10. The search engine system of claim 6, the one or more programs further including instructions for:

obtaining a set of historical search queries previously submitted by a community of users, wherein each of the search queries in the set of historical search queries has a frequency of submission and includes at least one Asian language ideograph;

mapping strings of one or more Asian language ideographs from the plurality of historical search queries into one or more representations that include a string of one or more phonetic characters; and

generating a plurality of ordered subsets from the identified set of historical search queries, wherein each ordered subset includes one or more historical search queries from the identified set of historical search queries ordered in accordance with the respective frequency of submission.

11. A non-transitory computer readable storage medium storing one or more programs to be executed by one or more processors of a search engine system, the one or more programs including instructions for:

receiving a partial search query from a search requestor, the partial search query comprising one or more ideographs followed by at least one phonetic character that forms an incomplete phonetic sequence consistent with a first ideograph distinct from the one or more ideographs, and the partial search query comprises a portion of a complete search query, wherein the one or more ideographs of the partial search query include one or more Asian language ideographs, and the first ideograph corresponding to the at least one phonetic character comprises a respective Asian language ideograph; and

automatically, in response to receiving the partial search query from the search requestor, prior to the search requestor signaling completion of a search query, and prior to the search requester entering any text beyond the one or more ideographs followed by at least one phonetic character;

in accordance with both the one or more ideographs and the at least one phonetic character, obtaining a set of predicted complete search queries corresponding to the partial search query from search queries submitted by a community of users, the set of predicted complete search queries ordered in accordance with a ranking criteria, including the search engine making a prediction of the first ideograph, based on the at least one phonetic character, and obtaining the set of predicted complete search queries corresponding to the one or more ideographs in the partial search query and the predicted first ideograph; and

conveying the set of ordered predicted search queries to the search requestor;

wherein each search query of the set of the predicted complete search queries includes both the one or more Asian language ideographs of the partial search query and the respective Asian language ideograph consistent with the incomplete phonetic sequence.

12. The computer readable storage medium of claim 11, wherein obtaining the set of predicted complete search queries includes obtaining two or more sets corresponding to the partial search query and merging the sets;

and

wherein a first one of the sets is obtained from a client and a second one of the sets is obtained from a server.

13. The computer readable storage medium of claim 11, the one or more programs further including instructions for:

generating search results relevant to at least one of the predicted search queries, and

conveying the search results to the requestor.

14. The computer readable storage medium of claim 11, the one or more programs further including instructions for:

after conveying the set of ordered predicted search queries;

obtaining a subsequent set of predicted complete search queries; and

transmitting, to the search requestor, the subsequent set of predicted complete search queries ordered in accordance with the ranking criteria.

15. The computer readable storage medium of claim 11, the one or more programs further including instructions for:

obtaining a set of historical search queries previously submitted by a community of users, wherein each of the search queries in the set of historical search queries has a frequency of submission and includes at least one Asian language ideograph;

mapping strings of one or more Asian language ideographs from the plurality of historical search queries into one or more representations that include a string of one or more phonetic characters; and

generating a plurality of ordered subsets from the identified set of historical search queries, wherein each ordered subset includes one or more historical search queries from the identified set of historical search queries ordered in accordance with the respective frequency of submission.