Method for Retrieving Items Represented by Particles from an Information Database

• US 20090265162A1
• Filed: 06/30/2009
• Published: 10/22/2009
• 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 B.
• Granted Patent: US 8,055,693 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• 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, wherein the words and the particles are unique within each set, comprising a processor for performing steps of the method comprising the steps of:

determining, for each word, all possible partitionings of the word into particles;

determining, for each word, a cost for each possible partitioning; and

adding the particles of the possible partitioning associated with a minimal cost to the set of particles.

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 possible particles are for alternative pronunciations of the word.

8. The method of claim 1, wherein each particle represents a concatenated phoneme sequence, and a string of particles represents a phoneme sequence for the corresponding word.

9. The method of claim 1, wherein frequent words are kept intact, while infrequent words are partitioned into particles.

10. The method of claim 1, wherein the cost is a function of frequencies c of the words in the word-based list of items, and a function of a length of the particles in the set of particles.

11. The method of claim 1, wherein the cost is the sum of a likelihood cost

$\sum _{}$

i ∈

particles 

- log 

( p i ) ,

where

$p_i=\frac{c_i}{\underset{k\in <br><br>\mathrm{particles}}{\sum <br><br>}<br><br>c_k},$

and c are frequencies of the particle and an inventory cost

$\underset{i\in <br><br>\mathrm{particles}}{\sum <br><br>}<br><br>-l_i<br><br>\log <br><br>\left(p_{\mathrm{phoneme}}\right).$

where p_phoneme is a log probability of a phoneme used by the particle.

12. The method of claim 1, wherein the possible partitionings use a left to right linear scan of the word, to partition the word into a left prefix and right prefix.

13. The method of claim 1, wherein the possible partitionings are made at syllable boundaries of the word, guided by additional information in a pronunciation dictionary.

14. The method of claim 1, wherein the set of words is arranged in a random order, and the set is reprocessing iteratively for a different random order until a termination condition is reached.

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

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

17. The method of claim 2, wherein the list of word-based items originates from text.

18. The method of claim 2, wherein the list of word-based items originates from speech.

19. The method of claim 1, wherein the cost increases with a size of the set particles, and decreases as a function of frequency of occurrence of the particles in the set.