Word predicting method, voice recognition method, and voice recognition apparatus and program using the same methods

• US 7,480,612 B2
• Filed: 08/22/2002
• Issued: 01/20/2009
• Est. Priority Date: 08/24/2001
• Status: Expired due to Fees

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Mori, Shinsuke, Nishimura, Masafumi, Itoh, Nobuyasu
• Primary Examiner(s): Wozniak; James S
• Application Number:
  US10/226,564
• Publication Number:
  US 20030046073A1
• Time in Patent Office: 2,343 Days
• Field of Search: 704/251, 704/255, 704/257, 704/231, 704/9, 704/1
• US Class Current: 704/9
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

A word predicting method for use with a voice recognition using a computer includes the steps of specifying a sentence structure of a history up to a word immediately before the word to be predicted, referring to a context tree stored in arboreal context tree storage section having information about possible structures of a sentence and a probability of appearance of words with respect to the structures at nodes, and predicting words based on the context tree and the specified sentence structure of the history.

Claims

1. A word predicting method of predicting words in a predetermined sentence by using a computer, comprising the steps of:

retrieving a history tree of word prediction covering words before a word to be predicted to be used in predicting words from a word prediction history storage means where a word prediction history of partial parse trees is stored;

dynamically selecting a shape of a partial parse tree as a word prediction reference range by specifying a sentence structure of said history;

acquiring an arboreal context tree for word prediction from a context tree storage means, which stores said context tree having information about possible structures of a sentence and a probability of appearance of words with respect to said structures at nodes;

comparing at least one node of said arboreal context tree to said history tree;

identifying a node of said arboreal context tree having a partial tree matched with said history tree;

using a probability distribution appended to the identified node of the arboreal context tree to predict a word to be predicted; and

outputting the predicted word.

2. The word predicting method according to claim 1, wherein said history is a row of partial parse trees, and the possible structures of the sentence at nodes of said context tree comprise a tree structure, and said word predicting method further comprises a step of predicting a word to be predicted by comparing a tree consisting of a virtual root having said row of partial parse trees directly under it added to said row of partial parse trees with said tree structure at the nodes of said context tree.

3. The word predicting method according to claim 1, further comprising the step of:

acquiring a context tree for sentence structure prediction from said context tree storage unit, which stores the context tree having the information about possible structures of the sentence and the probability of appearance of the sentence structure following said structures at nodes; and

predicting the sentence structure containing a predicted word, based on said predicted word, said sentence structure used in predicting said word, and said acquired context tree for sentence structure prediction, and storing said sentence structure in said history storage unit.

4. A data processing method comprising the steps of:

retrieving a processing history tree of word prediction covering words before a word to be predicted to be used in predicting a predetermined element from a word prediction history storage unit storing said processing history of partial parse trees for an array;

dynamically selecting a range of processing history for use as a word prediction reference range by acquiring a stochastic model from a stochastic model storage unit storing the stochastic model for the tree structure having predetermined partial trees and a probability distribution associated with said partial trees at nodes;

comparing at least one node of said stochastic model to said history tree to identify a node of said stochastic model having a partial tree corresponding to the tree structure of said processing history for said stochastic model,

using a probability distribution appended to the identified node of the stochastic model to predict said predetermined element; and

outputting the predicted element.

5. A computer-readable program storage medium readable by computer and tangibly embodying a program of instructions stored on the medium and executable by the machine for causing the computer to perform a method for predicting words in a predetermined sentence by controlling a computer,

wherein said method comprises the steps of:

retrieving a history tree of word prediction covering words before a word to be predicted to be used in predicting words from a word prediction history storage means where a word prediction history of partial parse trees is stored;

dynamically selecting a shape of a partial parse tree as a word prediction reference range by specifying a sentence structure of said history;

acquiring an arboreal context tree for word prediction from a context tree storage means, which stores said context tree having information about possible structures of a sentence and a probability of appearance of words with respect to said structures at nodes;

comparing at least one node of said arboreal context tree to said history tree;

identifying a node of said arboreal context tree having a partial tree matched with said history tree;

using a probability distribution appended to the identified node of the arboreal context tree to predict a word to be predicted; and

outputting the predicted word.

6. A computer-readable program storage medium readable by computer and tangibly embodying a program of instructions stored on the medium and executable by the machine for causing the computer,

wherein said method comprises the steps of:

retrieving a processing history tree of word prediction covering words before a word to be predicted to be used in predicting a predetermined element from a word prediction history storage unit storing said processing history of partial parse trees for an array;

dynamically selecting a range of processing history for use as a word prediction reference range by acquiring a stochastic model from a stochastic model storage unit storing the stochastic model for the tree structure having predetermined partial trees and a probability distribution associated with said partial trees at nodes;

comparing at least one node of said stochastic model to said history tree to identify a node of said stochastic model having a partial tree corresponding to the tree structure of said processing history for said stochastic model,

using a probability distribution appended to the identified node of the stochastic model to predict said predetermined element; and

outputting the predicted element.