(57)【要約】【課題】ＬＺ符号の符号化速度を向上させる符号化装置を提供すること。【解決手段】入力されたデータを記憶するデータ記憶手段５５と、前記データから順番に２バイトずつ抽出し、前記２バイトを指し示すインデックス値を記憶する２バイトテーブル記憶手段の記憶場所を生成する記憶場所生成手段４２ａと、前記２バイトの組み合わせの数に応じた前記記憶場所を有し、前記インデックス値が設定された前記２バイトテーブル記憶手段５１と、前記インデックス値に対応付けて、前記データ内の前記２バイトの先頭アドレスが設定された２次元アドレステーブル５２と、前記２次元アドレステーブルに記憶された前記先頭アドレスから３バイト目以降と、現在、着目している２バイトの次の３バイト目以降が一致する限り次の１バイトを探索するリスト探索手段４２ｂと、前記リスト探索手段が探索した一致長さと一致位置を符号化する符号化手段４２ｃと、を有する。【選択図】図８
2018067781.tif 000002
【特許請求の範囲】
【請求項１】
ＬＺ符号化で一致長さと一致位置を符号化する符号化装置であって、
入力されたデータを記憶するデータ記憶手段と、
前記データに含まれる２バイトの組み合わせの数に応じた記憶場所を有し、前記２バイトを指し示すインデックス値が設定された２バイトテーブルが構築された記憶手段と、
前記データから順番に前記２バイトずつ抽出し、前記２バイトテーブルにおける前記インデックス値の記憶場所を生成する記憶場所生成手段と、
前記インデックス値に対応付けて、前記２バイトの前記データにおける先頭アドレスを記憶する２次元アドレステーブルと、
前記２次元アドレステーブルに記憶された前記先頭アドレスから３バイト目以降と、現在、着目している２バイトの次の３バイト目以降が一致する限り次の１バイトを探索するリスト探索手段と、
前記リスト探索手段が探索した一致長さと一致位置を符号化する符号化手段と、
を有する符号化装置。
【請求項２】
前記２バイトテーブルには初期値が記憶されており、
前記記憶場所生成手段は、前記記憶場所に初期値か記憶されているか否かによって、前記２バイトが初出か否かを判断し、
初出である場合、初出の２バイトの数をカウントアップすると共に、前記２バイトテーブルの前記記憶場所に前記初出の２バイトの数を記憶させ、
初出でない場合、前記記憶場所の前記初出の２バイトの数を前記インデックス値として取得する請求項１に記載の符号化装置。
【請求項３】
前記２次元アドレステーブルでは、１つの前記インデックス値に対応付けてＮ個（＞２）の前記先頭アドレスを記憶することができ、前記２次元アドレステーブルはＮ個のリングバッファとなっており、
前記記憶場所生成手段は、前記２バイトで特定される前記インデックス値に対応付けて前記先頭アドレスを登録すると共に、前記先頭アドレスがＮ個を超えると最も古いものから前記先頭アドレスを上書きすることを特徴とする請求項１又は２に記載の符号化装置。
【請求項４】
Ｎ個の前記先頭アドレスのそれぞれが有効か否かを示すリストＦＬＧを有し、
前記リスト探索手段は、Ｎ個の前記先頭アドレスごとに前記リストＦＬＧを参照し、３バイト目以降を探索するか否かを決定する請求項３に記載の符号化装置。
【請求項５】
前記２次元アドレステーブルに記憶されている前記先頭アドレスの数を前記インデックス値に対応付けて記憶するカウンタテーブルを有し、
前記記憶場所生成手段は、カウンタテーブルに記憶されている数の前記先頭アドレスのうち、現在、着目している２バイトから窓サイズ以内の先頭アドレスから３バイト目以降と、現在、着目している２バイトの次の３バイト目以降が一致するか否かを比較する請求項３又は４に記載の符号化装置。
【請求項６】
前記カウンタテーブルに記憶される前記先頭アドレスの数はＮ個を超えると初期値に戻る請求項５に記載の符号化装置。
【請求項７】
前記符号化手段は画像データを１ラインごとに符号化し、新たなラインを符号化する際に前記２バイトテーブル、前記２次元アドレステーブル、及び、前記カウンタテーブルを初期化することを特徴とする請求項５又は６に記載の符号化装置。
【請求項８】
前記符号化手段は、プリンタの画像データを圧縮するものであり、Ｃ，Ｍ，Ｙ、Ｋの色ごとに符号化することを特徴とする請求項１〜７のいずれか１項に記載の符号化装置。
【請求項９】
ＬＺ符号化で一致長さと一致位置を符号化する情報処理装置に、
入力されたデータを記憶するデータ記憶手段と、
前記データに含まれる２バイトの組み合わせの数に応じた記憶場所を有し、前記２バイトを指し示すインデックス値が設定された２バイトテーブルが構築された記憶手段と、
前記インデックス値に対応付けて、前記データの前記２バイトの先頭アドレスを記憶する２次元アドレステーブルと、を参照させ、
前記情報処理装置を、
前記データから順番に前記２バイトずつ抽出し、前記２バイトテーブルにおける前記インデックス値の記憶場所を生成する記憶場所生成手段と、
前記２次元アドレステーブルに記憶された前記先頭アドレスから３バイト目以降と、現在、着目している２バイトの次の３バイト目以降が一致する限り次の１バイトを探索するリスト探索手段と、
前記リスト探索手段が探索した一致長さと一致位置を符号化する符号化手段、として機能させるためのプログラム。
【請求項１０】
ＬＺ符号化で一致長さと一致位置を符号化する符号化装置が行う符号化方法であって、
記憶場所生成手段が、データ記憶手段に記憶されたデータから順番に前記２バイトずつ抽出し、
前記データに含まれる２バイトの組み合わせの数に応じた記憶場所を有し、前記２バイトを指し示すインデックス値が設定された２バイトテーブルが構築された記憶手段の前記記憶場所を生成するステップと、
前記２バイトテーブルから、前記インデックス値を取得するステップと、
リスト探索手段が、前記インデックス値に対応付けて、前記データの前記２バイトの先頭アドレスを記憶する２次元アドレステーブルに記憶された前記先頭アドレスから３バイト目以降と、現在、着目している２バイトの次の３バイト目以降が一致する限り次の１バイトを探索するステップと、
符号化手段が、前記リスト探索手段が探索した一致長さと一致位置を符号化するステップと、を有する符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化装置、プログラム及び符号化方法に関する。
【背景技術】
【０００２】
データを効率よく圧縮する方法として、ユニバーサル符号によりデータを圧縮する方法が実用化されている。ユニバーサル符号は情報保存型のデータ圧縮方法であり、データ圧縮時に情報源の統計的な性質を予め仮定しないため、種々のタイプ（文字コード、オブジェクトコードなど）のデータの圧縮に適用することができる。
【０００３】
ユニバーサル符号の代表的な符号化方法として、レンペル・ジブ(Ziv-Lempel)符号がある。レンペル・ジブ符号化はＬＺ符号化とも呼ばれ、データ中に現れた文字列をポインタと対応させる辞書を適応的に構築し，辞書中の文字列がデータに再び現れたときにはポインタで置き換えていくことで圧縮を行う符号化方法である。
【０００４】
レンペル・ジブ符号では、ユニバーサル型と、増分分解型(Incremental parsing) の２つのアルゴリズムが提案されており、ユニバーサル型アルゴリズムを用いた実用的な方法として、ＬＺＳＳ符号があり、又、増分分解型アルゴリズムを用いた実用的な方法として、ＬＺＷ（Lempel- Ziv- Welch）符号がある。
【０００５】
ＬＺＳＳのベースとなるＬＺ７７のアルゴリズムは、着目しているデータと一致する最大長の過去のデータを任意の位置で区切り、過去の系列の複製として符号化する方法である。具体的には、符号化済みの入力データを格納する移動窓と、これから符号化するデータを格納する先読みバッファとを備え、先読みバッファのデータ列と移動窓のデータ列のすべての部分系列とを照合して、移動窓中で一致する最大長の部分系列を求める。
【０００６】
そして、移動窓中でこの最大長の部分系列を指定するために、「その最大長の部分系列の開始位置」、「一致する長さ」、及び「不一致をもたらした次のシンボル」の組を符号化する。次に、先読みバッファ内の符号化したデータ列を移動窓に移して、先読みバッファ内に符号化したデータ列の次の新たなデータ列を入力する。以下、同様の処理を繰り返していくことで、データを部分系列に分解して符号化を実行していく。
【０００７】
ＬＺ７７方式の符号化では、最長一致文字列の探索に最も時間がかかるため、探索を高速化する技術が提案されている（例えば、特許文献１参照。）。特許文献１には、ハッシュ法と連結リストの組合により、２文字の一致位置を求め、３文字以降の一致は一文字ずつ照合して、最終的に最長一致位置を検出する２バイトハッシュ法が開示されている。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、特許文献１に開示された２バイトハッシュ法では、圧縮速度が遅いという問題がある。図１７を用いて説明する。図１７は特許文献１の２バイトハッシュ法について説明する図である。２バイトハッシュ法は、ハッシュ法と連結リストの組合せにより、２文字の一致位置を求め、３文字以降の一致は一文字ずつ照合する方法である。まず、２バイトのハッシュ値が算出されハッシュ表のアドレスを指示する。このアドレスには、ハッシュ衝突確認用のテーブルのアドレス（Ａ１）が格納されている。Ａ１は最近一致文字列候補の位置である。Ａ１はＣ１，Ｃ２の一方の位置を示し、過去の同じ文字列であるＣ１，Ｃ２と連結するためのアドレスリストの作成が可能になる。ハッシュ衝突確認用の文字列が異なっている場合はハッシュが衝突したことが分かる。
【０００９】
しかし、この方式はハッシュ関数を使用するため、ハッシュ関数の衝突が起きル場合があり、効率が悪い。すなわち、符号化の効率低下をもたらすため、例えば画像をライン単位などの小さい領域に完結して圧縮する場合に連結リストの生成とクリアに時間がかかってしまう。
【００１０】
本発明は、上記課題に鑑み、ＬＺ符号化の符号化速度を向上させる符号化装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、ＬＺ符号化で一致長さと一致位置を符号化する符号化装置であって、入力されたデータを記憶するデータ記憶手段と、前記データから順番に２バイトずつ抽出し、前記２バイトを指し示すインデックス値を記憶する２バイトテーブル記憶手段の記憶場所を生成する記憶場所生成手段と、前記２バイトの組み合わせの数に応じた前記記憶場所を有し、前記インデックス値を記憶する前記２バイトテーブル記憶手段と、前記インデックス値に対応付けて、前記データ内の前記２バイトの先頭アドレスを記憶する２次元アドレステーブルと、前記２次元アドレステーブルに記憶された前記先頭アドレスから３バイト目以降と、現在、着目している２バイトの次の３バイト目以降が一致する限り次の１バイトを探索するリスト探索手段と、前記リスト探索手段が探索した一致長さと一致位置を符号化する符号化手段と、を有する。
【発明の効果】
【００１２】
ＬＺ符号化の符号化速度を向上させる符号化装置を提供することができる。
【図面の簡単な説明】
【００１３】
【図１】プリンタシステムの構成例を説明する図の一例である。
【図２】プリンタコントローラボードのブロック図の一例である。
【図３】プリンタコントローラボードの機能をブロック状に示す機能ブロック図の一例である。
【図４】図３の符号化処理部のより詳細な機能ブロック図の一例である。
【図５】図３の復号処理部のより詳細な機能ブロック図の一例である。
【図６】符号のフォーマットの一例を示す図である。
【図７】ライン単位の符号化を模式的に説明する図である。
【図８】２バイトテーブルを用いた符号化を説明する図の一例である。
【図９】符号化方式の全体動作を示すフローチャート図の一例である。
【図１０】図９のＬＩＮＥ符号化処理を説明するフローチャート図の一例である。
【図１１】スライド探索の処理手順を示すフローチャート図の一例である。
【図１２】スライド探索符号化の手順を示すフローチャート図の一例である。
【図１３】リスト探索処理の手順を示すフローチャート図の一例である。
【図１４】リスト探索結果符号化の手順を示すフローチャート図の一例である。
【図１５】スライド探索の具体例を示す図である。
【図１６】リスト探索の具体例を示す図である。
【図１７】特許文献１の２バイトハッシュ法について説明する図である。
【発明を実施するための形態】
【００１４】
以下、本発明を実施するための形態として符号化装置と符号化装置が行う符号化方法について図面を参照しながら説明する。
【００１５】
＜プリンタシステムの構成例＞
図１は、プリンタシステムの構成例を説明する図の一例である。図１（ａ）は従来のプリンタシステム１００であり、図１（ｂ）は本実施形態のプリンタシステム１００である。構成はどちらも同様であり、ＣＰＵ１、メインメモリ１４、ＰＣＩｅバス１５ａ、及びＡＳＩＣ１７を有している。しかし、処理の手順が異なっている。
【００１６】
従来の動作は以下のようになる。
（１）ＣＰＵ１がメインメモリ１４にＣＭＹＫバンド画像を書き込む。
（２）ＡＳＩＣ１７の符号化装置１７ａはＣＭＹＫバンド画像を読み出して符号化し、メインメモリ１４にＣＭＹＫページ符号として書き込む。
（３）ＡＳＩＣ１７の復号装置１７ｂがＣＭＹＫページ符号をメインメモリ１４から読み出して復号しプリンタエンジン２１に出力する。
【００１７】
本実施形態のプリンタシステム１００の動作は以下のようになる。
（１）ＣＰＵ１がメインメモリ１４にＣＭＹＫバンド画像を書き込む。
（２）ＣＰＵ１がＣＭＹＫバンド画像を読み出して符号化し、メインメモリ１４にＣＭＹＫページ符号として書き込む。
（３）ＡＳＩＣ１７の復号装置１７ｂがＣＭＹＫページ符号をメインメモリ１４から読み出して復号しプリンタエンジン２１に出力する。
【００１８】
本実施形態の構成によればＣＰＵ１が符号化するので符号化装置１７ａを省略できコストの低減が可能になる。
【００１９】
＜ハードウェア構成例＞
図２は、プリンタコントローラボード２０のブロック図の一例である。プリンタコントローラボード２０は主に、コントローラ１３、ＲＯＭ１６、メインメモリ１４、バス１５、ＡＳＩＣ１７、及び、符号メモリ１８を有している。さらに、コントローラ１３はＣＰＵ１、ＣＰＵ Ｉ/Ｆ２、メモリＡＲＢ３、通信コントローラ７、ＤＭＡ５、メモリコントローラ４、及びバスコントローラ６を有している。プリンタコントローラボード２０又はＣＰＵ１３は本実施形態の符号化装置に相当する。
【００２０】
まず、ＲＯＭ１６には、各種のプログラムや、文字などのフォント情報が記憶されている。後述するＣＰＵ１はこのプログラムを実行して符号化等を行う。
【００２１】
ＰＣ１９ではワープロソフトウェアなどの各種のアプリケーションプログラムが動作しており、ユーザが印刷の操作を行うと、プリンタドライバがＰＤＬ（Printer Description Language）で記述された印刷データ（以下、ＰＤＬという）生成する。ＰＣ１９はＰＤＬをプリンタのプリンタコントローラボード２０に送信する。また、プリンタコントローラボード２０とプリンタエンジン２１とでプリンタ２００を構築できる。プリンタコントローラボード２０は情報処理装置の機能を有している。
【００２２】
通信コントローラ７はネットワークＮを介してＰＣ１９と接続されており、プリンタコントローラボード２０はＰＣ１９からＰＤＬを受信する。ＣＰＵ１は、プリンタコントローラボード２０全体の制御を行う。ＣＰＵ１はＰＣ１９から送信されたＰＤＬをメインメモリ１４に記憶し、描画コマンドを抽出する。描画コマンドを解析することで、メインメモリ１４にＣ版少値バンド画像、Ｍ版少値バンド画像、Ｙ版少値バンド画像、及びＫ版少値バンド画像（これらをまとめて少値ＣＭＹＫバンド画像という）を書き込む。この少値とは元の画像よりもデータ数が低減されていることをいい、例えば、階調が少なくなっている。
【００２３】
ＣＰＵ Ｉ/Ｆ２は、ＣＰＵ１とメモリＡＲＢ３（アービタ）とのインタフェースである。ＣＰＵ１の端子が挿入されるソケットなどである。
【００２４】
メモリＡＲＢ３は、メモリコントローラ４へのアクセスを調停する。メインメモリ１４にはＣＰＵ１、バスコントローラ６、ＤＭＡ５及び通信コントローラ７がアクセスするため、これらがメインメモリ１４にアクセス要求を出力した場合に排他制御し、同時にはいずれか１つのアクセスを許可する。また、ＣＰＵ１、バスコントローラ６、ＤＭＡ５及び通信コントローラ７のうち複数がアクセスを要求した場合、優先度等に基づいていずれをアクセスさせるか決定する。
【００２５】
メモリコントローラ４はメインメモリ１４からの読み出し及び書き出し等を行い、また、読み出し先や書き込み先のアドレスをコントロールする。メモリコントローラ４はメモリＡＲＢ３を介してＣＰＵ１、バスコントローラ６、ＤＭＡ５及び通信コントローラ７と接続されている。
【００２６】
ＤＭＡ５はメモリコントローラ４とバス１５の先に接続されたＡＳＩＣ１７間のダイレクトメモリアクセスを行う。つまり、ＣＰＵ１はメインメモリ１４のアドレスをＤＭＡ５に指定するだけで、ＤＭＡ５がメインメモリ１４からバスコントローラ６にデータを送信する。バスコントローラ６から受信する場合も同様である。
【００２７】
バスコントローラ６は、バス１５の使用権を調停してバス１５を使用できる周辺機器やコントローラ１３を決定する。通信コントローラ７は、ネットワークに接続されており、ネットワークから各種データやコマンドなどを受け取る。通信コントローラ７はメモリＡＲＢ３を介して各種のコントローラ１３に接続されている。
【００２８】
メインメモリ１４は、読み書きが高速な例えば揮発性のメモリである。例えばＳＤＲＡＭ、ＤＤＲ，ＤＤＲ２、ＤＤＲ３、ＤＤＲ４などである。メインメモリ１４にはＰＤＬ，描画コマンド、少値ＣＭＹＫバンド画像や、及び、Ｃ版少値ページ符号、Ｍ版少値ページ符号、Ｙ版少値ページ符号、及びＫ版少値ページ符号（これらをまとめて少値ＣＭＹＫページ符号という）などが記憶される。また、ＣＰＵ１がプログラムを実行する際は、ＲＯＭ１６から展開されたプログラムが記憶されている。
【００２９】
バス１５は、コントローラ１３とＡＳＩＣ１７とを接続するシリアルバスである。例えば、ＰＣＩｅバス１５ａであるが高速であればどのようなバス１５でもよい。
【００３０】
一方、ＡＳＩＣ１７は、バスＩＦ８、ＤＭＡ処理部９、メモリ制御部１０、少値復号処理部１１、及び、エンジンコントローラ１２を有する。また、メモリ制御部１０は符号メモリ１８と接続されている。
【００３１】
ＡＳＩＣ１７は、ＰＣ１９からの印刷要求に対しプリンタエンジン２１を制御して印刷を行う。ＡＳＩＣ１７はメインメモリ１４に格納された少値ＣＭＹＫページ符号を、バス１５を介して読み込み、符号メモリ１８へ記憶させる。また、プリンタエンジン２１に同期して、符号メモリ１８から少値ＣＭＹＫページ符号を読み込み、復号してプリンタエンジン２１に転送する。そしてプリンタエンジン２１を制御し、画像を印刷する。
【００３２】
符号メモリ１８はメインメモリ１４と同様の高速なメモリであることが好ましい。符号メモリ１８はプリンタエンジン２１と同期して少値ＣＭＹＫページ符号をプリンタエンジン２１に送信するためのバッファメモリである。
【００３３】
バスＩＦ８はバス１５とのインタフェースであり、コントローラ１３のＣＰＵ１と接続され、ＣＰＵ１をＤＭＡ処理部９と接続させる。ＣＰＵ１はＤＭＡ処理部９を制御して、ＡＳＩＣ１７をコントローラ１３側と通信させる。
【００３４】
ＤＭＡ処理部９は、ＣＰＵ１によりメインメモリ１４の少値ＣＭＹＫページ符号の読み出しを要求されると、メインメモリ１４から少値ＣＭＹＫページ符号が読み出してメモリ制御部１０を介して符号メモリ１８へ転送する。
【００３５】
メモリ制御部１０は符号メモリ１８からの読み出し及び書き出し等を行い、また、読み出し先や書き込み先のアドレスをコントロールする。メモリ制御部１０はＤＭＡ処理部９と少値復号処理部１１と接続されている。メモリ制御部１０は、ＤＭＡ処理部９及び少値復号処理部１１からのメモリアクセスの要求を処理する。
【００３６】
少値復号処理部１１は符号メモリ１８から少値ＣＭＹＫページ符号を読み込み復号しエンジンコントローラ１２に転送する。エンジンコントローラ１２は復号された少値ＣＭＹＫバンド画像でプリンタエンジン２１をコントロールする。つまり、少値ＣＭＹＫバンド画像でレーザを点灯して感光体を感光させ、トナーを付着させ用紙に画像を形成する。
【００３７】
プリンタエンジン２１は、電子写真方式やインクジェット方式等で、画像を用紙等の記録媒体に形成するエンジン部分である。方式によって構成は変わるが、電子写真方式の場合、回転駆動される感光体の周囲に、帯電部、光書き込み部、現像部、転写部、分離部、クリーニング部等が配置されている。
【００３８】
＜機能について＞
図３は、プリンタコントローラボード２０の機能をブロック状に示す機能ブロック図の一例である。プリンタコントローラボード２０は、通信処理部３１、ＰＤＬ記憶部３２、ＰＤＬ解析部３３、描画コマンド記憶部３４、描画処理部３５、バンド画像記憶部３６、符号化処理部３７、第１のページ符号記憶部３８、第２のページ符号記憶部３９、及び復号処理部４０を有する。
【００３９】
通信処理部３１は、図２のＣＰＵ１がプログラムを実行し通信コントローラ７を制御すること等により実現され、ＰＣ１９からＰＤＬを受信する。通信処理部３１は、ＰＤＬを図２のメインメモリ１４のＰＤＬ領域に記憶させる。
【００４０】
ＰＤＬ記憶部３２は、図２のメインメモリ１４のＰＤＬ領域に構築されるＰＤＬの記憶部であり、ＰＤＬを記憶する。
【００４１】
ＰＤＬ解析部３３は図２のＣＰＵ１がプログラムを実行すること等により実現され、ＰＤＬ記憶部３２に記憶されたＰＤＬを解析し描画コマンドを生成する。描画コマンドは描画コマンド記憶部３４に記憶される。
【００４２】
描画コマンド記憶部３４は、図２のメインメモリ１４の描画コマンド領域に構築される描画コマンドの記憶部であり、描画コマンドを記憶する。
【００４３】
描画処理部３５は、図２のＣＰＵ１がプログラムを実行すること等により実現され、描画コマンド記憶部３４から描画コマンドを読み込み実行し、生成した画像データをバンド画像記憶部３６に記憶させる。
【００４４】
バンド画像記憶部３６は、図２のメインメモリ１４に構築される少値ＣＭＹＫバンド画像の記憶部であり、少値ＣＭＹＫバンド画像を記憶する。
【００４５】
符号化処理部３７は、図２のＣＰＵ１がプログラムを実行すること等により実現され、バンド画像記憶部３６から少値ＣＭＹＫバンド画像を読み込み、符号化し,第１のページ符号記憶部３８に記憶させる。
【００４６】
第１のページ符号記憶部３８は、図２のメインメモリ１４に構築される少値ＣＭＹＫページ符号の記憶部であり、少値ＣＭＹＫページ符号を記憶する。
【００４７】
この第１のページ符号記憶部３８に少値ＣＭＹＫページ符号が記憶されると、ＤＭＡ５がＡＳＩＣ１７に少値ＣＭＹＫページ符号を送信する。
【００４８】
第２のページ符号記憶部３９は、図２の符号メモリ１８に構築される少値ＣＭＹＫページ符号の記憶部であり、ＤＭＡ５により転送された少値ＣＭＹＫページ符号を記憶する。
【００４９】
復号処理部４０は、図２の少値復号処理部１１により実現され、第２のページ符号記憶部３９の少値ＣＭＹＫページ符号を読み込み、復号しプリンタエンジン２１へ転送する。
【００５０】
＜符号化処理部３７、復号処理部４０の機能＞
図４は、図３の符号化処理部３７のより詳細な機能ブロック図の一例である。符号化処理部３７は画像読込部４１、Slide List生成処理部４２、ハフマン符号化処理部４３、及び、符号書込部４４を有する。
【００５１】
画像読込部４１はバンド画像記憶部３６から少値ＣＭＹＫバンド画像を読み込み、Slide List生成処理部４２へ転送する。
【００５２】
Slide List生成処理部４２は後述する処理により、図６に示すようにSlide符号とＥＳＣ符号を作成する。符号化されたデータをハフマン符号化処理部４３へ転送する。Slide List生成処理部４２はスライド探索部４２ａ、リスト探索部４２ｂ、及び、符号化部４２ｃを有している。スライド探索部４２ａは後述するスライド探索処理を行い、リスト探索部４２ｂは後述するリスト探索を行う。また、符号化部４２ｃはそれぞれの探索結果を符号化する。なお、Slide List生成処理部４２はＣ，Ｍ，Ｙ、Ｋの色ごとに符号化する。
【００５３】
ハフマン符号化処理部４３はSlide List生成処理部４２から受け取ったSlide符号とＥＳＣ符号をハフマン符号化し符号書込部４４へ転送する。
【００５４】
符号書込部４４はハフマン符号化処理部４３で生成された符号を第１のページ符号記憶部３８へ書き込む。
【００５５】
図５は、図３の復号処理部４０のより詳細な機能ブロック図の一例である。復号処理部４０は符号読込部４６、ハフマン復号処理部４７、Slide展開部４８、及び、画像書込部４９を有する。
【００５６】
符号読込部４６は、第２のページ符号記憶部３９からハフマン符号化済みの少値ＣＭＹＫページ符号を読み込む。
【００５７】
ハフマン復号処理部４７は、読み込まれた少値ＣＭＹＫページ符号を解釈し、ハフマン符号化と逆の処理で図６のようなSlide符号とＥＳＣ符号に復号する。
【００５８】
Slide展開部４８は、図６のようなSlide符号とＥＳＣ符号を取得し、元の画素データに復号し、画像書込部４９に出力する。画像書込部４９は元の画素データをプリンタエンジン２１に出力する。
【００５９】
＜符号フォーマット＞
図６は、符号のフォーマットの一例を示す。符号には２つのフォーマットがある。１つはＥＳＣ符号であり、もう１つはＳｌｉｄｅ符号である。ＥＳＣ符号は、着目している２バイトと過去のデータ列のデータが一致しない場合のラインデータの１バイト分の符号フォーマットである。一致していないので符号化できず、ＥＳＣ符号は８ｂｉｔの画素値をそのまま有する。また、ＥＳＣ符号であるかＳｌｉｄｅ符号であるかを示すヘッダー（１ｂｉｔ）は"０"とする。
【００６０】
Ｓｌｉｄｅ符号は、着目している２バイトと過去のデータ列のデータが一致した場合のラインデータの符号フォーマットである。現在着目しているデータと、既に探索済みのラインデータ上のデータが一致する長さによって３バイト以上が符号化される場合もある。Ｓｌｉｄｅ符号は、現在着目しているデータと一致した探索済みのラインデータ上のデータの位置（一致位置値）と、一致した長さをバイト数で示す（Length）を有する。一致位置値は現在着目している２バイトからの相対位置である。図６の例では、Slideの長さ（窓サイズ）が256個であるとすると一致位置は8bitとなり、最大の一致長さも８bitとなるためLength値も８bitとなる。また、ＥＳＣ符号であるかＳｌｉｄｅ符号であるかを示すヘッダー（１ｂｉｔ）は"１"とする。
【００６１】
＜１バンドの符号フォーマット＞
図７は、本実施形態のライン単位の符号化を模式的に説明する図である。図７は、縦方向に各ラインを示し、横方向に符号化後のラインのデータ量を示す。このようにライン単位に符号化されており、毎ラインごとに符号化が完結することが本実施形態の特徴の１つである。こにより、図８に示すように、２次元アドレステーブルやカウンタテーブルはラインサイズの容量で済むことになる。
【００６２】
＜２バイトテーブル法について＞
図８は、２バイトテーブルを用いた符号化を説明する図の一例である。本実施形態では、Slide List生成処理部４２は２バイトテーブル５１、２次元アドレステーブル５２、カウンタテーブル５３、及びリストＦＬＧ５４を使って符号化する。２バイトテーブル５１、２次元アドレステーブル５２、カウンタテーブル５３、及びリストＦＬＧ５４は記憶手段としてのメインメモリ１４に構築される。
【００６３】
図８では２バイト（Ｃ２，Ｃ１）を符号化する例を説明する。２バイトテーブル５１は２バイトの全ての組合せ分の長さがある。１バイト（８ビット）は２５６値を取るので、２バイトでは256×256の値を取り得る。メモリの容量が許容すれば３バイトテーブルが用意されてもよい。
【００６４】
スライド探索部４２ａは、２バイト（Ｃ２、Ｃ１）が入力されると、「Ｃ２×２５６＋Ｃ１（これを２バイト値という）」で示すインデックス値の記憶場所（アドレス）を生成する。インデックス値は、２バイトテーブル５１における２バイト（Ｃ２、Ｃ１）の組み合わせの種類（識別）を示す。つまり、２バイトテーブル５１の記憶場所にはインデックス値（Ａ１〜Ａ１７００）が記憶されている。
【００６５】
２次元アドレステーブル５２は、あるラインデータにおいて現時点までに登録された同じ２バイトの先頭アドレスが登録されている。２次元アドレステーブルの行数はラインサイズのバイト数だけあれば良い。ライン上の２バイトが全て異なる場合、ラインサイズのバイト数だけあれば、全ての組み合わせをカバーできる。２次元アドレステーブル５２の行は、２バイトテーブル５１に格納されたインデックス値で識別される。
【００６６】
また、２次元アドレステーブル５２の列数は、図８の例では８個となっている。２次元アドレステーブル５２はリングバッファとなっているので、同じ２バイトが９個見つかると、一番古い０番目の列にもどり先頭アドレスが登録される。次の（１０個目）先頭アドレスは１番目の列に登録される。このようにリングバッファとして巡回するので古いものから消えていく。
【００６７】
２次元アドレステーブル５２の列数を大きくし、ラインメモリ５５から見つかった同じ２バイトの先頭アドレスを全て登録できるように構成すると、画像データの圧縮率は良くなる。しかし、リスト探索部４２ｂは２次元アドレステーブル５２の全ての先頭アドレスについて、３バイト目が現在、着目しているデータと一致するかどうかをチェックする必要がある。基本的に一致する確率は現在の位置に近いほど高いので、効率が悪く、処理スピードの低下へとつながる。このため、図８のように２次元アドレステーブル５２の列数は８個）のリングバッファで構成されている。なお、８個の一例であり、数個から数十個など、最適な値に設計される。
【００６８】
ラインメモリで窓サイズ内の同じ２バイトをリストという。窓サイズとは、現在、着目しているデータに対し同じ２バイトが符号化される範囲である。リスト探索部４２ｂは、現在、着目している１バイトのデータに対しリストとされる他の２バイトについて、３バイト目以降（３バイト目、４バイト目等）を比較して、一番長いバイト数を符号化する。
【００６９】
２バイト値により２バイトテーブルの記憶場所が一意に特定される。特定された記憶場所にはテーブルカウンタの値が記憶される。テーブルカウンタはＡ１から始まり、Ａ１７００（最大値なのでＡ１７００まで到達しない場合もある）まで１つずつ増える。２バイトが初出の際に２バイトテーブルの２バイトで特定される記憶場所にテーブルカウンタの値が記憶されるので、２回目以降に同じ２バイトが検出された場合に２バイトテーブルでＡ１〜Ａ１７００を特定できる。したがって、テーブルカウンタは２次元アドレステーブル５２の行の認識番号となる。２次元アドレステーブル５２の行番号をインデックス値と称する。
【００７０】
なお、カウンタテーブル５３は各インデックス値の先頭アドレスの数を記憶し、リストＦＬＧ５４は先頭アドレスが有効か否かを示す。２次元アドレステーブル５２、２バイトテーブル、カウンタテーブル５３及びリストＦＬＧ５４はラインごとに初期化される。
【００７１】
＜動作手順＞
図９は、符号化方式の全体動作を示すフローチャート図の一例である。図９の処理はバンド画像記憶部３６に少値ＣＭＹＫバンド画像が記憶されるとスタートする。ライン単位ごとにＬＩＮＥ符号化処理を呼び出し，全てのラインを処理すると終了する。符号化はSlide List生成処理部４２が行うものとし、特に記載がない場合はSlide List生成処理部４２が行うものとする。
【００７２】
Slide List生成処理部４２は変数ＩＹに０を設定する（Ｓ１）。ＩＹはバンド幅のライン数と比較される変数である。
【００７３】
次に、ＬＩＮＥ符号化処理を行う（Ｓ２）。そして、変数ＩＹを１つ大きくし（Ｓ３）、ＩＹがバンド高さ分になると終了する（Ｓ４）。
【００７４】
図１０は、図９のＬＩＮＥ符号化処理を説明するフローチャート図の一例である。このライン符号化処理は大きく２つのステップからなる。１つは、ステップＳ８のスライド探索である。すなわち、図８で説明したように２バイトにより２次元アドレステーブル５２のインデックス値を見つけ、インデックス値に対応付けられた先頭アドレスが、ＩＸが示す現在、着目しているラインメモリ５５のＸ値から窓サイズに入っているか否かを判断する。窓サイズに入っている場合は、先頭アドレスごとに設けられた図８のリストＦＬＧ５４の各値に"１"を設定する。
【００７５】
もう１つは、ステップＳ１０のリスト探索である。この処理は図８に示したリストＦＬＧ５４が有効な２次元アドレステーブル５２の先頭アドレスから３バイト目、４バイト目と順次比較して、一番長く連続するデータを求める処理である。本実施形態では、２５６バイト目まで探索する。
【００７６】
まず、ステップＳ１〜Ｓ３で変数の初期化を行っている。ＩＸはラインメモリ５５において現在、着目している画素のＸ値を示す。テーブルカウンタは１（＝Ａ１）から始まる。スライドＦＬＧはスライド探索が有効であるか否かを示す。スライド探索とは一致位置の探索を言う。
【００７７】
Slide List生成処理部４２は１ライン分の画素値を配列のラインメモリ５５に取り込む（Ｓ４）。
【００７８】
次に、ラインメモリ５５の０番目の画素をデータＡとする（Ｓ５）。
【００７９】
次に、ＩＸが示すラインメモリ５５の画素をデータＢに入れる（Ｓ６）。つまりラインデータの先頭から順番に符号化する。
【００８０】
次に、スライドＦＬＧが０（ゼロ）か否かを判断する（Ｓ７）。これは、スライドＦＬＧを見てリストが見つかったか否かを判断するためである。リストが見つかると、リスト探索が行われる。
【００８１】
スライドＦＬＧ＝０の場合、次のスライド探索を始めるので、スライド探索を行う（Ｓ８）。ステップＳ８の詳細は後述される。
【００８２】
次に、符号化部４２ｃはスライド探索結果に基づき符号化処理を行う（Ｓ９）。ステップＳ９の詳細は後述される。
【００８３】
スライドＦＬＧ＝１である場合、リスト探索部４２ｂは、スライド探索で見つけたリストをたどるリスト探索を行う（Ｓ１０）。ステップＳ１０の詳細は後述される。
【００８４】
次に、符号化部４２ｃはリスト探索結果に基づき符号化処理を行う（Ｓ１１）。ステップＳ１１の詳細は後述される。
【００８５】
１ライン分処理したか否かを判断し（Ｓ１２）、終了していない場合はステップＳ６以降を繰り返す。１ライン分、終了している場合、図１０が終了し図９のステップＳ３に戻る。
【００８６】
<<スライド探索>>
図１１は、スライド探索の処理手順を示すフローチャート図の一例である。スライド探索は、図８にて説明したように、２バイトから２次元アドレステーブル５２のインデックス値に対応付けられた先頭アドレスを特定し、ＩＸが示す現在、着目（符号化）しているラインメモリ５５から窓サイズに入っているものを見つけ出す処理である。窓サイズに入っている先頭アドレス（有効な先頭アドレス）は図６のリストＦＬＧ５４の各値に"１"が設定される。なお、図１５にスライド探索の具体例を示す。
【００８７】
Slide List生成処理部４２のスライド探索部４２ａは、データＡ，データＢを用いて２バイトテーブル５１におけるインデックス値の記憶場所を生成する。「２バイト値＝データＡ×２５６＋データＢ」である。
【００８８】
次に、２バイト値で２バイトテーブル５１を探索し、設定されているインデックス値を読み出す（Ｓ２）。この２バイトが初出の場合、２バイトテーブル５１の記憶場所には何も記憶されていないので０が格納されている。初出でない場合、Ａ１からＳ１７００のインデックス値が記憶されている。
【００８９】
このインデックス値で指定されるカウンタテーブルに設定された数が０か否かを判断する（Ｓ３）。カウンタテーブルに設定された数が０の場合、この２バイトは初出であるので，処理はステップＳ１７へ進む。インデックス値が０かどうかを判断してもよい。
【００９０】
まず、２バイト値で定まる２バイトテーブル５１の記憶場所にテーブルカウンタの値を設定する（Ｓ１７）。テーブルカウンタは２次元アドレステーブル５２の何個の行に先頭アドレスが登録されたかを示し、上記のように２次元アドレステーブルの行の認識番号となる。２回目以降に同じ２バイトが検出された場合、２バイトテーブルに現在のテーブルカウンタの値が記憶されているので、スライド探索部４２ａは２次元アドレステーブルの行（インデックス値）を取得できる。
【００９１】
次に、テーブルカウンタと０で指定される２次元アドレステーブル５２のマスに、現在の２バイトの先頭アドレスであるＩＸを設定する（Ｓ１８）。
【００９２】
次に、テーブルカウンタで指定されるカウンタテーブル５３に"１"を設定する（Ｓ１９）。そしてテーブルカウンタを１つ大きくする（Ｓ２０）。すなわち、カウントアップする。
【００９３】
ステップＳ３でカウンタテーブル５３の値が"０"でない場合、すでに同じ２バイトが登録されているので、処理はステップＳ４に進む。
【００９４】
まず、変数ＩＷを初期化して０を設定する（Ｓ４）。この変数ＩＷは、図８のリストＦＬＧ５４の０〜７を示すポインタである。
【００９５】
ステップＳ５，６で、２次元アドレステーブル５２の各先頭アドレスと現在のラインメモリ５５のＸ値を示すＩＸの値との相対アドレスを求める。
【００９６】
まず、インデックス値とＩＷで指定される２次元アドレステーブル５２のマスに登録された先頭アドレスを求め、変数ＷＩＸに設定する（Ｓ５）。
【００９７】
次に、相対アドレスをＩＸ−ＷＩＸで算出する（Ｓ６）。
【００９８】
そして、相対アドレスが窓サイズを超えているか否かを判断する（Ｓ７）。窓サイズは、１ラインで同じ２バイトを探索する範囲である。これは同じ２バイトはある範囲で検出される確率が高いため相対アドレスが窓サイズを超えると処理を打ち切り符号化効率を上げるためである。
【００９９】
ステップＳ７で相対アドレスが窓サイズ以上の場合（Ｓ７のＮｏ）、ＩＷの示すリストＦＬＧ５４を無効にする（Ｓ８）。つまりゼロを設定する。
【０１００】
ステップＳ７で窓サイズを超えていない場合（Ｓ７のＹｅｓ）、スライド探索が成功したことを示すスライドＦＬＧに"１"を設定する（Ｓ９）。
【０１０１】
そして、ＩＷが示すリストＦＬＧ５４を有効にする（Ｓ１０）。つまり"１"を設定する。
【０１０２】
次に、ＩＷを１つ大きくする（Ｓ１１）。
【０１０３】
そして、ＩＷが２次元アドレステーブル５２のデータ数を示すカウンタテーブル５３に登録された値を超えていないかを判断する（Ｓ１２）。
【０１０４】
超えていない場合は処理がステップＳ５に戻り、２次元アドレステーブル５２の１行の全ての先頭アドレスについて処理される。
【０１０５】
超えていた場合、処理がステップＳ１３に進む。インデックス値でカウンタテーブル５３を指定して記憶されている値を１つ大きくする（Ｓ１３）。また、８以上となる場合は０に戻すことで、０−７の値に丸める。
【０１０６】
インデックス値とＩＷで指定される２次元アドレステーブル５２のマスに現在のＩＸを設定する（Ｓ１４）。
【０１０７】
次に、２次元アドレステーブル５２のデータ数を示すＩＷでカウンタテーブル５３を更新する（Ｓ１５）。
【０１０８】
そして、ＩＷに対応するリストＦＬＧ５４の値を"０"に設定する（Ｓ１６）。これは、現在、着目している２バイトは直ぐにリスト探索されないようにするためである。
【０１０９】
図１１のステップＳ１３、Ｓ１５の処理でリングバッファのように古い先頭アドレスを削除して（上書きして）、新しいものへ更新している。例えば、カウンタテーブル５３に記憶された２次元アドレステーブル５２の先頭アドレスの数が"３"の場合、次の"４"が示す２次元アドレステーブル５２に現在のＩＸを追加する。また、カウンタテーブル５３に記憶されている値が"７"の場合、丸められて次の"０"が示す２次元アドレステーブル５２に現在のＩＸを追加する。リングバッファにより、一番古い０番地の値が新しい値に更新される。
【０１１０】
<<スライド探索結果符号化>>
メインフローである図１０のステップＳ９に続いて、スライド探索結果の符号化が行われる。
【０１１１】
図１２はスライド探索符号化の手順を示すフローチャート図の一例である。図１１の処理でスライド探索が有効か無効かを示すスライドＦＬＧに"１"又は"０"が設定されている。
【０１１２】
まず、スライドＦＬＧが"１"か否かを判断する（Ｓ１）。すなわち、現在のＩＸに対し、スライド探索でリストを見つけたか否かの判断を行う。
【０１１３】
リストが見つけられない場合（Ｓ１のＮｏ）、スライド範囲にデータＡで始まる２バイトと同じ２バイトがないので、データＡをＥＳＣ符号化する（Ｓ２）。
【０１１４】
そして、ＩＸを１つ大きくすることで、現在の位置を更新する（Ｓ３）。また、データＡにデータＢを設定することで、データＡを更新する（Ｓ４）。
【０１１５】
リストが見つかった場合（Ｓ１のＹｅｓ）、スライド範囲にデータＡで始まる２バイトと同じ２バイトがあるので、一致長さに２（２バイトの一致があったため）を設定する（Ｓ５）。
【０１１６】
次に、現在の位置を更新するため、ＩＸを２バイト大きくする（Ｓ６）。
【０１１７】
図１２の処理により、リストが見つからない場合は符号化できる。リストが見つかった場合はリスト探索に引き続き符号化される。また、現在の位置を示すＩＸを更新できる。
【０１１８】
<<リスト探索処理>>
図１３はリスト探索処理の手順を示すフローチャート図の一例である。リスト探索処理は、図８のリストＦＬＧ５４が有効である"１"の２次元アドレステーブル５２の先頭アドレスから３バイト目、４バイト目と順次比較して、一番長いリストを求める処理である。
【０１１９】
まず、リスト探索処理が成功したことを示すフラグであるLFINDFLGを初期化する（Ｓ１）。すなわち０を設定する。
【０１２０】
次に、変数ＩＷにゼロを設定する（Ｓ２）。ＩＷは、リストＦＬＧ５４の０〜７を示すポインタである。
【０１２１】
次に、ＩＷの示すリストＦＬＧ５４の値が有効（すなわち"１"）であるか否かを判断する（Ｓ３）。有効でない場合、処理はステップＳ１０に進む。つまり、探索処理は行わない。
【０１２２】
有効である場合、２次元アドレステーブル５２のインデックス値とＩＷで示す先頭アドレスを変数ＷＩＸに設定する（Ｓ４）。
【０１２３】
そして、このＷＩＸに一致長さを加えた値をラインメモリアドレスに設定する（Ｓ５）。一致長さは２バイトから始まり（図１２のＳ５）、一致する長さが続くと１バイトずつ増える。
【０１２４】
そして、ラインメモリアドレスで指定されるラインメモリ５５の１バイトのデータがデータＢと一致するか否かを判断する（Ｓ６）。データＢはＩＸと共に更新されるので、３バイト目が一致するかどうかが判断される。
【０１２５】
一致する場合、LFINDFLGに"１"を設定して一致したことを示す（Ｓ７）。そして、現在、着目している位置からの相対位置を変数ＡＤＤＲＥＳＳ記憶する（Ｓ８）。相対位置はＩＸ−ＷＩＸである。
【０１２６】
一致していない場合、２次元アドレステーブル５２の先頭アドレスを見ないようにＩＷを示すリストＦＬＧ５４の値を"０"に設定する（Ｓ９）。
【０１２７】
次に、ＩＷを１つ大きくする（Ｓ１０）。
【０１２８】
そして、ＩＷが２次元アドレステーブル５２に登録された先頭アドレスの数を超えていないかどうかを判断する（Ｓ１１）。
【０１２９】
ステップＳ１１の判断がＹｅｓの場合、処理はステップＳ３に戻り、２次元アドレステーブル５２の全ての先頭アドレスについて、リストＦＬＧが１である場合、３バイト目が一致するか否かが判断される。一致する長さが続く場合は、次回、図１３が実行されるごとに４バイト目、５バイト目…が一致するかどうかが判断される。
【０１３０】
<<リスト探索結果符号化>>
図１３の処理で一致する長さが続いている場合、LFINDFLGに"１"が設定されている。これを利用してリストを符号化する。
【０１３１】
図１４は、リスト探索結果符号化の手順を示すフローチャート図の一例である。
【０１３２】
まず、LFINDFLGが"１"か否かを判断する（Ｓ１）。
【０１３３】
LFINDFLGが"１"でない場合、一致する長さが続いていないので、符号化部４２ｃは今までの処理で得られた一致長さと一致位置を符号化する（Ｓ２）。一致位置は変数ＡＤＤＲＥＳＳに設定されている。
【０１３４】
そして、次のスライド探索を行うためスライドＦＬＧに"０"を設定する（Ｓ３）。
【０１３５】
LFINDFLGが"１"である場合、一致する長さが続いているので、符号化部４２ｃは符号化せずに一致長さを１バイト大きくする（Ｓ４）。
【０１３６】
＜処理の具体例＞
図１５は、スライド探索の具体例を示す図である。スライド探索処理は、現在の着目位置の２バイトのデータで２次元アドレステーブル５２のインデックス値を求め、２次元アドレステーブル５２の先頭アドレスに対し、現時点の位置から窓サイズにある先頭アドレスを有効にする処理である。
【０１３７】
図１５の例では窓サイズは１６バイトとする。現在、ラインメモリ上の２３,２４番目の"ab"を符号化している。リストＦＬＧ５４のサイズは４個であり、初期値としては全て"１"（有効）になっている。
【０１３８】
ラインメモリ上で今までに見つけた"ab"の先頭アドレスは４個あり、位置をバイト単位とする番号で言うと、先頭アドレスは２、８、１３、１７である。現在のラインメモリ上の位置は２３であるので、窓サイズが１６個であるとする７バイト目までしか窓サイズに含まれない。つまり２番のａｂは無効になるため、リストＦＬＧ５４の０番"０"（無効）となる。
【０１３９】
そして、２次元アドレステーブル５２の０番の列の先頭アドレスに２３（現在の位置）が設定され、リストＦＬＧ５４の０番目は"０"（無効）が設定される。
【０１４０】
図１６は、リスト探索の具体例を示す図である。リスト探索とはスライド探索処理で見つけたリストに対して、３バイト目、４バイト目のように順次、続くリストを探索する処理である。
【０１４１】
リストＦＬＧ５４は０番目＝０，１番目＝１，２番目＝１，３番目＝１なので、１から３番目の３つのリストの３バイト目がチェックされる。このうち、１番目と３番目のリストは３バイト目が"ｃ"なので、リストＦＬＧ５４は"１"のままである。２番目のリストは３バイト目が"ｃ"でないので、２番目のリストＦＬＧ５４は"０"（無効）となる。また、一致長さが続くリストがあるのでLFINDFLGは１であり、一致長さは４となる。
【０１４２】
次に、４バイト目がチェックされる。３バイト目のリスト探索処理で残った１，３番目のリストをチェックすると、１番目のリストの４バイト目は"ｄ"であるので、現在の位置から４バイト目の"ｄ"と一致している。しかし、３番目のリストの４バイト目は一致していないので、３番目のリストＦＬＧ５４は"０"（無効）となる。また、一致長さが続くリストがあるのでLFINDFLGは１であり、一致長さは５となる。
【０１４３】
次に、５バイト目がチェックされる。４バイト目のリスト探索処理で残った１番目のリストの５バイト目をチェックすると現在の位置から５バイト目（図では記載外）と一致していないので、全てのリストＦＬＧ５４が０となる。また、一致長さが続くリストがないのでLFINDFLGは０になる。
【０１４４】
以上の処理によると、最も長い一致長さは４であり、その先頭アドレスは８なので、一致長さ４，一致位置１５（＝２３−８）のようにＳｌｉｄｅ符号化される。着目している２バイトで始まる４バイトが２バイトという半分のサイズに圧縮できた。
【０１４５】
＜まとめ＞
以上説明したように、本実施形態のプリンタコントローラボード２０は、ハッシュ関数を使用しないので衝突が起きることがなく、符号化効率を向上させることができる。２バイトテーブルを有していれば符号化でき、２次元アドレステーブルもその全てが必要になることはほとんどない。仮に、バンド単位やページ単位で符号化する場合、２バイトテーブルでなく256×256の組合せの65536の大きさの２次元アドレステーブルやカウンタテーブル必要となる。本実施形態ではライン単位に符号化するので、メモリを圧迫しにくく高速な符号化が可能になる。
【０１４６】
また、２バイトハッシュ法のように連結リストではなく、２次元アドレステーブルはリングバッファとして構成されるのでリストの数が限定されている配列で構成できる。これによりライン単位の連結リストの生成とクリアの時間が不要であるので、ＣＰＵがソフトウェアを実行して畚固化する場合でも高速化を期待できる。
【０１４７】
＜その他の適用例＞
以上、本発明を実施するための最良の形態について実施例を用いて説明したが、本発明はこうした実施例に何等限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変形及び置換を加えることができる。
【０１４８】
なお、ラインメモリ５５はデータ記憶手段の一例であり、スライド探索部４２ａは記憶場所生成手段の一例であり、２バイトテーブル５１は２バイトテーブル記憶手段の一例であり、リスト探索部４２ｂはリスト探索手段の一例であり、符号化部４２ｃは符号化手段の一例である。
【符号の説明】
【０１４９】
２０        プリンタコントローラボード
４０        復号処理部
４２        List生成処理部
４２ａ      スライド探索部
４２ｂ      リスト探索部
４２ｃ      符号化部
２００      プリンタ
【先行技術文献】
【特許文献】
【０１５０】
【特許文献１】特許2713369号公報
【図１】
2018067781.tif 000003
【図２】
2018067781.tif 000004
【図３】
2018067781.tif 000005
【図４】
2018067781.tif 000006
【図５】
2018067781.tif 000007
【図６】
2018067781.tif 000008
【図７】
2018067781.tif 000009
【図８】
2018067781.tif 000010
【図９】
2018067781.tif 000011
【図１０】
2018067781.tif 000012
【図１１】
2018067781.tif 000013
【図１２】
2018067781.tif 000014
【図１３】
2018067781.tif 000015
【図１４】
2018067781.tif 000016
【図１５】
2018067781.tif 000017
【図１６】
2018067781.tif 000018
【図１７】
2018067781.tif 000019