Patent ID: 7165030

Claim:
A method for selecting segments from a corpus of source utterances for synthesizing a target utterance, comprising: searching a precomputed graph in which each path through the graph identifies a sequence of segments of the corpus of source utterances and a corresponding sequence of unit labels that characterizes a pronunciation of a concatenation of that sequence of segments, each path a numerical score that characterizes a quality of the sequence of segments; wherein searching the precomputed graph includes matching a pronunciation of the target utterance to paths through the graph, and selecting segments for synthesizing the target utterance based on numerical scores of matching paths through the graph; the precomputed graph includes a first part that encodes a sequence of segments and a corresponding sequence of unit labels for each of the source utterances, and a second part computed in advance of run-time when the target utterance is known that includes paths for coupling segments of the source utterances and encodes allowable transitions between segments of different source utterances and encodes a transition score for each of those transitions; and matching the pronunciation of the target utterance to paths through the graph includes considering paths in which each transition between segments of different source utterances identified by that path corresponds to a different subpath of that path that passes through the second part of the graph.