(57)【特許請求の範囲】
【請求項１】
少なくともファイルサイズ情報を含むヘッダを含む圧縮ファイルを受信して該圧縮ファイルを伸張するシステムにおいて、前記圧縮ファイルの一部に対応する圧縮コードワードを収めている第１の部分と、前記圧縮ファイルの残りに対応する圧縮されていないコードワードの部分を表すプレーン・テキストを収めている前記第１の部分に隣接する第２の部分とをもつ調整済みモノトーン圧縮ファイルを、あるサイズをもち、かつプレーン・テキストを収めている伸張ファイルに適切に伸張する方法であって、
前記圧縮ファイルを受信するステップと、
前記ヘッダを読んで、圧縮ファイルのサイズを判定し、並びに前記第１および第２の隣接する部分を特定するステップと、
前記伸張ファイルのサイズをもつメモリ・バッファを割り当てる割り当てステップと、
前記調整済みモノトーン圧縮ファイルを前記割り当てられたメモリ・バッファの第１のブロックにストアし、および前記調整済みモノトーン圧縮ファイルの先頭に対する前記メモリ・バッファ内の所定のロケーションを指すように入力ポインタをセットするストア・ステップと、
調整済み圧縮ファイルの第１の隣接する部分に入っている圧縮コードワードを伸張して対応する伸張コードワードを生成し、前記モノトーン圧縮ファイルにより使用されていない前記割り当てられた残りの部分に対応する前記割り当てられたメモリ・バッファの第２のブロックにそれぞれ伸張コードワードを挿入し、および前記割り当てられたメモリ・バッファの第２のブロックが一杯の場合、伸張済みの圧縮コードワードにより以前使用された所定のメモリのロケーションにある前記割り当てられたメモリ・バッファの第１のブロックに伸張コードワードを挿入し、それぞれの圧縮コードワードにアクセスしたのち前記入力ポインタを１つ進める伸張ステップと、
前記入力ポインタが、前記圧縮ファイルのすべてが伸張されていることを示す前記第２の隣接する部分の先頭に来た場合、伸張を停止するステップと
を具えたことを特徴とする伸張方法。
【請求項２】
請求項１に記載の伸張方法において、前記伸張ステップは、
前記割り当てられたメモリ・バッファの第２のブロックの先頭に出力ポインタをセットするステップと、
前記入力ポインタが指している前記割り当てられたメモリ・バッファの第１のブロックからコードワードを読み取って、前記入力ポインタを前進させるステップと、
コードワードをデコードしてプレーン・テキストを出力するステップと、
そのプレーン・テキストを前記出力ポインタが指している前記割り当てられたメモリ・バッファの第２のブロックの所定のロケーションに書き込んで、前記出力ポインタを前進させるステップと、
前記出力ポインタがプレーン・テキストを収めている前記第２の隣接する部分の前記先頭のロケーションに対応するまで、読取り、デコードおよび書込みステップを繰り返して、前記伸張を停止するステップと
を具えたことを特徴とする伸張方法。
【請求項３】
請求項１に記載の伸張方法において、
前記調整済みモノトーン圧縮ファイルは、あるサイズをもち、かつ前記調整済みモノトーン圧縮ファイルのサイズ、前記伸張ファイルのサイズおよび前記第２の隣接する部分のロケーションを表すデータを収めているヘッダを含んでおり、
前記割り当てステップは、前記ヘッダを読んで前記圧縮ファイルのサイズを決定し、および前記伸張ファイルのサイズに相当するメモリの所定のブロックを割り当てるステップを含んでおり、
前記ストア・ステップは、
前記ヘッダを読んで前記調整済みモノトーン圧縮ファイルのサイズを決定するステップと、
前記調整済みモノトーン圧縮ファイルの先頭について前記メモリ・バッファの割り当てられたブロック内のロケーションを、前記調整済みモノトーン圧縮ファイルと前記伸張ファイルのサイズから計算するステップと、
前記調整済みモノトーン圧縮ファイルを、前記計算で求めたロケーションを先頭にして前記メモリ・バッファの割り当てられたブロックにストアしていくステップとを含み、
前記伸張ステップは、
前記ヘッダを読んで前記第２の隣接する部分のロケーションを決定するステップと、
前記調整済みモノトーン圧縮ファイルの先頭について前記メモリ・バッファの割り当てられたブロック内の計算で求めたロケーションを指すように前記入力ポインタをセットするステップと、
前記メモリ・バッファの割り当てられたブロックの先頭を指すように前記出力ポインタをセットするステップと、
前記入力ポインタが指している前記メモリ・バッファ内のロケーションからコードワードを読み取って、前記入力ポインタを前進させるステップと、
前記コードワードをデコードしてプレーン・テキストを出力するステップと、
前記出力ポインタが指している前記メモリ・バッファ内のロケーションに当該プレーン・テキストを書き込んで、前記出力ポインタを前進させるステップと、
前記入力ポインタが前記第２の隣接する部分のロケーションに対応するまで読取り、デコードおよび書込みステップを繰り返していくステップとを含むことを特徴とする伸張方法。
【請求項４】
あるサイズを持つソース・ファイルを調整済み圧縮ファイルに圧縮する方法であって、
（ａ）前記ソース・ファイルを圧縮コードワードを収めている圧縮ファイルに圧縮するステップと、
（ｂ）前記圧縮ファイルを
（ｃ）前記伸張ファイルのサイズのメモリの所定のブロックを割り当てるステップと、
（ｄ）前記割り当てられたブロックの最後の場所に前記圧縮ファイルを置くステップと、
（ｅ）前記圧縮ファイルのコードワードを順に伸張して、伸張コードワードが伸張されなかった、前記最後のメモリの場所にストアされた圧縮コードワードをオーバライトするまで、最初のメモリの場所で開始する前記割り当てられたブロックに伸張コードワードを順にストアするステップと
を含むアルゴリズムに従って伸張するステップと、
（ｆ）前記オーバライトが発生する場合、伸張されたコードワードが伸張されなかった圧縮コードワードをオーバライトする場所の前に前記圧縮ファイルの圧縮コードワードに対応する圧縮コードワードを含み、および前記場所の次にある前記圧縮ファイルの圧縮コードワードに対応するプレーン・テキストを含むモノトーン圧縮ファイルを形成するステップと、
（ｈ）前記モノトーン圧縮ファイルに、前記場所に対応する標示を貼り付けるステップと
を備えた方法。
【請求項５】
請求項４に記載の方法において、前記（ｃ）ないし（ｆ）のステップは、伸張をシミュレートするステップであることを特徴とする方法。
【請求項６】
請求項４に記載の方法において、前記ソース・ファイルのサイズ、前記調整済み圧縮ファイルのサイズおよび前記標示を表しているデータを収めているヘッダを前記圧縮ファイルに追加するステップをさらに具えたことを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はシステム内のデータ・ファイルを圧縮し、伸張（復元）する方法に関し、もっと具体的には、圧縮はオフラインで行われ、伸張はオーディオ・ビデオ・インタラクティブ・システムのような、メモリに制約のあるシステムでリアル・タイムに行われる方法に関する。
【０００２】
なお、本明細書の記述は本件出願の優先権の基礎たる米国特許出願第０８／２８３，３４６号（１９９４年８月１日出願）の明細書の記載に基づくものであって、当該米国特許出願の番号を参照することによって当該米国特許出願の明細書の記載内容が本明細書の一部分を構成するものとする。
【０００３】
【従来の技術】
オーディオ・ビデオ・インタラクティブ(audio video interactive - AVI) システムは、テレビを見ている人がテレビジョン・プログラムとやりとり（対話）できるようにする手段を備えているブロードキャスト（放送）インタラクティブ・システムである。このシステムでは、各受信側ロケーションは送信側ロケーションからのアプリケーション・プログラムをＡＶＩ信号を介して受信するプロセッサを備えている。ＡＶＩ信号は、標準テレビジョン信号と同じようにオーディオ成分、すなわち音声成分とビデオ成分、すなわち映像成分とインタラクティブ成分とを含んでいる複合信号(composite signal)である。インタラクティブ成分はアプリケーション・プログラムを構成するコード・モジュールとデータ・モジュールを有する。アプリケーション・プログラマは、コンパイラなどの標準的プログラミング・ツールを使用してコード・モジュールとデータ・モジュールをオフラインで生成している。これらのコード・モジュールとデータ・モジュールはインタラクティブ成分に組み込まれるように処理され、さらに音声成分およびビデオ成分と結合されてＡＶＩ信号が作られている。
【０００４】
ＡＶＩ複合信号は受信側ロケーションへ送信される。音声成分とビデオ成分はＡＶＩ複合信号から抽出され、通常のテレビジョン・システムにおけると同じように既知の方法で処理されて音（サウンド）と画像（イメージ）を得ている。インタラクティブ成分は抽出され、コード・モジュールとデータ・モジュールは受信側ロケーションのプロセッサのメモリにロードされる。ついで、このプロセッサはコード・モジュールを実行し、データ・モジュールを処理して、多分、ＡＶＩ音声サウンドとビデオ・イメージに重ねられるサウンドとグラフィック・イメージを生成し、かつテレビを見ている人からの入力に応答してテレビジョン・プログラミングとやりとりする。
【０００５】
受信側ロケーションの機器は比較的低コストで製造し、販売することが考えられる。このコストは、各プロセッサに実装されるメモリ量を最小限とすることにより、そしてSGS/Thomson ST9 のように計算能力が比較的低いマイクロプロセッサを使用することにより低減化される。
【０００６】
さらにまた、アプリケーション・プログラムをいくつかの比較的小さなコード・モジュールとデータ・モジュール（32 kB 未満が代表例）に分割することが考えられる。インタラクティブ成分で利用できるバンド幅を最適化するために、コード・モジュールとデータ・モジュールは圧縮されてから送信されるようにしている。これらのモジュールは小さく、圧縮はオフラインで行われるので、圧縮速度に対する関心は最低になっている。他方、SGS/Thomson ST9 のような、比較的低い計算能力のマイクロプロセッサ（ビット・シフト能力に制約がある（例えば、シングル・ビット・シフトである）ので伸張に適していないマイクロプロセッサ）でも、伸張（復元）は高速化することが要求される。さらに加えて、受信側ロケーションのプロセッサでアプリケーション・プログラムをストアし、実行するために用意されるＲＡＭ量は比較的小さい。従って、使用されるいかなる伸張手法でも、最小限のメモリを使用することが要件になる。
【０００７】
従来の圧縮手法にはLempel-Ziv '77ファミリの圧縮アルゴリズムがある。これらの圧縮手法は、ソース・データには繰返しが非常に多いという基本的考え方を基礎にしている。以前に出現したものを指すポインタ（逆方向ポインタ(back pointer)と呼ばれる）と、多分、一致(match) のサイズとを収めている特殊なコードワードで繰返しを置き換えることによって圧縮を達成することができる。例えば、"abcdabcf"というソース・ストリングは次のようにコード化することが可能である。
【０００８】
文字'a'、 'b'および'c' を出力にコピーする；
一致のサイズ３を、現出力位置の４バイトあとから出力にコピーしていく
；
文字'f' を出力にコピーする。
【０００９】
この手法を用いて圧縮されたソース・データは、圧縮ファイルを先頭から最後までトラバース（走査）することにより伸張することが可能であり、この場合、後に戻ってトラッキングし(backtracking)、および以前に読み取った圧縮データを再読取りしたりする必要がない。さらに加えて、伸張プロセスが以前に伸張されたデータへのアクセスを必要とするのが通常であっても、伸張データもまた順次に出力される。このように伸張することのできる圧縮手法はモノトーン(monotone)圧縮／伸張手法と呼ばれている。
【００１０】
本発明者は、オーバラップ一致(overlapping match) を使用することによって、さらに圧縮を行うことができることを認識した。オーバラップ一致では、ソース・ファイル・データのうち次にコード化しようとする部分が、コード化される繰返しの中に含まれている。例えば、ソース・ストリング"abcabcabc" は、オーバラップ一致を用いると、次のようにコード化することができる。
【００１１】
文字'a'、 'b'および'c' を出力にコピーする；
一致サイズ６を、現出力位置の３バイトあとから出力にコピーしていく。
【００１２】
言い換えると、上記ストリングの先頭から始まる６文字ストリングは２番目の'abc' から始まる、つまり、最初の'abc' がコード化されたあとの６文字ストリングと一致する。オーバラップ一致を使用すると、オーバラップ一致を用いない場合よりも、圧縮ファイルのサイズを小さくすることができる。伸張器(decompressor −伸張ルーチン）は、繰返しの最初のロケーションから出力ファイル内の次のロケーションに文字を一度に１文字ずつコピーすることによって、コード化された繰返しを処理するものと解される。
【００１３】
圧縮されたファイルのサイズを最小限とするために、現在の圧縮手法では、文字が直接にコピーされることを示すコードワードと、以前に出現したものに対する逆方向ポインタと一致のサイズ(match size)を収めている特殊コードワードの構成を、これらのコードワードのサイズを変化させることによって最適化している。一般的に、直接に重ねてコピーされる文字のうち、ある文字は他の文字よりも頻繁に出現する可能性がある。また、代表的なデータについて生成された逆方向ポインタと一致サイズを調べた結果明らかになったことは、あるサイズの一致の回数が２から約６または７のサイズまではほぼ指数的に減少していき、そのあとは減少は急激に遅くなることである。同様に、繰返しに参照の局所性(locality of reference) があるために、小さい逆方向ポインタの方が大きい逆方向ポインタよりも多くなっている（このことは一致パターンが現在位置に近いことを示している）。現在の圧縮手法は、コードワードのサイズを連続的に変化させるエントロピー・コード化(entropy coding)を用いて、特殊コードワードと不一致の入力ストリングをコード化することにより、このようにゆがんだ逆方向ポインタと一致サイズの分布を利用している。
【００１４】
本発明者は、逆方向ポインタと一致ポインタおよびコピー文字コードワードを収めている特殊コードワードに対して真の可変長２次圧縮（エントロピー・コード化）を使用することは、２つの理由からＡＶＩシステムでは適していないことを認識した。第１の理由は、このようなデータを伸張するには、コードワードがバイト境界を尊重しないので、ビット・シフトを幅広く使用する必要があることである。これは、一度に１桁（１位置）ずつしかシフト（桁送り）ができないＳＴ９のような、処理能力が比較的低いマイクロプロセッサでは隘路となっている。可変シフトと回転を実行する際の消費時間を最小限とするために、伸張ルーチン側に多大の努力が要求される。第２の理由は、真の可変長コードワードの伸張を高速化するには、伸張器におけるルックアップ・テーブルを作って、維持する必要があることである。伸張器には、これらのルックアップ・テーブルを作るための計算時間が必要であり、ルックアップ・テーブルをストアするためにシステムＲＡＭのスペースを割り当てなければならない。ＡＶＩデコーダのシステムＲＡＭが最小量に限られているので（これは第一にデータが圧縮されて送信される理由の１つである）、システムＲＡＭスペースが不足し可変長コードのデコードを高速化するのに十分に大きいルックアップ・テーブルを作ることができない。
【００１５】
従って、主要目標は必要とするシステムＲＡＭスペースを最小限としたままで伸張を高速化することである。本発明のひとつの形態によれば、圧縮データは制限された可変長コードワードで表現される。つまり、コードワードは、真の可変長コード化によるのではなく、ニブル（４ビット）の倍数である長さに制限されている。このような方式によると、真の可変長コードワードで必要であった非常に多数回のシフトと回転オペレーション（演算）を必要とすることなくコードワードの長さをある程度最適化することができる。
【００１６】
【発明が解決しようとする課題】
従来の伸張過程では、圧縮ファイルは第１のメモリ・バッファに書込まれている。第２のメモリ・バッファは伸張されたソース・ファイルを収めておくために割り当てられている。そのあと、第１メモリ・バッファに入っている圧縮ファイルが初めから終わりまで調べられ、再構築されたソース・データ・ファイルが第２メモリ・バッファに書込まれる。このような手法によると、圧縮ファイルを伸張するためには２つのメモリ・バッファを割り当てる必要がある。
【００１７】
【課題を解決するための手段】
本発明者は、モノトーン（単調）圧縮／伸張手法の原理を用いて、圧縮ファイルを適切に伸張することが可能になるようにした。つまり、圧縮ファイルが受信されると、伸張されるソース・ファイルを入れておくのに十分なサイズのひとつのバッファがメモリ内に割り当てられる。圧縮ファイルはそのバッファに書込まれる。圧縮ファイルがソース・ファイルに伸張されると、その全体が単一のメモリ・バッファに収まるようになる。このようにすると、圧縮ファイルを入れておくための別個のバッファが不要になるので、伸張のために必要なメモリ量が最小限となる。
【００１８】
本発明の原理によれば、圧縮コードワードを収めている第１部分およびプレーン・テキストを収めている第２部分をもつ調整済みのモノトーン圧縮ファイルを、あるサイズをもち、かつプレーン・テキスト(plain text)を収めている伸張ファイルに適切に伸張するための方法は次のステップを具える。まず、伸張されるファイルのサイズをもつメモリ・バッファが割り当てられる。次に、調整済みのモノトーン圧縮ファイルがバッファのボトムにストアされる。最後に、調整済みのモノトーン圧縮ファイルの第１部分に入っている圧縮コードワードが伸張されて、伸張ファイルの対応する部分のプレーン・テキストがバッファのトップに出力される。
【００１９】
ソース・ファイルを調整済みのモノトーン圧縮ファイルに圧縮するための方法は次のステップを具える。まず、ソース・ファイルは圧縮コードワードを収めている圧縮ファイルにモノトーン圧縮される。次に、圧縮ファイルは、圧縮コードワードを収めている第１部分およびプレーン・テキストを収めている第２部分をもつ調整済みのモノトーン圧縮ファイルが得られるように調整される。ソース・ファイルを本発明に従って圧縮すると、もとの圧縮ファイルと同じサイズをもつ調整済みの圧縮ファイルが得られる。
【００２０】
【発明の実施の形態】
図１は、ＡＶＩ信号デコーダのうち本発明を取り入れている部分を示すブロック図である。図１に示すデコーダは各ＡＶＩ受信側ロケーションに設置されている。図１において、ＡＶＩ信号源（図示せず）はデコーダの入力端子５に結合されている。入力端子５はＡＶＩ信号受信装置３０の入力端子に結合されている。ＡＶＩ信号受信装置３０の出力端子は処理ユニット４０のシステム・バス４１６に結合されている。処理ユニット４０はSGS/Thomson ST9 のような中央処理ユニット（ＣＰＵ）４１０、読み／書きメモリ（ＲＡＭ）４１２およびリードオンリ・メモリ（ＲＯＭ）４１４を有し、これらはシステム・バス４１６を介して公知のように一緒に結合されている。
【００２１】
オーディオ信号をＡＶＩオーディオ出力端子２５へ供給するオーディオ・プロセッサ４１８、ビデオ信号をＡＶＩビデオ出力端子１５へ供給するビデオ・プロセッサ４２０、および入力端子３５を経てユーザからのデータを受け取るユーザ入出力（Ｉ／Ｏ）アダプタ４２４も、すべてが公知のようにシステム・バス４１６に結合されている。例えば、並置コンピュータにつながる入出力ポート、モデム、数値演算(math)プロセッサ、その他の入出力アダプタなどの他の機器もまた、公知のようにシステム・バス４１６に結合することができ、そしてデコーダ格納装置（エンクロージャ）の外側の格納装置内の他の機器と結合するためにバス・エクステンダを設けることもできる。
【００２２】
動作時には、ＡＶＩ信号源はパケットのストリームの形でＡＶＩ信号を出力する。ＡＶＩ信号源は、デコーダに対する、例えば、直接ＲＦ衛星リンク、ケーブル・システム・フィードまたは光ファイバ・リンクとすることができる。これらのパケットの一部はＡＶＩ信号のオーディオ成分を搬送し、他のパケットはビデオ成分を搬送し、さらに他のパケットはインタラクティブ成分を搬送している。ＡＶＩ信号受信装置３０は受信したＡＶＩ信号を処理して、オーディオ成分、ビデオ成分およびインタラクティブ成分を形成しているパケットを抽出し、パケットに入っているデータを、ＲＡＭ４１２内に以前に指定されていた、それぞれのメモリ・バッファに既知のＤＭＡ書込み手法を用いてストアする。ついで、オーディオ・プロセッサ４１８とビデオ・プロセッサ４２０は既知のＤＭＡ読取り手法を用いて、データをＲＡＭ４１２内のそれぞれのメモリ・バッファから読み取る。次に、オーディオ・プロセッサ４１８とビデオ・プロセッサ４２０はそれぞれのデータを処理してＡＶＩオーディオ信号を出力端子２５から、ＡＶＩビデオ信号を出力端子１５からそれぞれ出力する。ＣＰＵ４１０をビデオ・プロセッサ４２０および／またはオーディオ・プロセッサ４１８による処理と協働させることもできる。インタラクティブ成分パケットはコード・モジュールとデータ・モジュールを搬送し、ＣＰＵ４１０の制御の下で以下に説明するように処理される。
【００２３】
上述したように、インタラクティブ成分のバンド幅を最大にするために、アプリケーション・プログラマはコード・モジュールおよび／またはデータ・モジュールをLempel-Ziv '77手法などのモノトーン圧縮手法を用いて圧縮してから、それらをＡＶＩ信号のインタラクティブ成分に含ませるようにすることができる。さらに加えて、オーバラップ一致を用いてモジュールをさらに圧縮することができる。図２は、本発明の好適実施例に従って圧縮されたファイルに入っているソース・データを表しているコードワードの構造を示すメモリ・レイアウト図である。好適実施例では、圧縮ファイルはコードワードの順次のブロックの形態になっている。各ブロックは１コード・バイトのヘッダＨＤＲと、そのあとに続く８個のコードワード（ＣＷ１−ＣＷ８）とを有する。
【００２４】
図３は、図２におけるヘッダＨＤＲとコードワード（ＣＷ１−ＣＷ８）との関係を示す詳細メモリ・レイアウト図である。１コード・バイトのヘッダは各コードワードに対するビット・フラグを収めており、コードワードは、ヘッダの第１ビットから最初のコードワードまでの矢印と、ヘッダの第２ビットから２番目のコードワードまでの矢印とで図３に示すように、連続している。ヘッダのビットが１ならば、対応するコードワードは圧縮されていないデータ・バイトを表すコード・バイトであり、伸張時に伸張ファイルにコピーする必要があることを示している。ヘッダのビットが０ならば、対応するコードワードは逆方向ポインタ／一致サイズのコードワードである。
【００２５】
図４の（ａ）から（ｊ）までは、逆方向ポインタ／一致サイズを表すコードワードのそれぞれのフォーマットを示す詳細メモリ・レイアウト図である。上述したように、コードワードは可変長であるが、ニブル（４バイト）の倍数に制限されている。図４において、コードワードの長さ（つまり、ニブル数）、逆方向ポインタの値および一致のサイズは次のようにして判断される。第１ビットが１ならば、コードワードは２または３ニブルのコードワードである。第２ビットが０ならば、一致サイズは２である。第３ビットが０ならば（図４の（ａ））、２ニブルのコードワードであり、次の５ビットは逆方向ポインタ（ＢＰ）−１を表している。第３ビットが１ならば（図４の（ｂ））、３ニブルのコードであり、次の５ビットは最下位ビット（ＬＳＢ）を表し、次のニブルは逆方向ポインタ（ＢＰ）−１の最上位ビット（ＭＳＢ）を表している。
【００２６】
第２および第３ビットが１０ならば、一致サイズは３である。第４ビットが０ならば（図４の（ｃ））、２ニブルのコードワードであり、次の４ビットは逆方向ポインタ（ＢＰ）−１を表している。第４ビットが１ならば（図４の（ｄ））、３ニブルのコードワードであり、次の４ビットは最下位ビット（ＬＳＢ）を表し、次のニブルは逆方向ポインタ（ＢＰ）−１の最上位ビット（ＭＳＢ）を表している。第２、第３および第４ビットがそれぞれ１１０ならば（図４の（ｅ））、一致サイズは４であり、コードワードのサイズは３ニブルである。次の４ビットは最下位ビット（ＬＳＢ）を表し、次のニブルは逆方向ポインタ（ＢＰ）−１の最上位ビット（ＭＳＢ）を表している。第２、第３および第４ビットがそれぞれ１１１ならば（図４の（ｆ））、一致サイズは５であり、コードワードのサイズは３ニブルである。次の４ビットは最下位ビット（ＬＳＢ）を表し、次のニブルは逆方向ポインタ（ＢＰ）−１の最上位ビット（ＭＳＢ）を表している。
【００２７】
コードワードの第１ビットが０ならば、一致サイズはコードワード内にコード化される。これらのコードワードでは、一致サイズと逆方向ポインタは次のようにして判断される。第２、第３および第４ビットがそれぞれ１１１でなければ（図４の（ｇ））、コードワードのサイズは２コード・バイト（４ニブル）である。このような場合には、第２、第３および第４ビットは値Ｍを表している。一致サイズはＭ＋３である。残りの１２ビット（現在のコード・バイトからの４ビットと次のコードワードからの８ビット）は値Ｂを表している。逆方向ポインタはＢ＋１である。第２、第３および第４ビットがそれぞれ１１１ならば、コードワードは少なくとも３コード・バイトである。次の５ビットが１１１１１でなければ（図４の（ｈ））、コードワードは３コード・バイトからなっている。第５、第６、第７、第８および第９ビットは値Ｍを表している。一致サイズはＭ＋３である。逆方向ポインタ（ＢＰ）は最後の１５ビット＋１である。これは逆方向ポインタの最大許容サイズ（つまり、３２Ｋ）である。
【００２８】
第５、第６、第７、第８および第９ビットがそれぞれ１１１１１ならば、コードは少なくとも４コード・バイト長である。このようなコードワードでは、逆方向ポインタは次の１５ビット＋１の値である（図４の（ｈ）と同じ）。最後のコード・バイトが２５５（つまり、１１１１１１１１）でなければ（図４の（ｉ））、最後のコード・バイトは値Ｍになっている。一致サイズはＭ＋３４である。しかし、このバイトが値２５５（つまり、１１１１１１１１）になっていれば（図４の（ｊ））、コードワードは実際には６コード・バイト長である。逆方向ポインタ（ＢＰ）は図４の（ｉ）と同じ位置に入っている。最後の２コードバイト（バイト５と６）は値Ｍになっている。一致サイズはＭ＋２８９である。
【００２９】
このコード化方法では、より共通の逆方向ポインタ／一致サイズに対してはより小さなコードワードが使用されるが、より共通ではない逆方向ポインタ／一致サイズに対してはより大きなコードワードが必要になる。さらに加えて、すべてのコードワードの長さはニブルの倍数になっている。コードワードの長さをニブルの倍数に制限することにより、すべてのコードワードはメモリ内のバイト境界から始まるか、あるいはメモリ内のバイト内のニブル境界から始まる。ＳＴ９のような多くのローエンド・プロセッサはバイト内の２ニブルをスワップする命令をもっているので、多数のシフトを行う必要なく、コードワードを効率よく抽出することが可能である。さらに、圧縮器(compressor −圧縮ルーチン）はコードワードがメモリのどこに置かれているかを知っているので、伸張マイクロセッサによる検索が高速化されるような形でコードワードをコード化する。
【００３０】
例えば、コード・バイト X = b7.b6.....b0 を出力バイトＹ内のニブル境界に置くとすると、それを出力バイトＹとＹ＋１との間に置く１つの方法は、次のようになる。
【００３１】
【数１】
Y = x.x.x.x.b7.b6.b5.b4     Y+1 = b3.b2.b1.b0.x.x.x.x     (1)
ただし、ｘは一般的なビット (generic bit)を示している（つまり、０か１をとるこができる）。ついで、コード・バイトＸを抽出するにあたっては、１６ビットのワードＷをロケーションＹとＹ＋１とから読み取り、
【００３２】
【数２】
W = x.x.x.x.b7.b6.b5.b4.b3.b2.b1.b0.x.x.x.x               (2)
かつ、ビット・シフト操作を左（または右）へ４回実行することになる。しかし、圧縮器がこのコード・バイトを次のようにコード化していれば、
【００３３】
【数３】
Y = x.x.x.x.b3.b2.b1.b0     Y+1 = b7.b6.b5.b4.x.x.x.x     (3)
１６ビット・ワードＷをロケーションＹとＹ＋１とから読み取り、
【００３４】
【数４】
W = x.x.x.x.b3.b2.b1.b0.b7.b6.b5.b4.x.x.x.x               (4)
ＷとマスクＭとの論理積（ＡＮＤ）演算を実行し、
【００３５】
【数５】
M = 0.0.0.0.1.1.1.1.1.1.1.1.0.0.0.0                       (5)
その結果得た１６ビット・ワードの２バイトを加算、つまり、論理和（ＯＲ）演算を実行することにより、コード・バイトを抽出することが可能になる。ＳＴ９では、この最適化によって節減される時間は、従来の方法における４回のビット・シフト操作のうちの２回を減らすことと等価である。
【００３６】
本発明によれば、上述したように圧縮された圧縮ファイルは適切な伸張が行えるように調整される。この調節を行うためには、オリジナル・ソース・ファイルと圧縮ファイルの双方のサイズをひかえておき、圧縮ファイルは２回目に処理される。
【００３７】
図５および図６は、圧縮ファイルに対して調整を行って適切に伸張を行うことができるようにすることを理解するのに役立つメモリ図である。図５において、バッファ・メモリ１００は縦方向の矩形で示されている。バッファの総サイズは伸張されたファイルを収容するのに十分なサイズになっている。圧縮ファイルに対して調整を行うために、圧縮プロセスは、以下に説明するように、伸張を適切に行うことを試み、かつその試みの結果をモニタすることにより、以前に圧縮されたファイルの処理を続けていく。圧縮されたファイル１２０はバッファ１００のボトムに書込まれ、これは図５に陰影を付けた矩形で示されている。入力ポインタは圧縮ファイル１２０内の最初のロケーションを指すようにセットされ、出力ポインタは伸張ファイルが書込まれるメモリ・バッファ１００内の最初のロケーションを指すようにセットされる。以下で詳しく説明するが、圧縮プロセッサの調整フェーズの間は、圧縮ファイル１２０内のデータは入力ポインタが指しているロケーションから読み取られ、入力ポインタが前進する。データは出力ポインタが指しているロケーションにおいてメモリ・バッファ１００の先頭に書込まれ、出力ポインタが前進される。これらはすべて既知のやり方である。
【００３８】
圧縮プロセスの調整フェーズの間に、圧縮ファイル１２０は標準モノトーン伸張プロセスを使用して伸張され、その間、入力ポインタと出力ポインタの状態（ステート）がモニタされる。図６は圧縮プロセスの伸張フェーズの進み具合を一連のメモリ図で示すものである。図６において、メモリ・バッファ１００のうちデータを収容している部分は陰影付きで示されており、データを収容していない部分は陰影なしで示されている。図６の（ａ）は図５に対応し、調整のための伸張プロセスの開始時のメモリ・バッファ１００の状態を示し、入力ポインタ（ＩＰ）は圧縮ファイル１２０（陰影付き）の先頭を指すようにセットされ、出力ポインタ（ＯＰ）はメモリ・バッファ１００の先頭を指すようにセットされている。
【００３９】
図６の（ｂ）は伸張プロセスが開始された直後のメモリ・バッファ１００の状態を示している。図６の（ｂ）に示すように、圧縮ファイル１２０の第１部分は、入力ポインタＩＰが下方に移動したことによって示すようにすでに読み取られている。伸張プロセスの間、モノトーン圧縮ファイルでは逆方向トラッキングが行われないので、メモリ・バッファ１００のうちすでに読み取られた部分は再度読み取られることはないので、陰影なしで示すように、この部分にデータを入れることが可能である。同時に、伸張ファイル１４０の第１部分は、すでに読み取られた圧縮ファイル１２０の部分に応答して、すでに生成されている。伸張ファイル１４０のこの第１部分は、出力ポインタＯＰの移動で示すように、メモリ・バッファ１００の先頭にすでに書込まれている。
【００４０】
図６の（ｃ）は伸張がさらに進んだときのメモリ・バッファ１００の状態を示している。入力ポインタＩＰのロケーションで示すように、圧縮ファイル１２０の大部分が読み取られており、そして、出力ポインタＯＰのロケーションが示すように、さらに伸張ソース・ファイルの大部分が生成されている。図６の（ｃ）からわかるように、出力ポインタＯＰのロケーションは入力ポインタＩＰのロケーションの近くまで到達している。
【００４１】
出力ポインタＯＰが入力ポインタＩＰに追いつくと、伸張ソース・ファイル１４０の新たに書込まれる部分は次に読み取られる圧縮ファイル１２０の部分にオーバライト（重書き）するので、圧縮ファイル１２０をさらにデコードすることは不可能になる。図６の（ｄ）はそのような状態を示している。図６の（ｄ）において、次のコードワードは、入力ポインタＩＰの動きで示すように、圧縮ファイル１２０から読み取られる。このコードワードは図６の（ｅ）に陰影付き矩形ＣＷで示されている。図示のコードワードＣＷは逆方向ポインタ／一致サイズ・コードワードであり、これは、図６の（ｅ）に陰影付き矩形で示すようにプレーン・テキストＰＴを生成する。図から明らかなように、プレーン・テキストＰＴのサイズは、これが出力ポインタＯＰのロケーションにおいてバッファ１００に書込まれるときに、圧縮ファイル１２０の次に読み取られる部分にオーバライトするようなサイズになっている。ついで、出力ポインタ（ＯＰ）は伸張ファイルの新たに書込まれた部分のボトムを指すことになるが、これは入力ポインタ（ＩＰ）の値以下になっている。このように出力ポインタ（ＯＰ）が入力ポインタ（ＩＰ）を通り越したことのためには、圧縮プロセスの調整フェーズが入力ポインタ（ＩＰ）と出力ポインタ（ＯＰ）をモニタしている。
【００４２】
本発明によれば、次に、圧縮ファイル１２０は以下のようにして調整される。出力ポインタ（ＯＰ）の新しいロケーションから圧縮ファイル１２０の最後までの圧縮ファイル内のコードワードは圧縮されていないソース・ファイルからのプレーン・テキストで置き換えられる。その結果として調整された圧縮ファイル１２０′は図６の（ｆ）に示されている。図６の（ｆ）において、調整された圧縮ファイル１２０′は圧縮されていないソース・ファイルの対応する部分を表しているコードワードを収めている第１部分１２４と、圧縮されていないソース・ファイルの対応する部分のプレーン・テキストを表しているデータを収めている第２部分１２６（濃い陰影で示している）とを含んでいる。コードワードがそこで終わり、プレーン・テキストがそこから始まる、調整された圧縮ファイル１２０′内のロケーションはプレーン・インデックス（ＰＩ）と呼ばれ、これもひかえておく。ヘッダＨＤＲは、伸張ファイル（ＤＳ）のサイズ、圧縮ファイル（ＣＳ）のサイズおよびプレーン・インデックス（ＰＩ）を表すデータを（とりわけ）収めている調整された圧縮ファイル１２０′の先頭に付加される。
【００４３】
【実施例】
好適実施例では、上述した調整プロセスが行われても、実際には、図６に示すように、ソース・ファイル１４０は圧縮ファイル１２０から再構築されない。再構築がシミュレートされるだけである。圧縮ファイル１２０はトラバースされ、入力ポインタ（ＩＰ）と出力ポインタ（ＯＰ）は、実際の伸張が行われたとしたらそうなるであろうように正確に維持されるが、伸張ファイル１４０は実際には作成されない。圧縮ファイル１２０で調整が必要な個所が現れると、圧縮ファイル１２０は、上述したように、第１部分１２４に入っているコードワードと第２部分１２６に入っているプレーン・テキストで書き直される。そのあと、調整されたファイル１２０′にヘッダが付加される。
【００４４】
以上から理解されるように、調整された圧縮ファイル１２０′の長さは最初に生成された圧縮ファイル（図６の（ａ）から（ｄ）までに破線で示されている）とまったく同じになっている。つまり、この手法では、圧縮ファイルのサイズが大きくなることはない。
【００４５】
伸張は、受信した調整された圧縮ファイル１２０′のヘッダＨＤＲを読み取り、バッファ（図６の１００）に伸張ファイル１４０のサイズ（ＤＳ）をＲＡＭ４１２（図１）内に割り当て、調整されたファイル１２０′（ヘッダＨＤＲは除かれている）をバッファ１００のボトムにストアすることによって、行うことができる。調整された圧縮ファイル１２０′の開始アドレスは、ヘッダＨＤＲから抽出された圧縮ファイルのサイズ（ＣＳ）と伸張ファイルのサイズ（ＤＳ）から計算することができる。入力ポインタ（ＩＰ）はバッファ１００内の調整された圧縮ファイル１２０′の先頭を指すようにセットされ、出力ポインタ（ＯＰ）はバッファ１００の先頭を指すようにセットされる。ついで、標準モノトーン伸張手法が調整された圧縮ファイル１２０′の第１部分で実行されるが、これは、出力ポインタ（ＯＰ）の値がプレーン・インデックスと等しくなるまで、図６に示すのと同じように入力ポインタ（ＩＰ）と出力ポインタ（ＯＰ）を使用して行われる。その個所からは、プレーン・テキストだけが調整された圧縮ファイル１２０′に入っているので、それ以後の伸張は不要である。調整された圧縮ファイル１２０′の伸張が２つのバッファを使用して行われる場合は（つまり、適切でない場合）、伸張ファイル１４０内の出力ポインタ（ＯＰ）がプレーン・インデックス（ＰＩ）まで来ると、入力ポインタ（ＩＰ）はリセットされ、調整された圧縮ファイル１２０′内のプレーン・インデックス（ＰＩ）の位置も指すようになり、調整された圧縮ファイル１２０′の残り部分は未変更のまま伸張ファイル１４０にコピーされる。
【図面の簡単な説明】
【図１】ＡＶＩ信号デコーダのうち本発明を取り入れている部分を示すブロック図である。
【図２】本発明の好適実施例に従って圧縮されたファイル内のソース・データを表しているコードワードの構造を示すメモリ・レイアウト図である。
【図３】図２におけるヘッダＨＤＲとコードワード（ＣＷ１−ＣＷ８）との関係を示す詳細メモリ・レイアウト図である。
【図４】逆方向ポインタ／一致サイズを表しているコードワードのそれぞれのフォーマットを示す詳細メモリ・レイアウト図である。
【図５】圧縮ファイルに対して調整を行って適切に伸張を行うことができるようにすることを理解するのに役立つメモリ図である。
【図６】圧縮ファイルに対して調整を行って適切に伸張を行うことができるようにすることを理解するのに役立つメモリ図である。
【符号の説明】
１００  メモリ・バッファ
１２０  圧縮ファイル
１２０′  調整済みの圧縮ファイル
１２４  第１部分
１２６  第２部分
１４０  伸張ソース・ファイル
ＣＷ  コードワード
ＨＤＲ  ヘッダ
ＩＰ  入力ポインタ
ＯＰ  出力ポインタ
ＰＩ  プレーン・インデックス
ＰＴ  プレーン・テキスト
【図１】
0003869033.tif 000002
【図２】
0003869033.tif 000003
【図３】
0003869033.tif 000004
【図４】
0003869033.tif 000005
【図５】
0003869033.tif 000006
【図６】
0003869033.tif 000007