(57)【要約】【課題】ＬＺ７７符合に基づくデータ圧縮方法であって、圧縮率を改善でき、また、データ圧縮及び復元の処理に時間のかからないデータ圧縮方法等を提供する。【解決手段】符号済みの記号列の中に存在する、符号化対象の記号列に最大長一致する最長一致系列を検索し、当該最長一致系列の存在位置である一致位置と当該最長一致系列の長さである一致長さとに基づいて符号化を行いデータを圧縮するデータ圧縮方法であって、前記符号化によって生成される符号が、前記一致位置を表す符号の長さと前記一致長さを表す符号の長さとを表す符号と、前記一致位置を表す符号と、前記一致長さを表す符号と、から構成されることを特徴とする。【選択図】  図３
2005269184.tif 000002
【特許請求の範囲】
【請求項１】
符号化済みの記号列の中に存在する、符号化対象の記号列に最大長一致する最長一致系列を検索し、当該最長一致系列の存在位置である一致位置と当該最長一致系列の長さである一致長さとに基づいて符号化を行いデータを圧縮するデータ圧縮方法であって、
前記符号化によって生成される符号が、
前記一致位置を表す符号の長さと前記一致長さを表す符号の長さとを表す符号と、
前記一致位置を表す符号と、
前記一致長さを表す符号と、から構成される
ことを特徴とするデータ圧縮方法。
【請求項２】
請求項１において、
前記一致位置を表す符号が、前記一致位置を表す値を２進法で表現した場合の最上位の１を除いたものであり、
前記一致長さを表す符号が、前記一致長さを表す値を２進法で表現した場合の最上位の１を除いたものである
ことを特徴とするデータ圧縮方法。
【請求項３】
符号化済みの記号列の中に存在する、符号化対象の記号列に最大長一致する最長一致系列を検索し、当該最長一致系列の存在位置である一致位置と当該最長一致系列の長さである一致長さとに基づいて符号化を行いデータを圧縮するデータ圧縮方法であって、
前記最長一致系列の長さが、所定の値よりも小さい場合には、当該所定の値よりも小さい旨と元の記号を表す、所定長さの第一識別情報により前記符号化を行い、
前記最長一致系列の長さが、前記所定の値以上の場合には、当該所定の値以上である旨と前記一致位置を表す一致位置情報の長さと前記一致長さを表す一致長さ情報の長さとを表す、前記第一識別情報と同じ長さの第二識別情報と、前記一致位置情報と、前記一致長さ情報と、により前記符号化を行なう
ことを特徴とするデータ圧縮方法。
【請求項４】
請求項３において、
前記一致位置情報が、前記一致位置を表す値を２進法で表現した場合の最上位の１を除いたものであり、
前記一致長さ情報が、前記一致長さを表す値を２進法で表現した場合の最上位の１を除いたものである
ことを特徴とするデータ圧縮方法。
【請求項５】
請求項３あるいは請求項４において、
前記第一識別情報及び又は第二識別情報がハフマン符号化される
ことを特徴とするデータ圧縮方法。
【請求項６】
符号化済みの記号列の中に存在する、符号化対象の記号列に最大長一致する最長一致系列を検索し、当該最長一致系列の存在位置である一致位置と当該最長一致系列の長さである一致長さとに基づいて符号化を行いデータを圧縮する処理をコンピュータに実行させるデータ圧縮プログラムであって、
前記最長一致系列の長さが、所定の値以上であるか否かを判定する第一ステップと、
前記第一ステップにおいて、前記最長一致系列の長さが前記所定の値以上でないと判定された場合には、当該所定の値以上でない旨と元の記号を表す、所定長さの第一識別情報により前記符号化を行う第二ステップと、
前記第一ステップにおいて、前記最長一致系列の長さが前記所定の値以上であるなと判定された場合には、当該所定の値以上である旨と前記一致位置を表す一致位置情報の長さと前記一致長さを表す一致長さ情報の長さとを表す、前記第一識別情報と同じ長さの第二識別情報と、前記一致位置情報と、前記一致長さ情報と、により前記符号化を行う第三ステップとを、前記コンピュータに実行させる
ことを特徴とするデータ圧縮プログラム。
【請求項７】
符号化済みの記号列の中に存在する、符号化対象の記号列に最大長一致する最長一致系列を検索し、当該最長一致系列の存在位置である一致位置と当該最長一致系列の長さである一致長さとに基づいて符号化されたデータを復元するデータ復元方法であって、
前記復元対象のデータが、
前記最長一致系列の長さが、所定の値よりも小さい場合には、当該所定の値よりも小さい旨と元の記号を表す、所定長さの第一識別情報により符号化され、
前記最長一致系列の長さが、前記所定の値以上の場合には、当該所定の値以上である旨と前記一致位置を表す一致位置情報の長さと前記一致長さを表す一致長さ情報の長さとを表す、前記第一識別情報と同じ長さの第二識別情報と、前記一致位置情報と、前記一致長さ情報と、により符号化されている場合に、
前記第一識別情報あるいは第二識別情報の長さである前記所定長さ分の符号を解釈し、当該符号が第一識別情報であるかあるいは第二識別情報であるかを判断する第一ステップと、
前記第一ステップにおいて、第一識別情報であると判断された場合には、当該第一識別情報に含まれる前記元の記号に復号する第二ステップと、
前記第一ステップにおいて、第二識別情報であると判断された場合には、当該第二識別情報に基づいて前記一致位置情報と一致長さ情報の長さを求める第三ステップと、
前記第二識別情報に続く、前記第三ステップで求められた前記一致位置情報の長さ分の符号から、前記一致位置を求める第四ステップと、
前記一致位置情報に続く、前記第三ステップで求められた前記一致長さ情報の長さ分の符号から、前記一致長さを求める第五ステップと、
前記第四及び第五ステップで求められた一致位置と一致長さに基づいて、復号済みの記号列を用いて復号する第六ステップとを有する
ことを特徴とするデータ復元方法。
【請求項８】
符号化済みの記号列の中に存在する、符号化対象の記号列に最大長一致する最長一致系列を検索し、当該最長一致系列の存在位置である一致位置と当該最長一致系列の長さである一致長さとに基づいて符号化されたデータを復元するデータ復元装置であって、
復号済みの記号列を格納する記号列格納手段と、
前記復元対象のデータが、
前記最長一致系列の長さが、所定の値よりも小さい場合には、当該所定の値よりも小さい旨と元の記号を表す、所定長さの第一識別情報により符号化され、
前記最長一致系列の長さが、前記所定の値以上の場合には、当該所定の値以上である旨と前記一致位置を表す一致位置情報の長さと前記一致長さを表す一致長さ情報の長さとを表す、前記第一識別情報と同じ長さの第二識別情報と、前記一致位置情報と、前記一致長さ情報と、により符号化されている場合に、
前記第一識別情報あるいは第二識別情報の長さである前記所定長さ分の符号により、当該符号が第一識別情報であるかあるいは第二識別情報であるかを判断し、
第一識別情報であると判断された場合には、当該第一識別情報に含まれる前記元の記号に復号し、
第二識別情報であると判断された場合には、当該第二識別情報に基づいて前記一致位置情報と一致長さ情報の長さを求め、当該第二識別情報に続く、前記求められた一致位置情報の長さ分の符号と前記求められた一致長さ情報の長さ分の符号から、前記一致位置と前記一致長さを求め、前記求められた一致位置と一致長さに基づいて、前記記号列格納手段に格納された記号列を用いて復号する、復号手段とを備える
ことを特徴とするデータ復元装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化済みの記号列との一致に基づいて符号化することにより、データを圧縮する方法等に関し、特に、データ圧縮率を向上させることができ、データ圧縮及び復元の処理に時間のかからないデータ圧縮方法等に関する。
【背景技術】
【０００２】
近年、情報処理技術の発達やインターネット等のネットワークの普及により、膨大なデータが処理されると共に通信されるようになってきている。例えば、ホストコンピュータからネットワークを介してプリンタに印刷を実行させるということが一般によく行われ、また、プリンタの処理速度も随時向上してきているが、ホストコンピュータからプリンタに送信する印刷データの容量が大きい場合にはその通信に時間がかかってしまい、プリンタの処理速度を十分に生かすことができないという事態も発生する。従って、データを如何に圧縮して送信し、受信後、如何に復元するかというデータの圧縮及び復元技術が必要となってくる。
【０００３】
かかるデータの圧縮及び復元技術としては、従来から、その目的や対象データにより幾つかのものが提案されている。その一つとして、ＬＺ７７（Ｚｉｖ  ａｎｄ  Ｌｅｍｐｅｌ（１９７７））符号を用いた方法がある。かかる手法では、現在符号化を行なっている記号（データ）の前後の記号列をバッファに保存し、このバッファを辞書として参照して、符号化しようとしている記号列と一致する、最長の記号列を当該辞書内で探索する。そして、探索された記号列の長さと位置の情報により対象の記号列を符号化する。
【０００４】
このＬＺ７７方式にも様々なバリエーションが開発されており、例えば、下記非特許文献１に記載されたＬＺＳＳ符号を用いた方法は現在頻繁に用いられている。かかる方法は、前記一致する最長記号列の長さが所定の値より小さい場合には、元の記号をそのまま符号とし、即ち、上述の一致記号列の長さと位置による符号化は行なわず、一致する最長記号列の長さが所定の値より大きい場合には、上述の一致記号列の長さと位置による符号化を行なう。そして、両者を区別するためのフラグを符号の先頭に付加する。
【０００５】
また、このようなＬＺ７７方式のデータ圧縮方法について、圧縮率の向上などの目的により幾つかの提案がなされている（例えば、下記特許文献１及び２）。
【特許文献１】特開平５−１１９７３号公報
【特許文献２】特開平７−２６１９７７号公報
【非特許文献１】植松友彦著、「文書データ圧縮アルゴリズム入門」、第２版、ＣＱ出版、１９９５年６月、ｐ．１４５−１４８
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述したＬＺＳＳ符号では、前記一致する最長記号列の位置（以下、一致位置と呼ぶ）と長さ（以下、一致長さと呼ぶ）を固定長さの符号（ビット列）で表現しているので、データの圧縮率があまりよくないという課題があった。
【０００７】
また、上記特許文献１には、辞書内の一致する記号列に出現番号なるものを付けて、この出現番号を上記一致位置として出力することにより、データ圧縮率の向上を図ろうとする方法が記載されているが、かかる方法では、圧縮されたデータの復号の際にも、一致する記号列の出現位置を検索によって求める必要があり、復元の処理に時間がかかってしまうという問題があった。
【０００８】
また、上記特許文献２には、上記一致位置と一致長さを、スプレイ木により動的に変化する符号で表現し、圧縮率の向上を図る技術が示されているが、符号を動的に変更するため、圧縮、復元共に処理が複雑であり、それらの処理に時間がかかるという課題があった。
【０００９】
そこで、本発明の目的は、ＬＺ７７符合に基づくデータ圧縮方法であって、圧縮率を改善でき、また、データ圧縮及び復元の処理に時間のかからないデータ圧縮方法等を提供することである。
【課題を解決するための手段】
【００１０】
上記の目的を達成するために、本発明の一つの側面は、符号化済みの記号列の中に存在する、符号化対象の記号列に最大長一致する最長一致系列を検索し、当該最長一致系列の存在位置である一致位置と当該最長一致系列の長さである一致長さとに基づいて符号化を行いデータを圧縮するデータ圧縮方法であって、前記符号化によって生成される符号が、前記一致位置を表す符号の長さと前記一致長さを表す符号の長さとを表す符号と、前記一致位置を表す符号と、前記一致長さを表す符号と、から構成されることを特徴とする。従って、本発明によれば、一致位置を表す符号と一致長さを表す符号の長さを必要最低限の長さとすることができ、データ圧縮率の向上を図ることができる。
【００１１】
更に、上記の発明において、その好ましい態様は、前記一致位置を表す符号が、前記一致位置を表す値を２進法で表現した場合の最上位の１を除いたものであり、前記一致長さを表す符号が、前記一致長さを表す値を２進法で表現した場合の最上位の１を除いたものであることを特徴とする。これにより、データ圧縮率を高めることができる。
【００１２】
上記の目的を達成するために、本発明の別の側面は、符号化済みの記号列の中に存在する、符号化対象の記号列に最大長一致する最長一致系列を検索し、当該最長一致系列の存在位置である一致位置と当該最長一致系列の長さである一致長さとに基づいて符号化を行いデータを圧縮するデータ圧縮方法であって、前記最長一致系列の長さが、所定の値よりも小さい場合には、当該所定の値よりも小さい旨と元の記号を表す、所定長さの第一識別情報により前記符号化を行い、前記最長一致系列の長さが、前記所定の値以上の場合には、当該所定の値以上である旨と前記一致位置を表す一致位置情報の長さと前記一致長さを表す一致長さ情報の長さとを表す、前記第一識別情報と同じ長さの第二識別情報と、前記一致位置情報と、前記一致長さ情報と、により前記符号化を行なうことを特徴とする。従って、本発明によれば、復元が容易であり、かつ、圧縮率の高いデータ圧縮を可能とする。
【００１３】
更に、上記の発明において、その好ましい態様は、前記一致位置情報が、前記一致位置を表す値を２進法で表現した場合の最上位の１を除いたものであり、前記一致長さ情報が、前記一致長さを表す値を２進法で表現した場合の最上位の１を除いたものであることを特徴とする。
【００１４】
更に、上記の発明において、好ましい態様は、前記第一識別情報及び又は第二識別情報がハフマン符号化されることを特徴とする。これにより、さらにデータ圧縮率を高めることが可能となる。
【００１５】
上記の目的を達成するために、本発明の別の側面は、符号化済みの記号列の中に存在する、符号化対象の記号列に最大長一致する最長一致系列を検索し、当該最長一致系列の存在位置である一致位置と当該最長一致系列の長さである一致長さとに基づいて符号化を行いデータを圧縮する処理をコンピュータに実行させるデータ圧縮プログラムが、前記最長一致系列の長さが、所定の値以上であるか否かを判定する第一ステップと、前記第一ステップにおいて、前記最長一致系列の長さが前記所定の値以上でないと判定された場合には、当該所定の値以上でない旨と元の記号を表す、所定長さの第一識別情報により前記符号化を行う第二ステップと、前記第一ステップにおいて、前記最長一致系列の長さが前記所定の値以上であるなと判定された場合には、当該所定の値以上である旨と前記一致位置を表す一致位置情報の長さと前記一致長さを表す一致長さ情報の長さとを表す、前記第一識別情報と同じ長さの第二識別情報と、前記一致位置情報と、前記一致長さ情報と、により前記符号化を行う第三ステップとを、前記コンピュータに実行させることである。
【００１６】
上記の目的を達成するために、本発明の別の側面は、符号化済みの記号列の中に存在する、符号化対象の記号列に最大長一致する最長一致系列を検索し、当該最長一致系列の存在位置である一致位置と当該最長一致系列の長さである一致長さとに基づいて符号化されたデータを復元するデータ復元方法であって、前記復元対象のデータが、前記最長一致系列の長さが、所定の値よりも小さい場合には、当該所定の値よりも小さい旨と元の記号を表す、所定長さの第一識別情報により符号化され、前記最長一致系列の長さが、前記所定の値以上の場合には、当該所定の値以上である旨と前記一致位置を表す一致位置情報の長さと前記一致長さを表す一致長さ情報の長さとを表す、前記第一識別情報と同じ長さの第二識別情報と、前記一致位置情報と、前記一致長さ情報と、により符号化されている場合に、前記第一識別情報あるいは第二識別情報の長さである前記所定長さ分の符号を解釈し、当該符号が第一識別情報であるかあるいは第二識別情報であるかを判断する第一ステップと、前記第一ステップにおいて、第一識別情報であると判断された場合には、当該第一識別情報に含まれる前記元の記号に復号する第二ステップと、前記第一ステップにおいて、第二識別情報であると判断された場合には、当該第二識別情報に基づいて前記一致位置情報と一致長さ情報の長さを求める第三ステップと、前記第二識別情報に続く、前記第三ステップで求められた前記一致位置情報の長さ分の符号から、前記一致位置を求める第四ステップと、前記一致位置情報に続く、前記第三ステップで求められた前記一致長さ情報の長さ分の符号から、前記一致長さを求める第五ステップと、前記第四及び第五ステップで求められた一致位置と一致長さに基づいて、復号済みの記号列を用いて復号する第六ステップとを有することを特徴とする。従って、本発明によれば、上述のように符号化されたデータを、容易に復元することが可能となる。
【００１７】
上記の目的を達成するために、本発明の別の側面は、符号化済みの記号列の中に存在する、符号化対象の記号列に最大長一致する最長一致系列を検索し、当該最長一致系列の存在位置である一致位置と当該最長一致系列の長さである一致長さとに基づいて符号化されたデータを復元するデータ復元装置が、復号済みの記号列を格納する記号列格納手段と、前記復元対象のデータが、前記最長一致系列の長さが、所定の値よりも小さい場合には、当該所定の値よりも小さい旨と元の記号を表す、所定長さの第一識別情報により符号化され、前記最長一致系列の長さが、前記所定の値以上の場合には、当該所定の値以上である旨と前記一致位置を表す一致位置情報の長さと前記一致長さを表す一致長さ情報の長さとを表す、前記第一識別情報と同じ長さの第二識別情報と、前記一致位置情報と、前記一致長さ情報と、により符号化されている場合に、前記第一識別情報あるいは第二識別情報の長さである前記所定長さ分の符号により、当該符号が第一識別情報であるかあるいは第二識別情報であるかを判断し、第一識別情報であると判断された場合には、当該第一識別情報に含まれる前記元の記号に復号し、第二識別情報であると判断された場合には、当該第二識別情報に基づいて前記一致位置情報と一致長さ情報の長さを求め、当該第二識別情報に続く、前記求められた一致位置情報の長さ分の符号と前記求められた一致長さ情報の長さ分の符号から、前記一致位置と前記一致長さを求め、前記求められた一致位置と一致長さに基づいて、前記記号列格納手段に格納された記号列を用いて復号する、復号手段とを備えることである。
【００１８】
本発明の更なる目的及び、特徴は、以下に説明する発明の実施の形態から明らかになる。
【発明を実施するための最良の形態】
【００１９】
以下、図面を参照して本発明の実施の形態例を説明する。しかしながら、かかる実施の形態例が、本発明の技術的範囲を限定するものではない。なお、図において、同一又は類似のものには同一の参照番号又は参照記号を付して説明する。
【００２０】
図１は、本発明を適用したデータ圧縮装置の実施の形態例に係る構成図である。また、図２は、本発明を適用したデータ復元装置の実施の形態例に係る構成図である。図１及び図２に示すデータ圧縮装置１及びデータ復元装置２が、本発明に係るデータ圧縮方法及び復元方法を用いた装置である。本データ圧縮装置１のデータ圧縮方法は、ＬＺ７７符号の考え方を基本としているが、符号化に用いる前記一致位置と一致長さを固定長さの符号（ビット列）で表現せず、一致位置と一致長さを表現する符号の長さ（ビット数）の情報を、それらの符号の前に付けて符号化を行うと共に、一致位置と一致長さを表現する符号の長さを極力短くすることにより、データの圧縮率を改善しようとするものである。また、本データ復元装置２のデータ復元方法は、上記圧縮時に付加された、一致位置と一致長さを表現する符号長さの情報に基づいて、一致位置と一致長さの情報を容易に取得し、それらの情報から元の記号列に復号するものであり、処理に時間のかからない復元処理を実現するものである。
【００２１】
図１に示すように、データ圧縮装置１は、入力バッファ１１、符号化部１２、及び辞書バッファ１３から構成され、入力されるデータを符号化してデータ容量を圧縮する装置である。ここで、入力される符号化前のデータのことを記号（列）と呼ぶこととし、本実施の形態例においては、各記号、例えば、図１の入力バッファ１１内の“Ａ”、“Ｂ”など、は８ビットのデータであるものとする。また、処理後の符号は、２進法による“０”又は“１”のビット列で表現される。
【００２２】
入力バッファ１１は、符号化対象の記号列を順次受け入れて格納するデータバッファであり、符号化が終了した記号列を順次辞書バッファ１３に引き渡す。また、入力バッファ１１の長さ（図１のＬ２）、即ち、格納可能な記号の数は、本実施の形態例では２５８であるものとする。この長さＬ２は、前記一致長さ（例えば、図１のｌ）の最大値を意味するものである。
【００２３】
辞書バッファ１３は、符号化済みの記号列を上記入力バッファ１１から順次受け入れて格納するデータバッファであり、ＬＺ７７方式において所謂辞書と呼ばれているものである。ここに格納された記号列は、入力バッファ１１内の符号化処理対象の記号列と比較され、この中から入力バッファ１１内の記号列と一致する最大長の記号列（以下、最長一致系列と呼ぶ）が探索される。辞書バッファ１３では、符号化部１２における符号化が終了する度に、符号化が済んだ記号列を受け入れて、先頭にある（図１の左側に位置する）その分の記号列が不要の記号として吐き出される。また、辞書バッファ１３の長さ（図１のＬ１）、即ち、格納可能な記号の数は、本実施の形態例では１６３８４（１６Ｋ）であるものとする。この長さＬ１は、前記一致位置を表す距離（例えば、図１のｄ）の最大値を意味するものである。図１に示す例では、最長一致系列が“ＡＢＣＤ”であり、その長さである一致長さがｌであり、その一致位置がｐであるということになる。
【００２４】
次に、符号化部１２は、当該データ圧縮装置１における記号列の入力、符号化、及び符号の出力に係る全般の制御を行なう部分であるが、主に、辞書バッファ１３を参照しながら、入力バッファ１１内の記号列を符号化する処理を実行する。かかる符号化部１２が行なう符号化処理に特徴があり、その具体的な内容については後述する。なお、符号化部１２は、処理の手順を示したプログラムとそのプログラムに従って処理を実行するＣＰＵ等で構成してもよいし、ハードウェア回路で構成してもよい。
【００２５】
図２に示すように、データ復元装置２もデータ圧縮装置１と同様の構成をしており、入力バッファ２１、復号部２２（復号手段）、及び辞書バッファ２３（記号列格納手段）を備えている。本データ復元装置２は、前記データ圧縮装置１で圧縮されたデータ（符号）を元の記号列のデータに復元する装置である。入力バッファ２１は、処理対象の符号を順次受け入れて格納するデータバッファである。辞書バッファ２３は、復号済みの記号列を復号部２２から順次受け入れて格納するデータバッファである。ここに格納された記号列は、復号部２２による復号処理時に参照され、復号処理に利用される。辞書バッファ２３では、復号部２２における処理が終了する度に、復号された記号列を受け入れて、先頭にある（図２の右側に位置する）その分の記号列が不要の記号として吐き出される。また、辞書バッファ２３の長さ（サイズ）は、データ圧縮装置１の辞書バッファ１３の長さＬ１と同じである。
【００２６】
また、辞書バッファ２３内の状態は、その時に復号部２２において処理対象となっている符号が、データ圧縮装置１において符号化された時の辞書バッファ１３の状態と一緒の状態となっている。図１に示す例で“ＡＢＣＤ”という記号列が、一致位置ｐ（又はｄ）と一致長さｌに基づいて符号化された場合に、当該符号がデータ復元装置２によって復号処理される際には、辞書バッファ２３内の状態は図２に示すような状態になっている。即ち、辞書バッファ２３の左端から距離ｄの位置ｐより“ＡＢＣＤ”の順番に（図２では逆方向に表現されている）記号列が納められる。従って、復号部２２は、符号から取得される一致位置ｐ（又はｄ）と一致長さｌの情報に基づいて“ＡＢＣＤ”と復号することができる。
【００２７】
復号部２２は、当該データ復元装置２における符号の入力、復号、及び記号の出力に係る全般の制御を行なう部分であるが、主に、辞書バッファ２３を参照しながら、入力バッファ２１内の符号を復号する処理を実行する。かかる復号部２２が行なう復号処理の具体的な内容については後述する。なお、復号部２２は、処理の手順を示したプログラムとそのプログラムに従って処理を実行するＣＰＵ等で構成してもよいし、ハードウェア回路で構成してもよい。
【００２８】
図３は、データ圧縮装置１の符号化部１２が行なう処理の内容を例示したフローチャートである。以下、図３に基づいて、本データ圧縮装置１で行なわれる圧縮処理の具体的な内容について説明する。まず、処理対象の記号列が順番に入力バッファ１１に読み込まれる（ステップＳ１０）。次に、符号化部１２は、入力バッファ１１に格納された先頭位置（図１では、左端位置）からの記号列について、辞書バッファ１３内に格納された記号列との一致を探索する（ステップＳ１１）。即ち、前述した最長一致系列を検索する。
【００２９】
そして、検索された最長一致系列の長さ（一致長さ）が予め定められた値以上であるか否かがチェックされる（ステップＳ１２）。例えば、かかる所定数は“４”とされる。その結果、一致長さが３以下であれば（ステップＳ１２のＮｏ）、符号化部１２は、入力バッファ１１の先頭位置にある記号を、最長一致系列の一致位置と一致長さで表現せずに、当該記号をそのまま２進法で表現する手法で符号化する。そして、その符号を出力する（ステップＳ１３）。具体的には、本実施の形態例では、記号は８ビットのデータであるので、元の記号のままの８ビットのデータを９ビットで表現し、それを当該記号の符号とする。
【００３０】
図４は、本データ圧縮装置１によって生成される符号等を説明するための図である。図４の（ａ）が、本データ圧縮装置１によって生成される符号を模式的に示したものであり、上段に示される図（[不一致]と記載）が、上記ステップＳ１３で出力される符号である。言い換えれば、入力バッファ１１の先頭位置から所定数の記号列について、辞書バッファ１３内に一致するものが無かった場合の符号を示している。前述のように、かかる符号は、元々８ビットのデータを９ビットで表現したものであるので、必ず最上位のビットは“０”となる。後述するが、前記ステップＳ１２で一致長さが所定数以上である場合には、この最上位のビットが必ず“１”となるので、当該最上位のビットは、所定数の記号列について“不一致”であったことを示すことになる。また、それ以降に続く８ビットのデータは、元の記号そのものである。
【００３１】
従って、当該符号は、その最上位のビットにより上記“不一致”であること、即ち、その後のビット列で記号そのものを表していることを識別させている。言い換えれば、０〜５１１の値を取れる表現で、０〜２５５の値を表現することにより、元の記号をそのまま表現したものであることを識別させている。なお、この“不一致”であることと元の記号を含んだ、“不一致”の場合の符号全体を、ここでは“不一致”の場合の識別情報（第一識別情報）と称することとする。
【００３２】
図３に戻って、前記ステップＳ１２において、一致長さが所定数以上である場合には（ステップＳ１２のＹｅｓ）、符号化部１２は、検索された最長一致系列の一致位置及び一致長さを表すために必要なビット数（ビット列の長さ）を求める（ステップＳ１５）。  本実施の形態例では、前述した辞書バッファ１３のサイズから、一致位置は、１〜１６３８４の値を取るので、一致位置を表すのに必要なビット数は、１〜１４の値となる。また、前述した入力バッファ１１のサイズ及びステップＳ１２における条件から、一致長さは、４〜２５８の値を取るので、一致長さを表すのに必要なビット数は、１〜８の値となる。
【００３３】
次に、符号化部１２は、上記求められた一致位置及び一致長さのビット数と、入力バッファ１１の先頭位置から所定数の記号列について辞書バッファ１３内に“一致”するものがあった旨を示す符号を生成して出力する（ステップＳ１６）。かかる符号を、ここでは“一致”の場合の識別情報（第二識別情報）と称することとする。具体的には、一例として、下記（１）式のような値を識別情報として生成する。
識別情報（“一致”の場合）＝２５６＋（ＢＬ−１）×最大ＢＰ＋（ＢＰ−１）  （１）
但し、 ＢＬ：一致長さを表すのに必要なビット数
ＢＰ：一致位置を表すのに必要なビット数
最大ＢＰ：一致位置を表すのに必要な最大のビット数
なお、本実施の形態例では、上述の通り、最大ＢＰは１４の値となり、ＢＰ及びＢＬは上記値を取るので、（１）式により、上記識別情報（“一致”の場合）は２５６〜３６７の値となる。従って、当該識別情報（“一致”の場合）も２進法の符号として９ビットで表現される。図４の（ａ）の下段に示される図（[一致]と記載）が、上記所定数の記号列の“一致”があった場合に生成され出力される符号を示しているが、その左側部分の９ビットが当該識別情報に相当する。
【００３４】
上述のように、当該識別情報は２５６以上の値を取るので、そのことによって上記“一致”があったことを識別させ、また、当該識別情報の値から２５６を引いた値によって一致位置及び一致長さを表すのに必要なビット数を示している。言い換えれば、９ビットで表現される当該符号の最上位のビットは常に“１”の値となり、そのことで上記“一致”があったことを示し、下位の８ビットで一致位置及び一致長さを表すのに必要なビット数を示している。
【００３５】
このように、本実施の形態例による符号では、上記“一致”の場合にも“不一致”の場合にも、識別情報が共に９ビットで表現され、その値が２５６以上であるか否かにより、言い換えれば、最上位のビットにより、一致位置と一致長さに基づく符号化がなされているか否かが識別できる。また、その識別の後、下位８ビットにより、“不一致”の場合には、元の記号そのものを知ることができ、“一致”の場合には、識別情報の後に続く一致位置と一致長さを表す符号の長さを知ることができる。
【００３６】
かかる識別情報の出力が終了すると、符号化部１２は、前記検索された最長一致系列の一致位置を表す一致位置情報を符号として出力する（ステップＳ１７）。具体的には、一致位置を表す値を２進法表現した際の最上位の“１”のビットを除いた下位のビット列を一致位置情報として出力する。これは、最上位のビットが“１”であることが自明であり、極力データ量を少なくしようとする目的によるものである。例えば、一致位置の値が９である場合には、２進法では“１００１”となるが、“００１”を一致位置情報として出力する。
【００３７】
また、前述した、一致位置と一致長さを固定長のビット列で表現するＬＺＳＳ符号の場合と比較して表現すれば、一致位置を最大長の１４ビットで表現し、そのビット列のＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）側から連続して存在している“０”のビットとその次の“１”のビットを取り除いたものを一致位置情報とする。
【００３８】
次に、符号化部１２は、前記最長一致系列の一致長さを表す一致長さ情報を符号として出力する（ステップＳ１８）。この一致長さ情報も前記一致位置情報と同様に、一致長さを表す値を２進法表現した際の最上位の“１”のビットを除いた下位のビット列を一致長さ情報として出力する。
【００３９】
図４の（ａ）の下段に例示した符号において、右側に示される“一致位置情報”及び“一致長さ情報”が前記ステップＳ１７及びＳ１８において出力される各情報に相当する。
【００４０】
以上説明したように、“不一致”の場合あるいは“一致”の場合における符号の生成及び出力の処理が終了すると、入力バッファ１１及び辞書バッファ１３に格納されている記号列がスライドされる（ステップＳ１４）。具体的には、上記処理により符号が生成され出力された記号（列）が、入力バッファ１１の先頭部分から辞書バッファ１３の後尾部分に移動する。そして、その移動分の新たな記号（列）が入力バッファ１１に入力され、また、その移動分の記号（列）が辞書バッファ１３から吐き出される。なお、前記“不一致”の場合には、１記号のみが符号化されるので、上記移動する記号は一つであり、前記“一致”の場合には、４以上の記号が符号化されるので、上記移動する記号は４以上となる。
【００４１】
その後、今回行おうとしている圧縮処理が終了したか否かが判断され（ステップＳ１９）、終了していない場合には（ステップＳ１９のＮｏ）、前述したステップＳ１１からの処理が繰り返される。そして、圧縮処理が終了したと判断された場合には（ステップＳ１９のＹｅｓ）、一連のデータ圧縮処理を終了する。
【００４２】
図５は、データ復元装置２の復号部２２が行なう処理の内容を例示したフローチャートである。以下、図５に基づいて、本データ復元装置２で行なわれる復元処理の具体的な内容について説明する。まず、処理対象の符号が順番に入力バッファ２１に読み込まれる（ステップＳ２０）。次に、復号部２２は、符号の先頭の９ビット、即ち、識別情報を入力バッファ２１より読み込んでその情報を解釈する（ステップＳ２１）。
【００４３】
そして、現在処理対象の符号が、符号化時に前述した“不一致”の場合であったのか“一致”の場合であったのかを判断する（ステップＳ２２）。かかる判断は、前述の通り、識別情報の最上位のビットによって行うことができ、最上位のビットが“０”であれば、“不一致”の場合であったと判断し、最上位のビットが“１”であれば、“一致”の場合であったと判断する。言い換えれば、読み込んだ識別情報の値が０〜２５５であれば、その値が元の記号そのものを表していると判断し、識別情報の値が２５６以上であれば、この識別情報でこの後に続く一致位置と一致長さの情報のビット数を知ることができると判断する。
【００４４】
かかる判断で、“不一致”の場合であったと判断された場合には（ステップＳ２２のＮｏ）、上記読み込んだ識別情報が元の記号そのものを表しているので、元の記号を復元して出力する（ステップＳ２３）。より具体的には、９ビットの識別情報を８ビットとして出力する。
【００４５】
一方、“一致”の場合であったと判断された場合には（ステップＳ２２のＹｅｓ）、読み込んだ識別情報から、当該識別情報に続く一致位置情報のビット数と一致長さ情報のビット数を求める（ステップＳ２５）。具体的には、識別情報が前述した（１）式によって生成されているので、読み込んだ識別情報の値から２５６を引き、その後の値を前記最大ＢＰ（１４）で割り、その時の余りを一致位置情報のビット数とし、また、その時の商を一致長さ情報のビット数とする。
【００４６】
次に、復号部２２は、前記読み込んだ識別情報に続く、上記求めた一致位置情報のビット数分の符号を、入力バッファ２１から読み込む（ステップＳ２６）。その後、復号部２２は、当該読み込んだ一致位置情報から一致位置の値を求める（ステップＳ２７）。具体的には、読み込んだ一致位置情報のビット列の最上位に“１”のビットを付加した値を、一致位置の値とする。換言すれば、２の（前記一致位置情報のビット数）乗に一致位置情報の値を加えたものを一致位置の値とする。
【００４７】
引き続き、復号部２２は、前記読み込んだ一致位置情報に続く、前記求めた一致長さ情報のビット数分の符号を、入力バッファ２１から読み込む（ステップＳ２８）。その後、復号部２２は、当該読み込んだ一致長さ情報から一致長さの値を求める（ステップＳ２９）。具体的には、読み込んだ一致長さ情報のビット列の最上位に“１”のビットを付加した値に、３を加えた値を、一致長さの値とする。換言すれば、２の（前記一致長さ情報のビット数）乗に一致位置情報の値と３を加えたものを一致長さの値とする。ここで３を加えるのは、前述のように、一致長さの値が４〜２５８の値を取り、符号化時にそれを８ビットで表現するために、一致長さの値から３を引いた値（１〜２５５）を符号化していることによるものである。
【００４８】
次に、復号部２２は、上記求めた一致位置と一致長さの値から元の記号列を復元して復元した記号列を出力する（ステップＳ３０）。具体的には、辞書バッファ２３に格納されている記号列の上記求めた値の一致位置から上記求めた値の一致長さ分の記号列を読み出し、その読み出した記号列を元の記号列として出力する。
【００４９】
以上説明したように、“不一致”の場合あるいは“一致”の場合における復号処理が終了すると、入力バッファ２１及び辞書バッファ２３に格納されている符号及び記号列がスライドされる（ステップＳ２４）。具体的には、上記処理により復元された符号が入力バッファ２１から削除され、その分の新たな符号が入力バッファ２１に入力される。また、上記処理により復元された記号列が辞書バッファ２３の後尾部分に追加され、先頭部分のその分の記号列が不要な記号として辞書バッファ１３から吐き出される。
【００５０】
その後、今回行おうとしている復元処理が終了したか否かが判断され（ステップＳ３１）、終了していない場合には（ステップＳ３１のＮｏ）、前述したステップＳ２１からの処理が繰り返される。そして、復元処理が終了したと判断された場合には（ステップＳ３１のＹｅｓ）、一連のデータ復元処理を終了する。
【００５１】
図６は、本データ圧縮装置１及びデータ復元装置２が行う処理の具体例を示した図である。図に示す例は、データ圧縮時に前記所定数以上の記号の“一致”があった場合であり、その時の一致位置が３００で、一致長さが２２であった場合である。図６の（ａ）は、前記一致位置（３００）及び一致長さ（２２）を、最大限のビット数の長さで模式的に示した図である。図６の（ｂ）は、当該一致位置（３００）及び一致長さ（２２）を最大限のビット数で２進法表記したものである。
【００５２】
かかる状態に対して前述した符号化部１２による符号化が行われると図６の（ｃ）に示すような符号が生成されて出力される。図に示す符号の左部分が前述した識別情報（“一致”の場合）であり、前記（１）式に従って図に示すような計算がなされて、識別情報の値は３２０となる。即ち、一致長さの値である２２から３を引いた１９を２進法表現するのに必要なビット数５（ＢＬ）から１を差し引いた４という値に、１４（最大ＢＰ）を掛け、その値に、一致位置の値である３００を２進法表現するのに必要なビット数９（ＢＰ）から１を差し引いた値８と、２５６が加えられて３２０という識別情報が得られる。
【００５３】
また、図６の（ｃ）に示す符号の中央部分の８ビットが一致位置情報であり、３００を２進法表現したビット列の最上位の“１”が除かれたものとなっている。従って、図６の（ｂ）に示した１４ビットの表現から、ＭＳＢ側の全ての“０”と上記最上位の“１”が除かれた８ビットが符号として出力されることになる。また、図６の（ｃ）に示す符号の右部分が一致長さ情報であり、２２から３を引いた１９を２進法表現したビット列の最上位の“１”が除かれたものとなっている。従って、図６の（ｂ）に示した８ビットの表現から、ＭＳＢ側の全ての“０”と上記最上位の“１”が除かれた４ビットが符号として出力されることになる。
【００５４】
このような符号が、データ復元装置２で受け取られ復号部２２で復号されると、前記識別情報が解釈されて、一致位置情報と一致長さ情報のビット数がそれぞれ８と４であると判断される。そして、前述した処理内容に従って、図６の（ｄ）に示されるように、まず、識別情報の後の８ビットが読み出されて、その最上位に“１”のビットが付加される。これにより、一致位置の値が３００であると判断される。また、一致位置情報の後の４ビットが読み出されて、その最上位に“１”のビットが付加され、更に、３が加えられて、一致長さの値が２２であると判断される。これにより、復号部２２は、辞書バッファ２３から所定の記号列を取り出して出力し、当該符号に対する復号処理を終了する。
【００５５】
以上説明したように、本実施の形態例によるデータ圧縮方法及び復元方法では、辞書（バッファ１３）内に所定長以上の最長一致系列が存在しない場合には、その旨と元の記号を含む一定長の識別情報を符号として出力し、一方、辞書内に所定長以上の最長一致系列が存在する場合には、その旨と、一致位置を表す情報の長さ及び一致長さを表す情報の長さとを含む上記識別情報と同長さの識別情報をまず出力し、その後に、一致位置情報と一致長さ情報を出力する。そして、これら一致位置情報及び一致長さ情報は、一致位置及び一致長さを示す値を２進法表示した際の最上位のビットを除いたビット列で表現される。
【００５６】
従って、一致位置と一致長さに基づく符号化をした際に、それらを表す情報を常に最大の固定長（本実施の形態例では、１４と８）のビット列で表現する必要がなく、上記識別情報が付加されても、符号全体として平均的に符号の長さを短くでき、従来よりもデータ圧縮率を向上させることができる。図４の（ｂ）は、一致位置と一致長さの最大値が本実施の形態例と同じ場合に、ＬＺＳＳ符号を用いた時の符号例を模式的に示している。上段の辞書内に所定長以上の最長一致系列が存在しない場合（「不一致」）には、その旨を示す“０”と元の記号８ビットが出力される。また、下段の辞書内に所定長以上の最長一致系列が存在する場合（「一致」）には、その旨を示す“１”と固定長の一致位置情報及（１４ビット）及び一致長さ情報（８ビット）が出力される。図４の（ａ）に示した本実施の形態例の場合と比較して[不一致]の場合には、データ長さは同じであるが、[一致]の場合には、本実施の形態例の場合の方が平均してデータ長さが短くなるという評価が得られている。
【００５７】
また、当該符号を復元する場合には、まず、同じ長さの識別情報を解釈して、一致位置と一致長さに基づく符号化がなされているかが判断され、当該符号化がなされている場合にも、識別情報から一致位置情報と一致長さ情報を容易に読み取ることができる。従って、復号処理時に検索などの複雑な処理を必要とせず、処理に時間を要することはない。
【００５８】
なお、前記（１）式における乗数、即ち、一致長さ情報のビット数に掛ける乗数、を１４としたが、この乗数を１６にしてもよい。これにより、符号化時の乗算及び復号時の除算はビットシフトで済むことになり、さらに、圧縮及び復元の処理を高速化することができる。また、この場合にも識別情報のビット数は増やす必要がなく、データ量が増えることもない。
【００５９】
また、本実施の形態例における固定長の識別情報をハフマン符号化してもよい。これにより、更にデータ圧縮率を高めることができる。
【００６０】
次に、本実施の形態例に係るデータ圧縮方法及び復元方法の適用例について説明する。図７は、本実施の形態例に係るデータ圧縮方法及び復元方法を用いた印刷システムの概略構成図である。図７に示すように、本印刷システムは、ホストコンピュータ３とプリンタ４から構成される。ホストコンピュータ３のアプリケーション３１から印刷要求が出され、それを受けるプリンタドライバ３２が印刷データを生成して、プリンタ４へ送信する。プリンタ４では、その印刷データをコントローラ４１が受信し、所定の処理を施した後にデータをエンジン４２に送る。エンジン４２は、そのデータに基づいて、印刷媒体への印刷を実行する。
【００６１】
当該印刷システムは、所謂ホストベースのシステムであり、ホストコンピュータ３側でハーフトーン処理（スクリーン処理）までを行ってしまう。従って、プリンタドライバ３２には、図７に示すように、画像データを生成する画像生成部３３、色の変換処理を行う色変換部３４、ハーフトーン処理を行うハーフトーン処理部３５、及びハーフトーン処理後の印刷データを圧縮する圧縮部３６が備えられている。なお、これらの部分は、それぞれの処理内容が示されたドライバプログラムとそれに従って処理を実行するＣＰＵ（制御装置）等によって構成され得る。
【００６２】
一方、プリンタ４のコントローラ４１には、ホストコンピュータ３から圧縮処理された印刷データが送信されるので、それを復元処理する解凍部４３が備えられる。
【００６３】
このように構成される本印刷システムの上記圧縮部３６と解凍部４３に、それぞれ、前述した本実施の形態例に係るデータ圧縮装置１とデータ復元装置２が用いられている。従って、圧縮部３６ではハーフトーン処理後のドットイメージを表す印刷データが、前述した手法で符号化される。そして、その符号化された印刷データがプリンタ４に送信され、解凍部４３において述した手法で復号される。
【００６４】
本印刷システムでは、このように本実施の形態例に係るデータ圧縮方法及び復元方法が用いられるので、印刷データの圧縮率を高めることができ、ホストコンピュータ３からプリンタ４への送信時間を短縮できる。従って、高速化するホストコンピュータ３、プリンタ４での処理にデータ送信を追随させることができ、印刷システムとしてのスループットを向上させることができる。特に、本適用例のようにハーフトーン処理後の印刷データは、同じパターンのデータが繰り返し現れる傾向にあることから、圧縮率を向上させるために本データ圧縮方法が適しているといえる。なお、ハーフトーン処理後のデータについて、最長一致系列が同じであった場合に一致位置の値が小さい方を選択するようにして本圧縮方法を使用した場合に、一致位置情報は平均７〜８ビットで、一致長さ情報は平均２〜３ビットで表せるという評価が得られており、符号全体では平均１９ビット程度であるといえる。従って、ＬＺＳＳ方式による２３ビットの符号と比較してデータを短くすることができる（図４参照）。
【００６５】
また、プリンタ４の制御装置（ＣＰＵ）は、パーソナルコンピュータなどで構成されるホストコンピュータ３と比べて、それほど高速のものを採用しなくてもすむようにしたいという要望があるが、本圧縮方法及び復元方法を用いれば、前述の通り、プリンタ４で行われる復元処理が容易となり、当該要望にもかなっている。また、ハーフトーン処理後の印刷データの場合には、前記識別情報のハフマン符号化に適しており、これによって更に圧縮率を向上させることができる。
【００６６】
本発明の保護範囲は、上記の実施の形態に限定されず、特許請求の範囲に記載された発明とその均等物に及ぶものである。
【図面の簡単な説明】
【００６７】
【図１】本発明を適用したデータ圧縮装置の実施の形態例に係る構成図である。
【図２】本発明を適用したデータ復元装置の実施の形態例に係る構成図である。
【図３】符号化部１２が行なう処理の内容を例示したフローチャートである。
【図４】本データ圧縮装置１によって生成される符号等を説明するための図である。
【図５】復号部２２が行なう処理の内容を例示したフローチャートである。
【図６】データ圧縮装置１及びデータ復元装置２が行う処理の具体例を示した図である。
【図７】本データ圧縮方法及び復元方法を用いた印刷システムの概略構成図である。
【符号の説明】
【００６８】
１  データ圧縮装置、  ２  データ復元装置、  ３  ホストコンピュータ、  ４  プリンタ、  １１  入力バッファ、  １２  符号化部、  １３  辞書バッファ、  ２１  入力バッファ、  ２２  復号部（復号手段）、  ２３  辞書バッファ（記号列格納手段）、  ３１  アプリケーション、  ３２  プリンタドライバ、  ３３  画像生成部、  ３４  色変換部、  ３５  ハーフトーン処理部、  ３６  圧縮部、  ４１  コントローラ、  ４２  エンジン、  ４３  解凍部
【図１】
2005269184.tif 000003
【図２】
2005269184.tif 000004
【図３】
2005269184.tif 000005
【図４】
2005269184.tif 000006
【図５】
2005269184.tif 000007
【図６】
2005269184.tif 000008
【図７】
2005269184.tif 000009