INDEXING AND SEARCHING AUDIO USING TEXT INDEXERS

• US 20090150337A1
• Filed: 12/07/2007
• Published: 06/11/2009
• Est. Priority Date: 12/07/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Seide, Frank T.B., Yu, Peng, Thambiratnam, Albert Joseph Kishan
• Granted Patent: US 8,060,494 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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

Abstract

A full-text lattice indexing and searching system and method for indexing word lattices using a text indexer to enable enhance searching of audio content. The system and method utilize a Time-Anchored Lattice Expansion (TALE) method that represents word lattices such that they can be indexed with existing text indexers with little or no modification. Embodiments of system and method include an indexing module for generating and indexing word lattices based on audio content and a searching module for allowing searching of a full-text index containing indexed word lattices. The indexing module includes a custom IFilter and a custom Wordbreaker. Embodiments of the searching module include an ExpandQuery function for decorating an input query and a custom Stemmer. Embodiments of the searching module also include a GenerateSnippets module that extracts information from the indexed word lattices to enable the creation of clickable snippets.

Claims

1. A computer-implemented method for processing audio content, comprising:

generating word lattices for the audio content, the word lattices containing a plurality of word candidates and nodes that are connections between the word candidates; and

indexing the word lattices using a text indexer of a full-text search engine such that the audio content is contained in a full-text index as indexed audio content.

2. The computer-implemented method of claim 1, further comprising binning the word lattice to organize each word lattice in columns containing the words candidates and associated confidence scores, each confidence score defined as a likelihood that the word candidate is a possible substitute for a query term.

3. The computer-implemented method of claim 2, further comprising:

quantizing a plurality of confidence scores into a discrete number of confidence scores; and

decorating a word candidate with a confidence score by appending to the word candidate a suffix corresponding to that confidence score.

4. The computer-implemented method of claim 3, further comprising:

encoding each word lattice column as a single linear text string by concatenating each word in the column with a separation character; and

outputting the single linear text string from a text ingestion plug-in of the full-text search engine.

5. The computer-implemented method of claim 4, further comprising:

inputting the single linear text string to a Wordbreaker of the full-text search engine;

decoding the single linear text string to recover the word lattice columns and associated confidence scores; and

storing the word lattice columns and associated confidence scores in the full-text index.

6. The computer-implemented method of claim 1, further comprising:

inputting a query from a user containing at least one search term and a desired confidence level; and

searching the indexed audio content to obtain search results corresponding to the query and the desired confidence level.

7. The computer-implemented method of claim 6, further comprising decorating the query with the desired confidence level and all confidence levels better than the desired confidence level by appending to the search term a suffix corresponding to the desired confidence level and all confidence levels better than the desired confidence level to obtain a decorated query.

8. The computer-implemented method of claim 7, further comprising:

inputting the decorated query into a Wordbreaker of the full-text search engine; and

expanding the decorated query into a plurality of decorated queries corresponding whose number is equal to a sum of the desired confidence level plus a number of all confidence levels better than the desired confidence level.

9. The computer-implemented method of claim 8, further comprising:

inputting the plurality of decorated queries into a custom Stemmer; and

stripping off the decorations of each of the plurality of decorated queries by removing each suffix to obtain stripped queries; and

storing each suffix associated with each of the plurality of decorated queries for future appending.

10. The computer-implemented method of claim 9, further comprising:

inputting the stripped queries into an original Stemmer of the full-text search engine;

obtaining from the original Stemmer variations of each of the stripped queries to obtain query variations;

inputting the stripped queries and the query variations into the custom Stemmer;

appending the removed suffixes to their proper stripped queries and the query variations to obtain an expanded set of decorated queries; and

searching the full-text index using the expanded set of decorated queries.

11. A method for fitting a word lattice into a word slot of a text indexer of a full-text search engine, comprising:

generating a word lattice that is a weighted directed acyclic graph having arcs that represent a plurality of word candidates with associated confidence levels and nodes that are connections between the word candidates;

finding time boundaries for each of the plurality of word candidates and using these time boundaries as anchor points; and

binning the plurality of word candidates by aligning each node in the lattice to its nearest anchor point in time to enable the indexing of the word lattice by the text indexer.

12. The method of claim 11, further comprising finding a start time and an end time for each of the plurality of word candidates corresponding to the time boundaries.

13. The method of claim 12, further comprising:

retaining expected term frequencies of the word lattice to aid in ranking the plurality of word candidates;

keeping approximate time points of an individual search results or hit corresponding to a desired word candidate to allow playback of the desired word candidate; and

have phrases of three words or greater in consecutive word positions.

14. The method of claim 13, further comprising performing a P_Δ

-expansion by computing a probability distribution for a word slot i of words ω

being the Δ

-th token of a phrase given by the equation;

$P_{\mathrm{\Delta <br><br>}}<br><br>\left(\mathrm{\omega <br><br>}<br><br>i,O\right)=\underset{\forall <br><br>n;<br><br>s_n+\mathrm{\Delta <br><br>}=i}{\sum <br><br>}<br><br>P(<br><br>\begin{array}{c}*\end{array}<br><br>-n-*<br><br>O)·<br><br>P<br><br>\left(\mathrm{\omega <br><br>}<br><br>n,\mathrm{\Delta <br><br>},O\right)$

where O is an observed audio recoding, P(-n-*|O) is a node posterior, and S_n is a word slot that is closest to a node n and aligned with node n.

15. The method of claim 14, further comprising interpolating multiple P_Δ

-expansions to retain a words of the phrase in consecutive word slots using the equation;

$P<br><br>\left(\mathrm{\omega <br><br>}<br><br>i,O\right)=\underset{\mathrm{\Delta <br><br>}=1}{\overset{M}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{\Delta <br><br>}}·<br><br>P_{\mathrm{\Delta <br><br>}}<br><br>\left(\mathrm{\omega <br><br>}<br><br>i,O\right)$

where α

_n are the weights and Σ

α

_n=1.

16. A full-text lattice indexing and searching system for indexing and searching audio content of a document using a text indexer of a full-text search engine, comprising:

an indexing module that uses standard and custom functionality to place a word lattice in a searchable index, the indexing module further comprising;

a custom index function that uses a time-anchored lattice expansion technique to enable a word lattice of the audio content to be indexed by the text indexer; and

a searching module that uses standard and custom functionality to search the searchable index for indexed word lattices.

17. The full-text lattice indexing and searching system of claim 16, further comprising:

a full-text search engine table formatted such that word candidates of the word lattice are in a column corresponding to a word slot in the text indexer;

a custom IFilter that decorates each word candidate by appending a suffix representing a confidence score for that word candidate and then encodes each column of the table as a single linear text string by placing a separation character between each of the word candidates in the column.

18. The full-text lattice indexing and searching system of claim 17, further comprising:

a custom Wordbreaker that decodes the single linear text string to recover the word candidates and their associated confidence scores; and

a custom locale identifier (LCID) that is used to call the custom Wordbreaker after processing by the custom IFilter; and

a full-text index that stores the word candidates and their associated confidence scores in a searchable database.

19. The full-text lattice indexing and searching system of claim 18, further comprising:

a query containing a search term and a threshold containing a desired confidence level;

an ExpandQuery function that decorates the search term by appending a suffix to the search term representing the desired confidence level and any confidence levels having greater confidence than the desired confidence level to obtain a decorated query; and

the custom Wordbreaker that expands the decorated query into a plurality of decorated queries containing a single appended confidence score corresponding to the desired confidence level and any confidence levels having greater confidence than the desired confidence level.

20. The full-text lattice indexing and searching system of claim 19, further comprising:

a custom Stemmer that removes the decorations from each of the plurality of decorated queries by removing the suffixes and then stores the suffixes;

an original Stemmer that processes the plurality of decorated queries having removed suffixes to find additional word variations;

a set of re-decorated queries that are obtained by re-appending associated stored suffixes to the plurality of decorated queries having removed suffixes and the additional word variations;

search results that are obtained by searching the full-text index using the expanded set of re-decorated queries and displayed to a user; and

a GenerateSnippets function that extracts time information from each search result to allow the user to click on a displayed search result and be taken to that position in the document containing that search result.