(57)【要約】  符号列のデータストリームを一連のブロック群に分割し、ブロック群の先頭ブロックを該先頭ブロックの符号を参照辞書としたスライド辞書法に従い圧縮し、先頭ブロックに後続するブロックを順次的に圧縮の対象ブロックとして認識し、対象ブロックを認識するごとに、当該対象ブロックの符号と当該対象ブロックより前方のブロック群の圧縮結果とを参照辞書としたスライド辞書法に従い当該対象ブロックを圧縮し、当該対象ブロックの圧縮結果を前方のブロック群の圧縮結果の末尾に配置する。
2009057459.tif 000002
【特許請求の範囲】
【請求項１】
符号列のデータストリームを一連のブロック群に分割し、
前記ブロック群の先頭ブロックを該先頭ブロックの符号を参照辞書としたスライド辞書法に従い圧縮し、
前記先頭ブロックに後続するブロックを順次的に圧縮の対象ブロックとして認識し、
前記対象ブロックを認識するごとに、当該対象ブロックの符号と当該対象ブロックより前方のブロック群の圧縮結果とを参照辞書としたスライド辞書法に従い当該対象ブロックを圧縮し、当該対象ブロックの圧縮結果を前記前方のブロック群の圧縮結果の末尾に配置することを特徴とするデータ圧縮方法。
【請求項２】
前記一連のブロック群に関する各圧縮結果の開始位置を表す位置情報を記録し、
前記位置情報を前記一連のブロック群に関する一連の圧縮結果の先頭に付加することを特徴とする請求項１記載のデータ圧縮方法。
【請求項３】
前記データストリームがアイコン画像データを含むことを特徴とする請求項１又は２記載のデータ圧縮方法。
【請求項４】
符号列のデータストリームを一連のブロック群に分割する手段と、
前記ブロック群の先頭ブロックを該先頭ブロックの符号を参照辞書としたスライド辞書法に従い圧縮する手段と、
前記先頭ブロックに後続するブロックを順次的に圧縮の対象ブロックとして認識する手段と、
前記対象ブロックを認識するごとに、当該対象ブロックの符号と当該対象ブロックより前方のブロック群の圧縮結果とを参照辞書としたスライド辞書法に従い当該対象ブロックを圧縮し、当該対象ブロックの圧縮結果を前記前方のブロック群の圧縮結果の末尾に配置する手段とを備えることを特徴とするデータ圧縮装置。
【請求項５】
前記一連のブロック群に関する各圧縮結果の開始位置を表す位置情報を記録する手段と、
前記位置情報を前記一連のブロック群に関する一連の圧縮結果の先頭に付加する手段とを備えることを特徴とする請求項４記載のデータ圧縮装置。
【請求項６】
前記データストリームがアイコン画像データを含むことを特徴とする請求項４又は５記載のデータ圧縮装置。
【請求項７】
コンピュータに、
符号列のデータストリームを一連のブロック群に分割するステップと、
前記ブロック群の先頭ブロックを該先頭ブロックの符号を参照辞書としたスライド辞書法に従い圧縮するステップと、
前記先頭ブロックに後続するブロックを順次的に圧縮の対象ブロックとして認識するステップと、
前記対象ブロックを認識するごとに、当該対象ブロックの符号と当該対象ブロックより前方のブロック群の圧縮結果とを参照辞書としたスライド辞書法に従い当該対象ブロックを圧縮し、当該対象ブロックの圧縮結果を前記前方のブロック群の圧縮結果の末尾に配置するステップとを実行させることを特徴とするプログラム。
【請求項８】
前記コンピュータに、
前記一連のブロック群に関する各圧縮結果の開始位置を表す位置情報を記録するステップと、
前記位置情報を前記一連のブロック群に関する一連の圧縮結果の先頭に付加するステップとを実行させることを特徴とする請求項７記載のプログラム。
【請求項９】
前記データストリームがアイコン画像データを含むことを特徴とする請求項７又は８記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの圧縮処理に関する。
【背景技術】
【０００２】
データ圧縮の手法の一つに、いわゆるスライド辞書法（LZ77：Lempel-Ziv  coding 1977）がある。スライド辞書法によるエンコード（データ圧縮）では、所定長のバッファを窓とみなし、バッファ内のデータストリームをＦＩＦＯ（First-In First-Out）方式で入出力することにより、窓枠をスライドさせる。そして、窓枠内で最長一致する符号列パターンを検出し、その一致する符号列の位置情報と符号数とをコード化することで、データを圧縮するというものである。【０００３】
図４に、スライド辞書法によるデータ圧縮の例を示す。いま、「abcdebcd」というデータストリームが入力されたとする。この入力ストリームの先頭から“abcde”までの符号列は、異なる符号から構成されている。一方、後続の“bcd”については、それぞれと同じ符号が前方の符号列“abcde”の中に含まれる。【０００４】
上記のような入力ストリームをスライド辞書法により圧縮すると、図４に示すように、先頭から“abcde”の符号について、参照位置（Ref：Reference）「０」と参照長（L：Length）「５」とからなる参照符号に続き、非参照符号である元の符号“abcde”が出力される。参照位置は、参照すべき辞書（符号）の位置を表す。本例の先頭からの“abcde”の各符号は、それぞれ異なるものであり、この中には参照すべき候補が存在しないことから、参照位置として「０」が設定される。【０００５】
後続の符号列“bcd”の圧縮の際には、既に処理された上記の“abcde”が辞書として利用される。辞書“abcde”の中には、後続の符号列“bcd”により参照すべき候補“bcd”が存在する。この場合、図４に示すように、辞書末尾から参照開始位置まで遡った値（オフセット値）である参照位置「４」と、参照候補の符号数である参照長「３」とからなる参照符号とが、元の符号列“bcd”に替えて出力される。【０００６】
図５に、スライド辞書法によるデータ圧縮の他の例を示す。本例の入力ストリームは「abcdedededed」である。先頭から“abcde”までの符号列については、前述の例（図４）と同様に、参照位置「０」及び参照長「５」からなる参照符号に続いて、元の符号列“abcde”が出力される。【０００７】
一方、後続の符号列“dededed”については、最初の“de”が、辞書としての符号列“abcde”に含まれるので、参照位置の「２」が決定される。残りの“deded”については、図５に示すように、上記の最初の“de”を参照した後、２番目の“de”，３番目の“d”が順次参照されるような設定を行う。この設定のために、“dededed”の総数である「７」が参照長として決定される。その結果、元の符号列“dededed”に替えて、参照位置「２」と参照長「７」とからなる参照符号が出力される。【０００８】
図５の例のように、［参照位置］＜［参照長］となる参照符号のデコードの際は、既にデコードされた符号列を参照してデコード結果を作成した後、そのデコード結果を参照して新たなデコード結果を作成するという処理を繰り返す。すなわち、図示の圧縮手順とは逆の手順に沿ってデコードが進められる。これにより、圧縮時に設定された参照長の分の符号が復元される。【０００９】
このように、スライド辞書法によれば、入力ストリームにおいて複数回出現する符号が、２回目以降の出現から、参照位置と参照長とからなる参照符号に変換されるため、ストリームのデータ量が削減される。【００１０】
一方で、圧縮ストリームのデコードの際は、ストリームの途中からデコードする場合であっても、それより前方の全データを事前にデコードしておく必要がある。この制約は、長大なデータの一部分のみをデコードするような用途においては、デコードに時間がかかるという問題が発生する。【００１１】
かかる事態を回避する手法として、例えば、特許文献１に記載の圧縮方法がある。同文献の圧縮方法は、入力ストリームを適切なサイズのブロックに分割し、ブロック単位で、スライド辞書法によるデータ圧縮を実行するというものである。
【特許文献１】特開平６−１６８０９６号公報（第８−１０頁）
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、上記文献の圧縮方法にあっては、スライド辞書法に基づく辞書がブロックごとに初期化されることから、辞書の最大サイズがブロック長によって制限される。したがって、上記文献の手法では、辞書の規模が制限されることにより、入力ストリームの圧縮率が低下するおそれがある。【００１３】
本発明の目的は、ブロック単位に分割された入力ストリームの圧縮処理において圧縮率の低下を抑える技術を提供することにある。
【課題を解決するための手段】
【００１４】
本発明に係るデータ圧縮方法は、符号列のデータストリームを一連のブロック群に分割し、前記ブロック群の先頭ブロックを該先頭ブロックの符号を参照辞書としたスライド辞書法に従い圧縮し、前記先頭ブロックに後続するブロックを順次的に圧縮の対象ブロックとして認識し、前記対象ブロックを認識するごとに、当該対象ブロックの符号と当該対象ブロックより前方のブロック群の圧縮結果とを参照辞書としたスライド辞書法に従い当該対象ブロックを圧縮し、当該対象ブロックの圧縮結果を前記前方のブロック群の圧縮結果の末尾に配置するという方法である。【００１５】
本発明に係るデータ圧縮装置は、符号列のデータストリームを一連のブロック群に分割する手段と、前記ブロック群の先頭ブロックを該先頭ブロックの符号を参照辞書としたスライド辞書法に従い圧縮する手段と、前記先頭ブロックに後続するブロックを順次的に圧縮の対象ブロックとして認識する手段と、前記対象ブロックを認識するごとに、当該対象ブロックの符号と当該対象ブロックより前方のブロック群の圧縮結果とを参照辞書としたスライド辞書法に従い当該対象ブロックを圧縮し、当該対象ブロックの圧縮結果を前記前方のブロック群の圧縮結果の末尾に配置する手段とを備える。
【発明の効果】
【００１６】
本発明によれば、ブロック単位に分割された入力ストリームの圧縮処理において圧縮率の低下を抑えることができる。
【図面の簡単な説明】
【００１７】
【図１Ａ】本発明の実施形態における入力ストリーム及び圧縮ストリームの説明図である。
【図１Ｂ】本発明の実施形態の動作手順を示すフローチャートである。
【図２Ａ】本発明の実施形態における圧縮処理の説明図である。
【図２Ｂ】本発明の実施形態における圧縮処理の説明図である。
【図２Ｃ】本発明の実施形態における圧縮処理の説明図である。
【図２Ｄ】関連技術による圧縮処理の説明図である。
【図３】本発明の他の実施形態における入力ストリームの説明図である。
【図４】スライド辞書法による圧縮処理の説明図である。
【図５】スライド辞書法による圧縮処理の説明図である。
【符号の説明】
【００１８】
1  入力ストリーム
2  圧縮ストリーム
2a  インデックス（Index）
【発明を実施するための最良の形態】
【００１９】
本発明の実施の形態について、図面を参照して詳細に説明する。図１Ａに、本実施形態における入力ストリーム1及び圧縮ストリーム2の概念を示す。入力ストリーム1は、圧縮処理されるに先立ち、所定長のブロックに分割される。図示の例では、入力ストリーム1が、「block 0」〜「block 4」という一連の５つのブロックに分割されている。【００２０】
圧縮ストリーム2は、入力ストリーム1の各ブロックに対する後述の圧縮処理により得られる一連の圧縮結果である。圧縮ストリーム2の先頭には、圧縮ストリーム2における各ブロックの開始位置の情報（「offset 0」〜「offset 4」）が記述されたインデックス2aが付加される。【００２１】
図１Ｂに示すフローチャートに沿って、本実施形態の動作を説明する。以下の動作は、本発明に係るデータ圧縮装置としてのコンピュータ（図示略）により実行されることを想定したものである。【００２２】
コンピュータは、入力ストリーム1を、例えば１６ＫＢ単位のような、所定単位のブロックに分割する（ステップS1）。コンピュータは、これらのブロック群に対し、スライド辞書法に基づく次のような圧縮処理を施す。【００２３】
圧縮処理において、コンピュータは、まず、ブロック群の先頭ブロックを認識し、先頭ブロック内の符号を辞書として符号列を圧縮する（ステップS2）。【００２４】
図２Ａを参照し、上記の先頭ブロックの圧縮について具体例を挙げて説明する。本例では、入力ストリーム1として、現時点で「abcdebcdabcdfdfd」という合計１６個の符号が得られた状況を想定する。また、規定のブロック長が８符号分のデータ量であるとする。よって、現時点の入力ストリーム1は、“abcdebcd”からなる先頭ブロック「block 0」と、“abcdfdfd”からなる後続のブロック「block 1」という２つのブロックに分割される。【００２５】
コンピュータは、最初の「block 0」の“abcdebcd”を認識すると、その先頭から“abcde”までの符号列については、参照すべき辞書が存在しないと判断する。そして、スライド辞書法に従い、圧縮結果として、参照位置「０」及び参照長「５」に続いて、元の符号列“abcde”を出力する。また、「block 0」の残りの符号列“bcd”については、既に処理された上記“abcde”の中に辞書が存在する。よって、符号列“bcd”の圧縮結果として、スライド辞書法に基づく参照位置「４」と参照長「３」とが出力される。【００２６】
コンピュータは、上記のような手順で先頭ブロックの圧縮を終えると、圧縮結果の開始位置の情報をインデックスとして記録する（図１Ｂ：ステップS3）。図２Ａの例では、圧縮ストリーム2における「block 0」の参照符号“0,5”の位置が、インデックスとして記録される。この「block 0」の位置情報は、図１Ａにおける「offset 0」に対応するものである。なお、参照符号は、参照位置と参照長との組み合わせで１つの符号として取り扱われる。【００２７】
コンピュータは、次に圧縮すべき対象ブロックがあるかどうかを確認し、対象ブロックがある場合は（ステップS4：Yes）、その対象ブロックの圧縮処理を行う（ステップS5）。この圧縮処理において、コンピュータは、対象ブロックの符号列と、その対象ブロックより前方のブロックの圧縮結果とを辞書として利用する。そして、圧縮処理ごとに、圧縮結果の開始位置をインデックスとして記録する（ステップS6）。【００２８】
図２Ｂを参照し、先頭ブロックの後続のブロックの圧縮について具体例を挙げて説明する。本例は、前述した先頭の「block 0」の圧縮処理（図２Ａ）が済んだ状態を想定したものである。コンピュータは、次の「block 1」の圧縮にあたっては、このブロック内の符号列に限らず、前方の「block 0」の圧縮結果も辞書として利用する。【００２９】
コンピュータは、「block 1」の符号列“abcdfdfd”を認識すると、その先頭から“abcd”までが、前方の「block 0」の圧縮結果の中に含まれていると判断する。そこで、“abcd”の圧縮結果として、「block 0」の末尾位置からのオフセット値「６」を参照位置に決定し、参照すべき符号数「３」を参照長と決定する。この圧縮結果は、「block 0」の圧縮結果の末尾に続いて配置される。【００３０】
「block 1」において、上記“abcd”の後続の“f”は、既に処理された“abcd”にも、「block 0」の圧縮結果にも含まれない。よって、コンピュータは、“f”の圧縮結果として、参照位置「０」及び参照長「１」と符号“f”とを出力する。【００３１】
「block 1」において、さらに後続の“dfd”については、“df”が、既に処理された上記“abcdf”に含まれる。よって、コンピュータは、“dfd”の圧縮結果として、参照位置「２」及び参照長「３」を出力する。この圧縮手順は、前述した図５の手順に準じたもの、すなわち、参照符号が［参照位置］＜［参照長］となるケースである。【００３２】
ここで仮に、前述した特許文献１の手法のような、ブロック単位で辞書が初期化される手法により、上記の「block 1」を圧縮した場合、その圧縮結果は、図２Ｃに示すようなものとなる。この手法の場合、「block 1」の圧縮時に参照すべき辞書には、前方の「block 0」の圧縮結果は含まれない。よって、「block 1」の圧縮結果は、２つの参照符号“0,5”及び“2,3”と、５つの符号“abcdf”とからなる７符号となる。これに対し、本発明を適用した圧縮処理（図２Ｂ）によれば、「block 1」の圧縮結果が、３つの参照符号“6,4”、“0,1”、“2,3”と１つの符号“f”とからなる４符号である。よって、本発明の圧縮方法を適用することで、３つ分の符号が削減されることがわかる。【００３３】
コンピュータは、上記の手順により、先頭ブロックに後続するブロックの圧縮処理を進める。そして、入力ストリーム1の全てのブロックの圧縮が完了すると（図１ＢのステップS4：No）、図２Ｄに示すように、圧縮ストリーム2の先頭に、各ブロックの開始位置を記述したインデックス2aを付加する（ステップS5）。【００３４】
本実施形態によれば、先頭ブロックの後続のブロックを圧縮する際に、前方のブロックの圧縮結果を辞書に含めることから、辞書の規模が制限されることを回避できる。これにより、入力ストリームの圧縮率が低下することを防止できる。【００３５】
また、圧縮ストリーム2において、あるブロックの符号が前方のブロックに遡って参照する辞書は、圧縮結果である。具体的には、図２Ｂの圧縮ストリーム2において、「block 1」の参照符号“6,4”が、前方の「block 0」の圧縮結果を参照するケースに相当する。参照する辞書が圧縮結果であることから、圧縮ストリーム2の途中のブロックをデコードする場合でも、そのブロックより前方のブロックを事前にデコードしておくことは不要である。よって、本実施形態によれば、デコードを高速化できるというメリットもある。【００３６】
本発明は、上記実施形態に限定されるものではない。本発明の実施は、本願の請求の範囲内において、適宜変更が可能である。例えば、入力ストリーム（1）は、前述のような文字列に限らず、画像データであってもよい。【００３７】
図３に、本発明をアイコン画像データの圧縮処理に適用した例を示す。本例では、圧縮対象の入力ストリーム1が、携帯電話機等に用いられるアンテナ感度マークのアイコン画像からなる。一般に、アイコン画像データは、サイズが小さく、一度に大量のデータが使用される場合が多い。また、圧縮されたアイコン画像のデコード処理では、画像をランダムにデコードできることが望ましい。このような用途でも、例えば所定数のアイコン画像をブロック単位として、入力ストリーム1を分割し、上記実施形態と同様な手順で圧縮すればよい。これにより、より高い圧縮率を実現できるとともに、アイコン画像のランダムなデコード処理も高速に行うことができる。【００３８】
また、例えば電子メールのように、アイコン画像データと文字列とが混在した入力ストリームの場合であっても、その入力ストリームを上記実施形態と同様な手順で圧縮することができる。【００３９】
本発明は、上記実施形態におけるコンピュータの動作に対応したプログラム、あるいは、そのプログラムを記憶した記録媒体として実施することができる。【００４０】
本出願は、２００７年１０月３０日に日本出願された特願２００７−２８１０９０を基礎とする優先権を主張し、その開示の内容を全て本明細書に取り込むものである。
【図１Ａ】
2009057459.tif 000003
【図１Ｂ】
2009057459.tif 000004
【図２Ａ】
2009057459.tif 000005
【図２Ｂ】
2009057459.tif 000006
【図２Ｃ】
2009057459.tif 000007
【図２Ｄ】
2009057459.tif 000008
【図３】
2009057459.tif 000009
【図４】
2009057459.tif 000010
【図５】
2009057459.tif 000011
【国際調査報告】
2009057459.tif 000012
2009057459.tif 000013
2009057459.tif 000014
2009057459.tif 000015