JPH08223053A

JPH08223053A - 圧縮データの伸張方法

Info

Publication number: JPH08223053A
Application number: JP7278762A
Authority: JP
Inventors: Robert A Rust; ロバート・エー・ラスト
Original assignee: Hewlett Packard Co
Current assignee: HP Inc
Priority date: 1994-12-14
Filing date: 1995-10-26
Publication date: 1996-08-30
Anticipated expiration: 2015-10-26
Also published as: JP3342788B2; KR960024895A; US5680601A; KR100381518B1

Abstract

(57)【要約】【課題】リテラル・プレフィックスの使用頻度を減少さ
せることによってデータ圧縮伸張システムの圧縮比率を
向上させる。【解決手段】原データのストリングを辞書の有効エレメ
ントと比較し、一致した辞書位置をポイントする符号を
圧縮データに出力する。一致が検出されない場合該スト
リングをリテラルと定義し、該リテラルによってポイン
トされる辞書エレメントが有効である場合のみリテラル
・プレフィックスを出力し、最後に、いずれの場合も該
リテラルを出力する。伸張の場合は、取り出した圧縮デ
ータのエントリが、リテラル・プレフィックスであれ
ば、次のエントリを取り出しリテラルとして出力する。
リテラル・プレフィックスでなくとも、無効な辞書エレ
メントをポイントしていれば、そのエントリはリテラル
であるのでそのまま出力する。その他の場合は、符号で
あるので適切な伸張を行ったのち出力する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、データ圧縮に関す
るもので、特に、リテラル・プレフィックスの必要性を
減らすことによる圧縮比率効率の改善に関するものであ
る。

【０００２】

【従来の技術】ディジタル・データ信号のストリームを
圧縮デジタル符号信号へ符号化し、圧縮デジタル符号信
号を逆に元のデータにデコードするデータ圧縮システム
は、従来技術において既知のものである。データ圧縮と
は、所与の形式のデータを元のデータより少ない記憶空
間で済むように代替形式に変換することを試みるプロセ
スを云う。データ圧縮システムの目的は、所与の量のデ
ジタル情報を保持するために必要な記憶域またはそれを
転送するために必要とされる時間の節約を実現すること
である。

【０００３】実用的効用を発揮するためには、データ圧
縮システムは、一定の基準を満たさなければならない。
システムは、相互関係を持たなければならない。データ
圧縮システムが相互関係の特性を持つためには、圧縮さ
れたデータをいかなる情報の変更または損失なしに元の
形式に再伸張またはデコ―ドすることが可能でなければ
ならない。デコードされたデータと元のデータは、互い
に同一で見分けがつかないものでなければならない。相
互関係の特性は、情報理論の中で使われる厳格な無雑音
の特性と同義である。アプリケーションによっては、相
互関係の特性に厳格に固執しないものもある。そのよう
なアプリケーションの特別の例の１つは、グラフィック
・データである。人間の目は、雑音にさほど敏感ではな
いので、圧縮伸張プロセスの間の若干の情報の変更また
は損失は許容される。

【０００４】システムは、データ圧縮伸張システムが交
信する装置によって提供され受容されるデータ転送速度
に関して十分なパフォーマンスを提供しなければならな
い。データが圧縮される速度は、典型的には毎秒何百万
バイト（メガバイト／秒）という圧縮システムへの入力
データ処理速度によって決定される。典型的には１メガ
バイト／秒を越える現在のディスク、テープおよび通信
システムにおいて達成されるデータ速度を維持するに十
分なパフォーマンスが必要とされる。従って、データ圧
縮伸張システムは、システム全体に影響を及ぼさないよ
うに十分なデータ・バンド幅を持たなければならない。
典型的には、データ圧縮伸張システムのパフォーマンス
は、圧縮し、伸張するために必要な計算、および統計デ
ータを記憶し、圧縮伸張プロセスに指針を与えるために
利用されるランダム・アクセス・メモリ（ＲＡＭ）など
のシステム・コンポーネントの速度によって制約され
る。

【０００５】データ圧縮伸張システムの設計におけるも
う１つの重要な基準は、圧縮比率によって特徴づけられ
る圧縮効率である。圧縮比率は、未圧縮形式のデータ・
サイズを圧縮形式のサイズで除算した比率である。デー
タが圧縮可能であるためには、データは冗長度を含まな
ければならない。圧縮効率は、圧縮プロシージャが入力
データ中の冗長度を効果的に使用する度合いによって決
定される。典型的なコンピュータ記憶データにおいて
は、冗長度は、個々のシンボル、見本数字、バイトまた
は文字の非定形的使用および共通語、ブランク・レコー
ド・フィールドなどのような記号系列の頻繁な繰り返し
の両者において発生する。

【０００６】従来技術における既知の多目的データ圧縮
プロシージャは、、ハフマン（HUffman）法、タンスト
ール(Tunstall)法およびレンペル−ジブ(Lempel-Ziv)法
の３つである。ハフマン法は、広く普及しているもの
で、D.A.Huffman 著"A MethodFor Construction Of Min
imum Redundancy Codes", Proceedings IRE, 40, 1 0pa
ges 1098-1 1 00 (Sept. 1 952)に記載されている。タ
ンストール法は、B. P.Tunstallの博士論文 "Synthesis
of NoiselessCompression Codes", Georgia Institute
of Technology (Sept. 1 967)で参照できる。レンペル
−ジブ法は、J.ZivおよびA.Lempel共著の"A Universal
Algorithm For Sequential Data Compression", IEEE T
ransactions on Information Theory, IT-23, 3, pages
337-343 (May, 1977)に記載されている。

【０００７】レンペル−ジブ法では、可変長セグメント
記号を可変長２進値語にマップする。入力または出力セ
グメントに制約が何もない場合、それは、何の問題もな
く最適である。このプロシージャにおいては、入力デー
タ・ストリングは、解析の上適切に拡張したセグメント
に変換される。各セグメントは、以前の入力ストリング
部分の正確なコピーに当該入力データに含まれる１つの
新しい符号が末尾に加えられたもので構成される。作成
されるべきコピーは、可能な限り最長のもので、以前に
解析されたセグメントと一致するように制約されない。
出力においてセグメントを置き換える符号語は、以前に
コピーされた部分が開始する位置を示すポインタ、コピ
ーの長さおよび新しい記号から成る情報を含む。

【０００８】コストを合理的に保つため、データ圧縮
は、電子写真のようなページ・プリンタの技術分野にお
いて使用される。例えば、６００ドット／インチ（ＤＰ
Ｉ）の１ページは、約４ＭＢの大きさである。圧縮技術
を使用することによって、これを約１ＭＢに減少させる
ことができる。電子写真印刷の技術分野では、伸張プロ
セスに関するパフォーマンス上の制約がある。特に、圧
縮されたデータは、プリント・エンジンへのデータの一
定の流入を提供するために必要とされる速度で伸張され
なければならない。このパフォーマンス必要条件が充足
されることを保証するため、伸張タスクはハードウェア
によって実行される。

【０００９】

【発明が解決しようとする課題】典型的ハードウェア・
データ伸張は、第１に固定的符号サイズを使用し、第２
に伸張機構を援助する特別の符号を予約することによっ
て単純化される。固定的符号サイズを使用することによ
って、伸張機構は、固定的符号サイズを受け取り、固定
的符号を生成する。このように、例えば、典型的なハー
ドウェア伸張機構は、１つの８ビット・バイト圧縮デー
タを受け取り、１つまたは複数の８ビット・バイトの伸
張されたデータを出力する。入力が固定的であるため、
伸張機構に指示を与える特別な符号が必要とされる。そ
のような構成の１つは、リテラル・プレフィックス(LIT
ERAL PREFIX)を予約し、次の符号がリテラルであるこ
と、すなわち圧縮されていないことを標示する。更に、
ＥＯＤ（データの最後）符号が定義され、ハードウエア
伸張機構はＥＯＤを検出すると動作を停止する。未圧縮
データのサイズが既知で、それを伸張機構が知らされて
いれば、ＥＯＤ符号は任意選択機能である。このような
データ圧縮伸張システムにおいて、データ圧縮比率を更
に向上させる機能が必要とされている。

【００１０】

【課題を解決するための手段】本発明を達成するため、
処理システムにおいて原データ(Original Data)を記憶
するために使われるメモリの量を減少する方法が提供さ
れる。この方法は、原データのエントリを先ず受け取る
ことによって実行される。辞書がメモリに記憶されてい
る場合、このエントリは、辞書に存在する有効エレメン
トと比較される。エントリとある１つの有効辞書エレメ
ントとの間の一致が検出されれば、その有効辞書エレメ
ントをポイントするデータ符号が、圧縮されたデータと
してメモリに記憶される。一方、一致が検出されなけれ
ば、上記エントリはリテラルと定義される。

【００１１】リテラルが定義されると仮定すると、次
は、リテラルによってポイントされる辞書エレメントが
有効であるかを判定し、有効であれば、圧縮データに対
するリテラル・プレフィックス(LITERAL PREFIX)をメモ
リに記憶する。最後に、リテラルが有効辞書エレメント
をポイントするか否かに関係なく、リテラルそれ自体が
メモリの圧縮データに記憶される。原データ中のすべて
のエントリが処理されるまで、上述のステップを繰り返
して、原データの圧縮が行われる。

【００１２】圧縮されたデータを伸張するには、まず圧
縮データのエントリがメモリから取り出される。エント
リがリテラル・プレフィックスであれば、圧縮データの
次のエントリを出力する。そうではなく、該エントリが
無効辞書エレメントをポイントしていれば、それはリテ
ラルであるので、そのエントリを出力する。最後に残さ
れた可能性として、該エントリは有効辞書エレメントを
ポイントしているので、エントリは符号であり、従っ
て、出力の前に符号は伸張される。

【００１３】

【発明の実施の形態】本発明の好ましい実施例の記述に
先がけて、使用される圧縮方式の基本的概念を説明す
る。本発明の好ましい実施例は、固定的符号サイズを使
用するという理由から、ＬＺ（レンペル−ジブ）圧縮方
式のＬＺＳ８導出を使用する。ＬＺＳ８は、リテラルお
よび符号という２つの基本型にデータを圧縮する。符号
は、ストリングを含む辞書へのアドレスであり、一方、
リテラルは、伸張の際出力へ直接転送されるデータであ
る。予約された符号（リテラル・プレフィックス）が、
リテラルが符号ではないことを示すためリテラルに先行
する。効率の向上は、主として予約符号リテラル・プレ
フィックスの使用によって達成される。上述のとおり、
リテラル・プレフィックスは、次の符号がリテラルであ
ること、すなわち、それが圧縮されていないことを伸張
機構に示す。このようにして、圧縮プロセスの間にデー
タが圧縮されずに記憶される場合は必ず、そのデータに
は、前置きとしてリテラル・プレフィックスがつけられ
なければならない。従って、１バイトの未圧縮情報を記
憶するためには２バイトが必要とされる。

【００１４】ＬＺＳ８法では、データが圧縮または伸張
されるとき、辞書を構築する。始めは、辞書は空であ
る。データが処理されるにつれ、符号が辞書に加えられ
る。伸張の間、符号は、初めに圧縮されたストリングを
表す辞書エントリをポイントする。このように、圧縮可
能なデータについて、辞書は、単一の符号によって表さ
られる長いストリングを含む。

【００１５】ＬＺＳ８の実施例において、辞書は、００
からＦＦ（２５５）へ進展する。その他のＬＺＳ８圧縮
方式の実施形態は可能であるが、辞書は、逐次的にかつ
正の方向で進展するという理解のもと、本発明の実施例
を記述する。辞書における有効符号と無効符号の間の境
界を示すポインタが、圧縮機構および伸張機構の両者に
おいて保持される。圧縮および伸張の両プロセスにおい
て、有効なストリングで辞書を更新するため、この同一
のポインタが使われる。本発明の好ましい実施例は、圧
縮および伸張プロセスの間ポインタが００からＦＦへ移
動すると仮定する。しかし、後述されるように、他の実
施例も可能である。

【００１６】例として、図１は、従来技術において既知
のリテラル・プレフィックスを使用する圧縮データのセ
グメントを示す。図１は、また、任意選択機能であるEN
D_OF_DATA符号を示す。更に、図２は、図１におけるデ
ータ・セグメントに用いられる「辞書」の内容を示す。
最後に、図３は、辞書を更新するため伸張機構によって
使われる規則を提供する。

【００１７】例を説明する前に、辞書の構造を先ず説明
する。エントリは、リンクおよびデータとして辞書に記
憶される。リンクは、別の辞書エントリをポイントする
か、あるいは現エントリがルートであることを示す。従
って、リンクは、辞書において「リンクされたリスト」
を形成するために使われる。リンク・リストを参照する
ことによって、そのエントリによって表されるストリン
グを再現することができる。このような理解に立って、
所与のエントリによって記述されるストリングが、STRI
NG IN LOC XX（位置XXにおけるストリングの意）という
短縮表記法を使用して書き表される。

【００１８】以下は、図１のデータ・セグメントが伸張
機構に入力される時起きる動作の詳細な記述である。第
１のブロック、0X12、は、辞書に対するインデックスと
識別される。このインデックスを使用して、伸張機構
は、STRING IN LOCATION 12を出力する。簡略化のた
め、この第１のブロックの前は、辞書の更新を必要とし
ないリテラルであったと仮定する。次に、伸張機構は、
リテラル・プレフィックスとして定義される0X00を受け
取る。伸張機構は、次のバイト、0x34、を出力する。伸
張プロセスを続ける前に、図３の規則を使用して辞書を
更新しなければならない。圧縮データの後続がリテラル
であったので、図３は、２回の更新が辞書に実行されな
ければならないことを示す。最初は、新しいストリング
であり、次が新しいルートである。新しいストリング
は、リテラル34プラスSTRING IN LOC 12からなる。これ
は、位置00x15に12/34(リンク／データ)として記憶され
る。本実施例においては、00というリンクが、このエン
トリが任意のリンクのルートであることを示すものとす
る。図４に、更新された新しい辞書が示されている。

【００１９】辞書を更新した後、伸張機構は、00x14で
ある次の符号を取り出す。これは有効辞書エントリであ
るので、伸張機構は、STRING IN LOCATION 14を出力す
る。図３によれば、リテラルの後に圧縮データが続くと
き、辞書への更新は必要でない。

【００２０】次に、伸張機構は、圧縮データ符号00x12
を受け取り、STRING IN LOCATION 12を出力する。圧縮
データの後に圧縮データが続くとき、図３によれば、辞
書は１回更新されなければならない。今度は、伸張機構
は、STRING IN LOCATION 14プラスSTRING IN LOCATION
12のデータから成る新しいストリングを加える。例示の
目的のため、STRING IN LOCATION 12のデータは、75と
して示されている。かくして、新しい辞書エントリは、
14/75であり、図５に示されるように位置00x17に記憶さ
れる。

【００２１】図１の次のエントリは、リテラル・プレフ
ィックスである。これは、次のエントリがリテラルであ
ることを伸張機構に対して標示している。従って、伸張
機構は、次のエントリ0x12を取り出し、直接それをデー
タストリームに出力する。次に、図３に示されるとお
り、辞書は２回更新されなければならない。第１に、新
しいストリングが入れられ、次に新しいルートでる。新
しいストリングは、リテラル12プラスSTRING IN LOC 12
から成る。これは、位置00x18に12/12として保存され
る。新しいルートは、位置00x19に00/12として保存され
る。新しい辞書は、図６に示されるとおりとなる。

【００２２】最後に、伸張機構は、ＥＯＤ符号を取り出
し、伸張動作は停止する。上述のように、ＥＯＤ符号は
任意選択機能であるが、終了を示す単純な手段を提供す
る。しかし、この簡略化は、若干ではあるが圧縮比率を
向上させる辞書エントリの数の（１個の）減少の可能性
を減殺している。

【００２３】上述の例から、２点が観察される。第１
に、辞書は元々空で開始する。別の表現をすれば、辞書
のエントリは、時間的に相当の割合、定義されないまま
である。第２に、リテラル・プレフィックスの使用は、
圧縮効率に逆効果を及ぼす。このような観察に基づい
て、本発明は、リテラルの前に必ずLITERAL PREFIXを先
行させる必要性を取り除く。特に、リテラルが、未定義
の辞書エレメントをポイントする場合、リテラルは、そ
れに先行するリテラル・プレフィックスを必要としな
い。

【００２４】図７は、図１のデータ・セグメントに対し
て本発明を使用した場合のデータ・セグメントを示す。
図７をよく見ると、第１のリテラル・プレフィックスが
取り除かれているのがわかる。前と同様、第１のブロッ
ク、0x12は、辞書へのインデックスである。このインデ
ックスを使用して、伸張機構は、STRING IN LOCATION12
を出力する。次に、伸張機構は、0x34を受け取る。伸張
機構は、最後の有効な辞書エントリが0x14であることを
知っているから、0x34はリテラルでなければならない。
従って、伸張機構は0x34を出力する。同様の形態で、伸
張機構は、STRING IN LOCATION 14およびSTRING IN LOC
ATION 12を出力する。次に、伸張機構は、リテラル・プ
レフィックスである0x00を受け取る。リテラル0x12が有
効な辞書エントリであるので、このリテラル・プレフィ
ックスは削除されてはならない。伸張機構が、先行する
リテラル・プレフィックスなしでリテラル0x12を受け取
ったなら、それは符号であると仮定され、0x12リテラル
の代わりにSTRING IN LOCATION 12を出力することにな
る。

【００２５】伸張プロセスを大まかに説明したが、本発
明の一層の理解のため、圧縮および伸張の実際の例を以
下に示す。図８は、圧縮および伸張プロセスを詳細に例
示するために用いられる圧縮可能なストリングを示す図
である。通常のプロセスに従って、先ず圧縮プロセスを
説明する。圧縮機構は、空の辞書で開始し、先ず、Ｋを
取り出す（図９の（Ａ）参照）。この辞書には以前のエ
ントリがないので、この第１の文字に一致するものはな
い。従って、これはリテラルと定義され、位置02におけ
るルートとして辞書へ入力される。後に明らかとなる理
由で、辞書の最初のエントリは、出力ストリームにおい
てそれをプレフィックス付けするためLITERAL PREFIX 0
0を必要とする。従って、出力ストリームには, 最初の
バイトが00で、それに続いてリテラルＫが含められる。

【００２６】次に図９の（Ｂ）で示されるように、圧縮
機構は、入力データストリームの２番目のエントリｗを
取り出す。辞書の探索が行われ、圧縮機構は、一致がな
いと判断する。従って、それは、リテラルと定義され
る。辞書は、位置03で更新され、リテラルｗ、およびそ
の文字がストリングのルートであることを標示する00と
いうリンクが書き込まれる。同時に、リテラルｗは、出
力ストリームに出力されなければならない。本発明に従
って、この文字は、リテラル・プレフィックスを必要と
しない。

【００２７】図９の（Ｃ）に示されるように、圧縮機構
は、入力ストリームの次の文字、すなわち下線"_"、を
取り出す。再び辞書の探索が行われ、一致が見つけられ
ない。新しく定義されたリテラルが位置04において辞書
に付け加えられ、出力ストリームに挿入されなければな
らない。図９の（Ｃ）に示されているように、位置04の
左側に想像上のポインタが置かれている。このポインタ
は、辞書内の最後の有効な位置を示すために使われる。

【００２８】次に、図１０の（Ａ）に示されているよう
に、圧縮機構は、入力データストリームから大文字Ｋを
取り出す。今度は、位置02において一致が検出される。
小文字ｗが、入力ストリームから取り出され、ストリン
グＫｗが形成される。辞書の探索後、圧縮機構は、スト
リングＫｗが辞書の内に存在せず、従って、辞書に加え
られるべきと判断する。図１０の（Ａ）の辞書に、リン
ク02およびデータｗを含む位置05が示されている。位置
05の定義に基づいて、リンク・リストをさかのぼれば、
リンクが00である位置02が参照される。このようにし
て、位置05のストリングは、Ｋｗとなる。このエントリ
の前までは、実際のデータ圧縮は発生しなかった。しか
し、ここの２つの文字、すなわちＫｗは、出力ストリー
ムにおいて１つのエントリで表される。

【００２９】次の文字が入力ストリングから取り出さ
れ、圧縮機構によって分析される（図１０の（Ｂ）参
照）。現在、圧縮機構はｗ、下線というストリングを見
ている。文字ｗは、辞書の位置03にあり、出力ストリー
ムにインデクス03を出力することを圧縮機構に標示して
いる。次の文字、下線、もまた辞書にある。図１０の
（Ｂ）に示されるとおり、圧縮機構は、出力ストリーム
にインデックス04を挿入する。しかし、ストリング（ｗ
および下線）は辞書になかったのだから、圧縮機構は、
位置06にそれを書き込む。

【００３０】次に、図１０の（Ｃ）に示されるように、
圧縮機構は、入力ストリームから文字Ｋを取り出す。辞
書を探索して、圧縮機構は位置02で一致を検出する。一
致を検出すると、圧縮機構は、次の入力文字（この場合
はｗである）を取り出す。再び辞書の探索によって、ス
トリングＫｗが位置05で検出される。従って、入力スト
リングから次の文字Ｋを取り出して、ストリングＫｗＫ
を探索すると、一致が見あたらない。ストリングが辞書
にないと、圧縮機構は、最後に一致が見い出されたスト
リングの位置（この場合05）を出力する。ここで、２つ
の追加が辞書に対して行われなければならない。第１
に、下線、Ｋの前のストリングが、位置07において加え
られる。第２に、新しいストリングＫｗＫが、位置08で
辞書に加えられる。

【００３１】圧縮プロセスを継続して、圧縮機構は、入
力ストリングから次の文字を取り出す。図１１に示され
るように、圧縮機構は、ストリングＫｗに関して、位置
05において一致を検出する。入力ストリングからの次の
文字Ｋを加えて、圧縮機構は位置08で一致を検出する。
一致を見つけられなくなるまでこのプロセスを続ける。
圧縮機構が入力ストリームからＡを取り出し、ストリン
グＫwＫＡを探索しても辞書に一致が見あたらない。従
って、圧縮機構は出力ストリームに最後の有効な一致位
置番号08を出力する。その上、新しいストリングＫｗＫ
Ａが位置09において辞書に加えられ、リテラルＡが位置
0Aで加えられる。最後に、リテラルＡが出力ストリーム
に書き出される。再び本発明に従って、リテラルＡは、
リテラル・プレフィックスでプレフィックスされる必要
はない。最後に、圧縮機構は、出力ストリームの最後に
ＥＯＤ符号（01）を加える。

【００３２】図８の原データは、記憶のため１２個のメ
モリ位置を必要とした。圧縮プロセスを経た後、同じス
トリングに対する記憶域の必要量は、図１２に示される
ように１だけ減少した。

【００３３】図１３ないし図１５は、図１２の圧縮スト
リングの伸張のための辞書内容および出力ストリングを
示す。図１３の（Ａ）から開始して、伸張機構は、入力
ストリングから00およびＫを取り出す。本発明の好まし
い実施例において、00はリテラル・プレフィックスとし
て定義されているので、それは、入力ストリングの次の
文字がリテラルであることを伸張機構に標示している。
この場合、伸張機構は、次の文字Ｋを取り出す。図３の
規則を使用して、辞書は更新されなければならない。こ
こで、図１３の（Ａ）に示されるように、新しいリテラ
ルＫは位置02において辞書に挿入される。

【００３４】次に、図１３の（Ｂ）において、伸張機構
は、入力ストリングから文字ｗを取り出す。本発明を使
用して、伸張機構は、文字ｗが辞書の無効な位置をポイ
ントしていると判断する。従って、伸張機構は、文字ｗ
がリテラルであると理解して、出力ストリングへそれを
出力する。図１３の（Ｂ）は、また、辞書が位置03で新
しいリテラルｗを含むように更新されることを示す。

【００３５】次に、伸張機構は、図１３の（Ｃ）に示さ
れるように、次の文字、下線、を取り出す。前の文字と
同様に、この文字は無効の辞書エレメントをポイントし
ている。再度、伸張機構は、下線文字がリテラルであ
り、直接出力ストリームへ転送されなければならないこ
とを認識する。その上、辞書は、また、位置04でこのリ
テラルを含むように更新されなければならない。

【００３６】図１４の（Ａ）におけるように、伸張機構
は、次の入力文字、02、を取り出す。ここで、この文字
は、有効な辞書エントリをポイントしている。従って、
伸張機構は位置02に記憶されているストリングを抽出す
る。位置02のリンク00は、データがストリングのルート
であることを示すので、ストリング全体が位置02に記憶
されていることが伸張機構にはわかる。従って、Ｋが、
出力ストリングへ転送される。図３において述べた規則
に従って、図１４の（Ａ）の辞書は更新の必要がないこ
とを示している。

【００３７】図１４の（Ｂ）は、伸張機構が次の符号、
03、を入力データストリームから取り出すことを示す。
辞書へのインデックスを持つ03を用いて、伸張機構は、
データｗを取り出し、出力ストリングへそれを出力す
る。図３の規則に従って、伸張機構は、続けて２つの圧
縮バイトを受け取ったので、辞書を一回更新しなければ
ならない。図１４の（Ｂ）に示されるように、辞書は位
置05においてストリングＫｗを作成するように更新され
る。これは、位置05のデータ部分にｗを挿入して、リン
ク02をリンク位置に加えることによって達成される。

【００３８】伸張を続けると、符号04が、有効な辞書エ
ントリをポイントしているので、圧縮されたデータと解
釈される（図１４の（Ｃ））。従って、図１４の（Ｃ）
の位置04におけるストリングは、１バイトまたは１文字
の下線であり、それは出力ストリングに挿入される。再
び、新しいストリングが位置06で作成され、そして辞書
に記憶される。

【００３９】入力シーケンス中の符号05もまた有効な辞
書エントリである。図１５の（Ａ）の辞書を見ると、位
置05のストリングはＫｗである。従って、伸張機構は出
力ストリームにこのストリングを出力する。再び、新し
い辞書エントリが作成される。圧縮データに続いて圧縮
データが来る場合、図３は、辞書が１回更新されなけれ
ばならないことを示す。図１５の（Ａ）における位置07
を参照すると、新しいエントリは、04/Kとして定義され
ている。04は、図１４の（Ｃ）に示されている直前の圧
縮データ符号に基づく。Ｋは、05に記憶されているスト
リングの最初の文字から取られる。

【００４０】図１５の（Ｂ）は、符号がまだ伸張機構の
辞書に存在しない圧縮データであるという特別の問題を
例示する。ここで、伸張機構は入力ストリングから符号
08を取り出した。しかし、エントリ08は辞書にまだ加え
られていない。従って、伸張機構は、本発明に従って08
はリテラルであると仮定することができる。この仮定
は、この特定の状況においては、正しくない。伸張機構
の辞書が圧縮機構の辞書とプラスまたはマイナス１相違
することによって、この問題が発生する。伸張機構がま
だ定義されていない辞書の次のエレメントをアクセスし
ているというこの特別の状況では、出力ストリングが定
義される前に、辞書が先ず更新されなければならない。
図３の規則を使用し、そして本状況において図１５の
（Ａ）の圧縮データ05の次に図１５の（Ｂ）の圧縮デー
タ08が来るということを認識すると、辞書は１回更新さ
れなければならない。新しい辞書エントリ08は、前の圧
縮ストリング05へのリンク、および位置05における最初
のデータを含む。位置08における辞書の完全なエントリ
が、図１５の（Ｂ）に示されている。新たに定義された
エントリ08を用いて、伸張機構は、ストリングおよび位
置08を取り出し、そして出力ストリングに挿入すること
ができる。ストリング08は、位置02からのＫ、位置05か
らのｗおよび位置08からのＫである。

【００４１】最後に図１５の（Ｃ）に示されるように、
伸張機構は、入力文字Ａを取り出し、それを辞書と比較
する。Ａが無効な位置をポイントしていることを検出し
て、伸張機構は、Ａがリテラルであることを理解し、出
力ストリームにそれを挿入する。リテラルＡの後、機能
が完了したことを伸張機構に示す01のＥＯＤ符号が続
く。図９の（Ａ）に関しての記述の際に述べたよう
に、元の入力文字Ｋが実際に無効な辞書位置をポイント
する可能性がある。しかし、リテラル・プレフィックス
00がＫの前に挿入されている。また既に述べたように、
圧縮機構の辞書と伸張機構の辞書は、任意の時間に互い
にプラスまたはマイナス１相違しながら同期している。
圧縮辞書が一杯となってあふれ始め、伸張辞書が１だけ
遅れる場合問題が発生する可能性がある。このような状
況で、圧縮プロセスの間辞書への原エントリがリテラル
・プレフィックス00で先行されてない場合、圧縮機構の
空の辞書に比較して一杯の辞書を持つ伸張機構は、入力
符号が有効な辞書位置を実際にポイントしていると信じ
て、ストリングを誤って取り出すであろう。辞書への初
期エントリの前にリテラル・プレフィックス00を先行さ
せることを圧縮機構に要求することによって、伸張機構
は、後続のバイトがリテラルであることを自動的に知
る。そのリテラルの処理の間、伸張機構の辞書は再び圧
縮機構の辞書と同期する。

【００４２】辞書が相対的に空の間は、圧縮データは、
リテラル・プレフィックスが先行するリテラルを多く含
むがストリングは少ないことを当業者は理解することで
あろう。辞書の書込みが増加するにつれ、省略すること
ができるリテラル・プレフィックスの数は減少するが、
リテラル・データは辞書のストリングにあるため、圧縮
データ中に含まれるリテラルは少なくなる。従って、本
発明は、リテラル・プレフィックス出現の確率が高いと
き、リテラル・プレフィックスの数を減らすことによる
利益をもたらす。

【００４３】本発明の好ましい実施例が約１０％圧縮フ
ァイルを縮小したことをテストは示している。圧縮比に
関する経験的情報は、２つのタイプのデータを使用して
得られた。第１のタイプは圧縮が容易な、ビット・マッ
プ文字のようなイメージから構成される。もう１つのタ
イプは、圧縮が比較的難しい中間調ファイルである。第
１の圧縮が容易なタイプのファイルの圧縮比は、本発明
の改良によって、９.５：１から１０.５：１に向上し
た。圧縮が難しい方のファイルの圧縮比は、１.８５：
１から２.０２：１になった。

【００４４】圧縮機構がハードウェアであれば、本発明
の好ましい実施には、論理を殆ど必要とせず、圧縮機構
がソフトウェアであれば、コードはあまり長くない。い
ずれの実施においても、最後の有効辞書エントリに対す
るポインタが存在する。従って、ポインタに対するリテ
ラルの比較手段は、リテラルが先行するリテラル・プレ
フィックスを必要とするか否かを迅速に判断できる。同
様のポンインタが伸張機構にも存在するので、入力バイ
トが符号かまたはリテラルであるかを同様な比較によっ
て判断できる。

【００４５】本発明は、所与の辞書エントリが有効であ
るか、または無効であるかを検知することができる機能
に依存している。本発明の好ましい実施例では、符号
を、辞書における最後の有効エントリに対するポインタ
と比較することによって、この判断が行われる。しか
し、これが、唯一の可能な実施例ではない。本発明を使
用するためには、実施例は、要求された辞書エントリ
が、有効か無効かを標示しなければならない。辞書エン
トリの有効性を標示するためのいくつの可能なメカニズ
ムには、辞書エントリを無効な位置へリンクすること
や、辞書エントリ自身へリンクする形態が含まれる。例
えば、無効な辞書エントリがそれら自身へリンクされる
と、伸張機構が符号を取り出すとき、辞書エントリのリ
ンクがそれ自身をポイントしているかどうかを調べる。
この比較によって、伸張機構は、辞書エントリが有効か
無効かを判断する。本発明を使用する場合、辞書エント
リが無効であれば、符号はリテラルである。

【００４６】図１６の流れ図は、伸張機構に関する１つ
の可能な実施例を示す。詳細に述べれば、伸張機構は、
先ず符号を取り出す（４０１）。次に、伸張機構は、取
り出した符号がどのような種類かを判断する。図１６で
は、符号が、先ず、ＥＯＤ符号と比較される（４０
２）。それがＥＯＤと一致すると、伸張機構は、終了す
る（４０３）。符号がＥＯＤでないと仮定すると、伸張
機構は、符号がリテラル・プレフィックスであるか調べ
る（４０４）。そうであれば、伸張機構は、次のバイト
がリテラルであるということを知る。従って、伸張機構
は、次のバイトを取り出し（４０９）、データストリー
ムにそれを出力する（４０７）。符号がリテラル・プレ
フィックスでない場合、伸張機構は、それを、辞書にお
ける最後のエントリに対するポインタと比較する（４０
５）。符号がポインタより大であれば、符号はリテラル
であり、直接データストリームへ出力される（４０
８）。最後に、符号が辞書エントリに対する有効なポイ
ンタであれば、その符号は伸張される（４０６）。

【００４７】図１７は、圧縮機構に関する１つの実施例
の論理的流れ図である。具体的には、圧縮機構はデータ
を受け取り、それを圧縮して符号を生成する（６０
２）。次に、圧縮記憶は、符号がリテラルであるか否か
を判断し（６０３）、そうでなければ、辞書を更新する
（６０４）。符号がリテラルであれば、圧縮機構は、符
号が最後の有効な辞書エントリに対するポインタより大
きいか否かを判断する（６０５）。符号がポインタより
小であれば、リテラル・プレフィックスが挿入される
（６０６）。符号がポインタより大であれば、リテラル
・プレフィックスを記憶するために必要な空間が節約さ
れる（６０７）。最後に、すべてのデータが圧縮される
まで、圧縮機構は同じ動作を繰り返す（６０８）。

【００４８】コンピュータ論理の分野の知識を有する者
は、図１６および図１７の流れ図が、本発明を実施する
論理的な流れを図示するために意図されているに過ぎな
いことを理解するであろう。本発明の基本的構想が一旦
理解されれば、いくつかのバリエーションが可能であ
る。

【００４９】図１８には、プリンタの一般的ブロック図
が示されている。図１８に示されている適用業務プログ
ラム１４００は、プリンタ・システムの一部ではない点
注意されるべきである。

【００５０】図１８のブロック図に関していくつかの形
態でデータ圧縮方法が使われることができるが、以下に
２つの主要な形態を検討する。特定の方法の選択は、主
としてプリンタ・システム全体の費用計画によって決定
される。コストの高い実施形態では、ＣＰＵ１４０２
は、それ自身で圧縮アルゴリズムを実行するに十分な処
理能力およびメモリを持つ。低コストのプリンタ・シス
テムでは、ＣＰＵ１４０２は存在しないかもしれず、必
要メモリ量は最低限に抑えられる。低コストの構成で
は、適用業務プログラム１４００が圧縮アルゴリズムを
実行する。

【００５１】高性能プリンタ・システムでは、適用業務
プログラム１４００は、高水準印刷制御言語（ＰＣＬ）
１４０１を使用するプリンタ・システムにデータを送
る。ＣＰＵ１４０２は、高水準印刷制御言語１４０１か
らデータを取り出し、そのデータをメモリ１４０３へ未
圧縮形式でラスタライズする。次に、ＣＰＵは未圧縮の
ラスタライズされた情報をメモリ１４０３から取り出
し、それを、圧縮機構１４０５に渡し、圧縮機構１４０
５は圧縮したイメージをメモリ１４０４へ記憶のため戻
す。適切な時点で、ＣＰＵ１４０２の制御の下、ＤＭＡ
１４０６が、圧縮イメージをメモリ１４０４から取り出
す。次に、圧縮イメージは、伸張アルゴリズム実施のた
め伸張機構１４０８へ転送される。伸張機構１４０８の
出力は、未圧縮イメージ情報に従ってレーザ１４０９を
変調するビデオ・チップ１４０７に与えられる。

【００５２】上記第１の高性能構成では、ラスタライズ
されるデータをプリンタ・システムに送出する前に適用
プログラム１４００がそれを圧縮することによって、適
用業務プログラム１４００およびプリンタ・システムの
間のスループットの増加が達成される。データ圧縮方法
を使用して、適用業務プログラムは、情報を圧縮し、そ
れを高水準ＰＣＬブロック１４０１に転送する前に適切
なページ記述言語にそれを渡すことができる。ＣＰＵ１
４０２がページ記述言語命令を取り出すとき、後続の情
報が圧縮されたデータであることを意味する命令をデコ
―ドする。そこで、ＣＰＵ１４０２は、圧縮のステップ
をバイパスして、圧縮データを圧縮イメージ用メモリ１
４０４へ直接書き込む。前と同様に、ＤＭＡ１４０６が
メモリ１４０４から圧縮イメージを再び取り出し、伸張
機構１４０８へ転送し、伸張機構１４０８は、データを
伸張してビデオ・チップ１４０７およびレーザ・ダイオ
ード１４０９へ送る。

【００５３】第２の構成は、プリンタ・システム自身の
費用を最小にすることを目標にする。そのような構成で
は、メモリ１４０４、ＤＭＡ１４０６、伸張機構１４０
８、ビデオ・チップ１４０７およびレーザ・ダイオード
１４０９だけが使用される。このプリンタ・システムは
ＣＰＵを含まないので、適用業務プログラム１４００
は、アルゴリズムの半分の圧縮を実施しなければならな
い。

【００５４】通常の印刷プロセスにおいては、ＤＭＡ１
４０６が、圧縮イメージをメモリ１４０４から取り出
し、前と同様に、圧縮イメージを伸張する伸張機構１４
０８へそれを渡す。この構成は、ＣＰＵ１４０２がもは
や必要とされないため、プリンタ・システムの費用を大
幅に削減できる。しかし、一方、このような配置は、イ
メージをラスタライズし、圧縮するための負荷が適用業
務プログラム１４００に加えられる。

【００５５】以上のとおり、本発明の好ましい実施例が
例示され、その形態が記述されたが、本発明の精神また
は特許請求の範囲を逸脱することなく種々の修正が可能
であることは当業者に理解されることであろう。

【００５６】本発明には、例として次のような実施様態
が含まれる。（１）メモリに記憶されている圧縮データを圧縮前の原
データに伸張する方法であって、上記メモリから上記圧
縮データの１つのエントリを取り出すステップと、取り
出した上記エントリがリテラル・プレフィックスであれ
ば、上記圧縮データの次のエントリを取り出して上記原
データへ出力するステップと、取り出した上記エントリ
がリテラル・プレフィックスでなく、かつ、該エントリ
が、無効な辞書エレメントをポイントしていれば、該エ
ントリを上記原データへ出力するステップと、取り出し
た上記エントリがリテラル・プレフィックスでなく、か
つ、上記エントリが、有効な辞書エレメントをポイント
していれば、上記エントリは符号であるので、上記符号
を伸張した後上記原データへ出力するステップと、を含
む方法。（２）上記エントリと前のエントリに従って上記辞書を
更新するステップを含む上記（１）に記載の方法。（３）上記辞書更新ステップが、上記エントリが上記符
号であり、かつ、上記前のエントリが符号であった場
合、新しい有効な辞書エレメントを先ず作成し、次に上
記新しい有効な辞書エレメントを用いて上記辞書を更新
するステップと、上記エントリが上記リテラル・プレフ
ィックスであるかまたは上記無効な辞書エレメントをポ
イントしていて、かつ、上記前のエントリが符号であっ
たならば、第１および第２の新しい有効な辞書エレメン
トを作成し、上記第１および第２の新しい有効な辞書エ
レメントを用いて上記辞書を更新するステップと、上記
エントリが上記リテラル・プレフィックスであるかまた
は上記無効な辞書エレメントをポイントしていて、か
つ、上記前のエントリがリテラル・プレフィックスであ
ったかまたは無効な辞書エレメントをポイントしていた
ならば、第３および第４の新しい有効な辞書エレメント
を作成し、上記第３の新しい有効な辞書エレメントを用
いて上記辞書を更新するステップと、を含む上記（２）
に記載の方法。（４）メモリに記憶されている圧縮される前の原データ
を圧縮データに圧縮する方法であって、上記メモリから
上記原データのエントリを取り出すステップと、上記エ
ントリを辞書における有効なエレメントと比較するステ
ップと、上記比較の結果、上記エントリと１つの有効な
辞書エレメントの間における一致が検出されれば、上記
一致が検出された位置をポイントする符号を上記圧縮デ
ータへ出力するステップと、上記比較の結果、上記エン
トリがいずれの有効な辞書エレメントとも一致しない場
合、上記エントリをリテラルと定義するステップと、上
記リテラルが定義された場合、上記リテラルによってポ
イントされる辞書エレメントが有効であるか否かを判断
し、有効であれば、リテラル・プレフィックスを上記圧
縮データへ出力するステップと、上記リテラルが定義さ
れた場合、上記圧縮データに上記リテラルを出力するス
テップと、を含む方法。（５）上記比較のステップにおいて、上記エントリと１
つの有効な辞書エレメントの間の一致が検出される場
合、上記比較の結果が上記一致を検出しなくなるまで、
上記取り出しおよび比較のステップを繰り返すステップ
を更に含む上記（４）に記載の方法。

【００５７】（６）処理システムにおいて原データを保
存するために使用されるメモリ量を減少させる方法であ
って、(A)上記原データのエントリを受け取るステップ
と、(B)上記メモリに記憶されている辞書における有効
なエレメントと上記エントリを比較するステップと、
(C)上記比較のステップが上記エントリと１つの有効な
辞書エレメントの間の一致を検出するならば、圧縮デー
タとして、上記有効な辞書エレメントをポイントするデ
ータ符号を記憶するステップと、(D)上記比較のステッ
プが上記エントリと１つの有効な辞書エレメントの間の
一致を検出できない場合、上記エントリをリテラルとし
て定義するステップと、(E)上記リテラルが定義され、
上記リテラルによってポイントされる辞書エレメントが
有効であると判断されるなら、上記メモリの上記圧縮デ
ータにリテラル・プレフィックスを記憶するステップ
と、(F)上記リテラルが定義される場合、上記メモリの
上記圧縮データに上記リテラルを記憶するステップと、
(G)上記原データのすべてのエントリが処理されるま
で、上記(A)から(F)までのステップを繰り返すステップ
と、(H)上記メモリから上記圧縮データの第２のエント
リを取り出すステップと、(I)上記第２のエントリが上
記リテラル・プレフィックスであれば、該第２のエント
リの次のエントリを出力するステップと、(J)上記次の
エントリが無効な辞書エレメントをポイントしていれ
ば、上記第２のエントリを出力するステップと、(K)上
記第２のエントリが有効な辞書エレメントをポイントし
ていれば、上記第２のエントリは符号であるので、該符
号を伸張するステップと、を含む方法。（７）上記第２のエントリおよび前のエントリに従って
上記辞書を更新するステップを含む上記（６）に記載の
方法。（８）上記有効な辞書エレメントを抽出するステップ
と、上記有効な辞書エレメントを出力するステップと、
を更に含む上記（６）または上記（１）に記載の方法。（９）上記符号が最後の有効な辞書エレメントを過ぎた
辞書エレメントをポイントしていれば、上記辞書エレメ
ントは無効であるとみなされる、上記（６）または上記
（１）に記載の方法。（１０）上記一致が検出されれば、上記エントリを上記
原データの後続のエントリに加えて１つのストリングを
形成するステップと、上記ストリングを求めて上記辞書
を探索するステップと、上記探索ステップが上記ストリ
ングの検出に失敗するまで、上記ストリング形成および
探索のステップを繰り返すステップと、上記データ符号
によってポイントされる新しい有効な辞書エントリを作
成して、それを上記ストリングに含めるステップと、を
含む上記（６）に記載の方法。

【００５８】

【発明の効果】圧縮データに含まれるリテラル・プレフ
ィックス符号を可能な限り少なくすることによって、圧
縮データの圧縮比率を向上させることができる。

【図面の簡単な説明】

【図１】リテラル・プレフィックスがあらゆるリテラル
に先行しなければならない圧縮データのセグメントを示
す図である。

【図２】図１および図７の圧縮データ・セグメントにつ
いての辞書の内容を示す図である。

【図３】伸張機構によって使われる辞書更新規則を示す
図である。

【図４】図１および図７の圧縮データ・セグメントにつ
いての辞書の内容を示す図である。

【図５】図１および図７の圧縮データ・セグメントにつ
いての辞書の内容を示す図である。

【図６】図１および図７の圧縮データ・セグメントにつ
いての辞書の内容を示す図である。

【図７】図１のデータ・セグメントに対して本発明を使
用した場合の圧縮データ・セグメントを示す図である。

【図８】例示の目的のために使われる原未圧縮データを
示す図である。

【図９】図８のデータ例を使用する圧縮プロセスの各ス
テップ毎の圧縮データおよび辞書を示す図である。

【図１０】図８のデータ例を使用する圧縮プロセスの各
ステップ毎の圧縮データおよび辞書を示す図である。

【図１１】図８のデータ例を使用する圧縮プロセスの各
ステップ毎の圧縮データおよび辞書を示す図である。

【図１２】図８の原データを圧縮することによって作成
される圧縮データを示す図である。

【図１３】図１２のデータ例を使用する伸張プロセスの
各ステップ毎の未圧縮データおよび辞書を示す図であ
る。

【図１４】図１２のデータ例を使用する伸張プロセスの
各ステップ毎の未圧縮データおよび辞書を示す図であ
る。

【図１５】図１２のデータ例を使用する伸張プロセスの
各ステップ毎の未圧縮データおよび辞書を示す図であ
る。

【図１６】本発明に従うデータ伸張の実施例を示す流れ
図である。

【図１７】本発明に従うデータ圧縮の実施例を示す流れ
図である。

【図１８】本発明を使用するプリンタ・システムの概略
ブロック図である。

【符号の説明】

１４００適用業務プログラム１４０１高水準印刷制御言語（ＰＣＬ）１４０２ＣＰＵ１４０３未圧縮用メモリ１４０４圧縮用メモリ１４０５圧縮機構１４０６ＤＭＡ１４０７ビデオ・チップ１４０８伸張機構１４０９レーザ

Claims

【特許請求の範囲】

【請求項１】メモリに記憶されている圧縮データを圧縮
前の原データに伸張する方法であって、上記メモリから上記圧縮データの１つのエントリを取り
出すステップと、取り出した上記エントリがリテラル・プレフィックスで
あれば、上記圧縮データの次のエントリを取り出して上
記原データへ出力するステップと、取り出した上記エントリがリテラル・プレフィックスで
なく、かつ、該エントリが、無効な辞書エレメントをポ
イントしていれば、該エントリを上記原データへ出力す
るステップと、取り出した上記エントリがリテラル・プレフィックスで
なく、かつ、上記エントリが、有効な辞書エレメントを
ポイントしていれば、上記エントリは符号であるので、
上記符号を伸張した後上記原データへ出力するステップ
と、を含む方法。