(57)【特許請求の範囲】
【請求項１】
データを可逆符号化する方法であって、
（Ａ）入力データの連続した２バイトを調べ、前記２バイトの後端バイトと前記２バイトの直前の１バイトとが互いに等しく、かつ、前記２バイトの先頭バイトが所定の値以下であるとの符号化条件を満足するか否かを判定する工程と、
（Ｂ）前記符号化条件を満足する場合には前記２バイトを所定の符号化モードで符号化する工程と、
を備えることを特徴とするデータの可逆符号化方法。
【請求項２】
請求項１記載のデータの可逆符号化方法であって、
前記工程（Ｂ）は、
（Ｃ）前記２バイトを１６ビット未満の符号語で符号化する工程、を含む
データの可逆符号化方法。
【請求項３】
請求項２記載のデータの可逆符号化方法であって、
前記工程（Ｃ）は、
前記所定の符号化モードで符号化されたことを示す８ビット以下の接頭語と、前記先頭バイトの下位７ビットとを組み合わせることによって符号化データを作成する工程、を含む
データの可逆符号化方法。
【請求項４】
データを可逆符号化する方法であって、
（Ａ）入力データの連続した２バイトが、第１の符号化モードで符号化するための第１の符号化条件を満足するか否かを判定する工程と、
（Ｂ）前記第１の符号化条件が成立しない場合には、前記２バイトの後端バイトと前記２バイトの直前の１バイトとが互いに等しく、かつ、前記２バイトの先頭バイトが所定の値以下であるとの第２の符号化条件を満足するか否かを判定する工程と、
（Ｃ）前記第１の判定条件が成立する場合には少なくとも前記２バイトを圧縮率が最も高い前記第１の符号化モードで符号化し、前記第２の符号化条件が成立する場合には前記２バイトを圧縮率が中程度の第２の符号化モードで符号化し、前記第１と第２の符号化条件がいずれも成立しない場合には少なくとも前記先頭バイトを圧縮率が最も低い第３の符号化モードで符号化する工程と、
を備えることを特徴とするデータの可逆符号化方法。
【請求項５】
請求項４記載のデータの可逆符号化方法であって、
前記第２の符号化モードによる符号化工程は、
前記２バイトを１６ビット未満の符号語で符号化する工程、を含む
データの可逆符号化方法。
【請求項６】
請求項５記載のデータの可逆符号化方法であって、
前記第２の符号化モードによる符号化工程は、前記第２の符号化モードで符号化されたことを示す８ビット以下の接頭語と、前記先頭バイトの下位７ビットとを組み合わせることによって符号化データを作成する工程、を含む
データの可逆符号化方法。
【請求項７】
請求項４ないし６のいずれかに記載のデータの可逆符号化方法であって、
前記第１の符号化モードによる符号化工程は、
少なくとも前記２バイトを含む第１のバイト列と一致する最長の第２のバイト列を前記入力データ内で探索する工程と、
前記第１の符号化モードで符号化されたことを示す第１の符号語と、前記第１と第２のバイト列相互の距離を示す第２の符号語と、前記第１のバイト列の長さを示す第３の符号語とを組み合わせることによって符号化データを作成する工程と、を含む
データの可逆符号化方法。
【請求項８】
請求項４ないし７のいずれかに記載のデータの可逆符号化方法であって、
前記第３の符号化モードは、前記第３の符号化モードで符号化されたことを示す接頭語と、前記先頭バイトの下位７ビットとを組み合わせることによって符号化データを得る工程、を含み、
前記第３の符号化モードにおける前記接頭語は、前記先頭バイトの１６進数表記が７Ｆ以下である場合に使用される１ビットの第１の接頭語と、前記先頭バイトの１６進数表記が８０以上である場合に使用される複数ビットの第２の接頭語とのいずれか一方から選択される、データの可逆符号化方法。
【請求項９】
データの可逆符号化方法であって、
入力データ中において、１６進数表記が７Ｆ以下である第１のタイプのバイトデータの出現率が所定の条件を満足するか否かを判定し、
前記第１のタイプのバイトデータの出現率が所定の条件を満足する場合には、（Ａ）前記入力データ中の連続した２バイトが、圧縮率が１を超える符号化モードで符号化するための符号化条件を満足するか否かを判定する工程と、
（Ｂ）前記符号化条件が成立しない場合には、前記２バイトの少なくとも先頭バイトを、圧縮率が１以下の符号化モードで符号化する工程と、を実行することを特徴とするデータの可逆符号化方法。
【請求項１０】
請求項９記載のデータの可逆符号化方法であって、
前記工程（Ｂ）は、圧縮率が１以下の前記符号化モードで符号化されたことを示す接頭語と、前記先頭バイトの下位７ビットとを組み合わせることによって符号化データを得る工程と、を含み、
前記接頭語は、前記先頭バイトの１６進数表記が７Ｆ以下である場合に使用される１ビットの第１の接頭語と、前記先頭バイトの１６進数表記が８０以上である場合に使用される複数ビットの第２の接頭語とのいずれか一方から選択されるデータの可逆符号化方法。
【請求項１１】
データの可逆符号化装置であって、
入力データの連続した２バイトを調べ、前記２バイトの後端バイトと前記２バイトの直前の１バイトとが互いに等しく、かつ、前記２バイトの先頭バイトが所定の値以下であるとの符号化条件を満足するか否かを判定する判定手段と、
前記符号化条件を満足する場合には前記２バイトを所定の符号化モードで符号化する符号化手段と、
を備えることを特徴とするデータの可逆符号化装置。
【請求項１２】
請求項１１記載のデータの可逆符号化装置であって、
前記符号化手段は、
前記２バイトを１６ビット未満の符号語で符号化する第１の手段、を含む
データの可逆符号化装置。
【請求項１３】
請求項１２記載のデータの可逆符号化装置であって、
前記第１の手段は、
前記所定の符号化モードで符号化されたことを示す８ビット以下の接頭語と、前記先頭バイトの下位７ビットとを組み合わせることによって符号化データを作成する手段、を含む
データの可逆符号化装置。
【請求項１４】
データの可逆符号化装置であって、
入力データの連続した２バイトが、所定の第１の符号化モードで符号化するための第１の符号化条件を満足するか否かを判定する第１の判定手段と、
前記第１の符号化条件が成立しない場合には、前記２バイトの後端バイトと前記２バイトの直前の１バイトとが互いに等しく、かつ、前記２バイトの先頭バイトが所定の値以下であるとの第２の符号化条件を満足するか否かを判定する第２の手段と、
前記第１の判定条件が成立する場合には少なくとも前記２バイトを圧縮率が最も高い前記第１の符号化モードで符号化し、前記第２の符号化条件が成立する場合には前記２バイトを圧縮率が中程度の第２の符号化モードで符号化し、前記第１と第２の符号化条件がいずれも成立しない場合には少なくとも前記先頭バイトを圧縮率が最も低い第３の符号化モードで符号化する符号化手段と、
を備えることを特徴とするデータの可逆符号化装置。
【請求項１５】
請求項１４記載のデータの可逆符号化装置であって、
前記符号化手段は、
前記第２の符号化モードによる符号化において、前記２バイトを１６ビット未満の符号語で符号化する第１の手段、を含む
データの可逆符号化装置。
【請求項１６】
請求項１５記載のデータの可逆符号化装置であって、
前記第１の手段は、
前記第２の符号化モードで符号化されたことを示す８ビット以下の接頭語と、前記先頭バイトの下位７ビットとを組み合わせることによって符号化データを作成する手段、を含む
データの可逆符号化装置。
【請求項１７】
請求項１４ないし１６のいずれかに記載のデータの可逆符号化装置であって、
前記符号化手段は、
前記第１の符号化モードによる符号化において、少なくとも前記２バイトを含む第１のバイト列と一致する最長の第２のバイト列を前記入力データ内で探索する探索手段と、
前記第１の符号化モードで符号化されたことを示す第１の符号語と、前記第１と第２のバイト列相互の距離を示す第２の符号語と、前記第１のバイト列の長さを示す第３の符号語とを組み合わせることによって符号化データを作成する符号化データ生成手段と、を含む
データの可逆符号化装置。
【請求項１８】
請求項１４ないし１７のいずれかに記載のデータの可逆符号化装置であって、
前記符号化手段は、
前記第３の符号化モードによる符号化において、前記第３の符号化モードで符号化されたことを示す接頭語と、前記先頭バイトの下位７ビットとを組み合わせることによって符号化データを作成する手段と、
前記第３の符号化モードにおける前記接頭語として、前記先頭バイトの１６進数表記が７Ｆ以下である場合に使用される１ビットの第１の接頭語と、前記先頭バイトの１６進数表記が８０以上である場合に使用される複数ビットの第２の接頭語とのいずれか一方から選択する手段と、を含む
データの可逆符号化装置。
【請求項１９】
データの可逆符号化装置であって、
入力データ中において、１６進数表記が７Ｆ以下である第１のタイプのバイトデータの出現率が所定の条件を満足するか否かを判定する判定手段と、
前記第１のタイプのバイトデータの出現率が所定の条件を満足する場合において符号化を行なう符号化手段であって、
前記入力データ中の連続した２バイトが、圧縮率が１を超える符号化モードで符号化するための符号化条件を満足するか否かを判定する第１の手段と、
前記符号化条件が成立しない場合には、前記２バイトの少なくとも先頭バイトを、圧縮率が１以下の符号化モードで符号化する第２の手段と、を含む符号化手段と、
を備えることを特徴とするデータの可逆符号化装置。
【請求項２０】
請求項１９記載のデータの可逆符号化装置であって、
前記第２の手段は、
圧縮率が１以下の前記符号化モードで符号化されたことを示す接頭語と、前記先頭バイトの下位７ビットとを組み合わせることによって符号化データを生成する手段と、
前記接頭語として、前記先頭バイトの１６進数表記が７Ｆ以下である場合に使用される１ビットの第１の接頭語と、前記先頭バイトの１６進数表記が８０以上である場合に使用される複数ビットの第２の接頭語とのいずれか一方から選択する手段と、を含む
データの可逆符号化装置。
【請求項２１】
データの可逆符号化方法であって、
入力データ中において、連続した３バイトの両端のバイトデータが互いに一致する割合が所定の条件を満足するか否かを調べ、
前記一致する割合が所定の条件を満足する場合には、
（Ａ）前記入力データ中の連続した２バイトが、圧縮率が１を超える符号化モードで符号化するための符号化条件を満足するか否かを判定する工程と、
（Ｂ）前記符号化条件が成立しない場合には、前記２バイトの少なくとも先頭バイトを、圧縮率が１以下の符号化モードで符号化する工程と、を実行することを特徴とするデータの可逆符号化方法。
【請求項２２】
請求項９または２１に記載のデータの可逆符号化方法であって、
前記工程（Ｂ）は、
圧縮率が１以下の前記符号化モードで符号化されたことを示す接頭語と、前記先頭バイトの下位７ビットとを組み合わせることによって符号化データを得る工程と、を含み、
前記入力データにおいて１６進数表記が７Ｆ以下である第１のバイトデータ群の出現率と１６進数表記が８０以上である第２のバイトデータ群の出現率とを比較し、比較的出現率の高いバイトデータ群の各バイトデータの符号化においては１ビットの第１の接頭語を使用するとともに、比較的出現率の低いバイトデータ群の各バイトデータの符号化においては複数ビットの第２の接頭語を使用する、データの可逆符号化方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
この発明は、データを可逆符号化する方法および装置に関する。
【０００２】
【従来の技術】
近年では、コンピュータにおいて処理されるデータ量の急激な増大に対応するためにデータ圧縮技術が広く用いられるようになってきている。データ圧縮技術には、圧縮前のデータが元通りに復元される可逆符号化と、元通りに復元されない非可逆符号化とがある。非可逆符号化は、主として画像データの圧縮に用いられている。一方、可逆符号化は、プログラムデータ、テキストデータ、辞書データなどの種々のデータの圧縮に用いられている。
【０００３】
可逆符号化の対象となるデータの一種類としてフォントデータがある。フォントデータは、１セットのフォントに含まれる文字の形状を表わすデータである。近年では、パーソナルコンピュータに数種類のフォントデータがロードされ、ユーザが所望のフォントを選択して使用できるようになっている場合が多い。
【０００４】
【発明が解決しようとする課題】
ところが、フォントデータに対してテキストデータやプログラムデータと同じ可逆符号化方法で圧縮を行なうと、圧縮率があまり高くならない場合があった。これは、フォントデータがテキストデータやプログラムデータとは異なる特有のデータ配列を有しているためであると考えられる。
【０００５】
この発明は、従来技術における上述の課題を解決するためになされたものであり、フォントデータを効率的に圧縮することのできる可逆符号化方法および装置を提供することを目的とする。
【０００６】
【課題を解決するための手段および作用】
上述の課題を解決するため、この発明の請求項１に記載されたデータの可逆符号化方法は、（Ａ）入力データの連続した２バイトを調べ、前記２バイトの後端バイトと前記２バイトの直前の１バイトとが互いに等しく、かつ、前記２バイトの先頭バイトが所定の値以下であるとの符号化条件を満足するか否かを判定する工程と、（Ｂ）前記符号化条件を満足する場合には前記２バイトを所定の符号化モードで符号化する工程と、を備えることを特徴とする。
【０００７】
フォントデータでは、２バイトの後端バイトとその２バイトの直前の１バイトとが互いに等しく、かつ、その２バイトの先頭バイトが所定の値以下である場合が多い。そこで、このような符号化条件を満足する場合に、フォントデータに適した所定の符号化モードで符号化することによって、フォントデータを効率的に圧縮することができる。
【０００８】
請求項２に記載されたデータの可逆符号化方法では、前記工程（Ｂ）は、（Ｃ）前記２バイトを１６ビット未満の符号語で符号化する工程、を含む。
【０００９】
こうすれば、圧縮率を１以上にすることができる。
【００１０】
請求項３に記載されたデータの可逆符号化方法では、前記工程（Ｃ）は、前記所定の符号化モードで符号化されたことを示す８ビット以下の接頭語と、前記先頭バイトの下位７ビットとを組み合わせることによって符号化データを作成する工程、を含む。
【００１１】
こうすれば、１５ビット以下で２バイトを符号化することができる。
【００１２】
請求項４に記載されたデータの可逆符号化方法は、（Ａ）入力データの連続した２バイトが、所定の第１の符号化モードで符号化するための第１の符号化条件を満足するか否かを判定する工程と、（Ｂ）前記第１の符号化条件が成立しない場合には、前記２バイトの後端バイトと前記２バイトの直前の１バイトとが互いに等しく、かつ、前記２バイトの先頭バイトが所定の値以下であるとの第２の符号化条件を満足するか否かを判定する工程と、（Ｃ）前記第１の判定条件が成立する場合には少なくとも前記２バイトを圧縮率が最も高い前記第１の符号化モードで符号化し、前記第２の符号化条件が成立する場合には前記２バイトを圧縮率が中程度の第２の符号化モードで符号化し、前記第１と第２の符号化条件がいずれも成立しない場合には少なくとも前記先頭バイトを圧縮率が最も低い第３の符号化モードで符号化する工程とを備えることを特徴とする。
【００１３】
符号化条件で符号化モードを選択するようにすれば、２バイトのデータの内容に応じた適切な符号化モードを選択することができる。特にその２バイトがフォントデータに特有の第２の符号化条件を満足する場合には、フォントデータに適した第２の符号化モードで符号化することによって、フォントデータを効率的に圧縮することができる。
【００１４】
請求項７に記載したデータの可逆符号化方法では、前記第１の符号化モードによる符号化工程は、少なくとも前記２バイトを含む第１のバイト列と一致する最長の第２のバイト列を前記入力データ内で探索する工程と、前記第１の符号化モードで符号化されたことを示す第１の符号語と、前記第１と第２のバイト列相互の距離を示す第２の符号語と、前記第１のバイト列の長さを示す第３の符号語とを組み合わせることによって符号化データを作成する工程と、を含む。
【００１５】
第１の符号化モードでは、一致する最長バイト列を符号化するので、圧縮率を高くすることができる。
【００１６】
請求項８に記載のデータの可逆符号化方法では、前記第３の符号化モードは、前記第３の符号化モードで符号化されたことを示す接頭語と、前記先頭バイトの下位７ビットとを組み合わせることによって符号化データを得る工程、を含み、前記第３の符号化モードにおける前記接頭語は、前記先頭バイトの１６進数表記が７Ｆ以下である場合に使用される１ビットの第１の接頭語と、前記先頭バイトの１６進数表記が８０以上である場合に使用される複数ビットの第２の接頭語とのいずれか一方から選択される。
【００１７】
前記第３の符号化モードでは、２バイト中の先頭バイトの１６進数表記が７Ｆ以下の場合に８ビットで符号化するので、圧縮率が過度に低くならない。
【００１８】
請求項９に記載されたデータの可逆符号化方法は、入力データ中において、１６進数表記が７Ｆ以下である第１のタイプのバイトデータの出現率が所定の条件を満足するか否かを判定し、前記第１のタイプのバイトデータの出現率が所定の条件を満足する場合には、（Ａ）前記入力データ中の連続した２バイトが、圧縮率が１を超える符号化モードで符号化するための符号化条件を満足するか否かを判定する工程と、（Ｂ）前記符号化条件が成立しない場合には、前記２バイトの少なくとも先頭バイトを、圧縮率が１以下の符号化モードで符号化する工程と、を実行することを特徴とする。
【００１９】
１６進数表記が７Ｆ以下のバイトデータの出現率が所定の条件を満たす場合に工程（Ａ），（Ｂ）を含む符号化を実行するようにすれば、７Ｆ以下のバイトデータを符号化する場合の圧縮率が過度に低くならないように符号語を設定することが可能である。
【００２０】
請求項１０に記載されたデータの可逆符号化方法では、前記工程（Ｂ）は、圧縮率が１以下の前記符号化モードで符号化されたことを示す接頭語と、前記先頭バイトの下位７ビットとを組み合わせることによって符号化データを得る工程と、を含み、前記接頭語は、前記先頭バイトの１６進数表記が７Ｆ以下である場合に使用される１ビットの第１の接頭語と、前記先頭バイトの１６進数表記が８０以上である場合に使用される複数ビットの第２の接頭語とのいずれか一方から選択される。
【００２１】
７Ｆ以下のバイトデータは８ビットで符号化できるので、符号化時の圧縮率が過度に低くなることがない。
【００２２】
請求項１１に記載されたデータの可逆符号化装置は、入力データの連続した２バイトを調べ、前記２バイトの後端バイトと前記２バイトの直前の１バイトとが互いに等しく、かつ、前記２バイトの先頭バイトが所定の値以下であるとの符号化条件を満足するか否かを判定する判定手段と、前記符号化条件を満足する場合には前記２バイトを所定の符号化モードで符号化する符号化手段と、を備えることを特徴とする。
【００２３】
また、請求項１４に記載されたデータの可逆符号化装置は、入力データの連続した２バイトが、所定の第１の符号化モードで符号化するための第１の符号化条件を満足するか否かを判定する第１の判定手段と、前記第１の符号化条件が成立しない場合には、前記２バイトの後端バイトと前記２バイトの直前の１バイトとが互いに等しく、かつ、前記２バイトの先頭バイトが所定の値以下であるとの第２の符号化条件を満足するか否かを判定する第２の手段と、前記第１の判定条件が成立する場合には少なくとも前記２バイトを前記第１の符号化モードで符号化し、前記第２の符号化条件が成立する場合には前記２バイトを第２の符号化モードで符号化し、前記第１と第２の符号化条件がいずれも成立しない場合には少なくとも前記先頭バイトを第３の符号化モードで符号化する符号化手段と、を備えることを特徴とする。
【００２４】
請求項１９に記載されたデータの可逆符号化装置は、入力データ中において、１６進数表記が７Ｆ以下である第１のタイプのバイトデータの出現率が所定の条件を満足するか否かを判定する判定手段と、前記第１のタイプのバイトデータの出現率が所定の条件を満足する場合において符号化を行なう符号化手段であって、前記入力データ中の連続した２バイトが、圧縮率が１を超える符号化モードで符号化するための符号化条件を満足するか否かを判定する第１の手段と、前記符号化条件が成立しない場合には、前記２バイトの少なくとも先頭バイトを、圧縮率が１以下の符号化モードで符号化する第２の手段と、を含む符号化手段と、を備えることを特徴とする。
【００２５】
請求項２１に記載したデータの可逆符号化方法は、入力データ中において、連続した３バイトの両端のバイトデータが互いに一致する割合が所定の条件を満足するか否かを調べ、前記一致する割合が所定の条件を満足する場合には、（Ａ）前記入力データ中の連続した２バイトが、圧縮率が１を超える符号化モードで符号化するための符号化条件を満足するか否かを判定する工程と、（Ｂ）前記符号化条件が成立しない場合には、前記２バイトの少なくとも先頭バイトを、圧縮率が１以下の符号化モードで符号化する工程と、を実行することを特徴とする。
【００２６】
フォントデータでは、３バイトの両端のバイトデータが一致する割合が高いので、この一致割合が所定の条件を満たす場合に工程（Ａ），（Ｂ）を含む符号化を実行するようにすれば、フォントデータに適した符号化を行なうことが可能である。
【００２７】
請求項２２に記載した方法では、前記工程（Ｂ）は、圧縮率が１以下の前記符号化モードで符号化されたことを示す接頭語と、前記先頭バイトの下位７ビットとを組み合わせることによって符号化データを得る工程と、を含み、前記入力データにおいて１６進数表記が７Ｆ以下である第１のバイトデータ群の出現率と１６進数表記が８０以上である第２のバイトデータ群の出現率とを比較し、比較的出現率の高いバイトデータ群の各バイトデータの符号化においては１ビットの第１の接頭語を使用するとともに、比較的出現率の低いバイトデータ群の各バイトデータの符号化においては複数ビットの第２の接頭語を使用する。
【００２８】
７Ｆ以下のバイトデータ群と８０以上のバイトデータ群のうちで、比較的出現率の高いバイトデータ群の各バイトデータが８ビットで符号化できるので、符号化時の圧縮率が過度に低くなることがない。
【００２９】
【実施例】
Ａ．装置の構成：
図１は、この発明の一実施例を適用する情報処理装置のハードウェア構成を示すブロック図である。この情報処理装置は、パーソナルコンピュータシステムとして構成されたものであり、図示するように、ＣＰＵ１０１を中心にバスにより相互に接続された次の各部を備えている。
【００３０】
ＲＯＭ１０４：モニタプログラム等を記憶する読み出し専用メモリ
ＲＡＭ１０５：主記憶を構成する読み出し・書き込み可能なメモリ
ＰＩＣ１１２：各種の割込に優先順位を付けて制御する割込コントローラ
マウスインタフェース１１５：２ボタンマウス１１４とのデータ等のやり取りを司るインタフェース
キーボードインタフェース１１８：キーボード１１７からのキー入力を司るインタフェース
ＦＤＣ１２１：フレキシブルディスクドライブ（ＦＤＤ）１２０を制御するフレキシブルディスクコントローラ
ＨＤＣ１２５：ハードディスクドライブ（ＨＤＤ）１２４を制御するハードディスクコントローラ
ＣＲＴＣ１２９：必要なデータ等を表示するＣＲＴ１２８への信号出力を制御するＣＲＴコントローラ
プリンタインタフェース１３１：プリンタ１３０へのデータの出力を制御するインタフェース。
【００３１】
図２は、可逆符号化によるデータの圧縮と伸長とを行なう圧縮伸長用デバイスドライバ２００の構成を示す機能ブロック図である。この圧縮伸長用デバイスドライバ２００は、ＲＡＭ１０５に格納されたプログラムをＣＰＵ１０１が実行することによって実現されている。
【００３２】
圧縮伸長用デバイスドライバ２００は、圧縮対象となる１クラスタ分のデータを記憶するクラスタバッファ２０２と、可逆符号化によるデータの圧縮を行なう圧縮部２０４と、圧縮データを記憶する圧縮データバッファ２０６と、圧縮データをハードディスク１２３に書き込む書込制御部２０８とを備えている。なお、１クラスタは所定のデータサイズであり、例えば８Ｋバイトである。
【００３３】
圧縮部２０４は、後述する符号化タイプを判定する符号化タイプ判定部２１０と、ＬＺ（Ｌｅｍｐｅｌ−Ｚｉｖ）方式の符号化を行なうＬＺ符号化部２１２と、フォントタイプの符号化を行なうフォント符号化部２１４と、無圧縮タイプの符号化を行なう無圧縮符号化部２１６とを備えている。以下ではまず、ＬＺ符号化部２１２とフォント符号化部２１４と無圧縮符号化部２１６によって行なわれる３つのタイプの符号化について説明する。なお、この実施例においては、「符号化タイプ」と「符号化モード」は同じ意味である。
【００３４】
図３は、ＬＺタイプの符号化方法を示す説明図である。この実施例で使用するＬＺタイプの符号化はレンペル−ジフ（Ｌｅｍｐｅｌ−Ｚｉｖ）方式の符号化であり、特にスライド辞書法と呼ばれる符号化方法を使用している。図３（Ａ）に示す例では、被圧縮データがバイト列「７１ｈ  ３Ａｈ  ３Ｂｈ  …」を含んでいる。なお、この明細書において、付加記号「  ｈ」は１６進数表記であることを示している。
【００３５】
ＬＺタイプの符号化は、２バイト以上の連続したバイト列と同じバイト列が以前に出現しているか否かを調べ、以前に同じバイト列があれば、一致する最長のバイト列を調べる。そして、現在のバイト列から以前のバイト列までの距離（オフセット）と、一致した最長のバイト列のバイト数（一致長）とによって、現在のバイト列を符号化する。例えば図３（Ａ）の例では、実線の下線を付した２バイトのバイト列「３Ａｈ  ３Ｂｈ  」が、破線の下線を付した２バイトのバイト列と同じである。そこで、実線の下線を付した２バイトのバイト列「３Ａｈ  ３Ｂｈ  」の圧縮データは、ＬＺタイプの符号化データであることを示す接頭語と、一致したバイト列同士の距離を表わす符号語ＯＦＦＳＥＴ（３）と、一致長を表わす符号語ＬＥＮＧＴＨ（２）と、の３つの符号語の組み合わせによって表わされる。なお、ＯＦＦＳＥＴ（３）の括弧内の数値は距離を示すバイト数であり、ＬＥＮＧＴＨ（２）の括弧内の数値は一致長を示すバイト数である。各符号化タイプの圧縮データのフォーマットについては後述する。
【００３６】
図３（Ｂ）の例では、オフセットが３バイトで一致長が３バイトなので、接頭語と、符号語ＯＦＦＳＥＴ（３）と、符号語ＬＥＮＧＴＨ（３）の組み合わせによって実線の下線を付した３バイトのバイト列が符号化される。
【００３７】
図３（Ｃ）の例では、第２バイト以降の５バイトが同一である。この場合には、実線の下線を付した第３バイト以降の４バイトが、第２バイト以降の４バイトと一致することになる。従って、オフセットは１バイト、一致長は４バイトとなる。
【００３８】
以上のように、ＬＺタイプの符号化方法では、一致するバイト列が以前に存在している場合に、一致する最長のバイト列を符号化することによってデータを圧縮するので、同一のバイト列が繰り返し出現するようなデータを圧縮する場合に適している。
【００３９】
図４は、フォントタイプの符号化方法を示す説明図である。フォントデータでは、連続した３バイトの両端が互いに等しく、かつ、中央バイトが８０ｈ  未満（すなわち７Ｆ以下）である場合が多いという特徴がある。この特徴は、特にトゥルータイプ（ＴｒｕｅＴｙｐｅ）フォント（ＴｒｕｅＴｙｐｅはアップルコンピュータ社の商標）において顕著である。
【００４０】
図４において、先頭の１バイト「７１ｈ  」と下線を付した２バイト「３Ａｈ  ７１ｈ  」は、上述の特徴を有しているので、下線が付されている２バイトがフォントタイプの符号化によって圧縮される。フォントタイプの符号化の対象となる２バイト「３Ａｈ  ７１ｈ  」の直前の１バイト「７１ｈ  」は、無圧縮タイプの符号化で符号化されていても良く、また、ＬＺタイプの符号化によって符号化されていても良い。
【００４１】
フォントタイプの圧縮データは、フォントタイプであることを示す接頭語と、符号化の対象となる２バイト中の先頭バイト「３Ａｈ  」の下位７ビットとで構成される。なお、「３Ａｈ  」の下位７ビットのみを使用すれば良い理由は、フォントタイプの符号化が行なわれる場合に先頭バイトの１６進数表記が８０ｈ  未満であることが条件とされるので、先頭バイトの最上位ビット（ＭＳＢ）は常に０だからである。なお、フォントタイプであることを示す接頭語が付されている場合には、その直前に存在する１バイトと、フォントタイプで符号化された２バイト中の後端バイトが同一であることが解るので、後端バイトを示す情報は不要である。
【００４２】
この実施例におけるＬＺタイプの符号化では、２バイト以上の連続したバイト列が以前のバイト列と同一である場合に符号化される。また、フォントタイプの符号化でも、連続した２バイトが上記の所定の特徴を満足する場合に符号化される。従って、どの符号化タイプで符号化するかを判定する場合には、連続した２バイトを調べて３つの符号化タイプの１つを選択すればよい。
【００４３】
図５は、この実施例で用いられる各符号化タイプの圧縮データのフォーマットを示す説明図である。無圧縮タイプの符号化による圧縮データには、タイプ１（図５（Ａ））とタイプ２（図５（Ｂ））が存在する。無圧縮タイプ１は、圧縮前の最上位ビット（ＭＳＢ）が０であるバイトデータ（００ｈ  〜７Ｆｈ  ）の圧縮データである。また、無圧縮タイプ２は、圧縮前の最上位ビット（ＭＳＢ）が１であるバイトデータ（８０ｈ  〜ＦＦｈ  ）の圧縮データである。図５（Ａ），（Ｂ）に示すように、圧縮前のバイトデータの最上位ビットの値によって無圧縮タイプの圧縮データの接頭語を変えているので、接頭語の後ろに付加するデータは、圧縮前のデータの下位７ビットのみでよい。なお、無圧縮タイプ１の圧縮データでは、接頭語を含めた８ビットで圧縮前の１バイトが符号化されている。従って、無圧縮タイプ１の圧縮率は１．０である。無圧縮タイプ２の接頭語は４ビットなので、その圧縮率は約０．７である。
【００４４】
通常の符号化方法において、１バイトのデータを無圧縮で符号化した符号化データは、無圧縮を示す１ビット以上の接頭語と、元の８ビットとによって構成されている。従って、その符号化データは９ビット以上のビット数を有しており、圧縮率は１未満である。これに対して上述の無圧縮タイプ１の符号化では、圧縮率が１．０なので、圧縮率は通常の無圧縮の符号化データよりも高い。従って、８０ｈ  未満のバイトがある程度以上に含まれているデータに対してこの実施例の符号化方法を適用すれば、通常の符号化方法に比べて圧縮率を高めることが可能である。
【００４５】
ＬＺタイプの符号化による圧縮データにもタイプ１（図５（Ｃ））とタイプ２（図５（Ｄ））が存在する。ＬＺタイプ１はオフセットの値が２５５（１６進表記でＦＦｈ  ）以下の場合に使用される圧縮データであり、ＬＺタイプ２はオフセットの値が２５６（１６進数で１００ｈ  ）以上の場合に使用される圧縮データである。なお、ＬＺタイプ１とＬＺタイプ２では、接頭語が異なるだけでなく、オフセットを表わす符号語ＯＦＦＳＥＴも異なっている。例えば、ＬＺタイプ２のオフセットの符号語は８ビットで表わされているのに対して、ＬＺタイプ１のオフセットの符号語は９ビット以上の所定数のビットで表わされている。なお、ＬＺタイプ１，２の一致長の符号語ＬＥＮＧＴＨは、ハフマン符号化やワイル符号化などの符号化テーブルに従って符号化されている。
【００４６】
図５（Ｅ）に示すように、フォントタイプの圧縮データは、フォントタイプであることを示す接頭語「１１１０」と、先頭バイトの下位７ビットで構成されている。
【００４７】
図５に示す各符号化タイプは互いに接頭語が異なっており、また、接頭語は一意にかつ瞬時に復号可能な符号語である。従って、圧縮データを復号する際に、接頭語を調べるだけで瞬時に各符号化タイプを判定することができ、各符号化タイプに従って復号することが可能である。
【００４８】
図６は、符号化処理の手順を示すフローチャートである。ステップＳ１では、クラスタバッファ２０２に格納された被圧縮データの中から連続した２バイトが符号化タイプの判定対象として抽出される。２バイトを符号化タイプの判定対象とするのは、上述したように、ＬＺタイプとフォントタイプの符号化において、２バイト以上の連続したバイト列が符号化されるからである。
【００４９】
ステップＳ２では、ＬＺタイプの符号化条件を満足するか否かが判断される。ＬＺタイプの符号化条件Ｃ１は、次の通りである。
符号化条件Ｃ１：判定対象の２バイトと同一のバイト列が以前に存在する。
【００５０】
上記の条件Ｃ１が成立する場合には、ステップＳ４においてＬＺタイプの符号化が実行される。フォントタイプの符号化では、図３において説明したように、２バイト以上の連続したバイト列が符号化される。符号化条件Ｃ１が成立しない場合には、ステップＳ３においてフォントタイプの符号化条件を満足するか否かが判断される。フォントタイプの符号化条件Ｃ２は、次の通りである。
符号化条件Ｃ２：判定対象の２バイトの後端バイトが、対象２バイトの直前の１バイトと等しく、かつ、対象２バイトの先頭バイトが８０ｈ  未満である。
【００５１】
上記の符号化条件Ｃ２が成立する場合には、ステップＳ５においてフォントタイプの符号化が実行される。フォントタイプの符号化では２バイトが符号化される（図４）。符号化条件Ｃ２が成立しない場合には、ステップＳ６において、判定対象の２バイトの内の先頭バイトが無圧縮タイプで符号化される。無圧縮タイプの符号化では、１バイトが符号化されるだけである。
【００５２】
ステップＳ７では、クラスタバッファ２０２に格納された被圧縮データの全てが符号化されたか否かが判断され、終了していなければステップＳ１に戻る。なお、ステップＳ１〜Ｓ３，Ｓ７は符号化タイプ判定部２１０（図２）によって実行され、ステップＳ４，Ｓ５，およびＳ６はＬＺ符号化部２１２、フォント符号化部２１４、および無圧縮符号化部２１６によってそれぞれ実行される。
【００５３】
図６の手順は次のように言い換えることも可能である。すなわち、ＬＺタイプの符号化は、３つの符号化タイプの中で圧縮率が最も高いので、ＬＺタイプの符号化条件Ｃ１が成立する場合にはＬＺタイプの符号化が行なわれる。また、フォントタイプの符号化は、３つの符号化タイプの中で圧縮率が中程度なので、ＬＺタイプの符号化条件Ｃ１が成立しないが、フォントタイプの符号化条件Ｃ２が成立する場合にはフォントタイプの符号化が行なわれる。そして、無圧縮タイプの符号化は、圧縮率が最も低いので、ＬＺタイプとフォントタイプで符号化できない場合にのみ無圧縮タイプで符号化される。なお、ＬＺタイプとフォントタイプの符号化は圧縮率が１を超えるのに対して、無圧縮タイプの符号化は圧縮率が１以下である。
【００５４】
図７と図８は、実施例を適用して入力データを符号化する一例を示す説明図である。図７（Ａ）は被圧縮データのバイト列を示している。バイト列の最初の１バイトは、ＬＺタイプでもフォントタイプでも圧縮できないので、図７（Ｂ）に示すように無圧縮タイプで符号化される。第１バイト「８５ｈ  」は、８０ｈ  以上なので、無圧縮タイプ２で圧縮される。
【００５５】
第２，第３バイト「３Ａｈ  ８５ｈ  」は上述のフォントタイプの符号化条件Ｃ２を満足するので、図７（Ｃ）に示すようにフォントタイプで符号化される。
【００５６】
第４，第５バイト「３Ｂｈ  Ｅ０ｈ  」はＬＺタイプの符号化条件Ｃ１を満足せず、また、フォントタイプの符号化条件Ｃ２も満足しない。従って、図７（Ｄ）に示すように、第４バイト「３Ｂｈ  」のみが無圧縮タイプ１で符号化される。
【００５７】
第５，第６バイト「Ｅ０ｈ  ３Ｂｈ  」も２つの符号化条件Ｃ１，Ｃ２をいずれも満足しないので、図８（Ａ）に示すように、第５バイト「Ｅ０ｈ  」のみが無圧縮タイプ２で符号化される。また、第６，第７バイト「３Ｂｈ  ３Ａｈ  」も２つの符号化条件Ｃ１，Ｃ２をいずれも満足しないので、図８（Ｂ）に示すように、第６バイト「３Ｂｈ  」のみが無圧縮タイプ１で符号化される。
【００５８】
第７，第８バイト「３Ａｈ  ８５ｈ  」は第２，第３バイトと同じなので、ＬＺタイプで符号化される。ＬＺタイプの符号化では、一致する最長のバイト列さが調べられる。図８（Ｃ）の例では、一致する最長のバイト列は３バイトなので、第７〜第９バイトの３バイトがＬＺタイプで符号化される。なお、図８（Ｃ）の場合のオフセットは５バイトであり、２５５バイト以下なのでＬＺタイプ１の符号化が行なわれている。
【００５９】
第１０バイト「ＦＦｈ  」は、２つの符号化条件Ｃ１，Ｃ２をいずれも満足しないので、図８（Ｄ）に示すように、無圧縮タイプ２で符号化される。なお、被圧縮データの符号化が終了した場合には、図示しない所定の終了コードが圧縮データの終端に付加される。
【００６０】
上記実施例では、被圧縮データの連続した２バイトが判定条件Ｃ１またＣ２を満足するか否かに応じて符号化タイプを判別していたので、被圧縮データの局所的なデータ構造に応じて適切な符号化タイプを設定することができ、この結果、圧縮率を向上させることができるという利点がある。
【００６１】
なお、上記実施例では被圧縮データをフォントデータ用の可逆符号化方法で符号化する場合について説明したが、与えられた被圧縮データをフォントデータ用の可逆符号化方法で圧縮するか、他の可逆符号化方法で圧縮するかを事前に判定するようにすることも可能である。
【００６２】
例えば、フォントデータのファイル名の拡張子は、「ＴＴＦ」などの数種類に限定されていることが多い。そこで、データ圧縮を行なう際に被圧縮データファイルの拡張子を調べ、拡張子が「ＴＴＦ」などの予め登録された拡張子名と一致した場合には、上述のフォントデータの可逆符号化方法を適用するようしてもよい。
【００６３】
なお、上述の無圧縮タイプ１の符号化では符号化データが８ビットですむので、通常の符号化方法による場合よりも無圧縮タイプの符号化データの圧縮率が高いという利点がある。従って、８０ｈ  未満のバイトデータの出現率がある程度以上の入力データに対しては、上述の実施例によるフォントデータの符号化方法を適用すれば、通常の符号化方法に比べて符号化データの圧縮率を高めることが可能である。このような考え方に従ってフォントデータの符号化方法を適用すべきか否かを判断する方法としては種々のものが考えられる。例えば、被圧縮データの先頭から一定バイト数（すなわち、入力データの少なくとも一部）を調べ、８０ｈ  未満のバイト数が所定の値以上の場合にフォントデータの符号化方法を適用するようにしてもよい。また、被圧縮データを間引きしつつ一定バイト数を調べ、８０ｈ  未満のバイト数が所定の値以上の場合にフォントデータの符号化方法を適用するようにしてもよい。
【００６４】
なお、８０ｈ  以上のバイトデータが比較的多い場合には、８０ｈ  以上のデータのための接頭語を１ビット（例えば「０  」）とし、８０ｈ  未満のデータには２ビット以上の接頭語（例えば「１１１１」）を用いるようにしてもよい。換言すれば、入力データの少なくとも一部を調べて、１６進数表記が８０ｈ  未満のバイトデータと８０ｈ  以上のバイトデータの数（または出現率）を調べ、比較的出現率の高い方に１ビットの接頭語を使用し、比較的出現率の低い方２ビット以上の接頭語を使用するようにしてもよい。
【００６５】
なお、フォントデータでは連続した３バイトの両端のバイトが同一であるという特徴があるので、この特徴を利用して、１つおきの２バイトが一致する割合が一定以上であればフォントデータの符号化方法を適用するようにすることも可能である。この場合には、入力データの少なくとも一部について１つおきの２バイトが一致する割合を調べ、その結果に応じて、適用すべき符号化方法を選択すればよい。
【００６６】
なお、この発明は上記実施例に限られるものではなく、その要旨を逸脱しない範囲において種々の態様において実施することが可能であり、例えば次のような変形も可能である。
【００６７】
（１）図９は、図６の処理手順にステップＳ１０とＳ１１を付加したものである。ステップＳ１０において、ＬＺタイプで符号化する際のオフセットが２５６以上であり、かつ、一致長が２に等しい場合には、ステップＳ１１に移行し、符号化の対象となる２バイトがフォントタイプの判定条件Ｃ２を満足するか否かが判断される。フォントタイプの判定条件Ｃ２が成立する場合には、符号化対象の２バイトはフォントタイプで符号化され、そうでない場合にはＬＺタイプで符号化される。このようにするのは、ステップＳ１０，Ｓ１１の条件をいずれも満足する場合には、ＬＺタイプで符号化するよりもフォントタイプで符号化した方が符号化データの圧縮率が高くなるからである。
【００６８】
このように、ＬＺタイプの符号化判定条件Ｃ１を満足する２バイトのバイト列に対しても、フォントタイプで符号化した方が符号化データの圧縮率が高くなる場合には、フォントタイプで符号化するようにしてもよい。
【００６９】
（２）上記実施例におけるＬＺ方式の符号化方法の代わりに、ハフマン符号化や算術符号化などの種々の可逆符号化方法を使用することも可能である。
【００７０】
【発明の効果】
以上説明したように、請求項１および１１に記載された発明によれば、入力データが所定の符号化条件を満足する場合に、フォントデータに適した所定の符号化モードで符号化するので、フォントデータを効率的に圧縮することができるという効果がある。
【００７１】
請求項２、５、１２および１５に記載された発明によれば、圧縮率を１以上にすることができるという効果がある。
【００７２】
請求項３、６、１３および１６に記載された発明によれば、１５ビット以下で２バイトを符号化することができるという効果がある。
【００７３】
請求項４および１４に記載された発明によれば、２バイトのデータの内容に応じた適切な符号化モードを選択することができ、特に、その２バイトがフォントデータに特有の第２の符号化条件を満足する場合において効率的に圧縮することができるという効果がある。
【００７４】
請求項７および１７に記載された発明によれば、第１の符号化モードにおいて、一致する最長バイト列を符号化するので、圧縮率を高くすることができるという効果がある。
【００７５】
請求項８および１８に記載された発明によれば、第３の符号化モードにおいて、２バイト中の先頭バイトの１６進数表記が７Ｆ以下の場合に８ビットで符号化するので、圧縮率が過度に低くならないという効果がある。
【００７６】
請求項９および１９に記載された発明によれば、１６進数表記が７Ｆ以下のバイトデータの出現率が所定の条件を満たす場合に工程（Ａ），（Ｂ）を含む符号化を実行するので、７Ｆ以下のバイトデータを符号化する場合の圧縮率が過度に低くならないように符号語を設定することが可能であるという効果がある。
【００７７】
請求項１０およびに２０に記載された発明によれば、７Ｆ以下のバイトデータを８ビットで符号化できるので、符号化時の圧縮率が過度に低くなることがないという効果がある。
【００７８】
請求項２１に記載された発明によれば、３バイトの両端のバイトデータが一致する割合が所定の条件を満たす場合に工程（Ａ），（Ｂ）を含む符号化を実行するので、フォントデータに適した符号化を行なうことが可能であるという効果がある。
【００７９】
請求項２２に記載された発明によれば、７Ｆ以下のバイトデータ群と８０以上のバイトデータ群のうちで、比較的出現率の高いバイトデータ群の各バイトデータを８ビットで符号化できるので、符号化時の圧縮率が過度に低くなることがないという効果がある。
【図面の簡単な説明】
【図１】この発明の一実施例を適用する情報処理装置のハードウェア構成を示すブロック図。
【図２】可逆符号化によるデータの圧縮と伸長とを行なう圧縮伸長用デバイスドライバ２００の構成を示す機能ブロック図。
【図３】ＬＺタイプの符号化方法を示す説明図。
【図４】フォントタイプの符号化方法を示す説明図。
【図５】各符号化タイプの圧縮データのフォーマットを示す説明図。
【図６】符号化処理の手順を示すフローチャート。
【図７】実施例を適用して入力データを符号化する一例を示す説明図。
【図８】実施例を適用して入力データを符号化する一例を示す説明図。
【図９】符号化処理の手順の変形例を示すフローチャート。
【符号の説明】
１０１…ＣＰＵ
１０４…ＲＯＭ
１０５…ＲＡＭ
１１２…ＰＩＣ
１１５…マウスインタフェース
１１７…キーボード
１１８…キーボードインタフェース
１２１…ＦＤＣ
１２３…ハードディスク
１２４…ハードディスクドライブ
１２５…ＨＤＣ
１２８…ＣＲＴ
１２９…ＣＲＴＣ
１３０…プリンタ
１３１…プリンタインタフェース
２００…圧縮伸長用デバイスドライバ
２０２…クラスタバッファ
２０４…圧縮部
２０６…圧縮データバッファ
２０８…書込制御部
２１０…符号化タイプ判定部
２１２…ＬＺ符号化部
２１４…フォント符号化部
２１６…無圧縮符号化部
【図１】
0003603099.tif 000002
【図２】
0003603099.tif 000003
【図３】
0003603099.tif 000004
【図４】
0003603099.tif 000005
【図５】
0003603099.tif 000006
【図６】
0003603099.tif 000007
【図７】
0003603099.tif 000008
【図８】
0003603099.tif 000009
【図９】
0003603099.tif 000010