(57)【特許請求の範囲】
【請求項１】
不連続メモリに記憶された圧縮済みデータを伸張して元のデータを得るデータ伸張方法であって、
前記圧縮済みデータの符号を前記不連続メモリから検索するステップと、
前記符号がリンク符号であるかどうかを判定するステップと、
前記符号がリンク符号である場合、前記不連続メモリの次の領域を示すポインタであって、メモリ内において前記リンク符号の後に記憶されるポインタを読み取るステップと、
を含むことを特徴とするデータ伸張方法。
【請求項２】
圧縮済みデータが第１のメモリに記憶され、元のデータが第２のメモリに記憶されるコンピュータにおいて、複数の前記圧縮済みデータを複数の前記元のデータに伸張するデータ伸張方法であって、前記コンピュータにより実行されるデータ伸張方法であり、
前記コンピュータが、前記複数の圧縮済みデータのうちの１つを前記第１のメモリから読み取るステップと、
前記複数の圧縮済みデータのうちの１つがリンク符号である場合、メモリ内においてリンク符号の後に記憶され、かつ、前記複数の圧縮済みデータのうちの次の１つが記憶されている前記第１のメモリ内の新しい場所を示すアドレス・ポインタを前記第１のメモリから検索するステップと、
前記複数の圧縮済みデータのうちの前記１つが前記リンク符号以外のものである場合、前記コンピュータが、前記複数の圧縮済みデータのうちの前記１つを前記複数の元のデータのサブセットに伸張し、前記複数の元のデータの前記サブセットを前記第２のメモリに記憶するステップと、
を含むことを特徴とするデータ伸張方法。
【請求項３】
未圧縮データを、メモリに記憶される圧縮済みデータに圧縮するデータ圧縮方法であって、
前記未圧縮データのサブセットを検索するステップと、
前記未圧縮データの前記サブセットを前記圧縮済みデータのサブセットに圧縮するステップと、
前記メモリから次のメモリ・セグメントを要求するステップと、
を含む方法であって、
現在のメモリ・セグメント及び次のメモリ・セグメントが連続である場合、圧縮済みデータの前記サブセットを前記次のメモリ・セグメント内に記憶し、
これとは異なり、前記次のメモリ・セグメント及び現在のメモリ・セグメントが不連続である場合、前記メモリ内で前記次のメモリ・セグメントが置かれている場所を示すポインタによって、後続のリンク符号を前記現在のメモリ・セグメント内に置き、その後に、前記圧縮済みデータを前記次のメモリ内に保存するようにしたこと、
を特徴とするデータ圧縮方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、データ圧縮に関し、詳細には、圧縮済みデータを不連続メモリに記憶できるようにするデータ圧縮あるいは伸長のための構成と方法に関する。
【０００２】
【従来の技術】
ディジタル・データ信号のストリームを圧縮済みディジタル符号信号として符号化し、圧縮済みディジタル符号信号を元のデータに復号する、データ圧縮システムが従来技術で知られている。データ圧縮とは、所与のフォーマットのデータを、その元のデータよりも少ない空間しか必要としない代替フォーマットに変換しようとするプロセスを指す。データ圧縮システムの目的は、所与のディジタル情報本体を保持するために必要な記憶域の量、またはそのような情報本体を送るために必要な時間の量を節約することである。
【０００３】
汎用ディジタル・データ圧縮システムが実用的なものであるには、ある種の基準を満たすべきである。システムは可逆性を有するべきである。データ圧縮システムが可逆性を有するには、情報が変化することも、あるいは失われることもなしに、圧縮済みデータを再拡張し、あるいは復号して元の形に戻すことができなければならない。復号されたデータと元のデータは、同じであり、かつ相互に区別できないものでなければならない。この可逆性は、情報理論で使用される厳密な雑音なし特性と同義である。いくつかの応用例は、可逆性を厳密に満たすことを必要としない。そのような具体的な１つの応用例は、グラフィカル・データを扱う応用例である。人間の目は雑音の影響をそれほど受けないので、圧伸プロセス中の情報のある程度の変化または喪失は受け入れられる。
【０００４】
システムは、データ圧伸システムと通信する装置によって提供され、かつ受け入れられるデータ転送速度に関して十分な性能を提供すべきである。データを圧縮速度は、通常、圧縮システムへの入力データ処理速度によって決定され、それは典型的には毎秒１００万バイト（毎秒メガバイト）である。通常、毎秒１メガバイトを超えるデータ速度を維持するには、現行のディスク・システム、テープ・システム、および通信システムに十分な性能が必要である。したがって、データ圧伸システムは、システム全体に悪影響を与えないように十分なデータ帯域幅を有さなければならない。データ圧伸システムの性能は通常、圧縮および伸長に必要な計算と、統計データを記憶して圧伸プロセスを導くために使用されるランダム・アクセス・メモリ（ＲＡＭ）などシステム構成要素の速度とによって制限される。圧縮装置の性能は、圧縮器が入力文字当たりに必要とするサイクルの数によって特徴付けられる。サイクルの数が少なければ少ないほど、性能は高くなる。
【０００５】
データ圧伸システムの設計における他の重要な基準は、圧縮効果である。圧縮効果は、圧縮率で特徴付けられる。圧縮率とは、未圧縮形のデータ・サイズを圧縮形でのサイズで除した比である。データは、圧縮可能であるには、冗長性を含まなければならない。圧縮効果は、圧縮手順において入力データの冗長性がどれだけ効果的に使用されるかによって決定される。コンピュータに記憶される典型的なデータでは、冗長性は個別の記号、例示数字、バイト、または文字を定型化せずに使用するときや、共通の語、空白記録フィールドなど記号シーケンスを頻繁に繰り返すときに発生する。
【０００６】
汎用データ圧縮手順も従来技術で知られており、関連する３つの手順は、ハフマン法、Ｔｕｎｓｔａｌｌ法、レンペル・ジッフ法である。ハフマン法は広く知られ使用されており、「Ａ  Ｍｅｔｈｏｄ  Ｆｏｒ  Ｃｏｎｓｔｒｕｃｔｉｏｎ  Ｏｆ  Ｍｉｎｉｍｕｍ  Ｒｅｄｕｎｄａｎｃｙ  Ｃｏｄｅｓ」と題する論文（Ｄ．Ａ．ハフマン著、Ｐｒｏｃｅｅｄｉｎｇｓ  ＩＲＥ，  ４０，  １０、１０９８〜１１００ページ、１９５２年９月）に記載されている。Ｔｕｎｓｔａｌｌアルゴリズムについては「Ｓｙｎｔｈｅｓｉｓ  ｏｆ  Ｎｏｉｓｅｌｅｓｓ  ｏｍｐｒｅｓｓｉｏｎ  Ｃｏｄｅｓ」と題する博士論文（Ｂ．Ｐ．Ｔｕｎｓｔａｌｌ著、Ｇｅｏｒｇｉａ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｔｅｃｈｎｏｌｏｇｙ、１９６７年９月）に記載されている。また、レンペル・ジッフ法については「Ａ  Ｕｎｉｖｅｒｓａｌ  Ａｌｇｏｒｉｔｈｍ  Ｆｏｒ  Ｓｅｑｕｅｎｔｉａｌ  Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎ」と題する論文（Ｊ．ジブおよびＡ．レンペル著、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，  ＩＴ−２３，  ３、３３７〜３４３ページ、１９７７年５月）を参照されたい。
【０００７】
最初に開発された汎用データ圧縮手順の１つはハフマン法である。簡単に説明すると、ハフマン手順は、記号の全セグメント長を可変長語としてマップする。ハフマン・データ圧縮手順には２つの制限がある。第１に、ハフマン手順は、圧縮すべきデータが記号の固定長セグメントとして分解されるという制約の下で動作する。ハフマン手順は、このような制約の下で得られる最良の圧縮率を提供するが、制約が緩和されると、他の手順を使用することによって、はるかによい圧縮率を得ることができる。第２に、ハフマン符号化では、元データの統計的特性を十分に知っている必要がある。ハフマン手順は、各固定長入力セグメントが生起する確率が分かっているという仮定の下で動作する。ハフマン手順のこの要件は、実際には、データの処理時に必要な統計を累積させるこの手順の適応型を使用することによって満たすことができる。しかし、これは厄介であり、かなりの作業メモリ空間を必要とし、適応時の性能は最適なものではなくなる。
【０００８】
Ｔｕｎｓｔａｌｌアルゴリズムは、記号の可変長セグメントを固定長２進語としてマップし、ハフマン手順を補助するものであり、この場合、固定長制約は、入力セグメントではなく出力セグメントに適用される。ハフマン手順と同様に、Ｔｕｎｓｔａｌｌ手順でも、ソース・データ確率の予備知識が必要である。この場合も、この予備知識要件は、データの処理時に統計を累積させる適応型を使用することによって、ある程度満たすことができる。
【０００９】
レンペル・ジッフ手順は、記号の可変長セグメントを可変長２進語としてマップするものである。この手順は、入力セグメントにも出力セグメントにも制約がないときには漸近的に最適である。この手順では、入力データ文字列は、それぞれ、入力データから得た新しい１つの記号が語尾に付けられた入力文字列の最初の部分の正確なコピーから成る、適応的に成長するセグメントとして分解される。作成すべきコピーは、できるだけ長いものであり、最初に分解されたセグメントに一致するように制約されることはない。出力においてセグメントに置き換わる符号語は、最初にコピーされた部分が始まる場所を指すポインタと、コピーの長さと、新しい記号とから成る情報を含む。
【００１０】
データ圧縮は、コストを合理的に維持するために、電子写真などページ・プリンタ技術分野で使用されている。たとえば、インチ当たり６００ドット（６００ＤＰＩ）での１ページのサイズは約４ＭＢである。圧縮技法を使用することによって、これを約１ＭＢに減少させることができる。電子写真印刷技術分野では、伸長プロセスに関する性能制約を課している。具体的には、圧縮済みデータは、プリント・エンジンに一定のデータ・ストリームを提供できるほど高速に伸長しなければならない。この性能要件を満たすために、伸長タスクはハードウェアによって実行されている。
【００１１】
ハードウェアのデータ伸長は通常、第１に固定符号サイズを使用し、第２に伸長器を助ける特殊符号を留保することによって簡略化される。伸長器は、固定符号サイズを使用することによって、固定符号サイズを受け入れ、固定符号を生成する。したがって、たとえば、典型的なハードウェア伸長器は、圧縮済みの８ビット・バイトを受け入れ、伸長された１つまたは複数の８ビット・バイトを出力する。入力が固定されるので、伸長器に命令を与えるには特殊符号が必要である。そのようなある構成では、次の符号がリテラルであり、すなわち、圧縮されていないことを示すＬＩＴＥＲＡＬ符号が留保される。また、ハードウェア伸長器がＥＮＤ＿ＯＦ＿ＤＡＴＡ符号を検出したときに停止するように、このＥＯＤ符号が定義される。
【００１２】
【発明が解決しようとする課題】
ハードウェア伸長器は、ＥＯＤ符号を検出するまで単にメモリ内を移動し続けるので、本発明の前には、圧縮済みコードは連続メモリに存在しなければならなかった。しかし、メモリは時間の経過と共に細分化される傾向があるので、１ＭＢの連続メモリが常に見つかるわけではない。従って不連続メモリを使用してデータ圧縮・伸長をおこなうことが望まれる。
【００１３】
【課題を解決するための手段】
本発明を達成するために、圧縮済みデータを不連続メモリに記憶するデータ圧伸方法が提供される。圧縮済みデータを作成するにはいくつかの実施例がが可能である。しかし、基本的に、データを圧縮してメモリに記憶するとき、不連続セグメントに適当にマーク付けしなければならない。そのようなマーク付けでは、最後の位置が、次に使用されるメモリ位置を指すポインタを含む必要がある。ポインタのすぐ前に特殊「ＬＩＮＫ」符号が記憶される。したがって、圧縮器がジョブを完了すると、不連続メモリは論理的にリンクされる。
【００１４】
このリンキング・プロセスは、前述のように「圧縮プロセスの完了時に」実行することも、あるいは、圧縮プロセスが始まる前に実行することもできる。この手法では、メモリ管理装置などが、必要なメモリの割当てを行う。次に、適当な「ＬＩＮＫ」コードおよびポインタが各切れ目に記憶される。メモリがリンクされた後、圧縮器は、リンクをたどりながら圧縮済みデータを記憶する。
【００１５】
圧縮済みデータを伸長するにはまず、圧縮済みデータの符号を不連続メモリから検索する。符号がリンク符号である場合、次の圧縮済みデータが記憶されているメモリ中の次の位置を指すアドレス・ポインタがメモリから検索される。その符号がリンク符号でない場合は、伸長される。
【００１６】
【実施例】
まず、図１を参照する。前述のように、一般に、圧縮済みイメージは連続メモリに記憶しなければならない。この要件を図示すると、圧縮済みイメージ・データが単一のメモリ・ブロック２００に存在しなければならないことを示す図１のようになる。特殊符号「ＥＯＤ」は、伸長器に圧縮済みデータの終りを示す。
【００１７】
圧縮済みイメージ・データを連続メモリに記憶すると、最もコンパクトな圧縮済みデータが生成される。しかし、メモリを細分化すると、圧縮済みイメージ・データ全体を記憶するのに十分なサイズの連続メモリ・ブロックを見つけることができなくなる。特殊符号「ＬＩＮＫ」を追加することによって、メモリ細分に適合するように圧縮済みイメージ・データを細分化することができる。したがって、伸長器は、ＬＩＮＫ符号に出会ったとき、物理アドレスが後に続くことが分かる。物理アドレスは、次のメモリ・ブロックが始まる場所を示す。図２は、本発明を使用する圧縮方式によって圧縮済みデータをどのようにメモリ全体にわたって細分化できるのかを示す。
【００１８】
図２を参照すると、伸長器は、メモリ・ブロック２０１の開始アドレスを受け取る。伸長ブロック２０１の後、「ＬＩＮＫ」符号に出会う。ＬＩＮＫ符号の後のＡＤＤＲは、伸長器をブロック２０３の始めに向け、実際上、ブロック２０２をスキップさせる。ブロック２０４も同様にスキップされる。最後に、伸長器がブロック２０５の終りに到達すると、伸長器に停止するよう通知する「ＥＯＤ」符号に出会う。
【００１９】
圧縮器は、図２の細分化データを作成する。図１および図２の例を使用すると、圧縮器はまず、細分の数と利用可能な各メモリのサイズを決定する。圧縮器が、入力された未圧縮データに関する予備知識をもたない限り、圧縮済みデータを記憶するのに必要な記憶域の正確な量は分からない。したがって、圧縮器は、発見的データまたは統計的データに基づいて推定を行い、あるいは、最悪ケースを仮定することができる。圧縮済みデータを不連続メモリに記憶できるようにすることによって、必要な記憶域の要件に関する圧縮器の最初の推定は重大ではなくなる。
【００２０】
概念的には、圧縮器は２つのタスクを実行する。第１に、圧縮器は、入力されたデータを実際に圧縮する。第２に、圧縮済みデータが連続メモリに記憶されていない場合、そのデータをリンクする。圧縮器の１つの可能な実施例を示すフローチャートを図６に示す。図６では、圧縮器は６０２で、入力データを圧縮する。次に、圧縮器は、メモリが連続しているかどうかを判定する。メモリが連続している場合、６０７で、圧縮済みデータは単に記憶される。しかし、メモリが連続していない場合、圧縮器は、図２に示したように、「ＬＩＮＫ」符号および適当なアドレスを挿入する。
【００２１】
一実施例の下では、圧縮器は自己の推定に基づいて圧縮済みデータを記憶するのに十分なメモリを要求する。メモリ管理装置（ＭＭＵ）は、十分なメモリが利用できると仮定してこの要求を許可する。この許可の一部として、メモリ管理装置は圧縮器に正確なメモリ構造を通知する。圧縮器は次いでメモリ管理装置から得たメモリ構造を使用して、メモリ内を段階的に移動しながら、データを圧縮する。圧縮が完了した後、圧縮器は、最後に使用されたメモリ・アドレスをＭＭＵに送り返す。最後に、ＭＭＵは、未使用メモリの割り当てを解除する。
【００２２】
代替実施例の下では、圧縮器はまず、小さなメモリ・ブロックを要求する。必要に応じて、追加要求が発行される。圧縮器は、新しいブロックを受け取るとまず、それが最後のブロックと連続しているかどうかを調べるための検査を行う。新しいブロックが連続していない場合、適当な「ＬＩＮＫ」およびジャンプ・アドレスが前のブロックの終りに追加される。論理技術分野の当業者には、メモリ構造の上記の記述が与えられている場合、圧縮器のいくつかの代替実施例が可能であることが理解されよう。
【００２３】
次に、伸長要件について説明する。図３に示した概略フローチャートは、読者が本発明の伸長器部分をよりよく理解するうえで助けとなろう。伸長器（図５の１４０８）はまず１０１で、メモリ（図５の１４０４）から次の符号を検索する。次に、符号がどんなタイプのものであるかを判定するために符号が分析される。１０２で、符号が特殊符号の「ＥＯＤ」である場合、１０３で、伸長器は停止する。次に１０４で、この符号は、特殊符号「ＬＩＴＥＲＡＬ」と比較される。上述のように、「ＬＩＴＥＲＡＬ」符号は、次の符号が、未圧縮符号であり、かつ単に１０７で伸長済みデータ・ストリームにこの符号を出力すべきであることを伸長器に通知する。次に１０５で、符号が特殊符号「ＬＩＮＫ」と突き合わされて検査される。符号が「ＬＩＮＫ」である場合、次の位置は、メモリにおいて残りの符号が存在する場所を指すポインタを含む。したがって１０８で、伸長器は、次の符号を検索し、次いで、それをポインタとして使用して伸長を継続する。最後に、符号が特殊符号でない場合、その符号は１０６で、単に伸長される。論理技術分野の当業者には、決定ブロック１０２、１０４、１０５が任意の順序で発生することができることが理解されよう。図３に示した順序は、１つの可能な構成を示すものに過ぎない。本発明による一代替実施例の流れ図については図４を参照されたい。
【００２４】
プリンタの汎用ブロック図が示された図５を参照する。図５に示したＡＰＰＬＩＣＡＴＩＯＮ  ＰＲＯＧＲＡＭ  １４００はプリンタ・システムの一部ではないことに留意されたい。
【００２５】
データ圧縮方法は、図５のブロック図を含むいくつかの方法で使用できるが、本明細書では２つの主要な方法について論じる。どの特定の方法を選択するかは主として、プリンタ・システム全体の推定コストによって決定される。より高価な実施態様では、ＣＰＵ１４０２は、圧縮アルゴリズム自体を実施するのに十分な処理能力およびメモリを有する。低コストのプリンタ・システムでは、ＣＰＵ１４０２が存在しなくてもよく、メモリ量は最小限に抑えられる。廉価な構成では、アプリケーション・プログラム１４００が圧縮アルゴリズムを実施しなければならない。
【００２６】
高性能のプリンタ・システムでは、アプリケーション・プログラム１４００は、高級プリンタ制御言語１４０１を使用してプリンタ・システムにデータを送る。ＣＰＵ１４０２は、高レベルプリンタ制御言語１４０１からデータを検索し、未圧縮フォーマットでそのデータをラスタ化してメモリ１４０３に格納する。次に、ＣＰＵは、未圧縮ラスタ化情報を１４０３から検索し、圧縮器１４０５を通過させ、圧縮器１４０５は次いで、圧縮済みイメージをメモリ１４０４に記憶し直す。ＤＭＡ１４０６は適当な時間に、ＣＰＵ１４０２の制御下で、圧縮済みイメージをメモリ１４０４から検索する。圧縮済みイメージは次いで伸長器１４０８に送られ、伸長器１４０８は伸長アルゴリズムを実行する。伸長器１４０８の出力は、未圧縮イメージ情報に従ってレーザ１４０９を変調するビデオ・チップ１４０７に送られる。
【００２７】
第１の構成の下では、アプリケーション・プログラム１４００が、ラスタ化データを、プリンタ・システムに送る前に圧縮できるようにすることによって、アプリケーション・プログラム１４００とプリンタ・システムの間のスループットを向上することができる。アプリケーション・プログラムは、このデータ圧縮方法を使用して、情報を圧縮し、次いで、高級ＰＣＬブロック１４０１に送る前に適当なページ記述言語に変換することができる。ＣＰＵ１４０２は、ページ記述言語命令を受け取ると、この命令を復号して、以後の情報が圧縮済みデータであることを知る。したがって、ＣＰＵ１４０２は、圧縮ステップをバイパスし、圧縮済みデータを直接、圧縮済みイメージ・メモリ１４０４に入れる。前記と同様に、ＤＭＡ１４０６はこの場合も、圧縮済みイメージを１４０４から検索して伸長器１４０８に送る。伸長器１４０８は、このイメージを伸長してビデオ・チップ１４０７およびレーザ・ダイオード１４０９に渡す。
【００２８】
第２の構成は、プリンタ・システム自体のコストを最小限に抑えようとするものである。そのような構成は、メモリ１４０４、ＤＭＡ１４０６、伸長器１４０８、ビデオ・チップ１４０７、およびレーザ・ダイオード１４０９しか使用しない。プリンタ・システムがＣＰＵを含まないので、アプリケーション・プログラム１４００はアルゴリズムの圧縮部分を実施しなければならない。
【００２９】
通常の印刷プロセスでは、ＤＭＡ１４０６は、圧縮済みイメージを、メモリ１４０４から検索し、前記と同様に、伸長器１４０８に送り、伸長器１４０８は、圧縮済みイメージを伸長する。この構成では、ＣＰＵ１４０２がもはや必要とされないので、プリンタ・システムのコストが著しく低減する。しかし、そのような構成では、アプリケーション・プログラム１４００が、イメージをラスタ化し圧縮する追加負担を負う。
【００３０】
本発明の好ましい実施例を例示し、その態様を説明したが、当業者には、本発明の趣旨や添付の特許請求の範囲の範囲から逸脱せずに、本発明に様々な修正を加えられることが容易に明らかになろう。
【図面の簡単な説明】
【図１】圧縮済みイメージ・データがどのように連続メモリに記憶されるかを示した図である。
【図２】圧縮済みイメージ・データが、本発明を使用して、どのように不連続メモリに記憶されるかを示した図である。
【図３】本発明によるデータ伸長の好ましい実施例を示すフローチャートである。
【図４】本発明による、図３に示した実施例の代替実施例を示すフローチャートである。
【図５】本発明を使用するプリンタ・システムのハイレベル機能図である。
【図６】本発明による好ましい実施例のデータ圧縮を示すフローチャートである。
【符号の説明】
２００  単一のメモリ・ブロック
１４００  アプリケーション・プログラム
１４０１  高レベルプリンタ制御言語
１４０２  ＣＰＵ
１４０３  メモリ
１４０５  圧縮器
１４０６  ＤＭＡ
１４０７  ビデオ・チップ
１４０８  伸長器
１４０９  レーザ
【図１】
0003628393.tif 000002
【図２】
0003628393.tif 000003
【図３】
0003628393.tif 000004
【図４】
0003628393.tif 000005
【図５】
0003628393.tif 000006
【図６】
0003628393.tif 000007