Aligning a transcript to audio data

• US 8,131,545 B1
• Filed: 09/25/2008
• Issued: 03/06/2012
• Est. Priority Date: 09/25/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Moreno, Pedro J., Alberti, Christopher
• Primary Examiner(s): Azad, Abul
• Application Number:
  US12/238,257
• Time in Patent Office: 1,258 Days
• Field of Search: 704/235, 704/260, 704/257
• US Class Current: 704/235
• CPC Class Codes: G10L 15/04 Segmentation; Word boundary detection

Abstract

The subject matter of this specification can be implemented in, among other things, a computer-implemented method including receiving audio data and a transcript of the audio data. The method further includes generating a language model including a factor automaton that includes automaton states and arcs, each of the automaton arcs corresponding to a language element from the transcript. The method further includes receiving language elements recognized from the received audio data and times at which each of the recognized language elements occur in the audio data. The method further includes comparing the recognized language elements to one or more of the language elements from the factor automaton to identify times at which the one or more of the language elements from the transcript occur in the audio data. The method further includes aligning a portion of the transcript with a portion of the audio data using the identified times.

Claims

1. A computer-implemented method, comprising:

receiving audio data and a transcript of the audio data;

generating, from the transcript, a language model comprising a factor automaton that includes automaton states and arcs, each of the automaton arcs corresponding to a language element from the transcript;

receiving, from a speech recognizer, language elements recognized from the received audio data and times at which the recognized language elements occur in the audio data;

comparing the recognized language elements from the audio data to one or more of the language elements from the transcript and represented by the factor automaton to identify times at which the one or more of language elements from the transcript occur in the audio data;

aligning a portion of the transcript with a portion of the audio data using the identified times; and

outputting the aligned portion of the transcript.

2. The method of claim 1, wherein the language elements from the transcript and the recognized language elements comprise words, syllables, phonemes, or phones.

3. The method of claim 1, wherein comparing comprises transitioning between two automaton states in the factor automaton when a recognized language element is successfully matched with a language element represented by an arc between the two automaton states.

4. The method of claim 1, wherein comparing the recognized language elements to the one or more of language elements from the factor automaton further comprises searching the factor automaton for a language element that substantially matches a recognized language element.

5. The method of claim 4, wherein searching further comprises ending the comparison or continuing to a next automaton state adjacent to a previous automaton state connected by an arc, the arc representing the last language element from the transcript that was successfully matched to a recognized language element.

6. The method of claim 1, wherein transitions from the automaton states in the factor automaton comprise a self loop that permits a state to transition to itself instead of transitioning to a different state.

7. The method of claim 6, wherein the self loop permits one or more of the recognized language elements having no corresponding language element in the one or more language elements in the factor automaton to be accounted for in the alignment of the transcript.

8. The method of claim 6, wherein the self loop permits a portion of the audio having no recognized language elements to be accounted for in the alignment of the transcript.

9. The method of claim 1, wherein the factor automaton allows the one or more language elements from the factor automaton to begin at an automaton state located anywhere in the factor automaton.

10. The method of claim 1, wherein generating the language model of the transcript comprises generating a list of transitions, each of the transitions including an identifier of a source automaton state, an identifier of a destination automaton state, and a corresponding language element from the transcript.

11. The method of claim 1, further comprising estimating times at which the one or more language elements from the factor automaton likely occur in the audio data, and weighting the comparison of the recognized language elements and the one or more language elements from the factor automaton based on a difference between the estimated times and the times associated with the recognized language elements from the audio data.

12. The method of claim 1, further comprising determining a level of confidence for the alignment of a portion of the one or more language elements from the factor automaton with the recognized language elements from the audio.

13. The method of claim 12, further comprising selecting audio data and transcript portions associated with the level of confidence when the level does not meet a threshold level of confidence.

14. The method of claim 13, further comprising iteratively performing the method of claims 1, 12, and 13 on the selected audio data and transcript portions until the threshold level is met for the selected audio data and transcript portions or until a stop condition occurs.

15. The method of claim 14, wherein the stop condition comprises a number of iterations, an indication that the confidence level is within a satisfactory range from the threshold level, an elapsed period of time, or an amount of processing power used.

16. The method of claim 1, wherein steps of claim 1 are distributed across multiple systems.

17. The method of claim 1, further comprising outputting the received audio with the output aligned portion of the transcript.

18. The method of claim 17, further comprising storing the output audio and the aligned portion of the transcript in a training corpus configured for use in training speech recognition systems.

19. The method of claim 1, wherein the received audio data is based on television broadcasts, online videos, audio books, or music.

20. The method of claim 1, wherein the received transcript is based on closed captions, lyrics, or books.

21. A computer-implemented method comprising:

receiving audio data and a transcript of the audio data;

generating a graph comprising states and arcs that represent language elements in the transcript, wherein the states are linked in a configuration to permit the representation of substantially all possible phrases that occur within the received transcript;

generating a speech hypothesis of one or more language elements included in the audio using a speech recognizer, wherein the speech hypothesis includes time stamps associated with an occurrence of each of the one or more language elements;

comparing the one or more language elements of the speech hypothesis with one or more arcs in the graph; and

associating at least a portion of the language elements of the transcript with the time stamps based on the comparison.

22. The method of claim 21, wherein the graph comprises a factor automaton.

23. A computer-implemented system, comprising:

one or more computers having

an interface that receives audio data and a transcript of the audio data;

a model builder module that generates, from the transcript, a language model comprising a factor automaton that includes automaton states and arcs, each of the automaton arcs corresponding to a language element from the transcript;

a storage device that stores the factor automaton;

a speech recognizer that recognizes language elements from the received audio data and determines times at which each of the recognized language elements occur in the audio data; and

means for comparing the recognized language elements to one or more of the language elements from the stored factor automaton to identify times at which the one or more of the language elements from the transcript occur in the audio data and aligning a portion of the transcript with a portion of the audio data using the identified times, and outputting the aligned portion of the transcript.