(57)【要約】データベース内のデータファイルに注釈付けするためにデータ構造が提供される。注釈データは、所望の情報を求めるユーザの入力質問に応答して、データベース内でのデータファイルの迅速且つ効率的な検索を可能にする音素／単語ラティスから構成される。音素／単語ラティスは、複数の時間順のノード及びこれらのノード間にまたがる複数のリンクから構成される。各リンクはそれと関連付けられる音素又は単語を有する。ノードは、更なるデータをラティスへと加えるのが便利なように、時間順のブロックのシーケンス中に配置される。
2004510256.tif 000002
【特許請求の範囲】
【請求項１】
ラティスを定義するデータであって、
前記ラティス内の複数の整列されたノードを定義するためのデータと、
前記ラティス内にあり且つ各々が第１のノードから第２のノードまで伸びる複数のリンクを定義するためのデータと、
任意のブロック中のノードからのリンクが整列されたブロックのシーケンスにおいて所定数のブロックだけ後にあるブロック中のノードを越えて伸びないように前記シーケンス中のノードを配置するためのデータとを備えることを特徴とするデータ。
【請求項２】
前記データは複数の時間順のノードを定義し、前記データは時間順のブロックのシーケンス中のノードを配置する請求項１記載のデータ。
【請求項３】
前記ノード及び／又は前記リンクと関連付けられた情報入口を定義するデータを更に備えることを特徴とする請求項１又は２記載のデータ。
【請求項４】
データベース中で使用するための少なくとも音素ラティス及び単語ラティスのいずれかを定義するデータであって、
前記ラティス内の複数の時間順のノードを定義するためのデータと、
前記ラティス内にあり且つ各々が第１のノードから第２のノードまで伸びる複数のリンクを定義するためのデータと、
音素又は単語を少なくとも１つのノード又はリンクと関連付けるためのデータと、
任意のブロック中のノードからのリンクが時間順のブロックのシーケンスにおいて所定数のブロックだけ後にあるブロック中のノードを越えて伸びないように前記シーケンス中のノードを配置するためのデータとを備えることを特徴とするデータ。
【請求項５】
任意のブロック中のノードからの前記リンクは後続のブロック中のノードを越えて伸びないことを特徴とする請求項１から４のいずれか１項に記載のデータ。
【請求項６】
先行するブロックで始まるリンクが終点とする各ブロック中の最終のノードを識別する前記ブロックに対する第１のタイミング又はノード点（β）を定義するためのデータを更に備えることを特徴とする請求項５記載のデータ。
【請求項７】
後続するブロックまで伸びるリンクが始点とする各ブロック中の先頭のノードを識別する前記ブロックに対する第２のタイミング又はノード点（α）を定義するためのデータを更に備えることを特徴とする請求項６記載のデータ。
【請求項８】
各ノード及びそのリンクに対する前記データはデータのシーケンスとして配置され、各ノードに対する前記データのシーケンスは前記ノードの時間順に対応する順序でデータストリーム中に共に配置されることを特徴とする請求項７記載のデータ。
【請求項９】
複数のリンクを有するノードに対して、これらのリンクの各々に対するデータが前記対応するリンクの程度に応じて所定の方法で配置されることを特徴とする請求項１から８のいずれか１項に記載のデータ。
【請求項１０】
複数のリンクを有する前記ノードに対して、最長のリンクに対するデータが前記データのシーケンス内の複数のリンクのうちのその他のリンクと比べて常に同じ相対位置に配置されることを特徴とする請求項９記載のデータ。
【請求項１１】
前記最長のリンクに対するデータは、各前記データのシーケンス中の前記複数のリンクの中で常に先頭又は常に最後に配置されることを特徴とする請求項１０記載のデータ。
【請求項１２】
データベース中で使用するために、前記データベース内の各ブロックの位置を定義するデータを更に備えることを特徴とする請求項１から１１のいずれか１項に記載のデータ。
【請求項１３】
各前記ノードに対してタイムスタンプ情報を定義するデータを更に備えることを特徴とする請求項１から１２のいずれか１項に記載のデータ。
【請求項１４】
各前記ノードに対してタイムスタンプ情報を定義するデータを更に備え、音素ラティス及び単語ラティスを定義する前記データは時系列信号を定義する更なるデータと関連付けられ、前記タイムスタンプ情報は前記時系列信号と時間的に同期することを特徴とする請求項４記載のデータ。
【請求項１５】
前記更なるデータは少なくともオーディオ信号及びビデオ信号のいずれかを定義することを特徴とする請求項１４記載のデータ。
【請求項１６】
前記更なるデータは少なくとも音声データを定義し、前記音素ラティス及び単語ラティスを定義する前記データは前記更なるデータから得られることを特徴とする請求項１５記載のデータ。
【請求項１７】
前記音声データはオーディオデータを備え、前記音素ラティス及び単語ラティスを定義する前記データは前記オーディオ信号を自動音声認識システムに通すことによって得られることを特徴とする請求項１６記載のデータ。
【請求項１８】
前記音声データは複数の話者の陳述を定義し、前記データは各話者の陳述に対して個別の音素ラティス及び単語ラティスを定義することを特徴とする請求項１６又は１７記載のデータ。
【請求項１９】
ユーザによる入力質問に応答して、請求項４から１８のいずれか１項に記載のデータを備えることを特徴とするデータベースを検索する装置であって、
前記ユーザの入力質問に対応する音素データを生成する手段と、
前記入力質問に対して生成される前記音素データを使用して前記音素ラティス及び単語ラティスを検索する手段と、
前記検索手段からの出力により検索結果を出力する手段とを備えることを特徴とする装置。
【請求項２０】
前記ユーザの入力質問に対応する単語データを生成する手段と前記入力質問に対して生成される前記単語データを使用して前記音素ラティス及び単語ラティスを検索する手段とを更に備えることを特徴とする請求項１９記載の装置。
【請求項２１】
ユーザによる入力質問に応答して、請求項４から１８のいずれか１項に記載のデータを備えるデータベースを検索する方法であって、
前記ユーザの入力質問に対応する音素データを生成する工程と、
前記入力質問に対して生成される前記音素データを使用して音素ラティス及び単語ラティスを検索する工程と、
前記検索工程の結果に応じて検索結果を出力する工程と
を備えることを特徴とする方法。
【請求項２２】
前記ユーザの入力質問に対応する単語データを生成し、前記入力質問に対して生成される前記単語データを使用して前記音素ラティス及び単語ラティスを検索する工程を更に備えることを特徴とする請求項２１記載の方法。
【請求項２３】
データファイルへの注釈付けに使用する注釈データを生成する装置であって、
少なくとも音素データ及び単語データのいずれかを受信する受信手段と、
前記受信された少なくとも音素データ及び単語データのいずれかに対応する少なくとも音素ラティス及び単語ラティスのいずれかを定義する注釈データを生成する第１の生成手段とを備え、
前記第１の生成手段は、
前記ラティス内で複数の時間順のノードを定義するノードデータを生成する第２の生成手段と、
前記ラティス内にあり且つ各々が第１のノードから第２のノードまで伸びる複数のリンクを定義するリンクデータを生成する第３の生成手段と、
少なくとも前記音素データ及び単語データのいずれかから各ノード又はリンクを音素又は単語と関連付ける関連付けデータを生成する第４の生成手段と、
任意のブロック中のノードからのリンクは時間順のブロックのシーケンスにおいて所定数のブロックだけ後にあるブロック中のノードを越えて伸びないというブロック基準を満たす時間順のブロックのシーケンス中のノードを配置するためのブロックデータを生成する第５の生成手段とを備えることを特徴とする装置。
【請求項２４】
前記ブロック基準は任意のブロック中のノードからのリンクが後続のブロック中のノードを越えて伸びないとの基準であることを特徴とする請求項２３記載の装置。
【請求項２５】
前記第１の生成手段は各ノードに対する前記ノードデータ及び各リンクに対する前記リンクデータを処理することによって少なくとも前記音素ラティス及び単語ラティスのいずれかを形成する処理手段を備え、前記処理手段は、
ｉ）前記ラティスの現在のブロック中のノードの個数が所定数に到達するまで前記現在のブロックに対して１つ以上のノード及び関連するリンクを加える手段と、
ｉｉ）前記現在のブロックを前記ブロック基準に従って分割できると判定する第１の判定手段と、
ｉｉｉ）前記現在のブロックを少なくとも２つのノードのブロックへと分割する分割手段とを備えることを特徴とする請求項２３又は２４記載の装置。
【請求項２６】
少なくとも各音素及び単語のいずれかに対する少なくとも前記音素データ及び単語データのいずれかに対応して前記ノードデータ及びリンクデータを生成するように動作可能であることを特徴とする請求項２５記載の装置。
【請求項２７】
少なくとも前記音素ラティス及び単語ラティスのいずれかを形成する前に全てのノードデータ及び全てのリンクデータを生成するように動作可能であることを特徴とする請求項２６記載の装置。
【請求項２８】
少なくとも各音素及び単語のいずれかに対して少なくとも前記音素ラティス及び単語ラティスのいずれかが生成されるとき、少なくとも各音素及び単語のいずれかに対する前記ノードデータ及びリンクデータを少なくとも前記音素ラティス及び単語ラティスのいずれかへと徐々に加えるように動作可能であることを特徴とする請求項２６記載の装置。
【請求項２９】
処理中の現在の音素又は単語に対する開始時間及び終了時間に対してノードが既に存在するか否かを判定し、
前記ノードが既に存在しない場合、少なくとも前記開始時間及び終了時間のいずれかに対応するノードを前記ラティスへと加え、
処理中の前記現在の音素又は単語に対する前記開始時間及び終了時間に対応するノード間のリンクを加えることによって前記ノードデータ及びリンクデータを徐々に加えるように動作可能であることを特徴とする請求項２８記載の装置。
【請求項３０】
先行するブロックで始まるリンクが終点とするブロック中の最終のノードを識別する各ブロックに対して第１のタイミング又はノード点（β）と、後続するブロックまで伸びるリンクが始点とするブロック中の先頭のノードを識別する各ブロックに対して第２のタイミング又はノード点（α）とを判定する第２の判定手段を更に備え、
前記第１の判定手段は、前記第１のタイミング又はノード点（β）が前記第２のタイミング又はノード点（α）の前にあると判定することによって、前記ブロック基準に従って現在のノードのブロックが分割可能であると判定するように動作可能であり、前記分割手段は、前記現在のノードのブロックが分割可能であると判定する前記第１の判定手段に応答して前記現在のブロックを分割するように動作可能であることを特徴とする請求項２５から２９のいずれか１項に記載の装置。
【請求項３１】
前記第２の判定手段は、更なるノードを前記ラティスへと加える際に、各ブロックに対する前記第１のタイミング又はノード点（β）及び第２のタイミング又はノード点（α）を更新するように動作可能であることを特徴とする請求項３０記載の装置。
【請求項３２】
前記分割手段は、前記第１のタイミング又はノード点（β）と前記第２のタイミング又はノード点（α）との間で前記現在のブロックを分割するように動作可能であることを特徴とする請求項３０又は３１記載の装置。
【請求項３３】
前記分割手段は、前記先行するブロックの前記第１のタイミング又はノード点（β）又はその付近で開始し、前記現在のブロックの前記第１のタイミング又はノード点（β）又はその付近で終了する新規のブロックを形成することによって前記現在のブロックを分割するように動作可能であることを特徴とする請求項３０又は３１記載の装置。
【請求項３４】
前記先行するブロックの前記第１のタイミング又はノード点（β）が前記先行するブロックの第２のタイミング又はノード点（α）よりも遅い場合、前記分割手段は前記先行するブロックの前記第１のタイミング又はノード点（β）又はその付近で開始し、前記現在のブロックの前記第１のタイミング又はノード点（β）又はその付近で終了する新規のブロックを形成することによって前記現在のブロックを分割するように動作可能であり、前記先行するブロックの前記第１のタイミング又はノード点（β）が前記先行するブロックの第２のタイミング又はノード点（α）よりも早い場合、前記分割手段は前記第１のタイミング又はノード点（β）と前記第２のタイミング又はノード点（α）との間で前記現在のブロックを分割するように動作可能であることを特徴とする請求項３０又は３１記載の装置。
【請求項３５】
入力オーディオ又はテキストデータから少なくとも前記音素データ及び単語データのいずれかを生成する第６の生成手段を更に備えることを特徴とする請求項２３から３４のいずれか１項に記載の装置。
【請求項３６】
前記データファイルはオーディオデータを備え、前記第６の生成手段は前記データファイル中のオーディオデータに対して音素データを生成するための自動音声認識システムを備えることを特徴とする請求項３５記載の装置。
【請求項３７】
前記第６の生成手段は、前記自動音声認識システムにより生成される前記音素データ内の予想単語を識別することによって単語データを生成するための単語復号器を更に備えることを特徴とする請求項３６記載の装置。
【請求項３８】
前記データファイルはテキストデータを備え、前記第６の生成手段は前記データファイル中のテキストデータから音素データを生成するためのテキスト／音素変換装置を備えることを特徴とする請求項３５記載の装置。
【請求項３９】
前記第６の生成手段は、
ａ）入力音声注釈信号を受信・処理する手段、
ｂ）テキスト注釈を受信・処理する手段、並びに
ｃ）テキスト文書を表す画像データを受信する手段及び画像データをテキストデータへと変換する文字認識装置より成る群のうちの１つを備えることを特徴とする請求項３２記載の装置。
【請求項４０】
前記第１の生成手段は、各前記ノードに対してタイムスタンプ情報を定義するデータを生成するように動作可能であることを特徴とする請求項２３から３９のいずれか１項に記載の装置。
【請求項４１】
前記第１の生成手段は、データベース内の各ブロックの位置を定義するデータを生成するように動作可能であることを特徴とする請求項２３から４０のいずれか１項に記載の装置。
【請求項４２】
前記データファイルは時系列信号を含み、前記第１の生成手段は、前記時系列信号と時間的に同期するタイムスタンプデータを生成するように動作可能であることを特徴とする請求項４０又は４１記載の装置。
【請求項４３】
前記時系列信号は少なくともオーディオ信号及びビデオ信号のいずれかであることを特徴とする請求項４２記載の装置。
【請求項４４】
請求項４から１８のいずれか１項に記載の少なくとも音素ラティス及び単語ラティスのいずれかを定義するデータに１つ以上の音素又は単語に対応するデータを加える装置であって、
ｉ）追加する音素又は単語の開始時間及び終了時間に対して前記ラティスにノードが既に存在するか否かを判定し、既に存在しない場合には少なくとも前記開始時間及び終了時間のいずれかに対応するノードを前記ラティスに挿入することによってノードを前記ラティスへと挿入するノード処理手段と、
ｉｉ）前記追加する音素又は単語に対する前記開始時間及び終了時間に対応する前記ノード間にリンクを加えるリンク処理手段と、
ｉｉｉ）更なるノードの挿入により変更する必要がある関連するリンクデータを有する可能性があるのがどの既存のノードであるかを選択する選択手段と、
ｉｖ）前記選択された既存のノードのリンクデータを分析する分析手段と、
ｖ）必要に応じて前記分析されたリンクデータを変更する手段とを備え、
前記選択手段は、各更なるノードに対して、前記更なるノードを含むブロック中の前記更なるノードに先行するノード及び所定数のブロック以下の複数のブロックだけ前記更なるノードを含む前記ブロックに先行する各ブロック中の全てのノードを選択するように動作可能であることを特徴とする装置。
【請求項４５】
前記選択手段は、所定のブロックへと挿入する更なるノードに対して、ｉ）挿入中の前記ノードに先行する前記所定のブロック中のノード及びｉｉ）前記先行するブロック中の全てのノードのみを選択するように動作可能であることを特徴とする請求項４４記載の装置。
【請求項４６】
前記データは請求項７に記載される通りであり、前記選択手段は、タイミング又はノード点により定義される挿入位置において所定のブロックへと挿入される更なるノードに対して、
ａ）前記挿入位置が前記所定のブロックの前記第１のタイミング又はノード点（β）の後にある場合には、前記挿入位置に先行する前記所定のブロック中の前記既存のノード、
ｂ）前記挿入位置が前記所定のブロックの前記第１のタイミング又はノード点（β）の前にある場合には、ｉ）前記挿入位置に先行する前記所定のブロック中の前記既存のノード及びｉｉ）前記先行するブロックの前記第２のタイミング又はノード点（α）又はその後にある前記先行するブロック中の前記既存のノードを選択するように動作可能であることを特徴とする請求項４４記載の装置。
【請求項４７】
前記データは請求項９又はそれに従属したいずれか１項に記載される通りであり、前記分析手段は各選択されたノードから伸びる最長のリンクのみを分析するように構成されることを特徴とする請求項４４から４６のいずれか１項に記載の装置。
【請求項４８】
加えられる１つ以上の音素又は単語に対応するデータを前記先に受信された音素データ及び単語データへと加えるための請求項４４から４７のいずれか１項に記載の装置を更に備えることを特徴とする請求項２３から４３のいずれか１項に記載の装置。
【請求項４９】
データファイルへの注釈付けに使用する注釈データを生成する方法であって、
ｉ）少なくとも音素データ及び単語データのいずれかを受信する工程と、
ｉｉ）受信された少なくとも音素データ及び単語データのいずれかに対応する少なくとも音素ラティス及び単語ラティスのいずれかを定義する注釈データを生成する工程とを備え、
前記ラティスを定義する注釈データの生成工程は、
前記ラティス内の複数の時間順のノードを定義するノードデータを生成する工程と、
前記ラティス内にあり且つ各々が第１のノードから第２のノードまで伸びる複数のリンクを定義するリンクデータを生成する工程と、
各リンク又はノードを少なくとも前記音素データ及び単語データのいずれかからの音素又は単語と関連付ける関連付けデータを生成する工程と、
任意のブロック中のノードからのリンクが時間順のブロックのシーケンスにおいて所定数のブロックだけ後にあるブロック中のノードを越えて伸びないというブロック基準を満たす前記シーケンス中のノードを配置するためのブロックデータを生成する工程とを備えることを特徴とする方法。
【請求項５０】
前記ブロック基準は、任意のブロック中のノードからのリンクが後続するブロック中のノードを越えて伸びないという基準であることを特徴とする請求項４９記載の方法。
【請求項５１】
前記ラティスを定義する注釈データの生成工程は、各ノードに対する前記ノードデータ及び各リンクに対する前記リンクデータを処理することによって少なくとも前記音素ラティス及び単語ラティスのいずれかを形成するために、
ｉ）現在のブロック中のノードの数が所定数に到達するまで１つ以上のノード及び関連リンクを加える工程と、
ｉｉ）前記ブロック基準に従って前記現在のブロックを分割できると判定する工程と、
ｉｉｉ）前記現在のブロックを少なくとも２つのノードのブロックへと分割する工程と
を備えることを特徴とする請求項４９又は５０記載の方法。
【請求項５２】
前記ノードデータ及びリンクデータは、少なくとも各音素及び単語のいずれかに対する少なくとも前記音素データ及び単語データのいずれかに対応して生成されることを特徴とする請求項５１記載の方法。
【請求項５３】
全てのノードデータ及び全てのリンクデータは少なくとも前記音素ラティス及び単語ラティスのいずれかを形成する前に生成されることを特徴とする請求項５２記載の方法。
【請求項５４】
少なくとも各前記音素及び単語のいずれかに対して少なくとも前記音素ラティス及び単語ラティスのいずれかが生成されるとき、少なくとも各音素及び単語のいずれかに対する前記ノードデータ及びリンクデータは少なくとも前記音素ラティス及び単語ラティスのいずれかへと徐々に加えられることを特徴とする請求項５２記載の方法。
【請求項５５】
前記ノードデータ及びリンクデータは、
処理中の前記現在の音素又は単語に対する開始時間及び終了時間に対してノードが既に存在するか否かを判定し、
前記ノードが既に存在しない場合、少なくとも前記開始時間及び終了時間のいずれかに対応するノードを前記ラティスへと追加し、
処理中の少なくとも前記現在の音素及び単語のいずれかに対する前記開始時間及び終了時間に対応する前記ノード間にリンクを加える
ことにより徐々に加えられることを特徴とする請求項５４記載の方法。
【請求項５６】
先行するブロックで始まるリンクが終点とするブロック中の最終のノードを識別する各ブロックに対して第１のタイミング又はノード点（β）と、後続するブロックまで伸びるリンクが始点とする前記ブロック中の先頭のノードを識別する各ブロックに対して第２のタイミング又はノード点（α）とを判定する工程を更に備え、
前記ブロック基準に従って現在のノードのブロックを分割できると判定する判定工程は、前記第１のタイミング又はノード点（β）が前記第２のタイミング又はノード点（α）の前にあると判定する工程を備え、前記現在のノードのブロックが分割可能であると判定されるのに応じて前記現在のブロックは少なくとも２つのブロックへと分割されることを特徴とする請求項５１から５５のいずれか１項に記載の方法。
【請求項５７】
更なるノードを前記ラティスに加える際に、各ブロックに対する前記第１のタイミング又はノード点（β）及び第２のタイミング又はノード点（α）を更新する工程を更に備えることを特徴とする請求項５６記載の方法。
【請求項５８】
前記現在のブロックの分割工程は、前記第１のタイミング又はノード点（β）と前記第２のタイミング又はノード点（α）との間で前記現在のブロックを分割する工程を備えることを特徴とする請求項５６又は５７記載の方法。
【請求項５９】
前記現在のブロックの分割工程は、前記先行するブロックの前記第１のタイミング又はノード点（β）又はその付近で開始し、前記現在のブロックの第１のタイミング又はノード点（β）又はその付近で終了する新規のブロックを形成する工程を備えることを特徴とする請求項５６又は５７記載の方法。
【請求項６０】
前記現在のブロックの分割工程は、前記先行するブロックの前記第１のタイミング又はノード点（β）が前記先行するブロックの前記第２のタイミング又はノード点（α）よりも遅い場合に、前記先行するブロックの前記第１のタイミング又はノード点（β）又はその付近で開始し、前記現在のブロックの第１のタイミング又はノード点（β）又はその付近で終了する新規のブロックを形成する工程を備え、前記先行するブロックの前記第１のタイミング又はノード点（β）が前記先行するブロックの前記第２のタイミング又はノード点（α）よりも早い場合に、前記第１のタイミング又はノード点（β）と前記第２のタイミング又はノード点（α）との間で前記現在のブロックを分割する工程を備えることを特徴とする請求項５６又は５７記載の方法。
【請求項６１】
入力オーディオ又はテキストデータから少なくとも前記音素データ及び単語データのいずれかを生成する工程を更に備えることを特徴とする請求項４９から６０のいずれか１項に記載の方法。
【請求項６２】
前記データファイルはオーディオデータを備え、前記音素データ及び単語データの生成工程は、
自動音声認識システムを使用して前記データファイル中のオーディオデータに対する音素データを生成する工程と、
単語復号器を使用して前記自動音声認識システムにより生成される前記音素データ内の予想単語を識別することによって単語データを生成する工程と
を備えることを特徴とする請求項６１記載の方法。
【請求項６３】
前記データファイルはテキストデータを備え、前記音素データ及び単語データの生成工程は、テキスト／音素変換装置を使用して前記データファイル中のテキストデータから音素データを生成する工程を備えることを特徴とする請求項６１記載の方法。
【請求項６４】
前記少なくとも前記音素データ及び単語データのいずれかを生成する工程は、
ａ）入力音声注釈信号を受信し処理する工程と、
ｂ）テキスト注釈を受信し処理する工程と、
ｃ）テキスト文書と前記画像データをテキストデータへと変換するための文字認識部とを表す画像データを受信する工程と
を備えることを特徴とする請求項６１記載の方法。
【請求項６５】
各前記ノードに対してタイムスタンプ情報を定義するデータを生成する工程を更に備えることを特徴とする請求項４９から６４のいずれか１項に記載の方法。
【請求項６６】
前記データベース内の各ブロックの位置を定義するデータを生成する工程を更に備えることを特徴とする請求項４９から６５のいずれか１項に記載の方法。
【請求項６７】
前記データファイルは時系列信号を含み、前記生成されたタイムスタンプデータは前記時系列信号と時間的に同期することを特徴とする請求項６５又は６６記載の方法。
【請求項６８】
前記時系列信号は少なくともオーディオ信号及びビデオ信号のいずれかであることを特徴とする請求項６７記載の方法。
【請求項６９】
ｉ）２つのノードに対するノードデータ及びこれらにまたがる１つ以上のリンクに対するリンクデータを加える工程と、
ｉｉ）ブロックデータを加えて前記２つの加えられたノードにより構成される最初のノードのブロックを提供し、
ｉｉｉ）少なくとも１つ以上の更なるノード及びリンクのいずれかに対する少なくとも更なるノードデータ及びリンクデータのいずれかを前記最初のノードのブロックへと加え、
ｉｖ）前記最初のブロックが所定数のノードに到達するまで（ｉｉｉ）を繰り返し、
ｖ）前記ブロック基準に従って前記最初のノードのブロックを分割できると判定し、
ｖ）更なるブロックデータを加えて前記最初のノードのブロックを少なくとも２つの現在のノードのブロックへと分割し、
ｖｉｉ）少なくとも１つ以上の更なるノード及びリンクのいずれかに対する少なくとも更なるノードデータ及びリンクデータのいずれかを前記現在のノードのブロックのうちの１つへと加え、
ｖｉｉｉ）いずれかの現在のブロック中のノードの数が前記所定数のノードに到達したと識別されるまで（ｖｉｉ）を繰り返し、
ｉｘ）前記ブロック基準に従って前記識別された現在のブロックを分割できると判定し、
ｘ）更なるブロックデータを加えて前記識別された現在のブロックを少なくとも２つのブロックへと分割し、
ｘｉ）少なくとも前記音素データ及び単語データのいずれかに対して生成された前記ノード及びリンクの全てに対する前記ノードデータ及びリンクデータが少なくとも前記音素ラティス及び単語ラティスのいずれかへと加えられるまで必要に応じて（ｖｉｉｉ）、（ｉｘ）、及び（ｘ）を繰り返すことにより、
各ノードに対する前記ノードデータ及び各リンクに対する前記リンクデータを処理することにより少なくとも前記音素ラティス及び単語ラティスのいずれかを形成する工程を更に備えることを特徴とする請求項４９又は５０記載の方法。
【請求項７０】
１つ以上の音素又は単語に対応するデータを請求項４から１８のいずれか１項に記載の少なくとも音素ラティス及び単語ラティスのいずれかを定義するデータへと加える方法であって、
ｉ）追加する音素又は単語の開始時間及び終了時間に対して前記ラティスにノードが既に存在するか否か判定し、既に存在しない場合には少なくとも前記開始時間及び終了時間のいずれかに対応するノードを前記ラティスに挿入することによってノードを前記ラティスへと挿入する工程と、
ｉｉ）前記追加する音素又は単語に対する前記開始時間及び終了時間に対応する前記ノード間にリンクを加える工程と、
ｉｉｉ）更なるノードの挿入により変更する必要がある関連するリンクデータを有する可能性があるのがどの既存のノードであるかを選択する工程と、
ｉｖ）前記選択された既存のノードのリンクデータを分析する工程と、
ｖ）必要に応じて前記分析されたリンクデータを変更する工程と
を備え、
前記選択工程では、各更なるノードに対して、前記更なるノードを含むブロック中の前記更なるノードに先行するノード及び所定数のブロック以下の複数のブロックだけ前記更なるノードを含む前記ブロックに先行する各ブロック中の全てのノードが選択されることを特徴とする方法。
【請求項７１】
前記選択工程では、所定のブロックへと挿入する更なるノードに対して、ｉ）挿入中の前記ノードに先行する前記所定のブロック中のノード及びｉｉ）前記先行するブロック中の全てのノードのみが選択されることを特徴とする請求項７０記載の方法。
【請求項７２】
前記データは請求項７に記載される通りであり、前記選択工程は、タイミング又はノード点により定義される挿入位置において所定のブロックへと挿入される更なるノードに対して、
ａ）前記挿入位置が前記所定のブロックの前記第１のタイミング又はノード点（β）の後にある場合には、前記挿入位置に先行する前記所定のブロック中の前記既存のノード、
ｂ）前記挿入位置が前記所定のブロックの前記第１のタイミング又はノード点（β）の前にある場合には、ｉ）前記挿入位置に先行する前記所定のブロック中の前記既存のノード及びｉｉ）前記先行するブロックの前記第２のタイミング又はノード点（α）又はその後にある前記先行するブロック中の前記既存のノードを選択することを特徴とする請求項７０記載の方法。
【請求項７３】
前記データは請求項９又はそれに従属したいずれか１項に記載される通りであり、前記分析工程では各選択されたノードから伸びる最長のリンクのみが分析されることを特徴とする請求項７０から７２のいずれか１項に記載の方法。
【請求項７４】
請求項７０から７３のいずれか１項に記載の方法を利用して更なるデータを前記ラティスへと加える工程を更に備えることを特徴とする請求項４９から６９のいずれか１項に記載の方法。
【請求項７５】
請求項１から１８のいずれか１項に記載のデータ又は請求項２１、２２、及び４９から７４のいずれか１項に記載の方法を実現するようにプロセッサを制御するためのプロセッサ実現可能な命令を搬送するデータキャリア。
【請求項７６】
請求項２１、２２、及び４９から７４のいずれか１項に記載の方法を実現するようにプロセッサを制御するためのプロセッサ実現可能な命令。
【発明の詳細な説明】
【０００１】
本発明は、データベースに格納されるデータファイルのその後の検索を容易にするためのデータファイルの注釈付けに関する。また、本発明は、データファイルに付加される注釈データを生成するシステムと、データベース中の注釈データを検索し、ユーザの入力質問に応答して所望のデータファイルを取得するシステムとに関する。更に、本発明は、ノード及びリンクの未整列のリストをノード及びリンクの整列・ブロック化されたリストへと変換するシステムに関する。
【０００２】
情報のデータベースはよく知られているが、データベースから所望の情報の位置特定・取得をいかに迅速に効率良く行なうかという課題を抱えている。既存のデータベース検索ツールでは、ユーザは打ち込んだキーワードを使用してデータベースを検索することができる。この方法は迅速で効率が良いが、この種の検索はビデオデータベース又は音声データベースなどの種々のデータベースには適していない。
【０００３】
一の側面において本発明は、ユーザの入力質問に応答して迅速且つ効率良く検索を実行できるように、データベース内のデータファイルの注釈付けのためのデータ構造を提供することを目的とする。
【０００４】
別の側面において本発明は、データベース内に格納するデータファイルに注釈付けするための注釈データとして使用するための音素／単語ラティス（ａ ｐｈｏｎｅｍｅ ａｎｄ ｗｏｒｄ ｌａｔｔｉｃｅ）を定義するデータを提供する。このデータは複数のノード及びこれらのノードを結合する複数のリンクを定義するのが好ましい。更なるデータにより複数の音素が複数のリンクとそれぞれ関連付けられ、更なるデータにより少なくとも１つの単語が複数のリンクのうちの少なくとも１つと関連付けられ、更なるデータによりリンクが所定の最大数のブロックを越えて伸びるようにノードに対するブロック構成が定義される。更に、リンクは後続のブロックまでしか伸びないのが好ましい。
【０００５】
別の面において本発明は、データベースにファイルされたデータに注釈付けするための上述の注釈データを使用するデータベースを検索するための装置を提供する。この装置はユーザの質問又は入力に応答して音素データを生成し、生成された音素データを使用してデータベースを検索するように構成されるのが好ましい。更に、ユーザの入力又は質問から単語データも共に生成されるのが好ましい。
【０００６】
別の側面において本発明は、受信された音素データ及び単語データに対応する音素／単語ラティスを生成する装置において、複数のリンク及びリンクがまたがる複数のノードを定義する手段と、リンクを音素又は単語と関連付ける手段と、リンクが時間順のブロックのシーケンスにおいて最大数のブロックだけしか後に伸びないシーケンス中のノードを配置する手段とを備えることを特徴とする装置を提供する。好ましくは、リンクは最大後続するブロックまで伸びることができる。更に、この装置はラティスを形成するときにノード又はリンクを徐々に加え、既存のノードのブロックを少なくとも２つのノードのブロックへと分割するように構成されるのが好ましい。
【０００７】
別の側面において本発明は、音素又は単語を上述の型のうちのいずれかの音素／単語ラティスへと加えるための装置であって、リンクが１つのブロックから別のブロックへと伸びることを許される程度に従って現在の音素／単語ラティスを定義するどのデータが修正される必要があるかを分析するように構成される装置を提供する。この分析は、更に、先行するブロックで始まるリンクが終点とする各ブロック中の最終のノードを識別する点と、後続するブロックまで伸びるリンクが始点とする各ブロック中の先頭のノードを識別する点とのラティス内の位置に従うのが好ましい。
【０００８】
別の側面において本発明は、音素又は単語を上述の型のうちのいずれかの音素／単語ラティスへと加える方法において、リンクが＊＊＊（英文明細書３頁の最終段落以降に記載されるはずの内容が欠落しています。）程度に従って現在の音素／単語ラティスを定義するどのデータが修正される必要があるかを分析することからなる方法を提供する。この分析は、更に、先行するブロックで始まるリンクが終点とする各ブロック中の最終のノードを識別する各点のラティス内の位置に従うのが好ましい。
【０００９】
別の側面において、ノード及びリンクの未整列のリストをノード及びリンクの整列・ブロック化されたリストへと変換する方法及び装置が提供される。ブロックは充填・分割することにより形成され、ブロックが満杯になるまで連続するノードがブロックへと挿入された後、新規のブロックが開始される。新規のノードが既に満杯のブロックを過剰に満たす場合、そのブロックは２つ以上のブロックへと分割される。どのブロックまで伸びることができるかに関するリンクにおける制限は、ブロック分割プロセスの速度を向上し、どのノードが古いブロックに残り、どのノードが新規のブロックに入るかを識別するのに使用される。
【００１０】
【発明の実施の形態】
次に、添付の図面を参照して、本発明の各実施形態を説明する。
【００１１】
本発明の各実施形態は専用ハードウェア回路を使用して実現可能であるが、以下に説明する実施形態は、パーソナルコンピュータ、ワークステーション、複写機、ファクシミリ装置、又は携帯情報端末（ＰＤＡ）などの処理ハードウェアと連携して実行されるコンピュータソフトウェアまたはコードにおいて実現される。
【００１２】
図１は本発明の実施形態を動作させるようにプログラムされたパーソナルコンピュータ（ＰＣ）１を示す。キーボード３、ポインティングデバイス５、マイク７、及び電話回線９はインタフェース１１を介してＰＣ１に接続される。キーボード３及びポインティングデバイス５によりユーザはシステムを制御することができる。マイク７はユーザからの音響音声信号を等価の電気信号へと変換し、それを処理するためにＰＣ１に供給する。ＰＣ１が例えば遠隔のコンピュータ又は遠隔のユーザと通信できるように、内部モデム及び音声受信回路（不図示）が電話回線９に接続される。
【００１３】
ＰＣ１を本発明に従って動作させるプログラム命令は、既存のＰＣ１と共に使用するために、例えば、磁気ディスク１３などの記憶装置上で供給されても、あるいは、内部モデム及び電話回線９を介してインターネット（不図示）からソフトウェアをダウンロードすることによって供給されても良い。
【００１４】
［データファイルの注釈付け］
図２は、本実施形態において音素／単語注釈付け装置２５により入力データファイル２３に対する注釈データ２１を生成する方法を示すブロック図である。図２に示すように、生成された音素／単語注釈データ２１はデータ結合装置２７においてデータファイル２３と結合され、結合されたデータファイル出力がデータベース２９へと入力される。本実施形態では、注釈データ２１は結合された音素（又は音素状）／単語ラティスを備え、この音素／単語ラティスによりユーザは音声質問によってデータベースから情報を検索できるようになる。当業者は、データファイル２３がビデオファイル、音声ファイル、マルチメディアファイルなどの任意の種類のデータファイルであって良いことを認識するであろう。
【００１５】
ビデオデータファイルからの音声データを自動音声認識装置に通すことによって注釈データとして音声ストリームに対するＮ−ベスト単語リスト（Ｎ−Ｂｅｓｔ ｗｏｒｄ ｌｉｓｔｓ）を生成するシステムが提案されている。しかし、このような単語ベースのシステムには幾つかの問題点がある。これらの問題点には、（ｉ）従来の音声認識システムが認識時に基本的な誤りを犯すこと、（ｉｉ）従来の音声認識システムの状態は恐らく２０，０００語から１００，０００語の辞書を使用し、その語彙の範囲外の単語を生成できないこと、及び（ｉｉｉ）Ｎ−ベストリストの生成は各段階における仮説の数と共に指数関数的に増加し、結果として、長い発話の場合に注釈データが巨大化することが含まれる。
【００１６】
注釈データを生成して対応するデータファイルを検索するのに同じ自動音声認識システムを使用する場合、同じ復号化エラーが発生する可能性があるので、これらの問題のうち第１の問題はそれほど重要でないかもしれない。しかし、自動音声認識システムが毎年進歩するにつれ、将来的に同じ種類の誤りが発生しなくなることが考えられ、そうなれば、後日対応するデータファイルを検索することが不可能になる。第２の問題に関して、ユーザは入力質問語として名前及び場所（音声認識辞書にはない可能性がある）を使用する可能性が高いので、この問題はビデオデータの適用の際には特に重要である。名前の代わりに、自動音声認識システムは、通常、語彙の範囲外の単語を語彙の範囲内の音素的に類似する単語と置き替えるであろう。その結果、自動音声認識システムはしばしば近接する復号データを破損する。また、後で要求があったときに所望のデータファイルの検索に失敗する可能性も生じる。
【００１７】
これに対し、提案される音素／単語ラティス注釈データでは、データベース２９中の単語データを使用して迅速で効率的な検索を実行することができ、所望のデータファイルの提供に失敗しても、より強固な音素データを使用する更なる検索を実行することができる。音素／単語ラティスは単一の入口点と単一の出口点を有する非周期有向グラフである。このグラフは、データファイル中の音声ストリームの様々なパーズを表す。各単語は単一の代替物により置換される必要がなく、１つの単語は２つ以上の単語又は音素で置換することができ、構造全体は１つ以上の単語又は音素の代替物を形成することができるので、これは単に複数の代替物を伴う単語のシーケンスではない。従って、音素／単語ラティス内のデータの密度は上述のＮ−ベスト技術のように指数関数的に増加するのではなく、本質的に音声データの全体を通して線形のままである。音素は辞書に依存せず、システムが名前、場所、外来語などの語彙の範囲外の単語に対処できるようにするので、音声認識の分野の当業者は音素データの使用がより強固であることを認識するであろう。また、単語が元の自動音声認識システムにより理解されなかったときでもデータベースに配置されるデータファイルは検索可能であるので、音素データの使用によりシステムは今後の使用にも耐えるものとなる。
【００１８】
次に、図３を参照してこの音素／単語ラティス注釈データをビデオデータファイルに対して生成することができる方法を説明する。図３に示すように、ビデオデータファイル３１は、ビデオシーケンスを形成する画像のシーケンスを定義するビデオデータ３１−１と、ビデオシーケンスと関連付けられる音声を定義する音声データ３１−２とを備える。周知の通り、使用中、ビデオデータ及び音声データの双方が同時にユーザに供給されるように、音声データ３１−２はビデオデータ３１−１と時間的に同期している。
【００１９】
図３に示すように、本実施形態では、音声データ３１−２は自動音声認識装置３３へと入力される。自動音声認識装置３３は音声データ３１−２のストリームに対応する音素ラティスを生成するように動作可能である。このような自動音声認識装置３３は従来広く利用されているので、ここでは更に詳細に説明しない。この種の音声認識システムについて更なる情報を必要とする場合は、例えば、ローレンス・ラビナーとビーン・ハン・ジュアン（Ｌａｗｒｅｎｃｅ Ｒａｂｉｎｅｒ ａｎｄ Ｂｉｉｎｇ−Ｈｗａｎｇ Ｊｕａｎｇ）による著作「音声認識の基礎（Ｆｕｎｄａｍｅｎｔａｌｓ ｏｆ Ｓｐｅｅｃｈ Ｒｅｃｏｇｎｉｔｉｏｎ）」、特にその４２ページから５０ページを参照されたい。
【００２０】
図４ａは、「．．．ｎｏｗ ｉｓ ｔｈｅ ｗｉｎｔｅｒ ｏｆ ｏｕｒ．．．」というフレーズに対応する入力音声に対して音声認識装置３３により出力された音素ラティスデータの形態を示す。自動音声認識装置３３はこの入力音声発話に対応する複数の異なる予想音素ストリングを識別する。例えば、音声認識システムは音声ストリングの第１の音素が／ｍ／又は／ｎ／であると考える。明瞭にする目的で、第１の音素に対する代替候補のみを示す。音声認識の分野で良く知られているように、これらの異なる可能性は独自の重みを有する。この重みは、音声認識装置３３により生成され、音声認識装置の出力の信頼度を示す。例えば、音素／ｎ／に０．９の重みが与えられ、音素／ｍ／に０．１の重みが与えられる場合、音声認識システムは音声の対応部分が音素／ｎ／であることを相当に確信しているが、音素／ｍ／である可能性も依然として残っていることを示す。しかし、本実施形態では、この音素の重み付けは実行されない。
【００２１】
図３に示すように、自動音声認識装置３３により出力される音素ラティスデータ３５は単語復号器３７へと入力される。単語復号器３７は、音素ラティスデータ３５内の予想単語を識別するように動作可能である。本実施形態では、単語復号器３７により識別される単語は音素ラティスデータ構造に組み込まれている。例えば、図４ａに示す音素ラティスに関して、単語復号器３７は「ＮＯＷ」、「ＩＳ」、「ＴＨＥ」、「ＷＩＮＴＥＲ」、「ＯＦ」、及び「ＯＵＲ」の各単語を識別する。図４ｂに示すように、これらの識別された単語は音声認識装置３３により出力される音素ラティスデータ構造へと加えられ、注釈データ３１−３を形成する音素／単語ラティスデータ構造が生成される。この注釈データ３１−３はビデオデータファイル３１と結合され、増補ビデオデータファイル３１’が生成される。この増補ビデオデータファイル３１’はデータベース２９に格納される。音声データ３１−２がビデオデータ３１−１と時間的に同期しているのと同様に、注釈データ３１−３も対応するビデオデータ３１−１及び音声データ３１−２と時間的に同期すると共に関連しているので、注釈データ３１−３の対応する部分の検索・位置特定によりビデオデータ及び音声データの所望の部分を取得することができることを当業者は認識するであろう。
【００２２】
本実施形態において、データベース２９に格納される注釈データ３１−３は以下のような一般的な形態を有する：
ヘッダ
−開始時間
−単語か、音素か、又は混合かを示すフラグ
−メモリ内の注釈データのブロックの位置を所定の時点と関連付ける時
間指標
−使用される単語集合（すなわち、辞書）
−使用される音素集合
−音素確率データ
−語彙が所属する言語
ブロック（ｉ）　ｉ＝０，１，２，．．．．．
ノードＮｊ　ｊ＝０，１，２，．．．．．
−ブロック開始からのノードの時間オフセット
−音素リンク（ｋ）　ｋ＝０，１，２，．．．．．
ノードＮｊに対するオフセット＝Ｎｋ−Ｎｊ（ＮｋはリンクＫが結合するノード）、又はＮｋがブロック（ｉ＋１）にある場合、ノードＮｊに対するオフセット＝Ｎｋ−Ｎｊ（Ｎｂはブロック（ｉ）におけるノードの個数）
リンク（ｋ）と関連する音素
−単語リンク（ｌ）　ｌ＝０，１，２，．．．．．
ノードＮｊに対するオフセット＝Ｎｋ−Ｎｊ（Ｎｊはリンクｌが結合するノード）、又はＮｋがブロック（ｉ＋１）にある場合、ノードＮｊに対するオフセット＝Ｎｋ−Ｎｊ（Ｎｂはブロック（ｉ）におけるノードの個数）
リンク（ｌ）と関連する単語
ヘッダ中の開始時間データは、データの送信の日時を識別することができる。例えば、ビデオファイルがニュース放送である場合、開始時間は放送の正確な時間及びそれが放送された日付を含んでも良い。
【００２３】
データベース内の全てのデータファイルが上述の結合された音素／単語ラティス注釈データを含むとは限らないので、注釈データが単語注釈データであるか、音素注釈データであるか、又はその混合であるかを識別するフラグが設けられる。この場合、注釈データを検索するのに別の検索戦略が使用されるであろう。
【００２４】
本実施形態では、検索が所定の音声データストリームに対する注釈データの中央へとジャンプできるようにするために、注釈データは複数のブロックへと分割される。従って、ヘッダはメモリ内の注釈データのブロックの位置を開始時間とブロックの開始に対応する時間との間の所定の時間オフセットに関連付ける時間指標を含む。
【００２５】
また、ヘッダは使用される単語集合（すなわち、辞書）、使用される音素集合、及び語彙が所属する言語を定義するデータも含む。ヘッダは、注釈データを生成するのに使用される自動音声認識システムの詳細と注釈データの生成中に使用されるシステムの適切な設定とを更に含んでも良い。
【００２６】
音素確率データは、注釈データを生成した自動音声認識システムなどのシステムにとっての挿入、削除、誤認識、及び復号化の確率を定義する。
【００２７】
ヘッダの後には注釈データのブロックが続き、ブロック中のノードごとに、ブロックの開始からのノードの時間オフセット、ノードを音素により他のノードに結合する音素リンク、及びノードを単語により他のノードに結合する単語リンクを識別する。各音素リンクと各単語リンクは、そのリンクと関連する音素又は単語を識別する。また、各音素リンクと各単語リンクは、現在のノードに対するオフセットも識別する。例えば、ノードＮ５０が音素リンクによりノードＮ５５にリンクされる場合、ノードＮ５０に対するオフセットは５である。当業者は、このようなオフセット指示を使用することで、連続する注釈データを個別のブロックに分割できるようになることを認識するであろう。
【００２８】
自動音声認識装置が音声認識装置の出力の信頼度を示す重みを出力する実施形態では、これらの重み、すなわち、信頼度スコアもデータ構造内に含まれるであろう。特に、ノードに到達する信頼度を示す各ノードに対して信頼度スコアが提供される。また、音素／単語リンクの各々は、対応する音素又は単語に付される重みに応じて遷移スコアを含むであろう。これらの重みは、信頼度スコアの低い候補を破棄することによってデータの検索・取得を制御するのに使用されるであろう。
【００２９】
［データファイルの検索］
図５は、データベース２９から注釈付けされたデータファイルを検索するのに使用可能なユーザ端末５９の形態を示すブロック図である。このユーザ端末５９は、例えば、パーソナルコンピュータ又はハンドヘルド機器などであっても良い。図５に示すように本実施形態では、ユーザ端末５９は、注釈データファイルのデータベース２９、自動音声認識装置５１、サーチエンジン５３、制御装置５５、及びディスプレイ５７を備える。動作中、自動音声認識装置５１はマイク７及び入力ライン６１を介して受信されたユーザ３９からの入力音声質問を処理し、そこから対応する音素／単語データを生成するように動作可能である。このデータは音素／単語ラティスの形態をとっていても良いが、必ずしもそうである必要はない。この音素／単語データは制御装置５５へと入力される。制御装置５５は、サーチエンジン５３を使用してデータベース２９の適切な検索を開始するように動作可能である。サーチエンジン５３により生成された検索の結果は制御装置５５に送り返される。制御装置５５は検索結果を解析して、適切な表示データを生成すると共にディスプレイ５７を介してユーザに対して表示する。実行可能な検索技術の更なる詳細は、同時係属出願の国際出願ＰＣＴ／ＧＢ００／００７１８及び英国特許出願第９９２５５６１．４号において示され、その内容は参照により本明細書に組み入れられる。
【００３０】
［代替実施形態］
データベース中のデータファイルのこの種の音素／単語注釈付けは、ユーザが音声によってデータベースを検索できるようにするための便利且つ効果的な方法を提供することを当業者は認識するであろう。例示の実施形態では、単一の音声データストリームが注釈付けされ、後のユーザによる検索に備えてデータベースに格納された。入力データファイルがビデオデータファイルに対応する場合、そのデータファイル内の音声データは、通常、異なる話者に対する音声データを含むことを当業者は認識するであろう。音声データに対して単一の注釈データのストリームを生成するのではなく、各話者の音声データに対して別々の音素／単語ラティス注釈データを生成することができる。これは、音声信号のピッチ又は別の際立った特徴から各話者に対応する音声データを識別し、次に、異なる話者の音声に個別に注釈付けすることにより実行されても良い。また、話者ごとに音声データを処理してデータを抽出することが可能になるので、音声データがステレオで記録されても、あるいは、音声データを生成する際にマイクのアレイが使用されてもこの個別の生成を実現できるであろう。
【００３１】
図６は、このような実施形態における注釈データの形態を示し、第１の話者は「．．．ｔｈｉｓ ｓｏ」という言葉を話し、第２の話者は「ｙｅｓ」と応答している。図６に示すように、異なる話者の音声データに対する注釈データは相互に時間的に同期しているので、データファイル内のビデオデータ及び音声データとも注釈データは時間的に同期することになる。この実施形態では、データ構造中のヘッダ情報は、注釈データ内の異なる話者のリストと、話者ごとの言語、アクセント、方言及び音素集合を定義するデータとを含むのが好ましく、また、各ブロックはそのブロック中でアクティブ状態にある話者を識別すべきである。
【００３２】
上述の実施形態では、データベース中のデータファイルに注釈付けするための注釈データを生成するのに音声認識システムが使用された。この注釈データを生成するのに別の技術も使用可能であることを当業者は認識するであろう。例えば、オペレータが音声データを聴取し、音声／単語記号表記を生成することにより、手作業で注釈データを生成することも可能である。
【００３３】
上述の実施形態では、注釈データはデータファイル自体に格納されている音声から生成された。注釈データを入力するのに別の技術も使用可能であることを当業者は認識するであろう。図７は、データベース２９に格納すべきデータファイル９１に注釈付けするためにユーザがマイク７を介して音声注釈データを入力可能なユーザ端末５９の形態を示す。本実施形態では、データファイル９１は、例えば、カメラにより生成される２次元画像を備える。ユーザ端末５９によりユーザ３９は２Ｄ画像に適切な注釈を付けることができ、後にこれを使用してデータベース２９からその２Ｄ画像を検索することができる。本実施形態では、自動音声認識装置５１により入力音声注釈信号が音素／単語ラティス注釈データへと変換され、このデータが制御装置５５へと送信される。ユーザの入力に応答して、制御装置５５はデータベース２９から適切な２Ｄファイルを検索し、音素／単語注釈データをデータファイル９１に付加する。増補されたデータファイルはデータベース２９へと戻される。この注釈付け工程の間、注釈データが正しいデータファイル９１と関連付けられていることをユーザが確認できるように、制御装置５５は２Ｄ画像をディスプレイ５７に表示するように動作可能である。
【００３４】
自動音声認識装置５１は、（ｉ）入力発話に対し音素ラティスを生成し、（ｉｉ）次に、音素ラティス内の単語を識別し、（ｉｉｉ）最後にそれら２つを結合することにより音素／単語ラティス注釈データを生成する。図８は、「ｐｉｃｔｕｒｅ ｏｆ ｔｈｅ Ｔａｊ−Ｍａｈａｌ」という入力発話に対して生成される音素／単語ラティス注釈データの形態を示す。図示するように、自動音声認識装置は、この入力発話に対応する複数の異なる予想音素ストリングを識別する。図８に示すように、自動音声認識装置５１が音素ラティス内で識別する単語は音素ラティスデータ構造に組み込まれる。図示するように、自動音声認識装置５１は、例示のフレーズに対して「ｐｉｃｔｕｒｅ」、「ｏｆ」、「ｏｆｆ」、「ｔｈｅ」、「ｏｔｈｅｒ」、「ｔａ」、「ｔａｒ」、「ｊａｍ」、「ａｈ」、「ｈａｌ」、［ｈａ］、及び「ａｌ」という単語を識別する。制御装置５５は、この注釈データを２Ｄ画像データファイル９１へと加えるように動作可能である。データファイル９１はデータベース２９に格納される。
【００３５】
本実施形態を使用して、患者のＸ線写真、例えば、ＮＭＲスキャンの３Ｄビデオ、超音波スキャンなどのいかなる種類の画像でも注釈付けできることを当業者は認識するであろう。また、本実施形態を使用することで音声データ又は地震データなどの１次元データにも注釈付けできる。
【００３６】
上述の実施形態では、データファイルは音声による注釈で注釈付けされていた。注釈を入力するのに別の技術も使用可能であることを当業者は認識するであろう。例えば、図９は、データベース２９に格納すべきデータファイル９１に注釈付けするためにユーザがキーボード３を介してタイプ入力による注釈データを入力可能なユーザ端末５９の形態を示す。本実施形態では、タイプ入力は音素記号表記装置７５により音素／単語ラティス注釈データへと変換され（内部音素辞書（不図示）を使用）、このデータが制御装置５５へと送信される。ユーザの入力に応答して、制御装置５５はデータベース２９から適切な２Ｄファイルを検索し、音素／単語注釈データをデータファイル９１へと付加する。増補されたデータファイルはデータベース２９へと戻される。この注釈付け工程の間、注釈データが正しいデータファイル９１と関連付けられていることをユーザが確認できるように、制御装置５５はディスプレイ５７に２Ｄ画像を表示するように動作可能である。
【００３７】
図１０は、入力発話「ｐｉｃｔｕｒｅ ｏｆ ｔｈｅ Ｔａｊ−Ｍａｈａｌ」に対して生成される音素／単語ラティス注釈データの形態を示す。図２に示すように、音素／単語ラティスは単一の入口点及び単一の出口点を有する非周期有向グラフである。これはユーザの入力の様々なパーズを表す。図１０に示すように、音素記号表記装置７５はタイプ入力に対応する複数の異なる予想音素ストリングを識別する。
【００３８】
図１１は、文書注釈付けシステムを示すブロック図である。特に、図１１に示すように、テキスト文書１０１は文書スキャナ１０３により画像データファイルへと変換される。次に、画像データファイルは光学式文字認識（ＯＣＲ）装置１０５へと送信され、光学式文字認識装置１０５は文書１０１の画像データを電子テキストへと変換する。この電子テキストは音素記号表記装置１０７へと供給される。音素記号表記装置１０７は、データファイル１１１を形成するためにスキャナ１０３により出力される画像データに付加される音素／単語注釈データ１０９を生成するように動作可能である。図１１に示すように、データファイル１１１は後の検索に備えてデータベース２９に格納される。本実施形態では、注釈データ１０９は上述の結合された音素／単語ラティスを備え、ユーザは後に音声質問によりデータベース２９からデータファイル１１１を検索することができる。
【００３９】
図１２は、図１５に示す文書注釈付けシステムの変形を示す。図１６に示すシステムと、図１１に示すシステムとの相違点は、スキャナ１０３により出力される画像データではなく、光学式文字認識装置１０５の出力を使用してデータファイル１１３を生成することである。図１２に示すシステムのその他の部分は図１１に示すシステムと同じであるので、更なる説明は行なわない。
【００４０】
図１３は、図１１に示す文書注釈付けシステムの更なる変形を示す。図１３に示す実施形態では、入力文書はスキャナ１０３ではなく、ファクシミリ装置１１５により受信される。ファクシミリ装置により出力される画像データは図１１に示すスキャナ１０３により出力される画像データと同様に処理されるので、説明は繰り返さない。
上述の実施形態では、画像データ又はテキストデータに注釈付けするための注釈データを生成するのに音素記号表記装置１０７が使用された。他の技術も使用可能であることを当業者は認識するであろう。例えば、オペレータが文書自体の画像から手作業でこの注釈データを生成することができる。
【００４１】
第１実施形態では、音素注釈データを生成するために、データファイル３１からの音声データは自動音声認識装置を介して送信された。状況によっては、音声データの記号表記がデータファイル中に存在する。このような実施形態が図１４において示される。本実施形態では、データファイル８１はビデオデータ８１−１、音声データ８１−２、及びビデオフィルム中の種々の俳優の台詞を定義するスクリプトデータ８１−３を有するデジタルビデオファイルを表す。図１４に示すように、スクリプトデータ８１−３はテキスト／音素変換装置８３を介して送信される。テキスト／音素変換装置８３は、単語を予想音素シーケンスに変換する格納辞書を使用して音素ラティスデータ８５を生成する。この音素ラティスデータ８５はスクリプトデータ８１−３と結合され、上述の音素／単語ラティス注釈データ８１−４が生成される。この注釈データはデータファイル８１へと加えられて増補データファイル８１’が生成され、この増補データファイル８１’がデータベース２９へと加えられる。スクリプトデータは、通常、話者を示す標識を含んでいるため、本実施形態によりビデオデータファイル内の異なる話者に対して別々の音素／単語ラティス注釈データを容易に生成できることを当業者は認識するであろう。音素／単語ラティス注釈データと、ビデオデータ及び音声データとの同期は、自動音声認識システム（不図示）を使用してスクリプトデータと音声データを強制的に時間調整することにより実現できる。
【００４２】
上述の実施形態では、音素（音素状）／単語ラティスを使用してデータファイルが注釈付けされた。以上の説明及び請求の範囲中の用語「音素」は言語学上の意味には限定されず、音素、音節、カタカナ（日本語のアルファベット）などの標準的な音声認識システムで識別され、使用される様々な部分語単位を含むことを音声認識及び音声処理の分野の当業者は認識するであろう。
【００４３】
［ラティスの生成］
先の記述では、図３を参照して図４ｂに示す音素／単語ラティスデータ構造の生成についての説明が行なわれた。図１５から図１７を参照してノードのブロックへの好適な分割を含むデータ構造の好適な形態を説明する。その後、図１８から図２２を参照して好適なデータ構造を生成する方法の１つを説明する。
【００４４】
図１５ａは、共通のゼロタイムを基準とするラティスの各ノードのタイミングを示す。この例では、第１のノードが０．１０秒の時点で発生するように共通のゼロタイムが設定される。尚、図１５ａは概略を示すものであり、時間軸は線形的に表されていない。
【００４５】
本実施形態では、図１５ｂに示すように、ノードは３つのブロックへと分割される。本実施形態では、ノードのブロックへの分割はブロックマーカ、すなわち、フラグ２０２、２０４、２０６、及び２０８により実現される。ブロックマーカ２０４、２０６、及び２０８は、ブロックの最終ノードの直後に配置される。しかし、図１５ｂでは説明を明瞭にする目的でそこからわずかに間隔を置いた位置において示されている。ブロックマーカ２０４は、ブロック０の終了及びブロック１の開始をマークし、同様に、ブロックマーカ２０６はブロック１の終了及びブロック２の開始をマークする。ブロックマーカ２０８はラティスの終端にあり、ブロック２の終了のみを示す。ブロックマーカ２０２は、ブロック０の開始の境界を提供するためにｔ＝０．００秒の時点に組み込まれる。本実施形態では、ブロック０は５個のノードを有し、ブロック１は５個のノードを有し、ブロック２は７個のノードを有する。
【００４６】
各ノードの時間は、各ブロックの開始の時間を基準として与えられる。これは、ブロック０中の各ノードのタイミングには影響しない。しかし、それ以降のブロックに関しては、図１５ａに示すように、新規のオフセットタイミングは各ノードの絶対的相対タイミングと異なる。本実施形態では、ブロック０以外の各ブロックに対する開始時間は、先行するブロックの最終ノードの時間からとられる。例えば、図１５ａにおいて、音素／ｉｈ／と／ｚ／との間のノードが０．７１秒で発生しており、ブロック１の最終ノードであることが明らかである。図１５ａから次のノード、すなわち、音素／ｚ／と音素／ｄｈ／との間のノードが０．９４秒、すなわち、０．７１秒の時点の０．２３秒後に発生することが明らかである。従って、図１５ｂから明らかなように、ブロック１の第１のノードのオフセット時間は０．２３秒である。
【００４７】
ラティス全体の開始からではなく、各ブロックの開始を基準として判定される時間オフセットの使用により、以下のようなダイナミックレンジに関する利点が提供される。ラティスの合計時間が増加すると、ラティス構造にタイミング値を記録するのに使用されるデータ型のダイナミックレンジもそれに伴って拡大する必要が生じ、大容量のメモリを消費することになる。未知の長さのデータファイルに対してラティスが提供されるとき、例えば、１分のテレビＣＭ、あるいは、何時間も続く映画又はテレビ番組に注釈付けするために共通のラティス構造を使用することが望まれる場合、メモリ消費の問題は悪化する。これに対し、単一のブロックの最大予想時間オフセットを収容するだけで良いので、ブロックへと分割されるラティス構造に対する対応するデータ型のダイナミックレンジは大幅に縮小される。データファイルの最大持続時間に関わらず、この状況は変動しない。本実施形態では、使用されるデータ型は整数値を提供する。整数の各値は１００分の１秒単位で計測されたオフセット時間を表す。
また、図１５ｂはアルファ（α）及びベータ（β）として識別されるラティス構造の特定の部分を示す。これらの項目の重要性については後述する。
【００４８】
図１６ａを参照して、音素／単語ラティスデータ構造の好適な形態においてノードごとにデータが保持される形式を説明する。図１６ａは一例としてラティスの第１のノードに対するデータの形式を示す。この特定ノードに対するデータは、７つのデータ構成要素２１０、２１２、２１４、２１６、２１８、２２０、及び２２２の形態をとる。
【００４９】
第１のデータ構成要素２１０は、ブロックの開始からのノードの時間オフセットを指定する。この例では、値は０．１０秒であり、前述の整数データ型により実施される。
【００５０】
第２のデータ構成要素２１２は単語リンク「ＮＯＷ」を表す。この単語リンクが第１のノードから伸びているのが図１５ａ及び図１５ｂにおいて示される。第３のデータ構成要素は前述のリンク、すなわち、単語リンク「ＮＯＷ」のノードオフセットを指定する。これは、前述のリンクがまたがるノードの個数を意味する。図１５ａ及び図１５ｂを参照すると、単語リンク「ＮＯＷ」の終点となるノードは、リンクの始点となるノードから３番目のノードであることが明らかである。従って、図１６ａにおいて値００３により例証的に表されるように、ノードオフセットは３である。本実施形態では、ノードオフセット値を実現するために使用されるデータ型も、整数値を提供するデータ型である。
【００５１】
第４のデータ構成要素２１６は、第１のノードから第２のノードまで伸びる音素／ｎ／を表す。このため、ノードオフセットは必然的に１となり、図１６ａに示すように第５のデータ構成要素２１８に対する値００１に直結する。同様に、第６のデータ構成要素２２０は音素リンク／ｍ／を表し、第７のデータ構成要素２２２はそのリンクのノードオフセットを示す。ノードオフセットは１に等しく、００１として表される。
【００５２】
データ構成要素２１２、２１６、及び２２０がリンクと関連する単語又は音素を表す方法は、任意の適切な方法で実現できる。本実施形態では、データ構成要素２１２、２１６、及び２２０は、単語指標入口値（単語リンクの場合）に対応する整数値又は音素指標入口値（音素リンクの場合）からなる。指標入口値は、単語又は音素のリストを含む対応する単語指標又は音素指標において入口を適宜識別するのに役立つ。本実施形態では、対応する単語指標又は音素指標は、先に説明した注釈データ３１−３のヘッダ部分において保持される。他の実施形態では、ヘッダ自体が１つ以上の単語指標又は音素指標を格納する別個のデータベースへの更なる相互参照を含むだけであっても良い。
【００５３】
一般的に、所定のノードに対応する異なるリンクは図１６ａのデータ形式で任意の望ましい相対順序で配置することが可能である。しかし、本実施形態では、最大のノードオフセットを有する単語リンク又は音素リンク、すなわち、「最長」のリンクがシーケンスの先頭に配置される好適な順序が使用される。従って、この場合には、「最長」のリンクは３個のノードのノードオフセットを有する単語リンク「ＮＯＷ」であり、各々が１のノードオフセットを有する「より短い」音素リンク／ｎ／及び／ｍ／より前に配置される。この好適な構成の利点については後述する。
【００５４】
図１６ａに示す形態をとるノードごとのデータは時間順に整列され、ラティス全体（ヘッダ以外）を定義するデータストリームが形成される。図１５ｂに示すラティスに対するデータストリームが図１６ｂに示される。図示するように、データストリームは、後続するデータ構成要素がそれぞれ次のノードを参照することを識別するためのノードフラグとして機能するデータ構成要素２２５から２４１を追加的に含む。また、データストリームは、図１５ｂを参照して上述したブロックマーカ２０２、２０４、２０６、及び２０８をそれぞれ実現する更なるデータ構成要素２４４、２４６、２４８、及び２５０を含む。
【００５５】
先の説明で図４ｂを参照してこのラティスデータ構造のブロック構成の第１の利点を述べた。その利点とは、すなわち、検索が所定の音声データストリームに対する注釈データの中央へとジャンプすることが可能になるということである。このため、同じく図４ｂを参照して説明したヘッダは、メモリ内の注釈データのブロックの位置を開始時間とブロックの開始に対応する時間との間の所定の時間オフセットと関連付ける時間指標を含む。図１５ｂを参照して説明したように、本実施形態では、所定のブロックの開始に対応する時間は所定のブロックに先行するブロックの最終ノードの時間である。
【００５６】
図１５ｂに示すブロック構成は更なる特徴及び利点を示すので、それを次に説明する。ブロックは、単語リンク又は音素リンクがブロック間にまたがることを許される程度により判定される。例えば、本実施形態では、ブロック位置は、リンクが直接隣接するブロック以外のブロックへとまたがらないという基準を満たす。ブロック０の各ノードを例にとると、音素リンク／ｎ／、／ｍ／、／ｏｈ／、／ｗ／、及び／ｉｈ／と単語リンク「ＮＯＷ」とはそれぞれのソースノードが位置する同じブロック内にとどまり（基準により許容される）、音素リンク／ｚ／と単語リンク「ＩＳ」とはそれぞれブロック０からブロック１、すなわち、直接隣接するブロックまで伸びる（これも基準により許容される）ことが図１５ｂから明らかである。しかし、ブロック２まで伸びるリンクは存在しない。それは、このようなリンクはブロック０の直接隣接するブロック（すなわち、ブロック１）を越える必要があり、それは基準により許容されていないためである。
【００５７】
ブロックが上述の基準に従うように実行されるため、以下の利点が達成される。更なるデータが後に音素／単語ラティス構造へと挿入される場合、１個以上の追加のノードの挿入を伴う可能性がある。この場合、新規に挿入されたノードを「通過する」既存のリンクは、新規に挿入されたノードが既存のリンクがまたがるノードの個数のカウントに含まれる必要があるので、ノードオフセットを１つだけ増加することが要求されるであろう。例えば、新規のノードがブロック２の０．５０秒の時点に挿入された場合、０．４７秒の時点のノードから０．５５秒の時点のノードへと伸びる音素リンク／ｖ／は元の値１ではなく、ノードオフセット値２を獲得し、同様に、０．３４秒の時点のノードから０．５５秒の時点のノードへと伸びる単語リンク「ＯＦ」は、元のノードオフセット値２をノードオフセット３にまで増加するであろう。図１６ｂに示すデータストリームに関して述べると、最初００１の値を示すデータ構成要素２５２は００２の値に変更される必要があり、最初の値が００２であるデータ構成要素２５４は値を００３へと変更する必要があるだろう。
【００５８】
このような追加のノードの挿入とそれに伴うノードオフセットに対する変更の処理中、先行する既存のノードを分析し、新規に挿入されたノードを越えるのに十分大きい値のノードオフセットを有するリンクを有するのがどの既存ノードであるかを判定するために、新規に挿入されたノードの時点からラティスデータ構造をさかのぼって検索することが必要である。この基準に従ってラティスデータ構造の各ブロックを配列する利点は、分析を必要とする先行する既存のノードの個数を減少させることである。具体的には、挿入されたノードに先行する同じブロック中のノードに加えて、新規のノードが挿入されたブロックの直前の隣接するブロック中のノードのみを分析すれば良い。例えば、新規のノードがブロック２の０．５０秒の時点に挿入される場合、新規に挿入されたノードに先行するブロック２の４個の既存のノードに加えて、ブロック１の５個のノードのみを分析すれば良い。上述のブロック基準を考慮すると、ブロック０中のノードはいずれも検索する必要がない。
【００５９】
この利点は、ラティスの長さが増加し、形成されるブロックの数が減少するにつれ、ますます有益なものとなる。また、この利点は完全なラティスに新規のノードを挿入する場合に適用されるのみならず、ラティスを構築する進行中の手順にも適用される。これは、ノードが必ずしも厳密な時間順にラティスに挿入されないときに起きる可能性がある。
【００６０】
更に、リンクが隣接するブロックまで伸びることを許容する基準の選択肢は様々に異なる可能性があり、例えば、基準はリンクが最大４つ先まで伸びることを許容する可能性があることに留意すべきである。この場合、最大４つのブロックまでさかのぼって検索すれば良い。ラティスが大きい場合、特に、何百又は何千ものブロックを有するラティスの場合でも、要求される処理のレベルを低下させる観点からは重大な利点を提供する。任意の適切な数のブロックをその基準における限度として選択することが可能であり、さかのぼって検索されるブロックの数を相応に採用すれば良いことを当業者は認識するであろう。
【００６１】
本実施形態のラティスデータ構造は、更なる好適な改善を含む。この改善も単語リンク又は音素リンクの隣接するブロックへの延長に関する。特にラティスデータ構造は、各ブロックの２つの特徴的な点を指定するデータを更に含む。各ブロックに対する２つの特徴的な点は図１５ｂにおいてアルファ（α）及びベータ（β）として示される。
【００６２】
ある所定のブロックに対するベータは、前のブロックから始まるリンクの終点となるその所定のブロック中での最終のノードの時間として定義される。このため、ブロック１の場合、ブロック０において始まり、ブロック１の第１のノードより後に伸びるリンクがないので、ベータはブロック中の第１のノード（すなわち、音素リンク／ｚ／及び単語リンク「ＩＳ」の終点となるノード）である。ブロック２の場合、単語リンク「ＷＩＮＴＥＲ」はブロック１からの第３のノードまで伸びるので、ベータは第３のノードである。ラティス構造の第１のブロック、すなわち、ブロック０の場合、ブロック０まで伸びるリンクが元々存在しない。従って、このブロックに対するベータはラティスの開始より前に発生するものとして定義される。
【００６３】
所定のブロックに対するアルファは、次のブロックまで伸びるリンクの始点となるその所定のブロック中の最初のノードの時間として定義される。ブロック０の場合、２つのリンク、すなわち、単語リンク「ＩＳ」及び音素リンク／ｚ／がブロック１まで伸びる。これらのリンクのうち、単語リンク「ＩＳ」の始点となるノードの方が音素リンク／ｚ／の始点となるノードよりもブロック０において前にあるので、アルファは単語リンク「ＩＳ」の始点となるノードの位置にある。同様に、ブロック１に対するアルファは、単語リンク「ＷＩＮＴＥＲ」が始まるノードに位置する。ラティスの最終ブロック（この場合、ブロック２）の場合、アルファはブロック中の最終ノードとして特に定義されるので、以降のブロックまで伸びるリンクは元々存在しない。従って、概念的に、ベータは前のブロックと相互に作用するノードが存在するより前のブロック中の最終の点を表し、アルファは次のブロックと相互に作用するノードが存在するより後のブロック中の最初の時点を表すことが認識できるであろう。
【００６４】
各アルファ及びベータは、特定のノードの識別又は時間の観点からの指定により指定できることを当業者は認識するであろう。本実施形態では、識別は各ノードにより指定される。ラティスデータ構造内のアルファ及びベータを指定するデータは、複数の異なる方法で格納することができる。例えば、図１６ｂに示す型のデータ構成要素は、データストリーム内の関連する位置にフラグ、すなわち、マーカを含む状態で格納することができる。しかし、本実施形態では、各点はラティスデータ構造のヘッダ部分におけるルックアップテーブルに各ノードのアイデンティティを格納することにより指定される。
【００６５】
ブロックごとのアルファ及びベータの指定により、第１に、新規のノードの挿入の際のラティス中の先行するノードのノードオフセットの分析に関する利点が提供される。特に、新規のノードが所定のブロック中のベータの後の位置に挿入されるとき、所定のブロック中の先行するノードを分析するだけで良くなり、所定のブロックに先行するブロック中の各ノードを分析する必要がなくなる。これは、ベータの位置が前のブロックからリンクが伸びる最大限度を定義し、新規に挿入されたノードが所定のブロック内のベータの後に位置するために、前のブロックから新規に挿入されたノードを越えて伸びるリンクが定義上存在し得ないことが既に知られているからである。このため、先行するブロックの各ノードのいずれかを検索・分析する必要がなくなり、ブロックの平均サイズが増加するときには特に有利になる。また、新規のノードが所定のブロックのベータの前の位置に挿入される場合、先行するブロックから始まるリンクも考慮する必要が生じるが、先行するブロック中のアルファの位置又はアルファの後にあるノードのみである。これは、アルファの定義により、先行するブロックのアルファの前にある先行するブロック中の各ノードのいずれも所定のブロックまで伸びるリンクをもたないことが既に知られているという事実による。このため、処理が更に軽減され、個々のブロックのサイズが増加するときにはこの軽減がより顕著になる。更に、任意のブロック中のアルファの位置は、そのブロックの終了の方にある傾向が高いので、長いブロックの場合、先行するブロック全体を分析するのに使用されたであろう処理リソースの大半が節約される。
【００６６】
ブロックごとのアルファ及びベータの指定により、第２に、リンクは１つのブロックより後には伸びないという前述の基準に従いながら、より小さいか、あるいは、より一様に配置されたブロックを提供するように既存のラティス内で各ブロックを再定義する手順におけるアルファ及びベータの使用に関する利点が提供される。この手順では、既存のブロック内のアルファ及びベータの相対位置に従って、既存のブロックは本質的に分割される。１つのアプローチでは、所定のブロック内のベータの後でアルファが発生する場合、その所定のブロックをベータとアルファとの間のいずれかの位置で分割することによって、ブロックは２つのブロックへと分割される。同様に、ベータ及びアルファを指定するデータは、ラティスデータ構造を構築するための好適な手順中に、既存のブロックをより小さいブロックへと分割することが可能な時を判定するのに使用されるのが有利である。
【００６７】
本実施形態では、所定のノードからの最長のリンクは、図１６ａに示すように任意のノードに対するデータ構成要素のシーケンスの先頭に配置されることを先に説明した。これは、新規のノードをラティスデータ構造へと挿入する手順において有利である。この手順では、新規に挿入されたノードを越えるリンクが先行するノードから始まるか否かを判定するために先行するノードは分析される必要がある。任意のノードから伸びる最長のリンクを常にそのノードに対するデータ構成要素のシーケンス中の特定の場所（この場合、シーケンス内の最初の場所）に配置することによって、そのリンクが新規に挿入されたノードを越えないことが判明した場合、既に分析された最長リンクよりも定義上全長が短いので、そのノードに対するデータ構成要素のシーケンス中の残りのリンクのいずれかを分析する必要はない。このため、更なる処理の節約が達成される。
【００６８】
図１７から図１９を参照して、上述のラティスデータ構造を生成する好適な方法を説明する。この好適な方法では、構成データはデータ構成要素の集合へと編成され、データ構成要素の集合はラティス構造が発達するときに１度に１つずつ加えられる。
データ構成要素の各集合は以下のいずれかからなる：
（ｉ）２個の新規のノード＋これらに直接またがるリンク（既にラティスに存在するノードに結合されないラティスにノードを加える場合）、又は、
（ｉｉ）１個の新規のノード＋そのノードで終了する各リンク、又は、
（ｉｉｉ）ラティス内の既存のノード間にまたがるリンク。
【００６９】
図１７は、好適な方法で使用されるプロセスステップを表すフローチャートである。以下の図１７のプロセスステップの説明では、このステップの図１５ｂのラティスの構築への適用を実証する。この適用は、ノードが既に完全に時間順に整列されている入力データに適用されたときにこの方法がどのように機能するかを示すのに役立つ。続けて、図１５ｂのラティスデータ構造への様々なデータの追加を説明することによって、追加のノードが既存の時間順のノードシーケンスへと挿入されるときにこのプロセスステップが適用される（新規のラティスの構築に対して、あるいは、既存のラティスの変更に対してであるかに関わらず）方法を説明する。
【００７０】
概略を述べると、データ構成要素の各集合がラティスへと加えられると、種々のブロック終了、すなわち、アルファ及びベータが更新される。ブロック中のノードの個数が臨界値（この例では９）に到達すると、アルファ及びベータの位置が分析され、適宜ブロックは２つのより小さいブロックへと分割される。種々のアルファ及びベータは再度更新され、プロセスは更なるデータ構成要素の追加を伴って同様に継続する。
【００７１】
図１７に示したプロセスステップを詳細に説明する。図１８ａから図１８ｈも参照する。これらの図は図１５ｂのグラフィカルな表現形式でラティス構造の発達を示す。更に図１９ａから図１９ｈを参照する。これらの図はラティスを定義するデータストリームの構築の進行を示し、図１６ｂの形態に対応する。
【００７２】
図１７を参照すると、ステップＳ６１において、自動音声認識装置３３は第１のブロック、すなわち、ブロック０の開始を定義する。図１８ａにおいて、第１のブロックのスタータを定義するブロックマーカは符号２０２により示される。この定義はデータストリームではブロックフラグからなるデータ構成要素２４４（図１９ａ参照）の挿入により実現される。
【００７３】
ステップＳ６３において、自動音声認識装置３３はインクリメンタルカウンタｎを１に等しくなるように設定する。
【００７４】
ステップＳ６５において、自動音声認識装置３３はデータ構成要素の第１の集合をラティスデータ構造を定義するデータストリームへと挿入する。具体的には、自動音声認識装置３３はラティスの最初の２個のノードとそれらにまたがる直接的な音素リンク（この場合、音素リンク／ｎ／及び／ｍ／）とに対応するデータを収集する。自動音声認識装置３３は、単語復号器３７により２個のノード間のリンクと関連付けられているものとして識別された単語を追加的に収集する。ただし、最初の２個のノードの場合、そのような単語は識別されていない。自動音声認識装置３３は、対応するデータ構成要素をデータストリームへと挿入する。特に、図１９ａを再度参照すると、ラティス構造の第１のノードを定義し、ノードフラグからなるデータ構成要素とノードの時間を示すデータ構成要素とから構成されるデータ２６０が挿入される。続いて、音素リンク／ｎ／とノードオフセット値００１とからなるデータ構成要素を備えるデータ２６２が挿入され、その後に、音素リンク／ｍ／とノードオフセット値００１とからなるデータ構成要素を備えるデータ２６４が続く。最後に、ノードフラグからなるデータ構成要素と第２のノードの時間からなるデータ構成要素とを備えるデータ２６６が挿入される。こうして、データ構成要素の第１の集合の構成要素部分２６０、２６２、２６４、２６６の全てが挿入される。最初の２個のノードとそれらにまたがる音素リンク／ｎ／及び／ｍ／は、図１８ａにおいても見ることができる。ステップＳ６７において、自動音声認識装置３３は新規に挿入されたデータ構成要素の集合に新規のノードが含まれていたか否かを判定する。この場合の回答はｙｅｓであるので、プロセスはステップＳ６９へと進む。ステップＳ６９において、自動音声認識装置は新規のノードのいずれかが現在のデータラティス構造の終端に位置しているか否かを判定する。この場合の回答は再度ｙｅｓである。実際、図１７のフローチャートに示す方法が、この場合のように、ノードが時間順に整列されたデータからデータラティスを構築するのに使用されるとき、判定ステップＳ６７及びＳ６９に対する回答は本来常に肯定となる。これらの判定ステップは、プロセスが必要に応じてラティス内に挿入される追加のノード又はリンクを収容可能であることを示すためだけに含まれている（このような場合については後述する）。
【００７５】
この場合には、プロセスはステップＳ７１へと進む。ステップＳ７１において、自動音声認識装置３３はラティスの終端に位置する新規に挿入されたノードの直後に位置するように最終ブロックの終了を定義する。手順のこの段階ではブロックは１つしかないので、最終ブロックの終了を定義するときに実際には唯一のブロックの終了が定義される。ブロックのこの新規に定義された現在の終了は、図１８ａの項目２０３として示され、図１９ａに示すように、データストリームではブロックフラグからなるデータ構成要素２４５として実現される。
【００７６】
自動音声認識装置３３は、アルファ点及びベータ点の全てを判定する。現段階ではブロックは１つしかないので、１つのアルファ及び１つのベータのみが判定される。第１のブロック中のアルファ及びデータを判定する手順は先に説明した。結果の位置は図１８ａに示される。データストリームに関して、アルファ位置及びベータ位置は先に説明したようにヘッダデータへと入力される。
【００７７】
ステップＳ７９として、不定であるか、あるいは、リンクが直接隣接するブロックより後に伸びないという前述の基準に違反するように配置されているという意味においてアルファ値及びベータ値のいずれかが「無効」であるか否かを自動音声認識装置３３は判定する。ラティスの発達の現段階では、この判定ステップは明らかにこのような無効性が存在しないと判定するので、プロセスはステップＳ８１へと進む。ステップＳ８１において、自動音声認識装置は挿入されたばかりのノードを有するブロック中のノードの個数が所定の臨界数に到達した、あるいは、それを超えたか否かを判定する。所定の臨界数は、ブロックサイズをより小さくするか、あるいは、ブロック間隔をより一様にする目的でブロック構造が分析又は変更される前に、ブロック中に存在すべき最低ノード数を定義する目的で設定される。ブロック分割及びブロックフラグデータのデータ格納などを実行するときに必要とされるリソースの観点からすると間接費は経済的である。このため、臨界数より少ない個数のノードを含むブロックに対するブロック分割は逆効果を招きかねない。臨界数の値の選択は、考慮中のラティス又はデータファイルの特定の特徴によって決まるであろう。上述のように、本実施形態では数は９に設定される。従って、プロセスの現段階では、合計２個のノードしか挿入されていないので、判定ステップＳ８１に対する回答はｎｏである。
【００７８】
挿入されるデータ構成要素の第１の集合に対してのプロセスステップは完了した。ラティス及びデータストリームの現在の形態は図１８ａ及び図１９ａに示される。
【００７９】
手順はステップＳ８９へと進む。ステップＳ８９において、自動音声認識装置はデータ構成要素の集合を更に加えるべきであると判定するので、ステップＳ９１において、ｎの値を１だけ増分する。ステップＳ６５で開始されるプロセスステップがデータ構成要素の次の集合に対して繰り返される。この場合には、データ構成要素の次の集合は、ラティスの第３のノード及びその時間０．４１秒を指定するデータ（図１９ｂの項目２７０）と音素リンク／ｏｈ／及びノードオフセット値００１を指定するデータ（図１９ｂの項目２６８）とからなる。音素リンク／ｏｈ／及び第３のノードは、図１８ｂにおいても挿入されている様子が示される。ステップＳ７１において、最終ノードの後に位置するものとして定義されるブロックの終了２０３は、今度は図１８ｂに示すように配置され、データストリームではブロックフラグから成り且つ新規に挿入されたデータ２６８及び２７０の後に配置されるデータ構成要素２４５により実現される。現在新規の終了ノードの位置にあるアルファの新規の位置は、ステップＳ７５において判定されるように図１８ｂに示される。ステップＳ７９において、無効なアルファ又はベータが存在しないことが再度判定される。ノードの個数は３個しかない（すなわち、９より少ない）ので、このデータ構成要素の最終の集合の処理は完了する。その結果、ラティス及びデータストリームは現在図１８ｂ及び図１９ｂに示す通りとなる。
【００８０】
手順は継続し、データ構成要素の次の集合を表す第４のノード及びそのノードで終了する２つのリンク、すなわち、音素リンク／ｗ／及び単語リンク「ＮＯＷ」が挿入される。データ構成要素の前の集合に対して説明したようにＳ６５以降のプロセスステップが続く。結果として、ラティス構造は図１８ｃに示すようになり、データストリームは図１９ｃに示すようになる。図１９ｃから明らかなように、音素リンク／ｗ／に対応するデータ２７２及び最終のノードに対応するデータ２７４は、データストリームの終端にある最終ブロックフラグの直前に位置する一方、単語リンク「ＮＯＷ」に対応するデータ２７６は、リンクの始点となるノード、すなわち、第１のノードと共にデータストリームに配置される。更に、ノードオフセット値が単語リンク「ＮＯＷ」に対する値００３よりも小さい００１であるので、単語リンク「ＮＯＷ」は第１のノードを始点とするその他のリンク、すなわち、音素リンク／ｎ／及び／ｍ／の前に配置される。
第５のノード、第６のノード、第７のノード、及び第８のノードの挿入に関して変更なく上述のように手順がとられ、図１８ｄに示すラティス構造及び図１９ｄに示すデータストリームが提供される。
【００８１】
ステップＳ６５で開始される手順の次のサイクルでは、挿入されたデータ構成要素の集合は第９のノード及びそのノードで終了する音素リンク／ｗ／である。ステップＳ６７、Ｓ６９、Ｓ７１、及びＳ７５と同様の実現の後、ラティス構成は図１８ｅ−１に示すようになり、ブロックの終了２０３は新規に挿入された第９のノードの後に位置し、アルファは第９のノードの位置にある。ステップＳ７９において、自動音声認識装置はアルファ値及びベータ値の無効性は存在しないと判定し、プロセスはステップＳ８１へと進む。ここまでの手順は、データ構成要素の前の集合に対する手順と同じである。しかし、今度は、新規に挿入されたノードが唯一のブロック中のノードの総数を最大９まで増加するので、判定ステップＳ８１を実行するとき、自動音声認識装置は初めてブロック中のノードの個数が９以上であると判定する。従って、今回手順はステップＳ８３へと進む。ステップＳ８３において、自動音声認識装置はアルファがベータより大きいか否か、すなわち、アルファがブロック中でベータの後に発生するか否かを判定する。この場合には、アルファの方が大きいと判定される（実際、ベータが第１のラティスに対して定義される方法により、ラティスの第１のブロックに対しては常にアルファの方が大きい）。
【００８２】
従って、この方法の基本的なアプローチでは、アルファがベータよりも大きい場合でブロック中のノードの個数が９以上に到達するとき、ブロックは２つのブロックに分割されることを認識することができる。ノードの個数がある一定の個数に到達するまで待機する理由は、先に説明したように、間接リソースの費用のためである。アルファがベータより大きくなければならないという基準がある理由は、元のブロックの分割により形成される２つのブロックの各々が、リンクは直接隣接するブロックを超えたブロックまで伸びることが許容されないという前述の基準に従うことを確実にするためである。
【００８３】
従って、この場合には、手順はステップＳ８５へと進む。ステップＳ８５において、自動音声認識装置は図１８ｅ−１の唯一のブロックを２つのブロックへと分割する。これは、ベータとアルファとの間のいずれかの位置を指定する所望の基準に従って配置されるブロックの新規の終了２０５を定義することによって実行される。本実施形態では、基準はベータとアルファとの間に等しい間隔で配置される（ノードの個数の観点からであり、必要に応じて切り上げられる）ブロックの新規の終了を挿入することである。このため、図１８ｅ−２に示すように、第５のノードの直後にブロックの新規の終了２０５を挿入することによってブロックは分割される。これは、図１９ｅに示すように、データストリームではブロックフラグからなるデータ構成要素２９８の挿入により実現される。また、自動音声認識装置３３は、新規に形成された第２のブロックの開始時間からのオフセットとしてそのブロック中の全てのノードの時間を再計算する。第２のブロックの開始時間はラティス全体の第５のノードの時間（０．７１秒）である。このため、図１９ｅに示す結果のデータストリームは、新規に挿入されたデータ構成要素２９８、音素リンク／ｗ／に関する新規に挿入されたデータ３００、及び終了ノードに関する新規に挿入されたデータ３０２を含むようになる。更に、データ構成要素３０４、３０６、３０８、及び３１０は、時間値を新規のオフセット値へと変更している。
【００８４】
ステップＳ８７において、アルファ及びベータの更新値が自動音声認識装置により判定される。現在２つのブロックがあるので、判定対象となるのは２つのベータ及び２つのアルファである。これらのアルファ及びベータの新規の位置は図１８ｅ−２に示される。
【００８５】
ブロック１において臨界数の９個のノードに到達することなく、ラティス全体の第１０のノードから第１３のノードの挿入に対して図１７の手順が上述のようにとられる。これにより、図１８ｆに示すラティス構造及び図１９ｆに示すデータストリームが提供される。
【００８６】
挿入されるデータ構成要素の次の集合は、第１４のノードとそのノードで終了する音素リンク／ｏｈ／とからなる。このデータ構成要素の集合に対してステップＳ６５からＳ７９が実行された後の状況が図１８ｇ−１に示される。この最終のデータ構成要素の集合の挿入により第２のブロック中のノードの個数が９まで増加し、アルファはベータの後に位置する。その結果、自動音声認識装置３３はステップＳ８５を実行する。ステップＳ８５において、自動音声認識装置３３は、図１８ｇ−２に示すように、分割するブロックの第５のノードの直後にブロックの新規の終了２０７を挿入する。これは、図１９ｇに示すように、データストリームでは新規のブロックフラグからなるデータ構成要素３３０の挿入により実現される。また、自動音声認識装置３３は新規に形成された第３のブロック中のノードの調整されたオフセット時間（図１９ｇの３３４、３３６、３３８、３４０）を計算する。その後、ステップＳ８７において、自動音声認識装置はアルファ及びベータの更新値を判定する。この更新値は、第２のブロックに対する新規のアルファと第３のブロックに対する新規のベータとを提供し、双方は図１８ｇ−２に示される。
【００８７】
図１７に示す手順がデータ構成要素の追加対象の残りの３つの集合に対して繰り返されるので、図１８ｈに示すラティス構造及び図１９ｈに示すデータストリームが提供される。
【００８８】
この段階で、ステップＳ８９において、自動音声認識装置３３はデータ構成要素の挿入対象の集合が更に存在しないと判定するので、現在のラティスデータ構造は完了し、図１５ｂ及び図１６ｂに示すラティスに対応するものとなる。
隣接するブロックを越えて伸びる長いリンクを後で挿入することによる２つのブロックの結合を実証するための一例を挙げる。前述の例ではデータが完全に時間順のシーケンスに基づいて加えられたので、この状況は発生しなかった。これに対し、以下の例では、図１５ｂのラティスがこれまで説明してきた段階に到達した後で、追加のリンクがある特定の既存ノード間に挿入される必要がある。このような状況が発生する理由は幾つか存在する。可能性の１つは、ラティスがそれ以前に完了して注釈データとして使用されているが、後日変更が必要になる場合である。別の可能性は、全ての音素データが最初に処理され、その後に単語データが続く場合又はその逆の場合である。更に別の可能性は、異なる話者などの異なるサウンドトラックからのデータが別々に加えられ、単一のラティスが提供される場合である。
【００８９】
しかし、この例では、追加のリンクからなるデータ構成要素は終端において別個に処理されるが、先に時間設定されたリンクの挿入は、本質的にラティスの元の進行中の構築の一部である。なぜなら、このリンクは、音素データを第２の音声認識語彙に通すときに自動音声認識装置３３により認識される単語を構成するからである。この例では、第２の語彙はユーザがオプションで選択した専門の人名／地名の語彙からなる。このため、この例では、ステップＳ８９においてデータ構成要素の更なる集合が挿入されるべきであると判定され、ステップＳ９１においてｎの値を増分するのに続いて、ステップＳ６５においてデータが挿入される。データは単語リンク「ＥＳＴＯＮＩＡ」から成り、図２０ａに示すように、ブロック０の第４のノードからブロック２の第３のノードまで伸びる。
【００９０】
ステップＳ６７において、自動音声認識装置３３は新規のノードが挿入されていないことを認識するので、プロセスはステップＳ７５へと進む。ステップＳ７５において、自動音声認識装置３３はアルファ及びベータの更新位置を判定する。しかし、新規に挿入されたリンクはブロック０からブロック１を越えてブロック２で終了するので、直接隣接するブロックを越えるリンクの延長を禁止する前述の基準に違反すると共に、ブロック１に対して有効なアルファ及びベータを生成しない。これは、ブロック１に対するアルファが実際にはブロック０に出現する必要があり、ブロック１に対するベータがブロック２に出現する必要があることを示すことにより図２０ａにおいて表される。従って、次のステップＳ７９では、アルファ及びベータが無効であると判定される。
【００９１】
従って、手順はブロックの結合からなるステップＳ７７へと進む。どのブロックを結合すべきかを選択するのに任意の適切な基準を使用することができる。例えば、基準は最も一様な間隔で配置されたブロックの提供に基づくことも、あるいは、違反するブロックの先行するブロックとの結合からなることもできる。しかし、本実施形態では、違反するブロックを後続のブロックと結合することが選択される。すなわち、この例では、ブロック１はブロック２と結合される。
【００９２】
これは、ブロック１をブロックと分けるブロックマーカの除去により実現される。結果として、図２０ｂに示すようにブロックは２個だけになる。手順はステップＳ７５へと戻る。ステップＳ７５において、アルファ及びベータが再度判定される。アルファ及びベータの結果の位置は図２０ｂに示される。
【００９３】
ステップＳ７９において、自動音声認識装置３３はアルファ及びベータが有効であると判定するので、手順はステップＳ８１へと進む。この例では、ブロック１に１２のノードがあり、アルファがベータよりも大きいので、手順はステップＳ８５へと進む。ブロック１は前述の手順と同じ手順を使用して分割される。しかし、新規のブロック分割（すなわち、ベータとアルファとの間の各ノードの中間）をどの位置に配置するかを指定する先に使用した基準は、この例では、分割するブロックが１０個以上のノードを有するときに、可能な限り分割の結果生じる２個のブロックのうちの前のブロックは８個以下のノードを有するようにするという改善点を含む。これは、ブロック分割プロセスの非効率的な反復を回避するためである。このため、この例では図２０ｃに示すように、新規のブロックマーカは分割されるブロックの第８のノードの直後に挿入される。ステップＳ８７において、アルファ及びベータは再度判定される。これらの新規の位置は図２０ｃに示される。尚、アルファ及びベータの双方はブロック１の同じノードで発生する。この例では、ステップＳ８９において、データ構成要素の追加対象の集合が更に存在しないと判定されるので、手順は完了する。
【００９４】
図２０ａから図２０ｃを参照して説明した上述の手順では、ラティスに対する変更は先の例に対応するように図１６ｂのデータストリームに対する変更を行なうことにより実現される。特に、２つのブロックを結合するステップＳ７７は、元のブロック１及び２を分割する元のブロックフラグを含む関連するデータ構成要素２４８を除去することにより実現される。
【００９５】
図２１ａから図２１ｄを参照して、図１７のフローチャートで示される手順に従ってデータの処理を実証する更なる例を説明する。この例では、第７のノードが図１５ｃのラティスへと加えられた後で、追加のデータ構成要素が第７のノードの直後に加えられる。このため、図１７のステップＳ８９において、更なる構成要素が付加されることになるので、手順は再度増分ステップＳ９１を介して挿入ステップＳ６５へと戻る。しかし、以下の例で追加のデータ構成要素を加えるために使用される方法のステップも、元のラティス自体がどのように形成されたかに関わらず任意の適切な元のラティスを更新又は修正する独立の方法を構成する。
【００９６】
この更なる例では、図９に示すキーボード３及び音素記号表記装置７５と同じ形態のキーボード及び音素記号表記装置を介して追加のデータが加えられる。この更なる例では、音素記号表記装置の出力は自動音声認識装置３３へと接続される。ユーザはこの構成を使用してビデオデータ３１−１の特定の部分に対応させることを意図する注釈データを入力する。このようなデータは、従来技術では「メタデータ」と呼ばれることもある。ビデオデータの特定の部分は、例えば、俳優の複数のプロフィールショットであっても良く、ユーザは注釈データを使用することでこの部分を必要に応じて後日位置特定／検索できるようにすることを希望する。このため、ユーザは、「ＰＲＯＦＩＬＥ Ａ Ｂ Ｃ Ｄ Ｅ」という言葉を入力し、更に、音素リンクではなく単語リンクのみが記号表記されるように指定する。これにより、以下の追加すべきデータ構成要素が提供される：
（ｉ）第１の新規のノード、第２の新規のノード、及びこれらにまたがる単語リンク「ＰＲＯＦＩＬＥ」、
（ｉｉ）第３の新規のノード並びに新規の第２のノード及び第３のノードにまたがる単語リンク「Ａ」、
（ｉｉｉ）第４の新規のノード並びに新規の第３のノード及び第４のノードにまたがる単語リンク「Ｂ」、
（ｉｖ）第５の新規のノード並びに新規の第４のノード及び第５のノードにまたがる単語リンク「Ｃ」、
（ｖ）第６の新規のノード並びに新規の第５のノード及び第６のノードにまたがる単語リンク「Ｄ」、及び
（ｖ）第７の新規のノード並びに新規の第６のノード及び第７のノードにまたがる単語リンク「Ｅ」。
【００９７】
図１７を再度参照すると、ステップＳ６５において、先に説明したようなデータ構成要素（ｉ）が自動音声認識装置３３により図１５ｂのラティスの図２１ａに示す位置へと挿入される。ステップＳ６７において、自動音声認識装置３３は新規のノードが挿入されたことを判定する。ステップＳ６９において、自動音声認識装置は新規のノードのいずれも、ラティスの始端又は終端に挿入されていないと判定する。言い替えると、新規のノードは既存のラティス内に挿入されているので、ラティスの１個以上の既存のノードのノードオフセットを調整する必要が生じるであろう。このため、手順はステップＳ７３へと進む。ステップＳ７３において、自動音声認識装置３３は既存のノードのノードオフセットの必要な調整を実行する。ステップＳ７３では、オフセットを調整する任意の適切な方法を使用することができる。本実施形態では好適な方法が使用されるが、これについては図２２のフローチャートを参照して後述する。
【００９８】
オフセットの調整に続いて、前述の例に対して先に説明したように図１７の手順がとられ、データ構成要素（ｉｉ）の挿入のためにステップＳ６５へと戻る。データ構成要素（ｉ）に対する上述の手順が、データ構成要素（ｉｉ）及び（ｉｉｉ）に対して繰り返される。図２１ｂは、データ構成要素（ｉ）、（ｉｉ）、及び（ｉｉｉ）が挿入され、手順がステップＳ８１に到達したときに達する段階を示す。この段階において、追加のデータ構成要素の挿入中に初めて第２のブロック中のノードの個数が９に等しいと判定される。このため、ステップＳ８３において、自動音声認識装置３３はブロックを分割し、ステップＳ８７において、新規のアルファ及びベータを判定する。その結果、新規のブロック構造は図２１ｃに示すようになる。尚、新規のブロック終了を配置するために使用される基準は、ブロックの終了をアルファ自体の位置に配置することが許容されない点を除き、新規に形成された第２のブロックのサイズが最大化されるという基準である。
【００９９】
手順は同様に継続し、その結果、データ構成要素（ｉｖ）、（ｖ）、及び（ｖ）の挿入によりデータ構成要素（ｖ）の処理中にステップＳ８１へと到達する。この段階において、ラティスは図２１ｄに示す形態、すなわち、９個のノードが現在のブロック２に配置される形態をとるようになり、ステップＳ８１の結果、手順はステップＳ８３へと進む。尚、図２１ｄにおいて明らかなように、この例では、ベータがアルファの後に発生する、すなわち、ブロック２まで伸びる最長のリンクがブロック２から抜ける最初のリンクの開始を越えて伸びる状況を放棄している。ブロック２がこのような状況で分割される場合、この分割は、リンクは直接隣接するブロック以外のブロックまで伸びることが許容されないという本実施形態の基本的な基準に違反する新規のブロックを形成することを本質的に伴うであろう。このため、図１７の方法は９個のノードを有するにも関わらずブロック２の分割を許容しない。この不許可は判定ステップＳ８３の結果がアルファがベータよりも大きくないという判定になることにより実現される。この結果、手順はステップＳ８９へと進む。この例では、ステップＳ８９において、データ構成要素の追加対象の集合が更に存在しないと判定されるので、手順は終了する。
【０１００】
図２２のフローチャートを参照して、オフセットを調整するステップＳ７３を実現するための上述の好適な手順を説明する。図２２は、新規に挿入されたノードごとにとられる手順を示す。好適な方法は、各ブロック中のアルファ及びベータの位置が既知であるという事実を利用する。自動音声認識装置３３は、新規に挿入されたノードに先行する各ノードを分析し、新規に挿入されたノードの位置を越えて各ノードから伸びるリンクを判定する。このようなノードが見つかった場合、影響を受けるノードはノードオフセット値を１つだけ増加し、新規に挿入されたノードがその全長のもとに存在するという事実を受け入れる必要がある。新規に挿入されたノードが所定のブロック内のベータの後に配置される場合、ベータを越えて前のブロックから伸びるリンクは本来存在しないので、新規に挿入されたノードの前の同じ所定のブロック内にあるノードのみを分析する必要がある。また、新規に挿入されたノードが所定のブロック中のベータの前に配置される場合、その所定のブロック中の新規に挿入されたノードの前のノードに加えて、先行するブロック中のノードも分析する必要があるが、アルファに対応するノードを含む位置までしかさかのぼらない。アルファの前から新規のノードが挿入されたブロックまで伸びるリンクは本来存在しないので、先行するブロックのアルファの前に位置するノードは分析する必要がない。
【０１０１】
上述の手順は図２２に示すプロセスステップにより実現される。ステップＳ１０１において、自動音声認識装置３３は増分カウンタを値ｉ＝１に設定する。増分カウンタは、必要に応じて連続する前のノードにノード単位で繰り返し手順を適用するのを制御するために使用される。ステップＳ１０３において、挿入されたノードの１つ前の場所に位置するノードが識別される。図２１ａにおいて、単語リンク「ＰＲＯＦＩＬＥ」の始点となる新規に挿入されたノードの場合、その１つ前の位置の識別されたノードは単語リンク「ＴＨＥ」の始点となるノードである。ステップＳ１０５において、識別されたノードから伸びる全てのリンクが識別される。ここでは、単語リンク「ＴＨＥ」及び音素リンク／ｄｈ／である。自動音声認識装置３３はこれらのリンクのノードオフセット値、すなわち、単語リンク「ＴＨＥ」に対する００２及び音素リンク／ｄｈ／に対する００１を判定し、ステップＳ１０７において、これらのノードオフセット値の各々を新規の値００３及び００２へとそれぞれ１つだけ増加する。ステップＳ１０９において、新規に挿入されたノードがベータの前に配置されたか否かが判定される。この場合には、実際、ベータの後に配置されているので、ノードの分析は現在のブロックの第１のノードまでさかのぼれば良い。このため、ステップＳ１１１において、現在識別されたノード、すなわち、ノードオフセットが変更されたばかりのノードが現在のブロックの第１のノードであるか否かが判定される。この場合には、現在のブロックの第１のノードであり、オフセットを調整する必要があるノードは更に存在しないので、手順は終了する。しかし、処理すべき更なるノードが現在のブロック中に残っている場合、手順はステップＳ１１３へと続くことになる。ステップＳ１１３において、ｉの値が増分され、手順はステップＳ１０３から開始される次の先行するノードに対して繰り返される。また、上述の例において、新規に挿入されたノードが、実際、ベータの前に配置されていた場合、手順は先行するブロック中のアルファに対応するノードに至るまでの各ノードの処理が終了するまで継続されることになる。これを達成するために、挿入されたノードが、実際、ベータの前にあるときには、手順はステップＳ１１５へと進む。ステップＳ１１５において、自動音声認識装置は識別されたノードが先行するブロックのアルファの位置にあるか否かを判定する。アルファの位置にある場合、手順は完了する。アルファの位置にない場合、手順はステップＳ１１７へと進む。ステップＳ１１７において、ｉの値は増分され、手順はステップＳ１０３から繰り返される。
【０１０２】
ブロックを分割する代替の方法を説明する。所定のブロック中のノードの個数が臨界数に到達し、所定のブロックに対してアルファがベータの後に位置する場合、所定のブロック及び先行するブロックは調整され、これらの２つのブロックの代わりに３つの新規のブロックが形成される。図２３ａ及び図２３ｂを参照してこの手順をより詳細に説明する。
【０１０３】
図２３ａは、例えば、音素リンク４１２、単語リンク４１４の終了部分、及び更なる単語リンク４１６などの音素リンクにより連結されたラティス内のノードのシーケンスを示す。ノードはブロックマーカ４０２、４０４、及び４０６により複数のブロックへと分割され、ラティスのブロックｎ及びブロック（ｎ＋１）が形成される。ブロックｎ及びブロック（ｎ＋１）に対するアルファ及びベータの位置も示される。図２３ａは、音素リンク４１３及びこのリンクがまたがる２個のノードにより表されるデータが挿入された後のラティスの状態を示す。ブロック（ｎ＋１）中のノードの個数は９に到達しており、アルファはベータよりも後に位置するので、ブロックの再構成が実現される。図２３ａの２つのブロックは、図２３ｂに示すように、３つのブロック、すなわち、ブロックｎ、ブロック（ｎ＋１）、及びブロック（ｎ＋２）により置き換えられる。これは、ブロックディバイダ４０４を削除し、それをブロックｎのベータ及びブロック（ｎ＋１）のベータの直後に配置される２つの新規のブロックディバイダ４０８及び４１０と置き替えることによって実現される。その後、各ブロックに対するアルファ及びベータが再計算され、新規の位置は図２３ｂに示される。このブロックを再構成する手順により、特に一様な間隔で配置されたブロックが提供される。この再構成は、特に、所定のブロックが分割するのに必要な個数のノードを有し、アルファがベータの後に位置するときに行なわれるが、先行するブロックではベータがアルファの後に位置する。尚、これは図２３ａにおける場合である。このため、好適な実施形態では、関連の先行するブロック中でベータがアルファの後に位置するときは２つのベータ位置間に新規のブロックを形成する手順によりブロック分割が実行されるが、先行するブロック中でベータがアルファの前に位置するときはアルファとベータとの間で現在のブロックを分割する最初に説明した手順に続いて実行される。
【０１０４】
先行する段落において説明した各実施形態の代替の変形例では、２つの新規のブロックディバイダが、これらの２つのベータ位置ではなく、各ブロック中の複数のノードと比べてブロックｎのベータ及びブロック（ｎ＋１）のベータの位置に相対的に近いノードの位置に配置されても良い。
【０１０５】
上述の実施形態では、ラティスの各ノードのタイミングが、ブロック中の構成より前に、第１のノードが０．１０秒の時点で発生するように設定された共通ゼロ時間を基準として提供される。第１のブロックに対する開始時間は共通ゼロ時間と等しくなるように設定される。その他のブロックの各々に対する開始時間は、先行するブロックの最終ノードの時間である。しかし、代替実施形態では、各ノードのタイミングは絶対形式で提供されても良く、各ブロックの開始の境界を定めるブロックマーカに対して、最も近接する整数値の秒にまで切り下げられたそのブロックの第１のノードの絶対時間に対応する世界標準時（ＵＳＴ）タイムスタンプが与えられる。ＵＳＴタイムスタンプは、１９７０年１月１日以来の秒数のカウントを表す４バイト整数として実現されても良い。その後、各ブロック中のノードの時間が判定され、ブロックの開始の切り下げられたＵＳＴ時間を基準とするオフセット時間として格納される。本実施形態では、各ブロック時間は最も近接する秒に切り下げられるので、１秒未満のブロック持続時間が許容される場合、２つ以上のブロックに同じタイムスタンプ値が割り当てられる可能性がある。従って、ＵＳＴタイムスタンプが使用されるときには１秒未満のブロック持続時間は許容されない。これは、現在のブロックの分割が実行される前に現在のブロックが越えなければならない所定のブロック持続時間（例えば１秒）を指定することによって実現される。この必要条件は、現在のブロックの分割が実行される前に、現在のブロックは所定の個数より多いノードを含まなければならないという前述の必要条件と共に機能することになる。また、ＵＳＴ以外のタイムスタンプ規則を採用し、ブロックマーカ時間をブロックの最小許容持続時間よりも精密に切り下げることによって、より短いブロック持続時間が収容されても良い。
【０１０６】
上述の実施形態では、自動音声認識装置３３により音素／単語ラティス構造が判定・生成され、必要な機能を有するように構成された。当業者は容易に認識するであろうが、上述の音素／単語ラティス構造を判定・生成するための機能を備える別個のラティス作成装置と共に標準自動音声認識装置を代わりに使用することもできる。音素のシーケンスを出力する標準自動音声認識装置４０を使用する一実施形態が図２４に示される。図３に示す構成と同様に、単語復号器３７は音素データ３５から単語を識別する。図２４に示す実施形態では、識別された単語は音素データへと加えられ、音素／単語データ４２が形成される。このデータがラティス作成装置４４へと渡される。ラティス作成装置４４は上述の音素／単語ラティスを判定・生成し、このラティス構造が音素／単語注釈データ３１−３を形成する。単語のみを出力する標準自動音声認識装置を含む他の実施形態では、音素を生成するのに単語／音素辞書を使用することができ、ラティス生成装置（不図示）により単語及び音素は結合されて上述の音素／単語ラティス構造へと形成される。
【０１０７】
上述の実施形態では、音素／単語データはラティスのリンクと関連付けられた。代わりに少なくとも単語データ及び音素データのいずれかをノードと関連付けることが可能であることを当業者は認識するであろう。この場合、各ノードと関連付けられるデータは関連付けられる各単語又は音素に対する開始時間及び終了時間を含むのが好ましいであろう。
【０１０８】
以上、ノード及びリンクの未整列のリストを整列・ブロック化されたリストへと編成するための技術を説明した。この技術は、音素及び単語の未整列のリストの整列の特定の適用のために説明されたものである。しかし、この技術は他の型のデータラティスにも適用可能であることを当業者は認識するであろう。例えば、この技術を音素のみを有するラティス又は単語のみを有するラティスへと適用することができる。また、文字認識プロセスの結果、予想文字のラティスを生成する手書き認識システムから生成されたラティスへも適用することができる。この場合、ノード及びリンクは時間順に整列されていないが、整列されたラティス中の他の文字に対するページ上の文字の位置に対応する位置に文字が出現するように空間的に整列されるであろう。
【図面の簡単な説明】
【図１】
本発明の実施形態を動作させるようにプログラムされたコンピュータの概略図である。
【図２】
データファイルに付加するための音素／単語注釈データを生成するように動作可能な音素／単語注釈付け装置を示すブロック図である。
【図３】
図３が音素／単語注釈付け装置が入力ビデオデータファイルから注釈データを生成することが可能な１つの方法を示すブロック図である１つの方法を示すブロック図である。
【図４ａ】
入力ビデオデータファイルからの例示の音声ストリングに対する音素ラティスの概略図である。
【図４ｂ】
入力ビデオデータファイルからの例示の音声ストリングに対する本発明の一面を実施する単語／音素ラティスの概略ブロック図である。
【図５】
ユーザが音声質問によりデータベースから情報を検索できるようにするユーザの端末の概略ブロック図である。
【図６】
２人の話者からの例示の音声ストリングに対する１対の単語／音素ラティスの概略図である。
【図７】
ユーザからの音声信号入力から生成される注釈データを用いてデータファイルに注釈付けできるようにするユーザ端末を示す概略ブロック図である。
【図８】
データファイルに注釈付けするためにユーザにより入力された例示の発話に対して生成される音素／単語ラティス注釈データの概略図である。
【図９】
ユーザからのタイプ入力から生成された注釈データを用いてデータファイルに注釈付けできるようにするユーザ端末を示す概略ブロック図である。
【図１０】
データファイルに注釈付けするためのユーザによるタイプ入力に対して生成される音素／単語ラティス注釈データの概略図である。
【図１１】
文書注釈付けシステムの形態を示すブロック概略図である。
【図１２】
代替の文書注釈付けシステムのブロック概略図である。
【図１３】
別の文書注釈付けシステムのブロック概略図である。
【図１４】
ビデオデータファイル内に含まれるスクリプトデータから音素／単語ラティスを生成することができる方法を示す概略ブロック図である。
【図１５ａ】
ラティスの各ノードの相対タイミングを示す単語／音素ラティスの概略図である。
【図１５ｂ】
複数のブロックに分割された単語／音素ラティスの各ノードを示す概略図である。
【図１６ａ】
単語／音素ラティスの１個のノードに対応するデータの形式を示す概略図である。
【図１６ｂ】
単語／音素ラティスを定義するデータストリームを示す概略図である。
【図１７】
本発明の一実施形態に従って単語／音素ラティスを形成するプロセスを示すフローチャートである。
【図１８ａ】、
【図１８ｂ】、
【図１８ｃ】、
【図１８ｄ】、
【図１８ｅ−１】、
【図１８ｅ−２】、
【図１８ｆ】、
【図１８ｇ−１】、
【図１８ｇ−２】、
【図１８ｈ】
単語／音素ラティスの発達を示す概略図である。
【図１９ａ】、
【図１９ｂ】、
【図１９ｃ】、
【図１９ｄ】、
【図１９ｅ】、
【図１９ｆ】、
【図１９ｇ】、
【図１９ｈ】
単語／音素ラティスを定義するデータストリームの発達を示す概略図である。
【図２０ａ】、
【図２０ｂ】、
【図２０ｃ】
長いリンクの挿入時の単語／音素ラティスの更新を示す概略図である。
【図２１ａ】、
【図２１ｂ】、
【図２１ｃ】、
【図２１ｄ】
追加のノードの挿入時の単語／音素ラティスの更新を示す概略図である。
【図２２】
オフセットの調整の手順を示すフローチャートである。
【図２３ａ】、
【図２３ｂ】
ブロック分割手順の単語／音素ラティスへの適用を示す概略図である。
【図２４】
音素／単語注釈付け装置が入力ビデオデータファイルから注釈データを生成することが可能な１つの方法を示すブロック図である。
【図１】
2004510256.tif 000003
【図２】
2004510256.tif 000004
【図３】
2004510256.tif 000005
【図４ａ】
2004510256.tif 000006
【図４ｂ】
2004510256.tif 000007
【図５】
2004510256.tif 000008
【図６】
2004510256.tif 000009
【図７】
2004510256.tif 000010
【図８】
2004510256.tif 000011
【図９】
2004510256.tif 000012
【図１０】
2004510256.tif 000013
【図１１】
2004510256.tif 000014
【図１２】
2004510256.tif 000015
【図１３】
2004510256.tif 000016
【図１４】
2004510256.tif 000017
【図１５ａ】
2004510256.tif 000018
【図１５ｂ】
2004510256.tif 000019
【図１６ａ】
2004510256.tif 000020
【図１６ｂ】
2004510256.tif 000021
【図１７】
2004510256.tif 000022
【図１８ａ】
2004510256.tif 000023
【図１８ｂ】
2004510256.tif 000024
【図１８ｃ】
2004510256.tif 000025
【図１８ｄ】
2004510256.tif 000026
【図１８ｅ−１】
2004510256.tif 000027
【図１８ｅ−２】
2004510256.tif 000028
【図１８ｆ】
2004510256.tif 000029
【図１８ｇ−１】
2004510256.tif 000030
【図１８ｇ−２】
2004510256.tif 000031
【図１８ｈ】
2004510256.tif 000032
【図１９ａ】
2004510256.tif 000033
【図１９ｂ】
2004510256.tif 000034
【図１９ｃ】
2004510256.tif 000035
【図１９ｄ】
2004510256.tif 000036
【図１９ｅ】
2004510256.tif 000037
【図１９ｆ】
2004510256.tif 000038
【図１９ｇ】
2004510256.tif 000039
【図１９ｈ】
2004510256.tif 000040
【図２０ａ】
2004510256.tif 000041
【図２０ｂ】
2004510256.tif 000042
【図２０ｃ】
2004510256.tif 000043
【図２１ａ】
2004510256.tif 000044
【図２１ｂ】
2004510256.tif 000045
【図２１ｃ】
2004510256.tif 000046
【図２１ｄ】
2004510256.tif 000047
【図２２】
2004510256.tif 000048
【図２３ａ】
2004510256.tif 000049
【図２３ｂ】
2004510256.tif 000050
【図２４】
2004510256.tif 000051
【国際公開パンフレット】
2004510256.tif 000052
2004510256.tif 000053
2004510256.tif 000054
2004510256.tif 000055
2004510256.tif 000056
2004510256.tif 000057
2004510256.tif 000058
2004510256.tif 000059
2004510256.tif 000060
2004510256.tif 000061
2004510256.tif 000062
2004510256.tif 000063
2004510256.tif 000064
2004510256.tif 000065
2004510256.tif 000066
2004510256.tif 000067
2004510256.tif 000068
2004510256.tif 000069
2004510256.tif 000070
2004510256.tif 000071
2004510256.tif 000072
2004510256.tif 000073
2004510256.tif 000074
2004510256.tif 000075
2004510256.tif 000076
2004510256.tif 000077
2004510256.tif 000078
2004510256.tif 000079
2004510256.tif 000080
2004510256.tif 000081
2004510256.tif 000082
2004510256.tif 000083
2004510256.tif 000084
2004510256.tif 000085
2004510256.tif 000086
2004510256.tif 000087
2004510256.tif 000088
2004510256.tif 000089
2004510256.tif 000090
2004510256.tif 000091
2004510256.tif 000092
2004510256.tif 000093
2004510256.tif 000094
2004510256.tif 000095
2004510256.tif 000096
2004510256.tif 000097
2004510256.tif 000098
2004510256.tif 000099
2004510256.tif 000100
2004510256.tif 000101
2004510256.tif 000102
2004510256.tif 000103
2004510256.tif 000104
2004510256.tif 000105
2004510256.tif 000106
2004510256.tif 000107
2004510256.tif 000108
2004510256.tif 000109
2004510256.tif 000110
2004510256.tif 000111
2004510256.tif 000112
2004510256.tif 000113
2004510256.tif 000114
2004510256.tif 000115
2004510256.tif 000116
2004510256.tif 000117
2004510256.tif 000118
2004510256.tif 000119
2004510256.tif 000120
2004510256.tif 000121
2004510256.tif 000122
2004510256.tif 000123
2004510256.tif 000124
2004510256.tif 000125
2004510256.tif 000126
2004510256.tif 000127
2004510256.tif 000128
2004510256.tif 000129
2004510256.tif 000130
2004510256.tif 000131
2004510256.tif 000132
2004510256.tif 000133
2004510256.tif 000134
2004510256.tif 000135
2004510256.tif 000136
2004510256.tif 000137
2004510256.tif 000138
2004510256.tif 000139
2004510256.tif 000140
2004510256.tif 000141
2004510256.tif 000142
2004510256.tif 000143
2004510256.tif 000144
2004510256.tif 000145
2004510256.tif 000146
2004510256.tif 000147
2004510256.tif 000148
2004510256.tif 000149
2004510256.tif 000150
2004510256.tif 000151
2004510256.tif 000152
2004510256.tif 000153
2004510256.tif 000154
2004510256.tif 000155
2004510256.tif 000156
2004510256.tif 000157
2004510256.tif 000158
2004510256.tif 000159
2004510256.tif 000160
2004510256.tif 000161
2004510256.tif 000162
2004510256.tif 000163
2004510256.tif 000164
2004510256.tif 000165
2004510256.tif 000166
【国際公開パンフレット（コレクトバージョン）】
2004510256.tif 000167
【国際公開パンフレット（コレクトバージョン）】
2004510256.tif 000168
【国際調査報告】
2004510256.tif 000169
2004510256.tif 000170