(57)【特許請求の範囲】
【請求項１】
現在の位置として入力ファイル内の最初のリテラル位置で開始して、
前記現在の位置でリテラルセットのハッシュ値を作成することであって、前記ハッシュ値は、前記リテラルセットよりも小さいビットを有する出力を有するハッシュ関数である、ことと、
ハッシュテーブル内の前記ハッシュ値におけるエントリを取得することと、
前記現在の位置にマップされた前記ハッシュチェイン内の位置に前記エントリを書き込むことと、
前記入力ファイル内の次のリテラル位置に前記現在の位置を進めることと、
を含む第一番目の動作を実施することによって、前記入力ファイル内の複数のリテラルセットのうちの各リテラルセットに対して、前記入力ファイルからハッシュチェインの作成を開始すること、
前記入力ファイルの終了に到達するまで、前記第一番目の動作を繰り返すこと、
前記リテラルセットが繰り返しリテラルではない場合、前記ハッシュテーブルに関連付けられたバッファの状態を評価することにより生成された、前記ハッシュテーブルに関連付けられた前記バッファがフルであるという判定に応じて、前記ハッシュチェインを作成する間、前記現在の位置で前記リテラルセットの前記ハッシュ値を生成することと、前記ハッシュテーブル内の前記ハッシュ値におけるエントリを取得することと、前記ハッシュチェイン内の位置に前記エントリを書き込むことを保留すること、および
前記入力ファイルの終了に到達した場合、前記ハッシュチェインを用いて、前記入力ファイルを圧縮すること、
を含む、方法。
【請求項２】
直前に先行するリテラルと同一であって、前記リテラルのある閾値数の連続インスタンスより小さいリテラルを前記リテラルセットが含むのに応じて、ハッシュの作成を抑制した状態で、前記入力ファイル内の次のリテラル位置を参照するために、前記現在の位置をインクリメントすること、をさらに含む、請求項１に記載の方法。
【請求項３】
前記ハッシュチェインを用いて前記入力ファイルを圧縮することは、Ｌｅｍｐｅｌ−Ｚｉｖアルゴリズムに従って、コピーまたはリテラルコマンドを作成することを含む、請求項１または２のいずれか一項に記載の方法。
【請求項４】
前記Ｌｅｍｐｅｌ−Ｚｉｖアルゴリズムに従ってコピーまたはリテラルコマンドを作成することは、各ストリングに対して、
前記各ストリングの最初の前記リテラルセットを同定することと、
前記最初のリテラルセットに対応するハッシュチェインを同定することと、
前記最初のリテラルセットに対応する前記ハッシュチェインにおいて参照された位置のみで限定的に、一つ以上の同一のストリングを検索することと、
によって、同一かつ以前出現したストリングを参照するコピーおよびオフセットコマンドで、コマンドセット内の前記入力ファイル内のストリングを置換することを含む、請求項３に記載の方法。
【請求項５】
前記コマンドセットをハフマン符号化することをさらに含む、請求項４に記載の方法。
【請求項６】
メモリバンクと電子デバイスとを備える、データを圧縮するための装置であって、
前記電子デバイスは、
現在の位置として入力ファイル内の最初のリテラル位置を設定し、かつ、第一番目の動作を実施することによって、前記入力ファイル内の複数のリテラルセットのうちの各リテラルセットに対して、前記入力ファイルからハッシュチェインを作成することであって、前記第一番目の動作が、
前記現在の位置でリテラルセットのハッシュ値を作成することと、
前記メモリバンク内の前記ハッシュ値におけるエントリを取得することと、
前記現在の位置にマップされた前記ハッシュチェイン内の位置に前記エントリを書き込むことと、
前記メモリバンク内の前記ハッシュ値で前記現在の位置を書き込むことと、
前記入力ファイル内の次のリテラル位置に前記現在の位置を進めることと、
を含む、ことと、
前記入力ファイルの終了に到達するまで、前記第一番目の動作を繰り返すことと、
前記ハッシュチェインを作成する間、前記入力ファイル内の先行するリテラルと同一のリテラルである繰り返しリテラルを前記リテラルセットが含むことを検出するのに応じて、前記第一番目の動作の一部を実施することを保留することと、
前記ハッシュチェインを出力することと、
を含む処理を前記装置に行わせるようにプログラムされる、装置。
【請求項７】
前記電子デバイスは、１５個の連続したリテラルに先行するリテラルと同一の１５個の連続したリテラルまでに対して、前記入力ファイル内の前記次のリテラル位置に前記現在の位置を進めることを実施する間、前記第一番目の動作の前記一部を実施することを保留するようにさらにプログラムされる、請求項６に記載の装置。
【請求項８】
前記電子デバイスは、コマンド作成モジュールに前記ハッシュチェインを出力し、前記入力ファイル内の繰り返しリテラルのストリングに対してコピーオフセットコマンドを含むコマンドファイルを作成するために、前記ハッシュチェインを処理するようにさらにプログラムされる、請求項７に記載の装置。
【請求項９】
前記コマンド作成モジュールは、前記リテラルの先行するインスタンスによって先行されるリテラルの連続したインスタンスのランを、前記入力ファイル内の前記先行するインスタンスに対するオフセットを記述するランレングスコマンドと、前記リテラルの連続したインスタンスの前記ラン内のリテラル数とで置換するようにさらにプログラムされる、請求項８に記載の装置。
【請求項１０】
前記コマンド作成モジュールは、Ｌｅｍｐｅｌ−Ｚｉｖアルゴリズムを実装する、請求項９に記載の装置。
【請求項１１】
前記電子デバイスは、ハフマン符号化を用いて前記コマンドファイルをエンコードするようにさらにプログラムされる、請求項１０に記載の装置。
【請求項１２】
ＦＩＦＯバッファをさらに含み、
前記電子デバイスは、前記バッファに書き込み要求を追加することと、前記バッファからの前記書き込み要求を処理することとによって、前記メモリバンク内の前記ハッシュ値に前記現在の位置を書き込むようにさらにプログラムされる、請求項６から１１のいずれか一項に記載の装置。
【請求項１３】
前記電子デバイスは、前記ハッシュチェインを作成する間、前記バッファがもはやフルではなくなるまで、前記入力ファイル内の前記次のリテラル位置に前記現在の位置を進めることを実施する間、前記バッファがフルであることを検出するのに応じて、前記第一番目の動作の前記一部を実施することを保留するようにさらにプログラムされる、請求項１２に記載の装置。
【請求項１４】
メモリバンクと、
前記メモリバンクに対応するバッファと、
電子デバイスと、
を備える、データを圧縮するための装置であって、
前記電子デバイスは、
現在の位置として入力ファイル内の最初のリテラル位置を設定し、かつ、第一番目の動作を実施することによって、前記入力ファイル内の複数のリテラルセットのうちの各リテラルセットに対して、前記入力ファイルからハッシュチェインを作成することであって、前記第一番目の動作が、
前記現在の位置でリテラルセットのハッシュ値を作成することと、
前記メモリバンク内の前記ハッシュ値におけるエントリを取得することと、
前記現在の位置にマップされた前記ハッシュチェイン内の位置に対する前記エントリの書き込みを要求する前記バッファに書き込み要求を追加することと、
前記バッファからの前記書き込み要求を実行することと、
前記メモリバンク内の前記ハッシュ値で前記現在の位置を書き込むことと、
前記入力ファイル内の次のリテラル位置に前記現在の位置を進めることと、
を含む、ことと、
前記入力ファイルの終了に到達するまで前記第一番目の動作を繰り返すことと、
前記ハッシュチェインを作成する間、前記バッファがフルではなくなるまで、前記入力ファイル内の前記次のリテラル位置に前記現在の位置を進めることを実施する間、前記バッファがフルであることを検出するのに応じて、前記第一番目の動作の一部を実施することを保留することと、
前記ハッシュチェインを出力することと、
を含む処理を前記装置に行わせるようにプログラムされる、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願］
本出願は、２０１４年８月１２日に出願され、“Ａｄａｐｔｉｖｅ  Ｒａｔｅ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｈａｓｈ  Ｐｒｏｃｅｓｓｏｒ”と題された米国仮特許出願整理番号６２／０３６，４５３に対する優先権を享受する権利を主張する。
【０００２】
本発明は、データを圧縮するためのシステムおよび方法に関する。
【背景技術】
【０００３】
ソフトウェア圧縮は、非常によく理解され、ＧＺＩＰのようなプログラムのためのソースコードは、パブリックドメインにおいて容易にアクセス可能である。ＧＺＩＰ圧縮がＤＥＦＬＡＴＥ［２］アルゴリズムおよびハフマン符号化［３］に基づく場合には、圧縮を実装するためのアルゴリズムは、高帯域幅の用途に対してはハードウェアで行うには比較的複雑である。圧縮の背景にある考えは、データストリーム内でより早期に現れる、データストリーム内でのその後のコピーコマンドを使用することである。このように、全ての圧縮の実装は、検索履歴バッファと、ある種の比較長さ関数とを必要とし、コピーコマンド用に用いることができる最長の長さを判定する。以前の履歴内でマッチする検索を実装するための一方法は、圧縮されるデータストリームを比較するために用いられることができる固定値に、可変長のストリングをマップするハッシュ関数を実装することである。
【０００４】
図１は、ＧＺｉｐのための圧縮アルゴリズムの機能的なハードウェアブロック図を表す。入力データ１０２は、例えば、ＬＺ７／ＬＺ８アルゴリズムを実装するモジュール１０８のハッシュモジュール１０４によってハッシュされる。ハッシュされたデータは、Ｌｅｍｐｅｌ−Ｚｉｖ［４］アルゴリズムまたは比較可能アルゴリズム毎に、ＬＺ  ＣＭＤモジュール１０８によってコピーまたはリテラルコマンドを作成するために比較される。圧縮されるデータ用の統計が集められると、それらはハフマン符号化され、その後、圧縮された出力データ１１０として送出されるために圧縮される。
【０００５】
本明細書に開示されたシステムおよび方法は、入力データをハッシュするための改良された方法を提供する。
【図面の簡単な説明】
【０００６】
本発明の利点を容易に理解するために、簡潔に上述された本発明のより詳細な記述は、添付の図面内に示された特定の実施形態を参照することによって与えられるだろう。これらの図面は、本発明の典型的な実施形態を示しているにすぎないため、その範囲を限定するものとして考えられるべきではないことを理解したうえで、本発明は、添付の図面を通じてさらに具体的かつ詳細に記述され、説明されるだろう。
【図１】従来技術による圧縮スキームを実装するためのコンポーネントの概略ブロック図である。
【図２】本発明の一実施形態による、ハッシュおよびハッシュチェインの作成を示す図である。
【図３】本発明の一実施形態により、ハッシュチェインを作成するための方法のプロセスフロー図である。
【図４】本発明の一実施形態による、ハッシュを実装するための回路の概略ブロック図である。
【図５】本発明の一実施形態による、ハッシュ抑制を実装するためのデバイスの概略ブロック図である。
【図６】本発明の一実施形態による、ハッシュ抑制用の方法のプロセスフロー図である。
【図７】本発明の一実施形態による方法を実装するために適切なコンピュータシステムの概略ブロック図である。
【発明を実施するための形態】
【０００７】
本発明のコンポーネントは、本明細書の図面に一般的に記述されて示されるように、異なる様々な構成で配置され、設計されることができることは容易に理解されるだろう。したがって、本発明の実施形態の以下のより詳細な記述は、図面に表されるように、請求されるような本発明の範囲を限定することを意図するものではないが、本発明により現在考えられる実施形態のある例の単なる代表例に過ぎない。現在記述される実施形態は、図面に対する参照によって最良に理解され、類似部分は、図面を通して類似の参照番号によって指定される。
【０００８】
本発明は、本技術分野の現在の状態に応じて、より詳細には、現在利用可能な装置および方法によって完全に解決されてはいない本技術分野における問題点およびニーズに応じて開発されたものである。
【０００９】
非一時的媒体を含む、コンピュータ使用可能またはコンピュータ可読媒体のうちの一つ以上の任意の組み合わせが使用されてもよい。例えば、コンピュータ可読媒体は、ポータブルコンピュータディスケット、ハードディスク、ランダムアクセスメモリ（ＲＡＭ）デバイス、リードオンリーメモリ（ＲＯＭ）デバイス、消去可能プログラマブルリードオンリーメモリ（ＥＰＲＯＭまたはフラッシュメモリ）デバイス、ポータブルコンパクトディスクリードオンリーメモリ（ＣＤＲＯＭ）、光学記憶デバイスおよび磁気記憶デバイスのうちの一つ以上を含むことができる。選択された実施形態においては、コンピュータ可読媒体は、命令実行システム、装置もしくはデバイスによる使用のために、または命令実行システム、装置もしくはデバイスと接続して、プログラムを包含し、格納し、通信し、伝搬し、または伝送することができる任意の非一時的媒体を含むことができる。
【００１０】
本発明の動作を実行するためのコンピュータプログラムコードは、Ｊａｖａ、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋などのオブジェクト指向プログラミング言語、“Ｃ”プログラミング言語などの従来の手続き型プログラミング言語または同様のプログラミング言語を含む、一つ以上のプログラミング言語の任意の組み合わせで書かれることができる。プログラムコードは、スタンドアロンソフトウェアパッケージとしてコンピュータシステム上で全体として、スタンドアロンハードウェアユニット上で、コンピュータからある距離だけ離された遠隔コンピュータ上で部分的に、または遠隔コンピュータもしくはサーバで全体として、実行することが出来る。後者の状況においては、遠隔コンピュータは、ローカルエリアネットワーク（ＬＡＮ）もしくはワイドエリアネットワーク（ＷＡＮ）を含む任意の種類のネットワークを通じてコンピュータに接続されることが出来、または、接続は、（例えば、インターネットサービスプロバイダを用いてインターネットを通じて）外部コンピュータに対して行われることができる。
【００１１】
本発明は、本発明の一実施形態による方法、装置（システム）およびコンピュータプログラム製品のフローチャート図および／またはブロック図を参照して以下に記述される。フローチャート図および／またはブロック図の各ブロック、ならびにフローチャート図および／またはブロック図におけるブロックの組み合わせは、コンピュータプログラム命令またはコードによって実装されることができることが理解されるだろう。これらのコンピュータプログラム命令は、汎用コンピュータ、専用コンピュータまたはマシンを作成するための他のプログラマブルデータ処理装置のプロセッサに提供されることが出来、コンピュータもしくは他のプログラマブルデータ処理装置のプロセッサを介して実行する命令が、フローチャートおよび／またはブロック図の一つ以上のブロックで特定される機能／動作を実装するための手段を作成するようにする。
【００１２】
これらのコンピュータプログラム命令は、また、特定の方法で機能するようにコンピュータまたは他のプログラマブルデータ処理装置に命令することができる非一時的コンピュータ可読媒体内に格納されることも出来、コンピュータ可読媒体内に格納される命令が、フローチャートおよび／またはブロック図の一つ以上のブロックで特定される機能／動作を実装する命令手段を含む製造の態様を作成するようにする。
【００１３】
コンピュータプログラム命令は、また、コンピュータ実装されたプロセスを作成するために、コンピュータまたは他のプログラマブル装置上で一連の動作ステップを実施させるために、コンピュータまたは他のプログラマブルデータ処理装置上にロードされることも出来、コンピュータまたは他のプログラマブル装置上で実行する命令が、フローチャートおよび／またはブロック図の一つ以上のブロックで特定される機能／動作を実装するためのプロセスを提供するようにする。
【００１４】
図２および図３を参照すると、ハッシュ２００は、Ｌｅｍｐｅｌ−Ｚｉｖ（ＬＺ）アルゴリズムおよび他の圧縮派生物毎に、その後圧縮されるべきファイル、ストリングまたは他のデータセット２０２のうちの大部分または全ての可能性のある参照を迅速にインデックス化するために用いられる。作成され得るハッシュテーブル２０４およびハッシュチェイン２０６の一例が図２に示される。ハッシュテーブル２０４およびハッシュチェイン２０６の追加は、図３の方法３００を用いて実施されることができる。本明細書に開示された方法により作成されるようなハッシュテーブル２０４およびハッシュチェイン２０６は、本技術分野で既知の任意の方法、具体的には、ＬＺアルゴリズムに従って、元のデータセット２０２を圧縮するために処理されることができる。
【００１５】
ステップ３０２において、現在位置Ｐにおけるリテラル対Ｎが取得される。第一のリテラル対Ｐに対しては、ゼロに等しくすることができる。図２の例においては、位置Ｐは、Ｘに等しく、Ｎは‘ａｂ’に等しい。方法３００は、リテラルＮについてハッシュチェインの作成が抑制されるべきか否かを判定すること３０４を含むことができる。これは、図５の方法６００を実行することを含むことができる。ハッシュ値を計算することが抑制されるべきと見出されない場合３０４には、方法３００は、リテラル対Ｎのハッシュ、即ち、Ｈａｓｈ（Ｎ）を作成すること３０６を含むことが出来、ここでＨａｓｈ（）は、ハッシング関数である。例示的なハッシング関数および実装回路は、図４に示される。
【００１６】
アドレスＨａｓｈ（Ｎ）におけるハッシュテーブル２０４におけるエントリＥは、その後、ルックアップ（検索）される３０８。図２の例においては、Ｅの値は、リテラル対‘ａｂ’の第一の出現に対してゼロである。例えば、ハッシュテーブル２０４は、方法３００により処理される各セクタまたはデータファイルに対して、ゼロに初期化されることができる。
【００１７】
Ｅの値は、位置Ｐにおいてハッシュチェイン２０６に、その後格納されることができる３１０。図２の例においては、値０が‘ａｂ’の第一のインスタンスに対して、ハッシュチェイン２０６における位置Ｘに格納される。Ｐの値は、また、ハッシュテーブル２０４におけるアドレスＨａｓｈ（Ｎ）に書き込まれることもできる３１２。図示された例においては、Ｘの値は、ハッシュテーブル２０４におけるアドレスＨａｓｈ（‘ａｂ’）に書き込まれることができる。
【００１８】
位置Ｐが、最終のリテラルまたはリテラル対の位置である場合、データファイルは、完了されていることがわかり３１４、方法は終了するだろう。さもなければ、Ｐの値は、次のリテラル、即ち、Ｐ＝Ｐ＋１リテラル位置にインクリメントされ、方法はステップ３０２で継続するだろう。例えば、ストリング‘ａｂｃｄ’に対して、リテラル対‘ａｂ’は、Ｐ＝０でまず処理されるだろう。Ｐ＝１において、リテラル対‘ｂｃ’が処理されるだろう、などである。ステップ３１４およびステップ３１６は、図３に示されるように、ハッシュが抑制されるべきことが判定されるとき３０４であっても、実行されることが出来る。
【００１９】
図２の例においては、ステップ３０４−３１２の次の繰り返しの結果、位置Ｙにおける次の‘ａｂ’の出現を検出するのに応じて、アドレスＨａｓｈ（‘ａｂ’）からＸの値が取得されるだろう。したがって、Ｘはハッシュチェイン２０６における位置Ｙに書き込まれ、Ｙは、ハッシュテーブル内のアドレスＨａｓｈ（‘ａｂ’）に書き込まれる。
【００２０】
位置Ｚにおける次の‘ａｂ’の出現を検出するのに応じて、値Ｙは、ハッシュテーブル２０４内のアドレスＨａｓｈ（‘ａｂ’）から取得される。従って、Ｙは、ハッシュチェイン２０６内の位置Ｚに書き込まれ、Ｚは、ハッシュテーブル内のアドレスＨａｓｈ（‘ａｂ’）に書き込まれる。
【００２１】
容易に明らかなように、ハッシュテーブル２０４およびハッシュチェイン２０６は、ここで、同一のリテラル対の一つ以上のその後の出現に対して、リテラル対の最初の出現を関連付ける。位置Ｘにおけるハッシュチェイン内の値は、位置Ｙを指す。したがって、値Ｈａｓｈ（‘ａｂ’）を与える対の位置に対応するハッシュチェイン２０６内のリテラル‘ａｂ’ポインタで開始するストリングを検索するときは、元のデータセット全体を評価する必要なく、その後に続くことが出来る。上述されたように、ハッシュテーブル２０４および／またはハッシュチェイン２０６が元のデータセットを圧縮するために処理される方法は、ＬＺアルゴリズムなどの本技術分野で既知の任意の方法を含むことができる。
【００２２】
図４を参照すると、ハッシュ関数（Ｈａｓｈ（））は、２バイトに対して存在し得る合計６４Ｋの確率のうちのサブセットである決定性インデックスを作成するのに役立つ。例えば、８ビットの２バイト（例えば、Ｂｙｔｅ０およびＢｙｔｅ１）は、２＾８の可能性のある文字および（２＾８）＊（２＾８）＝６４ＫＢの文字のうちの可能性のある組み合わせを各々表すことができる。ハッシュ関数は、２つの異なるバイトの組み合わせのうちの１／８の確率で、２＾１３または８Ｋの可能性のある組み合わせに、要求された検索スペースを減少させる１３ビットハッシュを作成する。その結果、任意のランダムな２バイトの組み合わせに対して同一のハッシュ値を生じる。
【００２３】
ハッシュ値を作成するための回路の一例が図４に示される。明らかなように、バイト４００、４０２のうちのビット７−０は、１３個のＸＮＯＲゲート４０４のアレイに対する入力である。明らかなように、位置Ｎにおけるバイト４０２のうちの１ビットが、ＸＮＯＲゲートに対する入力であり、Ｎ＋３＜＝７の場合には位置Ｎ＋３におけるビットであり、Ｎ＋３＞７の場合には位置Ｎ＋３−７の位置におけるビットである。同様に、バイト４００のうちの位置Ｎにおける各ビットは、ＸＮＯＲゲートに対する入力であり、Ｎ＝４まで、Ｎの値に対して位置Ｎ＋３の位置におけるビットである。
【００２４】
図５を参照すると、ハッシュ値を計算することはバイトに基づくため、方法３００により複数のハッシュを処理するための課題は、複数のメモリバンクを有するハッシュプロセッサを用いることによって達成されることが出来、領域内で大きなオーバーヘッドなしで複数の同時の書き込みを可能とする。なぜなら、メモリバンクに対して単一のポートメモリが用いられることができるからである。同一のメモリバンクに複数対のバイトが書き込まれるとき、ハッシュ衝突の重要性を処理するためにＦＩＦＯが用いられることができる。ＦＩＦＯがフルになると、ハッシュプロセッサは、ハッシュ計算およびハッシュチェイニング動作（例えば、図３の方法３００）をオフにする。ハッシュ計算およびハッシュチェイニングをオフにすることによって、圧縮率を縮小させる。なぜなら、新しいハッシュ値が作成されず、それによって、ＬＺアルゴリズム毎にコピーするためにその後インデックス化されることが出来ないからである。
【００２５】
ハッシュプロセッサ５００は、図５に示される回路５００を用いて動作することが出来、各バイト対に対してハッシュ値を計算する。例えば、ハッシュプロセッサ５００は、ＦＩＦＯ５０６がフルになるとき、および書き込みに対してバンク衝突が存在するときを検出するために、ハッシュ制限エンジン５０４を用いることが出来、フルのＦＩＦＯ５０６に対応するＳＲＡＭハッシュバンク５０８に対するハッシュ作成を抑制し、それによって、ＦＩＦＯ５０６が排出することを可能とすることができるようにする。ハッシュを抑制することによって、ハッシュプロセッサ５００は圧縮率に対して、最小コストで高スループットを維持することができる。圧縮のうち無視できる程度の量のみが失われる。なぜなら、新しいハッシュ値は、データが既にそれほど圧縮可能ではないことを意味するからである。ハッシュプロセッサ５００が繰り返されるリテラルに遭遇すると、コピーコマンドを作成するために用いられるハッシュチェイニングのためのハッシュ衝突数を最小化するために、同一のリテラル文字のうちの１６バイトまで、ハッシュ作成を抑制するためにリテラルランレングスエンジン５１０を用いる。
【００２６】
幾つかの実施形態においては、ハッシュデータを作成するために、メモリのうちの８個のバンク５０８と、効率的に４個のハッシュ値を作成する５個の２バイトの対を処理するために必要とされるスムージング機能が、８個のＦＩＦＯ５０６とともに用いられることが出来る。各スムージングＦＩＦＯ５０６は、４個のハッシュのみが計算されるときに、ハッシュ衝突を処理するために、書き込みメモリの８個のバンク５０８に対して１６個のディープＦＩＦＯとして実装されることができる。格納される必要がある、必要とされるハッシュの数より多い限り、ハッシュ値を計算される任意のリテラル対に対するハッシュ衝突のスムージング機能を生成するために、如何なる数のＦＩＦＯ５０６とともに、メモリのうちの如何なる数のバンク５０８が用いられてもよい。例えば、より狭い帯域幅を必要とする用途に対しては、例示的実装における８個ではなく、２個のハッシュが、４個のバンク５０８書き込みおよびＦＩＦＯ５０６を用いて作成されることができる。スムージングＦＩＦＯ５０６は、ハッシュ処理が停止される前に、１６よりもよりディープか、またはよりシャロウに実装されることができる。なぜなら、図６の方法６００で要約されたように、ＦＩＦＯ５０６がフルであるからである。
【００２７】
ハッシュプロセッサ５００は、図６に示される方法６００を実装することができる。例えば、データファイルまたはストリングの圧縮は、ステップ６０２で開始することが出来、図３の方法３００により、ハッシュおよびハッシュチェインを作成すること６０４を含むことができる。同一のリテラル即ち、繰り返しリテラルが見つかった場合６０６、方法６００は、それが１６番目の連続繰り返しリテラルであるか否かを判定することを含むことができる。そうでない場合、そのリテラルのハッシュを作成することは、１６番目の連続繰り返しリテラルまで抑制されることができる６１０。ストリングまたはファイル内のデータが終了したと判定される場合６１２、ＬＺマッチングプロセス５１４にデータが送信され６１４、それによって、ハフマン符号化または他のあるアプローチに従って、符号化の準備として、コマンドファイルにおけるコピー／リテラルコマンドを有するリテラルを置換する。上述されたようなストリングまたはファイル内で同定された繰り返しリテラルのランは、繰り返しリテラルの数および繰り返しリテラルの第一のインスタンスの位置に対するオフセットで、繰り返しリテラルを置換する“ランレングス”リテラルで置換されることができる。幾つかの実施形態においては、単一の文字リテラルラン、即ち、繰り返しリテラルのランに対するコマンドファイル内のランレングスは、１６文字の倍数のオフセットに常に指すように抑制されることがある。このように、ランレングスコピーコマンドは、９０パーセントより大きい圧縮率を提供し、それによって圧縮率とランレングスコピーコマンドを実装する複雑性との間の良好なバランスを提供する。
【００２８】
幾つかの実施形態においては、ステップ６０６−６１０のランレングスハッシュ抑制は、マッチングレングスウインドウに関連付けられた一つおきの文字、またはｎ個おきの文字に限定されることができる。例えば、評価６０６および可能な抑制６１０は、一つおきの文字、またはｎ個おきの文字で実施されることが出来、ここで、ｎは、２より大きい整数である。幾つかの実施形態においては、繰り返しリテラルのストリングを示すランレングスコマンドは、繰り返しリテラルのストリングまたは、繰り返しリテラルのストリングからオフセットされた複数のリテラル位置の直前に先行する、繰り返しリテラルの最初のインスタンスを指すことができる。したがって、リテラルが繰り返されることを決定すること６０６は、方法６００の現在の繰り返しで処理されるリテラルに先行するあらゆる任意のオフセットで、そのリテラルが繰り返されるか否かを評価することを含むことができる。
【００２９】
より多くのデータがファイルまたはストリング内に残っていると分かった場合６１２、処理は、ストリングまたはファイル内の次のリテラル対についてステップ６０４で継続する。
【００３０】
方法６００は、ハッシュバンク５０８に対するＦＩＦＯバッファ５０６がフルであるか否かを判定すること６１６をさらに含むことができる。そうである場合、そのＦＩＦＯバッファ５０６に対するハッシュ処理は、オフにされることが出来６１８、ステップ６１２で処理が継続する。そうでない場合には、方法は、ストリングまたはファイルのデータが全て処理されたか否かを判定すること６１２を含むことが出来、そうでない場合、ハッシュおよびハッシュチェインの作成がステップ６０４で継続することが出来る。さもなければ、ステップ６１４は、ストリングまたはファイルに対して実施される。
【００３１】
図７は、例示的コンピューティングデバイス７００を示すブロック図である。コンピューティングデバイス７００は、本明細書で議論されたような様々な手順を実施するために用いられることができる。コンピューティングデバイス７００は、サーバ、クライアントまたは任意の他のコンピューティングエンティティとして機能することが出来る。コンピューティングデバイスは、本明細書で議論されるように様々な機能を実施することができる。コンピューティングデバイス７００は、デスクトップコンピュータ、ノートブックコンピュータ、サーバコンピュータ、ハンドヘルドコンピュータ、タブレットコンピュータなどの様々なコンピューティングデバイスのうちのいかなるものであってもよい。幾つかの実施形態においては、本明細書に開示された方法を実装する回路を含むハードウェアデバイスは、コンピューティングデバイス７００に含まれてもよく、または、以下に記載されたコンピューティングデバイスのコンポーネントのうちのいずれかに内蔵されてもよい。
【００３２】
コンピューティングデバイス７００は、一つ以上のプロセッサ７０２と、一つ以上のメモリデバイス７０４と、一つ以上のインターフェイス７０６と、一つ以上のマスストレージデバイス７０８と、一つ以上の入力／出力（Ｉ／Ｏ）デバイス７１０と、ディスプレイデバイス７３０とを含み、その全てはバス７１２に結合される。（複数の）プロセッサ７０２は、（複数の）メモリデバイス７０４および／または（複数の）マスストレージデバイス７０８に格納された命令を実行する一つ以上のプロセッサまたはコントローラを含む。（複数の）プロセッサ７０２は、また、キャッシュメモリなどの様々な種類のコンピュータ可読媒体も含むことができる。
【００３３】
（複数の）メモリデバイス７０４は、揮発性メモリ（例えば、ランダムアクセスメモリ（ＲＡＭ）７１４）および／または不揮発性メモリ（例えば、リードオンリーメモリ（ＲＯＭ）７１６）などの様々なコンピュータ可読媒体を含む。（複数の）メモリデバイス７０４は、また、フラッシュメモリなどの書き換え可能なＲＯＭも含むことができる。
【００３４】
（複数の）マスストレージデバイス７０８は、磁気テープ、磁気ディスク、光ディスク、ソリッドステートメモリ（例えば、フラッシュメモリ）などの様々なコンピュータ可読媒体を含む。図７に示されるように、特定のマスストレージデバイスはハードディスクドライブ７２４である。様々なドライブは、また、様々なコンピュータ可読媒体からの読み出しおよび／または様々なコンピュータ可読媒体への書き込みを可能とするために、（複数の）マスストレージデバイス７０８に含まれることもできる。（複数の）マスストレージデバイス７０８は、リムーバブル媒体７２６および／または非リムーバブル媒体を含む。
【００３５】
（複数の）Ｉ／Ｏデバイス７１０は、データおよび／または他の情報をコンピューティングデバイス７００に入力するか、またはコンピューティングデバイス７００から取得することを可能とする様々なデバイスを含む。例示的な（複数の）Ｉ／Ｏデバイス７１０は、カーソル制御デバイス、キーボード、キーパッド、マイクロフォン、モニタまたは他のディスプレイデバイス、スピーカ、プリンタ、ネットワークインターフェイスカード、モデム、レンズ、ＣＣＤまたは他の画像捕捉デバイスなどを含む。
【００３６】
ディスプレイデバイス７３０は、コンピューティングデバイス７００の一人以上のユーザに情報を表示することが可能なあらゆる種類のデバイスを含む。ディスプレイデバイス７３０の例は、モニタ、ディスプレイ端子、ビデオ投影デバイスなどを含む。
【００３７】
（複数の）インターフェイス７０６は、コンピューティングデバイス７００が他のシステム、デバイスまたはコンピューティング環境と相互作用することを可能とする様々なインターフェイスを含む。（複数の）例示的インターフェイス７０６は、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、無線ネットワークおよびインターネットなどのあらゆる数の様々なネットワークインターフェイス７２０を含む。他の（複数の）インターフェイスは、ユーザインターフェイス７１８および周辺デバイスインターフェイス７２２を含む。（複数の）インターフェイス７０６は、また、一つ以上のユーザインターフェイス素子７１８も含むことができる。（複数の）インターフェイス７０６は、また、プリンタ、ポインティングデバイス（マウス、トラックパッドなど）、キーボードなどに対するインターフェイスなどの一つ以上の周辺機器インターフェイスも含むことができる。
【００３８】
バス７１２は、（複数の）プロセッサ７０２、（複数の）メモリデバイス７０４、（複数の）インターフェイス７０６、（複数の）マスストレージデバイス７０８、（複数の）Ｉ／Ｏデバイス７１０が、相互に、また、バス７１２に結合された他のデバイスもしくはコンポーネントと通信することを可能とする。バス７１２は、システムバス、ＰＣＩバス、ＩＥＥＥ１３９４バス、ＵＳＢバスなどの、幾つかの種類のバス構造のうちの一つ以上を表す。
【００３９】
例示の目的のために、プログラムおよび他の実行可能なプログラムコンポーネントが別個のブロックとして本明細書に示されているが、このようなプログラムおよびコンポーネントは、コンピューティングデバイス７００の異なるストレージコンポーネント内に様々な時点で存在することが出来、（複数の）プロセッサ７０２によって実行されることが理解される。あるいは、本明細書に記述されたシステムおよび手順は、ハードウェア、またはハードウェア、ソフトウェアおよび／もしくはファームウェアの組み合わせで実装されることができる。例えば、一つ以上の特定用途向け集積回路（ＡＳＩＣ）は、本明細書に記述されたシステムおよび手順のうちの一つ以上を実行するためにプログラムされることが出来る。
【００４０】
本発明は、その精神または本質的特性から逸脱することなく、他の特定の形式で具現化されることができる。記述された実施形態は、全ての点で例示的なものとしてのみ考えられるべきであって、限定的なものとして考えられるべきではない。したがって、本発明の範囲は、前述の記述によってではなく、添付の請求項によって示される。請求項の均等物の意味および範囲内にある全ての変更は、その範囲内に包含されるべきである。
【００４１】
［参考文献］
[1].    J. Gailly and M. Adler, GZIP: The Data Compression Program, 1993, http://www.gzip.org/.
[2]     DEFLATE Compressed Data Format Specification version 1.3. IETF. May 1996. p. 1. sec. Abstract. RFC 1951. Retrieved 11 Nov. 2012. 
[3]     D. A. Huffman, "A method for the construction of minimum-redundancy codes" Proc. IRE 40 (9). pp. 1098-1101. 1952. 
[4].    Ziv, J.; Lempel, A. (1978). "Compression of individual sequences via variable-rate coding". IEEE Transactions on Information Theory 24 (5): 530.
【図１】
0006770506.tif 000002
【図２】
0006770506.tif 000003
【図３】
0006770506.tif 000004
【図４】
0006770506.tif 000005
【図５】
0006770506.tif 000006
【図６】
0006770506.tif 000007
【図７】
0006770506.tif 000008