1. An interactive method for composing an alphanumeric message using a telephone keypad, comprising in a messaging terminal the steps of: storing a received sequence of key codes that identifies a sequence in which keys on a telephone style keypad are pressed by a caller in order to enter the alphanumeric message; generating a word trellis from the sequence of key codes, the word trellis comprising at least one subset of candidate words recovered from a lexical database, each of the at least one subset of candidate words corresponding to one subsequence of the sequence of key codes; determining a most likely phrase having a maximum combined probability determined from probabilities stored in the lexical database, that comprises candidate words that are a combination of one candidate word from each of the at least one subset of candidate words; generating a most likely message from the most likely phrase and presenting the most likely message to the caller; confirming that the most likely message is the alphanumeric message; and editing the most likely message when, in response to the step of confirming, a message non-confirmation is received from the caller, wherein the step of editing the alphanumeric message further comprises the steps of: prompting the caller to speak an edit command; recognizing the edit command as one of a predetermined set of edit commands; and performing the edit command using voice recognition that is governed by a subsequence of the sequence of key codes.
1. An interactive method for composing an alphanumeric message using a telephone keypad, comprising in a messaging terminal the steps of: storing a received sequence of key codes that identifies a sequence in which keys on a telephone style keypad are pressed by a caller in order to enter the alphanumeric message; generating a word trellis from the sequence of key codes, the word trellis comprising at least one subset of candidate words recovered from a lexical database, each of the at least one subset of candidate words corresponding to one subsequence of the sequence of key codes; determining a most likely phrase having a maximum combined probability determined from probabilities stored in the lexical database, that comprises candidate words that are a combination of one candidate word from each of the at least one subset of candidate words; generating a most likely message from the most likely phrase and presenting the most likely message to the caller; confirming that the most likely message is the alphanumeric message; and editing the most likely message when, in response to the step of confirming, a message non-confirmation is received from the caller, wherein the step of editing the alphanumeric message further comprises the steps of: prompting the caller to speak an edit command; recognizing the edit command as one of a predetermined set of edit commands; and performing the edit command using voice recognition that is governed by a subsequence of the sequence of key codes. 4. The method according to claim 1, wherein the step of recognizing an edit command comprises the step of recognizing a spelling command for a word of the alphanumeric message, and wherein the step of performing the edit command further comprises the steps of: prompting for a sequence of vocalized letters in response to the spelling command; recording the sequence of vocalized letters; and performing voice recognition using a alphabet recognizer that matches the sequence of vocalized letters to the subsequence of the sequence of keycodes.