(57)【特許請求の範囲】
【請求項１】
メッセージング端末により、電話キーパッドへのユーザ入力に基づく英数字メッセージの一部分を作成する方法であって、：
複数の単語および複数の関連する確率を含む辞書データベースを格納する段階；
前記英数字メッセージを入力するために、電話キーパッド上のキーが押されるシーケンスに対応するキー・コードのシーケンスを受信する段階；
キー・コードの前記シーケンスから単語格子を生成する段階であって、前記単語格子は、前記辞書データベースから復元される候補単語のサブセットを含む、段階；および
前記辞書データベースに格納された確率から決定される最大組合せ確率を有する最もありそうな語句であって、候補単語の前記サブセットからの候補単語の組合せを含む、最もありそうな語句を決定する段階；
を備えることを特徴とする方法。
【請求項２】
前記最もありそうな語句から最もありそうなメッセージを生成し、前記最もありそうなメッセージを前記ユーザに提示する段階；および
前記英数字メッセージが前記最もありそうなメッセージから得られていることを確定する段階；
を、さらに備えることを特徴とする請求項１記載の方法。
【請求項３】
前記確定する段階に応答して、前記ユーザからメッセージ非確定が受信される場合に、前記最もありそうなメッセージを編集する段階；
を、さらに備えることを特徴とする請求項２記載の方法。
【請求項４】
前記最もありそうなメッセージを編集する前記段階において、前記編集はオペレータによって行われる入力に応答して実行されることを特徴とする請求項３記載の方法。
【請求項５】
前記最もありそうなメッセージを編集する前記段階は：
前記確定する段階に応答して、前記ユーザからメッセージ非確定が受信される場合に、前記最もありそうなメッセージのうち１つまたはそれ以上の不適切な候補単語を決定し、全ての残りの候補単語を前記最もありそうなメッセージの確定済み候補単語として決定する段階；
一つまたはそれ以上の不適切な候補単語を決定する前記段階に応答して、一つまたはそれ以上の不適切な候補単語のそれぞれに対応する前記英数字メッセージの発声単語を発声するように前記ユーザに対して要求を提示する段階；
前記発声単語を記録する段階；および
前記確定済み候補単語および前記発声単語をオペレータに提示する段階；
を備えることを特徴とする請求項４記載の方法。
【請求項６】
前記最もありそうなメッセージを編集する前記段階は：
ユーザの応答から、前記最もありそうなメッセージから不適切な候補単語を決定する段階であって、前記不適切な候補単語は、候補単語の第１サブセットにある、段階；および
候補単語の第１サブセットの他の候補単語をユーザに提示する段階であって、前記提示は、第１サブセットの全ての候補単語が提示されるか、あるいは単語確定がユーザから受信されるまで、ユニグラム確率の降順で、一度に一つの単語を生じさせて提示する段階；
を、さらに備えることを特徴とする請求項３記載の方法。
【請求項７】
前記最もありそうなメッセージを編集する前記段階は：
次のありそうなメッセージを提示する段階；
を、さらに備えることを特徴とする請求項３記載の方法。
【請求項８】
前記最もありそうなメッセージを編集する前記段階は：
ユーザの応答から、前記最もありそうなメッセージから不適切な候補単語を決定する段階であって、前記不適切な候補単語は、候補単語の第１サブセットにある、段階；および
候補単語の第１サブセットの他の候補単語をユーザに提示する段階であって、前記提示は、第１サブセットの全ての候補単語が提示されるか、あるいは単語確定がユーザから受信されるまで、ユニグラム確率の降順で、一度に一つの単語を生じさせて提示する段階；
を、さらに備えることを特徴とする請求項７記載の方法。
【請求項９】
前記最もありそうなメッセージを編集する前記段階は：
ユーザに編集コマンドを発声するように促す段階；
編集コマンドの所定のセットのうちの一つとして、前記編集コマンドを認識する段階；および
キー・コードのシーケンスのうちのサブシーケンスによって支配される音声認識を利用して、前記編集コマンドを実行する段階；
を、さらに備えることを特徴とする請求項３記載の方法。
【請求項１０】
前記辞書データベースを格納する段階は：
複数の単語についてユニグラム確率，順方向条件付き確率および逆方向条件付き確率を含む辞書データベースを格納する段階；
を備えることを特徴とする請求項１記載の方法。
【請求項１１】
前記最もありそうな語句を決定する段階は：
前記辞書データベースに格納された少なくとも順方向条件付き確率および逆方向条件付き確率から決定された最大組合せ確率を有する最もありそうな語句を決定する段階；
を備えることを特徴とする請求項１０記載の方法。
【請求項１２】
前記単語格子を生成する前記段階は：
キー・コードの前記受信シーケンスのうちＮサブシーケンスを決定する段階であって、前記Ｎサブシーケンスは、キー・コードの所定のセットによってキー・コードの前記受信シーケンス内で区分されたキー・コードのサブシーケンスである、段階；および
前記Ｎサブシーケンスの前記辞書データベースへの入力に基づいて、前記辞書データベースから候補単語の前記サブセットを復元する段階；
を備えることを特徴とする請求項１記載の方法。
【請求項１３】
メッセージング端末により、電話キーパッドを利用して発呼者により入力された英数字メッセージから単語格子を生成する方法であって、：
複数の単語および複数の関連する確率を備えた辞書データベースを格納する段階；
前記英数字メッセージを入力するために、電話キーパッド上のキーが押されるシーケンスに対応するキー・コードのシーケンスを受信する段階；および
キー・コードの前記シーケンスから単語格子を生成する段階であって、前記単語格子は、前記辞書データベースから復元される候補単語の少なくとも一つのサブセットを含み、前記生成する段階は：
キー・コードの前記受信シーケンスのうちＮサブシーケンスを決定する段階であって、前記Ｎサブシーケンスはキー・コードの所定のセットによってキー・コードの前記受信シーケンス内で区分されたキー・コードのサブシーケンスである、段階と、
前記Ｎサブシーケンスを前記辞書データベース内へ入力する段階と、
前記辞書データベースからナル・サブセットが復元された場合に、前記Ｎサブシーケンスのうちの一つを誤りサブシーケンスとして識別する段階と、
前記誤りサブシーケンスを利用して、キーパッド誤り訂正を行う段階と、
を備える、単語格子を生成する段階；
を備えることを特徴とする方法。
【請求項１４】
キーパッド誤り訂正を行う前記段階は：
異なるキー・コードを前記誤りサブシーケンス内のキー・コードのうちの一つと置換することにより、前記誤りサブシーケンスから新規サブシーケンスを生成する段階；および
前記新規サブシーケンスに基づいて、前記辞書データベースから候補単語のサブセットを復元する段階；
を備えることを特徴とする請求項１３記載の方法。
【請求項１５】
キーパッド誤り訂正を行う前記段階は：
前記誤りサブシーケンス内のキー・コードのうちの一つを削除することにより、前記誤りサブシーケンスから新規サブシーケンスを生成する段階；および
前記新規サブシーケンスに基づいて、前記辞書データベースから候補単語のサブセットを復元する段階；
を備えることを特徴とする請求項１３記載の方法。
【請求項１６】
キーパッド誤り訂正を行う前記段階は：
前記誤りサブシーケンス内のキー・コードに隣接する挿入ポイントを選択することにより、前記誤りサブシーケンスから新規サブシーケンスを生成する段階；
前記挿入ポイントにてキー・コードを挿入し、編集された新規サブシーケンスを生成する段階；および
前記編集された新規サブシーケンスに基づいて、前記辞書データベースから候補単語のサブセットを復元する段階；
を備えることを特徴とする請求項１３記載の方法。
【請求項１７】
キーパッド誤り訂正を行う前記段階は：
前記誤りサブシーケンス内で２つの連続したキー・コード間の挿入ポイントを選択する段階；
前記誤りサブシーケンスを、前記挿入ポイントにて２つの新規サブシーケンスに分割する段階；および
前記２つの新規サブシーケンスに基づいて、前記辞書データベースから候補単語の２つのサブセットを復元する段階；
を備えることを特徴とする請求項１３記載の方法。
【請求項１８】
メッセージング端末により、電話キーパッドを利用して発呼者により入力された英数字メッセージを作成する方法であって、：
複数の単語および複数の関連する確率を備える辞書データベースを格納する段階；
前記英数字メッセージを入力するために、電話キーパッド上のキーが押されるシーケンスに対応するキー・コードのシーケンスを受信する段階；
キー・コードの前記シーケンスから単語格子を生成する段階であって、前記単語格子は、前記辞書データベースから復元される候補単語のサブセットを含む、段階；
候補単語の前記サブセットから前記英数字メッセージを生成する段階であって：
候補単語の全てのサブセット内の全ての候補単語を提示する段階であって、全ての候補単語は、候補単語の各サブセットから前記発呼者に、一度に一つの候補単語が提示される、段階；および
前記提示する段階中に、一つまたはそれ以上の発呼者応答によって、候補単語の第１サブセットからの候補単語を確定する段階、または
前記提示する段階中に、一つまたはそれ以上の発呼者応答によって、候補単語の第１サブセットを非確定する段階
のうちの一つ、
を備える、前記英数字メッセージを生成する段階；
を備えることを特徴とする方法。
【請求項１９】
前記英数字メッセージを生成する前記段階は：
非確定する前記段階に応答して、キー・コードの前記受信シーケンスのうちのサブシーケンス内の全てのキー・コードによって表される全ての文字を提示する段階であって、前記サブシーケンスは、候補単語の前記第１サブセットに対応し、全ての文字は、一度に一文字が前記発呼者に提示される、段階；および
全ての文字を提示する前記段階中に、一つまたはそれ以上の発呼者応答により、各キー・コードの確定済み文字を判定する段階；
を、さらに備えることを特徴とする請求項１８記載の方法。
【発明の詳細な説明】
（産業上の利用分野）
本発明は、一般に、英数字メッセージを入力するため電話キーパッドを利用する方法に関し、さらに詳しくは、１メッセージ文字毎に１キーストロークを利用する方法を関する。
【０００１】
（従来の技術）
英数字メッセージを表示し、これに応答するページャなどの高度なパーソナル通信デバイス（ＰＣＤ：personal communication device）の利用はますます普及している。このようなＰＣＤに送信される英数字メッセージは、機械または人間によって生成される。機械によって生成されたメッセージの例には、ニュース更新や株式市況更新がある。人間によって生成されるメッセージは、ネットワークに接続されたコンピュータを利用したり、あるいはメッセージを入力するオペレータが待機するメッセージ入力サービスを呼び出したり、あるいは標準的な電話機器を利用したり、あるいは別のＰＣＤを利用して、作成・送信できる。標準的な電話機器を利用して英数字メッセージを作成する能力は、電話機器は広く普及しており、ほとんどの人にとって馴染みがあるので、極めて望ましいが、電話キーパッドは英数字入力ではなく数字用に開発されたので、英数字メッセージを作成するために電話キーパッドを適応することは工夫を必要とする。英数字文字を作成するために標準的な電話キーパッドを利用する既知の方法が存在する。既知の方法の例では、一つのキー上の３つまたは４つの英数字文字のうちどの文字をメッセージに入力するのかをユーザが識別する。例えば、一方法では、４つの文字のうちどの文字が入力されるのかを示すために、一つのキーが短い時間の間に１回〜４回鍵打される。別の方法では、あるキーは、このキーが表す文字が一度に一つユーザに（視覚的あるいは聴覚的に）提示される間、押し込まれ、所望の文字が提示されると、開放される。これら２つの方法では、英数字メッセージをうまく作成できるが、これらの方法は多くの発呼者にとって不自然で、難しい。
【０００２】
従って、確実かつ自然な、標準電話キーパッドから英数字メッセージを作成する方法が必要とされる。
【０００３】
（好適な実施例の説明）
図１を参照して、メッセージング・システム１００は、例えば、電話１０２，ページ入力装置１０４およびソース・コンピュータ１０７などのいくつかの外部ソースから、ページまたはメッセージング要求を受け付ける。ここに示されるソース・コンピュータ１０７は一例としての性質であり、メッセージング・クライアント，ワールド・ワイド・ウェブ・クライアント，情報システム・ホストまたはワールド・ワイド・ウェブ・ホストとして機能して、他のクライアントに対して情報を授受できる。
【０００４】
ページまたはメッセージング要求は、ソース・コンピュータ１０７などの装置に対して高速ネットワーク接続を行うために、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）に接続する能力を好ましくは含む、公衆または私設電話網１０８用の電話網入力を介して通常受け付けられる。公衆または私設電話網１０８は、ソース（すなわち、音声メッセージまたはコンピュータ・メッセージ発生器）のうちの一つからメッセージング端末１１２における自動電話入力１１０またはネットワーク入力１１７に、ページ要求を結合する。公衆または私設電話網１０８ならびに専用入力は、インターネットおよびイントラネットの両方に対するＴＣＰ／ＩＰまたは同様な接続をサポートするモデムまたは高速ネットワーク・インタフェース、例えば、ＩＥＥＥ８０２．３などの一つまたはそれ以上のネットワーク接続装置１２３によって接続される。
【０００５】
メッセージング端末１１２は、ネットワーク接続装置１２３，自動電話入力１１０，ネットワーク入力１１７およびプロセッサ１０９によって構成され、このプロセッサ１０９は、辞書データベース(lexical database)１３５に結合された電話メッセージ・ハンドラ(telephone message handler)１３０からなる。メッセージング端末１１２は、好ましくは、Schaumburg, ILのMotorola, Inc.社製のWMG（商標）Administrator!モデル・メッセージング端末である。自動電話入力１１０は、従来のように、受信した電話呼出の自動通話接続を行い、電話通話からのデジタル化音声をプロセッサ１０９に結合する。電話メッセージ・ハンドラ１３０は、従来の大容量メモリ（ハードディスク）やランダム・アクセス・メモリ（ＲＡＭ）に格納された独自の電話メッセージ処理プログラム命令のセットの下でＣＰＵが動作される結果として、従来の中央処理装置（ＣＰＵ）および関連プロセッサ周辺装置の時分割部分によって構成される。独自のプログラム命令のセットは、以下で説明する独自の機能を実行するために、プロセッサ１０９の動作を制御する。なお、従来のタスク共有手法を利用することにより、プログラム命令の他の従来のセットは、電話メッセージ・ハンドラ１３０と実質的に同時に実行できるプロセッサ１０９の他の機能を提供できることが理解される。
【０００６】
ページ要求を受け付けた後、メッセージング端末１１２は、選択呼出アドレスとおそらく定型メッセージ(canned message)とからなる選択呼出メッセージを、選択呼出受信機（より一般的には、パーソナル・メッセージング装置という）に送信するために、無線周波数（ＲＦ）コントローラ１１４に中継する。メッセージは、Motorola, Inc.社がライセンスする周知のFLEX（商標）プロトコルなどのプロトコル用に、ＲＦコントローラ１１４によって構成され、このＲＦコントローラ１１４は、好ましくはMotorola社製のConductor!（商標）モデルＲＦコントローラであり、送信機１１６に結合され、この送信機１１６は、好ましくはMotorola, Inc.社製のSymphony（商標）モデル送信機である。従来のメッセージング・システムは、複数のメッセージング・フォーマットを介して情報を発呼者からページャ・ユーザに伝達できる。各メッセージ・フォーマットは、ページャに送信されるデータのモード（例えば、文字，数字，音声，グラフィックまたは「ビープのみ」）を表すことができる。図１は、メッセージング端末１１２から情報メッセージを受信できる、選択呼出受信機，加入者ユニット，パーソナル・メッセージング・ユニットともいう多数のパーソナル・メッセージング装置を示す。図示のパーソナル・メッセージング装置は、従来の設計であり、かつ双方向メッセージング機能を有する選択呼出受信機である英数字メッセージング装置１１８，数字表示ページャ１２０，音声メッセージ・ページャ１２２およびトーン専用ページャ１２２である。後者の場合、トーン専用ページャ１２２（すなわち、ユーザにメッセージが提示されない）は、発呼者がページャ・ユーザに、受付電話番号など所定の電話番号を電話して応答することを希望する旨を、ユーザに報知する（例えば、可聴ビープ音）。さらに、ＲＦコントローラ１１４は、従来のメッセージング受信機１１５と結合され、この従来のメッセージング受信機１１５は、英数字メッセージング装置１１８から入シグナリング情報（例えば、肯定応答(acknowledge back response)および返信チャネル・メッセージ(return channel message)）を受信し、これをメッセージング端末１１２に中継すべく動作する。英数字メッセージング装置は、好ましくはSchaumburg, ILのMotorola, Inc.社製のPagewriter（商標）双方向ページャであり、英数字ディスプレイを有する。メッセージング受信機１１５は、好ましくはMotorola, Inc.社製のAudience（商標）モデル受信機である。メッセージング端末１１２，ＲＦコントローラ１１４，送信機１１６およびメッセージング受信機１１５は、異なるモデルおよび製造でもよい。
【０００７】
図２を参照して、本発明の好適な実施例により、辞書データベースを生成する方法を示す。辞書データベース１３５は、候補単語の復元(recovery of candidate words)および候補単語に関連する確率(probabilities)の復元を行う。辞書データベース１３５は、メッセージング端末１１２のセットアップ動作中に生成され、従来の大容量メモリの一部に格納される。辞書データベース１３５は、ステップ２０５において、新たなメッセージにおいて用いられることが予想される種類の単語シーケンスの大きなサンプルを取得し；ステップ２１０において、大きなサンプルから判定された単語の確率に基づいて、全てのユニグラム（unigram：単一の単語）と、辞書データベース１３５に含まれる全てのユニグラムの確率とを判定・格納し；ステップ２１５において、本発明の好適な実施例により、バイグラム(bigrams)であるが、所定の最大長さまでのより大きな単語シーケンスでもよい、マルチグラム(multigrams)を、判定し、辞書データベース１３５に格納することによって生成される。格納されるマルチグラムは、所定の最小確率を超える、サンプルから判定された確率を有する。辞書データベース１３５は、キーパッド・コードのシーケンス（またはサブシーケンス）が電話メッセージ・ハンドラ１３０によって辞書データベース１３５に与えられるときに、候補単語のセット（またはセブセット）が電話メッセージ・ハンドラ１３０によって効率的に復元されるように、従来のように整理される。候補単語のセット（またはサブセット）は、キー・コードのシーケンス（またはサブシーケンス）によって表されるデータベース内の全てのユニグラムを含む。また、辞書データベース１３５は、電話メッセージ・ハンドラ１３０が順方向条件付き確率ルックアップの要求においてルックアップ単語(lookup word)および前置単語(preceding words)（所定の最大単語シーケンス長まで）を辞書データベース１３５に与えるときに、ルックアップ単語の順方向条件付き確率(forward conditional probability)が電話メッセージ・ハンドラ１３０によって効率的に復元されるように、従来のようにマルチグラム単語シーケンスおよび関連確率を格納することによって整理される。復元される確率値は、ルックアップ単語から開始し、かつマルチグラム一致が見つかるだけ多くの連続した前置単語を含む、マルチグラムの確率である。また辞書データベース１３５は、電話メッセージ・ハンドラ１３０がルックアップ単語および後置単語(succeeding words)（所定の最大単語シーケンス長まで）を辞書データベース１３５に与え、逆方向条件付き確率ルックアップを要求するときに、単語の逆方向条件付き確率が電話メッセージ・ハンドラ１３０によって効率的に復元されるように整理される。復元される確率値は、ルックアップ単語から開始し、かつマルチグラム一致が見つかるだけ多くの連続した後置単語を含むマルチグラムの確率である。
【０００８】
キー・コード・シーケンス（またはサブシーケンス）について一致が見つかると、候補単語の空でないセット(non-empty set)（またはサブセット）が復元される。辞書データベース１３５に与えられるキー・コード・シーケンスについて一致が見つからなければ、候補単語のナル・セット(null set)（またはサブセット）が復元され、電話メッセージ・ハンドラ１３０によってキーパッド・エラーが想定される。
【０００９】
順方向ルックアップにおいて与えられたルックアップ単語および前置単語について、あるいは逆方向ルックアップにおいて与えられたルックアップ単語および後置単語について、条件付き確率が格納されなければ、候補単語の無条件ユニグラム確率が辞書データベース１３５から電話メッセージ・ハンドラ１３０によって復元される。
【００１０】
図３および図４を参照して、本発明の好適な実施例により、電話を利用して英数字メッセージを作成するためにメッセージング端末１１２において用いられる方法のフローチャートを示す。ステップ３０５において、電話呼出が受信され、電話メッセージ・ハンドラ１３０は従来のように発呼者と対話して、発呼者がどの特定のパーソナル・メッセージング装置にメッセージを送りたいのかを判断する。電話メッセージ・ハンドラ１３０は、ステップ３１０において、どの種類のパーソナル・メッセージング装置なのかを判定する。ステップ３１５において、パーソナル・メッセージング装置が英数字メッセージング装置でないと判断されると、ステップ３３０において電話メッセージ・ハンドラ１３０はこの方法の処理を停止する。ステップ３１５において、パーソナル・メッセージング装置が英数字メッセージング装置であると判断されると、電話メッセージ・ハンドラ１３０は、ステップ３２０において、数字モード(digit mode)およびテキスト・モード(text mode)の２つのモードのうちの一つで電話キーパッドを利用して、メッセージ入力を行うように発呼者に指示する。メッセージ入力は、所定のキー（好ましくは、「０」キー）が最初に押されない限り、テキスト・モードで開始する。各英数字文字について、発呼者は、メッセージの各文字毎にメッセージの文字を含む電話キーパッド上のキーを利用し、メッセージの各文字毎にそのキーを一度押すことにより、メッセージを綴る。また、発呼者は、各単語の間のスペースとして、所定のキーであって、好ましくは、以下「＃」キーという、「＃」と記されたキーを利用するように指示される（すなわち、＃キーは英数字単語の区切り記号(delimiter)である）。数字モード後にテキスト・モードに入る場合にも、発呼者は「＃」キーを押す。数字モードに入るためには、発呼者は「０」と記されたキーを鍵打する。次に、各数字毎に、発呼者は所望の数字を押す。数字シーケンス（または数字「単語」）の最後は、＃キー・コードによって表される。発呼者は、＃キーを二度押すことによってメッセージを終了するように指示される。従って、所定のキー（「０」、「＃」）は、単語の境界を示す所定のキー・コードを生成し、テキスト・モードで入力される各単語は、最初の単語でない限り、＃キー・コードで開始・終了する。
【００１１】
従来のデュアル・トーン・マルチ周波数（ＤＴＭＦ：dual tone multi-frequency）キー・コードのシーケンスは、ステップ３２５において、発呼者がメッセージを入力するときに生成され、このシーケンスは、自動電話入力１１０によって電話メッセージ・ハンドラ１３０に結合され、ステップ４０５において、電話メッセージ・ハンドラ１３０によって受信・格納される。キー・コードのシーケンスは、電話キーパッド上のキーが実際に鍵打されたシーケンスを識別し、発呼者の所望の文字シーケンス（すなわち、英数字メッセージ）を表す。なお、入力エラーにより、任意のキー・コードのシーケンス内には、余分なキー・コードまたは抜けたキー・コードがある場合もある。一例として、"Can you go to IBM tomorrow morning at 10."という文章は、次のようにして入力される（キー上の数字は、数字付きキーのキーを識別するために用いられる）：
キー：226#968#46#86#426#86667769#6676464#28#010##
CAN YOU GO TO IBM TOMORROW MORNING AT 10.
ステップ４１０において、電話メッセージ・ハンドラ１３０は、キー・コードの受信シーケンスのうちのＮサブシーケンスを判定する。（従って、Ｎは整数。）Ｎサブシーケンスは、＃キーの所定のキー・コードによってキー・コードの受信シーケンス内で区切られたキー・コードのサブシーケンスである。上記の例では、Ｎサブシーケンスは、キー２２６，９６８，４６，８６，４２６，８６６６７７６９，６６７６４６４，２８のキー・コードである。ステップ４１５において、電話メッセージ・ハンドラ１３０は、候補単語の少なくとも一つのサブセットからなる単語格子(word trellis)を生成し、これは、この例では、候補単語の８つのサブセット（すなわち、Ｎ＝８）である。
【００１２】
図５を参照して、本発明の好適な実施例により、ステップ４１５の単語格子を生成するためにメッセージング端末１１２において電話メッセージ・ハンドラ１３０によって用いられる方法のフローチャートを示す。電話メッセージ・ハンドラ１３０は、ステップ５０５において、辞書データベース１３５に対する入力として、Ｎサブシーケンスのそれぞれを一度に一つ提示することによって、単語格子を生成する。Ｎサブシーケンスのそれぞれについて、電話メッセージ・ハンドラ１３０は、ステップ５１０において、ナル・サブセットが復元されたかどうかを判断する。ナル・サブセットが復元されない場合、電話メッセージ・ハンドラ１３０は、ステップ５１５において、辞書データベース１３５から候補単語のサブセットを復元する。ナル・サブセットの復元は、候補単語が提示されたキー・コード・サブシーケンスと一致しないことを示し、このシーケンスは、ステップ５２０において、誤りシーケンス(errored sequence)として識別される。電話メッセージ・ハンドラ１３０は、ステップ５２５において、誤りシーケンスを利用してキーパッド誤り訂正を行う。
【００１３】
図６を参照して、本発明の好適な実施例により、ステップ５２５にて、キーパッド誤り訂正を行うためにメッセージング端末１１２において電話メッセージ・ハンドラ１３０によって用いられる方法のフローチャートを示す。ステップ６０５において、誤りシーケンスは、キーパッド誤り訂正ルーチンによって受信される。ステップ６１０において、ループ手順が設定され、誤りシーケンスの各キー・コードが選択され、一度用いられる。ステップ６１５において、サブループ手順が設定され、選択されたキー・コードに対してそれぞれ異なるキー・コードを置換することによって、新規サブシーケンスが生成される。ステップ６２０において、候補単語が新規サブシーケンスによって復元されるかどうかを調べるために試験が行われる。新規サブシーケンスによって候補単語が復元される場合、ステップ６２５において、新規サブシーケンスは新規サブシーケンス・メモリに蓄積される。新規サブシーケンスによって候補単語が復元されない場合、ステップ６１０において、サブループの次の反復が開始される。誤りサブシーケンス内の全てのキー・コードについて、全ての異なるキー・コードが置換・試験されると、ステップ６３０において新たなループ手順が設定され、誤りシーケンスの各キー・コードが選択され、一度用いられる。ステップ６３５において、ステップ６３０にて選択されたキー・コードを削除することによって、新規サブシーケンスは生成される。ステップ６４０において、候補単語が新規サブシーケンスによって復元されるかどうかを調べるために試験が行われる。候補単語が新規シーケンスによって復元される場合、ステップ６４５において、新規サブシーケンスは新規サブシーケンス・メモリに蓄積される。候補単語が新規サブシーケンスによって復元されない場合、ステップ６３０において、ループの次の反復が開始される。誤りサブシーケンス内の各キー・コードが個別に削除されると、ステップ６５０において新たなループ手順が設定され、誤りシーケンスの２つの連続するキー・コード間の各挿入ポイントが選択され、一度用いられる。ステップ６５５において、サブループ手順が設定され、選択された挿入ポイントにて各キー・コードを挿入することによって新規サブシーケンスが生成される。ステップ６６０において、候補単語が新規サブシーケンスによって復元されるかどうかを調べるために試験が行われる。候補単語が新規サブシーケンスによって復元される場合、ステップ６６５において、新規サブシーケンスは新規サブシーケンス・メモリに蓄積される。候補単語が新規サブシーケンスによって復元されない場合、ステップ６６５において、サブループの次の反復が開始される。誤りサブシーケンス内の全ての挿入ポイントについて、全てのキー・コードが挿入され試験されると、ステップ６７０において、サブシーケンスが新規サブシーケンス・メモリ内に蓄積されたかどうかを調べるために試験が行われる。
【００１４】
新規サブシーケンスが新規サブシーケンス・メモリにないと判断されると、ステップ６７５において、新たなループ手順が設定され、誤りサブシーケンスを各選択された挿入ポイントにて２つのサブシーケンスに分割することによって、２つの新規サブシーケンスを生成するために、誤りシーケンスの各挿入ポイントが選択され、一度用いられる。ステップ６８０において、少なくとも一つの候補単語が２つの新規サブシーケンスのうちそれぞれによって復元されるかどうかを調べるために試験が行われる。候補単語が新規サブシーケンスによって復元される場合、ステップ６８５において、新規サブシーケンスは新規サブシーケンス・メモリに蓄積される。ステップ６８５において、候補単語が新規サブシーケンスの両方によって復元されない場合、ステップ６７５において、ループの新たな反復が開始される。ステップ６７５の全ての反復が完了すると、ステップ６８５においてサブシーケンスが蓄積されたかどうかを判定するために、ステップ６７６において試験が行われる。サブシーケンスが蓄積されていないと判断された場合、ステップ６７７において、文字編集(letter edit)手順（以下でさらに詳しく説明する）が行われる。ステップ６７６またはステップ６７０においてサブシーケンスが新規サブシーケンス・メモリに蓄積されたと判断された場合、新たなループ手順がステップ６９０において開始され、ここで新規サブシーケンス・メモリに蓄積された各新規サブシーケンス（またはステップ６８５が実行された場合には、２つの新規サブシーケンスのセット）が一度用いられる。各新規サブシーケンス（または２つの新規サブシーケンスのセット）について、新規サブシーケンス（または２つの新規サブシーケンスのセット）に一致する全ての候補単語のユニグラム確率のうち最高ユニグラム確率がステップ６９５において判定される。これは、新規サブシーケンス・スコア(new subsequence score)である。これは、各サブシーケンス（または２つのサブシーケンスのセット）について繰り返される。ステップ６９６において、最高のサブシーケンス・スコアを有する新規サブシーケンス（または２つの新規サブシーケンスのセット）は選択され、誤りサブシーケンスと置換される。なお、ステップ５２５のキーパッド誤り訂正の次に、サブシーケンスの数は、ステップ６７５におけるシーケンス分割のために増加する場合もあることが理解される。従って、サブシーケンスの数は、ステップ５２５以降は、Ｑとして識別され、ここでＱ≧Ｎである。
【００１５】
図４に戻って、ステップ４１５において単語格子が生成されると、ステップ４２０において、最大組合せ確率(maximum combined probability)を有する最もありそうな語句(most likely phrase)が判定される。最大組合せ確率は、上記のように辞書データベース１３５に格納されたユニグラム確率，順方向条件付き確率および逆方向条件付き確率から判定される。最もありそうな語句は、候補単語の各サブセットからの一つの候補単語の組合せからなる。
【００１６】
図７を参照して、本発明の好適な実施例により、ステップ４２０にて最もありそうな語句の判定を行うためにメッセージング端末１１２において電話メッセージ・ハンドラ１３０によって用いられる方法のフローチャートを示す。ステップ７０５において、二重反復ループが設定され、ここで第１反復においてｉ＝１，２，．．．Ｑについて、また第１反復のサブ反復である第２反復においてｊ＝１，２，．．．Ｍｉについて、部分的順方向確率(partial forward probabilities)αｉ，ｊが再帰的に算出される。Ｍｉは、候補単語のｉ番目のサブセット内の候補単語の数である整数である。ｉおよびｊの各値について、部分的順方向確率αｉ，ｊは次式のようにして算出される：
［数１］
αｉ，ｊ＝ｍａｘ(αｉ−１，ｋＰ（ｗｉ，ｊ｜Ｗ０ｉ−１，Ｗ０ｉ−２，．．．Ｗ０１））、
ただし１＜＝ｋ＜Ｍｉ−１
この式では、式ｗｉ，ｊ｜Ｗ０ｉ−１，Ｗ０ｉ−２，．．．Ｗ０１は、候補単語ｗｉ，ｊの順方向条件付き確率を表し、αｉ，ｊを算出するために用いられるαｉ−１，ｋに関連する蓋然単語(probable word)Ｗ０ｉ−１，Ｗ０ｉ−２，．．．Ｗ０１のセットが与えられると、部分的確率αｉ，ｊが計算される。候補単語ｗｉ，ｊの順方向条件付き確率は、図２を参照して説明したように、辞書データベース１３５に要求を行い、候補単語ｗｉ，ｊと、αｉ−１，ｋに関連する蓋然単語のセットとをルックアップ単語および前置単語として与えることによって、電話メッセージ・ハンドラ１３０によって取得される。
【００１７】
（前置部分的順方向積と、関連する順方向条件付き確率との）Ｍｉ−１積の最大値を選択することにより、部分的順方向確率αｉ，ｊが判定されると、αｉ，ｊを生成するαｉ−１，ｊに関連する蓋然単語のセットに候補単語を追加し、蓋然単語の新たなセットをαｉ，ｊと関連付けることにより、蓋然単語のセットは部分的順方向確率αｉ，ｊと関連付けられる。
【００１８】
ステップ７１０および７１５において、全ての部分的順方向確率が算出されると、ステップ７２０において、新たな二重反復ループが設定され、ここで第１反復におけるｉ＝Ｑ，Ｑ−１，．．．１について、また第１反復のサブ反復である第２反復におけるｊ＝１，２，．．．Ｍｉについて、部分的組合せ確率(partialcombination probabilities)βｉ，ｊが再帰的に算出される。ｉおよびｊの各値について、部分的組合せ確率βｉ，ｊは次式のようにして算出される：
［数２］
βｉ，ｊ＝ｍａｘ（αｉ，ｊβｉ＋１，ｋＰ（ｗｉ，ｊ｜Ｗ０ｉ＋１，Ｗ０ｉ＋２，．．．Ｗ０Ｑ））、
ただし１≦ｋ≦Ｍｉ＋１
この式では、式ｗｉ，ｊ｜Ｗ０ｉ＋１，Ｗ０ｉ＋２，．．．Ｗ０Ｑは、候補単語ｗｉ，ｊの逆方向条件付き確率を表し、βｉ，ｊを算出するために用いられるβｉ＋１，ｋに関連する蓋然単語Ｗ０ｉ＋１，Ｗ０ｉ＋２，．．．Ｗ０Ｑのセットが与えられると、部分的確率βｉ，ｊが計算される。候補単語ｗｉ，ｊの逆方向条件付き確率は、図２を参照して説明したように、辞書データベース１３５に要求を行い、候補単語ｗｉ，ｊと、βｉ＋１，ｋに関連する蓋然単語のセットとをルックアップ単語および後置単語として与えることによって、電話メッセージ・ハンドラ１３０によって取得される。
【００１９】
（関連した部分的順方向積確率と、前置部分的組合せ積と、関連した逆方向条件付き確率との）Ｍｉ＋１積の最大値を選択することにより、部分的組合せ確率βｉ，ｊが判定されると、βｉ，ｊを生成するβｉ＋１，ｊに関連する蓋然単語のセットに候補単語を追加し、蓋然単語の新たなセットをβｉ，ｊと関連付けることにより、蓋然単語の新たなセットは部分的組合せ確率βｉ，ｊと関連付けられる。
【００２０】
ステップ７２５および７３０において、全ての部分的組合せ確率が算出されると、ステップ７３５において、最大組合せ確率ｍａｘ（β１，ｊ），ただし１＜＝ｊ＜＝Ｍ１、に関連する蓋然単語のセットを見つけることによって、最もありそうな語句が選択される。
【００２１】
なお、上記の再帰的計算は、当業者に明白なように、実質的に同様であり、かつ近似的に同じものを生成する他の方法によっても行うことができることが理解される。例えば、ステップ７０５〜７３０に示される式に対して明白な変更を行うことで、ステップ７０５〜７１５において部分的順方向確率の代わりに部分的逆方向確率が算出できる。
【００２２】
図４に戻って、ステップ４２５において、最もありそうなメッセージが生成され、発呼者に提示される。最もありそうなメッセージは、ステップ４０５中に数字モードにて発呼者により入力された数字と、最もありそうな語句を再合成することによって、好ましくは生成される。最もありそうなメッセージは、単語および数字の従来のコンピュータ合成(computer synthesis)を利用して、発呼者に提示される。最もありそうなメッセージが発呼者に提示されると、最もありそうなメッセージからの英数字メッセージの確定(confirming)がステップ４３０において行われる。ステップ４３０において発呼者が肯定指示で提示に応答すると、確定が行われ、その結果、ステップ４３５において最もありそうなメッセージを利用して英数字メッセージの作成が完了し、このメッセージは所望の英数字メッセージング装置に送信される。ステップ４３０において発呼者が肯定指示で提示に応答すると、非確定となり、その結果、ステップ４４０において最もありそうなメッセージの編集となる。
【００２３】
図８を参照して、本発明の好適な実施例により、ステップ４４０の編集を行うためにメッセージング端末１１２において電話メッセージ・ハンドラ１３０によって用いられる方法のフローチャートを示す。発呼者からの応答により、ステップ８０５において、不適切な候補単語が発呼者によって特定される。ステップ８１０において、最大Ｒ個の次の最もありそうなメッセージが一度に一つ発呼者に提示される。Ｒ個の次の最もありそうなメッセージは、１＜＝ｋ＜＝Ｍ１について部分的組合せ確率β１，ｋに関連する蓋然単語のセットとして選択され、ここでβ１，ｋは、ステップ７２５および７３０の完了時に上記のように判定されたβ１，ｋであり、降順の値で並べ替えられ、これに対して数字および文字は（ステップ４２５におけるように）再合成されている。本発明の好適な実施例により、Ｒは１であるが、それよりも大きくてもよい。ステップ８１５において、発呼者が次の最もありそうな語句のうちの一つを選択すると、ステップ８２０において、これは所望の英数字メッセージング装置に送信される。ステップ８１５において、発呼者が英数字メッセージとして次の最もありそうなメッセージを特定しない場合、最もありそうなメッセージは発呼者に再度提示され、発呼者はステップ８２５において編集のために候補単語のうちの一つを選択できる。発呼者が候補単語のうちの一つを選択すると、電話メッセージ・ハンドラ１３０は、選択された候補単語が判定されたサブシーケンスに対応する他の候補単語を辞書データベース１３５から復元し、ステップ８３０においてユニグラム確率の順番でこれらの単語を発呼者に提示する。発呼者がステップ８３５においてそのうち一つを選択すると、ステップ８４０において、選択された単語は最もありそうな語句内の候補単語の代わりに用いられる。ステップ８３５において、発呼者が適切な単語として候補単語のどれも選択しない場合、電話メッセージ・ハンドラ１３０は、ステップ８４５において、サブシーケンス内の各キー・コードによって表される各文字を一度に一つ提示し、発呼者は適切な文字を確定し、それにより編集された単語を生成し、この単語はステップ８５０において最もありそうな語句において用いられる。２つ以上の単語が誤りである場合、ステップ８２５および８５０は、全ての候補単語を訂正するために必要なだけ繰り返される。次に、数字および文字は、ステップ８２０，８４０，８５０のうちの一つにおいて最終的に生成された最もありそうな語句と再合成され、最もありそうなメッセージを生成する。また、ステップ８４５，８５０は、図６を参照して説明したステップ６７７を実行する方法として、ステップ８０５〜８５０を含む上記の方法から独立して、用いられる。
【００２４】
本発明の好適な実施例により、本明細書において説明したように電話キーパッドを利用して英数字メッセージを作成する対話式の方法は、米国におけるほとんどの電話にある標準的な電話キーパッドを利用するが、本発明は他の実施例に従って容易に利用できることが理解される。例えば、キーパッドは、携帯電話において多用される従来の方式で、パラレル信号によってプロセッサに直接接続できる。このような実施例では、キーパッド上のキーが鍵打されるシーケンスに対応するキー・コードのシーケンスが生成されるが、このキー・コードは、ＤＴＭＦコードではなく、パラレル・バイナリ・コードである。また、キーパッドは標準的な米国電話キーパッドである必要はなく、他の言語の余分なキーまたは文字を有するキーパッドでもよい。各キーが２つ以上の英数字文字を表すキーをキーパッドが含む場合でも、本発明の効果は実現される。このようなキーパッドは、本明細書では、簡単に、電話スタイル・キーパッドとして識別される、別の言語を用いる場合、辞書データベースはそれに応じて変更される。
【００２５】
図３および図４を参照して説明したように、所望の英数字メッセージについてキー・コード・シーケンス全体を格納する動作は、順方向条件付き確率のみを利用する音声認識システムなどの従来のリアルタイム・デコーディング装置よりも優れた結果をもたらす独自の方法で、順方向および逆方向条件付き確率の両方を利用して最もありそうな語句を判定できることが理解される。さらに、発呼者が作成中のメッセージ内に意図せずにミス入力や、キーを省いたり、あるいはキーを追加した場合に、確からしい訂正を効率的かつ自動的に行うキーパッド誤り訂正手法の独自のセットについて説明したことが理解される。さらに、発呼者が作成中の英数字メッセージではない最もありそうなメッセージを自動メッセージ判定が選択した場合に、メッセージの効率的かつ自然で階層的な編集を行う、メッセージ訂正手法の独自のセットについて説明したことが理解される。
図９は、本発明の別の実施例により、候補単語のサブセットから英数字メッセージを生成する方法のフローチャートを示す。単語格子は図４のステップ４１５で生成されるが、図９はその生成方法の実施例を示すものである。
図１０は、本発明の別の実施例により、オペレータによって入力されたエントリに応じて最もありそうなメッセージの編集を実行する方法のフローチャートを示す。オペレータは、メッセージング端末１１２で、英数字キーボードとディスプレイ、およびスピーカとマイクロフォンにより、発呼者をモニタおよび援助し、連絡をとる人である。
図１１は、本発明の別の実施例により、最もありそうなメッセージの編集を実行する方法のフローチャートを示す。
【図面の簡単な説明】
【図１】  本発明の好適な実施例による、メッセージング・システムのブロック図を示す。
【図２】  本発明の好適な実施例により、辞書データベースを生成するためにメッセージング・システムのメッセージング端末において用いられる方法のフローチャートを示す。
【図３】  本発明の好適な実施例により、電話を利用して英数字メッセージを作成するためにメッセージング端末において用いられる方法のフローチャートを示す。
【図４】  本発明の好適な実施例により、電話を利用して英数字メッセージを作成するためにメッセージング端末において用いられる方法のフローチャートを示す。
【図５】  本発明の好適な実施例により、単語格子(word trellis)を生成するためにメッセージング端末において用いられる方法のフローチャートを示す。
【図６】  本発明の好適な実施例により、キーパッド誤り訂正を行うためにメッセージ端末において用いられる方法のフローチャートを示す。
【図７】  本発明の好適な実施例により、最もありそうな語句の判定を行うためにメッセージング端末において用いられる方法のフローチャートを示す。
【図８】  本発明の好適な実施例により、編集を行うためにメッセージング端末において用いられる方法のフローチャートを示す。
【図９】  本発明の別の実施例により、候補単語のサブセットから英数字メッセージを生成する方法のフローチャートを示す。
【図１０】  本発明の別の実施例により、オペレータにより作成されたエントリに応じて最もありそうなメッセージの編集を実行する方法のフローチャートを示す。
【図１１】  本発明の別の実施例により、最もありそうなメッセージの編集を実行する方法のフローチャートを示す。
【図１】
0004171780.tif 000002
【図２】
0004171780.tif 000003
【図３】
0004171780.tif 000004
【図４】
0004171780.tif 000005
【図５】
0004171780.tif 000006
【図６】
0004171780.tif 000007
【図７】
0004171780.tif 000008
【図８】
0004171780.tif 000009
【図９】
0004171780.tif 000010
【図１０】
0004171780.tif 000011
【図１１】
0004171780.tif 000012