Multiresolution searching
View Patent ↗This invention relates to processing of audio files, and more specifically, to an improved technique of searching audio. More particularly, a method and system for processing audio using a multi-stage searching process is disclosed.
1. A method for searching an audio source for occurrence of a search string, the method comprising:
processing the audio source using a computer to generate a first representation of the audio source that includes scores associated with the occurrence of a plurality of audio states;
generating a second representation of the audio source using a computer, the second representation having a plurality of parts, each part corresponding to a different part of the first representation, the second representation comprising fewer entries than the first representation;
using a computer, using the search string and the second representation to determine a set of candidate locations in the audio source; and
searching the candidate locations using a computer using the search string and the first representation.
2. The method of claim 1 , wherein generating the second representation of the audio source comprises processing the first representation to generate the second representation.
3. The method of claim 2 , wherein:
processing the audio source to generate the first representation comprises processing the audio source according to a first set of audio states independently of the search string; and
generating the second representation of the audio source comprises processing the audio source according to a second set of audio states independently of the search string.
4. The method of claim 2 , wherein processing the first representation to generate the second representation comprises reducing a number of states in the state dimension.
5. The method of claim 4 , wherein the states include states of phonemes and reducing the number of states includes reducing the number of states for at least some of the phonemes.
6. The method of claim 4 , wherein reducing the number of states comprises reducing the number of states from two-states-per-phoneme in the first representation to one-state-per-phoneme in the second representation.
7. The method of claim 2 , wherein processing the first representation to generate the second representation comprises merging phonemes in the first representation by class to generate the second representation.
8. The method of claim 7 , wherein reducing the frame rate comprises reducing the frame rate by a factor of 3 or greater.
9. The method of claim 2 , wherein processing the first representation to generate the representation comprises reducing a frame rate.
10. The method of claim 2 , wherein processing the first representation to generate the second representation comprises reducing a number of states and reducing a frame rate.
11. The method of claim 2 , wherein processing the first matrix to generate the second matrix comprises:
reducing a number of states by a factor of at least about 2; and
reducing a frame rate by a factor of at least about 3.
12. The method of claim 1 , wherein:
the first representation comprises a first matrix having a time frame dimension and a state dimension, wherein the probabilities associated with the occurrence of a plurality of audio states are stored as entries in the first matrix; and
the second representation comprises a second matrix having a time frame dimension and a state dimension, the second matrix having fewer entries than the first matrix.
13. The method of claim 12 , wherein generating the second representation of the audio source comprises processing the first matrix to generate the second matrix.
14. The method of claim 13 , wherein processing the first matrix to generate the second matrix comprises reducing a number of states.
15. The method of claim 14 , wherein each part of the second representation comprises a quantization of quantities in the corresponding part of the first representation.
16. The method of claim 1 , wherein:
the first representation comprises a first lattice; and
the second representation comprises a second lattice, the second lattice having fewer entries than the first lattice.
17. The method of claim 16 , wherein generating the second representation of the audio source comprises processing the first lattice to generate the second lattice.
18. The method of claim 17 , wherein states of the second representation correspond to classes of states of the first representation.
19. The method of claim 1 , further comprising:
accepting the search string;
generating a first representation of the search string for use with the first representation of the audio source; and
generating a second representation of the search string for use with the second representation of the audio source.
20. The method of claim 19 , wherein:
using the search string and the second representation to determine a set of candidate locations in the audio source comprises using the second representation of the search string and the second representation of the audio source to determine a set of candidate locations in the audio source; and
searching the candidate locations using the search string and the first representation comprises searching the candidate locations using the first representation of the search string and the first representation of the audio source.
21. The method of claim 1 , the method further comprising:
generating a third representation of the audio source, the third representation having a plurality of parts, each part in the first representation corresponding to a different part of the third representation, the first representation comprising fewer entries than the third representation.
22. The method of claim 21 , wherein:
the set of candidate locations comprises a first set of candidate locations; and
searching the candidate locations using the search string and the first representation comprises generating a second set of candidate locations, and the method further comprises:
searching the second set of candidate locations using the search string and the third representation.
23. A method for searching an audio source for occurrence of a search string, the method comprising:
processing the audio source using a computer to generate a first matrix or lattice, the first matrix or lattice including probabilities associated with the occurrence of a plurality of audio states within a time frame;
processing the first matrix or lattice using a computer to generate a second matrix or lattice that includes probabilities associated with the occurrence of a plurality of audio states within a time frame, the second matrix or lattice having fewer entries than the first matrix or lattice;
determining, using a computer, a set of candidate locations in the audio source by searching for the search string using the second matrix or lattice; and
searching the candidate locations using a computer using the search string and the first matrix or lattice.
24. A method for searching an audio source for occurrence of a search string, the method comprising:
processing the audio source using a computer according to a first set of audio states independently of the search string;
storing, using a computer, for a plurality of time frames, a first set of quantities characterizing probabilities associated with the occurrence of each of the audio states in the first set of audio states;
processing the audio source using a computer according to a second set of audio states independently of the search string;
storing, using a computer, for a plurality of time frames, a second set of quantities characterizing probabilities associated with the occurrence of each of the audio states in the second set of audio states, the second set of audio states comprising fewer audio states than the first set of audio states;
accepting the search string using a computer;
using a computer, using the search string and the second set of quantities to identify a set of candidate locations in the audio source; and
using a computer, using the search string and the first set of to search for the search string within the identified candidate locations.
25. The method of claim 24 , further comprising providing a set of one or more hits for the search string in the audio source based on a result of the search of the candidate locations.
26. The method of claim 24 , wherein
said first set of audio states comprise R 1 plus M 1 time N 1 states, where M 1 is a number of states per phoneme, N 1 is a number of different phonemes, and R 1 is a number of bridge states;
said second set of audio states comprise R 2 plus M 2 time N 2 states, where M 2 is a number of states per phoneme, N 2 is a number of different phonemes, and R 2 is a number of bridge states; and
M 1 is less than M 2 .
27. The method of claim 24 , wherein
said first set of audio states comprise R 1 plus M 1 time N 1 states, where M 1 is a number of states per phoneme, N 1 is a number of different phonemes, and R 1 is a number of bridge states;
said second set of audio states comprise R 2 plus M 2 time N 2 states, where M 2 is a number of states per phoneme, N 2 is a number of different phonemes, and R 2 is a number of bridge states; and
N 1 is less than N 2 .
28. The method of claim 24 , wherein:
processing the audio source according to a first set of audio states comprises constructing a first matrix having a time frame dimension and a state dimension, each entry in the first matrix representing a quantity characterizing a probability of an audio state occurring in a time frame; and
processing the audio source according to a second set of audio states comprises constructing a second matrix having a time frame dimension and a state dimension, each entry in the second matrix representing a quantity characterizing a probability of an audio state occurring in a time frame, the second matrix having less entries in the time frame dimension that the first matrix.
29. The method of claim 24 , wherein the set of candidate locations comprise locations in the audio source having a shorter duration than the entire audio source.