Method for retrieving items represented by particles from an information database

• US 8,055,693 B2
• Filed: 06/30/2009
• Issued: 11/08/2011
• Est. Priority Date: 02/25/2008
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Ezzat, Tony, Gouvea, Evandro
• Primary Examiner(s): CHEN, TE Y
• Application Number:
  US12/495,540
• Publication Number:
  US 20090265162A1
• Time in Patent Office: 861 Days
• Field of Search: 704/270, 704/275, 706/48
• US Class Current: 707/899
• CPC Class Codes: G06F 16/3343 using phonetics
• CPC Class Codes: G10L 15/26 Speech to text systems G10L15/08 takes precedence

Abstract

A set of words is converted to a corresponding set of particles, wherein the words and the particles are unique within each set. For each word, all possible partitionings of the word into particles are determined, and a cost is determined for each possible partitioning. The particles of the possible partitioning associated with a minimal cost are added to the set of particles.

Claims

1. A method for converting a set of words to a corresponding set of particles, comprising the steps of:

acquiring the set of particles, each particle uniquely corresponds to a word in the set of words;

defining a cost as a function of a size of the set particles, a frequency of occurrence of the particle in the set of particles, and a length of the particle, such that the cost decreases if the size of the set particles is decreased, the cost decreases if the frequency of occurrence of the particle in the set of particles is increased, and the cost decreases if a number of phonemes in the particle is decreased;

partitioning each particle in the set of particles into a prefix particle and a suffix particle, if the partitioning minimizes the cost; and

repeating the partitioning until a desired number of unique particles in the set is achieved, wherein the steps of the method are performed by a processor.

2. The method of claim 1, wherein the set of words is obtained from a word-based list of items, and further comprising:

generating a corresponding particle-based list of items from the word-based list of items using the set of words and the set of particles.

3. The method of claim 2, further comprising:

indexing the particle-based list of item using the set of particles to generate a particle-based index to the particle-based list of items.

4. The method of claim 3, further comprising:

acquiring a query from a user;

accessing the particle-based list of items using the particle-based index to retrieve particle-based items that best match the query; and

outputting corresponding word-based items as a result list for the user.

5. The method of claim 1, wherein the query is text, and the text is converted to a particle-based query using the set of particles.

6. The method of claim 1, wherein the query is speech, and speech is converted to a particle-based query using the set of particles.

7. The method of claim 1, wherein the set of particles includes alternative pronunciations of the word.

8. The method of claim 1, wherein the cost includes a sum of a likelihood cost

9. The method of claim 1, wherein the partitioning uses a left to right linear scan of the word.

10. The method of claim 1, wherein the partitioning is made at syllable boundaries of the word.

11. The method of claim 1, wherein the cost depends on an n-gram perplexity.

12. The method of claim 1, wherein the cost depends on a finite state grammar.