(57)【特許請求の範囲】
【請求項１】
入力データを複数種類のデータ長の複数のデータブロックに分割する分割部と、
前記各データブロックのハッシュ値を計算するハッシュ計算部と、
過去の前記入力データを前記データブロック毎に記憶し、異なる前記データ長間で共有される共有辞書を含む第１の辞書を記憶する第１の辞書メモリと、
前記ハッシュ値に対応する前記データブロックの前記第１の辞書上の格納場所を示すアドレスを前記データブロック毎に記憶し、異なる前記データ長間で共有される共有テーブルを含むハッシュテーブルを記憶するハッシュテーブルメモリと、
新規の前記入力データに基づいて前記第１の辞書を更新し、新規の前記入力データ及び更新された前記第１の辞書に基づいて前記ハッシュテーブルの前記アドレスを更新する第１の更新部と、
前記ハッシュテーブルに基づいて、新規の前記入力データから分割された前記データブロックに対応する前記アドレスを取得するアドレス取得部と、
取得された前記アドレスが示す前記格納場所に記憶された過去の前記データブロックと、新規の前記入力データの各部分との同一性を判定するマッチング部と、
前記同一性の判定結果を示すマッチング情報を含み、前記同一性があると判定された一致部分が前記アドレスに変換された圧縮データを生成する符号化部と、
を備えるデータ圧縮システム。
【請求項２】
前記共有辞書は、第１のデータ長に対応する第１の領域と、前記第１のデータ長より短い第２のデータ長に対応する第２の領域とを含み、
前記第１の領域のエントリアドレスと前記第２の領域のエントリアドレスとが連続して割り当てられ、
前記第１の領域のワード長と前記第２の領域のワード長とが同一であり、
前記アドレスは、前記エントリアドレスを示す辞書エントリ情報と、前記第１の領域及び前記第２の領域のワード方向のオフセットを示すオフセット情報とを含む、
請求項１に記載のデータ圧縮システム。
【請求項３】
前記第１の辞書は、同一の前記データ長を有する複数の前記データブロック間で共有され、
前記ハッシュテーブルは、同一の前記データ長を有する複数の前記データブロック間で共有される、
請求項１又は２に記載のデータ圧縮システム。
【請求項４】
前記マッチング部は、判定を行った結果、同一である数が設定値を超えないように前記同一性の判定を行う、
請求項１〜３のいずれか１項に記載のデータ圧縮システム。
【請求項５】
前記圧縮データを復元し、復元データを生成する復元部、
を更に備える請求項１〜４のいずれか１項に記載のデータ圧縮システム。
【請求項６】
前記復元部は、
前記マッチング情報に基づいて前記圧縮データ内の前記一致部分を解析するマッチング解析部と、
過去の前記復元データを記憶する第２の辞書を記憶する第２の辞書メモリと、
前記第２の辞書に基づいて、解析された前記一致部分に相当する前記アドレスを前記入力データの生データに変換して前記復元データを生成する伸張部と、
新規の前記復元データに基づいて前記第２の辞書を更新する第２の更新部と、
を含む、
請求項５に記載のデータ圧縮システム。
【請求項７】
前記入力データと前記復元データとを比較する比較部と、
比較結果に応じて前記圧縮データの出力を制御する出力制御部と、
を更に備える請求項５又は６に記載のデータ圧縮システム。
【請求項８】
入力データを複数種類のデータ長の複数のデータブロックに分割するステップと、
前記各データブロックのハッシュ値を計算するステップと、
過去の前記入力データを前記データブロック毎に記憶し、異なる前記データ長間で共有される共有辞書を含む第１の辞書を生成するステップと、
前記ハッシュ値に対応する前記データブロックの前記第１の辞書上の格納場所を示すアドレスを前記データブロック毎に記憶し、異なる前記データ長間で共有される共有テーブルを含むハッシュテーブルを生成するステップと、
新規の前記入力データに基づいて前記第１の辞書を更新するステップと、
新規の前記入力データ及び更新された前記第１の辞書に基づいて前記ハッシュテーブルの前記アドレスを更新するステップと、
前記ハッシュテーブルに基づいて、新規の前記入力データから分割された前記データブロックに対応する前記アドレスを取得するステップと、
取得された前記アドレスが示す前記格納場所に記憶された過去の前記データブロックと、新規の前記入力データの各部分との同一性を判定するステップと、
前記同一性の判定結果を示すマッチング情報を含み、前記同一性があると判定された一致部分が前記アドレスに変換された圧縮データを生成するステップと、
を含むデータ圧縮方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、データ圧縮システム及び方法に関する。
【背景技術】
【０００２】
データ圧縮技術として、ＬＺ７８、ＬＺＷ等の辞書式圧縮法が知られている。
【０００３】
例えば、入力データを８バイト、４バイト、及び２バイトのデータ長のデータブロックに分割し、各データ長に対応する辞書をネスト状の階層構造に構築するデータ圧縮装置がある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許出願公開第２００６／０１０６８７０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
入力データを所定のデータ長のデータブロックに分割し、データ長のパターン毎に生成された辞書を利用することにより、高速且つ高精度なデータ圧縮を実現することができる。また、データ長のパターンを増やすことにより、より性能の向上を図ることができる。しかしながら、データ長のパターンを増加させると、各パターンに対応する辞書の数が増加するため、辞書を記憶するために必要な物理的記憶領域が増大化する場合がある。
【０００６】
そこで、以下の実施形態では、物理的記憶領域を増大させることなく性能を向上させることを目的とする。
【課題を解決するための手段】
【０００７】
実施形態のデータ圧縮システムは、分割部と、ハッシュ計算部と、第１の辞書メモリと、ハッシュテーブルメモリと、第１の更新部と、アドレス取得部と、マッチング部と、符号化部とを備える。分割部は、入力データを複数種類のデータ長の複数のデータブロックに分割する。ハッシュ計算部は、各データブロックのハッシュ値を計算する。第１の辞書メモリは、過去の前記入力データをデータブロック毎に記憶し、異なるデータ長間で共有される共有辞書を含む第１の辞書を記憶する。ハッシュテーブルメモリは、ハッシュ値に対応するデータブロックの第１の辞書上の格納場所を示すアドレスをデータブロック毎に記憶し、異なるデータ長間で共有される共有テーブルを含むハッシュテーブルを記憶する。第１の更新部は、新規の入力データに基づいて第１の辞書を更新し、新規の入力データ及び更新された第１の辞書に基づいてハッシュテーブルのアドレスを更新する。アドレス取得部は、ハッシュテーブルに基づいて、新規の入力データから分割されたデータブロックに対応するアドレスを取得する。マッチング部は、取得されたアドレスが示す格納場所に記憶された過去のデータブロックと、新規の入力データの各部分との同一性を判定する。符号化部は、同一性の判定結果を示すマッチング情報を含み、同一性があると判定された一致部分がアドレスに変換された圧縮データを生成する。
【図面の簡単な説明】
【０００８】
【図１】第１の実施形態に係るデータ圧縮システムの構成を示す図。
【図２】第１の実施形態に係るデータブロックの構成を示す図。
【図３】第１の実施形態に係る圧縮データのコード構造を示す図。
【図４】第１の実施形態に係るハッシュテーブル及び圧縮辞書の構成を示す図。
【図５】比較例に係るハッシュテーブル及び圧縮辞書の構成を示す図。
【図６】第１の実施形態に係るハッシュテーブルメモリのメモリマップを示す図。
【図７】第１の実施形態に係る圧縮辞書メモリのメモリマップを示す図。
【図８】第１の実施形態に係る２バイトデータブロックにおけるアドレス変換を示す図。
【図９】第１の実施形態に係る復元部の構成を示す図。
【図１０】第１の実施形態に係る復元辞書メモリの構成を示す図。
【図１１】比較例に係る復元辞書メモリの構成を示す図。
【図１２】第２の実施形態に係るデータ圧縮システムにおける読出し／書込み処理に要するサイクル数を示す図。
【図１３】第２の実施形態に係るデータ圧縮システムにおける同一性判定処理の流れを示すフローチャート。
【図１４】第３の実施形態に係るデータ圧縮システムの構成を示す図。
【図１５】第４の実施形態に係るハッシュテーブル及び圧縮辞書の構成を示す図。
【発明を実施するための形態】
【０００９】
（第１の実施形態）
図１は、第１の実施形態に係るデータ圧縮システム１の構成を示す図である。データ圧縮システム１は、入力データ１０を入力して圧縮データ１１を出力する圧縮部２０を含む。圧縮部２０は、分割部２１、ハッシュ計算部２２、ハッシュテーブルメモリ２３、圧縮辞書メモリ２４（第１の辞書メモリ）、更新部２５（第１の更新部）、アドレス取得部２６、マッチング部２７、及び符号化部２８を含む。
【００１０】
データ圧縮システム１は、プログラムに従って処理を行うＣＰＵ（Central  Processing  Unit）、プログラムを記憶するＲＯＭ（Read  Only  Memory）、ワーキングエリアとして機能するＲＡＭ（Random  Access  Memory）、汎用ロジックＩＣ（Integrated  Circuit）等の組み合わせにより構成され得る。
【００１１】
分割部２１は、圧縮対象となる入力データ１０を複数のデータブロックに分割する。複数のデータブロックは、互いに異なるデータ長を有する。データ長は、例えば、１６バイト、８バイト、４バイト、２バイト等であり得る。
【００１２】
ハッシュ計算部２２は、所定のハッシュ関数を用いて各データブロックのハッシュ値を計算する。
【００１３】
圧縮辞書メモリ２４は、過去の入力データ１０をデータブロック毎に記憶する圧縮辞書４０を記憶するメモリである。圧縮辞書４０は、異なる複数のデータ長間で共有される共有辞書を含む。例えば、８バイトのデータ長のデータブロックに対応する辞書と１６バイトのデータ長のデータブロックに対応する辞書とが１つの共有辞書として形成される。また、圧縮辞書４０は、同一のデータ長を有する複数のデータブロック間で共有される。例えば、４バイトのデータ長を有する複数のデータブロックを記憶する辞書が１つの辞書として形成される。
【００１４】
ハッシュテーブルメモリ２３は、ハッシュ値に対応するデータブロックの格納場所を示すアドレスを含むハッシュテーブル３０をデータブロック毎に記憶するメモリである。アドレスは圧縮辞書４０（圧縮辞書メモリ２４）上の位置を特定する。ハッシュテーブル３０は、異なる複数のデータ長間で共有される共有テーブルを含む。例えば、８バイトのデータ長のデータブロックに対応するアドレスを記憶するテーブルと１６バイトのデータ長のデータブロックに対応するアドレスを記憶するテーブルとが１つの共有テーブルとして形成される。また、ハッシュテーブル３０は、同一のデータ長を有する複数のデータブロック間で共有される。例えば、４バイトのデータ長を有する複数のデータブロックに対応する各アドレスを記憶するテーブルが１つのテーブルとして形成される。
【００１５】
更新部２５は、新規の入力データ１０に基づいて圧縮辞書４０を更新し、新規の入力データ１０及び更新された圧縮辞書４０に基づいてハッシュテーブル３０のアドレスを更新する。
【００１６】
アドレス取得部２６は、ハッシュテーブル３０に基づいて新規の入力データ１０の各データブロックに対応するアドレスを取得する。
【００１７】
マッチング部２７は、アドレス取得部２６により取得されたアドレスが示す圧縮辞書４０上の格納場所に記憶された過去のデータブロックと、新規の入力データ１０の各部分との同一性を判定する。
【００１８】
符号化部２８は、入力データ１０を圧縮した圧縮データ１１を生成する。符号化部２８は、同一性があると判定された入力データ１０の一部又は全部である一致部分をアドレスに変換することにより入力データ１０を圧縮する。圧縮データ１１は、同一性の判定結果を示すマッチング情報と、入力データ１０の一致部分に対応するアドレス又は入力データ１０の生データ（非一致部分）の少なくとも一方とを含む。符号化部２８は、圧縮データ１１をビットストリームとして出力してもよい。
【００１９】
図２は、第１の実施形態に係るデータブロック５１〜５４の構成を示す図である。本実施形態においては、分割部２１により１つの１６バイトの入力データ１０から４種類（１６バイト、８バイト、４バイト、及び２バイト）のデータ長を有する複数（１５）のデータブロック５１，５２Ａ，５２Ｂ，５３Ａ〜５３Ｄ，５４Ａ〜５４Ｈが生成される。具体的には、１つの１６バイトデータブロック５１、２つの８バイトデータブロック５２Ａ，５２Ｂ、４つの４バイトデータブロック５３Ａ〜５３Ｄ、及び８つの２バイトデータブロック５４Ａ〜５４Ｈが生成される。
【００２０】
１６バイトデータブロック５１は入力データ１０と同一のデータ長を有する。１６バイトデータブロック５１は入力データ１０の内容の全て「ＡＢＣＤＥＦＧＨ１２３４５６７８」を含む。
【００２１】
８バイトデータブロック５２は８バイトのデータ長を有する。分割部２１は、入力データ１０を２つに分割して第１の８バイトデータブロック５２Ａ及び第２の８バイトデータブロック５２Ｂを生成する。第１の８バイトデータブロック５２Ａは入力データ１０の内容の一部「ＡＢＣＤＥＦＧＨ」を含む。第２の８バイトデータブロック５２Ｂは入力データ１０の内容の一部「１２３４５６７８」を含む。
【００２２】
４バイトデータブロック５３は４バイトのデータ長を有する。分割部２１は、入力データ１０を４つに分割して第１の４バイトデータブロック５３Ａ、第２の４バイトデータブロック５３Ｂ、第３の４バイトデータブロック５３Ｃ、及び第４の４バイトデータブロック５３Ｄを生成する。第１の４バイトデータブロック５３Ａは入力データ１０の内容の一部「ＡＢＣＤ」を含む。第２の４バイトデータブロック５３Ｂは入力データ１０の内容の一部「ＥＦＧＨ」を含む。第３の４バイトデータブロック５３Ｃは入力データ１０の内容の一部「１２３４」を含む。第４の４バイトデータブロック５３Ｄは入力データ１０の内容の一部「５６７８」を含む。
【００２３】
２バイトデータブロック５４は２バイトのデータ長を有する。分割部２１は、入力データ１０を８つに分割して第１の２バイトデータブロック５４Ａ、第２の２バイトデータブロック５４Ｂ、第３の２バイトデータブロック５４Ｃ、第４の２バイトデータブロック５４Ｄ、第５の２バイトデータブロック５４Ｅ、第６の２バイトデータブロック５４Ｆ、第７の２バイトデータブロック５４Ｇ、及び第８の２バイトデータブロック５４Ｈを生成する。第１の２バイトデータブロック５４Ａは入力データ１０の内容の一部「ＡＢ」を含む。第２の２バイトデータブロック５４Ｂは入力データ１０の内容の一部「ＣＤ」を含む。第３の２バイトデータブロック５４Ｃは入力データ１０の内容の一部「ＥＦ」を含む。第４の２バイトデータブロック５４Ｄは入力データ１０の内容の一部「ＧＨ」を含む。第５の２バイトデータブロック５４Ｅは入力データ１０の内容の一部「１２」を含む。第６の２バイトデータブロック５４Ｆは入力データ１０の内容の一部「３４」を含む。第７の２バイトデータブロック５４Ｇは入力データ１０の内容の一部「５６」を含む。第８の２バイトデータブロック５４Ｈは入力データ１０の内容の一部「７８」を含む。
【００２４】
図３は、第１の実施形態に係る圧縮データ１１（１１Ａ〜１１Ｄ）のコード構造を示す図である。同図において、４つの例が示されている。第１の例は、１６バイトデータブロック５１から生成される第１の圧縮データ１１Ａのコード構造を示している。第２の例は、８バイトデータブロック５２から生成される第２の圧縮データ１１Ｂのコード構造を示している。第３の例は、４バイトデータブロック５３から生成される第３の圧縮データ１１Ｃのコード構造を示している。第４の例は、２バイトデータブロック５４から生成される第４の圧縮データ１１Ｄのコード構造を示している。同図のデータブロックにおいて、空白で示されている部分は一致部分、すなわち入力データ１０の各部分のうちマッチング部２４による判定結果が「同一性あり（Match）」である部分を示している。ハッチングが付されている部分は非一致部分、すなわち入力データ１０の各部分のうちマッチング部２４による判定結果が「同一性なし（Not  Match）」である部分を示している。
【００２５】
第１の例においては、１６バイトデータブロック５１内の全ての内容データ＜１＞：「ＡＢＣＤＥＦＧＨ１２３４５６７８」について「Match」の判定がなされている。この場合には、第１の圧縮データ１１Ａは、マッチング情報（Matching  Info）１５Ａ及びアドレス［１］から構成される。マッチング情報１５Ａは、圧縮データ１１Ａ内のどの部分が「Match」であるか又は「Not  Match」であるかを示す情報である。本例のマッチング情報１５Ａは、アドレス［１］に相当する部分が「Match」であることを示す情報となる。アドレス［１］は、内容データ＜１＞が記憶された圧縮辞書４０上の格納位置を示すアドレスである。すなわち、本例においては、「Match」の判定がなされた内容データ＜１＞がアドレス［１］に変換されて第１の圧縮データ１１Ａに組み込まれている。
【００２６】
第２の例においては、第１の８バイトデータブロック５２Ａ内の全部の内容データ＜２＞：「ＡＢＣＤＥＦＧＨ」及び第２の８バイトデータブロック５２Ｂ内の一部の内容データ＜４＞：「５６７８」について「Match」の判定がなされ、第２の８バイトデータブロック５２Ｂ内の一部の内容データ＜３＞：「１２３４」について「Not  Match」の判定がなされている。この場合には、第２の圧縮データ１１Ｂは、マッチング情報１５Ｂ、アドレス［２］、生データ［３］、及びアドレス［４］から構成される。本例のマッチング情報１５Ｂは、アドレス［２］，［４］に相当する各部分が「Match」であり、生データ［３］に相当する部分が「Not  Match」であることを示す情報となる。アドレス［２］は、内容データ＜２＞が記憶された圧縮辞書４０上の格納場所を示すアドレスである。生データ［３］は、内容データ＜３＞：「１２３４」をそのまま示すデータである。アドレス［４］は、内容データ＜４＞が記憶された圧縮辞書４０上の格納場所を示すアドレスである。すなわち、本例においては、「Match」の判定がなされた内容データ＜２＞，＜４＞がアドレス［２］，［４］に変換され、「Not  Match」の判定がなされた内容データ＜３＞がそのまま生データ［３］として第２の圧縮データ１１Ｂに組み込まれている。
【００２７】
第３の例においては、第２の４バイトデータブロック５３Ｂ内の一部の内容データ＜６＞：「ＥＦ」及び第４の４バイトデータブロック５３Ｄ内の一部の内容データ＜１０＞：「７８」について「Match」の判定がなされ、その他の内容データ＜５＞，＜７＞〜＜９＞について「Not  Match」の判定がなされている。この場合には、第３の圧縮データ１１Ｃは、マッチング情報１５Ｃ、生データ［５］、アドレス［６］、生データ［７］、生データ［８］、生データ「９」、及びアドレス［１０］から構成される。本例のマッチング情報１５Ｃは、アドレス［６］，［１０］に相当する各部分が「Match」であり、生データ［５］，［７］〜［９］に相当する各部分が「Not  Match」であることを示す情報となる。本例においては、内容データ＜６＞，＜１０＞がアドレス［６］，［１０］に変換され、内容データ＜５＞，＜７＞〜＜９＞がそのまま生データ［５］，［７］〜［９］として第３の圧縮データ１１Ｃに組み込まれている。
【００２８】
第４の例においては、全ての２バイトデータブロック５４Ａ〜５４Ｈ内の全ての内容データ＜１１＞〜＜１８＞について「Not  Match」の判定がなされている。この場合には、第４の圧縮データ１１Ｄは、マッチング情報１５Ｄ、及び生データ［１１］〜［１８］から構成される。本例のマッチング情報１５Ｄは、生データ［１１］〜［１８］に相当する各部分が「Not  Match」であることを示す情報となる。本例においては、内容データ＜１１＞〜＜１８＞がそのまま生データ［１１］〜［１８］として第４の圧縮データ１１Ｄに組み込まれている。
【００２９】
上記第１〜第４の例に示すように、全ての圧縮データ１１Ａ〜１１Ｄは、マッチング情報１５Ａ〜１５Ｄと、アドレス又は生データの少なくともどちらか一方とを含む。データブロック５１〜５４に含まれる内容のうち「Match」の判定がなされた内容データ＜１＞，＜２＞，＜４＞，＜６＞，＜１０＞は、それらの各々に対応するアドレス［１］，［２］，［４］，［６］，［１０］に変換されて圧縮データ１１Ａ〜１１Ｄに組み込まれる。一方、「Not  Match」の判定がなされた内容データ＜３＞，＜５＞，＜７＞，＜８＞，＜９＞，＜１１＞〜＜１８＞は、そのまま生データ［３］，［５］，［７］，［８］，［９］，［１１］〜［１８］として圧縮データ１１Ａ〜１１Ｄに組み込まれる。マッチング情報１５Ａ〜１５Ｄの構成は特に限定されるべきものではないが、例えば、圧縮データ１１内の対象となる区間の位置及び大きさを示す情報と「Match」であるか否かを示す情報との組み合わせを複数のビットにより示す情報等であってもよい。
【００３０】
図４は、第１の実施形態に係るハッシュテーブル３０及び圧縮辞書４０の構成を示す図である。同図において、１つの１６バイトデータブロック５１、２つの８バイトデータブロック５２、４つの４バイトデータブロック５３、及び８つの２バイトデータブロック５４が、ハッシュ関数（ハッシュ計算部２２）に入力され、各データブロック５１〜５４に関連するデータがハッシュテーブル３０及び圧縮辞書４０に入力されている状況が示されている。
【００３１】
ハッシュテーブル３０として、１つの８バイト／１６バイトハッシュテーブル３１、１つの４バイトハッシュテーブル３２、及び２つの２バイトハッシュテーブル３３Ａ，３３Ｂが形成されている。圧縮辞書４０として、１つの８バイト／１６バイト辞書４１、１つの４バイト辞書４２、及び２つの２バイト辞書４３Ａ，４３Ｂが形成されている。
【００３２】
１つの１６バイトデータブロック５１及び２つの８バイトデータブロック５２に関連するデータは、１つの８バイト／１６バイトハッシュテーブル３１及び１つの８バイト／１６バイト辞書４１に入力している。４つの４バイトデータブロック５３に関連するデータは、１つの４バイトハッシュテーブル３２及び１つの４バイト辞書４２に入力している。８つの２バイトデータブロック５４に関連するデータは、２つの２バイトハッシュテーブル３３Ａ，３３Ｂ及び２つの４バイト辞書４３Ａ，４３Ｂに入力している。
【００３３】
８バイト／１６バイトハッシュテーブル３１は、異なる複数のデータ長（８バイト及び１６バイト）間で共有される共有テーブルである。また、各ハッシュテーブル３１，３２，３３Ａ，３３Ｂは、それぞれ同一のデータ長（８バイト、４バイト、又は２バイト）を有する複数のデータブロック５２〜５４間で共有されている。
【００３４】
８バイト／１６バイト辞書４１は、異なる複数のデータ長（８バイト及び１６バイト）間で共有される共有辞書である。また、各圧縮辞書４１，４２，４３Ａ，４３Ｂは、それぞれ同一のデータ長（８バイト、４バイト、又は２バイト）を有する複数のデータブロック５２〜５４間で共有されている。
【００３５】
上記構成により、ハッシュテーブル３１，３２，３３Ａ，３３Ｂの数（４）及び圧縮辞書４１，４２，４３Ａ，４３Ｂの数（４）は、１つの入力データ１０から分割されるデータブロック５１〜５４の総数（１５）より少なくなる。これにより、ハッシュテーブルメモリ２３及び圧縮辞書メモリ２４の物理的記憶領域を削減することができる。
【００３６】
なお、図４においては、複数のデータブロック５１〜５４に対応する複数の矢印が各ハッシュ関数、各ハッシュテーブル３１，３２，３３Ａ，４４Ｂ、及び各圧縮辞書４１，４２，４３Ａ，４３Ｂにパラレルに入力するように描かれているが、実際には、各データブロック５１〜５４及びそれらに関連するデータは各ハッシュ関数、各ハッシュテーブル３１，３２，３３Ａ，４４Ｂ、及び各圧縮辞書４１，４２，４３Ａ，４３Ｂにシリアルに入力する。
【００３７】
図５は、比較例に係るハッシュテーブル１３０及び圧縮辞書１４０の構成を示す図である。本比較例においては、ハッシュテーブル１３０として、１つの１６バイトハッシュテーブル１３１、２つの８バイトハッシュテーブル１３２Ａ，１３２Ｂ、４つの４バイトハッシュテーブル１３３Ａ〜１３３Ｄ、及び８つの２バイトハッシュテーブル１３４Ａ〜１３４Ｈが形成されている。圧縮辞書１４０として、１つの１６バイト辞書１４１、２つの８バイト辞書１４２Ａ，１４２Ｂ、４つの４バイト辞書１４３Ａ〜１４３Ｄ、及び８つの２バイト辞書１４４Ａ〜１４４Ｈが形成されている。
【００３８】
本比較例においては、１５のデータブロック５１〜５４の各々に対応するように、１５のハッシュテーブル１３１，１３２Ａ，１３２Ｂ，１３３Ａ〜１３３Ｄ，１３４Ａ〜１３４Ｈ及び１５の圧縮辞書１４１，１４２Ａ，１４２Ｂ，１４３Ａ〜１４３Ｄ，１４４Ａ〜１４４Ｈが形成されている。また、全てのハッシュテーブル１３１，１３２Ａ，１３２Ｂ，１３３Ａ〜１３３Ｄ，１３４Ａ〜１３４Ｈは１つのデータブロックに占有され、全ての圧縮辞書１４１，１４２Ａ，１４２Ｂ，１４３Ａ〜１４３Ｄ，１４４Ａ〜１４４Ｈは１つのデータブロックに占有される。このような構成であると、ハッシュテーブル１３０及び辞書１４０を記憶するための膨大な物理的記憶領域が必要となる。
【００３９】
図６は、第１の実施形態に係るハッシュテーブルメモリ２３のメモリマップを示す図である。ハッシュテーブルメモリ２３上には、第１の２バイトハッシュテーブル３３Ａを記憶するための第１の２バイトハッシュテーブル領域６３Ａ、第２の２バイトハッシュテーブル３３Ｂを記憶するための第２の２バイトハッシュテーブル領域６３Ｂ、４バイトハッシュテーブル３２を記憶するための４バイトハッシュテーブル領域６２、及び８バイト／１６バイトハッシュテーブル３１を記憶するための８バイト／１６バイトハッシュテーブル領域６１が形成されている。
【００４０】
本例においては、全ての領域６１，６２，６３Ａ，６３Ｂの各エントリは８ビット（１バイト）のワード長を有している。各エントリ内に、ハッシュ値に対応するデータブロック５１，５２Ａ，５２Ｂ，５３Ａ〜５３Ｄ，５４Ａ〜５４Ｈの格納位置を示すアドレスを示すデータが記憶されている。なお、各領域６１，６２，６３Ａ，６３Ｂのワード長は８ビットに限られるものではなく、使用状況に応じて適宜設計されるべき事項である。圧縮辞書４０が大きくなるほど格納場所を特定するために必要なアドレスのデータ量も大きくなるため、圧縮辞書４０の大きさに合わせてワード長を増減させてもよい。
【００４１】
本例においては、２バイトハッシュテーブル領域６３Ａ，６３Ｂのアドレス範囲（エントリの数）は５１２である。４バイトハッシュテーブル領域６２のアドレス範囲は１０２４である。８バイト／１６バイトハッシュテーブル領域６１のアドレス範囲は２０４８（１０２４×２）である。これらのアドレス範囲は圧縮辞書４０の大きさに合わせて設定される。
【００４２】
８バイト／１６バイトハッシュテーブル領域６１のアドレス範囲の先頭位置から中間位置までの１０２４の領域は、８バイトのデータ長を有するデータブロック５２の格納場所を特定するアドレスを記憶するための８バイトハッシュテーブル領域６１Ａである。８バイト／１６バイトハッシュテーブル領域６１の中間位置から最終位置までの１０２４の領域は、１６バイトのデータ長を有するデータブロック５１を特定するアドレスを記憶するための１６バイトハッシュテーブル領域６１Ｂである。このように、８バイト／１６バイトハッシュテーブル領域６１は、異なるデータ長（８バイト及び１６バイト）間で共有される。
【００４３】
図７は、第１の実施形態に係る圧縮辞書メモリ２４のメモリマップを示す図である。圧縮辞書メモリ２４上には、第１の２バイト辞書４３Ａを記憶するための第１の２バイト辞書領域７３Ａ、第２の２バイト辞書４３Ｂを記憶するための第２の２バイト辞書領域７３Ｂ、４バイト辞書４２を記憶するための４バイト辞書領域７２、及び８バイト／１６バイト辞書４１を記憶するための８バイト／１６バイト辞書領域７１が形成されている。
【００４４】
本例においては、全ての領域７１，７２，７３Ａ，７３Ｂの各エントリは、入力データ１０のデータ長と同じ１２８ビット（１６バイト）のワード長を有している。各エントリ内に、各データブロック５１，５２Ａ，５２Ｂ，５３Ａ〜５３Ｄ，５４Ａ〜５４Ｈが記憶されている。なお、各領域７１，７２，７３Ａ，７３Ｂのワード長は必ずしも入力データ１０と同じワード長であることに限られるものではない。
【００４５】
本例においては、２バイト辞書領域７３Ａ，７３Ｂのアドレス範囲（エントリの数）は３２である。４バイト辞書領域７２のアドレス範囲は６４である。８バイト／１６バイト辞書領域７１のアドレス範囲は２５６である。これらのアドレス範囲は上記に限られるものではない。
【００４６】
８バイト／１６バイト辞書領域７１のアドレス範囲の先頭位置から中間位置までの領域は、入力データ１０を８バイトのデータ長に分割したデータブロック５２Ａ，５２Ｂを記憶するための８バイト辞書領域７１Ａである。８バイト／１６バイトハッシュテーブル領域７１の中間位置から最終位置までの領域は、入力バイト１０と同じデータ長を有するデータブロック５１を記憶するための１６バイト辞書領域７１Ｂである。このように、８バイト／１６バイト辞書領域７１は、異なるデータ長（８バイト及び１６バイト）間で共用されるように構成される。８バイト辞書領域７１Ａのエントリアドレスと１６バイト辞書領域７１Ｂのエントリアドレスとは連続して割り当てられている（本例では０ｘ００〜０ｘＦＦ）。８バイト辞書領域７１Ａのワード長と１６バイト辞書領域７１Ｂのワード長とは同一である（本例では１２８ビット）。
【００４７】
図８は、第１の実施形態に係る２バイトデータブロック５４におけるアドレス変換を示す図である。同図には、第１の２バイトハッシュテーブル３３Ａ及び第１の２バイト辞書４３Ａが示されている。
【００４８】
第１の２バイトハッシュテーブル３３Ａの各エントリにはエントリアドレス８１が割り当てられている。各エントリアドレス８１はハッシュ計算部２２により計算されたハッシュ値と一意に対応している。第１の２バイトハッシュテーブル３３Ａの各エントリには第１の２バイト辞書４３Ａ上の格納場所を示すアドレス８２が記憶されている。
【００４９】
アドレス８２は、辞書エントリ情報８３及びオフセット情報８４を含んでいる。辞書エントリ情報８３は、第１の２バイト辞書４３Ａのエントリアドレス９１を示す情報であり、本例では３２エントリを区別するために５ビットのＭＳＢ（Most  Significant  Bit）を要する。オフセット情報８４は、第１の２バイト辞書４３Ａの各エントリ内におけるワード方向のオフセットを示す情報であり、本例では８種類（ａ〜ｈ）のオフセットを区別するために３ビットのＬＳＢ（Least  Significant  Bit）を要する。
【００５０】
本例では、エントリアドレス８１「０ｘ０１」が割り当てられたエントリに辞書エントリ情報８３「０ｘ００」及びオフセット情報８４「ｂ」が記憶され、エントリアドレス８１「０ｘ０３」が割り当てられたエントリに辞書エントリ情報８３「０ｘ１ｆ」及びオフセット情報８４「ｈ」が記憶され、エントリアドレス８１「０ｘ０５」が割り当てられたエントリに辞書エントリ情報８３「０ｘ００」及びオフセット情報８４「ａ」が記憶され、エントリアドレス８１「０ｘ１ｆｅ」が割り当てられたエントリに辞書エントリ情報８３「０ｘ１ｆ」及びオフセット情報８４「ｆ」が記憶されている。このような第１の２バイトハッシュテーブル３３Ａを参照することにより、ハッシュ値に対応する２バイトデータブロック５４の２バイト辞書４３上の格納場所を特定することができる。第２の２バイトハッシュテーブル３３Ｂと第２の２バイト辞書４３Ｂとの関係についても同様である。
【００５１】
４バイトハッシュテーブル３２においては、４バイト辞書４２のエントリ数が６４であり、オフセットが４種類であるため、２バイトハッシュテーブル３３Ａ，３３Ｂと同様に、辞書エントリ情報８３を５ビットとし、オフセット情報８４を３ビットとすることができる。
【００５２】
８バイト／１６バイトハッシュテーブル３１においては、８バイトデータブロック５２Ａ，５２Ｂの２種類のオフセットを区別すればよいため、オフセット情報８４は１ビットで足りる。残りの７ビットを辞書エントリ情報８３に割り当てることにより、８バイト／１６バイト辞書４１の全２５６エントリの半分である１２８エントリを区別することができる。上記のような構成は循環記憶機構にも適用することができる。
【００５３】
図９は、第１の実施形態に係る復元部１００の構成を示す図である。復元部１００は、圧縮部２０により生成された圧縮データ１１を伸張して復元データ１２を生成するユニットである。復元部１００はデータ圧縮システム１に含まれてもよい。
【００５４】
復元部１００は、マッチング解析部１０１、復元辞書メモリ１０２（第２の辞書メモリ）、伸張部１０３、及び復元辞書更新部１０４（第２の更新部）を含む。
【００５５】
マッチング解析部１０１は、圧縮データ１１に含まれるマッチング情報１５Ａ〜１５Ｄに基づいて各圧縮データ１１における「Match」及び「Not  Match」の位置を解析する。圧縮データ１１内の「Match」の位置に相当するデータは、入力データ１０の生データがアドレスに変換されたデータである。圧縮データ１１内の「Not  Match」の位置に相当するデータは、入力データ１０の生データがそのままコピーされたデータである。
【００５６】
復元辞書メモリ１０２は、過去の復元データ１２を記憶する復元辞書１１０を記憶するメモリである。
【００５７】
伸張部１０３は、マッチング解析部１０１により解析された「Match」の位置に相当するデータ（アドレス）を復元辞書１１０に基づいて元の入力データ１０（生データ）に変換することにより、圧縮データ１１を伸張し、復元データ１２を生成する。
【００５８】
復元辞書更新部１０４は、新規の復元データ１２に基づいて復元辞書１１０を更新する。このとき、復元辞書更新部１０４は、マッチング解析部１０１から取得される生データ、アドレス等の情報を利用して復元データ１２を更新する。
【００５９】
図１０は、第１の実施形態に係る復元辞書メモリ１０２の構成を示す図である。図１１は、比較例に係る復元辞書メモリ１５１の構成を示す図である。図１０に示す本実施形態に係る復元辞書メモリ１０２は、全てのデータブロック間で共有されている。図１１に示す比較例に係る復元辞書メモリ１５１は、複数のデータブロックの各々に対応するように設けられている。比較例に係る復元辞書メモリ１５１の総数は１５（１つの１６バイト辞書メモリ、２つの８バイト辞書メモリ、４つの４バイト辞書メモリ、及び８つの２バイト辞書メモリ）となるのに対し、本実施形態に係る復元辞書メモリ１０２は１つである。
【００６０】
上記データ圧縮システム１の各種機能を実現させるプログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録されて提供することができる。また、プログラムは、ネットワークに接続された所定の記憶装置から所定の情報処理装置にダウンロードすることにより提供されてもよいし、予めＲＯＭ等に組み込まれて所定の情報処理装置に提供されてもよい。また、プログラムは、上記各種機能を実現する複数のモジュールから構成されてもよい。
【００６１】
上記のように、本実施形態によれば、異なるデータ長間で共有される共有テーブル（８バイト／１６バイトハッシュテーブル３１）及び共有辞書（８バイト／１６バイト辞書４１）が形成される。また、各ハッシュテーブル３１，３２，３３Ａ，３３Ｂ及び各圧縮辞書４１，４２，４３Ａ，４３Ｂは、同一のデータ長（８バイト、４バイト、又は２バイト）を有する複数のデータブロック５２〜５４間で共有される。これにより、ハッシュテーブル３０の数（４）及び圧縮辞書４０の数（４）が１つの入力データ１０から分割されるデータブロック５１〜５４の総数（１５）より少なくなる。これにより、ハッシュテーブルメモリ２３及び圧縮辞書メモリ２４の物理的記憶領域を増大させることなく、性能を向上させることが可能となる。
【００６２】
以下、他の実施形態について図面を参照して説明するが、第１の実施形態と同一又は同様の作用効果を奏する箇所については同一の符号を付してその説明を省略する場合がある。
【００６３】
（第２の実施形態）
図１２は、第２の実施形態に係るデータ圧縮システム１における読出し／書込み処理に要するサイクル数を示す図である。同図において、辞書構成２０１、データブロック構成２０２、及び読出し／書込みサイクル２０３が概念的に示されている。
【００６４】
ここでは、第１の２バイト辞書４３Ａを「Ｄｉｃｔ２Ｂａ」、第２の２バイト辞書４３Ｂを「Ｄｉｃｔ２Ｂｂ」、４バイト辞書４２を「Ｄｉｃｔ４Ｂ」、８バイト／１６バイト辞書４１を「ＤｉｃｔＸＢ」と称する。また、１６バイトデータブロック５１を「１６Ｂａ」、２つの８バイトデータブロック５２を「８Ｂａ」，「８Ｂｂ」、４つの４バイトデータブロック５３を「４Ｂａ」，「４Ｂｂ」，「４Ｃｂ」，「４Ｂｂ」、８つの２バイトブロック５４を「２Ｂａ」，「２Ｂｂ」，「２Ｂｃ」，「２Ｂｄ」，「２Ｂｅ」，「２Ｂｆ」，「２Ｂｇ」，「２Ｂｈ」と称する。
【００６５】
本実施形態においては、読出し／書込みサイクル２０３に示すように、全ての読出し／書込み処理が５サイクル以内で完了する。４バイトデータブロック５３及び２バイトデータブロック５４の読出し／書込み処理においては、各辞書４２，４３Ａ，４３Ｂからのデータ読出しに４サイクルを要し、各辞書４２，４３Ａ，４３Ｂの更新に１サイクルを要することが示されている。このように、本実施形態に係るデータ圧縮システム１は、読出し／書込み処理が所定のサイクル数以下となるように構成されている。
【００６６】
図１３は、第２の実施形態に係るデータ圧縮システム１における同一性判定処理の流れを示すフローチャートである。マッチング部２７は、先ず、新規の入力データ１０の１６バイトデータブロック５１について同一性を判定する（Ｓ１０１）。ステップＳ１０１において同一性が認められた場合（Ｙｅｓ）、マッチング数をインクリメントし（Ｓ１０２）、マッチング数が予め設定された最大マッチング数より小さいか否かを判定する（Ｓ１０３）。マッチング数が最大マッチング数より小さくない場合（Ｓ１０３：Ｎｏ）、同一性判定処理を終了し、その後更新部２５による圧縮辞書４０の更新（書込み処理）が行われる。
【００６７】
ステップＳ１０３において、マッチング数が最大マッチング数より小さい場合（Ｙｅｓ）、８バイトデータブロック５２のうちの１つについて同一性が判定される（Ｓ１０４）。ステップＳ１０４において同一性が認められた場合（Ｙｅｓ）、マッチング数をインクリメントし（Ｓ１０５）、マッチング数が最大マッチング数より小さいか否かを判定する（Ｓ１０６）。マッチング数が最大マッチング数より小さくない場合（Ｓ１０３：Ｎｏ）には同一性判定処理を終了し、小さい場合（Ｓ１０３：Ｙｅｓ）には８バイトデータブロック５２の全てについて同一性の判定が終了したか否かが判定される（Ｓ１０７）。
【００６８】
ステップＳ１０７において、判定が終了していない場合（Ｎｏ）にはステップＳ１０４に戻り、判定が終了している場合（Ｙｅｓ）には、４バイトデータブロック５３のうちの１つについて同一性が判定される（Ｓ１０８）。ステップＳ１０８において同一性が認められた場合（Ｙｅｓ）、マッチング数をインクリメントし（Ｓ１０９）、マッチング数が最大マッチング数より小さいか否かを判定する（Ｓ１１０）。マッチング数が最大マッチング数より小さくない場合（Ｓ１１０：Ｎｏ）には同一性判定処理を終了し、小さい場合（Ｓ１１０：Ｙｅｓ）には４バイトデータブロック５３の全てについて同一性の判定が終了したか否かが判定される（Ｓ１１１）。
【００６９】
ステップＳ１１１において、判定が終了していない場合（Ｎｏ）にはステップＳ１０８に戻り、判定が終了している場合（Ｙｅｓ）には、２バイトデータブロック５４のうちの１つについて同一性が判定される（Ｓ１１２）。ステップＳ１１２において同一性が認められた場合（Ｙｅｓ）、マッチング数をインクリメントし（Ｓ１１３）、マッチング数が最大マッチング数より小さいか否かを判定する（Ｓ１１４）。マッチング数が最大マッチング数より小さくない場合（Ｓ１１４：Ｎｏ）には同一性判定処理を終了し、小さい場合（Ｓ１１４：Ｙｅｓ）には２バイトデータブロック５４の全てについて同一性の判定が終了したか否かが判定される（Ｓ１１５）。
【００７０】
上記同一性判定処理により、読出し／書込み処理のサイクル数が最大マッチング数より大きくなることを防止することができる。これにより、実質的に不要な同一性判定処理を抑制し、良好なスループットを維持することが可能となる。
【００７１】
（第３の実施形態）
図１４は、第３の実施形態に係るデータ圧縮システム３０１の構成を示す図である。データ圧縮システム３０１は、圧縮部２０、復元部１００、比較部３１０、及びビットストリーム制御部３２０を含む。
【００７２】
比較部３１０は、入力データ１０と復元部１００から出力される復元データ１２とを比較する。
【００７３】
ビットストリーム制御部３２０は、比較部３１０による比較結果に基づいて、圧縮部２０からビットストリームとして出力される圧縮データ１１の出力を制御する。ビットストリーム制御部３２０は、比較部３１０によりエラーの発生（入力データ１０と復元データ１２との不一致）が検知された場合に、圧縮データ１１の出力を停止したり、エラー情報を加えて出力したりしてもよい。
【００７４】
上記構成により、圧縮データ１１の品質をリアルタイムで検証し、不具合の発生に迅速に対処することが可能となる。
【００７５】
（第４の実施形態）
図１５は、第４の実施形態に係るハッシュテーブル４３０及び圧縮辞書４４０の構成を示す図である。ハッシュテーブル４３０は、第１の２バイトハッシュテーブル３３Ａ及び第２の２バイトハッシュテーブル３３Ｂから構成される。圧縮辞書４４０は、第１の２バイト辞書４３Ａ及び第２の２バイト辞書４３Ｂから構成される。マッチング部４０１は、新規の２バイトデータブロック５４を、２バイトハッシュテーブル３３Ａ，３３Ｂから取得されたアドレスが示す格納場所に記憶された過去の２バイトデータブロック５４と比較するのみではなく、他のデータ長（例えば４バイト、８バイト、又は１６バイト）のデータブロックとも比較して同一性を判定する。
【００７６】
このような構成であっても、物理的記憶領域の増大を招くことなく、性能を向上させることができる。
【００７７】
以上、本発明の実施形態を説明したが、この実施形態は例として提示したものであり、発明の範囲を限定することを意図するものではない。この新規な実施形態はその他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。この実施形態及びその変形は発明の範囲及び要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００７８】
１，３０１  データ圧縮システム
１０  入力データ
１１，１１Ａ〜１１Ｄ  圧縮データ
１５Ａ〜１５Ｄ  マッチング情報
２０  圧縮部
２１  分割部
２２  ハッシュ計算部
２３  ハッシュテーブルメモリ
２４  圧縮辞書メモリ
２５  更新部
２６  アドレス取得部
２７，４０１  マッチング部
２８，４０２  符号化部
３０，４３０  ハッシュテーブル
３１  ８バイト／１６バイトハッシュテーブル
３２  ４バイトハッシュテーブル
３３Ａ，３３Ｂ  ２バイトハッシュテーブル
４０，４４０  圧縮辞書
４１  ８バイト／１６バイト辞書
４２  ４バイト辞書
４３Ａ，４３Ｂ  ２バイト辞書
５１  １６バイトデータブロック
５２，５２Ａ，５２Ｂ  ８バイトデータブロック
５３，５３Ａ〜５３Ｄ  ４バイトデータブロック
５４，５４Ａ〜５４Ｈ  ２バイトデータブロック
６１Ａ  ８バイトハッシュテーブル領域
６１Ｂ  １６バイトハッシュテーブル領域
６２  ４バイトハッシュテーブル領域
６３Ａ，６３Ｂ  ２バイトハッシュテーブル領域
７１Ａ  ８バイト辞書領域
７１Ｂ  １６バイト辞書領域
７２  ４バイト辞書領域
７３Ａ，７３Ｂ  ２バイト辞書領域
８１，９１  エントリアドレス
８２  アドレス
８３  辞書エントリ情報
８４  オフセット情報
１００  復元部
１０１  マッチング解析部
１０２  復元辞書メモリ
１０３  伸張部
１０４  復元辞書更新部
１１０  復元辞書
２０１  辞書構成
２０２  データブロック構成
２０３  読出し／書込みサイクル
３１０  比較部
３２０  ビットストリーム制御部
【図１】
0006523195.tif 000002
【図２】
0006523195.tif 000003
【図３】
0006523195.tif 000004
【図４】
0006523195.tif 000005
【図５】
0006523195.tif 000006
【図６】
0006523195.tif 000007
【図７】
0006523195.tif 000008
【図８】
0006523195.tif 000009
【図９】
0006523195.tif 000010
【図１０】
0006523195.tif 000011
【図１１】
0006523195.tif 000012
【図１２】
0006523195.tif 000013
【図１３】
0006523195.tif 000014
【図１４】
0006523195.tif 000015
【図１５】
0006523195.tif 000016