Speech index pruning

• US 7,831,428 B2
• Filed: 11/09/2005
• Issued: 11/09/2010
• Est. Priority Date: 11/09/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Acero, Alejandro, Sanchez, Jorge F. Silva, Chelba, Ciprian I.
• Primary Examiner(s): Dorvil; Richemond
• Assistant Examiner(s): BORSETTI, GREG
• Application Number:
  US11/270,673
• Publication Number:
  US 20070106512A1
• Time in Patent Office: 1,826 Days
• Field of Search: 704/270, 704/3, 707/3, 707/706, 707/711, 707/741, 707/742
• US Class Current: 704/270
• CPC Class Codes: G06F 16/61 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/685 using automatically derived transcript of audio data, e.g. lyrics speech recognition G10L15/00
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams

Abstract

A speech segment is indexed by identifying at least two alternative word sequences for the speech segment. For each word in the alternative sequences, information is placed in an entry for the word in the index. Speech units are eliminated from entries in the index based on a comparison of a probability that the word appears in the speech segment and a threshold value.

Claims

1. A computer-implemented method of searching a speech index comprising:

accessing a speech index of a plurality of spoken documents each comprising a collection of speech signals using a processor, wherein the speech index comprises a plurality of word entries, each entry identifying a plurality of candidate positions for a word in the plurality of speech signals and a probability of the word appearing at each of the candidate positions given the corresponding speech signal;

receiving a search query comprising a target word from a user using the processor;

receiving a first threshold value from the user using the processor;

searching the speech index for one of the word entries that matches the target word of the search query using the processor;

retrieving from the matched entry the plurality of candidate positions for the target word and the probability of the word appearing at each of the candidate positions, using the processor;

eliminating the candidate positions based on a comparison of the probability of the word appearing at a candidate position and the first threshold value;

ranking the speech signals based on the probabilities of the remaining candidate positions relative to each other to form ranked speech signals using the processor; and

returning search results to the user based on the ranked speech signals using the processor, the search results comprising an identification of one or more of the spoken documents.

2. The method of claim 1, wherein eliminating the candidate positions comprises comparing the probabilities of the candidate positions to the first threshold value and eliminating those candidate positions whose probabilities fail to reach a predefined relationship to the first threshold value using the processor.

3. The method of claim 1 further comprising modifying the target word of the search query to form a modified target word and searching the index for an entry associated with the modified target word.

4. The method of claim 1, further comprising:

receiving a second threshold value from the user;

replacing the first threshold with the second threshold;

eliminating the candidate positions based on a comparison of their probabilities to the second threshold value using the processor;

ranking the speech signals based on the probabilities of the remaining candidate positions relative to each other to form ranked speech signals using the processor; and

returning search results to the user based on the ranked speech signals using the processor, the search results comprising an identification of one or more of the spoken documents.

5. A computer-implemented method of searching a speech index comprising:

accessing a speech index of a plurality of spoken documents each comprising a collection of speech signals using a processor, the speech index comprising positions of words in the speech signals, and a probability of the words appearing at each of the positions given the corresponding speech signal;

receiving a search query from a user using the processor;

receiving a first threshold value from the user using the processor;

eliminating the positions of words from the speech index based on a comparison of the probability of a word appearing at a position to the first threshold value to form a pruned speech index using the processor;

searching the pruned speech index for an entry associated with a word in the search query using the processor;

retrieving from the entry candidate positions for the word and their probabilities using the processor;

ranking the speech signals based on the probabilities of the candidate positions to form ranked speech signals using the processor; and

returning search results to the user based on the ranked speech signals using the processor, the search results comprising an identification of one or more of the spoken documents.

6. The method of claim 5, wherein eliminating the positions comprises comparing the probabilities of the positions to the first threshold value and eliminating those positions whose probabilities fail to reach a predefined relationship to the first threshold value using the processor.

7. The method of claim 5, further comprising:

receiving a second threshold value from the user;

replacing the first threshold with the second threshold;

eliminating the candidate positions based on a comparison of their probabilities to the second threshold value using the processor;

ranking the speech signals based on the probabilities of the remaining candidate positions relative to each other to form ranked speech signals using the processor; and

returning search results to the user based on the ranked speech signals using the processor, the search results comprising an identification of one or more of the spoken documents.

8. A computer-implemented method of searching a speech index comprising:

accessing a speech index of a plurality of spoken documents each comprising a collection of speech signals using a processor;

receiving a search query from a user using the processor;

modifying a word of the search query using the processor;

receiving a first threshold value from the user using the processor;

searching the speech index for an entry associated with the modified word using the processor;

retrieving from the entry a plurality of candidate positions for the modified word in a plurality of the speech signals, and a probability of the modified word appearing at each of the candidate positions given the corresponding speech signal, using the processor;

eliminating the candidate positions based on a comparison of their probabilities to the first threshold value using the processor;

ranking the speech signals based on the probabilities of the remaining candidate positions relative to each other to form ranked speech signals using the processor; and

returning search results to the user based on the ranked speech signals using the processor, the search results comprising an identification of one or more of the spoken documents.

9. The method of claim 8, wherein eliminating the candidate positions comprises comparing the probabilities of the candidate positions to the first threshold value and eliminating those candidate positions whose probabilities fail to reach a predefined relationship to the first threshold value using the processor.