JPH0879719A - データ・ファイルの圧縮および伸張方法 - Google Patents
データ・ファイルの圧縮および伸張方法Info
- Publication number
- JPH0879719A JPH0879719A JP7196899A JP19689995A JPH0879719A JP H0879719 A JPH0879719 A JP H0879719A JP 7196899 A JP7196899 A JP 7196899A JP 19689995 A JP19689995 A JP 19689995A JP H0879719 A JPH0879719 A JP H0879719A
- Authority
- JP
- Japan
- Prior art keywords
- file
- compressed
- location
- compressed file
- pointer
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000000034 method Methods 0.000 title claims description 48
- 239000000872 buffer Substances 0.000 claims abstract description 52
- 238000007906 compression Methods 0.000 claims description 34
- 230000006837 decompression Effects 0.000 claims description 31
- 230000006835 compression Effects 0.000 claims description 29
- 238000004088 simulation Methods 0.000 claims 2
- 230000002452 interceptive effect Effects 0.000 description 13
- 238000010586 diagram Methods 0.000 description 12
- 239000002131 composite material Substances 0.000 description 3
- 230000007423 decrease Effects 0.000 description 2
- 238000005457 optimization Methods 0.000 description 2
- 230000004044 response Effects 0.000 description 2
- 230000005236 sound signal Effects 0.000 description 2
- 239000004606 Fillers/Extenders Substances 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 230000003750 conditioning effect Effects 0.000 description 1
- 238000007796 conventional method Methods 0.000 description 1
- 230000008878 coupling Effects 0.000 description 1
- 238000010168 coupling process Methods 0.000 description 1
- 238000005859 coupling reaction Methods 0.000 description 1
- 238000000605 extraction Methods 0.000 description 1
- 239000000835 fiber Substances 0.000 description 1
- 238000012544 monitoring process Methods 0.000 description 1
- 230000003252 repetitive effect Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
- H03M7/3086—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method employing a sliding window, e.g. LZ77
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
- H03M7/42—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code using table look-up for the coding or decoding process, e.g. using read-only memory
- H03M7/425—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code using table look-up for the coding or decoding process, e.g. using read-only memory for the decoding process only
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/42—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Two-Way Televisions, Distribution Of Moving Picture Or The Like (AREA)
- Television Systems (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
- Document Processing Apparatus (AREA)
Abstract
(57)【要約】 （修正有）
【課題】 圧縮コードワードを収めている第１部分及び
プレーン・テキストを収めている第２部分をもつ調整済
みモノトーン圧縮ファイルを、あるサイズをもちプレー
ン・テキストを収めている伸張ファイルに適切に伸張す
る。 【解決手段】 伸張ファイルのサイズをもつメモリ・バ
ッファ１００が割り当てられる。次に、調整されたモノ
トーン圧縮ファイル１２０′がバッファのボトム１２０
にストアされる。最後に、調整済みモノトーン圧縮ファ
イルの圧縮コードワードの第１部分に入っている圧縮コ
ードワードが伸張されて、伸張ファイルの対応する部分
のプレーン・テキストがバッファの先頭１４０に出力さ
れる。
プレーン・テキストを収めている第２部分をもつ調整済
みモノトーン圧縮ファイルを、あるサイズをもちプレー
ン・テキストを収めている伸張ファイルに適切に伸張す
る。 【解決手段】 伸張ファイルのサイズをもつメモリ・バ
ッファ１００が割り当てられる。次に、調整されたモノ
トーン圧縮ファイル１２０′がバッファのボトム１２０
にストアされる。最後に、調整済みモノトーン圧縮ファ
イルの圧縮コードワードの第１部分に入っている圧縮コ
ードワードが伸張されて、伸張ファイルの対応する部分
のプレーン・テキストがバッファの先頭１４０に出力さ
れる。
Description
【０００１】
【発明の属する技術分野】本発明はシステム内のデータ
・ファイルを圧縮し、伸張（復元）する方法に関し、も
っと具体的には、圧縮はオフラインで行われ、伸張はオ
ーディオ・ビデオ・インタラクティブ・システムのよう
な、メモリに制約のあるシステムでリアル・タイムに行
われる方法に関する。
・ファイルを圧縮し、伸張（復元）する方法に関し、も
っと具体的には、圧縮はオフラインで行われ、伸張はオ
ーディオ・ビデオ・インタラクティブ・システムのよう
な、メモリに制約のあるシステムでリアル・タイムに行
われる方法に関する。
【０００２】なお、本明細書の記述は本件出願の優先権
の基礎たる米国特許出願第０８／２８３，３４６号（１
９９４年８月１日出願）の明細書の記載に基づくもので
あって、当該米国特許出願の番号を参照することによっ
て当該米国特許出願の明細書の記載内容が本明細書の一
部分を構成するものとする。
の基礎たる米国特許出願第０８／２８３，３４６号（１
９９４年８月１日出願）の明細書の記載に基づくもので
あって、当該米国特許出願の番号を参照することによっ
て当該米国特許出願の明細書の記載内容が本明細書の一
部分を構成するものとする。
【０００３】
【従来の技術】オーディオ・ビデオ・インタラクティブ
(audio video interactive - AVI) システムは、テレビ
を見ている人がテレビジョン・プログラムとやりとり
（対話）できるようにする手段を備えているブロードキ
ャスト（放送）インタラクティブ・システムである。こ
のシステムでは、各受信側ロケーションは送信側ロケー
ションからのアプリケーション・プログラムをＡＶＩ信
号を介して受信するプロセッサを備えている。ＡＶＩ信
号は、標準テレビジョン信号と同じようにオーディオ成
分、すなわち音声成分とビデオ成分、すなわち映像成分
とインタラクティブ成分とを含んでいる複合信号(compo
site signal)である。インタラクティブ成分はアプリケ
ーション・プログラムを構成するコード・モジュールと
データ・モジュールを有する。アプリケーション・プロ
グラマは、コンパイラなどの標準的プログラミング・ツ
ールを使用してコード・モジュールとデータ・モジュー
ルをオフラインで生成している。これらのコード・モジ
ュールとデータ・モジュールはインタラクティブ成分に
組み込まれるように処理され、さらに音声成分およびビ
デオ成分と結合されてＡＶＩ信号が作られている。
(audio video interactive - AVI) システムは、テレビ
を見ている人がテレビジョン・プログラムとやりとり
（対話）できるようにする手段を備えているブロードキ
ャスト（放送）インタラクティブ・システムである。こ
のシステムでは、各受信側ロケーションは送信側ロケー
ションからのアプリケーション・プログラムをＡＶＩ信
号を介して受信するプロセッサを備えている。ＡＶＩ信
号は、標準テレビジョン信号と同じようにオーディオ成
分、すなわち音声成分とビデオ成分、すなわち映像成分
とインタラクティブ成分とを含んでいる複合信号(compo
site signal)である。インタラクティブ成分はアプリケ
ーション・プログラムを構成するコード・モジュールと
データ・モジュールを有する。アプリケーション・プロ
グラマは、コンパイラなどの標準的プログラミング・ツ
ールを使用してコード・モジュールとデータ・モジュー
ルをオフラインで生成している。これらのコード・モジ
ュールとデータ・モジュールはインタラクティブ成分に
組み込まれるように処理され、さらに音声成分およびビ
デオ成分と結合されてＡＶＩ信号が作られている。
【０００４】ＡＶＩ複合信号は受信側ロケーションへ送
信される。音声成分とビデオ成分はＡＶＩ複合信号から
抽出され、通常のテレビジョン・システムにおけると同
じように既知の方法で処理されて音（サウンド）と画像
（イメージ）を得ている。インタラクティブ成分は抽出
され、コード・モジュールとデータ・モジュールは受信
側ロケーションのプロセッサのメモリにロードされる。
ついで、このプロセッサはコード・モジュールを実行
し、データ・モジュールを処理して、多分、ＡＶＩ音声
サウンドとビデオ・イメージに重ねられるサウンドとグ
ラフィック・イメージを生成し、かつテレビを見ている
人からの入力に応答してテレビジョン・プログラミング
とやりとりする。
信される。音声成分とビデオ成分はＡＶＩ複合信号から
抽出され、通常のテレビジョン・システムにおけると同
じように既知の方法で処理されて音（サウンド）と画像
（イメージ）を得ている。インタラクティブ成分は抽出
され、コード・モジュールとデータ・モジュールは受信
側ロケーションのプロセッサのメモリにロードされる。
ついで、このプロセッサはコード・モジュールを実行
し、データ・モジュールを処理して、多分、ＡＶＩ音声
サウンドとビデオ・イメージに重ねられるサウンドとグ
ラフィック・イメージを生成し、かつテレビを見ている
人からの入力に応答してテレビジョン・プログラミング
とやりとりする。
【０００５】受信側ロケーションの機器は比較的低コス
トで製造し、販売することが考えられる。このコスト
は、各プロセッサに実装されるメモリ量を最小限とする
ことにより、そしてSGS/Thomson ST9 のように計算能力
が比較的低いマイクロプロセッサを使用することにより
低減化される。
トで製造し、販売することが考えられる。このコスト
は、各プロセッサに実装されるメモリ量を最小限とする
ことにより、そしてSGS/Thomson ST9 のように計算能力
が比較的低いマイクロプロセッサを使用することにより
低減化される。
【０００６】さらにまた、アプリケーション・プログラ
ムをいくつかの比較的小さなコード・モジュールとデー
タ・モジュール（32 kB 未満が代表例）に分割すること
が考えられる。インタラクティブ成分で利用できるバン
ド幅を最適化するために、コード・モジュールとデータ
・モジュールは圧縮されてから送信されるようにしてい
る。これらのモジュールは小さく、圧縮はオフラインで
行われるので、圧縮速度に対する関心は最低になってい
る。他方、SGS/Thomson ST9 のような、比較的低い計算
能力のマイクロプロセッサ（ビット・シフト能力に制約
がある（例えば、シングル・ビット・シフトである）の
で伸張に適していないマイクロプロセッサ）でも、伸張
（復元）は高速化することが要求される。さらに加え
て、受信側ロケーションのプロセッサでアプリケーショ
ン・プログラムをストアし、実行するために用意される
ＲＡＭ量は比較的小さい。従って、使用されるいかなる
伸張手法でも、最小限のメモリを使用することが要件に
なる。
ムをいくつかの比較的小さなコード・モジュールとデー
タ・モジュール（32 kB 未満が代表例）に分割すること
が考えられる。インタラクティブ成分で利用できるバン
ド幅を最適化するために、コード・モジュールとデータ
・モジュールは圧縮されてから送信されるようにしてい
る。これらのモジュールは小さく、圧縮はオフラインで
行われるので、圧縮速度に対する関心は最低になってい
る。他方、SGS/Thomson ST9 のような、比較的低い計算
能力のマイクロプロセッサ（ビット・シフト能力に制約
がある（例えば、シングル・ビット・シフトである）の
で伸張に適していないマイクロプロセッサ）でも、伸張
（復元）は高速化することが要求される。さらに加え
て、受信側ロケーションのプロセッサでアプリケーショ
ン・プログラムをストアし、実行するために用意される
ＲＡＭ量は比較的小さい。従って、使用されるいかなる
伸張手法でも、最小限のメモリを使用することが要件に
なる。
【０００７】従来の圧縮手法にはLempel-Ziv '77ファミ
リの圧縮アルゴリズムがある。これらの圧縮手法は、ソ
ース・データには繰返しが非常に多いという基本的考え
方を基礎にしている。以前に出現したものを指すポイン
タ（逆方向ポインタ(back pointer)と呼ばれる）と、多
分、一致(match) のサイズとを収めている特殊なコード
ワードで繰返しを置き換えることによって圧縮を達成す
ることができる。例えば、"abcdabcf"というソース・ス
トリングは次のようにコード化することが可能である。
リの圧縮アルゴリズムがある。これらの圧縮手法は、ソ
ース・データには繰返しが非常に多いという基本的考え
方を基礎にしている。以前に出現したものを指すポイン
タ（逆方向ポインタ(back pointer)と呼ばれる）と、多
分、一致(match) のサイズとを収めている特殊なコード
ワードで繰返しを置き換えることによって圧縮を達成す
ることができる。例えば、"abcdabcf"というソース・ス
トリングは次のようにコード化することが可能である。
【０００８】文字'a'、 'b'および'c' を出力にコピーす
る；一致のサイズ３を、現出力位置の４バイトあとから
出力にコピーしていく；文字'f' を出力にコピーする。
る；一致のサイズ３を、現出力位置の４バイトあとから
出力にコピーしていく；文字'f' を出力にコピーする。
【０００９】この手法を用いて圧縮されたソース・デー
タは、圧縮ファイルを先頭から最後までトラバース（走
査）することにより伸張することが可能であり、この場
合、後に戻ってトラッキングし(backtracking)、および
以前に読み取った圧縮データを再読取りしたりする必要
がない。さらに加えて、伸張プロセスが以前に伸張され
たデータへのアクセスを必要とするのが通常であって
も、伸張データもまた順次に出力される。このように伸
張することのできる圧縮手法はモノトーン(monotone)圧
縮／伸張手法と呼ばれている。
タは、圧縮ファイルを先頭から最後までトラバース（走
査）することにより伸張することが可能であり、この場
合、後に戻ってトラッキングし(backtracking)、および
以前に読み取った圧縮データを再読取りしたりする必要
がない。さらに加えて、伸張プロセスが以前に伸張され
たデータへのアクセスを必要とするのが通常であって
も、伸張データもまた順次に出力される。このように伸
張することのできる圧縮手法はモノトーン(monotone)圧
縮／伸張手法と呼ばれている。
【００１０】本発明者は、オーバラップ一致(overlappi
ng match) を使用することによって、さらに圧縮を行う
ことができることを認識した。オーバラップ一致では、
ソース・ファイル・データのうち次にコード化しようと
する部分が、コード化される繰返しの中に含まれてい
る。例えば、ソース・ストリング"abcabcabc" は、オー
バラップ一致を用いると、次のようにコード化すること
ができる。
ng match) を使用することによって、さらに圧縮を行う
ことができることを認識した。オーバラップ一致では、
ソース・ファイル・データのうち次にコード化しようと
する部分が、コード化される繰返しの中に含まれてい
る。例えば、ソース・ストリング"abcabcabc" は、オー
バラップ一致を用いると、次のようにコード化すること
ができる。
【００１１】文字'a'、 'b'および'c' を出力にコピーす
る；一致サイズ６を、現出力位置の３バイトあとから出
力にコピーしていく。
る；一致サイズ６を、現出力位置の３バイトあとから出
力にコピーしていく。
【００１２】言い換えると、上記ストリングの先頭から
始まる６文字ストリングは２番目の'abc' から始まる、
つまり、最初の'abc' がコード化されたあとの６文字ス
トリングと一致する。オーバラップ一致を使用すると、
オーバラップ一致を用いない場合よりも、圧縮ファイル
のサイズを小さくすることができる。伸張器(decompres
sor −伸張ルーチン）は、繰返しの最初のロケーション
から出力ファイル内の次のロケーションに文字を一度に
１文字ずつコピーすることによって、コード化された繰
返しを処理するものと解される。
始まる６文字ストリングは２番目の'abc' から始まる、
つまり、最初の'abc' がコード化されたあとの６文字ス
トリングと一致する。オーバラップ一致を使用すると、
オーバラップ一致を用いない場合よりも、圧縮ファイル
のサイズを小さくすることができる。伸張器(decompres
sor −伸張ルーチン）は、繰返しの最初のロケーション
から出力ファイル内の次のロケーションに文字を一度に
１文字ずつコピーすることによって、コード化された繰
返しを処理するものと解される。
【００１３】圧縮されたファイルのサイズを最小限とす
るために、現在の圧縮手法では、文字が直接にコピーさ
れることを示すコードワードと、以前に出現したものに
対する逆方向ポインタと一致のサイズ(match size)を収
めている特殊コードワードの構成を、これらのコードワ
ードのサイズを変化させることによって最適化してい
る。一般的に、直接に重ねてコピーされる文字のうち、
ある文字は他の文字よりも頻繁に出現する可能性があ
る。また、代表的なデータについて生成された逆方向ポ
インタと一致サイズを調べた結果明らかになったこと
は、あるサイズの一致の回数が２から約６または７のサ
イズまではほぼ指数的に減少していき、そのあとは減少
は急激に遅くなることである。同様に、繰返しに参照の
局所性(locality of reference) があるために、小さい
逆方向ポインタの方が大きい逆方向ポインタよりも多く
なっている（このことは一致パターンが現在位置に近い
ことを示している）。現在の圧縮手法は、コードワード
のサイズを連続的に変化させるエントロピー・コード化
(entropy coding)を用いて、特殊コードワードと不一致
の入力ストリングをコード化することにより、このよう
にゆがんだ逆方向ポインタと一致サイズの分布を利用し
ている。
るために、現在の圧縮手法では、文字が直接にコピーさ
れることを示すコードワードと、以前に出現したものに
対する逆方向ポインタと一致のサイズ(match size)を収
めている特殊コードワードの構成を、これらのコードワ
ードのサイズを変化させることによって最適化してい
る。一般的に、直接に重ねてコピーされる文字のうち、
ある文字は他の文字よりも頻繁に出現する可能性があ
る。また、代表的なデータについて生成された逆方向ポ
インタと一致サイズを調べた結果明らかになったこと
は、あるサイズの一致の回数が２から約６または７のサ
イズまではほぼ指数的に減少していき、そのあとは減少
は急激に遅くなることである。同様に、繰返しに参照の
局所性(locality of reference) があるために、小さい
逆方向ポインタの方が大きい逆方向ポインタよりも多く
なっている（このことは一致パターンが現在位置に近い
ことを示している）。現在の圧縮手法は、コードワード
のサイズを連続的に変化させるエントロピー・コード化
(entropy coding)を用いて、特殊コードワードと不一致
の入力ストリングをコード化することにより、このよう
にゆがんだ逆方向ポインタと一致サイズの分布を利用し
ている。
【００１４】本発明者は、逆方向ポインタと一致ポイン
タおよびコピー文字コードワードを収めている特殊コー
ドワードに対して真の可変長２次圧縮（エントロピー・
コード化）を使用することは、２つの理由からＡＶＩシ
ステムでは適していないことを認識した。第１の理由
は、このようなデータを伸張するには、コードワードが
バイト境界を尊重しないので、ビット・シフトを幅広く
使用する必要があることである。これは、一度に１桁
（１位置）ずつしかシフト（桁送り）ができないＳＴ９
のような、処理能力が比較的低いマイクロプロセッサで
は隘路となっている。可変シフトと回転を実行する際の
消費時間を最小限とするために、伸張ルーチン側に多大
の努力が要求される。第２の理由は、真の可変長コード
ワードの伸張を高速化するには、伸張器におけるルック
アップ・テーブルを作って、維持する必要があることで
ある。伸張器には、これらのルックアップ・テーブルを
作るための計算時間が必要であり、ルックアップ・テー
ブルをストアするためにシステムＲＡＭのスペースを割
り当てなければならない。ＡＶＩデコーダのシステムＲ
ＡＭが最小量に限られているので（これは第一にデータ
が圧縮されて送信される理由の１つである）、システム
ＲＡＭスペースが不足し可変長コードのデコードを高速
化するのに十分に大きいルックアップ・テーブルを作る
ことができない。
タおよびコピー文字コードワードを収めている特殊コー
ドワードに対して真の可変長２次圧縮（エントロピー・
コード化）を使用することは、２つの理由からＡＶＩシ
ステムでは適していないことを認識した。第１の理由
は、このようなデータを伸張するには、コードワードが
バイト境界を尊重しないので、ビット・シフトを幅広く
使用する必要があることである。これは、一度に１桁
（１位置）ずつしかシフト（桁送り）ができないＳＴ９
のような、処理能力が比較的低いマイクロプロセッサで
は隘路となっている。可変シフトと回転を実行する際の
消費時間を最小限とするために、伸張ルーチン側に多大
の努力が要求される。第２の理由は、真の可変長コード
ワードの伸張を高速化するには、伸張器におけるルック
アップ・テーブルを作って、維持する必要があることで
ある。伸張器には、これらのルックアップ・テーブルを
作るための計算時間が必要であり、ルックアップ・テー
ブルをストアするためにシステムＲＡＭのスペースを割
り当てなければならない。ＡＶＩデコーダのシステムＲ
ＡＭが最小量に限られているので（これは第一にデータ
が圧縮されて送信される理由の１つである）、システム
ＲＡＭスペースが不足し可変長コードのデコードを高速
化するのに十分に大きいルックアップ・テーブルを作る
ことができない。
【００１５】従って、主要目標は必要とするシステムＲ
ＡＭスペースを最小限としたままで伸張を高速化するこ
とである。本発明のひとつの形態によれば、圧縮データ
は制限された可変長コードワードで表現される。つま
り、コードワードは、真の可変長コード化によるのでは
なく、ニブル（４ビット）の倍数である長さに制限され
ている。このような方式によると、真の可変長コードワ
ードで必要であった非常に多数回のシフトと回転オペレ
ーション（演算）を必要とすることなくコードワードの
長さをある程度最適化することができる。
ＡＭスペースを最小限としたままで伸張を高速化するこ
とである。本発明のひとつの形態によれば、圧縮データ
は制限された可変長コードワードで表現される。つま
り、コードワードは、真の可変長コード化によるのでは
なく、ニブル（４ビット）の倍数である長さに制限され
ている。このような方式によると、真の可変長コードワ
ードで必要であった非常に多数回のシフトと回転オペレ
ーション（演算）を必要とすることなくコードワードの
長さをある程度最適化することができる。
【００１６】
【発明が解決しようとする課題】従来の伸張過程では、
圧縮ファイルは第１のメモリ・バッファに書込まれてい
る。第２のメモリ・バッファは伸張されたソース・ファ
イルを収めておくために割り当てられている。そのあ
と、第１メモリ・バッファに入っている圧縮ファイルが
初めから終わりまで調べられ、再構築されたソース・デ
ータ・ファイルが第２メモリ・バッファに書込まれる。
このような手法によると、圧縮ファイルを伸張するため
には２つのメモリ・バッファを割り当てる必要がある。
圧縮ファイルは第１のメモリ・バッファに書込まれてい
る。第２のメモリ・バッファは伸張されたソース・ファ
イルを収めておくために割り当てられている。そのあ
と、第１メモリ・バッファに入っている圧縮ファイルが
初めから終わりまで調べられ、再構築されたソース・デ
ータ・ファイルが第２メモリ・バッファに書込まれる。
このような手法によると、圧縮ファイルを伸張するため
には２つのメモリ・バッファを割り当てる必要がある。
【００１７】
【課題を解決するための手段】本発明者は、モノトーン
（単調）圧縮／伸張手法の原理を用いて、圧縮ファイル
を適切に伸張することが可能になるようにした。つま
り、圧縮ファイルが受信されると、伸張されるソース・
ファイルを入れておくのに十分なサイズのひとつのバッ
ファがメモリ内に割り当てられる。圧縮ファイルはその
バッファに書込まれる。圧縮ファイルがソース・ファイ
ルに伸張されると、その全体が単一のメモリ・バッファ
に収まるようになる。このようにすると、圧縮ファイル
を入れておくための別個のバッファが不要になるので、
伸張のために必要なメモリ量が最小限となる。
（単調）圧縮／伸張手法の原理を用いて、圧縮ファイル
を適切に伸張することが可能になるようにした。つま
り、圧縮ファイルが受信されると、伸張されるソース・
ファイルを入れておくのに十分なサイズのひとつのバッ
ファがメモリ内に割り当てられる。圧縮ファイルはその
バッファに書込まれる。圧縮ファイルがソース・ファイ
ルに伸張されると、その全体が単一のメモリ・バッファ
に収まるようになる。このようにすると、圧縮ファイル
を入れておくための別個のバッファが不要になるので、
伸張のために必要なメモリ量が最小限となる。
【００１８】本発明の原理によれば、圧縮コードワード
を収めている第１部分およびプレーン・テキストを収め
ている第２部分をもつ調整済みのモノトーン圧縮ファイ
ルを、あるサイズをもち、かつプレーン・テキスト(pla
in text)を収めている伸張ファイルに適切に伸張するた
めの方法は次のステップを具える。まず、伸張されるフ
ァイルのサイズをもつメモリ・バッファが割り当てられ
る。次に、調整済みのモノトーン圧縮ファイルがバッフ
ァのボトムにストアされる。最後に、調整済みのモノト
ーン圧縮ファイルの第１部分に入っている圧縮コードワ
ードが伸張されて、伸張ファイルの対応する部分のプレ
ーン・テキストがバッファのトップに出力される。
を収めている第１部分およびプレーン・テキストを収め
ている第２部分をもつ調整済みのモノトーン圧縮ファイ
ルを、あるサイズをもち、かつプレーン・テキスト(pla
in text)を収めている伸張ファイルに適切に伸張するた
めの方法は次のステップを具える。まず、伸張されるフ
ァイルのサイズをもつメモリ・バッファが割り当てられ
る。次に、調整済みのモノトーン圧縮ファイルがバッフ
ァのボトムにストアされる。最後に、調整済みのモノト
ーン圧縮ファイルの第１部分に入っている圧縮コードワ
ードが伸張されて、伸張ファイルの対応する部分のプレ
ーン・テキストがバッファのトップに出力される。
【００１９】ソース・ファイルを調整済みのモノトーン
圧縮ファイルに圧縮するための方法は次のステップを具
える。まず、ソース・ファイルは圧縮コードワードを収
めている圧縮ファイルにモノトーン圧縮される。次に、
圧縮ファイルは、圧縮コードワードを収めている第１部
分およびプレーン・テキストを収めている第２部分をも
つ調整済みのモノトーン圧縮ファイルが得られるように
調整される。ソース・ファイルを本発明に従って圧縮す
ると、もとの圧縮ファイルと同じサイズをもつ調整済み
の圧縮ファイルが得られる。
圧縮ファイルに圧縮するための方法は次のステップを具
える。まず、ソース・ファイルは圧縮コードワードを収
めている圧縮ファイルにモノトーン圧縮される。次に、
圧縮ファイルは、圧縮コードワードを収めている第１部
分およびプレーン・テキストを収めている第２部分をも
つ調整済みのモノトーン圧縮ファイルが得られるように
調整される。ソース・ファイルを本発明に従って圧縮す
ると、もとの圧縮ファイルと同じサイズをもつ調整済み
の圧縮ファイルが得られる。
【００２０】
【発明の実施の形態】図１は、ＡＶＩ信号デコーダのう
ち本発明を取り入れている部分を示すブロック図であ
る。図１に示すデコーダは各ＡＶＩ受信側ロケーション
に設置されている。図１において、ＡＶＩ信号源（図示
せず）はデコーダの入力端子５に結合されている。入力
端子５はＡＶＩ信号受信装置３０の入力端子に結合され
ている。ＡＶＩ信号受信装置３０の出力端子は処理ユニ
ット４０のシステム・バス４１６に結合されている。処
理ユニット４０はSGS/Thomson ST9 のような中央処理ユ
ニット（ＣＰＵ）４１０、読み／書きメモリ（ＲＡＭ）
４１２およびリードオンリ・メモリ（ＲＯＭ）４１４を
有し、これらはシステム・バス４１６を介して公知のよ
うに一緒に結合されている。
ち本発明を取り入れている部分を示すブロック図であ
る。図１に示すデコーダは各ＡＶＩ受信側ロケーション
に設置されている。図１において、ＡＶＩ信号源（図示
せず）はデコーダの入力端子５に結合されている。入力
端子５はＡＶＩ信号受信装置３０の入力端子に結合され
ている。ＡＶＩ信号受信装置３０の出力端子は処理ユニ
ット４０のシステム・バス４１６に結合されている。処
理ユニット４０はSGS/Thomson ST9 のような中央処理ユ
ニット（ＣＰＵ）４１０、読み／書きメモリ（ＲＡＭ）
４１２およびリードオンリ・メモリ（ＲＯＭ）４１４を
有し、これらはシステム・バス４１６を介して公知のよ
うに一緒に結合されている。
【００２１】オーディオ信号をＡＶＩオーディオ出力端
子２５へ供給するオーディオ・プロセッサ４１８、ビデ
オ信号をＡＶＩビデオ出力端子１５へ供給するビデオ・
プロセッサ４２０、および入力端子３５を経てユーザか
らのデータを受け取るユーザ入出力（Ｉ／Ｏ）アダプタ
４２４も、すべてが公知のようにシステム・バス４１６
に結合されている。例えば、並置コンピュータにつなが
る入出力ポート、モデム、数値演算(math)プロセッサ、
その他の入出力アダプタなどの他の機器もまた、公知の
ようにシステム・バス４１６に結合することができ、そ
してデコーダ格納装置（エンクロージャ）の外側の格納
装置内の他の機器と結合するためにバス・エクステンダ
を設けることもできる。
子２５へ供給するオーディオ・プロセッサ４１８、ビデ
オ信号をＡＶＩビデオ出力端子１５へ供給するビデオ・
プロセッサ４２０、および入力端子３５を経てユーザか
らのデータを受け取るユーザ入出力（Ｉ／Ｏ）アダプタ
４２４も、すべてが公知のようにシステム・バス４１６
に結合されている。例えば、並置コンピュータにつなが
る入出力ポート、モデム、数値演算(math)プロセッサ、
その他の入出力アダプタなどの他の機器もまた、公知の
ようにシステム・バス４１６に結合することができ、そ
してデコーダ格納装置（エンクロージャ）の外側の格納
装置内の他の機器と結合するためにバス・エクステンダ
を設けることもできる。
【００２２】動作時には、ＡＶＩ信号源はパケットのス
トリームの形でＡＶＩ信号を出力する。ＡＶＩ信号源
は、デコーダに対する、例えば、直接ＲＦ衛星リンク、
ケーブル・システム・フィードまたは光ファイバ・リン
クとすることができる。これらのパケットの一部はＡＶ
Ｉ信号のオーディオ成分を搬送し、他のパケットはビデ
オ成分を搬送し、さらに他のパケットはインタラクティ
ブ成分を搬送している。ＡＶＩ信号受信装置３０は受信
したＡＶＩ信号を処理して、オーディオ成分、ビデオ成
分およびインタラクティブ成分を形成しているパケット
を抽出し、パケットに入っているデータを、ＲＡＭ４１
２内に以前に指定されていた、それぞれのメモリ・バッ
ファに既知のＤＭＡ書込み手法を用いてストアする。つ
いで、オーディオ・プロセッサ４１８とビデオ・プロセ
ッサ４２０は既知のＤＭＡ読取り手法を用いて、データ
をＲＡＭ４１２内のそれぞれのメモリ・バッファから読
み取る。次に、オーディオ・プロセッサ４１８とビデオ
・プロセッサ４２０はそれぞれのデータを処理してＡＶ
Ｉオーディオ信号を出力端子２５から、ＡＶＩビデオ信
号を出力端子１５からそれぞれ出力する。ＣＰＵ４１０
をビデオ・プロセッサ４２０および／またはオーディオ
・プロセッサ４１８による処理と協働させることもでき
る。インタラクティブ成分パケットはコード・モジュー
ルとデータ・モジュールを搬送し、ＣＰＵ４１０の制御
の下で以下に説明するように処理される。
トリームの形でＡＶＩ信号を出力する。ＡＶＩ信号源
は、デコーダに対する、例えば、直接ＲＦ衛星リンク、
ケーブル・システム・フィードまたは光ファイバ・リン
クとすることができる。これらのパケットの一部はＡＶ
Ｉ信号のオーディオ成分を搬送し、他のパケットはビデ
オ成分を搬送し、さらに他のパケットはインタラクティ
ブ成分を搬送している。ＡＶＩ信号受信装置３０は受信
したＡＶＩ信号を処理して、オーディオ成分、ビデオ成
分およびインタラクティブ成分を形成しているパケット
を抽出し、パケットに入っているデータを、ＲＡＭ４１
２内に以前に指定されていた、それぞれのメモリ・バッ
ファに既知のＤＭＡ書込み手法を用いてストアする。つ
いで、オーディオ・プロセッサ４１８とビデオ・プロセ
ッサ４２０は既知のＤＭＡ読取り手法を用いて、データ
をＲＡＭ４１２内のそれぞれのメモリ・バッファから読
み取る。次に、オーディオ・プロセッサ４１８とビデオ
・プロセッサ４２０はそれぞれのデータを処理してＡＶ
Ｉオーディオ信号を出力端子２５から、ＡＶＩビデオ信
号を出力端子１５からそれぞれ出力する。ＣＰＵ４１０
をビデオ・プロセッサ４２０および／またはオーディオ
・プロセッサ４１８による処理と協働させることもでき
る。インタラクティブ成分パケットはコード・モジュー
ルとデータ・モジュールを搬送し、ＣＰＵ４１０の制御
の下で以下に説明するように処理される。
【００２３】上述したように、インタラクティブ成分の
バンド幅を最大にするために、アプリケーション・プロ
グラマはコード・モジュールおよび／またはデータ・モ
ジュールをLempel-Ziv '77手法などのモノトーン圧縮手
法を用いて圧縮してから、それらをＡＶＩ信号のインタ
ラクティブ成分に含ませるようにすることができる。さ
らに加えて、オーバラップ一致を用いてモジュールをさ
らに圧縮することができる。図２は、本発明の好適実施
例に従って圧縮されたファイルに入っているソース・デ
ータを表しているコードワードの構造を示すメモリ・レ
イアウト図である。好適実施例では、圧縮ファイルはコ
ードワードの順次のブロックの形態になっている。各ブ
ロックは１コード・バイトのヘッダＨＤＲと、そのあと
に続く８個のコードワード（ＣＷ１−ＣＷ８）とを有す
る。
バンド幅を最大にするために、アプリケーション・プロ
グラマはコード・モジュールおよび／またはデータ・モ
ジュールをLempel-Ziv '77手法などのモノトーン圧縮手
法を用いて圧縮してから、それらをＡＶＩ信号のインタ
ラクティブ成分に含ませるようにすることができる。さ
らに加えて、オーバラップ一致を用いてモジュールをさ
らに圧縮することができる。図２は、本発明の好適実施
例に従って圧縮されたファイルに入っているソース・デ
ータを表しているコードワードの構造を示すメモリ・レ
イアウト図である。好適実施例では、圧縮ファイルはコ
ードワードの順次のブロックの形態になっている。各ブ
ロックは１コード・バイトのヘッダＨＤＲと、そのあと
に続く８個のコードワード（ＣＷ１−ＣＷ８）とを有す
る。
【００２４】図３は、図２におけるヘッダＨＤＲとコー
ドワード（ＣＷ１−ＣＷ８）との関係を示す詳細メモリ
・レイアウト図である。１コード・バイトのヘッダは各
コードワードに対するビット・フラグを収めており、コ
ードワードは、ヘッダの第１ビットから最初のコードワ
ードまでの矢印と、ヘッダの第２ビットから２番目のコ
ードワードまでの矢印とで図３に示すように、連続して
いる。ヘッダのビットが１ならば、対応するコードワー
ドは圧縮されていないデータ・バイトを表すコード・バ
イトであり、伸張時に伸張ファイルにコピーする必要が
あることを示している。ヘッダのビットが０ならば、対
応するコードワードは逆方向ポインタ／一致サイズのコ
ードワードである。
ドワード（ＣＷ１−ＣＷ８）との関係を示す詳細メモリ
・レイアウト図である。１コード・バイトのヘッダは各
コードワードに対するビット・フラグを収めており、コ
ードワードは、ヘッダの第１ビットから最初のコードワ
ードまでの矢印と、ヘッダの第２ビットから２番目のコ
ードワードまでの矢印とで図３に示すように、連続して
いる。ヘッダのビットが１ならば、対応するコードワー
ドは圧縮されていないデータ・バイトを表すコード・バ
イトであり、伸張時に伸張ファイルにコピーする必要が
あることを示している。ヘッダのビットが０ならば、対
応するコードワードは逆方向ポインタ／一致サイズのコ
ードワードである。
【００２５】図４の（ａ）から（ｊ）までは、逆方向ポ
インタ／一致サイズを表すコードワードのそれぞれのフ
ォーマットを示す詳細メモリ・レイアウト図である。上
述したように、コードワードは可変長であるが、ニブル
（４バイト）の倍数に制限されている。図４において、
コードワードの長さ（つまり、ニブル数）、逆方向ポイ
ンタの値および一致のサイズは次のようにして判断され
る。第１ビットが１ならば、コードワードは２または３
ニブルのコードワードである。第２ビットが０ならば、
一致サイズは２である。第３ビットが０ならば（図４の
（ａ））、２ニブルのコードワードであり、次の５ビッ
トは逆方向ポインタ（ＢＰ）−１を表している。第３ビ
ットが１ならば（図４の（ｂ））、３ニブルのコードで
あり、次の５ビットは最下位ビット（ＬＳＢ）を表し、
次のニブルは逆方向ポインタ（ＢＰ）−１の最上位ビッ
ト（ＭＳＢ）を表している。
インタ／一致サイズを表すコードワードのそれぞれのフ
ォーマットを示す詳細メモリ・レイアウト図である。上
述したように、コードワードは可変長であるが、ニブル
（４バイト）の倍数に制限されている。図４において、
コードワードの長さ（つまり、ニブル数）、逆方向ポイ
ンタの値および一致のサイズは次のようにして判断され
る。第１ビットが１ならば、コードワードは２または３
ニブルのコードワードである。第２ビットが０ならば、
一致サイズは２である。第３ビットが０ならば（図４の
（ａ））、２ニブルのコードワードであり、次の５ビッ
トは逆方向ポインタ（ＢＰ）−１を表している。第３ビ
ットが１ならば（図４の（ｂ））、３ニブルのコードで
あり、次の５ビットは最下位ビット（ＬＳＢ）を表し、
次のニブルは逆方向ポインタ（ＢＰ）−１の最上位ビッ
ト（ＭＳＢ）を表している。
【００２６】第２および第３ビットが１０ならば、一致
サイズは３である。第４ビットが０ならば（図４の
（ｃ））、２ニブルのコードワードであり、次の４ビッ
トは逆方向ポインタ（ＢＰ）−１を表している。第４ビ
ットが１ならば（図４の（ｄ））、３ニブルのコードワ
ードであり、次の４ビットは最下位ビット（ＬＳＢ）を
表し、次のニブルは逆方向ポインタ（ＢＰ）−１の最上
位ビット（ＭＳＢ）を表している。第２、第３および第
４ビットがそれぞれ１１０ならば（図４の（ｅ））、一
致サイズは４であり、コードワードのサイズは３ニブル
である。次の４ビットは最下位ビット（ＬＳＢ）を表
し、次のニブルは逆方向ポインタ（ＢＰ）−１の最上位
ビット（ＭＳＢ）を表している。第２、第３および第４
ビットがそれぞれ１１１ならば（図４の（ｆ））、一致
サイズは５であり、コードワードのサイズは３ニブルで
ある。次の４ビットは最下位ビット（ＬＳＢ）を表し、
次のニブルは逆方向ポインタ（ＢＰ）−１の最上位ビッ
ト（ＭＳＢ）を表している。
サイズは３である。第４ビットが０ならば（図４の
（ｃ））、２ニブルのコードワードであり、次の４ビッ
トは逆方向ポインタ（ＢＰ）−１を表している。第４ビ
ットが１ならば（図４の（ｄ））、３ニブルのコードワ
ードであり、次の４ビットは最下位ビット（ＬＳＢ）を
表し、次のニブルは逆方向ポインタ（ＢＰ）−１の最上
位ビット（ＭＳＢ）を表している。第２、第３および第
４ビットがそれぞれ１１０ならば（図４の（ｅ））、一
致サイズは４であり、コードワードのサイズは３ニブル
である。次の４ビットは最下位ビット（ＬＳＢ）を表
し、次のニブルは逆方向ポインタ（ＢＰ）−１の最上位
ビット（ＭＳＢ）を表している。第２、第３および第４
ビットがそれぞれ１１１ならば（図４の（ｆ））、一致
サイズは５であり、コードワードのサイズは３ニブルで
ある。次の４ビットは最下位ビット（ＬＳＢ）を表し、
次のニブルは逆方向ポインタ（ＢＰ）−１の最上位ビッ
ト（ＭＳＢ）を表している。
【００２７】コードワードの第１ビットが０ならば、一
致サイズはコードワード内にコード化される。これらの
コードワードでは、一致サイズと逆方向ポインタは次の
ようにして判断される。第２、第３および第４ビットが
それぞれ１１１でなければ（図４の（ｇ））、コードワ
ードのサイズは２コード・バイト（４ニブル）である。
このような場合には、第２、第３および第４ビットは値
Ｍを表している。一致サイズはＭ＋３である。残りの１
２ビット（現在のコード・バイトからの４ビットと次の
コードワードからの８ビット）は値Ｂを表している。逆
方向ポインタはＢ＋１である。第２、第３および第４ビ
ットがそれぞれ１１１ならば、コードワードは少なくと
も３コード・バイトである。次の５ビットが１１１１１
でなければ（図４の（ｈ））、コードワードは３コード
・バイトからなっている。第５、第６、第７、第８およ
び第９ビットは値Ｍを表している。一致サイズはＭ＋３
である。逆方向ポインタ（ＢＰ）は最後の１５ビット＋
１である。これは逆方向ポインタの最大許容サイズ（つ
まり、３２Ｋ）である。
致サイズはコードワード内にコード化される。これらの
コードワードでは、一致サイズと逆方向ポインタは次の
ようにして判断される。第２、第３および第４ビットが
それぞれ１１１でなければ（図４の（ｇ））、コードワ
ードのサイズは２コード・バイト（４ニブル）である。
このような場合には、第２、第３および第４ビットは値
Ｍを表している。一致サイズはＭ＋３である。残りの１
２ビット（現在のコード・バイトからの４ビットと次の
コードワードからの８ビット）は値Ｂを表している。逆
方向ポインタはＢ＋１である。第２、第３および第４ビ
ットがそれぞれ１１１ならば、コードワードは少なくと
も３コード・バイトである。次の５ビットが１１１１１
でなければ（図４の（ｈ））、コードワードは３コード
・バイトからなっている。第５、第６、第７、第８およ
び第９ビットは値Ｍを表している。一致サイズはＭ＋３
である。逆方向ポインタ（ＢＰ）は最後の１５ビット＋
１である。これは逆方向ポインタの最大許容サイズ（つ
まり、３２Ｋ）である。
【００２８】第５、第６、第７、第８および第９ビット
がそれぞれ１１１１１ならば、コードは少なくとも４コ
ード・バイト長である。このようなコードワードでは、
逆方向ポインタは次の１５ビット＋１の値である（図４
の（ｈ）と同じ）。最後のコード・バイトが２５５（つ
まり、１１１１１１１１）でなければ（図４の
（ｉ））、最後のコード・バイトは値Ｍになっている。
一致サイズはＭ＋３４である。しかし、このバイトが値
２５５（つまり、１１１１１１１１）になっていれば
（図４の（ｊ））、コードワードは実際には６コード・
バイト長である。逆方向ポインタ（ＢＰ）は図４の
（ｉ）と同じ位置に入っている。最後の２コードバイト
（バイト５と６）は値Ｍになっている。一致サイズはＭ
＋２８９である。
がそれぞれ１１１１１ならば、コードは少なくとも４コ
ード・バイト長である。このようなコードワードでは、
逆方向ポインタは次の１５ビット＋１の値である（図４
の（ｈ）と同じ）。最後のコード・バイトが２５５（つ
まり、１１１１１１１１）でなければ（図４の
（ｉ））、最後のコード・バイトは値Ｍになっている。
一致サイズはＭ＋３４である。しかし、このバイトが値
２５５（つまり、１１１１１１１１）になっていれば
（図４の（ｊ））、コードワードは実際には６コード・
バイト長である。逆方向ポインタ（ＢＰ）は図４の
（ｉ）と同じ位置に入っている。最後の２コードバイト
（バイト５と６）は値Ｍになっている。一致サイズはＭ
＋２８９である。
【００２９】このコード化方法では、より共通の逆方向
ポインタ／一致サイズに対してはより小さなコードワー
ドが使用されるが、より共通ではない逆方向ポインタ／
一致サイズに対してはより大きなコードワードが必要に
なる。さらに加えて、すべてのコードワードの長さはニ
ブルの倍数になっている。コードワードの長さをニブル
の倍数に制限することにより、すべてのコードワードは
メモリ内のバイト境界から始まるか、あるいはメモリ内
のバイト内のニブル境界から始まる。ＳＴ９のような多
くのローエンド・プロセッサはバイト内の２ニブルをス
ワップする命令をもっているので、多数のシフトを行う
必要なく、コードワードを効率よく抽出することが可能
である。さらに、圧縮器(compressor −圧縮ルーチン）
はコードワードがメモリのどこに置かれているかを知っ
ているので、伸張マイクロセッサによる検索が高速化さ
れるような形でコードワードをコード化する。
ポインタ／一致サイズに対してはより小さなコードワー
ドが使用されるが、より共通ではない逆方向ポインタ／
一致サイズに対してはより大きなコードワードが必要に
なる。さらに加えて、すべてのコードワードの長さはニ
ブルの倍数になっている。コードワードの長さをニブル
の倍数に制限することにより、すべてのコードワードは
メモリ内のバイト境界から始まるか、あるいはメモリ内
のバイト内のニブル境界から始まる。ＳＴ９のような多
くのローエンド・プロセッサはバイト内の２ニブルをス
ワップする命令をもっているので、多数のシフトを行う
必要なく、コードワードを効率よく抽出することが可能
である。さらに、圧縮器(compressor −圧縮ルーチン）
はコードワードがメモリのどこに置かれているかを知っ
ているので、伸張マイクロセッサによる検索が高速化さ
れるような形でコードワードをコード化する。
【００３０】例えば、コード・バイト X = b7.b6.....b
0 を出力バイトＹ内のニブル境界に置くとすると、それ
を出力バイトＹとＹ＋１との間に置く１つの方法は、次
のようになる。
0 を出力バイトＹ内のニブル境界に置くとすると、それ
を出力バイトＹとＹ＋１との間に置く１つの方法は、次
のようになる。
【００３１】
【数１】 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) その結果得た１６ビット・ワードの２バイトを加算、つ
まり、論理和（ＯＲ）演算を実行することにより、コー
ド・バイトを抽出することが可能になる。ＳＴ９では、
この最適化によって節減される時間は、従来の方法にお
ける４回のビット・シフト操作のうちの２回を減らすこ
とと等価である。
まり、論理和（ＯＲ）演算を実行することにより、コー
ド・バイトを抽出することが可能になる。ＳＴ９では、
この最適化によって節減される時間は、従来の方法にお
ける４回のビット・シフト操作のうちの２回を減らすこ
とと等価である。
【００３６】本発明によれば、上述したように圧縮され
た圧縮ファイルは適切な伸張が行えるように調整され
る。この調節を行うためには、オリジナル・ソース・フ
ァイルと圧縮ファイルの双方のサイズをひかえておき、
圧縮ファイルは２回目に処理される。
た圧縮ファイルは適切な伸張が行えるように調整され
る。この調節を行うためには、オリジナル・ソース・フ
ァイルと圧縮ファイルの双方のサイズをひかえておき、
圧縮ファイルは２回目に処理される。
【００３７】図５および図６は、圧縮ファイルに対して
調整を行って適切に伸張を行うことができるようにする
ことを理解するのに役立つメモリ図である。図５におい
て、バッファ・メモリ１００は縦方向の矩形で示されて
いる。バッファの総サイズは伸張されたファイルを収容
するのに十分なサイズになっている。圧縮ファイルに対
して調整を行うために、圧縮プロセスは、以下に説明す
るように、伸張を適切に行うことを試み、かつその試み
の結果をモニタすることにより、以前に圧縮されたファ
イルの処理を続けていく。圧縮されたファイル１２０は
バッファ１００のボトムに書込まれ、これは図５に陰影
を付けた矩形で示されている。入力ポインタは圧縮ファ
イル１２０内の最初のロケーションを指すようにセット
され、出力ポインタは伸張ファイルが書込まれるメモリ
・バッファ１００内の最初のロケーションを指すように
セットされる。以下で詳しく説明するが、圧縮プロセッ
サの調整フェーズの間は、圧縮ファイル１２０内のデー
タは入力ポインタが指しているロケーションから読み取
られ、入力ポインタが前進する。データは出力ポインタ
が指しているロケーションにおいてメモリ・バッファ１
００の先頭に書込まれ、出力ポインタが前進される。こ
れらはすべて既知のやり方である。
調整を行って適切に伸張を行うことができるようにする
ことを理解するのに役立つメモリ図である。図５におい
て、バッファ・メモリ１００は縦方向の矩形で示されて
いる。バッファの総サイズは伸張されたファイルを収容
するのに十分なサイズになっている。圧縮ファイルに対
して調整を行うために、圧縮プロセスは、以下に説明す
るように、伸張を適切に行うことを試み、かつその試み
の結果をモニタすることにより、以前に圧縮されたファ
イルの処理を続けていく。圧縮されたファイル１２０は
バッファ１００のボトムに書込まれ、これは図５に陰影
を付けた矩形で示されている。入力ポインタは圧縮ファ
イル１２０内の最初のロケーションを指すようにセット
され、出力ポインタは伸張ファイルが書込まれるメモリ
・バッファ１００内の最初のロケーションを指すように
セットされる。以下で詳しく説明するが、圧縮プロセッ
サの調整フェーズの間は、圧縮ファイル１２０内のデー
タは入力ポインタが指しているロケーションから読み取
られ、入力ポインタが前進する。データは出力ポインタ
が指しているロケーションにおいてメモリ・バッファ１
００の先頭に書込まれ、出力ポインタが前進される。こ
れらはすべて既知のやり方である。
【００３８】圧縮プロセスの調整フェーズの間に、圧縮
ファイル１２０は標準モノトーン伸張プロセスを使用し
て伸張され、その間、入力ポインタと出力ポインタの状
態（ステート）がモニタされる。図６は圧縮プロセスの
伸張フェーズの進み具合を一連のメモリ図で示すもので
ある。図６において、メモリ・バッファ１００のうちデ
ータを収容している部分は陰影付きで示されており、デ
ータを収容していない部分は陰影なしで示されている。
図６の（ａ）は図５に対応し、調整のための伸張プロセ
スの開始時のメモリ・バッファ１００の状態を示し、入
力ポインタ（ＩＰ）は圧縮ファイル１２０（陰影付き）
の先頭を指すようにセットされ、出力ポインタ（ＯＰ）
はメモリ・バッファ１００の先頭を指すようにセットさ
れている。
ファイル１２０は標準モノトーン伸張プロセスを使用し
て伸張され、その間、入力ポインタと出力ポインタの状
態（ステート）がモニタされる。図６は圧縮プロセスの
伸張フェーズの進み具合を一連のメモリ図で示すもので
ある。図６において、メモリ・バッファ１００のうちデ
ータを収容している部分は陰影付きで示されており、デ
ータを収容していない部分は陰影なしで示されている。
図６の（ａ）は図５に対応し、調整のための伸張プロセ
スの開始時のメモリ・バッファ１００の状態を示し、入
力ポインタ（ＩＰ）は圧縮ファイル１２０（陰影付き）
の先頭を指すようにセットされ、出力ポインタ（ＯＰ）
はメモリ・バッファ１００の先頭を指すようにセットさ
れている。
【００３９】図６の（ｂ）は伸張プロセスが開始された
直後のメモリ・バッファ１００の状態を示している。図
６の（ｂ）に示すように、圧縮ファイル１２０の第１部
分は、入力ポインタＩＰが下方に移動したことによって
示すようにすでに読み取られている。伸張プロセスの
間、モノトーン圧縮ファイルでは逆方向トラッキングが
行われないので、メモリ・バッファ１００のうちすでに
読み取られた部分は再度読み取られることはないので、
陰影なしで示すように、この部分にデータを入れること
が可能である。同時に、伸張ファイル１４０の第１部分
は、すでに読み取られた圧縮ファイル１２０の部分に応
答して、すでに生成されている。伸張ファイル１４０の
この第１部分は、出力ポインタＯＰの移動で示すよう
に、メモリ・バッファ１００の先頭にすでに書込まれて
いる。
直後のメモリ・バッファ１００の状態を示している。図
６の（ｂ）に示すように、圧縮ファイル１２０の第１部
分は、入力ポインタＩＰが下方に移動したことによって
示すようにすでに読み取られている。伸張プロセスの
間、モノトーン圧縮ファイルでは逆方向トラッキングが
行われないので、メモリ・バッファ１００のうちすでに
読み取られた部分は再度読み取られることはないので、
陰影なしで示すように、この部分にデータを入れること
が可能である。同時に、伸張ファイル１４０の第１部分
は、すでに読み取られた圧縮ファイル１２０の部分に応
答して、すでに生成されている。伸張ファイル１４０の
この第１部分は、出力ポインタＯＰの移動で示すよう
に、メモリ・バッファ１００の先頭にすでに書込まれて
いる。
【００４０】図６の（ｃ）は伸張がさらに進んだときの
メモリ・バッファ１００の状態を示している。入力ポイ
ンタＩＰのロケーションで示すように、圧縮ファイル１
２０の大部分が読み取られており、そして、出力ポイン
タＯＰのロケーションが示すように、さらに伸張ソース
・ファイルの大部分が生成されている。図６の（ｃ）か
らわかるように、出力ポインタＯＰのロケーションは入
力ポインタＩＰのロケーションの近くまで到達してい
る。
メモリ・バッファ１００の状態を示している。入力ポイ
ンタＩＰのロケーションで示すように、圧縮ファイル１
２０の大部分が読み取られており、そして、出力ポイン
タＯＰのロケーションが示すように、さらに伸張ソース
・ファイルの大部分が生成されている。図６の（ｃ）か
らわかるように、出力ポインタＯＰのロケーションは入
力ポインタＩＰのロケーションの近くまで到達してい
る。
【００４１】出力ポインタＯＰが入力ポインタＩＰに追
いつくと、伸張ソース・ファイル１４０の新たに書込ま
れる部分は次に読み取られる圧縮ファイル１２０の部分
にオーバライト（重書き）するので、圧縮ファイル１２
０をさらにデコードすることは不可能になる。図６の
（ｄ）はそのような状態を示している。図６の（ｄ）に
おいて、次のコードワードは、入力ポインタＩＰの動き
で示すように、圧縮ファイル１２０から読み取られる。
このコードワードは図６の（ｅ）に陰影付き矩形ＣＷで
示されている。図示のコードワードＣＷは逆方向ポイン
タ／一致サイズ・コードワードであり、これは、図６の
（ｅ）に陰影付き矩形で示すようにプレーン・テキスト
ＰＴを生成する。図から明らかなように、プレーン・テ
キストＰＴのサイズは、これが出力ポインタＯＰのロケ
ーションにおいてバッファ１００に書込まれるときに、
圧縮ファイル１２０の次に読み取られる部分にオーバラ
イトするようなサイズになっている。ついで、出力ポイ
ンタ（ＯＰ）は伸張ファイルの新たに書込まれた部分の
ボトムを指すことになるが、これは入力ポインタ（Ｉ
Ｐ）の値以下になっている。このように出力ポインタ
（ＯＰ）が入力ポインタ（ＩＰ）を通り越したことのた
めには、圧縮プロセスの調整フェーズが入力ポインタ
（ＩＰ）と出力ポインタ（ＯＰ）をモニタしている。
いつくと、伸張ソース・ファイル１４０の新たに書込ま
れる部分は次に読み取られる圧縮ファイル１２０の部分
にオーバライト（重書き）するので、圧縮ファイル１２
０をさらにデコードすることは不可能になる。図６の
（ｄ）はそのような状態を示している。図６の（ｄ）に
おいて、次のコードワードは、入力ポインタＩＰの動き
で示すように、圧縮ファイル１２０から読み取られる。
このコードワードは図６の（ｅ）に陰影付き矩形ＣＷで
示されている。図示のコードワードＣＷは逆方向ポイン
タ／一致サイズ・コードワードであり、これは、図６の
（ｅ）に陰影付き矩形で示すようにプレーン・テキスト
ＰＴを生成する。図から明らかなように、プレーン・テ
キストＰＴのサイズは、これが出力ポインタＯＰのロケ
ーションにおいてバッファ１００に書込まれるときに、
圧縮ファイル１２０の次に読み取られる部分にオーバラ
イトするようなサイズになっている。ついで、出力ポイ
ンタ（ＯＰ）は伸張ファイルの新たに書込まれた部分の
ボトムを指すことになるが、これは入力ポインタ（Ｉ
Ｐ）の値以下になっている。このように出力ポインタ
（ＯＰ）が入力ポインタ（ＩＰ）を通り越したことのた
めには、圧縮プロセスの調整フェーズが入力ポインタ
（ＩＰ）と出力ポインタ（ＯＰ）をモニタしている。
【００４２】本発明によれば、次に、圧縮ファイル１２
０は以下のようにして調整される。出力ポインタ（Ｏ
Ｐ）の新しいロケーションから圧縮ファイル１２０の最
後までの圧縮ファイル内のコードワードは圧縮されてい
ないソース・ファイルからのプレーン・テキストで置き
換えられる。その結果として調整された圧縮ファイル１
２０′は図６の（ｆ）に示されている。図６の（ｆ）に
おいて、調整された圧縮ファイル１２０′は圧縮されて
いないソース・ファイルの対応する部分を表しているコ
ードワードを収めている第１部分１２４と、圧縮されて
いないソース・ファイルの対応する部分のプレーン・テ
キストを表しているデータを収めている第２部分１２６
（濃い陰影で示している）とを含んでいる。コードワー
ドがそこで終わり、プレーン・テキストがそこから始ま
る、調整された圧縮ファイル１２０′内のロケーション
はプレーン・インデックス（ＰＩ）と呼ばれ、これもひ
かえておく。ヘッダＨＤＲは、伸張ファイル（ＤＳ）の
サイズ、圧縮ファイル（ＣＳ）のサイズおよびプレーン
・インデックス（ＰＩ）を表すデータを（とりわけ）収
めている調整された圧縮ファイル１２０′の先頭に付加
される。
０は以下のようにして調整される。出力ポインタ（Ｏ
Ｐ）の新しいロケーションから圧縮ファイル１２０の最
後までの圧縮ファイル内のコードワードは圧縮されてい
ないソース・ファイルからのプレーン・テキストで置き
換えられる。その結果として調整された圧縮ファイル１
２０′は図６の（ｆ）に示されている。図６の（ｆ）に
おいて、調整された圧縮ファイル１２０′は圧縮されて
いないソース・ファイルの対応する部分を表しているコ
ードワードを収めている第１部分１２４と、圧縮されて
いないソース・ファイルの対応する部分のプレーン・テ
キストを表しているデータを収めている第２部分１２６
（濃い陰影で示している）とを含んでいる。コードワー
ドがそこで終わり、プレーン・テキストがそこから始ま
る、調整された圧縮ファイル１２０′内のロケーション
はプレーン・インデックス（ＰＩ）と呼ばれ、これもひ
かえておく。ヘッダＨＤＲは、伸張ファイル（ＤＳ）の
サイズ、圧縮ファイル（ＣＳ）のサイズおよびプレーン
・インデックス（ＰＩ）を表すデータを（とりわけ）収
めている調整された圧縮ファイル１２０′の先頭に付加
される。
【００４３】
【実施例】好適実施例では、上述した調整プロセスが行
われても、実際には、図６に示すように、ソース・ファ
イル１４０は圧縮ファイル１２０から再構築されない。
再構築がシミュレートされるだけである。圧縮ファイル
１２０はトラバースされ、入力ポインタ（ＩＰ）と出力
ポインタ（ＯＰ）は、実際の伸張が行われたとしたらそ
うなるであろうように正確に維持されるが、伸張ファイ
ル１４０は実際には作成されない。圧縮ファイル１２０
で調整が必要な個所が現れると、圧縮ファイル１２０
は、上述したように、第１部分１２４に入っているコー
ドワードと第２部分１２６に入っているプレーン・テキ
ストで書き直される。そのあと、調整されたファイル１
２０′にヘッダが付加される。
われても、実際には、図６に示すように、ソース・ファ
イル１４０は圧縮ファイル１２０から再構築されない。
再構築がシミュレートされるだけである。圧縮ファイル
１２０はトラバースされ、入力ポインタ（ＩＰ）と出力
ポインタ（ＯＰ）は、実際の伸張が行われたとしたらそ
うなるであろうように正確に維持されるが、伸張ファイ
ル１４０は実際には作成されない。圧縮ファイル１２０
で調整が必要な個所が現れると、圧縮ファイル１２０
は、上述したように、第１部分１２４に入っているコー
ドワードと第２部分１２６に入っているプレーン・テキ
ストで書き直される。そのあと、調整されたファイル１
２０′にヘッダが付加される。
【００４４】以上から理解されるように、調整された圧
縮ファイル１２０′の長さは最初に生成された圧縮ファ
イル（図６の（ａ）から（ｄ）までに破線で示されてい
る）とまったく同じになっている。つまり、この手法で
は、圧縮ファイルのサイズが大きくなることはない。
縮ファイル１２０′の長さは最初に生成された圧縮ファ
イル（図６の（ａ）から（ｄ）までに破線で示されてい
る）とまったく同じになっている。つまり、この手法で
は、圧縮ファイルのサイズが大きくなることはない。
【００４５】伸張は、受信した調整された圧縮ファイル
１２０′のヘッダＨＤＲを読み取り、バッファ（図６の
１００）に伸張ファイル１４０のサイズ（ＤＳ）をＲＡ
Ｍ４１２（図１）内に割り当て、調整されたファイル１
２０′（ヘッダＨＤＲは除かれている）をバッファ１０
０のボトムにストアすることによって、行うことができ
る。調整された圧縮ファイル１２０′の開始アドレス
は、ヘッダＨＤＲから抽出された圧縮ファイルのサイズ
（ＣＳ）と伸張ファイルのサイズ（ＤＳ）から計算する
ことができる。入力ポインタ（ＩＰ）はバッファ１００
内の調整された圧縮ファイル１２０′の先頭を指すよう
にセットされ、出力ポインタ（ＯＰ）はバッファ１００
の先頭を指すようにセットされる。ついで、標準モノト
ーン伸張手法が調整された圧縮ファイル１２０′の第１
部分で実行されるが、これは、出力ポインタ（ＯＰ）の
値がプレーン・インデックスと等しくなるまで、図６に
示すのと同じように入力ポインタ（ＩＰ）と出力ポイン
タ（ＯＰ）を使用して行われる。その個所からは、プレ
ーン・テキストだけが調整された圧縮ファイル１２０′
に入っているので、それ以後の伸張は不要である。調整
された圧縮ファイル１２０′の伸張が２つのバッファを
使用して行われる場合は（つまり、適切でない場合）、
伸張ファイル１４０内の出力ポインタ（ＯＰ）がプレー
ン・インデックス（ＰＩ）まで来ると、入力ポインタ
（ＩＰ）はリセットされ、調整された圧縮ファイル１２
０′内のプレーン・インデックス（ＰＩ）の位置も指す
ようになり、調整された圧縮ファイル１２０′の残り部
分は未変更のまま伸張ファイル１４０にコピーされる。
１２０′のヘッダＨＤＲを読み取り、バッファ（図６の
１００）に伸張ファイル１４０のサイズ（ＤＳ）をＲＡ
Ｍ４１２（図１）内に割り当て、調整されたファイル１
２０′（ヘッダＨＤＲは除かれている）をバッファ１０
０のボトムにストアすることによって、行うことができ
る。調整された圧縮ファイル１２０′の開始アドレス
は、ヘッダＨＤＲから抽出された圧縮ファイルのサイズ
（ＣＳ）と伸張ファイルのサイズ（ＤＳ）から計算する
ことができる。入力ポインタ（ＩＰ）はバッファ１００
内の調整された圧縮ファイル１２０′の先頭を指すよう
にセットされ、出力ポインタ（ＯＰ）はバッファ１００
の先頭を指すようにセットされる。ついで、標準モノト
ーン伸張手法が調整された圧縮ファイル１２０′の第１
部分で実行されるが、これは、出力ポインタ（ＯＰ）の
値がプレーン・インデックスと等しくなるまで、図６に
示すのと同じように入力ポインタ（ＩＰ）と出力ポイン
タ（ＯＰ）を使用して行われる。その個所からは、プレ
ーン・テキストだけが調整された圧縮ファイル１２０′
に入っているので、それ以後の伸張は不要である。調整
された圧縮ファイル１２０′の伸張が２つのバッファを
使用して行われる場合は（つまり、適切でない場合）、
伸張ファイル１４０内の出力ポインタ（ＯＰ）がプレー
ン・インデックス（ＰＩ）まで来ると、入力ポインタ
（ＩＰ）はリセットされ、調整された圧縮ファイル１２
０′内のプレーン・インデックス（ＰＩ）の位置も指す
ようになり、調整された圧縮ファイル１２０′の残り部
分は未変更のまま伸張ファイル１４０にコピーされる。
【図１】ＡＶＩ信号デコーダのうち本発明を取り入れて
いる部分を示すブロック図である。
いる部分を示すブロック図である。
【図２】本発明の好適実施例に従って圧縮されたファイ
ル内のソース・データを表しているコードワードの構造
を示すメモリ・レイアウト図である。
ル内のソース・データを表しているコードワードの構造
を示すメモリ・レイアウト図である。
【図３】図２におけるヘッダＨＤＲとコードワード（Ｃ
Ｗ１−ＣＷ８）との関係を示す詳細メモリ・レイアウト
図である。
Ｗ１−ＣＷ８）との関係を示す詳細メモリ・レイアウト
図である。
【図４】逆方向ポインタ／一致サイズを表しているコー
ドワードのそれぞれのフォーマットを示す詳細メモリ・
レイアウト図である。
ドワードのそれぞれのフォーマットを示す詳細メモリ・
レイアウト図である。
【図５】圧縮ファイルに対して調整を行って適切に伸張
を行うことができるようにすることを理解するのに役立
つメモリ図である。
を行うことができるようにすることを理解するのに役立
つメモリ図である。
【図６】圧縮ファイルに対して調整を行って適切に伸張
を行うことができるようにすることを理解するのに役立
つメモリ図である。
を行うことができるようにすることを理解するのに役立
つメモリ図である。
１００ メモリ・バッファ １２０ 圧縮ファイル １２０′ 調整済みの圧縮ファイル １２４ 第１部分 １２６ 第２部分 １４０ 伸張ソース・ファイル ＣＷ コードワード ＨＤＲ ヘッダ ＩＰ 入力ポインタ ＯＰ 出力ポインタ ＰＩ プレーン・インデックス ＰＴ プレーン・テキスト
───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.6 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｇ０６Ｆ 5/00 Ｈ Ｈ０３Ｍ 7/30 Ｚ 9382−5Ｋ Ｈ０４Ｎ 7/24 7/173
Claims (10)
- 【請求項１】 圧縮コードワードを収めている第１部分
とプレーン・テキストを収めている第２部分とをもつ調
整済みモノトーン圧縮ファイルを、あるサイズをもち、
かつプレーン・テキストを収めている伸張ファイルに適
切に伸張する方法であって、 伸張ファイルのサイズをもつメモリ・バッファを割り当
てる割り当てステップと、 調整済みモノトーン圧縮ファイルを前記バッファのボト
ムにストアするストア・ステップと、 調整済み圧縮ファイルの第１部分に入っている圧縮コー
ドワードを伸張して伸張ファイルの対応する部分のプレ
ーン・テキストを前記バッファのトップに生成する伸張
ステップとを具えたことを特徴とする伸張方法。 - 【請求項２】 請求項１に記載の伸張方法において、前
記伸張ステップは、 調整済みモノトーン圧縮ファイルの先頭に対応する前記
バッファ内のロケーションを指すように入力ポインタを
セットするステップと、 前記バッファの先頭を指すように出力ポインタをセット
するステップと、 前記入力ポインタが指している前記バッファ内のロケー
ションからコードワードを読み取って、前記入力ポイン
タを前進させるステップと、 コードワードをデコードしてプレーン・テキストを出力
するステップと、 そのプレーン・テキストを前記出力ポインタが指してい
る前記バッファ内のロケーションに書き込んで、前記出
力ポインタを前進させるステップと、 前記出力ポインタが前記第２部分のロケーションに対応
するまで読取り、デコードおよび書込みステップを繰り
返していくステップとを具えたことを特徴とする伸張方
法。 - 【請求項３】 請求項１に記載の伸張方法において、 前記調整済みモノトーン圧縮ファイルは、さらに、ある
サイズをもち、かつ前記調整済みモノトーン圧縮ファイ
ルのサイズ、前記伸張ファイルのサイズおよび前記第２
部分のロケーションを表すデータを収めているヘッダを
含んでおり、 前記割り当てステップはヘッダを読んで前記圧縮ファイ
ルのサイズを決定するステップを含んでおり、 前記ストア・ステップは、 前記ヘッダを読んで前記調整済みモノトーン圧縮ファイ
ルのサイズと前記伸張ファイルのサイズとを決定するス
テップと、 前記調整済みモノトーン圧縮ファイルの先頭に対する前
記バッファ内のロケーションを、前記調整済みモノトー
ン圧縮ファイルと前記伸張ファイルのサイズから計算す
るステップと、 前記調整済みモノトーン圧縮ファイルを、計算で求めた
ロケーションを先頭にして前記バッファにストアしてい
くステップとを含み、 前記伸張ステップは、 前記ヘッダを読んで前記第２部分のロケーションを決定
するステップと、 前記調整済みモノトーン圧縮ファイルの先頭に対する前
記バッファ内の計算で求めたロケーションを指すように
前記入力ポインタをセットするステップと、 前記バッファの先頭を指すように前記出力ポインタをセ
ットするステップと、 前記入力ポインタが指している前記バッファ内のロケー
ションからコードワードを読み取って、前記入力ポイン
タを前進させるステップと、 そのコードワードをデコードしてプレーン・テキストを
出力するステップと、 前記出力ポインタが指している前記バッファ内のロケー
ションに当該プレーン・テキストを書き込んで、前記出
力ポインタを前進させるステップと、 前記出力ポインタが前記第２部分のロケーションに対応
するまで読取り、デコードおよび書込みステップを繰り
返していくステップとを具えたことを特徴とする伸張方
法。 - 【請求項４】 請求項１に記載の伸張方法において、 前記第１部分における圧縮コードワードはオーバラップ
する一致を用いて反復ストリング内の文字のロケーショ
ンと文字数を表すコードワードを含み、 前記伸張ステップは前記反復ストリング内の文字数を、
前記反復ストリングの、伸張ファイル内におけるロケー
ションから前記伸張ファイルの対応する部分へ、一文字
ずつコピーすることによって、反復ストリングを表すコ
ードワードを伸張するステップとを含んでいることを特
徴とする伸張方法。 - 【請求項５】 請求項１に記載の伸張方法において、前
記圧縮コードワードはそれぞれがニブルの倍数である長
さを有することを特徴とする伸張方法。 - 【請求項６】 あるサイズをもつソース・ファイルを調
整されたモノトーン圧縮ファイルに圧縮する方法であっ
て、 前記ソース・ファイルを圧縮コードワードを収めている
圧縮ファイルにモノトーン圧縮するモノトーン圧縮ステ
ップと、 前記圧縮ファイルを調整して、圧縮コードワードを収め
ている第１部分とプレーン・テキストを収めている第２
部分とをもつ調整済みモノトーン圧縮ファイルを出力す
る調整ステップとを具えたことを特徴とする圧縮方法。 - 【請求項７】 請求項６に記載の圧縮方法において、前
記圧縮コードワードはそれぞれがニブルの倍数である長
さを有することを特徴とする圧縮方法。 - 【請求項８】 請求項６に記載の圧縮方法において、前
記調整ステップは、 前記ソース・ファイルのサイズをもつメモリ・バッファ
を割り当てることをシミュレートするステップと、 前記圧縮ファイルを前記バッファのボトムにストアする
ことをシミュレートするステップと、 前記圧縮ファイルの先頭を指すように前記入力ポインタ
をセットするステップと、 前記バッファの先頭を指すように前記出力ポインタをセ
ットすることをシミュレートするステップと、 前記入力ポインタが指している前記圧縮ファイル内のロ
ケーションからコードワードを読み取り、そのあとで前
記入力ポインタを前進させるステップと、 そのコードワードをデコードしてプレーン・テキストを
出力することをシミュレートするステップと、 前記出力ポインタを前進させることにより、前記出力ポ
インタが指している前記バッファ内のロケーションに前
記プレーン・テキストを書くことをシミュレートするス
テップと、 コードワードのデコードのシミュレーションによって、
デコードされていれば、前記出力ポインタが前記入力ポ
インタを通過するまで読取りステップ、デコードのシミ
ュレーション・ステップおよび書込みのシミュレーショ
ン・ステップを繰り返すステップとを実行することによ
り、前記圧縮ファイルを伸張することをシミュレートす
るステップと、 コードワードのデコードのシミュレーションによって、
前記出力ポインタが前記入力ポインタを通過したとき、
前記出力ポインタが指しているロケーションに対応する
前記ソース・ファイル内のロケーションから前記ソース
・ファイルの終わりまでプレーン・テキストを前記圧縮
ファイルにコピーして、調整済み圧縮ファイルを出力す
るステップを実行するステップとを具えたことを特徴と
する圧縮方法。 - 【請求項９】 請求項６に記載の圧縮方法において、前
記ソース・ファイルのサイズ、前記調整済み圧縮ファイ
ルのサイズ、およびプレーン・テキストを収めている前
記調整済み圧縮ファイル内のロケーションを表している
データを収めているヘッダを前記圧縮ファイルに追加す
るステップをさらに含むことを特徴とする圧縮方法。 - 【請求項１０】 請求項６に記載の圧縮方法において、
前記モノトーン圧縮ステップはオーバラップする一致を
用いて圧縮コードワードを生成することを特徴とする圧
縮方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US28334694A | 1994-08-01 | 1994-08-01 | |
| US283346 | 1994-08-01 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0879719A true JPH0879719A (ja) | 1996-03-22 |
| JP3869033B2 JP3869033B2 (ja) | 2007-01-17 |
Family
ID=23085603
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP19689995A Expired - Lifetime JP3869033B2 (ja) | 1994-08-01 | 1995-08-01 | データ・ファイルの圧縮および伸張方法 |
Country Status (6)
| Country | Link |
|---|---|
| US (1) | US5841953A (ja) |
| EP (1) | EP0696107B1 (ja) |
| JP (1) | JP3869033B2 (ja) |
| KR (1) | KR100339772B1 (ja) |
| CN (1) | CN1127219C (ja) |
| DE (1) | DE69524999T2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2022117668A (ja) * | 2021-02-01 | 2022-08-12 | 三菱電機株式会社 | データ圧縮装置、データ復号装置、データ圧縮方法、データ復号方法、データ圧縮プログラム及びデータ復号プログラム |
Families Citing this family (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100313290B1 (ko) * | 1996-04-18 | 2002-02-28 | 쥬리 페트로비치 밀토 | 이진코드압축과복원방법병렬압축과복원프로세서 |
| US6567911B1 (en) * | 1999-12-06 | 2003-05-20 | Adaptec, Inc. | Method of conserving memory resources during execution of system BIOS |
| JP3540243B2 (ja) | 2000-04-24 | 2004-07-07 | Ｎｅｃエレクトロニクス株式会社 | 半導体記憶装置 |
| US7158255B2 (en) * | 2002-06-18 | 2007-01-02 | Lexmark International, Inc. | Method for printing shingling print data |
| FR2878668B1 (fr) * | 2004-11-26 | 2007-07-13 | Siemens Vdo Automotive Sas | Procede de compression de donnees numeriques |
| JP6476618B2 (ja) * | 2014-07-07 | 2019-03-06 | 富士通株式会社 | 伸長方法、伸長プログラムおよび伸長装置 |
| US10283091B2 (en) * | 2014-10-13 | 2019-05-07 | Microsoft Technology Licensing, Llc | Buffer optimization |
| US10374628B2 (en) | 2017-04-05 | 2019-08-06 | International Business Machines Corporation | In-place data compression with small working memory |
| CN108197204B (zh) * | 2017-12-28 | 2021-12-21 | 北京安博通科技股份有限公司 | 文件处理方法及装置 |
| US10768861B1 (en) * | 2019-02-27 | 2020-09-08 | Microsoft Technology Licensing, Llc | In-place safe decompression |
| CN113111040B (zh) * | 2021-04-21 | 2024-04-30 | 郑旭纯 | 一种文件解压方法及装置 |
| US20230004533A1 (en) * | 2021-07-01 | 2023-01-05 | Microsoft Technology Licensing, Llc | Hybrid intermediate stream format |
Family Cites Families (21)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4494151A (en) * | 1979-07-02 | 1985-01-15 | Xerox Corporation | 4-Pixel run-length code for data compression |
| US4597057A (en) * | 1981-12-31 | 1986-06-24 | System Development Corporation | System for compressed storage of 8-bit ASCII bytes using coded strings of 4 bit nibbles |
| US4888645A (en) * | 1984-01-16 | 1989-12-19 | International Business Machines Corporation | Method for encoding and decoding a digital image |
| US4876541A (en) * | 1987-10-15 | 1989-10-24 | Data Compression Corporation | Stem for dynamically compressing and decompressing electronic data |
| US5108207A (en) * | 1988-07-20 | 1992-04-28 | Matsushita Electric Industrial Co., Ltd. | Printer with variable memory size |
| US5003307A (en) * | 1989-01-13 | 1991-03-26 | Stac, Inc. | Data compression apparatus with shift register search means |
| US5018060A (en) * | 1989-01-26 | 1991-05-21 | Ibm Corporation | Allocating data storage space of peripheral data storage devices using implied allocation based on user parameters |
| US5109433A (en) * | 1989-10-13 | 1992-04-28 | Microsoft Corporation | Compressing and decompressing text files |
| US5049881A (en) * | 1990-06-18 | 1991-09-17 | Intersecting Concepts, Inc. | Apparatus and method for very high data rate-compression incorporating lossless data compression and expansion utilizing a hashing technique |
| JPH0753454B2 (ja) * | 1990-07-06 | 1995-06-07 | 株式会社日立製作所 | テキスト情報処理装置 |
| US5212565A (en) * | 1990-11-19 | 1993-05-18 | Allied-Signal Inc. | Method for reducing amount of stored digital image data without degrading a reconstituted image |
| US5168356A (en) * | 1991-02-27 | 1992-12-01 | General Electric Company | Apparatus for segmenting encoded video signal for transmission |
| US5179378A (en) * | 1991-07-30 | 1993-01-12 | University Of South Florida | Method and apparatus for the compression and decompression of data using Lempel-Ziv based techniques |
| JP3233173B2 (ja) * | 1992-01-07 | 2001-11-26 | セイコーエプソン株式会社 | ラスタイメージシリアルプリンタ |
| EP0582907A3 (en) * | 1992-08-10 | 1995-05-10 | Stac Electronics Inc | Device and method for data compression using search by comparison of strings and Huffman coding. |
| US5394534A (en) * | 1992-09-11 | 1995-02-28 | International Business Machines Corporation | Data compression/decompression and storage of compressed and uncompressed data on a same removable data storage medium |
| BR9405508A (pt) * | 1993-07-12 | 1999-09-08 | Sony Corp | Processo e aparelho decodificador e codificador de imagem. |
| DE69420797T2 (de) * | 1993-07-30 | 2000-03-23 | Victor Company Of Japan, Ltd. | Verfahren und Vorrichtung zur Übertragung von digitalen Daten |
| JP3509080B2 (ja) * | 1993-10-15 | 2004-03-22 | ソニー株式会社 | データ再生装置 |
| JP2611637B2 (ja) * | 1993-11-22 | 1997-05-21 | 日本電気株式会社 | 画像圧縮伸長装置 |
| JP2760287B2 (ja) * | 1994-07-01 | 1998-05-28 | ヤマハ株式会社 | ディスク記録再生装置 |
-
1995
- 1995-07-21 EP EP95111495A patent/EP0696107B1/en not_active Expired - Lifetime
- 1995-07-21 DE DE69524999T patent/DE69524999T2/de not_active Expired - Lifetime
- 1995-07-31 CN CN95109053A patent/CN1127219C/zh not_active Expired - Fee Related
- 1995-08-01 KR KR1019950024084A patent/KR100339772B1/ko not_active Expired - Lifetime
- 1995-08-01 JP JP19689995A patent/JP3869033B2/ja not_active Expired - Lifetime
-
1996
- 1996-07-01 US US08/674,302 patent/US5841953A/en not_active Expired - Lifetime
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2022117668A (ja) * | 2021-02-01 | 2022-08-12 | 三菱電機株式会社 | データ圧縮装置、データ復号装置、データ圧縮方法、データ復号方法、データ圧縮プログラム及びデータ復号プログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| US5841953A (en) | 1998-11-24 |
| KR100339772B1 (ko) | 2002-10-31 |
| JP3869033B2 (ja) | 2007-01-17 |
| DE69524999D1 (de) | 2002-02-21 |
| EP0696107A3 (en) | 1997-10-15 |
| EP0696107B1 (en) | 2002-01-16 |
| DE69524999T2 (de) | 2002-07-18 |
| CN1124436A (zh) | 1996-06-12 |
| EP0696107A2 (en) | 1996-02-07 |
| KR960009755A (ko) | 1996-03-22 |
| CN1127219C (zh) | 2003-11-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6425125B1 (en) | System and method for upgrading client software | |
| US8090027B2 (en) | Data compression using an arbitrary-sized dictionary | |
| EP0813167A2 (en) | Method and apparatus for font compression and decompression | |
| JP3007235B2 (ja) | 可変長符号の伸長装置および圧縮伸長装置 | |
| JPH0879719A (ja) | データ・ファイルの圧縮および伸張方法 | |
| JPH0368219A (ja) | データ圧縮装置及び方法 | |
| JPH0662262A (ja) | デジタル画像ｃｏｄｅｃ（圧縮及び伸長）プロセッサ用ブロック制御方法及び装置 | |
| US20030128878A1 (en) | Method and device for forming a derived digital signal from a compressed digital signal | |
| JP2863065B2 (ja) | マッチングストリング探索およびハフマン符号化を用いたデータ圧縮装置および方法ならびにデータ伸長装置および方法 | |
| US5751860A (en) | Method for compressing and decompressing digital image data | |
| WO2021034749A1 (en) | Decompression engine for decompressing compressed input data that includes multiple streams of data | |
| CN112165331A (zh) | 数据压缩方法及其装置、数据解压方法及其装置、存储介质及电子设备 | |
| JPH0876969A (ja) | 圧縮済みデータを不連続メモリに記憶するデータ圧伸方法 | |
| US6363176B1 (en) | Picture data decompression apparatus | |
| JPH11145849A (ja) | 符号化方法及びデータ圧縮器 | |
| US6748520B1 (en) | System and method for compressing and decompressing a binary code image | |
| JPH07170196A (ja) | ２値シンボルの符号化・復号化回路 | |
| JP3266419B2 (ja) | データ圧縮・伸長方式 | |
| JPH09247466A (ja) | 符号化装置 | |
| JP2003318739A (ja) | データシーケンスを圧縮するシステム、方法、およびコンピュータ読み取り可能媒体 | |
| JP3499589B2 (ja) | 符号化装置及び符号化方法 | |
| JPH0621827A (ja) | データ圧縮装置及びその方法 | |
| WO1991006153A1 (en) | Huffman data string decompression apparatus and method | |
| JPS63176049A (ja) | デ−タ圧縮方式 | |
| JPH0563583A (ja) | データ圧縮及び復元方法並びにこれらの方法を使用した電子交換機におけるバツクアツプ方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20051028 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20060130 |
|
| RD04 | Notification of resignation of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7424 Effective date: 20060130 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20060206 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20060428 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20060526 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20060828 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20060912 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20061012 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20091020 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101020 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111020 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20121020 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20131020 Year of fee payment: 7 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| EXPY | Cancellation because of completion of term |