(57)【要約】まず、写像モジュール（２２）は、２次元平面におけるラティスの写像を求める。次に、写像モジュール（２２）は、初期写像を処理して交差するリンクが存在しない平面グラフを生成する。次に、平面グラフは、リンク符号化モジュール（２４）により簡易化され、形状符号化モジュール（２６）により、ラティス構造を表現するデータが生成される。このデータ中、簡易化平面グラフは、平面グラフにより定義されるエリアの境界を規定するリンクの数を特定するシェイプ符号化データ（４２）及び平面グラフの中におけるそれらのエリアの場所を特定するデータと；リンク符号化モジュール（２４）によりラティス構造に対して実行された修正を特定するリンクリスト（４３）とにより表現される。それらの符号化データは、ラティス中の同一の部分構造が同一のデータを使用して表現され、従って、従来の技法を使用して圧縮するのに適した符号化である。
2006503318.tif 000002
【特許請求の範囲】
【請求項１】
認識データを生成する方法であって、
単位を特定するデータに係るリンクによって接続された複数のノードを含むラティス構造を定義するラティスデータを受信する受信ステップと、
前記ラティスデータにより定義される前記ラティス構造の少なくとも一部に対して、前記ラティス構造の少なくとも一部のノード及びリンクで定義される辺及び頂点を有する複数の区域を判定する判定ステップと、
前記複数の区域に対して、各区域の境界を規定するリンクの数を特定するデータと、前記ラティス構造の少なくとも一部における前記区域の位置を特定するデータとを生成する生成ステップと、
リンクに関連付けられる前記単位を特定するデータと前記複数の区域を定義するデータとを認識データとして出力する出力ステップと、
を有する方法。
【請求項２】
音声ラティスを定義するデータを生成する方法であって、
音声単位を特定するデータに関連付けられるリンクによって相互に接続された複数のノードを含む第１の音声ラティスを定義するデータを受信する受信ステップと、
音声単位を特定するデータに関連付けられるリンクによって相互に接続された複数のノードを含む平面グラフであってリンクの交差が存在せず、これらのリンク及びノードによって２次元平面における複数の区域の辺および頂点が定義される平面グラフ、を有する第２の音声ラティスを求めるべく、前記受信したデータを処理する処理ステップと、
前記平面グラフを定義するデータとして、当該平面グラフにより定義される前記複数の区域の各々の境界を規定するリンクの数と当該平面グラフにおける前記複数の区域の位置とを特定する識別データを生成する生成ステップと、
前記第２の音声ラティスを定義するデータとして、前記識別データと、前記識別データにより定義される前記平面グラフのリンクに関連付けられる音声単位を特定するデータとを出力する出力ステップと、
を有する方法。
【請求項３】
前記処理ステップは、
前記受信したデータにより定義される前記ラティス構造の２次元平面への写像を算出する写像算出ステップと、
前記算出した写像を処理して前記第２の音声ラティスを生成する写像処理ステップと、
を含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記写像処理ステップは、
前記算出した写像の中で交差するリンクであるクロスリンクの部分を特定するクロスリンク特定ステップと、
前記特定したクロスリンクのうちのいくつかを削除して前記第２の音声ラティスを生成するクロスリンク削除ステップと、
を含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記クロスリンク特定ステップは、
クロスリンクの数を特定するクロスリンクデータを生成するクロスリンクデータ生成ステップと、
前記クロスリンクデータを用いて、前記写像からクロスリンクをなくすために、前記特定したクロスリンクのうちから削除するリンクを選択するクロスリンク選択ステップと、
を含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記選択されるリンクは、前記特定したクロスリンクのうちの削除されないリンクより、多くのリンクと交差するリンクであることを特徴とする請求項５に記載の方法。
【請求項７】
前記特定したクロスリンクのうち削除されるリンクは、リンクに関する確率データに基づいて削除されるクロスリンクであることを特徴とする請求項４に記載の方法。
【請求項８】
前記写像算出ステップは、
２次元平面における前記ラティス構造の初期写像を算出する第１算出ステップと、
前記初期写像を処理して前記ラティス構造の別の写像を算出する第２算出ステップと、
を含み、
前記別の写像におけるクロスリンクの数は、前記初期写像におけるクロスリンクの数よりも少ないことを特徴とする請求項３に記載の方法。
【請求項９】
前記生成ステップは、前記区域ごとに、
当該区域の１つの頂点を定義する第１のノードを特定するデータと、
前記第１のノードから当該区域の別の頂点を定義する選択された第２のノードに至る一対のパスにあるリンクの数をそれぞれ特定する第１の数及び第２の数と、
を生成することを特徴とする請求項２に記載の方法。
【請求項１０】
前記ノードの各々は、複数の順序付けされたレイヤのうちの１つと関連付けられ、１つの区域の前記第１のノードは、１つのレイヤにおける１つの頂点を定義するノードであり、前記第２のノードは、前記第１のノードと関連する前記レイヤから、当該区域の頂点を定義する他のノードと関連するレイヤより更に遠くに隔たっているレイヤと関連する１つの頂点を定義するノードであることを特徴とする請求項９に記載の方法。
【請求項１１】
前記ラティス構造における前記ノードの各々はタイミングデータと関連付けられ、同一のタイミングデータと関連するノードは同一のレイヤと関連することを特徴とする請求項１０に記載の方法。
【請求項１２】
前記生成ステップは、前記区域ごとに、前記区域の１つの頂点を形成する１つのノードを特定するデータと、前記区域の境界を規定するリンクの総数を特定するデータと、既にデータが生成されている区域と前記区域が共有するリンクの数を特定するデータと、を生成するステップを含むことを特徴とする請求項２に記載の方法。
【請求項１３】
前記生成ステップは、
第１の選択された区域を特定するデータを生成するステップと、
前記平面グラフにより定義される残る区域を特定するデータを生成するステップと、
を含み、
前記識別データが生成される順序は、識別データが生成される区域が、先に識別データが生成された区域に隣接する区域に対応するような順序であることを特徴とする請求項２に記載の方法。
【請求項１４】
１つの区域の１つの頂点を定義するノードを特定する前記データは、先に識別データが生成された区域の頂点を特定するノードに対する、前記ノードの位置を特定するオフセット値を含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記オフセット値は、ノードのリストにおける前記ノードの相対位置を特定するオフセット値であることを特徴とする請求項１４に記載の方法。
【請求項１６】
前記リストは、環状リストであることを特徴とする請求項１５に記載の方法。
【請求項１７】
前記オフセット値は、前記リストにおける異なる方向へのオフセットを特定する正または負の数であることを特徴とする請求項１６に記載の方法。
【請求項１８】
前記リストは、識別データが既に生成された区域の境界の頂点を特定するノードのリストであることを特徴とする請求項１５に記載の方法。
【請求項１９】
前記識別データは、前記平面グラフにより定義される前記区域の各々に対して生成される前記識別データの連結であることを特徴とする請求項２に記載の方法。
【請求項２０】
前記識別データの連結は、前記区域に対して識別データが生成された順に順序付けされた連結であることを特徴とする請求項１９に記載の方法。
【請求項２１】
ラティスを生成する方法であって、
２次元平面において、交差するリンクが存在しない平面グラフにおけるノード及びリンクに対応する頂点及び辺を有する複数の区域を定義するシェイプデータを受信する第１受信ステップと、
前記シェイプデータにより定義される平面グラフのリンクを単位を特定するデータに関連付ける仮説データの複数の項目を受信する第２受信ステップと、
リンクによって接続された複数のノードを含むラティスを生成する生成ステップと、
を有し、
前記生成ステップは、
前記シェイプデータにより定義される平面グラフを算出するステップと、
前記仮説データを用いて、前記算出した平面グラフのリンクを、単位と関連付けるステップと、
を含む方法。
【請求項２２】
前記シェイプデータは、前記区域ごとに、
当該区域の１つの頂点を定義する１つのノードを特定するデータと、
前記第１のノードから当該区域の別の頂点を定義する選択された第２のノードに至る一対のパスにあるリンクの数をそれぞれ特定する第１の数及び第２の数と、
を含むことを特徴とする請求項２１に記載の方法。
【請求項２３】
前記ノードの各々は、複数の順序付けされたレイヤのうちの１つと関連付けられ、１つの区域の前記第１のノードは、１つのレイヤにおける１つの頂点を定義するノードであり、前記第２のノードは、前記第１のノードと関連する前記レイヤから、前記区域の頂点を定義する他のノードと関連するレイヤより更に遠くに隔たっているレイヤと関連する頂点を定義するノードであることを特徴とする請求項２２に記載の方法。
【請求項２４】
前記ラティス構造における前記ノードの各々はタイミングデータと関連付けられ、同一のタイミングデータと関連するノードは同一のレイヤと関連することを特徴とする請求項２３に記載の方法。
【請求項２５】
前記シェイプデータは、前記区域の各々に対して、前記区域の１つの頂点を形成する１つのノードを特定するデータと、前記区域の境界を規定するリンクの数を特定するデータと、既にデータが生成されている区域と前記区域が共有するリンクの数を特定するデータと、を含むことを特徴とする請求項２１に記載の方法。
【請求項２６】
区域の１つの頂点を定義する１つのノードを特定する前記データは、先にデータが生成された区域の頂点を特定するノードに対する、前記ノードの位置を特定するオフセット値を含むことを特徴とする請求項２２に記載の方法。
【請求項２７】
前記オフセット値は、ノードのリストにおける前記ノードの相対位置を特定するオフセット値であることを特徴とする請求項２６に記載の方法。
【請求項２８】
前記リストは、環状リストであることを特徴とする請求項２７に記載の方法。
【請求項２９】
前記オフセット値は、前記リストにおける異なる方向へのオフセットを特定する正または負の数であることを特徴とする請求項２８に記載の方法。
【請求項３０】
前記リストは、データが生成された区域の境界の頂点を特定するノードのリストであることを特徴とする請求項２７に記載の方法。
【請求項３１】
前記識別データは、前記平面グラフにより定義される前記区域の各々に対して生成される前記データの連結を含むことを特徴とする請求項２７に記載の方法。
【請求項３２】
前記識別データの連結は、前記区域に対して識別データが生成された順に順序付けされた連結であることを特徴とする請求項３１に記載の方法。
【請求項３３】
前記ラティス構造の前記少なくとも一部と、前記受信したデータにより定義されるラティス構造との差分を特定する差分データを求めるステップと、
認識データとして、リンクと関連する前記単位を特定するデータと、区域を定義する前記データと、前記差データと、を出力するステップと、
を更に有することを特徴とする請求項１に記載の認識データを生成する方法。
【請求項３４】
ラティス構造を定義するデータを生成する方法であって、
リンクによって相互に接続された複数のノードを含むラティス構造を定義するデータを受信する受信ステップと、
前記ラティス構造の２次元平面への写像と、リンクによって相互に接続された複数のノードを含む平面グラフであってリンクの交差が存在せず、これらのリンク及びノードによって２次元平面における複数の区域の辺及び頂点が定義される平面グラフ、との差分を算出すべく、前記受信したデータを処理する処理ステップと、
前記算出した差分を特定する差分データを生成する差分データ生成ステップと、
前記平面グラフにより定義される前記２次元平面の前記複数の区域に対して、前記複数の区域の各々の境界を規定するリンクの数を特定する識別データと、前記平面グラフにおける前記複数の区域の位置を特定するデータとを生成する識別データ生成ステップと、
前記ラティス構造を定義するデータとして、前記生成した識別データと前記生成した差分データとを出力する出力ステップと、
を有する方法。
【請求項３５】
前記処理ステップは、
前記ラティス構造の２次元平面への写像を算出する写像算出ステップと、
前記算出した写像のうち、交差するリンクであるクロスリンクの部分を特定するクロスリンク特定ステップと、
前記算出した写像に対して、クロスリンクを含まず、前記特定したリンクのうちのいくつかが存在しない、前記写像に対応する平面グラフを特定する平面グラフ特定ステップと、
を含み、
前記差分データは、前記算出した写像と前記特定した平面グラフとの差分を特定するデータを含むことを特徴とする請求項３４に記載の方法。
【請求項３６】
前記処理ステップは、
前記ラティス構造の２次元平面への写像を算出する写像算出ステップと、
前記算出した写像のうち、交差するリンクであるクロスリンクの部分を特定するクロスリンク特定ステップと、
前記算出した写像から、前記クロスリンクのうちのいくつかを特定するデータを削除することにより、クロスリンクを含まない平面グラフを生成するステップと、
を含み、
前記差分データは、前記ラティス構造の前記算出した写像から削除されたリンクを特定するデータを含むことを特徴とする請求項３４に記載の方法。
【請求項３７】
前記クロスリンク特定ステップは、
クロスリンクの数を特定するクロスリンクデータを生成するクロスリンクデータ生成ステップと、
前記クロスリンクデータを用いて、前記写像からクロスリンクをなくすために、前記特定したクロスリンクのうちから削除するリンクを選択するクロスリンク選択ステップと、
を含むことを特徴とする請求項３５に記載の方法。
【請求項３８】
前記選択されるリンクは、前記特定したクロスリンクのうちの削除されないリンクより、多くのリンクと交差するリンクであることを特徴とする請求項３７に記載の方法。
【請求項３９】
前記写像算出ステップは、
２次元平面における前記ラティス構造の初期写像を算出する第１算出ステップと、
前記初期写像を処理して前記ラティス構造の別の写像を算出する第２算出ステップと、
を含み、
前記別の写像におけるクロスリンクの数は、前記初期写像におけるクロスリンクの数よりも少ないことを特徴とする請求項３５に記載の方法。
【請求項４０】
前記受信したデータにより定義される前記ラティス構造の前記ノードの各々を、一体となってタイミングのシーケンスを定義するタイミングデータの複数の項目のうちの１つの項目と関連付けるデータを受信するステップと、
同一のタイミングデータと関連付けられたノードを特定するステップと、
第１のタイミングが単一のノードと関連するか否かを判定するステップと、
前記第１のタイミングが単一のノードと関連しない場合、前記シーケンスにおける、より早いタイミングと、当該より早いタイミングと関連付けられるダミーノードとを生成し、かつ、前記生成したダミーノードと、前記第１のタイミングと関連付けられたノードとの間にリンクを生成することにより、前記ラティス構造の前記算出した写像を修正する写像修正ステップと、
更に有し、
前記差分データは、追加されるノードを特定するデータを含むことを特徴とする請求項３５に記載の方法。
【請求項４１】
前記写像修正ステップは、
最終タイミングが単一のノードと関連するか否かを判定するステップと、
前記最終タイミングが単一のノードと関連しない場合、前記シーケンスにおける、より遅いタイミングと、当該より遅いタイミングと関連付けられるダミーノードと、前記生成したダミーノードと、前記最終タイミングと関連付けられたノードとの間のリンクと、を生成するステップと、
を更に含み、
前記差分データは、前記追加されるノードを特定するデータを含むことを特徴とする請求項４０に記載の方法。
【請求項４２】
前記写像修正ステップは、
前記タイミングのシーケンスにおいて隣接しないタイミングと関連付けられたノードの間のリンクを、前記削除されたリンクにより特定される前記ノードの前記タイミングの間の、前記シーケンス中の前記タイミングの各々に対してタイミングデータと関連付けられるダミーノードを接続する一連のリンクと置き換えるステップを更に含み、
前記差分データは、前記ラティス構造の前記修正された部分を特定するデータを含むことを特徴とする請求項４０に記載の方法。
【請求項４３】
前記写像修正ステップは、
前記タイミングのシーケンスのうちで最も早いタイミング及び最も遅いタイミングと関連付けられないノードに対して、前記ノードの各々が、他のリンクと交差しないリンクにより、前記写像ラティス中の開始ノード及び終了ノードとして識別されるか否かを判定するステップと、
ノードが開始ノード及び終了ノードのどちらにも識別されない場合、前記ノードの全てがリンクの開始ノード及び終了ノードの双方として識別されるように前記写像に別のリンクを追加するステップと、
を更に含み、
前記差分データは、前記追加されるリンクを特定するデータを含むことを特徴とする請求項４０に記載の方法。
【請求項４４】
前記写像修正ステップは、
前記ラティス構造のうちで、ダミーノードを含まない１つ以上のパスを介して、前記タイミングのシーケンスにおける第１のタイミングと関連付けられたノードにリンクされたノードを判定するステップと、
前記タイミングのシーケンスにおける後続するタイミングと関連付けられたノードに対して、いずれかのノードが前記判定されたグループにあるか否かを判定し、かつ前記ノードに対して、前記ノードを、より早いタイミングと関連付けられた、前記判定されたグループの中のノードに接続するダミーノードを含むパスを特定するステップと、
前記特定したパスに含まれないダミーノードを介するノードの間のパスを、前記ノードの間のリンクと置き換えるステップと、
を更に含み、
前記差分データは、残るダミーノードを特定するデータを含むことを特徴とする請求項４０に記載の方法。
【請求項４５】
前記算出した写像のうちで、複数対のノードの間のパスを定義し、前記ラティス構造の他のどのノードにもリンクされない部分を特定することにより、前記算出した写像を修正するステップと、
前記部分を、前記対のノードの間の単一のリンクを特定するデータと置き換えるステップと、
前記対のノードの間の前記リンクを、前記削除された部分にあるノード及びリンクを特定するデータと関連付けるステップと、
を更に有し、
前記差分データは、前記リンクと関連付けられたデータを含むことを特徴とする請求項３５に記載の方法。
【請求項４６】
前記部分は、複数対のノードの間の他のノードを介するパスを含み、前記他のノードは、単一のリンクの開始ノード及び単一のリンクの終了ノードとして識別され、生成されたリンクと関連付けられる前記データは、前記ノードの削除を識別するデータと、前記ノードを開始ノード及び終了ノードとして有する削除されたリンクと関連するデータとを含むことを特徴とする請求項４５に記載の方法。
【請求項４７】
前記部分は、複数対のノードの間の、前記対のノードの間の一対のリンクを含むパスを含み、前記ノードの間で生成されるリンクと関連付けられる前記データは、前記対のリンクの併合を識別するデータと、削除されたリンクと関連するデータとを含むことを特徴とする請求項４５に記載の方法。
【請求項４８】
一対の併合されたリンクと置き換えられるリンクと関連する前記データは、一対のリンクの併合を識別するデータと、前記併合されたリンクと関連するデータの連結とを含み、前記データは、前記リンクの各々と関連するデータの量に応じて定められる順序で連結されることを特徴とする請求項４７に記載の方法。
【請求項４９】
前記識別データ生成ステップは、
前記区域の１つの頂点を形成する１つのノードを特定するデータと、
前記第１のノードから、前記区域の別の頂点を定義する選択された第２のノードに至る一対のパスにあるリンクの数をそれぞれ特定する第１の数及び第２の数と、
を含むことを特徴とする請求項３４に記載の方法。
【請求項５０】
前記ノードの各々は、複数の順序付けされたレイヤのうちの１つと関連付けられ、１つの区域の前記第１のノードは、１つのレイヤにおける１つの頂点を定義するノードであり、前記第２のノードは、前記第１のノードと関連する前記レイヤから、前記区域の頂点を定義する他のノードと関連するレイヤより更に遠くに隔たっているレイヤと関連する頂点を定義するノードであることを特徴とする請求項４９に記載の方法。
【請求項５１】
前記ラティス構造における前記ノードの各々は、タイミングデータと関連付けられ、同一のタイミングデータと関連するノードは、同一のレイヤと関連することを特徴とする請求項５０に記載の方法。
【請求項５２】
前記識別データ生成ステップは、前記区域の１つの頂点を形成する１つのノードを識別するデータと、前記区域の境界を規定するリンクの総数を識別するデータと、既にデータが生成された区域と前記区域が共有するリンクの数を識別するデータとを含むことを特徴とする請求項３４に記載の方法。
【請求項５３】
前記識別データ生成ステップは、
第１の選択された区域を特定するデータを生成するステップと、
前記平面グラフにより定義される残る区域を特定するデータを生成するステップと、
を含み、
前記識別データが生成される順序は、識別データが生成される区域が、先に識別データが生成された区域に隣接する区域に対応するような順序であることを特徴とする請求項３４に記載の方法。
【請求項５４】
１つの区域の１つの頂点を形成する１つのノードを特定する前記データは、先に識別データが生成された区域の１つの頂点を特定するノードに対する、前記ノードの位置を特定するオフセット値を含むことを特徴とする請求項５３に記載の方法。
【請求項５５】
前記オフセット値は、ノードのリストにおける前記ノードの相対位置を特定するオフセット値であることを特徴とする請求項５４に記載の方法。
【請求項５６】
前記リストは、環状リストであることを特徴とする請求項５５に記載の方法。
【請求項５７】
前記オフセット値は、前記リストにおける異なる方向へのオフセットを特定する正または負の数であることを特徴とする請求項５５に記載の方法。
【請求項５８】
前記リストは、識別データが既に生成された区域の境界の頂点を特定するノードのリストであることを特徴とする請求項５５に記載の方法。
【請求項５９】
前記識別データは、前記平面グラフにより定義される前記区域の各々に対して生成された前記識別データの連結であることを特徴とする請求項３４に記載の方法。
【請求項６０】
前記識別データの連結は、前記区域に対して識別データが生成された順序で順序付けされた連結であることを特徴とする請求項５９に記載の方法。
【請求項６１】
前記差分データは、平面グラフのリンクと関連付けられた前記生成データの連結であることを特徴とする請求項３４に記載の方法。
【請求項６２】
認識データを生成する装置であって、
単位を特定するデータに係るリンクによって接続された複数のノードを含むラティス構造を定義するラティスデータを受信する受信ユニットと、
前記受信ユニットにより受信されたラティスデータにより定義される前記ラティス構造の少なくとも一部に対して、前記ラティス構造の少なくとも一部のノード及びリンクで定義される辺及び頂点を有する複数の区域を判定する判定ユニットと、
前記判定ユニットにより判定された前記複数の区域に対して、各区域の境界を規定するリンクの数を特定するデータと、前記ラティス構造の少なくとも一部における前記区域の場所を特定するデータを生成する生成ユニットと、
リンクに関連付けられる前記単位を特定するデータと前記複数の区域を定義するデータとを認識データとして出力する出力ユニットと、
を有する装置。
【請求項６３】
音声ラティスを定義するデータを生成する装置であって、
音声単位を特定するデータに関連付けられるリンクによって相互に接続された複数のノードを含む第１の音声ラティスを定義するデータを受信する受信ユニットと、
音声単位を特定するデータに関連付けられるリンクによって相互に接続された複数のノードを含む平面グラフであってリンクの交差が存在せず、これらのリンク及びノードによって２次元平面における複数の区域の辺および頂点が定義される平面グラフ、を有する第２の音声ラティスを求めるべく、前記受信ユニットにより受信されたデータを処理する処理ユニットと、
前記処理ユニットにより算出される平面グラフを定義するデータとして、当該平面グラフにより定義される前記複数の区域の各々の境界を規定するリンクの数と当該平面グラフにおける前記複数の区域の位置とを特定する識別データを生成する生成ユニットと、
前記第２の音声ラティスを定義するデータとして、前記生成ユニットにより生成された前記識別データと、前記受信ユニットにより受信された前記識別データにより定義される前記平面グラフのリンクに関連付けられる音声単位を特定するデータとを出力する出力ユニットと、
を有する装置。
【請求項６４】
前記処理ユニットは、
前記受信ユニットにより受信されたデータにより定義されるラティス構造の２次元平面への写像を算出する写像ユニットと、
前記算出された写像を処理して前記第２の音声ラティスを生成する写像プロセッサと、
を含むことを特徴とする請求項６３に記載の装置。
【請求項６５】
前記写像プロセッサは、
前記算出された写像の中で交差するリンクであるクロスリンクを特定し、
前記特定したクロスリンクのうちのいくつかを削除して前記第２の音声ラティスを生成する
ことを特徴とする請求項６４に記載の装置。
【請求項６６】
前記写像プロセッサは、
クロスリンクの数を特定するクロスリンクデータを生成し、
前記クロスリンクデータを用いて、前記写像からクロスリンクをなくすために、前記特定したクロスリンクのうちから削除するリンクを選択する
ことにより、前記算出された写像中のクロスリンクを特定することを特徴とする請求項６５に記載の装置。
【請求項６７】
前記選択されるリンクは、前記特定したクロスリンクのうちの削除されないリンクより、多くのリンクと交差するリンクであることを特徴とする請求項６６に記載の装置。
【請求項６８】
前記受信ユニットは、前記ラティスにおけるリンクと確率とを関連付ける確率データを受信し、
前記写像プロセッサは、前記リンクと関連付けられる確率データに基づいて、リンクを削除する
ことを特徴とする請求項６５に記載の装置。
【請求項６９】
前記写像ユニットは、
２次元平面における前記ラティス構造の初期写像を算出するとともに、
前記初期写像を処理して前記ラティス構造の別の写像を算出し、
前記別の写像におけるクロスリンクの数は、前記初期写像におけるクロスリンクの数より少ないことを特徴とする請求項６４に記載の装置。
【請求項７０】
前記生成ユニットは、前記区域ごとに、
当該区域の１つの頂点を形成する１つのノードを特定するデータと、
前記第１のノードから当該区域の別の頂点を定義する選択された第２のノードに至る一対のパスにあるリンクの数をそれぞれ特定する第１の数及び第２の数と、
を含む識別データを生成することを特徴とする請求項６３に記載の装置。
【請求項７１】
前記処理ユニットは、前記ノードの各々を複数の順序付けされたレイヤのうちの１つと関連付けを行うよう動作し、
前記生成ユニットは、識別データを生成するよう動作し、
前記生成ユニットは、前記識別データにおいて、１つの区域の前記第１のノードが、１つのレイヤにおける１つの頂点を定義するノードであり、前記第２のノードが、前記第１のノードと関連する前記レイヤから、前記区域の頂点を定義する他のノードと関連するレイヤより更に遠くに隔たっているレイヤと関連する頂点を定義するノードであるような識別データを生成するよう動作する
ことを特徴とする請求項７０に記載の装置。
【請求項７２】
前記受信ユニットは、前記ラティス構造における前記ノードの各々をタイミングデータと関連付けるデータを受信するよう動作し、
同一のタイミングデータと関連するノードは、同一のレイヤと関連することを特徴とする請求項７１に記載の装置。
【請求項７３】
前記生成ユニットは、区域ごとに識別データを生成するよう動作し、
前記識別データは、前記区域の１つの頂点を形成する１つのノードを特定するデータと、前記区域の境界を規定するリンクの総数を特定するデータと、既にデータが生成された区域と前記区域が共有するリンクの数を特定するデータとを含む
ことを特徴とする請求項６３に記載の装置。
【請求項７４】
前記生成ユニットは、
第１の選択された区域を特定するデータを生成するとともに、
前記平面グラフにより定義される残りの区域を特定するデータを生成するよう動作し、
前記識別データが生成される順序は、識別データが生成される区域が、先に識別データが生成された区域に隣接する区域に対応するような順序であることを特徴とする請求項６３に記載の装置。
【請求項７５】
前記生成ユニットは、区域ごとに、当該区域の１つの頂点を定義する１つのノードを特定するデータを生成するよう動作し、
前記データは、先に識別データが生成された区域の１つの頂点を特定するノードに対する、前記ノードの位置を特定するオフセット値を含むことを特徴とする請求項７４に記載の装置。
【請求項７６】
前記オフセット値は、ノードのリストにおける前記ノードの相対位置を特定するオフセット値であることを特徴とする請求項７５に記載の装置。
【請求項７７】
前記リストは、環状リストであることを特徴とする請求項７６に記載の装置。
【請求項７８】
前記オフセット値は、前記リストにおける異なる方向へのオフセットを特定する正または負の数であることを特徴とする請求項７７に記載の装置。
【請求項７９】
前記リストは、識別データが生成された区域の境界の頂点を特定するノードのリストであることを特徴とする請求項７６に記載の装置。
【請求項８０】
前記生成ユニットは、前記平面グラフにより定義される前記区域の各々に対して生成される前記識別データの連結を含む識別データを生成することを特徴とする請求項６３に記載の装置。
【請求項８１】
前記識別データの連結は、前記区域に対して識別データが生成された順序で順序付けされた連結であることを特徴とする請求項８０に記載の装置。
【請求項８２】
前記出力ユニットにより出力される前記ラティス構造を定義する出力データを圧縮する圧縮ユニットと、
前記圧縮ユニットにより生成された圧縮データを送信する送信ユニットと、
を更に有することを特徴とする請求項６３に記載の装置。
【請求項８３】
前記送信ユニットにより送信された圧縮データを受信して伸長する伸長ユニットと、
前記伸長ユニットにより伸長された識別データ及び差分データを処理して前記定義されたラティス構造を判定する再生ユニットと、
を更に有することを特徴とする請求項８２に記載の装置。
【請求項８４】
前記再生ユニットは、
前記識別データを用いて平面グラフを生成するとともに、
音声単位を識別するデータを用いて、前記平面グラフのリンクを、音声単位を識別する前記データと関連付けるように動作することを特徴とする請求項８３に記載の装置。
【請求項８５】
ラティスを生成する装置であって、
２次元平面において、交差するリンクが存在しない平面グラフにおけるノード及びリンクに対応する頂点及び辺を有する複数の区域を定義するシェイプデータと、前記シェイプデータにより定義される平面グラフのリンクを単位を特定するデータに関連付ける仮説データの複数の項目と、を受信する受信ユニットと、
リンクを介して接続された複数のノードを含むラティスを生成する生成ユニットと、
を有し、
前記生成ユニットは、
前記受信ユニットにより受信された前記シェイプデータにより定義される平面グラフを算出するとともに、
前記受信ユニットにより受信された前記仮説データを用いて、前記算出された平面グラフのリンクを、単位と関連付けることにより前記ラティスを生成する
ことを特徴とする装置。
【請求項８６】
前記受信ユニットは、前記区域の各々に対して、
当該区域の１つの頂点を形成する１つのノードを特定するデータと、
前記第１のノードから当該区域の別の頂点を定義する選択された第２のノードに至る一対のパスにあるリンクの数をそれぞれ識別する第１の数及び第２の数と、
を含むシェイプデータを受信することを特徴とする請求項８５に記載の装置。
【請求項８７】
前記受信ユニットは、前記ノードの各々を、複数の順序付けされたレイヤのうちの１つと関連付けるデータを受信するよう動作し、
１つの区域の前記第１のノードは、１つのレイヤにおける１つの頂点を定義するノードであり、前記第２のノードは、前記第１のノードと関連する前記レイヤから、前記区域の頂点を定義する他のノードと関連するレイヤより更に遠くに隔たっているレイヤと関連する頂点を定義するノードであることを特徴とする請求項８６に記載の装置。
【請求項８８】
前記受信ユニットは、前記ラティス構造における前記ノードの各々をタイミングデータと関連付けるデータを受信するよう動作し、
同一のタイミングデータと関連するノードは、同一のレイヤと関連することを特徴とする請求項８７に記載の装置。
【請求項８９】
前記受信ユニットは、前記区域の各々に対して、前記区域の１つの頂点を形成する１つのノードを特定するデータと、前記区域の境界を規定するリンクの総数を特定するデータと、既にデータが生成されている区域と前記区域が共有するリンクの数を特定するデータとを含むシェイプデータを受信するように構成されていることを特徴とする請求項８５に記載の装置。
【請求項９０】
前記受信ユニットは、１つの区域の１つの頂点を定義する１つのノードを特定するデータを受信するように動作可能であり、
前記データは、先にデータが生成された区域の頂点を特定するノードに対する、前記ノードの位置を特定するオフセット値を含むことを特徴とする請求項８６に記載の装置。
【請求項９１】
前記オフセット値は、ノードのリストにおける前記ノードの相対位置を特定するオフセット値であることを特徴とする請求項９０に記載の装置。
【請求項９２】
前記リストは、環状リストであることを特徴とする請求項９１に記載の装置。
【請求項９３】
前記オフセット値は、前記リストにおける異なる方向へのオフセットを識別する正または負の数であることを特徴とする請求項９２に記載の装置。
【請求項９４】
前記リストは、データが生成された区域の境界の頂点を特定するノードのリストであることを特徴とする請求項９１に記載の装置。
【請求項９５】
前記受信ユニットは、前記平面グラフにより定義される前記区域の各々を表す前記データの連結である識別データを受信することを特徴とする請求項８５に記載の装置。
【請求項９６】
前記識別データの連結は、前記区域に対して識別データが生成された順序で順序付けされた連結であることを特徴とする請求項９５に記載の装置。
【請求項９７】
前記ラティス構造の前記少なくとも一部と、前記受信されたデータにより定義されるラティス構造との差分を特定する差分データを判定する差判定ユニットを更に有し、
前記出力ユニットは、認識データとして、リンクと関連付けられる前記単位を識別するデータと、前記区域を定義するデータと、前記差分データとを出力する
ことを特徴とする請求項６２に記載の認識データを生成する装置。
【請求項９８】
ラティス構造を定義するデータを生成する装置であって、
リンクにより相互に接続された複数のノードを含むラティス構造を定義するデータを受信する受信ユニットと、
前記ラティス構造の２次元平面への写像と、リンクによって相互に接続された複数のノードを含む平面グラフであってリンクの交差が存在せず、これらのリンク及びノードによって２次元平面における複数の区域の辺及び頂点が定義される平面グラフ、との差分を算出すべく、前記受信ユニットにより受信されたたデータを処理する処理ユニットと、
差分を特定する差分データを生成する差分生成ユニットと、
前記平面グラフにより定義される前記２次元平面の前記複数の区域に対して、前記複数の区域の各々の境界を規定するリンクの数を特定する識別データと、前記平面グラフの中における前記複数の区域の位置を特定するデータとを生成するシェイプ符号化ユニットと、
前記ラティス構造を定義するデータとして、前記シェイプ符号化ユニットにより生成された前記識別データと前記差分生成ユニットにより生成された前記差分データとを出力する出力ユニットと、
を有する装置。
【請求項９９】
前記処理ユニットは、
前記受信ユニットにより受信されたデータにより定義されるラティス構造の２次元平面への写像を算出する写像ユニットと、
前記算出された写像のうち、交差するリンクであるクロスリンクの部分を特定するとともに、前記写像ユニットにより算出された写像に対して、クロスリンクを含まず、前記特定されたリンクのうちのいくつかが存在しない、前記写像に対応する平面グラフを特定する平面グラフ特定ユニットと、
を含み、
前記差分生成ユニットにより生成される前記差分データは、前記写像と、前記平面グラフにより特定される前記平面グラフとの差分を特定するデータを含むことを特徴とする請求項９８に記載の装置。
【請求項１００】
前記処理ユニットは、
前記受信ユニットにより受信されたデータにより定義されるラティス構造の、２次元平面への写像を算出する写像ユニットと、
前記写像により算出された写像のうち、交差するリンクであるクロスリンクの部分を特定するとともに、前記算出された写像から、前記クロスリンクのうちのいくつかを特定するデータを削除することにより、クロスリンクを含まない平面グラフを生成する平面グラフ特定ユニットと、
を含み、
前記差分生成ユニットにより生成される前記差分データは、前記平面グラフ特定ユニットにより、前記ラティス構造の前記算出された写像から削除されたリンクを特定するデータを含むことを特徴とする請求項９８に記載の装置。
【請求項１０１】
前記平面グラフ特定ユニットは、
クロスリンクの数を特定するクロスリンクデータを生成するクロスリンク特定ユニットと、
前記クロスリンクデータを用いて、前記写像からクロスリンクをなくすために、前記特定したクロスリンクのうちから削除するリンクを選択するリンク選択ユニットと、
を含むことを特徴とする請求項９９に記載の装置。
【請求項１０２】
前記リンク選択ユニットは、前記特定したクロスリンクのうちの削除されないリンクより、多くのリンクと交差するリンクを、削除するリンクとして選択することを特徴とする請求項１０１記載の装置。
【請求項１０３】
前記写像ユニットは、
２次元平面における前記ラティス構造の初期写像を算出する写像算出ユニットと、
前記写像算出ユニットにより算出された初期写像を処理して前記ラティス構造の別の写像を算出する写像プロセッサと、
を含み、
前記別の写像におけるクロスリンクの数は、前記初期写像におけるクロスリンクの数より少ないことを特徴とする請求項９９記載の装置。
【請求項１０４】
前記受信ユニットは、
前記受信されたデータにより定義される前記ラティス構造の前記ノードの各々を、一体となってタイミングのシーケンスを定義するタイミングデータの項目のうちの１つの項目と関連付けるデータを受信するよう動作し、
前記装置は、
同一のタイミングデータと関連するノードを特定するレイヤ規定ユニットと、
第１のタイミングが単一のノードと関連するか否かを判定し、前記第１のタイミングが単一のノードと関連しない場合、前記シーケンスにおける、より早いタイミングと、当該より早いタイミングと関連するダミーノードとを生成し、かつ、前記生成されたダミーノードと、前記第１のタイミングと関連するノードとの間にリンクを生成することにより、前記写像ユニットにより算出された写像を修正する修正ユニットと、
を更に有し、
前記差分生成ユニットは、追加されるノードを特定するデータを含む差分データを生成することを特徴とする請求項９９に記載の装置。
【請求項１０５】
前記修正ユニットは、
最終タイミングが単一のノードと関連するか否かを判定し、
前記タイミングが単一のノードと関連しない場合、前記シーケンスにおける、より遅いタイミングと、当該より遅いタイミングと関連するダミーノードと、前記生成されたダミーノードと、前記最終タイミングと関連するノードとの間のリンクと、を生成する
ことにより、前記写像ユニットにより判定された写像を修正し、
前記差分生成ユニットは、前記追加されるノードを識別するデータを含む差分データを生成する
ことを特徴とする請求項１０４に記載の装置。
【請求項１０６】
前記修正ユニットは、
前記タイミングのシーケンスにおいて隣接しないタイミングと関連するノードとの間のリンクを、前記シーケンスにおいて、前記削除されたリンクにより特定される前記ノードの前記タイミングの間にある前記タイミングの各々に対するタイミングデータと関連するダミーノードを接続する一連のリンクと置き換えることにより、前記写像ユニットにより算出された写像を修正し、
前記差分生成ユニットは、前記ラティス構造の前記修正された部分を特定するデータを含む差分データを生成する
ことを特徴とする請求項１０４に記載の装置。
【請求項１０７】
前記修正ユニットは、前記タイミングのシーケンスの最も早いタイミング及び最も遅いタイミングと関連しないノードに対して、前記ノードの各々が、前記写像ラティスにおいて、他のリンクと交差しないリンクにより、リンクの開始ノード及び終了ノードとして識別されるか否かを判定するとともに、ノードが開始ノード及び終了ノードのどちらにも識別されない場合、前記ノードの全てが１つのリンクの開始ノード及び終了ノードの双方として識別されるように前記写像に別のリンクを追加することにより、前記写像ユニットにより算出された写像を修正し、
前記差分生成ユニットは、前記追加されるリンクを識別するデータを含む差分データを生成する
ことを特徴とする請求項１０４に記載の装置。
【請求項１０８】
前記修正ユニットは、
ダミーノードを全く含まない１つ以上のパスを介して、前記タイミングのシーケンスにおける第１のタイミングと関連するノードにリンクされた前記ラティス構造のノードを判定し、
前記タイミングのシーケンスにおける後続するタイミングと関連するノードに対して、いずれかのノードが前記判定されたグループに入っていないかを判定し、前記ノードに対して、前記ノードを、前記判定されたグループの中の、より早いタイミングと関連するノードに接続するダミーノードを含むパスを特定し、かつ、
前記特定されたパスに含まれないダミーノードを介するノード間のパスを、前記ノード間のリンクと置き換えることにより、前記写像ユニットにより判定された写像を修正し、
前記差分生成ユニットは、残るダミーノードを識別するデータを含む差分データを生成する
ことを特徴とする請求項１０４に記載の装置。
【請求項１０９】
前記写像のうちで、複数対のノードの間のパスを定義し、前記ラティス構造の他のどのノードにもリンクされない部分を特定し、
前記部分を、前記対のノードの間の単一のリンクを特定するデータと置き換え、かつ、
前記対のノードの間の前記リンクを、前記削除された部分にあるノード及びリンクを特定するデータと関連付けることにより、前記判定された写像を修正するリンク符号化ユニットを更に有し、
前記差分生成ユニットは、リンクと関連付けられた前記データを含む差分データを生成する
ことを特徴とする請求項９９に記載の装置。
【請求項１１０】
前記リンク符号化ユニットは、単一のリンクの開始ノードとして識別され、かつ単一のリンクの終了ノードとして識別される他のノードを介する、複数対のノードの間のパスを含む部分を識別するように動作可能であり、
生成されるリンクと関連付けられる前記データは、前記ノードの除去を識別するデータと、前記ノードを開始ノード及び終了ノードとして有する、削除されたリンクと関連するデータとを含む
ことを特徴とする請求項１０９に記載の装置。
【請求項１１１】
前記リンク符号化ユニットは、前記対のノードの間の一対のリンクを含む、複数対のノードの間のパスを含む部分を識別するように動作可能であり、
前記ノードの間に生成されるリンクと関連付けられる前記データは、前記対のリンクの併合を識別するデータと、削除されたリンクと関連するデータとを含む
ことを特徴とする請求項１０９に記載の装置。
【請求項１１２】
前記リンク符号化ユニットは、一対の併合されたリンクと置き換えられるリンクと、一対のリンクの併合を識別するデータ及び前記併合されたリンクと関連するデータの連結を含むデータを関連付けるように動作可能であり、
前記データは、前記リンクの各々と関連するデータの量に応じて定められる順序で連結される
ことを特徴とする請求項１１１に記載の装置。
【請求項１１３】
前記シェイプ符号化ユニットは、区域ごとに、
当該区域の１つの頂点を形成する１つのノードを識別するデータと、
前記第１のノードから、当該区域の別の頂点を定義する選択された第２のノードに至る一対のパスにあるリンクの数をそれぞれ特定する第１の数及び第２の数と、
を含む識別データを生成することを特徴とする請求項９８に記載の装置。
【請求項１１４】
前記処理ユニットは、前記ノードの各々を、複数の順序付けされたレイヤのうちの１つと関連付けるように動作可能であり、
１つの区域の前記第１のノードは、１つのレイヤにおける１つの頂点を定義するノードであり、前記第２のノードは、前記第１のノードと関連する前記レイヤから、前記区域の頂点を定義する他のノードと関連するレイヤより更に遠く隔たっているレイヤと関連する頂点を定義するノードである
ことを特徴とする請求項１１３に記載の装置。
【請求項１１５】
前記受信ユニットは、前記ラティス構造における前記ノードの各々をタイミングデータと関連付けるためのデータを受信するよう動作し、
同一のタイミングデータと関連するノードは、前記処理ユニットにより、同一のレイヤと関連付けられる
ことを特徴とする請求項１１４に記載の装置。
【請求項１１６】
前記シェイプ符号化ユニットは、区域ごとに、前記区域の１つの頂点を形成する１つのノードを特定するデータと、前記区域の境界を規定するリンクの総数を特定するデータと、既にデータが生成された区域と前記区域が共有するリンクの数を特定するデータとを含む識別データを生成することを特徴とする請求項９８に記載の装置。
【請求項１１７】
前記シェイプ符号化ユニットは、第１の選択された区域を特定するデータと、前記平面グラフにより定義される残る区域を特定するデータとを生成するよう動作し、
前記識別データが生成される順序は、識別データが生成される区域が、先に識別データが生成された区域に隣接する区域に対応するような順序であることを特徴とする請求項９８に記載の装置。
【請求項１１８】
前記シェイプ符号化ユニットは、区域ごとに、当該区域の１つの頂点を定義する１つのノードを特定するデータを生成するように動作し、
前記データは、先に識別データが生成された区域の頂点を特定するノードに対する、前記ノードの位置を特定するオフセット値を含むことを特徴とする請求項１１７に記載の装置。
【請求項１１９】
前記オフセット値は、ノードのリストにおける前記ノードの相対位置を特定するオフセット値であることを特徴とする請求項１１８に記載の装置。
【請求項１２０】
前記リストは、環状リストであることを特徴とする請求項１１９に記載の装置。
【請求項１２１】
前記オフセット値は、前記リストにおける異なる方向へのオフセットを特定する正または負の数であることを特徴とする請求項１１９に記載の装置。
【請求項１２２】
前記リストは、識別データが生成された区域の境界の頂点を特定するノードのリストであることを特徴とする請求項１１９に記載の装置。
【請求項１２３】
前記シェイプ符号化ユニットは、前記平面グラフにより定義される前記区域の各々に対して生成された前記識別データの連結を含む識別データを生成することを特徴とする請求項９８に記載の装置。
【請求項１２４】
前記シェイプ符号化ユニットは、前記区域に対して識別データが生成される順序で順序付けされた前記識別データの前記連結を生成することを特徴とする請求項１２３に記載の装置。
【請求項１２５】
前記差分生成ユニットは、平面グラフのリンクと関連付けられる、前記生成されたデータの連結を含むデータを生成することを特徴とする請求項９８に記載の装置。
【請求項１２６】
プログラマブルコンピュータに、請求項１に記載の方法を実行させるためのコンピュータ実現可能なプロセッサステップを格納した記憶媒体。
【請求項１２７】
プログラマブルコンピュータを、請求項６２に記載の装置として構成させるためのコンピュータ実現可能なプロセッサステップを格納した記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、ラティスデータを符号化する方法及び装置に関する。
【背景技術】
【０００２】
ラティス（lattice）とは、有向リンクにより互いに接続された複数のノードで構成される有向非周期グラフのことである。ラティスデータを生成するシステムの一例としては、音声認識アプリケーションがある。このアプリケーションにおいては、ラティスデータは、検出された音声信号を処理するときに、多数の候補仮説を表現するのに利用される。その後、音声認識システムにより生成されたラティスデータは、別のアプリケーションへの入力として利用が可能である。音声認識システムのラティスデータの場合、検出された信号が表現する候補仮説をラティスデータが記録するように、ラティスノード及びラティスリンクは、語（words）あるいは音韻（phonemes）などの音声単位および確率値を特定する、他のデータと関連付けられる。
【０００３】
ラティスデータが生成されると、２種類のラティスデータが特定される。第１のラティスデータは個々のリンク及びノードに関連付けられたデータであり、これが、そのラティスが表現する仮説を特定する。第２のラティスデータは、そのラティスのノードが互いにどのように接続されるかを特定するラティス構造である。
【０００４】
一般に、ラティス構造は、開始ノード−終了ノードデータの形態でリンクデータを格納することにより記憶される。開始ノードにより分類されるリンクを記憶し（それにより、記憶されるべきノードデータを、終了ノードデータのみに限定する）、絶対ノード番号ではなく、ノードオフセットを使用することにより、更に縮小されたリンクデータの表現を実現できる。この方法に関連する主な問題点は、この方法を実行した符号化が、必ずしも、ラティスに規則性をもたらさないことである。換言すれば、視覚的に同一である２つの部分構造が、２つの全く異なるシンボル列を生成する可能性があるということである。これは、リンクデータとノード番号（又はオフセット）が、特定の部分構造の符号化とは無関係であるためである。したがって、この形態で記憶されたラティス構造を表現するデータを圧縮することは、困難である。
【０００５】
例えば、音声認識システムにより生成されるラティス構造は、枝刈りパラメータによっては非常に大きくなることがある。大きなラティス構造を記憶する場合、大容量の記憶装置が必要になる。大きなラティス構造がネットワークを介して送信される場合には、大量の送信容量が必要とされる。したがって、記憶及び送信の双方のために、ラティス構造を効率よく圧縮することが要求される。
【０００６】
このため、同一のシンボル列を使用しつつ等価の構造を表現する能力が高く、これにより、従来の圧縮技法を使用してより高効率な圧縮を実行可能なラティス構造の表現が必要である。
【発明を実施するための最良の形態】
【０００７】
（特定の実施形態）
以下、一例を参照して、本発明の特定の実施形態を説明する。
【０００８】
図１は、文書検索システムの概略ブロック図である。図１を参照すると、クライアントコンピュータ１は、ネットワーク３を介して文書記憶装置２に接続されている。クライアントコンピュータ１には、マイクロフォン５も接続される。
【０００９】
本実施形態では、クライアントコンピュータ１及び文書記憶装置２はそれぞれ、プログラマブルコンピュータで構成されている。このプログラマブルコンピュータは、ディスク８等の記憶媒体からコンピュータ命令を読み出すか、又はネットワーク３を介して、信号９の形態をとる命令をダウンロードすることにより、複数の概念上の機能モジュールが構成されるように、構成される。
【００１０】
本実施形態では、クライアントコンピュータ１の機能モジュールは、音声認識モジュール１０、ラティスプロセッサ１１及びデータ圧縮モジュール１２を含む。文書記憶装置２の機能モジュールは、伸長ユニット１５、再生モジュール１７及び文書検索ユニット１９を含む。
【００１１】
クライアントコンピュータ１の音声認識モジュール１０は、例えば、ユーザが発話した語句等の音声信号の検出に応答して、マイクロフォン５により生成された電気信号を受信するように構成される。音声認識モジュール１０は、受信した電気信号を処理して音声ラティスを生成する。音声ラティスは、ユーザが発話しマイクロフォン５により検出された音声信号がどの語句を表現するかに関する複数の仮説を表現する。
【００１２】
一例として、図２は、「Taj Mahal drawing」という表現の仮説上の組み合わせ音韻及び語の復号化のラティス構造を示す概略図である。図２において、ノードは、丸で表現され、それらの丸は、時間経過の順に左から右に配列されている。図２のラティス構造におけるリンクは、ノード間の矢印で表現される。図示のように、それらのリンクはそれぞれ、大文字で表現される語と関連するか、あるいは小文字で表現される音韻と関連するかのいずれかである。本実施形態では、音声認識モジュール１０は、従来と同様に、例えば、［ノード番号，ノードから出るリンクのリスト，ノードにより表現される時間，ノードと関連する他のデータ］の形態で音声ラティスデータを生成し、記憶するように構成される。更に、音声ラティスのリンクデータも従来のように、例えば、［開始ノード，終了ノード，リンクと関連するデータ］の形態で記憶される。
【００１３】
音声認識モジュール１０により生成される音声ラティスは非常に大きくなる可能性がある。ネットワーク３に大量のデータが送信されるのを避けるために、ラティスプロセッサ１１は、音声ラティスが生成された後、ラティス構造の短縮表現を生成する。詳細は後述するが、短縮表現は、同一のシンボル列を使用して同一のラティス部分構造を符号化するものであり、このため特に、従来のデータ圧縮技法を使用して容易に圧縮される。
【００１４】
ラティス構造の短縮表現が生成されると、この表現は、生成された元の音声ラティスにおけるリンク及びノードと関連するデータと共に、従来のデータ圧縮技法を使用して、データ圧縮モジュール１２により圧縮される。その後、圧縮データは、ネットワーク３を介して、文書記憶装置２へ送信される。
【００１５】
文書記憶装置２は、伸長ユニット１５及び再生モジュール１７を使用して、圧縮データを処理し、元の音声ラティスを再生する。再生された音声ラティスは、その後、文書検索ユニット１９へ送信される。文書検索ユニット１９は、受信された音声ラティスに応答して、文書を検索する。このようにして検索された文書は、コンピュータによりネットワーク３を経て、クライアントコンピュータ１へ返信される。
【００１６】
（ラティスプロセッサの構成）
図３は、ラティスプロセッサ１１の機能構成要素の概略ブロック図である。図３に示すように、本実施形態においては、ラティスプロセッサ１１は、データ記憶装置２０、写像モジュール（embedding module）２２、リンク符号化モジュール２４、シェイプ符号化モジュール２６、復号化モジュール２８、そして、出力モジュール２９を具備する。
【００１７】
特に、本実施形態では、データ記憶装置２０は、音声認識モジュール１０から音声ラティスデータを受信するように構成される。音声ラティスデータは、受信された後、データ記憶装置２０に格納される。音声ラティスデータは、音声ノードデータ３０と音声リンクデータ３２とを含む。
【００１８】
本実施形態では、音声ノードデータ３０は音声ラティスを定義するデータを含む。このデータは、［ノード番号，接続されるノードのリスト，ノードにより表現される時間、及び、例えば、ノードと関連する遷移確率等の他のデータ］の形態のような、従来どおりの形態で記憶される。音声リンクデータ３２は、音声ノードデータ３０により定義されるラティス構造におけるリンクを、語又は音韻を識別するデータと関連付けるデータを含む。この音声リンクデータ３２も、［開始ノード，終了ノード，語又は音韻を識別するデータ又はそのリンクと関連する遷移確率を識別するデータ等の他のデータ］の形態のデータのように、従来の形態で記憶される。
【００１９】
写像モジュール２２は、音声ノードデータ３０を処理して音声ノードデータ３０のノードにより表現される異なる時間を識別するタイミングデータ３４を生成するように構成される。このタイミングデータは、生成後、データ記憶装置２０に格納される。その後、後述するように、写像モジュール２２は、音声ノードデータ３０により定義されるラティス構造の第１の表現を生成する。この表現は、写像テーブル（embedding table）３６、ダミーリンク／ノードデータ（dummy links and nodes data）３８、及びクロスリンクデータ（cross links data）３９の形態をとる。
【００２０】
本実施形態では、写像モジュール２２により生成されたラティス構造の表現がリンク符号化モジュール２４によって処理される。特に、リンク符号化モジュール２４は、ラティス構造を簡易化するために、ラティス構造から一部のリンク及びノードを除去する処理を行う。その一方で、リンク符号化モジュール２４は、ラティス構造から除去されたリンク及びノードを特定するリンク符号化データ４０を生成する。このリンク符号化データ４０も、データ記憶装置２０に格納される。
【００２１】
リンク符号化モジュール２４により、ラティス構造が簡易化された後、シェイプ符号化モジュール２６は、簡易化ラティス構造を処理し、ラティス構造の最終符号化を生成する。本実施形態では、この符号化は、シェイプ符号化データ４２、リンクリスト４３及びノードリスト４４の形態をとり、これらは全て、データ記憶装置２０内部に格納される。後ほど詳細に説明するように、音声ノードデータ３０による元のラティス構造の表現とは対照的に、シェイプ符号化データ４２及びリンクリスト４３は、同一のシンボル列を使用して等価の構造を符号化し、かつ従来の圧縮技法を使用して、より高度な圧縮の実行を容易にする表現によって、同一のラティス構造を符号化するデータを含む。
【００２２】
シェイプ符号化モジュール２６がラティス構造の最終符号化を生成した後、復号化モジュール２８は、最終符号化を処理し、符号化ラティス構造におけるリンクの順序を判定する。これは、復号化モジュール２８が符号化ラティス構造を再生し、次に、再生されたラティス構造におけるリンクの順序を判定することにより実現される。
【００２３】
復号化モジュール２８により、リンクの順序が判定されたならば、出力モジュール２９は、データ圧縮モジュール１２へデータを出力する。ここで出力されるデータは、写像モジュール２２により生成された、タイミングデータ３４、ダミーノード／リンク３８を識別するデータ、及びクロスリンクデータ３９と；シェイプ符号化モジュール２６により生成されたシェイプ符号化データ４２及びリンクリスト４３と；音声ノードデータ３０及び音声リンクデータ３２により、元の音声ラティスにおけるノード及びリンクとそれぞれ関連付けられるその他のデータ、である。ノードと関連付けられる他のデータは、シェイプ符号化モジュール２６により生成されたノードリスト４４を使用して順序付けられ、リンクと関連付けられる他のデータは、復号化モジュール２８により判定された順序で順序付けられる。
【００２４】
出力モジュール２９により出力されたデータは、その後、データ圧縮モジュール１２により、従来の方式で圧縮される。したがって、圧縮データは、ネットワーク３を介して送信された後に伸長されることが可能であり、文書記憶装置２により音声ラティスが再生される。
【００２５】
次に、ラティスプロセッサ１１により実行される処理を示す図４のフローチャートを参照して、ラティスプロセッサ１１の処理の概要を更に詳細に説明する。
【００２６】
（ラティスプロセッサにより実行される処理の概要）
まず、音声ノードデータ３０及び音声リンクデータ３２により表現される音声ラティスがラティスプロセッサ１１により受信され、データ記憶装置２０に格納されると、写像モジュール２２は、音声ノードデータ３０により表現されるラティス構造の第１の表現を判定する（Ｓ４−１）。この初期表現は、データ記憶装置２０に格納されるタイミングデータ３４及び写像テーブル３６の形態をとる。
【００２７】
特に、音声ノードデータ３０がラティスプロセッサ１１により受信されると、写像モジュール２２は、まず、音声ノードデータ３０のノードにより表現される全ての異なる時間のリストを含むタイミングデータ３４を生成する。
【００２８】
先に述べた通り、音声ノードデータ３０は、音声ラティスの中のノードごとに、そのノードにより表現される時間を特定する。したがって、例えば、図２に示される音声ラティスの場合、それらの異なるタイミングは、図２の例のラティスにおいて、ノードを表現する丸のそれぞれ異なる左／右の位置により表現される。
【００２９】
音声ノードデータ３０は、時間データを各ノードと明確に関連付けるので、同一の時間と関連付けられるノードが２つ以上存在する場合には、この時間データは繰り返される。したがって、この繰り返しを排除することにより、ノードにより表現される時間を表現するデータ量の減少が可能である。特に、異なるタイミングのリストが生成される場合、個々のノードは、リスト中の特定のタイミングと関連付けられていると認められる。このように、同一のタイミングと関連付けられるノードが多数存在する場合には、このタイミングデータを、各ノードと関連する音声ノードデータ３０の中に時間データとして明示して含めることにより、このタイミングデータは何度も記録されるのではなく、一度記録される。
【００３０】
ラティス構造のタイミングデータ３４が写像モジュール２２により判定され、データ記憶装置２０に格納された後、音声ノードデータ３０により符号化されたラティス構造の初期表現が、写像モジュール２２により生成される。
【００３１】
本実施形態では、この初期表現は、以下の説明においては、タイミングデータ３４のリストにおける時間により識別されるレイヤと呼ばれる各タイミングに対して、音声ノードデータ３０により、それらのタイミングと関連付けられるノードのリストを含む。更に、このノードのリストに加えて、ラティスにおけるリンクごとの開始ノードと終了ノードとの対を識別するデータのコピーを含む。このデータは、写像モジュール２２により、写像データ及びリンクデータとして、データ記憶装置２０の写像テーブル３６の中に格納される。
【００３２】
図６Ａにラティス構造の一例を示す。この例においては、ノードは、番号を囲む丸で表現され、ノード間のリンクは、丸の間の矢印の形で示される。図６Ａでは、同一のタイミングデータを共有するノードは、同一の水平位置に示される。
【００３３】
図６Ａのラティスの場合、写像モジュール２２により生成される図示されたラティス構造の初期表現は、下記の写像データの形態で、写像テーブル３６の中に格納されている。
【００３４】
レイヤ番号 ノードのリスト
１          ［０］
２          ［１，２］
３          ［３，４，５］
４          ［６］
５          ［７，８］
６          ［９］
【００３５】
上記のレイヤ番号はノードが含まれる列を示し、ノードのリストはその列にあるノードを示す。この例においては、リンクデータは、図６Ａに示される各矢印に関する開始ノードと、終了ノードとを識別するデータのリストを含む。したがって、リンク（０，１）、（０，２）、（１，３）、（１，４）、（１，５）等の形態をとるリンクデータも、写像テーブル３６に格納される。
【００３６】
後ほど詳しく説明するように、写像モジュール２２により生成された初期表現は、代替表現を生成するように、更に処理される。
【００３７】
図６Ａのラティスの場合、この代替表現が図６Ｅに示される。図６Ａの構造と図６Ｅの構造とを比較すると、図６Ａでは、いくつかの矢印（例えば、ノード３とノード７との間の矢印、及びノード４とノード７との間の矢印）が、互いに隣接していない列にあるノードをリンクするのに対し、図６Ｅにおいては、各ノードが隣接する列の１つ以上のノードに接続されるように、補足的なダミーノード及びダミーリンクが表現に追加されている。図６Ｅの場合、追加ノードはラティス中に現れる矩形で示され、追加リンクは破線で示されている。
【００３８】
さらに、図６Ａと比較すると、図６Ｅにおいては、最終レイヤが、図６Ｅに示される単一のノードをダミーノードＤ４として含むように、ラティスに別のレイヤが追加されている。列内部のノードの順序を再配列し、１つのリンク（ノード５とノード６との間のリンク）を除去することにより、図６Ｅに示される構造が、図６Ａのリンク２−３及びリンク１−５に示されるように互いに交差するリンクを含まないように変更されている。換言すれば、この表現におけるリンク及びノードによって、平面グラフ、すなわち、クロスリンクを含まない１つの平面に写像可能なグラフ、が特定される。
【００３９】
写像モジュール２２による処理の結果、追加又は除去されたノード及びリンクを特定するデータは、写像モジュール２２によってデータ記憶装置２０に格納される。なお、追加データはダミーリンク／ノードデータ３８として格納され、除去されたデータは、クロスリンクデータ３９として格納される。
【００４０】
写像モジュール２２によりラティス構造の修正表現が求められると、ラティスプロセッサ１１はこの修正された構造の符号化を生成する。この符号化は２段階プロセスで実行される。
【００４１】
まず、リンク符号化モジュール２４は、構造のいくつかの部分を、ノード間のリンクと関連付けられるデータの形態で符号化する（Ｓ４−２）。特に、後ほど詳しく説明するように、リンク符号化モジュール２４は、修正ラティス構造の中で、互いに直列に接続された複数のリンク、又はラティス構造において他のどのノードにも接続されない複数の並行するパスを介して接続された複数のリンクのいずれかに対応する部分を符号化する。
【００４２】
したがって、例えば、図６Ｅにより示されるラティス構造の場合、図６Ｅのノード８及び１０を介するノード６とノードＤ４との間のリンク及びノードの符号化は、図６Ｅのノード４及び５を介するノード１とノード７との間で並行するパスの符号化であるとして判定される。
【００４３】
図８Ｈは、一次（linear）のパス及び並行する（parallel）パスが符号化された後の、図６Ｅのラティスに対応する簡易化ラティス構造の一例を示している。図８Ｈにおいてはノードが丸で示され、ノード間のリンクが矢印で示されている。図８Ｈに示される各リンクに１つのコードが関連付けられ、このコードは矢印に付記されている。それらのコードはリンク符号化モジュール２４により生成され、リンク符号化データ４０としてデータ記憶装置２０に格納される。
【００４４】
リンク符号化モジュール２４が簡易化ラティス構造及びリンク符号化データ４０を生成した後、図８Ｈのラティス構造に示されるように、簡易化ラティス構造はクロスリンクを含まない平面グラフになり、そのリンク及びノードは、互いに接続されたいくつかの区域を定義する。図８Ｈの場合、それらの区域は、図８Ｈの左から右に向かって、ノード０、２、３及び１と、それらのノードと関連するリンクにより形成される菱形、ノード２、６、７及び３と、それらのノードと関連するリンクにより形成される斜方形、ノード１、３及び７と、それらのノードと関連するリンクにより形成される三角形、並びにノード６、７及びＤ４と、それらのノードの間のリンクにより形成される別の三角形である。
【００４５】
次に、シェイプ符号化モジュール２６は、リンク符号化モジュール２４により最初に処理されたラティス構造を、３つのシンボルリストの形態で符号化する（Ｓ４−３）。
【００４６】
本実施形態では、それらのリストは、シェイプ符号化データ４２、リンクリスト４３及びノードリスト４４を含む。シェイプ符号化データ４２は、リンク符号化モジュール２４により生成された簡易化ラティスにより定義される区域が互いにどのようにリンクするかを特定する。リンクリスト４３は、簡易化ラティスにおけるリンクと関連付けられるリンク符号化データ４０の順序付き連結を示す。ノードリスト４４は、簡易化ラティス及び関連するリンク符号化データにノード番号が現れる順序を特定する。
【００４７】
それらのリストの生成について詳細に説明する際に明らかになるであろうが、これらのリストによって、同一の部分構造が同一のシンボル列で符号化され、そして、従来のデータ圧縮技法によるデータ圧縮を非常に実行しやすい符号が生成されるように、リンク符号化モジュール２４により処理されたラティス構造が符号化される。
【００４８】
それら３つのリストがシェイプ符号化モジュール２６により作成され、データ記憶装置２０に格納された後、シェイプ符号化データ４２、リンクリスト４３及びノードリスト４４は、復号化モジュール２８により処理される（Ｓ４−４）。復号化モジュール２８による復号化の結果、データ記憶装置２０の写像テーブル３６に格納された音声ノードデータ３０により表現されるラティス構造の別の表現が生成される。図６Ａのラティス構造に対して生成されたシェイプ符号化データ４２、リンクリスト４３及びノードリスト４４からラティスを生成するプロセスについては、後に詳細に説明する。
【００４９】
図６Ａの構造に対して、シェイプ符号化データ４２、リンクリスト４３及びノードリスト４４を復号化して求められる最終表現を、図１４Ｇに示す。図１４Ｇにより示されるラティス構造と図６Ａにより示されるラティス構造とを比較すると、図６Ａにより示されるリンクの相互接続と図１４Ｇにより示されるリンクの相互接続とは同一であり、各ノードは同じ列にあるものの、各列におけるノードの表現順序が異なっていることがわかる。しかし、列内の順序は音声ノードデータ３０に依存しないので、図６Ａの写像ラティスと図１４Ｇの写像ラティスとは全く同じではないがそれらは同一のラティス構造を表現している。
【００５０】
データ記憶装置２０に格納されたデータにより符号化された実際の写像ラティス構造が、復号化モジュール２８によって求められた後、出力モジュール２９は、タイミングデータ３４、ダミーノード及びダミーリンク３８のリスト、クロスリンクデータ３９、並びにシェイプ符号化データ４２及びリンクリスト４３を、データ圧縮モジュール１２へ出力する（Ｓ４−５）。これらのデータは、復号化モジュール２８により復号された通りに、この最終写像表現を表す。
【００５１】
さらに、後述するように、出力モジュール２９は、音声ノードデータ３０及び音声リンクデータ３２によりノード及びリンクと関連付けられるデータの順序付きリストも、出力モジュール１２へ送信する。
【００５２】
音声ノードデータ３０によりノードと関連付けられるデータは、データ記憶装置２０に格納されたノードリスト４４に対応する順序で順序付けられる。音声リンクデータ３２によりリンクと関連付けられるデータは、音声ラティスに対して復号化モジュール２８により生成される最終ラティス構造に基づいて順序付けられる。例えば、図１４Ｇの音声ラティスの場合、リンクデータは、上から下へ、次に、左から右に現れるリンクの列に対応して、順序付けられる。したがって、例えば、最初に、リンク０−２のデータが出力モジュール２９により伸長モジュール１２へ送信された後に、後続するリンクのリンクデータは、図１４Ｇにおけるリンクの順序に対応して、０−１，２−６、２−３，１−３，１−４，１−５等々の順序で送信される。
【００５３】
先に述べたように、ラティス構造を符号化するためのシェイプ符号化データ４２及びリンクリスト４３は、等価の構造を、完全に同一のシンボル列を使用して表現する。すなわち、ラティス部分構造の多くが類似している場合には、ネットワーク３を介して送信される必要があるデータ量を減少するために、ラティスプロセッサ１１によりデータ圧縮モジュール１２へ送信されるデータを、従来の圧縮技法を使用して効率よく圧縮することが可能である。
【００５４】
圧縮データが伸長ユニット１５により伸長される時、伸長されたデータは、元の音声ラティスを再生するために利用される。その後、元の音声ラティスは、文書記憶装置２に格納された特定の文書を文書検索ユニット１９がアクセスするのに使用される。
【００５５】
次に、写像モジュール２２、リンク符号化モジュール２４、シェイプ符号化モジュール、及び復号化モジュール２８によるデータの詳細な処理について、順次検討する。
【００５６】
（写像モジュールにより実行される処理）
図５及び、図６Ａ〜図６Ｅを参照して、ラティスプロセッサ１１の写像モジュール２２の処理を詳細に説明する。
【００５７】
最初に、音声ノードデータ３０及び音声リンクデータ３２の形態をとる音声ラティスがラティスプロセッサ１１により受信され、データ記憶装置２０に格納されると、写像モジュール２２は、音声ノードデータ３０においてノードにより表現される個々の時間を識別するタイミングデータ３４を生成する（Ｓ５−１）。
【００５８】
特に本実施形態では、音声ノードデータ３０は、［ノード番号，接続するノードのリスト，ノードのタイミング，ノードと関連する他のデータ］の形態で、データ記憶装置２０に格納されるので、写像モジュール２２は、まず、音声ノードデータ３０を処理して音声ノードデータ３０のノードにより表現される全てのタイミングのリストを生成する。次に、写像モジュール２２は、生成されたリストを処理し、タイミングの順序付きリストを作成する。次に、リスト中に表現される重複したタイミングが除去され、その結果、タイミングデータ３４が作成される。タイミングデータ３４は、異なる時間のリストから成る。また、その異なる時間は、異なるタイミングの順序で順序付けられた音声ノードデータ３０により異なるノードにより表現される。その後、このリストは、ラティスプロセッサ１１のデータ記憶装置２０に、タイミングデータ３４として格納される。
【００５９】
タイミングのリストがタイミングデータ３４の形態でデータ記憶装置２０に格納された後、写像モジュール２２は、データ記憶装置２０に格納された音声ノードデータ３０により表現されるラティス構造に対して、初期写像データを生成する（Ｓ５−２）。
【００６０】
特に、写像モジュール２２は、タイミングデータ３４により表現される各タイミング（以下レイヤという。）に対して、特定された時間に対応する時間データを有するノードのリストを求める。それらのリストは、タイミングデータ３４により特定される各々の時間に対して１つずつ、写像テーブル３６に写像データとして格納される。さらに、音声ノードデータ３０により特定されるノード間の各リンクに対して、写像モジュール２２は、リンクごとの開始ノードおよび終了ノードを識別するデータから成るリンクデータを生成し、写像テーブル３６に格納する。
【００６１】
したがって、例えば、図６Ａにより示されるラティス構造の場合、写像テーブル３６には、以下に示すようなデータが格納されることになる。なお、図６Ａにおいては、ノード番号は番号を取り囲む丸で示され、リンクはそれらの丸を接続する矢印で示される。また、同じタイミングに係り同一のレイヤにあるノードは、互いに上下する縦の列に示される。
【００６２】
写像データ
レイヤ番号 ノードのリスト
１            ［０］
２            ［１，２］
３            ［３，４，５］
４            ［６］
５            ［７，８］
６            ［９，１０］
リンク（０，１）、（０，２）、（１，３）、（１，４）（１，５）、（２，３）、（２，６）、（３，７）、（４，７）、（５，６）、（６，７）、（６，８）、（６，８）、（７，９）、（８，１０）
【００６３】
併せて、タイミングデータ３４及び写像テーブル３６が、音声認識モジュール１０から受信される音声ラティスの全てのラティス構造を符号化することは明らかである。さらに、タイミングデータ３４及び写像テーブル３６は、各ノードと関連するタイミングを識別するデータも黙示的に記録する。
【００６４】
また、ノード間のリンクの方向も、写像テーブル３６内のデータにおいて暗黙に符号化される。これは、異なるレイヤ、すなわち異なるタイミングにより識別されるノードのリストがタイミングの順序で順序付けられるためである。その結果、リストにおいては、若いレイヤ番号に対して、より早い時間を表すノードが現れ、写像テーブル３６において時間の遅いレイヤに対しては、遅いタイミングに対応するノードがリスト中に現れる。したがって、１つのノードから別のノードに至るリンクが記録される場合、図６Ａにおいて矢印により示されるような、そのリンクの方向は、より早いタイミングに対応するレイヤのノードから、遅いタイミングに対応するレイヤのノードに向かう方向になることが理解されよう。
【００６５】
ラティス構造の初期写像が判定された後、写像モジュール２２は、写像テーブル３６にいくつかの追加ノードを追加し、リンクデータを更新するために、初期格納データを修正する（Ｓ５−３）。リンクデータの更新により、各リンクは、１つのレイヤのノードから、隣接するレイヤのノードにのみ接続し、第１のレイヤ及び最後のレイヤのノードのリストは、単一のノードを含むようになる。
【００６６】
特に、写像モジュール２２は、写像テーブル３６に格納されたリンクの各々を順次考慮する。各リンクについて、開始ノードのレイヤ番号が、そのリンクの終了ノードのレイヤ番号と比較される。開始ノードのレイヤ番号と、終了ノードのレイヤ番号が番号１つ分離れている場合、それ以上の処理は実行されない。開始ノードが２つ以上のレイヤをはさんで終了ノードにリンクされている場合には、必ず、介在する各レイヤにダミーノードが追加される。その後、処理中であるリンクデータを、各レイヤにおいて、追加された各ダミーノードを介して、開始ノードと終了ノードとの間にあるリンクを識別するリンクデータの一連の項目と置き換えるために、リンクデータは更新される。
【００６７】
したがって、例えば、図６Ａにより示される写像の場合、各リンクが順次考慮される。ノード２とノード６との間のリンクが処理される時、ノード２は第２レイヤにあるとして識別され、ノード６は第４レイヤにあるとして識別される。そこで、写像モジュール２２は、第３レイヤに関するノードのリストにダミーノードを追加し、ノード２とノード６との間のリンクを、２つのリンク、すなわち、ノード２と追加されたダミーノードとの間のリンク及び追加されたダミーノードとリンク６との間のリンク、と置き換える。
【００６８】
特に、図６Ａに示されるラティスの場合、２と６との間のリンク、３と７との間のリンク及び４と７との間のリンクは、レイヤ２つ分以上離れたレイヤにあるノードを接続しているリンクとして識別される。そこで、写像テーブル３６に格納された写像データは、次のように更新される。
【００６９】
レイヤ番号 ノードのリスト
１                ［０］
２                ［１，２］
３                ［３，４，５，Ｄ１］
４                ［Ｄ２，Ｄ３，６］
５                ［７，８］
６                ［９，１０］
【００７０】
ここで、Ｄ１、Ｄ２、Ｄ３は、写像モジュール２２により追加された追加ダミーノードである。ノード２とノード６との間のリンク、ノード３とノード７との間のリンク及びノード４とノード７との間のリンクのリンクデータは、次のリンクデータ：（２，Ｄ１）、（Ｄ１，６）、（３，Ｄ２）、（Ｄ２，７）、（４，Ｄ３）、（Ｄ３，７）と置き換えられる。
【００７１】
その後、それらのダミーノードを識別するデータは、写像モジュール２２により、データ記憶装置２０のダミーリンク／ノードデータ３８に格納される。
【００７２】
次に、写像モジュール２２は、写像テーブル３６に格納されたデータの第１のレイヤ及び最終レイヤのノードのリストを考慮する。第１レイヤが２つ以上のノードを含む場合、ダミーノードを含む追加の第０レイヤが追加され、この最初のダミーノードと第１レイヤのノードとの間にダミーリンクが追加される。
【００７３】
次に、最終レイヤのノードのリストが考慮される。最終レイヤに２つ以上のノードが現れた場合には、写像データに１つのダミーノードを含む追加レイヤが追加され、最終レイヤの各ノードから、追加されたダミーノードに至るリンクがリンクのリストに追加される。その後、追加された全てのダミーノードを識別するデータが、データ記憶装置２０内のダミーリンク／ノードデータ３８に追加される。
【００７４】
したがって、図６Ａの例の場合、第１レイヤは１つのノード、すなわち、ノード０を含むので、ダミーノードは追加されない。しかし、最終レイヤは当初、ノード９及び１０を含んでいた。そこで、１つのダミーノードを含む追加の最終レイヤが追加される。先に最終レイヤであったレイヤにあるノードの全て、この場合には、ノード９及び１０は、追加レイヤにある、この最終ノードに接続されるものとして記録される。
【００７５】
図６Ｂは、図６Ａのラティスにダミーノードが追加された後のラティスの概略図である。図６Ｂにおいては、ダミーノードは、Ｄ１、Ｄ２、Ｄ３及びＤ４とラベル付けされた矩形で示される。また、図６Ｂにおいては、ラティスに追加された補足リンクは破線で示される。図６Ｂを参照するとわかるように、図６Ｂのラティスの場合、図中に表れている矢印の全ては、２つ以上の列とは交差せず、ラティス全体は、単一の開始ノード、すなわち、図の左側のノード０と、図の右側のＤ４とラベル付けされた単一の終了ノードとを有する。
【００７６】
リンクが隣接する列のノードを接続することを保証するために、ダミーノードがラティスに追加され、かつラティスが１つの開始ノードと、１つの終了ノードとを含むことを保証するために、ダミーノードが追加された後、写像テーブル３６中の写像データにより表現されるラティス写像が、互いに交差するリンクを限られた数しか含まないように、各レイヤと関連するノードのリストを再順序付けするために、写像テーブル３６の写像データが処理される（Ｓ５−４）。
【００７７】
本実施形態では、写像モジュール２２は、写像テーブル３６に格納された写像データを、従来の技法を使用して処理する。従来の技法は例えば、Roberto Tamassia, "Graph Drawing""CRC Handbook of Discrete and Computational Geometry", (CRC Press, ed. Jacob Goodman and Joseph O'Rouke, 1997) に記載されている技法である。この文献は、引用により本明細書に組み込まれる。
【００７８】
特に、第２レイヤから始めて、まず、レイヤ中の各ノードに、そのレイヤにおけるノードの順序に対応する順序番号が割り当てられる。したがって、図６Ｂのノードの場合には、ノード１に順番１が割り当てられ、ノード２に順番２が割り当てられることになるであろう。その後、次のレイヤのノードにリンクされた先のレイヤにおけるノードの平均順番値に基づいて、次のレイヤのノードが順序付けられる。
【００７９】
したがって、図６Ｂの場合、ノード１に値１が与えられ、ノード２に値２が与えられるとすると、ノード１とノード２の双方にリンクされるノード３には、（１＋２）／２＝１．５の値が割り当てられることになる。ノード１にのみ接続されるノード４及び５にはそれぞれ、１の値が割り当てられる。ノード２にのみ接続されるノードＤ１には２の値が割り当てられる。
【００８０】
次に、写像モジュール２２は、関連する順序番号が最小であるノードがリストの先頭に現れ、それより順に大きくなる番号を有するノードがリストの中で順に後の位置に現れるように、次のレイヤのノードを再順序付けする。
【００８１】
したがって、図６Ｂの場合、第３レイヤの列を表すリストは、リスト［３，４，５，Ｄ１］から、リスト［４，５，３，Ｄ１］となるように再順序付けされる。その後、最終レイヤの最終ノードに到達するまで、次のレイヤも同様に再順序付けされる。次に、ノードの第２レイヤから始めて、最終レイヤまで、各レイヤにおけるノードの再順序付けが繰り返され、その最終レイヤからのリンクにより識別される順序番号の平均値から判定される順序値に基づいて、直前のレイヤを再順序付けする。この処理は、第１レイヤに到達するまで、更に前のレイヤにさかのぼって繰り返される。
【００８２】
図６Ｃは、交差するリンクを最小限にするために、ノードが再順序付けされた後の、図６Ｂのラティスの例を示す図である。図６Ｂと図６Ｃを比べると明らかなように、図６Ｂでは、ノード２−３間のリンクと、ノード１−４間及びノード１−５間のリンクが全て交差しているが、図６Ｃにおいては、交差するリンクは一対だけ、すなわち、ノード３−Ｄ２間のリンクと、ノード５−６との間のリンクだけである。
【００８３】
写像モジュール２２が、写像テーブル３６中の写像データのレイヤにおけるノードを再順序付けした後、写像モジュール２２は、各リンクを順次考慮し、修正ラティスから交差するリンクを除去し、除去されたリンクを特定するデータを、データ記憶装置２０内に格納されたクロスリンクデータ３９に格納する（Ｓ５−５）。
【００８４】
特に、各レイヤの各リンクが順次考慮され、リンクが他のリンクと交差すると判定されるたびに、リンクが他のリンクと交差する回数を表す数が１増分される。全てのリンクに関するデータが生成されると、レイヤ間の各リンクセットが順次考慮される。クロスリンクが存在する場所では、関連する数が最大である１つのリンクが除去され、このリンクを識別するデータは、クロスリンクデータ３９に格納される。次に、各レイヤにおける交差するリンクの数の計算値が更新され、交差するリンクがなくなるまでリンクが除去される。このようにして、写像テーブル３６における写像とは別個に除去され、クロスリンクデータ３９として格納される交差するリンクは、最大数のリンクと交差するリンクに対応するように選択される。すなわち、１つのリンクが他の２つのリンクと交差する場合、交差する２つのリンクが除去されるのではなく、１つのリンクが除去される。
【００８５】
図６Ｃを参照すると、交差するリンクの数を最小限にするために、レイヤのノードが再順序付けされた後、図６Ａの例のラティスの写像データは、図６Ｃにより表される順序となるように再順序付けされる。図６Ｃにおいては、交差する一対のリンクは、ノード３−Ｄ２間のリンクとノード５−６間のリンクである。これらのリンクは共に、他のただ１つのリンクと交差するので、それらのリンクのうちの一方が無作為に選択され、クロスリンクデータ３９に格納される。
【００８６】
図６Ｄは、ノード５−６間のリンクが除去された後の、図６Ｃのラティスの例を示す図である。図６Ｄからわかるように、リンクを表す各矢印は、２つの隣接する列にある２つのノードを接続する。また、矢印により表されるリンクの中に、矢印により表される他のリンクと交差するものは１つもない。
【００８７】
写像テーブル３６のデータにより表現されるラティスがクロスリンクを含まないように、写像テーブル３６のリンクデータから十分な数のリンクが除去され、クロスリンクデータ３９として格納された後、写像モジュール２２は、第１のレイヤ及び最終レイヤのノードを除く各ノードを順次考慮し、そのノードが先のレイヤ及び後続レイヤの双方のノードに接続されているか否かを判定する（Ｓ５−６）。
【００８８】
換言すれば、写像モジュール２２は、各ノードを順次考慮し、ラティスに関する写像テーブル３６の中にリンクデータとして格納されたリンクのうちの少なくとも１つのリンクにおいて、処理中のノードが、開始ノードと終了ノードの双方として現れるか否かを判定するために、写像テーブル３６中のリンクデータを検査する。そのような非接続ノードが識別されるたびに、写像モジュール２２は、その非接続ノードをラティス中の他のノードに接続するために、リンクデータを追加する。
【００８９】
特に、最終レイヤのノードを除く各ノードが順次考慮される。写像テーブル３６の中のリンクデータにより、あるノードが開始ノードとして表現されないと判定された場合、そのレイヤにおけるノードのリストの中でリンクされないノードに隣接するノードが次に考慮される。
【００９０】
したがって、図６Ｄのラティスの場合、どのリンクに対しても開始ノードではないノード５が識別され、それに隣接する２つのノード、すなわち、ノード３及び４が考慮される。次に、それらの隣接するノードを開始ノードとして有するリンクにより接続されたノードが識別される。図６Ｄの場合、問題となるノードは、ダミーノードＤ２及びＤ３である。
【００９１】
図６Ｄの場合のように、それら２つのノードが共にダミーノードであれば、それら２つのダミーノードを含むレイヤの写像データにおいて、それらのノード間に新たなダミーノードが追加され、非接続ノードと、新たなダミーノードとの間にリンクが追加される。
【００９２】
次に、写像モジュール２２は、２つのダミーノードにリンクされたノードを考慮する。それらのノードもダミーノードであれば、そのレイヤで識別された２つのダミーノードの間に、次のレイヤの更に別のダミーノードが追加され、更に、最も近い時点で追加されたダミーノードと新たなダミーノードとの間のリンクが、写像テーブルの写像データに追加される。
【００９３】
最終的には、非接続ノードに隣接するノードのうちの１つに接続されたレイヤにおいて、ダミーノードではないノードに到達する。このレイヤに到達すると、写像モジュール２２は、先のレイヤの非接続ノードを、次のレイヤの実ノードに接続するパスに、リンクを追加する。
【００９４】
非接続ノードが開始ノードとして現れなかったラティスに、非接続ノードが接続された後、第１のレイヤに現れる単一のノードとは別個に、終了ノードではないとして識別されるノードに、追加のノード及びリンクを追加するために、同様の処理が実行される。写像テーブル３６に格納されたデータにノード及びリンクが追加されるたびに、追加されるダミーノード及びダミーリンクを識別するデータは、データ記憶装置２０に、ダミーリンク／ノードデータ３８として格納される。
【００９５】
図６Ｅは、図６Ａのラティスが写像モジュール２２により処理された後の、図６Ａのラティスの概略図である。図６Ｅからわかるように、処理後のラティスにおいて、全てのリンクは、隣接するレイヤのノードの間を接続し、図６Ｅのラティスのリンクの中で、他のリンクと交差するものは１つもない。
【００９６】
すなわち、ノードを接続するパスは、それらのノードが関連するレイヤを暗黙に識別する。これは、第１レイヤのノードが第１のノードからノード１つ分の長さのパスによって識別されるのに対し、第２レイヤのノードは、ノード２つ分の長さのパスにより、第１レイヤのノードに接続され、一般に、第ｎレイヤのノードは、ｎ個のノードを含むパスにより、第１のノードに接続されるからである。
【００９７】
図６Ａのラティスを処理するこの段階においては、図６Ｅの構造を表現する、下記の写像データが、構造中の各リンクを特定するリンクデータと共に、写像テーブルに格納される。
【００９８】
写像データ
レイヤ番号 レイヤのノード
１            ［０］
２            ［２，１］
３            ［Ｄ１，３，５，４］
４            ［６，Ｄ２，Ｄ５，Ｄ３］
５            ［８，７］
６            ［１０，９］
７            ［Ｄ４］
【００９９】
次に、写像モジュール２２は、写像テーブルに格納されたリンクデータを順序付けする（Ｓ５−７）。特に、写像モジュール２２は、まず、異なるレイヤに対して開始ノードが写像データ中に現れる順序で、リンクデータを順序付けする。次に、同一の開始ノードを有するリンクは、終了ノードが写像データに現れる順序により順序付けされる。
【０１００】
したがって、図６Ｅのリンクの場合、写像テーブル３６には、次のように順序付けされたリンクデータが格納される。
リンク（０，２）、（０，１）、（２，Ｄ１）、（２，３）、（１，３）、（１，５）、（１，４）、（Ｄ１，６）、（３，Ｄ２）、（５，Ｄ５）、（４，Ｄ３）、（６，８）、（６，８）、（６，７）、（Ｄ２，７）、（Ｄ５，７）、（Ｄ３，７）、（８，１０）、（７，９）、（１０，Ｄ４）、（９，Ｄ４）
【０１０１】
さらに、データ記憶装置２０には、図６Ａのラティスに追加されたダミーノード、すなわち、ダミーノードＤ１、Ｄ２、Ｄ３、Ｄ４、Ｄ５を識別するデータが格納される。続くデータは、ダミーリンクデータ（５，７）及びクロスリンクデータ（５，６）として格納される。
【０１０２】
クロスリンク及び隣接するレイヤと交差するリンクが除去されたこの写像ラティス構造は、その後、リンク符号化モジュール２４により処理されるために送信される。以下に説明するように、リンク符号化モジュール２４は、このようにして生成されたラティス構造を簡易化する。
【０１０３】
（リンク符号化モジュールによる処理）
次に、図７及び図８Ａ〜図８Ｈを参照して、ラティスプロセッサ１１のリンク符号化モジュール２４により実行される処理を詳細に説明する。
【０１０４】
リンク符号化モジュールの処理は、写像モジュール２２により生成された写像テーブル３６を処理して生成されたテーブル３６に基づき表現されるラティス構造を簡易化する。特に、リンク符号化モジュール２４の処理は、写像モジュール２２により生成されたラティス構造のうちの、他の２つのノードにのみ接続されたノードであるノードの間の一次（linear）パスを識別する部分、及び複数の一次パスが同じ２つのノードを接続している部分を符号化する。
【０１０５】
図７を参照すると、写像モジュール２２が写像データ及びリンクデータを生成し、写像テーブル３６に格納した後、リンク符号化モジュール２４は、初期リンク符号化データ４０を生成する（Ｓ７−１）。
【０１０６】
特に、写像テーブル３６のリンクデータにより識別されるリンクの各々に対して、識別されたリンクのリンク符号化として、１つのシンボル、本実施形態では、文字Ｅを含むデータが、リンク符号化データ４０としてデータ記憶装置２０に格納される。
【０１０７】
図８Ａは、各々のリンクが、リンクごとに１つのシンボルＥを含むリンク符号化データ４０と関連付けられる場合の図６Ｅのラティスの概略図である。後ほど詳細に説明するように、これに続くリンク符号化モジュール２４の処理は、写像テーブル３６中のデータにより表現されるラティスからリンク及びノードを除去するために、リンク符号化データ４０及び写像テーブル３６の中に格納されたデータを修正する。その一方で、ラティスにおいて、ノード及びリンクが除去された場所を識別するために、リンク符号化データ４０を修正する。
【０１０８】
初期のリンク符号化データ４０が格納された後、リンク符号化モジュール２４は、処理する第１のノードを選択する（Ｓ７−２）。本実施形態では、処理する第１のノードは、写像テーブル３６の写像データにより定義されるラティス構造の第２レイヤから最終レイヤに至るまでのノードを識別するリストの先頭から選択される。
【０１０９】
図８Ａのラティスの例の場合、第２レイヤから最終レイヤについて選択されるノードは、ノード１０になる。
【０１１０】
初期ノードが選択された後、リンク符号化モジュール２４は、処理する初期リンクを選択する（Ｓ７−３）。本実施形態では、写像テーブルに格納されたリンクデータのうち、選択されたノードを開始ノードとして有するリンクデータにおいてリンクが現れる順序で、選択されたノードから出るリンクが選択される。図８Ａの例においては、ノード１０からノードＤ４に至るリンクは１つである。したがって、処理のために最初に選択されるのは、このリンクである。
【０１１１】
処理するリンクが選択された後、リンク符号化モジュール２４は、処理するリンクの終了ノードを考慮する（Ｓ７−４）。特に、リンク符号化モジュール２４は、そのリンクにより特定される終了ノードが、写像テーブル３６に格納された写像データのリンクのリストにおいて、開始ノードとしてただ１度現れるか否か及び終了ノードとしてただ１度現れるか否かを判定する。
【０１１２】
この条件が当てはまる場合、そのノードを通過するパスは１つである。そこで、リンク符号化モジュール２４は、その単一のパスにおけるそのノードの存在を符号化するために、リンク符号化データ４０と、写像テーブル３６中のデータとを修正する（Ｓ７−５）。
【０１１３】
特に、リンクの開始ノードを特定するリンクデータをＮ１とし、終了ノードを特定するリンクデータをＮ２とすると、処理対象のリンクがリンクデータ（Ｎ１，Ｎ２）を含み、かつＮ２を開始ノードとする別の１つのリンク（Ｎ２，Ｎ３）が存在する場合には、リンク符号化モジュール２４は、写像テーブル３６から、リンクデータのそれらの項目を削除し、リンクデータの単一の項目（Ｎ１，Ｎ３）をそれらの項目と置き換える。この新たなリンクは、順序付きリンクデータにおいて、削除されたリンク（Ｎ１，Ｎ２）の位置に含まれる。
【０１１４】
次に、リンク符号化モジュール２４は、削除された２つのリンクのリンク符号化データを利用して、新たなリンクのリンク符号化データを生成する。
【０１１５】
特に、リンク符号化モジュール２４は、リンク（Ｎ１，Ｎ２）のリンク符号化データを、リンク（Ｎ２，Ｎ３）の符号化データの終わりに付け加える。次に、リンク符号化モジュール２４は、ノードＮ２がダミーノード３８中のデータにより識別されるようなダミーノードに対応する場合は、新たに生成されたシンボルのリストの先頭に、文字Ｄを追加する。そうでない場合には、リンク符号化モジュール２４は、文字Ｐと、対応する番号を付されたノードが写像テーブルの表現から送り出されたことを特定するノードの番号とを追加する。その後、リンク符号化モジュール２４は、写像テーブル３６中に格納された写像データのノードのリストから、特定されたノードＮ２を削除する。
【０１１６】
したがって、図８Ａのノード８−１０間のリンク及びノード１０−Ｄ４間のリンクの場合、ノード８−１０間のリンク及びノード１０−Ｄ４間のリンクを特定するリンクデータが削除された後、ノード８−Ｄ４間のリンクを特定するデータを含む新たなリンクデータが格納される。次に、ノード８−１０間のリンク及びノード１０−Ｄ４間のリンクについて格納されたリンク符号化データ４０を利用して、新たなリンクのリンク符号化データが生成される。この例においては、新たなリンクのリンク符号化データは、シンボルＰと、除去されるべきノード、この場合には、ノード１０を識別する識別子と、除去されるべきリンクと関連するシンボルとを含む。除去されるべきリンクと関連するシンボルは、ノード８−１０間のリンクのリンク符号化、続いて、ノード１０−Ｄ４間のリンクのリンク符号化の順序に従う。この例の場合には、符号化Ｅの後に別の符号化Ｅが続くことになる。その後、削除されるリンクの符号化データと、写像テーブル３６中のノード１０の表現とが削除される。
【０１１７】
写像テーブル３６及びリンク符号化データ４０が更新された後、現在のノードと、他のノードとの接続が再度考慮される（Ｓ７−３、Ｓ７−４）。特に、写像テーブル３６のリンクデータのうち、現在選択されたノードを開始ノードとして有する第１のリンクが再度考慮され（Ｓ７−３）、そのリンクにより識別される終了ノードが、写像テーブル３６中のリンクデータにおいて単一の開始ノードにより識別されるか否かが判定される（Ｓ７−４）。この条件が当てはまる場合には、写像テーブル３６及びリンク符号化データ４０が、先に説明したように更新される（Ｓ７−５）。
【０１１８】
選択されたリンクが、写像テーブル３６中のデータにより開始ノードとして１度ならず識別され、かつ終了ノードとしても１度ならず識別されるノードを識別すると判定された（Ｓ７−４）場合には、リンク符号化モジュール２４は、現在選択されたノードから出る全てのリンクの処理が完了したか否かを判定する（Ｓ７−６）。まだ完了していなければ、リンク符号化モジュール２４は、写像テーブル３６中のリンクデータのうち、現在選択されたノードを開始ノードとして有する次のリンクを考慮し（Ｓ７−７）、そのリンクデータが、開始ノードとしてただ１度現れる終了ノードを識別するか否かを、先に説明したように判定する（Ｓ７−４）。
【０１１９】
現在選択されたノードから出る全てのリンクの処理が完了したならば、リンク符号化モジュール２４は、現在選択されたノードと、他のいずれかのノードとの間に２つ以上のリンクが存在するか否かを判定する（Ｓ７−８）。すなわち、リンク符号化モジュール２４は、現在選択されたノードを開始ノードとして有するリンクデータの格納項目のうちのいずれかが、写像テーブル３６に格納されたリンクデータのその他の項目のうちのいずれかの複製であるか否かを判定する。複製であると判定された場合、リンク符号化モジュール２４は、複製リンクのうちの１つを削除し、残るリンクと関連するリンク符号化データ４０を更新する（Ｓ７−９）。
【０１２０】
特に、リンク符号化は、シンボルリストへと更新される。このシンボルリストは、２つのリンクが併合されたことを示すシンボル、本実施形態においては、シンボルＭと、それに続く、処理対象の対のリンクのうちの一方のリンクに関するリンク符号化を含む２つのシンボルのリストのうちの長いほうのリストと、更にそれに続く、考慮されるべき他方のリンクに関するシンボルのリストとを含む。次に、現在選択されたノードから出る第１のリンクが再度考慮され（Ｓ７−３）、その後、リンクは、先に説明したように処理される（Ｓ７−４〜Ｓ７−８）。
【０１２１】
現在選択されたノードから出るその他のリンクのいずれもが、現在選択されたノードから出る他のリンクと同一の終了ノードを有していないと判定された（Ｓ７−８）場合には、リンク符号化モジュール２４は、最終ノードに到達したか否かを判定する（Ｓ７−１０）。
【０１２２】
特に、リンク符号化モジュール２４は、現在のノードが、写像データの第１レイヤにおいて特定されるノードに対応するか否かを判定する。この条件に当てはまる場合、ラティス中の一次パス及び並行パスの符号化は完了しており、処理は終了する。
【０１２３】
この条件が当てはまらない場合には、処理すべき次のノードが選択される（Ｓ７−１１）。本実施形態では、ここで選択される次のノードは、リスト中の、先に処理されたノードと同じレイヤにある次のノードである。リストの末尾に到達している場合には、次に早いタイミングのレイヤに関するノードのリストにおける第１のノードが選択される。
【０１２４】
次に、新たに選択されたノードからの第１のリンクが選択され（Ｓ７−３）、その後、先に説明された方法と同じ方法により処理される（Ｓ７−４〜Ｓ７−１０）。
【０１２５】
したがって、例えば、図８Ａのラティスを処理する場合、まず、ノード１０及び９が選択され、処理される。これら２つのノードに対しては、各ノードからノードＤ４へ出る１つのリンクが存在する。しかし、Ｄ４は、どのリンクに対しても開始ノードではなく、したがって、この段階では、除去されるリンク又はノードはない。
【０１２６】
次に、リンク符号化モジュール２４は、ノード８−１０間のリンクを考慮する。図８Ａの図からわかるように、ノード１０は、ノード８−１０間のリンクにより１つの終了ノードとして一度識別され、更に、ノード１０−Ｄ４間のリンクの開始ノードとして一度識別されるノードであり、リンク符号化モジュール２４は、そのことを識別する。したがって、ノード１０を開始ノード又は終了ノードとして有するリンクを考える時、リンク符号化モジュール２４は、ノード１０が一次パス上のノードであると判定する。
【０１２７】
そこで、リンク符号化モジュール２４は、写像テーブル３６の写像データから、ノード１０と、ノード８−１０間のリンク及びノード１０−Ｄ４間のリンクとを削除し、それらを、ノード８−Ｄ４との間の単一のリンクと置き換える。新たなリンクと関連付けられるリンク符号化データ４０は、シンボルＰと、削除されたノードを識別する番号１０と、削除された２つのリンクの付加コードである２つのシンボルＥＥとを含む。
【０１２８】
次に、ノードＤ４が開始ノードとして一度現れ、かつ終了ノードとして一度現れるか否かを判定するために、リンク符号化モジュール２４は、ノード８から出るリンク、この場合には、ノード８−Ｄ４間の単一のリンクを再度考慮する。この条件は当てはまらないので、ノード８−Ｄ４間のリンクのリンク符号化データは、それ以上修正されない。ノード８から出る全てのリンクの処理が完了したので、次に、リンク符号化モジュール２４は、ノード７から出るリンクを考慮する。
【０１２９】
ノード１０の処理と同様に、リンク符号化モジュール２４は、ノード７−９間のリンクが１つのノード、すなわち、開始ノードとしてただ一度現れ、かつ終了ノードとしてただ一度現れるノード９を識別する。そこで、リンク符号化モジュール２４は、ノード７−９間のリンクと、ノード９−Ｄ４間のリンクとを削除し、それを、ノード７−Ｄ４間の単一のリンクと置き換える。このリンクは、ノード９が除去されたことを特定するリンク符号化データＰ９ＥＥと関連付けられる。この段階における図６Ｅのラティスの処理は、図８Ｂにより示される。
【０１３０】
ノード９を削除した後、リンク符号化モジュール２４は、ノード７からノードＤ４に至るリンクを再度考慮し、ノード７から出るリンクをそれ以上除去できないことを判定する。
【０１３１】
その後、リンク符号化モジュール２４は、ノード６に目を向ける。ノード６の場合、ノード６から出る２つのリンクは、ノード８を識別する。すなわち、ノード８は、開始ノードとして一度識別されるだけではない。しかし、ノード６から出るリンクは、共に、ノード８にリンクするという点で同一であるため、リンク符号化モジュール２４は、それら２つのリンクを並行パスの符号化として識別し、リンクのうちの一方を削除する。その一方で、リンク符号化モジュール２４は、他方のリンクに対して、リンク符号化データを更新する。このリンク符号化データは、文字Ｍの後に、互いに付随する２つの先の符号化Ｅ及びＥが続くリンク符号化ＭＥＥである。
【０１３２】
ノード６−８間の２つのリンクのうちの一方が削除され、リンク符号化データが更新された後の図８Ｂのラティスの処理の結果を、図８Ｃに示す。
【０１３３】
次に、ノード６からノード８に至る新たな単一のリンクを考慮する。この時点で、ノード８は、リンク８−Ｄ４において一度現れる開始ノードであり、かつ、新たな単一のリンク６−８において一度現れる終了ノードであると識別される。つまり、これはノード８を削除できることを意味する。ノード６−Ｄ４間の新たなリンクに対するリンク符号化データは、削除されたノードを表現するＰ８の後に、ノード６−８間のリンク符号化データであるＭＥＥと、ノード８−Ｄ４間のリンクに対する先のリンク符号化データであるＰ１０ＥＥとが続く形態になる。
【０１３４】
図８Ｄは、この処理段階におけるラティスを示している。図８Ｄからわかるように、ノード６−Ｄ４間のリンクはコードＰ８ＭＥＥＰ１０ＥＥと関連付けられ、ノード７−Ｄ４間のリンクはコードＰ９ＥＥと関連付けられる。その他の全てのリンクは、同一のコード、すなわち、１つの文字Ｅと関連付けられる。
【０１３５】
ノード６を処理し、ノード８を除去した後、ノード６から出るリンクの処理はそれ以上実行されないので、リンク符号化モジュール２４は、ノードＤ２、Ｄ５及びＤ３のそれぞれを順次考慮する。この場合、これら３つのノードは全て、４つのリンクに対する終了ノードであるノード７に接続しているので、それらのノードを除去することは不可能である。
【０１３６】
ノードＤ２、Ｄ５及びＤ３を考慮した後、ノードＤ１が考慮される。このノードＤ１は、単一のリンクによりノード６に接続される。しかし、ノード６は、２つのリンク、すなわち、ノード７に至るリンク及びノードＤ４に至るリンクの開始ノードである。したがって、ノード６は除去されない。
【０１３７】
次に、ノード３を考慮する。このノードは、ノードＤ２に至る単一のリンクに対する開始ノードである。ノードＤ２は、リンク３〜Ｄ２において終了ノードとして一度現れるばかりではなく、単一のリンクＤ２〜７に対しても開始ノードとして一度記録される。したがって、Ｄ２は処理される。Ｄ２はダミーノードであるので、写像テーブル３６中に格納されたデータからＤ２が削除され、ノード３とノードＤ２との間のリンク及びノードＤ２とノード７との間のリンクは、ノード３とノード７との間の単一のリンクにより置き換えられる。この単一のリンクは、コードＤＥＥと関連付けられる。ここでＤはダミーノードが削除されたことを意味し、ＥＥは除去された２つのリンクと関連する２つのコードである。
【０１３８】
図８Ｅに、この処理段階におけるラティス及びリンク符号化データを示す。
【０１３９】
ノード３を処理した後、ノード５、４及び２が順次同様に処理される。この処理により、ダミーノードＤ５、Ｄ３及びＤ１はそれぞれ除去され、写像テーブル３６のリンクデータが更新される。ダミーノードＤ２の除去が処理されたときと同様の方法で、処理されたリンクと関連付けられたリンク符号化データ４０が処理される。
【０１４０】
図８Ｆは、ダミーノードＤ５、Ｄ３及びＤ１が処理され、除去された後のラティスの概略図である。この段階では、ノード２−６間のリンク、ノード３−７間のリンク、ノード５−７間のリンク、及びノード４−７間のリンクの各々は、コードＤＥＥと関連付けられる。このコードＤＥＥは、それぞれのリンクから、１つのダミーノードが除去されたことを示す。
【０１４１】
ノード２を処理した後、ノード１が選択される。ノード１−３間のリンクは、ノード１−３間のリンク及びノード２−３間のリンクの終了ノードとしてノード３を識別する。このため、ノード３を除去することは不可能である。
【０１４２】
続いて、ノード１を開始ノードとして有する次のリンクが選択される。この例では、次のリンクは、ノード１−５間のリンクになる。そこで、ノード５は、そのリンクの終了ノードとして一度現れ、かつノード５からノード７に至るリンクに対して開始ノードとして一度現れると識別される。したがって、ノード５は削除され、ノード１−７との間の新たなリンクが生成され、これがリンク符号化データＰ５ＥＤＥＥと関連付けられる。
【０１４３】
次に、ノード１−４間のリンク及びノード４−７間のリンクが同様にして処理され、ノード４が削除される。また、ノード１−４間のリンク及びノード４−７間のリンクは、ノード１からノード７に至る単一のリンクと置き換えられる。この単一のリンクは、リンク符号化データＰ４ＥＤＥＥと関連付けられる。
【０１４４】
この処理段階で格納されるラティスを、図８Ｇに示す。この段階では、ノード１を開始ノードとして有する３つのリンクのうちの２つが、同一の終了ノード、すなわち、ノード７を識別する。したがって、リンク符号化モジュール２４は、それらのリンクのうちの一方を削除し、他方のリンクの符号化データを更新する。更新後の符号化データは、Ｍの後に、削除されたリンク又は残ったリンクに対応する、長いほうの符号化データが続き、更にその後に、残ったリンク又は削除されたリンクに対応する、短いほうの符号化データが続く形態を有する。
【０１４５】
この例では、更新後の符号化データは、ＭＰ５ＥＤＥＥＰ４ＥＤＥＥとなる。この処理段階におけるラティスを、図８Ｈに示す。この段階では、ノード１から出るリンクにより識別されるノードは、いずれも、削除できないため、次に、ノード０から出るリンクを考慮する。ノード０を開始ノードとして有するリンクにより識別されるノードは、いずれも、削除できず、ノード０は最終ノードであるため、リンク符号化モジュールの処理は完了する。
【０１４６】
したがって、この段階において、図８Ｈの例のラティスの場合、次に示すデータが写像テーブル３６に格納される。
【０１４７】
写像データ
レイヤ番号 ノード
１          ［０］
２          ［２，１］
３          ［３］
４          ［６］
５          ［７］
６
７          ［Ｄ４］
リンクデータ
（０，２）、（０，１）、（２，６）、（２，３）、（１，３）、（１，７）、（３，７）、（６、Ｄ４）、（６，７）、（７，Ｄ４）
【０１４８】
また、リンク符号化４２は、上記の各リンクを、下記のリンク符号化データとそれぞれ関連付ける。
Ｅ，Ｅ，ＤＥＥ，Ｅ，Ｅ，ＭＰ５ＥＤＥＥＰ４ＥＤＥＥ，ＤＥＥ，Ｐ８ＭＥＥＰ１０ＥＥ，Ｅ，Ｐ９ＥＥ
【０１４９】
第１レイヤ及び最終レイヤのノードと、簡易化写像において少なくとも３つの他のノードに接続されたノードのみが残るように、リンク符号化モジュール２４は、ラティスから全ての一次パス及び全ての並行パスを除去する。除去後、残った簡易化ラティスは、以下に説明するように、シェイプ符号化モジュール２６により符号化される。
【０１５０】
（シェイプ符号化モジュールにより実行される処理）
以下、図９Ａ及び図９Ｂ、並びに図１０Ａ、図１０Ｂ及び図１０Ｃを参照して、シェイプ符号化モジュール２６の処理を詳細に説明する。図９Ａ及び図９Ｂは、シェイプ符号化モジュール２６により実行される処理動作のフローチャートである。図１０Ａ、図１０Ｂ及び図１０Ｃは、図８Ｈのラティスの符号化を示す概略図である。
【０１５１】
先述したように、リンク符号化モジュール２４は、ラティス構造におけるリンクと関連付けられたリンク符号化データ４０の形態でラティスの部分を符号化するために、写像テーブル３６中の写像データ及びリンクデータ４０により特定されるラティス構造を簡易化する。なお、そのラティスの部分とは、ノード間の一次パス及び並行パスに対応し、それらパスは、それらノード自体にのみ接続し、ラティスの他のどの部分にも接続しない。したがって、リンク符号化モジュール２４による処理の結果は、ラティスの始まりと終わりにあるノード（図８Ｈのラティスの場合、ノード０及びノードＤ４）を除いて、全てのノードが少なくとも他の３つのノードに接続されているようなラティス構造である。更に、簡易化ラティス構造においては、ノード間のリンクはいずれも重複しない。すなわち、どの対のノードの間にも、２つ以上のリンクは存在しない。
【０１５２】
リンク符号化モジュール２４により、簡易化ラティス構造が生成された後、リンク符号化モジュール２４により処理された元のラティス構造の完全表現が、シェイプ符号化モジュール２６により、３つのデータセットの形態で生成される。それら３つのデータセットは、シェイプ符号化データ４２と、リンクリスト４３と、ノードリスト４４である。シェイプ符号化データ４２は、リンク符号化モジュール２４により生成された簡易化ラティスのシェイプを符号化する。リンクリスト４３は、簡易化ラティスにおけるリンクに対して判定されたリンク符号化データ４０の連結リストである。ノードリスト４４は、リンク符号化モジュール２４により処理された元のラティス構造における全てのノードの順序付きリストを含む。
【０１５３】
本実施形態においては、シェイプ符号化データ４２は、簡易ラティスにより規定される区域ごとに、３桁の数字のコードを含む。この３文字のコードのうちの第１の数は、区域がラティス上のどの場所に付随しているかを特定し、次の２つの数は、符号化された区域におけるリンクの数を特定する。
【０１５４】
したがって、例えば、図１０Ａ〜図１０Ｃを参照すると、以下詳細に説明するように、図８Ｈのラティスを処理する場合、まず、図１０Ａにおいて陰影を付けられたノード０、２、３、１の区域が、シェイプ符号化データ０，２，２により包囲される。ここで、０はオフセット値を示し、２，２は、符号化シェイプを規定するパス０，２，３と０，１，３におけるリンクの数を特定する。
【０１５５】
次に符号化対象の区域のオフセットを求める。この例では、次の区域は２、６、７、３である。ノード０に対するノード２のオフセットは１であるから、シェイプ符号化データは１，２，２となる。この段階で符号化された区域は、図１０Ｂにおいて、陰影を付けられたノード及び実線の矢印により示される。
【０１５６】
その後、次の区域６、Ｄ４、７が特定され、この区域は、図１０Ｃにより示されるように符号化される。次に、符号化されていない最後の区域１、３、７が識別され、その区域の最後の３桁の数字のコードが生成される。
【０１５７】
以下詳細に説明するように、完全なシェイプ符号化データ４２、リンクリスト４３及びノードリスト４４が生成されると、データ記憶装置２０に格納された音声ノードデータ３０により定義されるラティス構造に対応する最終ラティス構造を確定するために、それらのデータは、復号化モジュール２８により処理される。その後、シェイプ符号化データ４２及びリンクリスト４３は、ノードリスト４４に対応する順序で順序付けられたノードと関連付けられた追加データ、並びに復号化モジュール２８により生成される最終ラティス構造により判定される順序で順序付けられた音声リンクデータ３２により、ノードにおけるリンクと関連付けられたデータと共に、出力モジュール２９により出力される。
【０１５８】
図９Ａを参照すると、まず、第１のノードのレイヤに関するノードのリストにおける単一のノードを識別する（Ｓ９−１）。このノードを識別する番号はノードリスト４４に追加されると共に、上方境界（upper boundary）及び下方境界（lower boundary）に関するリストにも追加される。更に、その番号は、現在のノードと、最後に処理されたノードの双方として識別されるように設定される。
【０１５９】
したがって、例えば、図８Ｈのラティスの場合、第１のノードが０である時、次のデータが格納される。
【０１６０】
最後に処理されたノード  ０
現在のノード            ０
ノードリスト          ［０］
上方境界              ［０］
下方境界              ［０］
【０１６１】
次に、シェイプ符号化モジュール２６は、写像テーブル３６中のリンクデータにより識別される１または２以上のリンクが、現在のノードを開始ノードとして識別するか否かを判定する（Ｓ９−２）。
【０１６２】
写像テーブル３６中のリンクデータにより、現在のノードを開始ノードとして有するリンクが１つしか識別されない場合、これは、ラティスのうち、現在のノードにすぐ隣接する部分が、１または２以上の並行パス又は一次パスを表す複数のリンク又はノードを含むことを示す。この条件が当てはまるならば、シェイプ符号化モジュール２６は、最後に処理されたノードの値を現在のノードの値と比較する（Ｓ９−３）。最初のノードを処理する時のように、それら２つの数が等しい場合、シェイプ符号化モジュール２６は、データ記憶装置に格納されたシェイプ符号化データに、０に設定されたオフセット値と、数字１，１を含む数字から成るストリングを追加する（Ｓ９−３）。２つの値が等しくない場合には、以下に詳細に説明するように、異なるオフセット値が計算される。
【０１６３】
次に、シェイプ符号化モジュール２６は、処理中である現在リンク、すなわち、現在のノードを開始ノードとして有する単一のリンクと関連するリンク符号化データ４０を選択し、そのリンクと関連するリンク符号化を利用して、リンクリスト４３及びノードリスト４４を更新する（Ｓ９−４）。特に、処理中であるリンクに関するリンク符号化データ４０に何らかの数字が現れる場合、それらの数字は、リンク符号化においてそれらの数字が現れる順に、ノードリストに追加される。次に、それらの数字が除去された、リンク符号化の残る部分は、リンクリスト４３に追加される。
【０１６４】
次に、最後に処理されたノードがリンクの最終ノードとして識別されるノードに設定され、現在のノード、上方境界及び下方境界のリストが全て、この終了ノードのみを識別するようにリセットされる（Ｓ９−５）。次に、終了ノードは、ノードリスト４４の終わりに付加される。
【０１６５】
したがって、例えば、下記のリンク符号化ＭＰ４ＥＥＰ３ＥＥＥと関連付けられる単一のリンク（０，５）を有するノード０の場合、最後に処理されたノード、現在のノード、ノードリスト４４、リンクリスト４３、シェイプ符号化データ４２、上方境界及び下方境界は、更新後、次のようになる。
【０１６６】
最後に処理されたノード  ５
現在のノード            ５
ノードリスト          ［０，４，３，５］
リンクリスト          ［ＭＰＥＥＰＥＥＥ］
シェイプ符号化        ［０，１，１］
上方境界              ［５］
下方境界              ［５］
【０１６７】
図８Ｈの例のラティスでは、ノード０は、２つのリンク、すなわち、ノード０−２間のリンク及びノード０−１間のリンクにより接続される。このラティスの場合のように、写像テーブル３６中のリンクデータにより識別されるリンクで、現在のノードが２回以上開始ノードとして現れると、シェイプ符号化モジュール２６が判定した（Ｓ９−２）場合、シェイプ符号化モジュール２６は、符号化対象のラティスの区域に対して、上方パス及び下方パスを識別する（Ｓ９−６）。
【０１６８】
特に、シェイプ符号化モジュール２６は、まず、写像テーブル３６の順序付きリンクデータにより識別され、現在のノードを開始ノードとして有する最後の２つの未処理リンクを識別する。
【０１６９】
したがって、図８Ｈのラティスの場合、ノード０−２間のリンク及びノード０−１間のリンクが特定される。次に、それらのリンクを特定するデータが、符号化対象の区域のパスデータとして、シェイプ符号化モジュール２６により格納される。
【０１７０】
特に、順序付きリンクデータにおいて後の順序のリンクを識別するデータが、下方パスを識別するパスに追加され、他方のリンクを識別するデータは、上方パスのデータに追加される。
【０１７１】
したがって、例えば、図８Ｈのラティス構造の場合、下記のデータが格納されることになる。
【０１７２】
上方パス：［０，２］
下方パス：［０，１］
【０１７３】
次に、上方パスと下方パスにおける最終ノードにより識別されるノードのレイヤ番号を比較する。上方パスリストの最終ノードが下方パスリストの最終ノードより早いタイミングデータ３４のレイヤに対応する場合、上方パスリストが処理される。そうでない場合には下方パスが処理される。
【０１７４】
上方パスが処理される時、上方パスの最終ノードを開始ノードとして有するリンクが特定される。上記のパス及び図８Ｈのラティス構造の場合、リンク２−６及びリンク２−３が特定される。次に、上方パスの最終ノードを開始ノードとして有する順序付きリンクデータにおいて最も遅い順番のリンクの最終ノードにより特定されるノードが識別される。次に、識別されたノードは、上方パスリストの終わりに追加される。したがって、図８Ｈのラティス構造の場合、上方パスリストは、［０，２，３］になるように更新される。
【０１７５】
下方パスが処理される時には、下方パスの最終ノードを開始ノードとして有するリンクが特定され、最終ノードを開始ノードとして有する順序付きリンクデータにおいて最も早い順番のリンクが特定される。次に、このようにして特定されたリンクの最終ノードが、下方パスのノードのリストに追加される。
【０１７６】
上方パスと下方パスのノードのリストにおける最終ノードが一致するまで、このプロセスが繰り返される。したがって、例えば、図８Ｈのラティスの場合、ノード０、２及び３を含む上方パスと、ノード０、１及び３を含む下方パスが特定され、格納される。次に、シェイプ符号化モジュール２６により格納された上方境界及び下方境界は、特定されたそれらの上方パスと下方パスにそれぞれ対応するように更新される。
【０１７７】
次に、シェイプ符号化モジュール２６は、特定されたパスを利用して、シェイプ符号化データ４２を更新する（Ｓ９−７）。特に、最後に処理されたノードデータと、現在のノードとを比較して、オフセット値を判定する。ラティスの第１の区域を処理する場合のように、それら２つの数が等しい時には、オフセットを０と判定する。次に、現在リストの終わりに、判定したオフセット値と、上方パスにおけるリンクの数及び下方パスにおけるリンクの数を特定する数とを含む３つの数のリストを追加することにより、シェイプ符号化を更新する。したがって、図８Ｈのノード０、２、３及び１により識別される区域の場合、上方パスと下方パスに２つのリンクを有する区域を示す［０，２，２］のシェイプ符号化が格納される。
【０１７８】
次に、上方パスと下方パスにより特定されるリンクと関連するリンクデータが識別され（Ｓ９−８）、処理され（Ｓ９−９）、その後、リンクリスト４３及びノードリスト４４が更新される。
【０１７９】
特に、更新された上方パスリストにより特定される第１のノードから始めて、上方境界リストの最初の２つの番号により特定される第１のリンクが特定される。図８Ｈのラティスの場合、これは、ノード０−２間のリンクになる。次に、このリンクと関連するリンク符号化に現れるノード番号が全てノードリストに追加され、かつそれらの番号が除去されたリンク符号化データがリンクリストに追加されるように、このリンクと関連するリンクデータが処理される。
【０１８０】
図８Ｈにおいて、０−２間のリンクにより特定されるリンク符号化データの場合、このリンクは、単一のシンボルである文字Ｅを含むので、ノードリストにノードは追加されず、リンクリストに文字Ｅが追加される。次に、上方パスリストにおける次のノードがノードリストに追加され、ノードの上方パスリストにより、そのノードからのリンクとして特定されるリンクが、先述の方法と同じ方法で処理される。上方パスリストの全てがこのようにして処理された時、下方パスリストの最後の２つのノードの間の最終リンクが完全に処理されるまで、下方パスリストが同様に処理される。
【０１８１】
したがって、例えば、図８Ｈのラティス構造を処理する場合、この段階で、下記のデータが格納される。
【０１８２】
最後に処理したノード  ０
現在のノード          ０
ノードリスト        ［０，２，３，１］
リンクリスト        ［ＥＥＥＥ］
シェイプ符号化      ［０，２，２］
上方境界            ［０，２，３］
下方境界            ［０，１，３］
【０１８３】
リンクリスト及びノードリストが更新された後、シェイプ符号化モジュール２６は、現在のノードが、上方境界リスト及び下方境界リストの最終番号により識別されるノードに対応するか否かを判定する（Ｓ９−１０）。対応する場合、あるいは、処理中である現在のノードから出る単一のリンクを処理し終わった後（Ｓ９−２、Ｓ９−５）、シェイプ符号化モジュール２６は、処理中である現在のノードが、写像テーブル３６中の写像データの最終レイヤにおける単一のノードを識別するか否かを判定する（Ｓ９−１１）。最終レイヤのノードを識別する場合、シェイプ符号化モジュール２６により、ラティス構造全体が符号化されたことになり、シェイプ符号化モジュール２６の処理は終了する。
【０１８４】
しかし、現在のノードが、写像テーブル３６中の写像データにより識別される最終レイヤのノードを識別しない場合には、シェイプ符号化モジュール３６は、現在のノードを開始ノードとして有するリンクの数を判定し、次に、それらのリンクを先述のように処理する（Ｓ９−２〜Ｓ９−１０）。
【０１８５】
現在のノードが、上方境界リスト及び下方境界リストの最終ノードを識別しない場合、シェイプ符号化モジュール２６は、現在のノードが、まだ処理されていないいずれかのリンクと関連するか否かを判定する（Ｓ９−１２）。
【０１８６】
関連しない場合、シェイプ符号化モジュール２６は、処理する別のノードを選択する（Ｓ９−１３）。
【０１８７】
特に、現在のノードが、上方境界リストの最後の２つのノードを除く、上方境界リスト中のノードのうちの１つに対応する場合、処理する次のノードは、上方境界リストにおける次のノードであるとして選択される。現在のノードが、上方境界リストにおいて最後から２番目のノードを識別する場合、選択される次のノードは、下方境界リストにおける第２のノードである。現在のノードが、最初のノード番号を除く、下方境界リストの番号のいずれかにより識別されるノードである場合には、下方境界リストの次のノードが選択される。したがって、図８Ｈのラティスの場合、ノード０から出る全てのリンクが処理された後、選択される次のノードは、ノード２になる。
【０１８８】
現在のノードが更新された後、シェイプ符号化モジュール２６は、現在のノードが、上方境界リスト及び下方境界リストにおける最終ノードを識別するか否かを判定する（Ｓ９−１０）。その後、シェイプ符号化モジュール２６は、全てのノードが完全に処理されたか否かを判定する（Ｓ９−１１）か、あるいは、新たに選択されたノードが、まだ処理されていないリンクの開始ノードであるか否かを判定する（Ｓ９−１２）。
【０１８９】
現在のノードが、まだ処理されていないリンクの開始ノードであると判定された（Ｓ９−１２）場合、未処理リンクを含む区域の上方パス及び下方パスが判定される（Ｓ９−１４）。
【０１９０】
特に、現在のノードが上方境界リストにある場合、現在のノードを開始ノードとして有し、かつ現在のノードの次のノードを上方境界リストに有するリンクが特定される。このリンクは、処理する次の区域に対して、下方パスの最初の２つのノードを設定するために使用される。したがって、図８Ｈのラティスの場合、ノード０、２、３、１により規定される区域が符号化され、ノード２が処理された後、ノード２及び３が、下方パスリストにおける最初のノードとして設定される。
【０１９１】
次に、現在のノードを開始ノードとして有する、順序付きリンクデータの末尾に最も近い未処理リンクが、上方パスに追加すべきノードを識別するために使用される。図８Ｈのラティスの場合、これはリンク（２，６）になり、したがって、上方パスは、リスト［２，６］になるように設定されることにより、更新される。
【０１９２】
現在のノードが、上方境界リスト中の番号により識別されない場合には、現在のノード及び下方境界リスト中の次のノードにより識別されるリンクが、上方パスリストの始まりとして設定され、順序付きリンクデータの先頭に最も近く、かつ現在のノードを開始ノードとして有する次の未処理リンクが、下方パスリストの始まりを設定するために使用される。
【０１９３】
次に、符号化する区域に対して、上方パスリスト及び下方パスリストの残る部分が、先にステップ（Ｓ９−６）に関連して説明された方法と同じ方法で判定される。したがって、図８Ｈのノード２を開始ノードとして有する区域の場合、ノード［２，６，７］及びノード［２，３，７］を識別する上方パス及び下方パスが判定される。
【０１９４】
次に、シェイプ符号化モジュール２６は、計算された上方パス及び下方パスにより規定される区域を、この段階で符号化できるか否かを判定する（Ｓ９−１５）。これを判定するために、まず、シェイプ符号化モジュール２６は、上方境界リスト中のノードにより現在のノードが識別されるか否かを検査する。識別される場合、シェイプ符号化モジュール２６は、現在の区域の下方パスが、上方境界リストにより識別されるノードのみを含むか、又は上方境界リストにおいて、現在のノードから上方境界リストの終わりに至るまでの全てのノードを含むかを判定する。この条件に当てはまる場合、区域は符号化可能である。
【０１９５】
現在のノードが上方境界リストのノードのいずれにも対応しない場合には、シェイプ符号化モジュール２６は、区域に対して判定された上方パスが、下方境界リストにより識別されるノードのみを含むか、又は下方境界リストにおいて、現在のノードから下方境界リストの終わりに至るまでの全てのノードを含むかを判定する。この条件に当てはまる場合、区域は符号化可能である。
【０１９６】
この段階で、現在の区域を符号化することが不可能であると判定された（Ｓ９−１５）場合、ノードと、そのノードと関連する上方パス及び下方パスは格納され（Ｓ９−１６）、境界上にある、現在のノードの次のノードが処理のために選択される（Ｓ９−１３）。
【０１９７】
シェイプ符号化モジュール２６が、現在のノードの区域を符号化できると判定した（Ｓ９−１５）場合、シェイプ符号化モジュール２６は、現在のノードの値及び最後に処理されたノードの値からのオフセット値を判定し、シェイプ符号化に判定されたオフセットに対応する数と、処理中のノードと関連する上方パス及び下方パスにおけるリンクの数を識別する数とを追加する。
【０１９８】
シェイプ符号化モジュール２６により判定されるオフセットは、以下に図１０Ａを参照して詳細に説明するように、ステップ（Ｓ９−３）及び（Ｓ９−７）についてオフセットが判定される方法と同じ方法で判定される。
【０１９９】
先に述べたように、現在のノードが最後に処理されたノードと等しくなるように設定されるたびに、シェイプ符号化モジュール２６により生成されるシェイプ符号化に対するオフセット値は、０に設定される。
【０２００】
最後に処理されたノードの番号と、現在のノードの番号が等しくない場合、オフセット値は、次のように計算される。まず、上方境界リストをコピーし、そのリストに現れる最終ノードを除去した後、下方境界リストを逆の順序で付加することにより、オフセットリストが生成される。
【０２０１】
したがって、図１０Ａにおいて、陰影を付けられた円により示される境界の場合、境界におけるノードを識別する番号［０，２，３，１］を含むオフセットリストが生成される。
【０２０２】
次に、最後に処理されたノードから始めて、オフセットリストにより識別される順序でノードを巡って時計回り方向又は反時計回り方向に進むことにより現在のノードに到達するまで、順にノードをたどる、境界を巡るステップの数が判定される。
【０２０３】
時計回り方向に進むステップの数が、反時計回り方向に進むステップの数より小さい場合、これがオフセットの値である。反時計回り方向に進むステップの数が、時計回り方向に進むステップの数より小さい場合、オフセットは、ステップの数に対応する負の数に設定される。
【０２０４】
したがって、例えば、図１０Ａに示されるように、図中、０が、＊で特定される最後に処理されたノードであり、かつ上方境界がノード０、２、３を含み、下方境界はノード０、１、３を含む時、図中の陰影を付けられた円の上方の数により示されるように、ノード２のオフセットは１であり、ノード３のオフセットは２であり、ノード１のオフセットは−１である。これらの数は、最後に処理されたノード、すなわち、ノード０に対する、境界上の各ノードの位置を一意性をもって識別する。
【０２０５】
シェイプ符号化データ４２が更新された後、シェイプ符号化モジュール２６は、境界リストを更新する（Ｓ９−１９）。
【０２０６】
特に、シェイプ符号化モジュール２６は、まず、現在のノードとして識別されるノードが上方境界リストにあるか否かを判定する。上方境界リストにある場合、符号化されるべき区域に対して判定された下方パスのリンクの数が、現在のノードから、上方境界リストの終わりにあるノードに至るまでのリンクの数と比較される。
【０２０７】
下方パスのリンクの数が、処理中である現在のノードを上方境界リストの最終ノードから離間させているリンクの数より多い場合、下方パスの終わりで上方境界リスト中の最終ノードから現在のノードを離間させているノードを超過するノードの数が、下方境界リストに付加される。
【０２０８】
したがって、例えば、図１０Ａにおいてノード２、６、７、３により規定される区域を処理する場合、ノード０、２、３及び１により規定される区域は既に処理されており、処理する区域の下方パス［２，３，７］は、現在のノードであるノード２を、上方境界リスト［０，２，３］の終わりから離間させているリンク、すなわち、１つのリンクより多いリンクを含むので、下方境界は、最終ノードであるノード７を追加することにより、符号化されるべき区域の下方パスから更新される。したがって、この場合、下方境界は、［０，１，３，７］となる。
【０２０９】
次に、現在のノードからリストの終わりに至る全てのノードを削除させ、かつ上方パスリストを短縮された上方境界リストに付加することにより、上方境界リストが修正される。
【０２１０】
したがって、ノード２、６、７及び３により規定される区域を処理する場合、現在のノードが２である時、上方境界は、元来、［０，２，３］であるので、まず、上方境界が短縮されて、［０］となる。次に、上方パス［２，６，７］がこの短縮リストに付加されるので、上方境界リストは、［０，２，６，７］となる。図１０Ｂにおいて、陰影を付けられたノードは、この段階で境界リストに含まれるノードである。
【０２１１】
処理中である現在のノードが、上方境界リストのノードに対応しない場合には、現在のノードを下方境界リストにおける最終ノードから離間しているリンクの数が判定される。次に、このリンク数を超過している上方パスのリンクの数が判定される。次に、上方パスリストの終わりに現れる、この数に対応するノードの数が、上方パス境界を識別するノードのリストに付加される。その後、現在のノード又は後続するノードを含む下方境界のノードが削除され、下方パスリストが下方境界リストに付加される。
【０２１２】
境界が更新された後、ラティスの符号化済み区域に追加されたリンクが識別される（Ｓ９−２０）。それらのリンクは、上方境界リスト及び下方境界リストにそれぞれ追加されたリンクを含む。したがって、図１０Ａのノード２、６、７、３により規定される区域を処理する場合、ノード０、２、３、１により規定される区域が符号化された後、追加リンクは、３−７間のリンク、２−６間のリンク、及び６−７間のリンクを含む。
【０２１３】
符号化する区域が上方境界の現在のノードと関連している場合、それらのリンクは、下方境界に追加されたリンクの順序で、次に、上方境界に追加されたリンクの順序で順序付けされる。したがって、上記の場合においては、リンクは３−７，２−６、及び６−７として順序付けされる。現在のノードが上方境界リストにない場合には、上方境界に追加されたリンクは、下方境界に追加されたリンクの前に配置される。
【０２１４】
次に、これらの各リンクのリンクデータは、先にステップ（Ｓ９−５）及び（Ｓ９−９）に関連して説明された方法と同じ方法で順次処理される（Ｓ９−２１）。このとき、リンクごとの終了ノードが、まだ、ノードリストに追加されていない場合には、リンクデータが処理された後、このノードは、ノードリストにノードとして追加される。次に、最後に処理されたノードが、現在のノードの値と等しくなるように更新される。
【０２１５】
したがって、図８Ｈのノード２、６、７、３により規定される区域を符号化する場合、ノード０、２、３、１により規定される区域が符号化された後、この段階で、下記のデータが格納される。
【０２１６】
最後に処理されたノード  ２
現在のノード            ２
ノードリスト          ［０，２，３，１，７，６］
リンクリスト          ［ＥＥＥＥＤＥＥＤＥＥＥ］
シェイプ符号化        ［０，２，２，１，２，２］
上方境界              ［０，２，６，７］
下方境界              ［０，１，３，７］
【０２１７】
リンクリスト及びノードリストと、最後に処理されたノードとが更新された後、シェイプ符号化モジュール２６は、境界上のいずれかのノードが後に処理されるようにスケジューリングされているか否かを判定する（Ｓ９−２２）。スケジューリングされている場合、符号化を拒否された最後の区域が選択され（Ｓ９−２３）、その区域について、オフセット及びシェイプ符号化が判定される。この時、現在のノードは、選択されたノードに設定され、そのノードに対して判定された上方パスデータ及び下方パスデータが処理される。次に、上方パスデータ及び下方パスデータを利用して、シェイプ符号化モジュール２６により格納された境界データ、シェイプ符号化データ、ノードリスト、リンクリスト及びその他のデータが、先に説明されたように（Ｓ９−１８〜Ｓ９−２２）更新される。
【０２１８】
後に処理されることがスケジューリングされる全てのノードが処理された場合、シェイプ符号化モジュール２６は、現在選択されているノードが、まだ処理されていない、区域を符号化する（Ｓ９−１２）可能性がある別のリンクを有するか否かを判定し、次に、それらのリンクを処理する（Ｓ９−１４〜Ｓ９−２３）か、又は境界上の次のノードを選択し（Ｓ９−１３）、その後、そのノードを先述した方法により処理する（Ｓ９−１０〜Ｓ９−２３）。
【０２１９】
したがって、このようにして簡易化ラティスを処理することにより、ラティスにより規定される各区域が順次、符号化される。図１０Ａ、図１０Ｂ及び図１０Ｃを参照すると、例えば、図１０Ａにおいて陰影を付けられた丸で特定される区域が符号化された後、符号化すべきノードとして次に選択されるノードは、先に符号化された区域の開始ノードであるノード０に対して１のオフセット値を有するノード２である。次に、ノード２と、リンク２−６，６−７，３−７、及び２−３により特定される区域が符号化され、それにしたがって、図１０Ｂに示されるように、境界が更新される。
【０２２０】
この段階で、ノード２は現在のノードになり、境界のノードは、図１０Ｂにおいて陰影を付けられたノードを含む。
【０２２１】
未処理リンクと関連する境界上の次のノードが判定される時、ノード６が識別される。次に、ノード２に対するノード６のオフセットが判定される。この場合、図１０Ｂの丸の上方の数により示されるように、オフセットは１になる。次に、ノード１、６、Ｄ４、７により特定される区域が符号化される。
【０２２２】
上方境界が全て処理された後、下方境界のノードが順次考慮され、未処理リンクに付随する、下方境界の第１のノード、すなわち、ノード１が識別される。次に、ノード６に対するオフセット値が判定される。図１０Ｃに示される丸の上方の数により示されるように、オフセット値は−３である。次に、ノード１、３、７により特定されるシェイプのシェイプ符号化が判定され、リンクリスト及びノードリストが、先述のように更新される。ノード１が考慮された後、最終ノード、すなわち、ノードＤ４に到達するまで、ノード７及びノードＤ４が順次考慮される。ノードＤ４に到達した時点で、それ以上の符号化は実行不可能になる。
【０２２３】
このプロセスの終了時に、下記のデータが格納される。このとき、ラティスにおけるリンクのリンク符号化は、図８Ｈにおいて識別されるリンクに対応する。
【０２２４】
ノードリスト    ［０，２，３，１，７，６，９，Ｄ４，８，１０，５，４］
リンクリスト    ［ＥＥＥＥＤＥＥＤＥＥＥＰＥＥＰＭＥＥＰＥＥＭＰＥＤＥＥＰＥＤＥＥ］
シェイプ符号化  ［０，２，２，１，２，２，１，１，２，−３，２，１］
ダミーノード    ［Ｄ１，Ｄ２，Ｄ３，Ｄ４，Ｄ５］
ダミーリンク    （５〜７）
クロスリンク    （５〜７）
【０２２５】
次に説明するように、このデータは、復号化モジュール２８が、図６Ａに示される元の符号化ラティス構造を表すラティス構造を生成するのに十分なデータである。
【０２２６】
次に、図１１Ａ〜図１１Ｄ、図１２及び図１３Ａ〜図１３Ｇを参照して、ラティス構造を再生するための復号化モジュール２８の処理を詳細に説明する。
【０２２７】
（復号化モジュールにより実行される処理）
図１１Ａを参照すると、ラティス構造全体に対するノードリスト４４、リンクリスト及びシェイプ符号化データ４２がシェイプ符号化モジュール２６により判定されると、復号化モジュール２８は、データ記憶装置２０に格納されたノードリスト４４、リンクリスト４３、シェイプ符号化データ４２、ダミーノード／ダミーリンク３８及びクロスリンクデータ３９により、ラティス構造の別の表現を生成する。
【０２２８】
具体的には、復号化モジュール２８は、まず、ノードリストから第１のノードを読み出す（Ｓ１１−１）。読み出されたノードは、ラティス構造における第１のノードのノード番号となる。その後、復号化モジュール２８は、生成されるべきラティス構造の第１レイヤに対するノードのリストを生成する。このリストは、ノードリストから読み出されたノード番号を含む。
【０２２９】
したがって、上記ノードリストの場合、ノードリスト４４の第１のノードがノード０である時、第１のレイヤに対する写像データの項目のための、ノード［０］のリストを含むノードリストが生成される。
【０２３０】
次に、復号化モジュール２８は、初期上方境界リスト及び初期下方境界リストを生成する。この２つのリストは、共に、単一の要素を有するリストで構成される。その要素とは、ノードリスト４４から読み出されたノードの番号である。また、復号化モジュール２８は、ノードリストから読み出されたノードと等しくなるように、最後に処理されたノード及び現在のノードを設定する。
【０２３１】
この段階において、復号化モジュール２８は、データ記憶装置２０に格納された下記のデータを有する。
【０２３２】
最後に処理されたノード  ０
現在のノード            ０
ノードリスト          ［２，３，１，７，６，９，Ｄ４，８，１０，５，４］
リンクリスト          ［ＥＥＥＥＤＥＥＤＥＥＥＰＥＥＥＰＥＥＭＰＥＤＥＥＰＥＤＥＥ］
シェイプ符号化        ［０，２，２，１，２，２，１，１，２，−3，２，１］
ダミーノード          ［Ｄ１，Ｄ２，Ｄ３，Ｄ４，Ｄ５］
ダミーリンク          （５〜７）
クロスリンク          （５〜７）
上方境界              ［０］
下方境界              ［０］
写像データ
レイヤ１              ［０］
リンクデータ            なし
【０２３３】
復号化モジュール２８は、シェイプ符号化から次の番号を読み出し（この場合、値は０）、現在のノード番号を更新する（Ｓ１１−２）。
【０２３４】
更に具体的には、シェイプ符号化から読み出された番号が０である場合、これ以上の処理は実行されない。番号が０でない場合、次に説明するように、現在のノードを更新する。
【０２３５】
まず、シェイプ符号化から読み出された番号が、正又は負の数のいずれの場合も、上方境界リスト及び下方境界リスト内で現在のノードの位置が識別される。
【０２３６】
シェイプ符号化から読み出された番号が正の数であり、且つ現在のノード番号が上方境界リストのノードを識別する場合、そのリスト中に更にあるノードの数が識別され、それに応じて現在のノードが更新される。現在のノードが上方境界リストにあり、かつシェイプ符号化から読み出された番号が負の数の場合、復号化モジュール２８は、そのリストの先頭に向かってカウントする。シェイプ符号化の番号に対応するノードの数が読み出された時、読み出された最終番号が識別され、それに応じて現在のノードが更新される。
【０２３７】
正の数の場合に、上方境界リストの先頭又は末尾のいずれかに到達すると、必要数のノードがカウントされるまで、下方境界リストの末尾からそのリスト中のノードの残りの数をカウントしながら、次に続くノードが考慮される。一方、負の数の場合に、リストの先頭に到達すると、ノードの残りの数分、下方境界リストの先頭からその数のノードが順次考慮される。
【０２３８】
現在のノードが上方境界リストに現れない場合、下方境界リストの現在のノードの位置が識別される。この時、シェイプ符号化から読み出された番号が正の数であるとすると、下方境界リストの先頭に向かって、その数のノードが読み出され、読み出された最終ノードは、現在のノードを更新するのに使用される。シェイプ符号化から読み出された番号が負の数であり、かつ現在のノードが上方境界リストに現れない場合、シェイプ符号化の番号により表される数のノードが、現在のノードから、下方境界リストの末尾に向かって読み出される。
【０２３９】
下方境界リストの先頭又は末尾に到達すると、シェイプ符号化リストにより識別される数のノードが全て考慮されるまで、上方境界リストから（正の数の場合は先頭から、負の数の場合は末尾から）更にノードをカウントする。現在のノードの値は、境界リストにおいて識別されたこの最終ノードと等しくなるように設定される。
【０２４０】
現在のノードデータが更新された（Ｓ１１−２）後、復号化モジュール２８は、シェイプ符号化リストから次の２つの番号を読み出す（Ｓ１１−３）。この上記シェイプ符号化リストの例では、この２つの番号は、２、２になる。
【０２４１】
シェイプ符号化リストの次の２つの番号が読み出された後、復号化モジュール２８は、読み出された２つの番号が共に１であるか否かを判定する（Ｓ１１−４）。
【０２４２】
共に１である場合、復号化モジュール２８は、リンクリスト４３から読み出されたシンボルＥの数が他のシンボルの数を超えるまで、リンクリスト４３からシンボルを読み出す（Ｓ１１−５）。これにより、リンク符号化モジュール２４により生成された簡易化ラティスの複数のリンクのうち１つのリンクに対するリンク符号化データが構成される。リンクリスト４３から読み出されたリンク符号化データは、図１２を参照して以下に詳細に説明するように処理される。なお、図１２は、リンク符号化により表現される符号化ラティスの一部を再生するための、復号化モジュール２８によるリンクリスト４３のリンク符号化データの処理を示すフローチャートである。
【０２４３】
図１２を参照すると、まず、復号化モジュール２８は、現在のノードが上方境界リストのノードに対応するか否かを判定する（Ｓ１２−１）。対応する場合に、リンク符号化を処理する時、生成されるべきラティス構造に対する写像データに追加されたノードは、各レイヤのリストの先頭に追加される。対応しない場合、新たに追加されたノードは、写像データのリストの末尾に追加される。
【０２４４】
次に、開始ノードとして追加された最後のノードと、ヌルの終了ノードとを識別するリンクデータが生成される。リンクリストから読み出されたリンク符号化データは、新たに生成されたリンクデータ及び生成されたリンクの開始ノードを含むレイヤを識別するレベルデータと関連付けられる。復号化モジュール２８は、リンク符号化データと関連付けられた各リンクを順次処理する。
【０２４５】
特に、復号化モジュール２８は、まず、処理中のリンク符号化データの第１のシンボルが文字Ｄであるか否かを判定する（Ｓ１２−２）。文字Ｄである場合、復号化モジュール２８は、リンクと関連付けられたレベルデータを増分し、そのリンクに対するリンク符号化データから、リンク符号化データの最初の２つのシンボルを削除する。
【０２４６】
リンクに関連付けられたリンク符号化データの第１のシンボルが文字Ｄでない場合、復号化モジュール２８は、第１のシンボルが文字Ｐであるか否かを判定する（Ｓ１２−４）。文字Ｐである場合、ノードリストの次の要素が読み出される。更に、ノードリストから読み出されたノード番号を終了ノードとして識別するために、処理中のリンク符号化と関連付けられたリンクデータが更新される（Ｓ１２−５）。
【０２４７】
その後、リンクと関連付けられたデータよりも１つ大きい番号のレイヤに対するノードリストが、リンクに対する終了ノードを含むように更新される。
【０２４８】
開始ノードとして新たに読み出されたノードと、ヌルの終了ノードとを有する新たなリンクデータが生成され、リンクの開始ノードを含むレイヤを識別するレベルデータと関連付けられる。リンクと関連付けられた処理中のリンク符号化データは、第１のシンボル、すなわち、文字Ｐをリンク符号化データから削除することにより更新される。残るリンク符号化データにおけるシンボルは、読み出された文字Ｅの数が他の文字の数を超えるまで、順次読み出される。この読み出されたリンク符号化データは、新たに生成されたリンクデータと関連付けられる。復号化モジュール２８により読み出されたシンボルは、現在処理中のリンクのリンク符号化データから削除される。
【０２４９】
処理中のリンク符号化の次のシンボルが、文字Ｐでないと判定される（Ｓ１２−４）場合、復号化モジュール２８は、処理中のリンク符号化データの先頭のシンボルが文字Ｍであるか否かを判定する（Ｓ１２−６）。
【０２５０】
文字Ｍである場合、復号化モジュール２８は、処理中のリンク符号化データと関連付けられたリンクデータ及びレベルデータのコピーを生成する（Ｓ１２−７）。復号化モジュール２８は、現在のリンクと関連付けられたリンク符号化データを更新する。この更新処理は、リンクと関連付けられたシンボル列の先頭から文字Ｍを削除し、リンク符号化データにおける文字Ｅの数が他の文字の数を越すまで、リンク符号化データのシンボルを読み出すことにより、実行される。リンク符号化データから読み出されたシンボルは、リンク符号化として、新たに生成されたリンクと関連付けられる。処理中のリンクに対するリンク符号化データは、リンクと関連付けられたシンボルのリストから、読み出されたリンク符号化データを削除することにより、更新される。
【０２５１】
したがって、例えば、図１３Ａ〜図１３Ｆを参照して、以下の初期リンクデータ及びレベルデータと関連付けられたリンクリスト［ＭＤＥＰＥＥＤＥＤＥＥ］から、以下のデータを復号化する場合を考慮する。
（０，−）−レベル０
また、下記は、写像データである。
写像データ
レイヤ０［０］
【０２５２】
図１３Ａを参照すると、リンクの開始ノードが丸の中の数字で示され、かつリンクが第２の丸を指す矢印で示される場合、上記リンク符号化データ及びリンクデータは、図１３Ａに概略的に示される。図１３Ａにおいて、ノードの長さがレベルデータに対応する。より長い矢印を有するレベルデータは、より大きいレベル番号と関連付けられる。リンク符号化データは、リンクに隣接して示される。
【０２５３】
まず、リンク符号化データの第１の文字は、文字Ｍである。したがって、リンクデータ（０，−）及びレベルデータのコピーが、作成される。リンクデータの２つのコピーは、次のリンク符号化［ＤＥＰＥＥ］及び［ＤＥＤＥＥ］に関連付けられる。この段階において、図１３Ｂにより示されるように、下記のデータが格納される。
【０２５４】
リンク リンク符号化 レベル
（０，−）  ［ＤＥＰＥＥ］    レベル０
（０，−）  ［ＤＥＤＥＥ］    レベル０
【０２５５】
２つのリンクに関連付けられた符号化データが単一の文字Ｅでないため、リンク符号化のうちの一方が、処理するために選択される。
【０２５６】
第１のリンク符号化［ＤＥＰＥＥ］の場合、第１のシンボルはＤである。したがって、このリンクに対するレベルデータは、１増分される。リンクに対するリンク符号化は、リンク符号化［ＰＥＥ］に置き換えられる。この段階において、図１３Ｃにより示されるように、下記のデータが格納される。
【０２５７】
リンク リンク符号化 レベル
（０，−）  ［ＰＥＥ］        レベル１
（０，−）  ［ＤＥＤＥＥ］    レベル０
【０２５８】
更新されたリンク符号化が処理される時、第１のシンボルが文字Ｐであるため、リンクに関連付けられたリンク符号化は、終了ノードをノードリスト上に現れる次のノードに設定することにより、更新される。また、開始ノードとして新たなノードを有する新たなリンクが、生成される。新たなリンクは、最初と最後のシンボルが削除された先のリンク符号化と関連付けられる。新たなノードは、処理中のリンクに対するレイヤデータにより識別されたレイヤと隣接するノードのリストに追加される。新たなリンクは、このレイヤを識別するレベルデータと関連付けられる。
【０２５９】
この段階において、ノードリスト上の次のノードがノード１である場合、下記のデータが格納される。
【０２６０】
写像データ
レイヤ０  ［０］
レイヤ１    −
レイヤ２  ［１］
リンクデータ リンク符号化 レベル
（０，１）    ［Ｅ］            レベル１
（０，−）    ［ＤＥＤＥＥ］    レベル０
（１，−）    ［Ｅ］            レベル２
【０２６１】
このデータは、図１３Ｄにより示される。
【０２６２】
残るリンクは双方とも、リンク符号化Ｅと関連付けられるため、復号化モジュール２８は、次に、リンクデータ（０，−）と関連付けられたリンク符号化を処理する。このリンク符号化がＤＥＤＥＥから成るため、レベルデータが２になるように更新される。この時点で、符号化は、単一の文字Ｅのみを含む。その後、全てのリンク符号化データが処理されたことになる。リンク符号化の処理結果は、図１３Ｅにより示される。
【０２６３】
このように、復号化モジュール２８は、リンクリストのデータを処理し、リンク符号化データ４０により符号化されたノードの１または２以上の並行一次パスを含むラティス構造の部分を示す写像データ及びリンクデータを、生成することが可能である。
【０２６４】
図１１Ａを参照すると、全てのリンクデータが処理された（Ｓ１１−５）後、復号化モジュール２８は、ノードリスト４４から次のノードを読み出す（Ｓ１１−６）。リンクリスト４３から取得されたリンク符号化を処理した結果、復号化モジュール２８により生成されたヌルの終了ノードを有するリンクデータを更新するために、このノード番号が利用される。この更新処理は、ノードリスト４４から読み出されたノードの値で、ヌル値を置き換えることにより実行される。更新されたリンクのうち１つのリンクが選択される。ノードリスト４４から読み出されたノードは、リンクに対するレベルデータにより識別されたレイヤに隣接するレイヤのノードのリストに追加される。
【０２６５】
例えば、上述したリンクの場合、次のノード番号をノード２とすると、写像データ及びリンクデータは、以下のようになる。
【０２６６】
写像データ
レイヤ０［０］
レイヤ１
レイヤ２［１］
レイヤ３［２］
リンクデータ
（０，１），（０，２），（１，２）
【０２６７】
ノード２が追加された後の上記例の最終的な構造は、図１３Ｆに示される。
【０２６８】
現在のノードデータ及び最後に処理されたノードデータは、ノードリスト４４から読み出された最終ノードと等しくなるように再設定される。また、上方境界リスト及び下方境界リストは、ノードリスト４４から読み出された最終ノードの番号である単一の要素を含むように、再設定される。
【０２６９】
復号化モジュール２８は、全てのシェイプ符号化データ４２が処理されたか否かを判定する（Ｓ１１−７）。全てのシェイプ符号化データ４２が処理された場合、復号化モジュール２８は、後述するように、データ記憶装置２０に格納されたダミーリンク／ノードデータ３８及びクロスリンクデータ３９を使用して、ラティス構造の表現を完成する（Ｓ１１−２３）。あるいは、全てのシェイプ符号化データ４２が処理されていない場合、復号化モジュール２８は、詳細を後述するように、シェイプ符号化データ４２の次の番号を処理する（Ｓ１１−７）。
【０２７０】
初期上方パスの番号及び初期下方パスの番号がシェイプ符号化データ４２から読み出された（Ｓ１１−３）時に、これら番号の双方が１であると判定されない（Ｓ１１−４）場合、復号化モジュール２４は、文字Ｅにより表されるシンボルの総数が他のシンボルの数を超えるまで、リンクリスト４３からリンク符号化の次のセクションを読み出す（Ｓ１１−８）。更に、復号化モジュール２８は、先にステップ（Ｓ１１−５）に関連して説明されたように、このリンク符号化データを処理する。
【０２７１】
リンクリスト４３から読み出されたリンク符号化データが処理された後、復号化モジュール２８は、ノードリスト４４から次のノード番号を読み出す（Ｓ１１−９）。リンク符号化データの処理結果として生成され、ヌルの終了ノードを識別するリンクデータは、ノードリスト４４から読み出されたこのノードを終了ノードとして含むように更新される。その後、ラティス構造の写像データは、前述のように更新される。ここで、ノードリスト４４から読み出されたノードの番号は、更新されたリンクのいずれかのレベルデータにより認識されるレイヤと隣接するレイヤのノードのリストに追加される。
【０２７２】
復号化モジュール２８は、処理中のシェイプ符号化データにより符号化された全ての上方パスが、復号化されたか否かを判定する（Ｓ１１−１０）。すなわち、復号化モジュール２８は、処理するシェイプ符号化がシェイプ符号化データ４２より読み出されてから、リンク符号化及びノードが、ステップ（Ｓ１１−９）の処理結果として生成されるべきラティス構造に、追加される回数をカウントする。この回数が、シェイプ符号化データ４２から読み出された３つの番号うち第２の番号より小さい場合、復号化モジュール２８は、リンクリスト４３のリンク符号化の次のセクションを処理する（Ｓ１１−８）。更に、復号化モジュール２８は、ノードリスト４４の次のノードを読み出し、処理する（Ｓ１１−９）。
【０２７３】
したがって、例えば、下記のデータが、データ記憶装置２０により格納された場合：
現在のノード      ０
ノードリスト    ［２，３，１，．．．］
リンクリスト    ［ＥＥＥＥ．．．］
シェイプ符号化  ［０，２，２，．．．］
写像データ
レイヤ１      ［０］
リンクデータ    なし
上方境界      ［０］
下方境界      ［０］
リンクリストの最初の２項目の処理後、データ記憶装置に格納されるデータは、下記のようになる。
【０２７４】
現在のノード      ０
ノードリスト    ［１，．．．］
リンクリスト    ［ＥＥ．．．］
シェイプ符号化  ［０，２，２，．．．］
写像データ
レイヤ１      ［０］
レイヤ２      ［２］
レイヤ３      ［３］
リンクデータ  （０，２），（２，３）
上方境界      ［０，２，３］
下方境界      ［０］
【０２７５】
復号化モジュール２８が、処理のためにシェイプ符号化データ４２の第２の番号により識別される全てのリンクが処理されたと判断した場合、復号化モジュール２８は、追加された最終ノードのノード番号を記録し（Ｓ１１−１１）、文字Ｅを他の文字よりも多く含むリンクリストのリンク符号化データの次のセクションを処理する（Ｓ１１−１３）。その後、復号化モジュール２８は、リンクリスト４３から読み出されたリンク符号化データを、現在のノードに対応する開始ノード及びヌルの終了ノードを有する生成されたリンクと関連付ける。リンク符号化は、先述のように処理される。リンク符号化データの項目が処理された後、復号化モジュール２８は、最終ノードの値を記録（Ｓ１１−１１）してから、ステップ（Ｓ１１−１３）において処理されたリンク符号化データのセクションの総数が、処理中のシェイプ符号化データの最終番号に対応するか否かを判定する（Ｓ１１−１４）。
【０２７６】
対応しない場合、復号化モジュール２８は、ノードリストから次のノードを読み出し（Ｓ１１−１５）、現在、ヌルの終了ノードを識別しているリンクデータに、読み出されたノードを、終了ノードとして追加する。先にステップ（Ｓ１１−９）に関連して説明された方法と同一の方法で、このノード番号を使用して、写像データを更新する。復号化モジュール２８は、生成されるラティスに関連付けられた境界リストを更新する。ここで、現在のノードが上方境界リスト及び下方境界リスト双方の要素である場合、この更新処理は、ステップ（Ｓ１１−９）の更新処理とは異なり、新たに認識されるノードを下方境界リストに追加する処理を含む。
【０２７７】
したがって、上記例の場合、リンクリストのリンク符号化データの更なる２つの項目が処理された後、下記のデータが格納される。
【０２７８】
現在のノード    ０
ノードリスト    ［１，．．．］
リンクリスト    ［．．．］
シェイプ符号化  ［０，２，２，．．．］
写像データ
レイヤ１      ［０］
レイヤ２      ［２,１］
レイヤ３      ［３］
リンクデータ  （０，２），（２，３），（０，１），（１，−）
上方境界      ［０，２，３］
下方境界      ［０，１］
最後のノード    ３
【０２７９】
最後のノードが記録（Ｓ１１−１１）されてから、ステップ（Ｓ１１−１３）において処理されたリンク符号化データのセクションの総数が、処理中のシェイプ符号化の最終値により識別される番号に対応する場合、復号化モジュール２８は、最後のノードを識別するために終了ノードとしてヌル値を有するリンクデータを修正し、最後のノードを下方境界リストに追加する（Ｓ１１−１６）。
【０２８０】
上述の例のこの段階において、復号化モジュール２８によりデータ記憶装置２０に格納される写像データ、リンクデータ、上方境界リスト及び下方境界リストは、下記のようになる。
【０２８１】
写像データ
レイヤ１      ［０］
レイヤ２      ［２，１］
レイヤ３      ［３］
リンクデータ  （０，２），（２，３），（０，１），（１，３）
上方境界      ［０，２，３］
下方境界      ［０，１，３］
【０２８２】
この段階において、この組み込みデータ及びリンクデータにより符号化されたラティス構造は、図１４Ａにより示される。ここで、同一のレイヤであるノードは、縦の列に示されており、リンクデータは、リンクデータの開始ノードと終了ノードとを接続する矢印により示される。
【０２８３】
図１４Ａの構造を図１０Ａの構造と比較すると、生成された構造が、図１０Ａにおいて陰影を付けられたノード及び実線の矢印に対応することは明らかである。更に、この例における初期ノードリスト、リンクリスト及びシェイプ符号化を、図１０Ａの例における対応するノードリスト、リンクリスト及びシェイプ符号化データと比較する。前述の方法で、構造に対して生成されたノードリスト、シェイプ符号化データ及びリンクリストを処理することにより、その構造を再現することが可能であることは、明らかである。
【０２８４】
ラティス構造における第１のノードから開始するリンクに対するシェイプ符号化データを構成する３つの番号の第１のセットが復号化され、対応するラティス構造が生成されると、復号化モジュールは、すべての符号化データが処理されたか否かを判定する（Ｓ１１−７）。
【０２８５】
図１１Ｃを参照すると、すべて処理されていない場合、復号化モジュール２８は、シェイプ符号化データ４２から次の番号を読み出す（Ｓ１１−７）。その後、復号化モジュール２８は、先にステップ（Ｓ１１−２）に関連して説明されたように、現在のノード番号を更新する。すなわち、シェイプ符号化リスト４２から読み出された番号が「０」である場合、更新処理は実行されない。その番号が正又は負の数である場合、符号化された構造の境界上にある他のノードが選択される。その選択されたノードは、上方境界リスト又は下方境界リストのいずれかにある複数のノードのうちの１つである。
【０２８６】
図１４Ａの構造の場合、シェイプ符号化の次の番号が１で、現在のノード番号が０に設定されており、更に上方境界リスト［０，２，３］及び下方境界リスト［０，１，３］が格納されている時、現在のノード番号は、２に設定される。
【０２８７】
現在のノード番号が更新された（Ｓ１１−１７）後、復号化モジュール２８は、現在のノード番号により識別されるノードが境界リストの最終ノードに対応するか否かを判定する（Ｓ１１−１８）。対応する場合、復号化モジュール２８は、先にステップ（Ｓ１１−３）〜ステップ（Ｓ１１−１６）に関連して説明された方法と同一の方法で、シェイプ符号化の次の２つの番号、関連付けられたリンクリストのリンク符号化及びノードリスト４４のノードを処理する（Ｓ１１−３〜Ｓ１１−１６）。
【０２８８】
現在のノード番号により識別されるノードが、境界リストの最後の番号により識別されるノードと等価でない場合、シェイプ符号化データ４２の次の２つの番号が読み出される。復号化モジュール２８は、処理され、かつ生成された構造の最終ノードに追加されるべきリンクがあれば、そのリンク数を判定する（Ｓ１１−１９）。
【０２８９】
特に、まず、復号化モジュール２８は、現在のノードが上方境界リストにあるノードであるか否かを判定する。現在のノードが上方境界リストにある場合、上方境界リストの末尾から現在のノードを離間して、その離間したノードの数と、シェイプ符号化の２つの番号のうち第２の番号とを比較する。
【０２９０】
シェイプ符号化の第２の番号が、上方境界リストの最終ノードから現在のノードを離間するノード数を超える場合、シェイプ符号化の第１の番号と上方境界リストの末尾から現在のノードを離間するノード数との差が判定される。この差が、処理するリンク数に設定される。
【０２９１】
現在のノードが上方境界リストのノードにより識別されない場合、下方境界リストの末尾から現在のノードを離間するノード数が判定される。この数字は、シェイプ符号化の２つの番号のうち第１の番号と比較される。シェイプ符号化の第１の番号が下方境界リストの末尾から現在のノードを離間するノード数を超える場合、シェイプ符号化の第１の番号と下方境界リストの末尾から現在のノードを離間するノード数との差が処理されるリンク数として設定される。
【０２９２】
したがって、例えば、現在のノードがノード２のシェイプ符号化［１，３，３］を処理する場合で、かつ上方境界と下方境界が次のような場合：
上方境界  ［０，１，２，３，４］
下方境界  ［０，５，４］
現在のノード２は、上方境界に存在するとして識別され、ノード３及びノード４により上方境界の末尾から離間される。ノード２の総数は、シェイプ符号化［１，３，３］の最終番号より小さいため、１つの追加ノードが、生成された構造の最終ノード（ノード４）から、その構造に追加されるべきノードとして識別される。
【０２９３】
一方、上記例において、現在のノードがノード１として識別され、同一のシェイプ符号化が同一の境界に対して処理される場合、上記例のように、ノード１は、ノード２、ノード３及びノード４により上方境界の最終ノードから離間される。このノード数を処理中のシェイプ符号化の最終番号と比較することにより、境界リストの最終ノードに追加されるべきノードが存在しないと判定される。
【０２９４】
追加すべきリンクの総数が判定された（Ｓ１１−１９）後、復号化モジュール２８は、全ての必要なリンクが処理されたか否かを判定する（Ｓ１１−２０）。全て処理されていない場合、復号化モジュール２８は、文字Ｅにより表されたシンボルの総数が他の文字により表されたシンボルの総数を超えるまで、リストの先頭のシンボルである次のリンクのために、リンク符号化データを読み出す。このリンク符号化は、図１２を参照して先に詳細に説明された方法と同一の方法で処理される。
【０２９５】
ノードリスト４４の次のノード番号が、読み出される（Ｓ１１−２２）。このノード番号は、ヌル値を終了ノードとして識別するリンクデータの更新処理に使用される。更新されたリンクに関連付けられたレベルデータは、識別される。また、読み出されたノード番号に対応する番号は、更新されるべきリンクのレベルデータにより識別されるレイヤに隣接するレイヤに対する写像データのノードのリストに追加される。
【０２９６】
写像データ及びリンクデータの双方が更新された時で、現在のノードが上方境界リストのノードにより識別されない場合、ノード番号は、上方境界リストの末尾に追加される。あるいは、現在のノードが上方境界リストのノードにより識別される場合は、ノード番号は、下方境界リストに追加される。
【０２９７】
復号化モジュール２８は、ステップ（Ｓ１１−２１）において処理されたリンクデータのセクションの総数が処理するリンクの必要数に対応するか否かを再判定する（Ｓ１１−２０）。対応しない場合、更にリンクデータが処理され（Ｓ１１−２１）、境界データ、写像データ及びリンクデータが全て更新される（Ｓ１１−２１、Ｓ１１−２２）。
【０２９８】
例えば、図１４Ｂを参照すると、ノード０、ノード２、ノード３及びノード１により識別される区域のシェイプ符号化データが、先に図１４Ａに関連して説明されたように処理された後、処理する次のシェイプ符号化データは、符号［１，２，２］である。この場合、第１の番号１は、元の開始ノード０からのオフセットを示し、復号化された区域の周囲を時計回り方向に動くことでノード２に達する。このノードは、上方境界０，２，３の中に存在し、境界の中で、単一のリンク２−３により最終ノードから離間される。
【０２９９】
シェイプ符号化の最終番号、この例では２が、復号化された区域において最終ノードから現在のノード２を離間するリンクの数、この例では単一のリンクと比較される。シェイプ符号化が、復号化された区域において最終ノードから現在のノードを離間するリンクの数より大きな数を識別するため、最終ノードに追加されるべきリンクの数がその差として判定される。この場合、もう１つのリンクが追加される。
【０３００】
１つのリンクデータのセットが処理された後、ノードテーブルから次のノードが読み出され、読み出されたノードは、次のレイヤで追加される。図１４Ｂは、リンクデータＤＥＥが処理され、次のノード番号７がノードリスト４４から読み出された後の、図１４Ａの更新された構造を示す図である。
【０３０１】
必要なノードが、先に符号化された区域の最終ノードに接続して追加された後、復号化モジュールは、リンクリスト４３から、Ｅ以外の文字により表されるシンボルよりもシンボルＥをより多く有する次のセクションを読み出す（Ｓ１１−１３）。これは、先に説明された方法と同一の方法で処理される。
【０３０２】
復号化モジュール２８は、必要な追加リンクの全てが処理されたか否かを判定する（Ｓ１１−１４）。処理されていない場合、復号化モジュール２８は、ノードリストから次のノードを読み出し、この新たに読み出されたノードを使用して、上方境界又は下方境界を更新する（Ｓ１１−１５）。
【０３０３】
更に具体的には、現在のノードが、上方境界リストの先頭の番号ではない上方境界リスト上の番号により識別される場合、ステップ（Ｓ１１−１３）において処理されたリンク符号化のセクションの数は、シェイプ符号化から読み出された一対の番号のうち第１の番号と比較される。リンク符号化の処理されたセクションの数がその番号と等しい場合、ノードはそれ以上追加されない。等しくない場合、次のノードが読み出され、写像データ及びリンクデータが前述の方法で先に更新される。その後、上方境界リストが更新される。
【０３０４】
最初の繰返し処理で境界リストを更新する時、上方境界において、現在のノードから最終ノードに至るまでの全てのノードが削除され、ノードリスト４４から読み出された新たなノードが、上方境界のノードのリストに追加される。続く全ての繰返し処理において、削除処理は発生せず、新たなノードが上方境界リストに追加される。
【０３０５】
一方、上方境界リストにも存在しないノードが、下方境界リストの現在のノードに追加される時、ステップ（Ｓ１１−１３）において処理されたリンク符号化のセクションの数は、シェイプ符号化から読み出された一対の番号のうち第２の番号と比較される。リンク符号化のセクションの数がこの番号に等しい場合、ノードはそれ以上追加されない。等しくない場合、ノードリストから次のノードが読み出され、写像データ及びリンクデータは、前述のように更新される。その後、下方境界が更新される。この更新処理は、最初の繰返し処理において、現在のノードから下方境界リストの終わりに至るまでの全てのノードが削除され、新たに読み出されたノードがリストの終わりに追加されるという処理である。続く繰返し処理において、削除処理は発生せず、新たなノード番号がリストの終わりに追加される。
【０３０６】
復号化モジュール２８がリンク符号化のセクションを必要な数だけ処理したと判定される（Ｓ１１−１４）と、ヌルの終了ノードを有する生成されたリンクは、識別する終了ノードを有するように、現在のノードを含まない境界リストの最終ノードに更新される。その後、現在のノードを含まない境界リストにおける最終ノードが、現在のノードを含む境界リストの終わりに追加される。
【０３０７】
したがって、例えば、先に生成した図１４Ａの構造と、シェイプ符号化の処理が完了した部分とを有する符号化１，２，２が、図１４Ｂに示す構造を生成するために処理された後、現在のノード、すなわちノード２に追加されるべき最後の２つのリンクが識別され、順次処理される。
【０３０８】
この処理において、ノードリストの次のノードは［６］であり、リンク符号化の次のセクションが［ＤＥＥＥ］である場合、上方境界リストは、まず、［０，２，６］となるように修正される。必要なリンクが双方とも処理された後、上方境界は、［０，２，６，７］となる。その結果、図１４Ｃの構造が生成される。
【０３０９】
下記のシェイプ符号化、リンクリスト及びノードリストを考慮する。
【０３１０】
シェイプ符号化  ［０，２，２，１，２，２，１，１，２，−３，２，１］
リンク符号化    ［ＥＥＥＥＤＥＥＤＥＥＥＰＥＥＰＭＥＥＰＥＥＭＰＥＤＥＥＰＥＤＥＥ］
ノードリスト    ［０，２，３，１，７，６，９，Ｄ４，８，１０，５，４］
【０３１１】
これらは、図８Ｈの構造を符号化して生成されたシェイプ符号化、ノードリスト及びリンクリストに対応する。図１４Ａ〜図１４Ｆの構造は、順次、段階的に状態が変化される。
【０３１２】
更に具体的には、処理後は下記のようになる。
【０３１３】
シェイプ符号化  ［０，２，２，１，２，２］
リンク符号化    ［ＥＥＥＥＤＥＥＤＥＥＥ］
ノードリスト    ［０，２，３，１，７，６］
【０３１４】
図１４Ｃの構造が、生成され、処理されたノードはノード２と識別される。
【０３１５】
シェイプ符号化の次の数字［１］は、ノード６を、次に処理するノードとして識別する。次の２つの数字１、２は、ノード７に追加されるリンクを示す。その後、リンク符号化の次セクションである［ＰＥＥ］を処理し、次の２つのノードを追加することで、図１４Ｄの構造を生成する。
【０３１６】
リンクデータの次セクションである［ＰＭＥＥＰＥＥ］は、ノード６から出るリンクを追加することで、処理される。図１４Ｅは、このリンク符号化の処理中に生成される構造を示す。ここで、リンク符号化［ＰＥＥ］は、リンク（８，−）と関連して処理すべき符号化として残る。
【０３１７】
次に、残りのデータが処理され、最終的に、図１４Ｆの構造が作成される。
【０３１８】
最後のシェイプ符号化が処理されたと判定されると（Ｓ１１−７）、復号化モジュール２８は、（Ｓ１１−２３）へ進み、その構造に追加されたダミーリンク及びダミーノードを除去する。
【０３１９】
特に、復号化モジュールは、データ記憶装置２０に格納されたデータにより識別されるノードリスト及びダミーノード／ダミーリンク３８の双方に存在するダミーノードを識別する。その後、復号化モジュールは、対応する生成されたノードを表現するデータを、写像データから除去する。この写像データは、復号化モジュール２８が、復号化される構造に対して作成したデータである。ダミーノードが除去されると、そのダミーノードを開始ノード又は終了ノードのいずれかとして識別するすべてのリンクデータは、常に削除される。
【０３２０】
次に、ダミーリンク３８に対応するリンクもまた、リンクデータから削除され、クロスリンクデータ３９に対応する新たなリンクが、写像テーブル３６に格納されたデータに追加される。
【０３２１】
したがって、例えば、シェイプ符号化データ４２、リンクリスト４３及びノードリスト４４から、図１４Ｆに示すラティス構造を生成後、下記のダミーリンク／ノードデータ３８及びクロスリンクデータ３９が格納される場合を考える。
【０３２２】
ダミーノード  ［Ｄ１，Ｄ２，Ｄ３，Ｄ４，Ｄ５］
ダミーリンク  （５，７）
クロスリンク  （５，６）
【０３２３】
この場合、ダミーリンク／ノードデータ３８及びクロスリンクデータ３９の処理後、生成された写像データと写像テーブル３６内のリンクデータとにより定義されるラティス構造は、図１４Ｇに示す構造を定義する。
【０３２４】
図１４Ｇの構造と図６Ａの元の構造とを比較すると、一部のレイヤ中のノードは、わずかに再順序付けされているが、同一のノードが同一のレイヤに現れており、図６Ａ及び図１４Ｇに示すラティスが同一であることは、明らかである。更に、図６Ａのノード間の各接続に対応する接続が、図１４Ｇにおいて同一の番号を有するノードに対して存在する。したがって、図１４Ｇにより識別されるラティス構造は、元のラティス構造の表現となる。元のラティス構造は、元々、写像モジュール２２により処理された音声ノードデータ３０により表現されたものであり、図６Ａは、この表現である。また、図１４Ｇのラティス構造は、定義されたシェイプ符号化データ４２、リンクリスト４３及びノードリスト４４の復号化動作の結果であるため、このラティス構造は、シェイプ符号化データ４２、リンクリスト４３及びノードリスト４４が、別の復号化モジュール２８により同様の方法で処理される場合も、必ず生成される構造である。
【０３２５】
したがって、復号化モジュール２８により生成された最後のラティス構造は、ラティス構造のリンクに対する特定の順序の判定に使用できる。この特定の順序とは、音声リンクデータ３２により、これら特定のリンクと関連付けられたデータを、特定の順序で圧縮モジュール１２へ送信可能にするための順序である。
【０３２６】
（出力モジュールにより実行される処理）
音声ラティス構造の最後の表現が復号化モジュール２８により生成され、写像テーブル３６に格納されると、次に、出力モジュール２９が呼び出される。出力モジュール２９は、シェイプ符号化モジュール２６により事前に生成されたシェイプ符号化データ４２及びリンクリスト４３を、データ圧縮モジュール１２へ出力する。その後、出力モジュール２９は、ダミーリンク３８、クロスリンクデータ３９及びタイミングデータ３４を識別するデータを、データ圧縮モジュール１２へ出力する。
【０３２７】
出力モジュール２９は、ノードリスト４４を利用し、音声ノードデータ３０により音声ラティス内の各ノードと関連付けられる他のデータの項目を、順次選択する。特に、ノードリスト４４の第１のノードは、読み出され、音声ノードデータ３０によりその第１のノードと関連付けられる他のデータが、データ圧縮モジュールへ出力される。次に、ノードリスト内の第２のノードが識別され、音声ノードデータ３０によりその第２のノードに関連付けられる他のデータが、データ圧縮モジュール１２へ出力される。ノードリスト４４にダミーノードが現れる場合は、そのノードをダミーノードとして識別するデータが、データ圧縮モジュールへ出力される。ノードリスト４４の最後に到達するまで、この処理は繰り返される。
【０３２８】
最後に、出力モジュール２９は、写像テーブル３６中に格納されたラティス構造のリンクデータを、開始ノード番号により順序付けする。また、出力モジュール２９は、同一の開始ノード番号を有するリンクデータを、リンクの終了ノードが、写像データによってレイヤと関連付けられるリスト内に現れる順序で順序付けする。
【０３２９】
したがって、例えば、図１４Ｇのラティスの場合、図１４Ｇに示すリンクは、以下の順序に配置される。
（０，２）、（０，１）（２，３）、（２，６）、（１，３）、（１，４）、（１，５）、（３，７）、（４，７）、（５，６）、（６，８）、（６，８）、（８，１０）、（７，９）
【０３３０】
次に、出力モジュール２９は、順序付けされたリンクごとに、音声リンクデータ３２内の対応するリンクを識別し、これらのリンクごとに関連するデータを、リンクの順序に対応する順序で、データ圧縮モジュールに出力する。
【０３３１】
このように、データ圧縮モジュール１２は、ラティス構造を表現するシェイプ符号化データ４２及びリンクリスト４３と、ラティス構造のダミーデータ３４に追加又はラティス構造から除去されたタイミングデータ３４、リンク／ノード３８及びクロスリンクデータ３９のリストとを受信するように構成される。更に、データ圧縮モジュール１２は、定義された順序で、元の音声ラティス内の各ノード及び各リンクと関連する他のデータと、元の音声ラティスの各リンクと関連するデータとを受信するように構成される。
【０３３２】
次に、これら全てのデータは、データ圧縮モジュール１２により、従来のように処理され、その後、圧縮状態で、ネットワーク３を介して、文書記憶装置２へ送信される。
【０３３３】
（文書記憶装置により実行される処理）
圧縮音声ラティスデータの受信に応答して、文書記憶装置２が実行する処理を、図１５を参照して、以下に詳細に説明する。
【０３３４】
最初に、クライアントコンピュータ１から、ネットワーク３を介して、圧縮データを受信し、この圧縮データを、伸長ユニット１５により、従来の方法で伸長する（Ｓ１５−１）。
【０３３５】
伸長ユニット１５を使用したデータの伸長により、文書記憶装置２は、シェイプ符号化データ４２と、リンクリスト４３と、ダミーリンク／ノードデータ３８、クロスリンクデータ３９、タイミングデータ３４のリストと、元の順序付きデータとを再生できる。元の順序付きデータは、音声ノードデータ３０及び音声リンクデータ３２により、それぞれ、リンク及びノードと関連付けられている。
【０３３６】
音声ノードデータ３０により音声ノードと関連付けられる他のデータは、ラティスプロセッサによってデータ圧縮モジュール１２へ出力された順序になるように、再生される。他のデータの各項目は、ノード番号、すなわち、番号順に生成されるノード番号と関連付けられる。このデータは、再生モジュール１７により格納される。タイミングデータ３４、ダミーリンク／ノードデータ３８、クロスリンクデータ３９、シェイプ符号化データ４２及びリンクリスト４３は、伸長ユニット１５を使用した圧縮データの処理により得られ、これらもまた、再生モジュール１７により格納される。
【０３３７】
次に、再生モジュール１７は、受信したシェイプ符号化データ４２及びリンクリスト４３を処理する（Ｓ１５−２）。再生モジュール１７による処理は、前述した復号化モジュール２８により実行された処理と同一であり、説明を繰り返さない。但し、ノードリスト４４から番号を選択した代わりに、ラティスプロセッサ１７が新たなノードを必要とする際は、常に、番号順で次に使用可能な番号が利用される。
【０３３８】
シェイプ符号化データ４２及びリンクリスト４３の処理の結果、クライアントコンピュータ１のラティスプロセッサ１１により符号化されたラティス構造を定義する写像データ及びリンクデータが、再生モジュール１７により生成される。このデータは、次に、再生モジュール１７により格納された音声ノードデータ３０の項目ごとにリンクされたノード及びタイミングデータのリスト作成に利用される。
【０３３９】
ラティスプロセッサ１７は、クライアントコンピュータ１内のラティスプロセッサ１１の出力モジュール２９による処理に関して前述したように、開始ノード及び終了ノードにより、写像テーブル３６中のリンクデータを順序付けする（Ｓ１５−３）。その後、音声リンクデータ３２は、受信された他のデータと、順序付けされたデータとを関連付けることにより生成される。なお、受信された他のデータは、他のデータが受信された順序でリンクと関連している。また、順序付けされたデータは、写像テーブル３６のリンクを識別する。このデータは、再生モジュール１７により、音声リンクデータ３２として格納される。
【０３４０】
音声ノードデータ３０及び音声リンクデータ３２が再生モジュール１７により再生されると、音声ノードデータ３０及び音声リンクデータ３２は、文書検索ユニット１９へ出力される。次に、文書検索ユニット１９は、受信した音声ノードデータ３０及び音声リンクデータ３２を利用して、検索用の文書を選択する（Ｓ１５−４）。この文書は、ネットワーク３を介して、クライアントコンピュータ１へ出力される。したがって、このように、クライアントコンピュータ１により生成された音声ラティスは、ネットワーク３を介した送信用に符号化且つ圧縮される音声信号のために生成された音声ラティスと共に、文書記憶装置２に格納された文書へのアクセスに利用される。
【０３４１】
（他の実施形態及び変形例）
上述の実施形態において、ノード及びリンクに関連したデータは、特定の方法で順序付けされるように記述したが、シェイプ符号化及びリンクリストにより表現されるラティス構造のシェイプが、写像テーブル３６中の写像データ及びリンクデータの形態で判別されると、任意の適切な順序付けを、識別されたノード又はリンクへの特定のデータの割り当てに利用できる。
【０３４２】
上述の実施形態において、写像モジュール２２の処理は、前のレイヤ内にあるノードの位置の平均値として計算された順序番号に基づいて、レイヤ内のノードを順序付けすることとして記述したが、ラティス構造の写像におけるクロスリンクの数を最小限にする任意の従来技術を、この順序付けの実行に利用できる。したがって、例えば、順序付けは、平均値ではなく、中間値に基づいて実行できる。
【０３４３】
上述の実施形態において、写像テーブル３６は、初期写像表現におけるクロスリンクの数を最小限にするように再順序付けされるとして記述したが、この工程は、次にネットワーク３を介して文書記憶装置２へ送信されるクロスリンクデータ３９の量を最小限にするために実行される。しかし、再順序付けの工程は省略してもよく、代わりに、より多量のクロスリンクデータ３９を、ネットワーク３を介して送信してもよい。
【０３４４】
上述の符号化システムでは、ダミーノードは、符号化されたダミーノードごとに文字Ｄ及び文字Ｅを使用して、符号化される。しかし、Ｄの短縮符号を使用してもよい。そのような実施形態では、シンボルＥの数がシンボルＭ及びシンボルＰの数を超過するまで、シンボルをリンクリスト４４から、継続して読みとることにより、異なるリンクに対するリンク符号化データが読み出される。リンク符号化処理の際、リンクと関連するレベルデータは、文字Ｄが現れ、その文字Dが処理中のリンク符号化の先頭から除去されるたびに、更新される。
【０３４５】
更に、１つのリンク符号化中に同一文字のコピーが複数ある場合、リンク符号化データを、代わりに、異なる文字を識別する第１の符号化データと、異なる文字ごとに、特定の文字が反復された回数を示す数字を表す第２の符号化データとで表現するようにしてもよい。
【０３４６】
すなわち、例えば、リンクリストが［ＤＤＤＤＤＤＥＥＥＥＥＥＥ］の場合、リンクリストは、代わりに、リスト［ＤＥ］及びリスト［６，７］の、２つのリストの形態で表現できる。
【０３４７】
そのような実施形態において、文字Ｄの複数セットが互いに隣接して符号化される場合、リンクと関連するレベルデータは、文字Ｄを個別に処理するのではなく、レベルデータを、連続するＤの数分増分することで、自動的に更新できる。
【０３４８】
更に、他の実施形態において、この２つのリストは、文字のリスト及び数字のリストを含んでもよい。この場合、ダミーノードに対する重複文字のみが文字のリストから除去され、数字のリストは、ダミーノードの反復する符号化の数を識別する。そのような実施形態においては、上述のように、ダミーノード又はノードに対する文字は、レベルデータを、数字のリスト内の文字と関連する数分増分することにより、１つの工程で処理できる。
【０３４９】
上述の実施形態において、生成中のラティス構造に、新たな区域を追加するためのオフセット値は、正の値又は負の値のいずれかとして記述した。しかし、別の実施形態おいて、区域の生成に使用された最終ノードを、区域の生成に使用される次のノードから離間して、オフセットが、特定の方向で、境界付近のノード数を識別する場合は、正の値のみを使用することもある。
【０３５０】
あるいは、現在のノードと、境界リスト上の次に処理されるノードとの相対位置に対してオフセット値を使用する代わりに、例えば、ノードリスト内の現在のノードに関するオフセット値を使用してもよい。あるいは、より一般的には、次のノードを、オフセット値及び現在のノードから識別可能にする任意の適切なオフセットを使用してもよい。
【０３５１】
上述の実施形態において、リンク符号化データ４０が生成中であり、２つのリンクのいずれかが併合される場合、新たなリンク符号化データは、それらのリンクに対するリンク符号化データ４０の長さに依存する順番で、除去されるリンクと関連するリンク符号化データを付随することにより生成されるとして説明した。このように、新たなリンクに対するリンク符号化データ４０を生成することは、文字列が反復し、したがって、従来技術を使用する圧縮が可能な文字列を生成する傾向がある点で好ましい。しかし、この符号化データ４０を生成する別の方法が、例えば、写像テーブル３６中のリンクの順序付けに基づいて、リンク符号化データが付随される順序の選択に利用できる。
【０３５２】
上述の実施形態において、ダミーノードは、隣接しないタイミングデータと関連付けられるノードを接続する全てのリンクに追加されると説明した。全てのダミーノードは、リンク符号化データを使用して、符号化される。生成されたリンク符号化データの続いて行われる復号化は、ノード再生の際に、ノードが正しいタイミングと関連付けられることを保証するために、利用される。
【０３５３】
２つ以上のリンクに対する終了ノードであるノードが追加される場合、リンク符号化処理の際に、終了ノードとしてノードを有する少なくとも１つの生成されたリンクは、終了ノードがレイヤ内に正確に配置され、正しいタイミングデータと関連付けられるように、レベルデータと関連付けられることが十分に保証される。
【０３５４】
別の実施形態では、ラティス表現が生成された後、各ノードは、同一数のノードにより、開始ノードから出る全てのパスへ離間される。生成されたラティス構造内の適切なノードの各々が、少なくともそのノードに到達する１つのパス上で先に存在したように、依然として、同一数のノードにより開始ノードから離間されることを保証する。その一方で、生成されたラティス構造は、複数のダミーノードを除去するよう処理される。この簡易化ラティスは、先に説明した方法と同様に符号化される。
【０３５５】
更に詳細には、第１のレイヤから開始して、第１のレイヤ中にある全ての実ノードは、識別され、且つそのノードに対するレイヤを既知として識別するデータと関連付けられる。その後、既知のレイヤを識別するデータと関連付けられた実開始ノードを有するリンクごとに、これらのリンクにより識別された実終了ノードは、既知のレイヤを有する実終了ノードを識別するデータとも関連付けられる。
【０３５６】
全てのリンクが考慮されると、既知のレイヤデータと関連しない各実ノードは、識別可能となる。第２のレイヤ中の実ノードから開始し、任意の実ノードが既知のレイヤデータと関連しない場合には、第１の深度検索が、既知のレイヤデータと関連する任意の早いタイミングのレイヤ内の実ノードから、考慮中のノードへの、最短パスを発見するよう実行される。パス中の全てのダミーノードは、保存中として識別され、処理中の実ノードは、既知のレイヤデータと関連付けられる。この処理は、全ての実ノードが既知のレイヤを有すると識別されるまで、後続のレイヤごとに繰り返される。保存中であると識別されないダミーノードは、削除される。
【０３５７】
ラティスを復号化する際、写像テーブル３６中の写像データに新たなノードを追加する場合は、必ず、新たなノードを終了ノードとして含むリンクが識別され、新たなノードは、リンクに対するレベルデータから判定された最大番号により識別されるレイヤと関連付けられる。そのような実施形態において生成された結果の構造は、上述の実施形態で説明された方法で生成された結果の構造と、同一となる。しかし、複数のダミーノードが除去され且つ符号化されないため、圧縮ユニット１２により圧縮が必要なデータ量が減少し、より効率よい圧縮が実現される。
【０３５８】
上述の実施形態において、クロスリンクは、リンク符号化の判定前に除去されると説明したが、別の実施形態においては、クロスリンクは、リンク符号化を生成中に、識別され且つ符号化されてもよい。そのような実施形態では、（Ｃ, 開始ノード, 終了ノード）の形態のリンク符号化は、クロスリンクが符号化されたことの識別に利用される。リンク符号化を復号化する場合、クロスリンクは、２つのノード間にあるクロスリンクが符号化されたことを識別するこのデータから、再生される。
【０３５９】
上述の実施形態において、平面グラフは、生成され、その後、シェイプ符号化として符号化される前に、一次パス及び並行パスの除去により簡易化されると説明したが、ラティスの部分を表現する平面グラフの簡易化は、省略してもよい。
【０３６０】
そのような実施形態では、単一の一次パスが２つのレイヤ間に延在する場合、（オフセット，リンクの数，０）の形態のシェイプ符号化を使用する。一対のリンクが同一の開始ノード及び終了ノードを有する場合、（オフセット，１，１）の形態のシェイプ符号化を使用する。
【０３６１】
ここで得られたシェイプ符号化の次の処理は、先に述べた処理とほぼ同一であるが、符号化（０，１，１）は、もはや、ラティスの一端から延出する単一のリンクを示さない。代わりに、シェイプ符号化の最終番号が０であることは、単一のパスがラティスの一端に追加されていることを示す。
【０３６２】
そのような実施形態の場合、図６Ｅのラティスは、以下に示す単一のシェイプ符号化の形態で、符号化される。ここで、オフセット値は、上述の方法と同様に計算される。
［０，２，２，１，３，３，２，３，３，０，１，１，−４，３，３，０，３，３］
【０３６３】
上述の実施形態において、シェイプ符号化及びリンク符号化からのラティスの再生は、シェイプ符号化及びリンク符号化の同時処理により実行されると説明した。他の実施形態では、初期ラティス構造は、リンク符号化データが初期構造内のリンクと関連する場合に、シェイプ符号化のみの処理により生成される。全てのシェイプ符号化の処理後、リンク符号化が処理され、初期ラティス内のノードに関連するレイヤデータは、リンク符号化を使用して更新され、追加ノード及びリンクは、リンク符号化を処理する際に追加される。
【０３６４】
上述の実施形態において、リンクと関連するデータは、シェイプ符号化及びリンク符号化から生成される写像におけるリンクの順序付けに基づいて順序付けされると説明した。しかし、他の順序付けを使用してもよい。特に、ラティス内のリンクに関連するデータは、それらのリンクが、シェイプ符号化及びリンク符号化から生成される順序で、順序付けられてもよい。このようなデータの順序付けにより、ラティスの部分の完全表現が再生され、その後、ラティス構造全体が判定される。
【０３６５】
上述の実施形態において、全てのノードは、少なくとも１つのリンクの開始ノードでも終了ノードでもないノードにダミーリンクを追加するように、処理される。他の実施形態では、ダミーリンクの追加の代わりに、シェイプ符号化が、ノードを非接続であると識別してもよい。例えば、（オフセット，０，１）の形態のシェイプ符号化は、オフセットにより識別されたノードから非接続ノードへの、１方向のリンクの識別に使用され、（オフセット，０，０）の形態の符号化は、逆方向のリンクの識別に使用される。
【０３６６】
非接続ノードを識別する別の方法は、複数のリンクにおいて、終了ノードのみ又は開始ノードのみとなるノードの識別に使用される。
【０３６７】
したがって、例えば、いかなるリンクにおいても開始ノードではないノードの場合、シェイプ符号化は、そのノードの識別に使用される。例えば、（オフセット，−１，−１）の形態の符号化が使用される。次の区域を処理する場合、識別されたノードが境界リストから削除され、一方の境界リスト内の最終ノードがもう一方の境界リストに追加されると同時に、識別されたノードが無視される。これにより、非接続ノードの周辺区域が符号化される。
【０３６８】
いかなるリンクにおいても終了ノードではないノードの場合、シェイプ符号化データを、そのノードの特定に使用してもよい。特定されたノードが接続するノードに先行するように、特定されたノードと関連するレイヤデータを変形してもよい。特定されたノードに隣接する区域は、通常の方法で処理される。
【０３６９】
上述の実施形態において、元のラティス構造を再生可能とする符号化の方法を説明したが、いくつかの実施形態においては、元のラティスに一部のみが対応するラティスが再生されてもよい。したがって、例えば、元のラティスの写像を判定後、クロスリンクを有さない平面グラフが判定されるように、複数のリンクが除去されてもよい。その後、平面グラフにより定義される構造に対応する音声ラティスの部分のみを、上述の方法で処理してもよい。
【０３７０】
元のラティスの一部のみが、生成されたデータにより表現されるが、生成が必要なクロスリンクデータがないため、圧縮の改良が可能である。そのようなシステムでは、除去され、かつ表現されないリンクは、符号化された構造が、受信信号が表現する内容に関してより高確率の仮説を表現するように、低確率と関連するクロスリンクとして選択される。
【０３７１】
あるいは、平面グラフ生成のために交差するリンクを除去する代わりに、他の方法を使用してもよい。一例において、ダミーノードを、追加されたダミーノードを介するリンクにより置き換えられる全ての交差点及び交差するリンクに挿入してもよい。
【０３７２】
あるいは、ラティスの一部が交差するリンク無しでは表現されないと判定された場合は、その部分を表現するノード及びリンクの追加コピーを生成し、交差するリンクを、追加部分へのリンクで置き換えるようにしてもよい。そのような実施形態において、ラティスのサイズは増加するが、対応する区域の符号化は類似しているため、より大きなラティスのために生成されたデータは、元のラティスの符号化と同様のサイズに圧縮可能である必要がある。
【０３７３】
上述の実施形態において、ノードの再順序付けは、クロスリンクの数を減少するとして説明した。このようなノード再順序付けの複雑性は、処理すべきノード及びリンクの数に依存する。他の実施形態において、再順序付け工程に先行して、処理中のラティス構造を簡易化してもよい。
【０３７４】
したがって、例えば、ラティスの部分に対するリンク符号化は、ラティス構造内に表現されるノード及びリンクの数が減少するように求めてもよい。簡易化ラティスは、クロスリンクを最小限にするように、再順序付けされてもよい。その後、任意の残りのクロスリンクは、除去される。更に、ラティスは、リンク符号化データによってその時点で表現される部分を更に除去するように、処理される。残りのラティス構造に対するシェイプ符号化データは、先に述べた方法と同様に生成してもよい。
【０３７５】
上述の実施形態において、ダミーノードは、ノードと、タイミングデータの正確な項目との関連付けを可能とするために使用されると説明したが、他の方法を使用してもよい。一例において、時間オフセットのリストは、ノードリスト中のノードごとに、リスト中の直前のノードに相関するノードに対して相関するレイヤを識別するために使用してもよい。
【０３７６】
上述の実施形態において、区域に対するシェイプ符号化データを、オフセット、上位パスのリンク数、下位パスのリンク数の形態で特定するデータとして説明したが、他の方法を使用して区域のシェイプを特定してもよい。
【０３７７】
したがって、例えば、区域の境界を規定するリンクの数を識別する数字と、符号化する区域の一部を形成する符号化区域の境界における最終リンクを識別するデータとを使用できる。そのようなシステムで生成されたシェイプは、ノードをタイミングデータと関連付ける処理が必要である。この処理は、ノードに対するタイミングを明確に符号化することで、実現できる。
【０３７８】
あるいは、全てのノードが残されている場合、区域を形成する上位パス及び下位パスは、必然的に同一数のノード及びリンクを含む。したがって、そのような区域は、開始ノードを識別するデータと、１つのパスにのみあるリンクの数を識別するデータとの形態に、符号化される。これは、他のパスが必然的に同一のノード数を含むからである。
【０３７９】
上述の実施形態においては、音声ラティスの処理を説明したが、本発明は、より広範に適用可能である。したがって、例えば、本発明は、ラティスの写像表現が作成されるような順序でノードが配置される任意のラティス構造の符号化に使用できる。
【０３８０】
対象物をグラフ表示するラティス構造のようなラティス構造であって、定義された開始ノード、終了ノード及びノードの順序付けを有しないラティス構造が符号化される場合は、任意の開始ノード、終了ノード及びノードの順序付けが判定され、ラティスが処理される。
【０３８１】
上述の実施形態において、圧縮符号化データの送信について説明したが、本発明は、格納のためのラティス構造データの圧縮にも、同様に適用可能である。
【０３８２】
図面を参照して説明された本発明の実施形態は、コンピュータ装置と、コンピュータ装置において実行される処理とを含むが、本発明は、本発明の実現に適用されるコンピュータプログラム、特に、キャリア上又はキャリア内部のコンピュータプログラムにも及ぶ。プログラムは、ソース、オブジェクトコード、又は本発明に係る処理の実現に適した他のどのような形態であってもよい。キャリアは、本プログラムを実行可能な任意のエンティティ又は装置であってもよい。
【０３８３】
例えば、キャリアは、ＲＯＭ等の記憶媒体を含んでよい。ＲＯＭは、例えば、ＣＤ−ＲＯＭ、半導体ＲＯＭ又は磁気記憶媒体であり、磁気記憶媒体は、フロッピディスク又はハードディスク等である。更に、キャリアは、ケーブル又は光ケーブルを介して搬送される、あるいは無線手段又は他の手段により搬送される、電気信号又は光信号等の、送信可能なキャリアであってもよい。
【０３８４】
プログラムが、ケーブル、他の装置又は他の手段を介して直接搬送される信号に組込まれた場合、キャリアは、そのようなケーブル、他の装置又は他の手段で構成されてもよい。
【０３８５】
あるいは、キャリアは、プログラムが組込まれた集積回路であってもよく、それは、該当処理の実行、又は該当処理の実行中での使用に適用される。
【図面の簡単な説明】
【０３８６】
【図１】図１は、本発明に従ってラティスプロセッサ及び再生モジュールを具現化した文書検索システムの概略ブロック図；
【図２】図２は、語句「Taj Mahal drawing．．．」を表現する信号を音声認識システムにより復号するためのラティス構造の一例を示す概略図；
【図３】図３は、図１のラティスプロセッサの機能ユニットの概略ブロック図；
【図４】図４は、図１のラティスプロセッサにより実行される処理動作の概要を示すフローチャート；
【図５】図５は、図１のラティスプロセッサの写像モジュールにより実行される処理動作のフローチャート；
【図６Ａ】、
【図６Ｂ】、
【図６Ｃ】、
【図６Ｄ】、
【図６Ｅ】図６Ａ〜図６Ｅは、図１のラティスプロセッサの写像モジュールによるラティス構造の一例の処理を示す概略図；
【図７】図７は、図１のラティスプロセッサのリンク符号化モジュールにより実行される処理動作のフローチャート；
【図８Ａ】、
【図８Ｂ】、
【図８Ｃ】、
【図８Ｄ】、
【図８Ｅ】、
【図８Ｆ】、
【図８Ｇ】、
【図８Ｈ】図８Ａ〜図８Ｈは、図１のラティスプロセッサのリンク符号化モジュールによる図６Ｅの写像ラティス構造例の処理を示す概略図；
【図９Ａ】、
【図９Ｂ】図９Ａ及び図９Ｂは、図１のラティスプロセッサのシェイプ符号化モジュールにより実行される処理動作のフローチャート；
【図１０Ａ】、
【図１０Ｂ】、
【図１０Ｃ】図１０Ａ、図１０Ｂ、及び図１０Ｃは、図１のラティスプロセッサの符号化モジュールによる図８Ｈの写像ラティスの例の符号化を示す概略図；
【図１１Ａ】、
【図１１Ｂ】、
【図１１Ｃ】、
【図１１Ｄ】図１１Ａ〜図１１Ｄは、図１のラティスプロセッサの復号化モジュールにより実行される処理動作のフローチャート；
【図１２】図１２は、リンク符号化を処理するために、図１のラティスプロセッサの復号化モジュールにより実行される処理動作のフローチャート；
【図１３Ａ】、
【図１３Ｂ】、
【図１３Ｃ】、
【図１３Ｄ】、
【図１３Ｅ】、
【図１３Ｆ】図１３Ａ〜図１３Ｆは、リンク符号化データを利用する写像ラティスの一部の再生を示す概略図；
【図１４Ａ】、
【図１４Ｂ】、
【図１４Ｃ】、
【図１４Ｄ】、
【図１４Ｅ】、
【図１４Ｆ】、
【図１４Ｇ】図１４Ａ〜図１４Ｇは、図６Ａに例示された写像ラティスに対する、図１のラティスプロセッサの復号化モジュールによる再生を示す概略図；
【図１５】図１５は、圧縮データの受信に応答して、図１の文書記憶装置により実行される処理動作のフローチャート、である。
【図１】
2006503318.tif 000003
【図２】
2006503318.tif 000004
【図３】
2006503318.tif 000005
【図４】
2006503318.tif 000006
【図５】
2006503318.tif 000007
【図６Ａ】
2006503318.tif 000008
【図６Ｂ】
2006503318.tif 000009
【図６Ｃ】
2006503318.tif 000010
【図６Ｄ】
2006503318.tif 000011
【図６Ｅ】
2006503318.tif 000012
【図７】
2006503318.tif 000013
【図８Ａ】
2006503318.tif 000014
【図８Ｂ】
2006503318.tif 000015
【図８Ｃ】
2006503318.tif 000016
【図８Ｄ】
2006503318.tif 000017
【図８Ｅ】
2006503318.tif 000018
【図８Ｆ】
2006503318.tif 000019
【図８Ｇ】
2006503318.tif 000020
【図８Ｈ】
2006503318.tif 000021
【図９Ａ】
2006503318.tif 000022
【図９Ｂ】
2006503318.tif 000023
【図１０Ａ】
2006503318.tif 000024
【図１０Ｂ】
2006503318.tif 000025
【図１０Ｃ】
2006503318.tif 000026
【図１１Ａ】
2006503318.tif 000027
【図１１Ｂ】
2006503318.tif 000028
【図１１Ｃ】
2006503318.tif 000029
【図１１Ｄ】
2006503318.tif 000030
【図１２】
2006503318.tif 000031
【図１３Ａ】
2006503318.tif 000032
【図１３Ｂ】
2006503318.tif 000033
【図１３Ｃ】
2006503318.tif 000034
【図１３Ｄ】
2006503318.tif 000035
【図１３Ｅ】
2006503318.tif 000036
【図１３Ｆ】
2006503318.tif 000037
【図１４Ａ】
2006503318.tif 000038
【図１４Ｂ】
2006503318.tif 000039
【図１４Ｃ】
2006503318.tif 000040
【図１４Ｄ】
2006503318.tif 000041
【図１４Ｅ】
2006503318.tif 000042
【図１４Ｆ】
2006503318.tif 000043
【図１４Ｇ】
2006503318.tif 000044
【図１５】
2006503318.tif 000045
【国際調査報告】
2006503318.tif 000046
2006503318.tif 000047