(57)【要約】方法は、データ圧縮スキームの辞書を増強する。各々の入力文字列に対し、スライディングウインドウ探索の結果は、辞書探索の結果と比較される。スライディングウインドウ探索結果が辞書探索結果よりも長い場合、スライディングウインドウ探索結果により辞書が増強される。開示の実施形態は、複数のスライディングウインドウを実装し、各々のスライディングウインドウは、関連するサイズを有し、スライディングウインドウのサイズは、対応する一致長に依存する。１つの実施形態について、各々のスライディングウインドウは、一致長に基づいた対応するハッシュ関数を有する。【選択図】図１
2021527376.tif 000002
【特許請求の範囲】
【請求項１】
動的辞書をスライディングウインドウと組み合わせる圧縮方法であって、
入力データ文字列を含む入力データを受信することと、
スライディングウインドウに包含されるデータに一致する入力データの最長文字列を判定するよう、前のデータの前記スライディングウインドウにわたって文字列一致探索を実行することと、
前記動的辞書に参照として包含される入力データの最長文字列を判定するよう、前記動的辞書にわたって辞書探索を実行することと、
前記スライディングウインドウに包含されるデータに一致する入力データの前記最長文字列の長さを、前記動的辞書に参照として包含される入力データの前記最長文字列の長さと比較することと、
前記動的辞書内でエントリを作成することであって、前記エントリは、前記スライディングウインドウに包含されるデータに一致する入力データの前記最長文字列が、前記動的辞書に参照として包含される入力データの前記最長文字列よりも長い場合のみ作成される、前記作成することと、
を備えた、前記方法。
【請求項２】
前記スライディングウインドウは、複数のスライディングウインドウの１つであり、前記複数のスライディングウインドウの各々は、対応する一致長を有する、請求項１に記載の方法。
【請求項３】
（削除）
【請求項４】
（削除）
【請求項５】
スライディングウインドウデータ圧縮方法であって、
複数のデータ文字列一致長を判定することと、
連続したデータ文字列一致長の組に対する対応するスライディングウインドウを実装することであって、前記対応するスライディングウインドウの各々のサイズは、前記対応する一致長に依存している、前記実装することと、
を備えた、前記スライディングウインドウデータ圧縮方法。
【請求項６】
最小データ文字列一致長は、５ビットの十分に小さいウインドウの下で圧縮可能である、２バイトである、請求項５に記載のスライディングウインドウデータ圧縮方法。
【請求項７】
前記スライディングウインドウの各々は、対応するハッシュ関数及びハッシュチェーンを有する、請求項５に記載のスライディングウインドウデータ圧縮方法。
【請求項８】
（削除）
【請求項９】
前記スライディングウインドウ方法は、辞書に基づく方法であり、前記方法は更に、
入力データ文字列を含む入力データを受信することと、
各々のスライディングウインドウに包含されるデータに一致する入力データの最長文字列を判定するよう、前のデータの各々のスライディングウインドウにわたって文字列一致探索を実行することと、
前記動的辞書に参照として包含される入力データの最長文字列を判定するよう、前記動的辞書にわたって辞書探索を実行することと、
各々のスライディングウインドウに包含されるデータに一致する入力データの前記最長文字列の長さを、前記動的辞書に参照として包含される入力データの前記最長文字列の長さと比較することと、
各々のスライディングウインドウに包含されるデータに一致する入力データの前記最長文字列が、前記動的辞書に参照として包含される入力データの前記最長文字列よりも長い場合のみ、前記動的辞書内で前記入力データ文字列を参照するエントリを作成することと、
を備えた、請求項５に記載のスライディングウインドウデータ圧縮方法。
【請求項１０】
スライディングウインドウデータ圧縮処理に対する方法を実行するよう処理システムを制御する、コンピュータ可読媒体に記憶されたコンピュータプログラムであって、前記方法は、
入力データ文字列を含む入力データを受信することと、
最長入力データ文字列一致を特定するよう、複数のスライディングウインドウの各々を探索することであって、前記複数のスライディングウインドウの各々は、複数のデータ文字列一致長の１つに対応するスライディングウインドウサイズを有する、前記探索することと、
を備えた、前記コンピュータプログラム。
【請求項１１】
前記処理システムは、複数のプロセッサを含み、各々のプロセッサは、対応するスライディングウインドウの探索を同時に実行する、請求項１０に記載のコンピュータプログラム。
【請求項１２】
最小データ文字列一致長は、２バイトである、請求項１０に記載のコンピュータプログラム。
【請求項１３】
前記スライディングウインドウの各々は、対応するハッシュ関数及びハッシュチェーンを有する、請求項１０に記載のコンピュータプログラム。
【請求項１４】
前記スライディングウインドウデータ圧縮処理は、辞書に基づくデータ圧縮処理であり、前記方法は更に、
前記動的辞書に参照として包含される最長入力データ文字列を判定するよう、前記動的辞書にわたって辞書探索を実行することとと、
各々のスライディングウインドウに包含されるデータに一致する前記最長入力データ文字列の長さを、前記動的辞書に参照として包含される前記最長入力データ文字列の長さと比較することと、
前記動的辞書内でエントリを作成することであって、前記エントリは、前記スライディングウインドウに包含されるデータに一致する入力データの前記最長文字列が、前記動的辞書に参照として包含される入力データの前記最長文字列よりも長い場合に作成される、前記作成することと、
を備えた、請求項１０に記載のコンピュータプログラム。
【請求項１５】
辞書エントリは、サイクリックポインタ及び関連する参照カウントを使用して動的に追い出し可能である、請求項１に記載の圧縮方法。
【請求項１６】
辞書エントリは、前記スライディングウインドウから結果として生じる最長一致長が予め定められた範囲内にある場合に作成される、請求項１に記載の圧縮方法。
【請求項１７】
辞書一致を表すために、辞書インデックスに従ったインジケータを使用することを更に備えた、請求項１に記載の圧縮方法。
【請求項１８】
より小さい一致長は、より小さいスライディングウインドウと関連付けられる、請求項５に記載のスライディングウインドウデータ圧縮方法。
【請求項１９】
より大きなスライディングウインドウにわたる一致が成功する場合、一致処理は、より小さいウインドウを探索することなく事前に終了する、請求項５に記載のスライディングウインドウデータ圧縮方法。
【請求項２０】
前記スライディングウインドウサイズは、前記データ文字列一致長に基づいて制限される、請求項５に記載のスライディングウインドウデータ圧縮方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は概して、データの伝送及び記憶の分野に関し、特に、データの圧縮及び復元に関する。
【背景技術】
【０００２】
デジタルシステムでは、記憶コストを節約し、または伝送時間を減少させるために、データが圧縮される場合がある。多種多様なデジタルデータ信号（例えば、データファイル、ドキュメント、画像など）が圧縮される場合がある。データ記憶のための必要とされるメモリ、及び／またはデータ伝送のための必要とされる時間を低減させることによって、圧縮は、改善されたシステム性能及び減少したコストを得ることができる。
【０００３】
公知であり、広範囲に使用されるいくつかの、可逆圧縮の、圧縮スキームは、多くのデータタイプが反復する文字の連続を包含するという事実を使用する、辞書に基づく圧縮を採用する。１つの従来のアルゴリズム、ＬＺ７７は、反復されるデータの発生を、圧縮されていないデータストリーム内の前に存在するそのデータの単一の複製への参照と置き換えることによって圧縮を達成する。繰り返されるデータ（文字列一致）は、長さ−距離のペアと称されるペアの数によって符号化され、ペアは、「次の長さの文字の各々が圧縮されていないストリーム内のその背後にある文字と厳密な距離の文字に等しい」というステートメントに等しい。「距離」は代わりに、「オフセット」と称されることがある。
【０００４】
文字列一致を見分けるために、エンコーダは、例えば、データの直近の３２キロバイトなど、若干の直近のデータを記録する必要がある。データが保持される構造は、スライディングウインドウと称される。エンコーダは、文字列一致を探索するためにこのデータを使用し、デコーダは、エンコーダが参照した一致を解釈するためにこのデータを使用する。スライディングウインドウがより大きいと、エンコーダが参照を作成することを検索することが逆に長くなる場合がある。
【０００５】
よって、圧縮の効果をもたらすために、エンコーダは、入力ストリーム内の現在の位置において開始する文字列に一致する最長文字列を発見するために、スライディングウインドウに包含されるデータを探索する。エンコーダは、現在の位置におけるいくつかの単位のデータに対して、及び入力ストリーム内の１つ以上の後続の単位のデータに対してハッシュ関数を実行し、結果として生じるハッシュをハッシュテーブルへのインデックスとして使用し、ハッシュテーブルは、各々のハッシュに対し、同一のハッシュを作成した履歴バッファ内の他の文字列を指し示すポインタのセットを含む。
【０００６】
ＬＺ７８アルゴリズムは、反復されるデータの発生を、入力データストリームに基づいて構築された辞書への参照と置き換えることによって圧縮を達成する。各々の辞書エントリは、ｄｉｃｔｉｏｎａｒｙ［．．．］＝｛ｉｎｄｅｘ，ｃｈａｒａｃｔｅｒ｝の形式のエントリであり、インデックスは、前の辞書エントリへのインデックスであり、文字は、ｄｉｃｔｉｏｎａｒｙ［ｉｎｄｅｘ］によって表される文字列に付加される。例えば、「ａｂｃ」は、ｄｉｃｔｉｏｎａｒｙ［ｋ］＝｛ｊ，’ｃ’｝，ｄｉｃｔｉｏｎａｒｙ［ｊ］＝｛ｊ，’ｂ’｝，ｄｉｃｔｉｏｎａｒｙ［ｉ］＝｛０，’ａ’｝として記憶され（逆の順序で）、０のインデックスは、文字列の第１の文字を指定する。
【０００７】
アルゴリズムは、最後に一致したインデックスを０に初期化し、次の利用可能なインデックスを１に初期化する。入力ストリームの各々の文字に対し、辞書は、一致：｛最後に一致したインデックス，文字｝に対して探索される。一致が発見される場合、次いで、最後に一致したインデックスは、一致したエントリのインデックスに設定され、何も出力されない。文字列一致が発見されない場合、次いで、新たな辞書エントリ、辞書［次の利用可能なインデックス］＝｛最後に一致したインデックス，文字｝が作成され、アルゴリズムは、最後に一致したインデックスと、それに続いて、文字を出力し、次いで、最後に一致したインデックスを０にリセットし、次の利用可能なインデックスをインクリメントする。
【０００８】
ＬＺＷは、全てのとり得る文字（シンボル）により事前に初期化された辞書または事前に初期化された辞書のエミュレーションを使用するＬＺ７８に基づくアルゴリズムである。ＬＺＷの主要な改善は、一致が発見されないとき、現在の入力ストリーム文字が、辞書内の既存の文字列の第１の文字であると推定され（辞書が全てのとり得る文字により初期化されるので）、よって、最後に一致したインデックス（前の入力文字または初期の入力文字に対応する事前に初期化された辞書インデックスである場合がある）のみが出力されることである。ＬＺＷにより圧縮されたデータを復号するために、デコーダは、使用される初期の辞書にアクセスすることを必要とする。前のエントリから追加のエントリを再構築することができる。
【０００９】
概して、辞書に基づく圧縮方法は、データストリーム内の部分文字列を、辞書内のその部分文字列を識別するコードワードと置き換える原理を使用する。この辞書は、入力ストリームの知識及び統計が既知である場合に静的であることができ、または適応的であることができる。統計が既知でなく、または変化するデータストリームを扱うことにおいて、適応的辞書スキームがより良好である。
【００１０】
従来の辞書に基づく、スライディングウインドウ、圧縮技術の各々に対する不利な点が存在する。例えば、ＬＺ７８タイプの辞書（例えば、ＬＺＷ）を使用して、いくつかのデータタイプを圧縮することが有益となる場合があり、ＬＺ７７文字列一致を使用して、他のデータタイプの圧縮がより効率的である場合がある。
【００１１】
また、より大きなスライディングウインドウは典型的には、ソフトウェア及びハードウェアの両方において、より多くの一致及びより長い一致を生じさせ、スライディングウインドウのサイズを増大させることは、実装コストまたは減少した性能の点でより高価となる場合がある。例えば、スライディングウインドウは、標準メモリと比較して、実装するためにより多くの回路を必要とする連想メモリなどの特殊化メモリに記憶される場合がある。
【００１２】
加えて、より大きなスライディングウインドウは、より小さい一致に対して参照を記憶することを非効率にさせる場合がある。更に、典型的な辞書に基づくスキームは、本質的に直列であり、多くのプロセッサアーキテクチャにおいて利用可能な並列処理を利用せず、低減した性能をもたらす。
【００１３】
それは、本開示に対する必要性が生じた上述したコンテキストの中にある。よって、従来のシステム及び方法の先述の不利な点のうちの１つ以上に対処する必要性が存在し、本開示は、この必要性を満たす。
【発明の概要】
【００１４】
本開示の例示的な実施形態において、データ圧縮スキームの辞書を増強する方法の様々な態様を発見することができる。
【００１５】
開示の１つの実施形態では、各々の入力文字列に対し、スライディングウインドウ探索の結果は、辞書探索の結果と比較される。スライディングウインドウ検索結果が辞書検索結果よりも長い場合、スライディングウインドウ検索結果により辞書が増強される。開示の別の実施形態は、複数のスライディングウインドウを実装し、各々のスライディングウインドウは、関連するサイズを有し、スライディングウインドウのサイズは、対応する一致長に依存する。１つの実施形態について、各々のスライディングウインドウは、一致長に基づいた対応するハッシュ関数を有する。
【００１６】
明細書の残りの部分及び添付図面を参照することによって、本明細書における本開示の特質及び利点の更なる理解を実現し得る。本開示の更なる特徴及び利点と共に、本開示の様々な実施形態の構造及び動作が添付図面を参照して以下で詳細に説明される。図面では、同一の参照番号は、同一または機能的に同様の要素を示す。
【図面の簡単な説明】
【００１７】
【図１】開示の１つの実施形態に従った、スライディングウインドウ圧縮スキームに対する辞書を提供する処理を例示する。
【図２】開示の１つの実施形態に従った、一致長に依存した複数のスライディングウインドウ圧縮スキームを例示する。
【図３】開示の１つの実施形態に従った、一致長に依存した複数のスライディングウインドウ圧縮スキームを例示する。
【図４】開示の様々な実施形態に従った、処理を実行するために使用し得るコンピューティングデバイスを例示する。
【発明を実施するための形態】
【００１８】
ここで、開示の実施形態への参照が詳細に行われ、その実施例が添付図面において例示される。開示が実施形態と共に説明されるが、それらは開示をそれらの実施形態に限定することを意図していないことが理解されよう。逆に、開示は、添付の特許請求の範囲によって定義されるように、開示の精神及び範囲内に含み得る、代替物、修正物、及び同等物を網羅することが意図される。更に、本開示の以下の詳細な説明では、本開示の完全な理解をもたらすために、多数の特定の詳細が示される。しかしながら、本開示がそれらの特定の詳細なしに実施されてもよいことが当業者にとって自明である。他の例では、本開示の態様を不必要に曖昧にしないよう、公知の方法、手順、構成要素、及び回路が詳細に説明されていない。その上、発明的態様は、単一の開示される実施形態のすべての特徴未満に存在する。よって、発明を実施するための形態に続く特許請求の範囲は、以下でこの発明を実施するための形態に明示的に組み込まれ、各々の請求項は、本開示の別個の実施形態としてそれ自体を表す。
【００１９】
改善された辞書に基づく圧縮アルゴリズムに対するシステム及び方法が開示される。開示の実施形態は、文字列探索及びデータ圧縮スキームの辞書を増強する方法を提供する。各々の入力文字列に対し、スライディングウインドウ探索の結果は、辞書探索の結果と比較される。スライディングウインドウ検索結果が辞書検索結果よりも長い場合、スライディングウインドウ検索結果により辞書が増強される。開示の実施形態は、複数のスライディングウインドウを実装し、各々のスライディングウインドウは、関連するサイズを有し、スライディングウインドウのサイズは、対応する一致長に依存する。１つの実施形態について、各々のスライディングウインドウは、一致長に基づいた対応するハッシュ関数を有する。
【００２０】
開示の実施形態は、データ圧縮または復元が影響される様々な設定において適用可能である。
【００２１】
一致した文字列辞書
開示の様々な代替的な実施形態は、辞書エントリを判定するためにスライディングウインドウ一致長探索を使用して、辞書に基づく圧縮スキームに対する辞書を作成するシステム及び方法を提供する。
【００２２】
上記議論されたように、ＬＺ７７圧縮は、スライディングウインドウにわたる一致文字列探索を採用し、最長一致が判定されると、長さ−距離ペアを使用して一致が符号化される。典型的なスライディングウインドウサイズが３２キロバイトであるので、最小一致長は典型的には、（長さ，距離）ペアとして符号化することによって圧縮の効果をもたらすよう、３バイトに設定される。ＬＺ７７圧縮の間、直近に一致した文字列が繰り返される場合が高いことがある。複数の（長さ、距離）ペアとしてよりも辞書エントリとしてそのような繰り返しを圧縮することがより効率的である。したがって、一致文字列を（辞書インジケータ、辞書インデックス）として符号化することがより短くなる可能性が高いので、直近に一致した文字列を含む辞書は、より大きな圧縮効率性をもたらし得る。これは、一致文字列を判定するために辞書が使用されることが多いとき、インジケータは、エントロピ符号化（例えば、ハフマン符号化）によってより短い長さにより表現されることを理由とする。更に、直近に一致した文字列を含む辞書を採用することは、最長一致をより即時的に判定することをもたらし得る。加えて、増強された辞書は、スライディングウインドウを超える文字列一致探索を有効にする。
【００２３】
図１は、開示の１つの実施形態に従った、スライディングウインドウ圧縮スキームに対する辞書を提供する処理を例示する。
【００２４】
図１に示されるように、処理１００は、データ文字列が受信される動作１０２において開始する。動作１０４において、上記議論されたように、ＬＺ７７圧縮アルゴリズムに準拠して、スライディングウインドウ（典型的には、３２キロバイト）にわたって探索が実行され、最長の一致した文字列長が判定される。動作１０６において、最長の辞書一致の長さを判定するよう、辞書探索が実行される。動作１０８において、一致した文字列長は、辞書一致の長さと比較される。
【００２５】
動作１０９において、一致した文字列長が辞書一致長よりも長い場合、次いで、動作１１０において、一致文字列を参照する辞書エントリが辞書に追加される。開示の様々な実施形態について、従来の辞書に基づく圧縮スキーム処理に従って、一致した文字列が辞書に追加される。一致した文字列長が辞書一致長以下である場合、次いで、動作１１１において、入力データ文字列が一致する辞書エントリとして符号化され、後続の入力データ文字列により処理が繰り返される。
【００２６】
開示の態様に従って、一致した文字列が辞書一致よりも長い場合、それのみが辞書に追加される。したがって、辞書が一致した文字列のみによって構成される。辞書にないいずれかの文字列に対する辞書エントリを作成する従来技術の辞書に基づく圧縮方法とは対照的に、開示の実施形態は、文字列がスライディングウインドウ文字列一致探索を通じて最長一致として識別される場合のみ、辞書エントリを作成する。これは、より高速な、より効率的な圧縮をもたらし得る。復元されると、一致結果に基づいて辞書エントリを作成することによって、エンコーダの辞書構築処理を反復し、したがって、圧縮に対して使用される同一の辞書を再作成する。
【００２７】
複数の一致長依存スライディングウインドウ
上記述べられたように、ＬＺ７７などのスライディングウインドウ圧縮スキームは、固定された数の直近のデータストリーム入力を記録するために、単一のスライディングウインドウを実装する。スライディングウインドウサイズは、例えば、２キロバイト、４キロバイト、または３２キロバイトであってもよい。より小さなスライディングウインドウサイズは、より小さな一致を効率的に符号化することを可能にすると共に、より大きなスライディングウインドウサイズは典型的には、より長い一致をもたらす。ＤＥＦＬＡＴＥ及びＧＺＩＰなどのいくつかのＬＺ７７に基づくアルゴリズムは、３２キロバイトのスライディングウインドウを使用する。そのようなアルゴリズムは、一致を（オフセット，長さ）として符号化するために２３バイトを必要とし、オフセットに対して１５ビット及び長さに対して８ビットを使用する。よって、３２キロバイトのスライディングウインドウに対し、３バイト未満の一致を符号化することは効果がない。より長い一致を識別する尤度を増大させるためにスライディングウインドウサイズを拡大することは、更に長い一致（例えば、３バイトの一致）を符号化することを非効率にさせる。
【００２８】
例えば、Ｈｉと表わされるｉバイトごとの文字のハッシュ関数を考え、３２キロバイトのスライディングウインドウ圧縮スキームは、３バイトの最小一致長を有し、したがって、ハッシュ関数Ｈ３が使用される。データストリームが１６キロバイトのオフセットにおいて４バイトの長さとの一致、及び４８キロバイトのオフセットにおいて１２バイトの長さとの一致（すなわち、スライディングウインドウ外の）を含んでいた場合、次いで、最長の識別された一致は、オフセット１６キロバイトにおいて４バイトの一致となる。より長い一致を特定するために、スライディングウインドウサイズが増大する場合、次いで、最小の効率的な一致長が増大する。
【００２９】
開示の実施形態は、異なるサイズの複数のスライディングウインドウを実装してもよく、サイズは、一致長に基づいている。開示の実施形態はまた、実装される各々のスライディングウインドウサイズに対する対応するハッシュ関数を作成してもよい。
【００３０】
開示の実施形態は、一致長を効率的に圧縮可能にするスライディングウインドウサイズ及び一致長の全ての組み合わせを包含する。１つの実施形態について、各々が対応する一致長を有する７個のスライディングウインドウサイズが実装される。一致ペアは、そのような長さ−オフセットの形式にあり、復元されると、デコーダは、対応する、長さ依存の、スライディングウインドウを採用する。
【００３１】
図２は、開示の１つの実施形態に従った、一致長依存の複数のスライディングウインドウ圧縮スキームを例示する。
【００３２】
図２に示されるように、２バイトの一致長は、５ビットに対応するスライディングウインドウサイズを有し、３バイトの一致長は、９ビットに対応するスライディングウインドウサイズを有し、４バイトの一致長は、１２ビットに対応するスライディングウインドウサイズを有し、５バイトの一致長は、１５ビットに対応するスライディングウインドウサイズを有し、６バイトの一致長は、１７ビットに対応するスライディングウインドウサイズを有し、７バイトの一致長は、１９ビットに対応するスライディングウインドウサイズを有し、８バイトまたはそれ以上のバイトの一致長は、２０ビットに対応するスライディングウインドウサイズを有する。よって、一致長に基づいてスライディングウインドウサイズを制限することによって、様々なサイズにされた一致の各々は、効率的に圧縮可能である。例えば、５ビットに対応するスライディングウインドウサイズが使用されるとき、２バイトの一致が圧縮可能である。
【００３３】
開示の様々な実施形態に従った一致長依存の複数のスライディングウインドウスキームは、従来の単一のスライディングウインドウスキームと比較して、圧縮性能を大幅に改善する。開示の様々な実施形態に従って、複数のハッシュ関数スキームを実装することによって、圧縮速度を増大させることができる。
【００３４】
不必要な探索を回避するために、開示の代替的な実施形態について、複数のスライディングウインドウサイズの各々に対するハッシュチェーンが実装されてもよい。１つのそのような実施形態について、対応するハッシュ関数の各々は、特定のウインドウサイズと関連付けられた文字の最小一致長の入力を取る。例えば、図２に示されるように、２バイトの一致は、ハッシュ関数Ｈ３を採用し、８バイト以上の一致は、Ｈ８を採用する。したがって、そのような実施形態について、Ｈ８ハッシュチェーンにわたってのみ最長一致が探索され、最初の厳密な一致が他のハッシュチェーンを満たす。
【００３５】
並列処理
開示の様々な実施形態に従った複数のスライディングウインドウサイズ−複数のハッシュ関数スキームは、各々のハッシュチェーン探索が独立して及び並列して実行されてもよいので、マルチコア環境において適している。一致長がスライディングウインドウサイズに比例するので、いくつかのハッシュチェーンの各々は、長さにおいて比較可能であってもよく、したがって、並列処理に適し得る。例えば、２０ビットのスライディングウインドウに対するＨ８ハッシュチェーンにわたる最長一致を判定するよう、１つのコアが割り当てられてもよい。１９ビットのスライディングウインドウに対するＨ７ハッシュチェーンにわたる最長一致を判定するよう、別のコアが割り当てられてもよい。１８ビットのスライディングウインドウに対するＨ６ハッシュチェーンにわたる最長一致を判定するよう、別のコアが割り当てられてもよい。１５ビットのスライディングウインドウに対するＨ５ハッシュチェーンにわたる最長一致を判定するよう、別のコアが割り当てられてもよい。１２ビットのスライディングウインドウに対するＨ４ハッシュチェーンにわたる最長一致を判定するよう、別のコアが割り当てられてもよい。９ビットのスライディングウインドウに対するＨ３ハッシュチェーンにわたる最長一致を判定するよう、別のコアが割り当てられてもよい。また、５ビットのスライディングウインドウに対するＨ２ハッシュチェーンにわたる最長一致を判定するよう、別のコアが割り当てられてもよい。開示の実施形態に従った複数の並列探索は、最長一致を判定する時間を減少させることによって、より高速な圧縮をもたらす。更に、述べられたように、Ｈ２ハッシュチェーンが５ビットに対応するスライディングウインドウサイズを有することを理由に、厳密な２バイトの一致が圧縮可能である。したがって、開示の実施形態は、複数の対応するサイズのスライディングウインドウなしにマルチハッシングを実装した従来技術のスキームとは対照的に、より効率的な圧縮をもたらす。
【００３６】
順次処理
探索が順次行われる場合、成功した探索が判定されるまで、探索は、減少する順序のハッシュバイトに従う。例えば、図２の実装態様を参照して、探索は、２０ビットのスライディングウインドウに対するＨ８にわたる最長一致を判定することによって開始し、探索が成功して終了する場合、他に、最初の厳密な７バイトの一致を判定するよう、１９ビットのスライディングウインドウに対するＨ７ハッシュチェーンにより探索が続き、探索が判定されるまで、各々のハッシュチェーン／スライディングウインドウサイズの組み合わせにわたって処理が続く。
【００３７】
開示の代替的な実施形態では、一致長依存の圧縮スキームは、複数のスライディングウインドウサイズに対する単一のハッシュ関数サイズを使用する。
【００３８】
図３は、開示の１つの実施形態に従った、スライディングウインドウサイズに対応する一致長サイズ及びハッシュ関数サイズを例示する。
【００３９】
図３では、５ビットの一致長依存スライディングウインドウサイズを有する２バイトの一致長に対して、２バイトのハッシュ関数サイズが使用される。９ビットの一致長依存スライディングウインドウサイズを有する３バイトの一致長に対しても、２バイトのハッシュ関数サイズが使用される。図３に示されるように、複数の一致長／スライディングウインドウサイズの組み合わせに対しても、他のハッシュ関数が使用される。これは、適切である場合に、ハッシュ関数の数を減少させることを可能にする。図３に示されるように、そのような実施形態について、ハッシュ関数のサイズは、最小一致長に等しい。
【００４０】
様々な動作を含むとして開示の実施形態が説明されてきた。処理の多くがそれらの最も基本的な形式において説明されるが、開示の範囲から逸脱することなく、処理のいずれかに動作を追加することができる、または処理のいずれかから動作を削除することができる。例えば、開示の様々な実施形態に従った辞書一致アルゴリズムは、一致長依存の複数のスライディングウインドウスキームと共に実装されてもよく、または相互に独立して実装されてもよい、のいずれかである。
【００４１】
本開示に従った実施形態は、装置、方法、またはコンピュータプログラム製品として具体化されてもよい。したがって、本開示は、全体的にハードウェアの実施形態、全体的にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなど）、または全てが本明細書で「モジュール」もしくは「システム」と称されてもよいソフトウェアの態様及びハードウェアの態様を組み合わせた実施形態の形式を取ってもよい。更に、本開示は、媒体において具体化されたコンピュータ使用可能プログラムコードを有する表現のいずれかの有形媒体において具体化されたコンピュータプログラム製品の形式を取ってもよい。
【００４２】
非一時的媒体を含む１つ以上のコンピュータ使用可能媒体または１つ以上のコンピュータ可読媒体のいずれかの組み合わせが利用されてもよい。例えば、コンピュータ可読媒体は、ハードディスク、ランダムアクセスメモリ（ＲＡＭ）デバイス、リードオンリメモリ（ＲＯＭ）デバイス、消去可能プログラマブルリードオンリメモリ（ＥＰＲＯＭまたはフラッシュメモリ）デバイス、ポータブルコンパクトディスクリードオンリメモリ（ＣＤＲＯＭ）、光学記憶装置、及び磁気記憶装置のうちの１つ以上を含んでもよい。選択された実施形態では、コンピュータ可読媒体は、命令実行システム、装置、もしくはデバイスによる使用、または命令実行システム、装置、もしくはデバイスにおける使用のためにプログラムを包含することができ、記憶することができ、通信することができ、伝播することができ、または搬送することができるいずれかの非一時的媒体を含んでもよい。
【００４３】
本開示の動作を実行するためのコンピュータプログラムコードは、Ｊａｖａ、Ｓｍａｌｌｔａｌｋ、またはＣ＋＋などのオブジェクト指向プログラミング言語、及び「Ｃ」プログラミング言語または同様のプログラミング言語などの従来の手続型プログラミング言語を含む、１つ以上のプログラミング言語のいずれかの組み合わせにおいて記述されてもよい。プログラムコードは、スタンドアロンソフトウェアパッケージとしてコンピュータシステム上で全体的に実行されてもよく、スタンドアロンハードウェアユニット上で実行されてもよく、コンピュータから何らかの距離で間隔を空けられたリモートコンピュータ上で部分的に実行されてもよく、またはリモートコンピュータもしくはサーバ上で全体的に実行されてもよい。後者のシナリオでは、リモートコンピュータは、ローカルエリアネットワーク（ＬＡＮ）もしくはワイドエリアネットワーク（ＷＡＮ）を含むいずれかのタイプのネットワークを通じてコンピュータに接続されてもよく、または外部コンピュータに対して接続が行われてもよい（例えば、インターネットサービスプロバイダを使用してインターネットを通じて）。
【００４４】
開示の実施形態に従った、方法、装置（システム）、及びコンピュータプログラム製品のフローチャートの例示及び／またはブロック図を参照して、本開示を以下で説明し得る。フローチャートの例示及び／またはブロック図の各々のブロック、ならびにフローチャートの例示及び／またはブロック図におけるブロックの組み合わせは、コンピュータプログラム命令またはコンピュータプログラムコードによって実装されることができる。それらのコンピュータプログラム命令は、マシンを生成するために、汎用コンピュータ、特殊目的コンピュータ、または他のプログラム可能データ処理装置に提供されてもよく、その結果、コンピュータまたは他のプログラム可能データ処理装置のプロセッサを介して実行する命令が、フローチャート及び／またはブロック図のブロックまたはブロック（複数可）において指定される機能／動作を実装するための手段を作成する。
【００４５】
コンピュータまたは他のプログラム可能データ処理装置に、特定の方式において機能するよう指令することができる、それらのコンピュータプログラム命令は、非一時的コンピュータ可読媒体にも記憶されてもよく、その結果、コンピュータ可読媒体に記憶された命令は、フローチャート及び／またはブロック図のブロックまたはブロック（複数可）において指定される機能／動作を実装する命令の手段を含む製品を作成する。
【００４６】
コンピュータにより実施される処理を生成するよう、コンピュータまたは他のプログラム可能装置上で一連の動作ステップが実行されるよう、コンピュータプログラム命令はまた、コンピュータまたは他のプログラム可能データ処理装置上にロードされてもよく、その結果、コンピュータまたは他のプログラム可能装置上で実行される命令は、フローチャート及び／またはブロック図のブロックまたはブロック（複数可）において指定される機能／動作を実装するための処理を提供する。
【００４７】
図４は、開示の様々な実施形態に従った、処理を実行するために使用してもよいコンピューティングデバイス４００を例示する。コンピューティングデバイス４００は、サーバ、クライアント、またはいずれかの他のコンピューティングエンティティとして機能することができる。コンピューティングデバイス４００は、データを圧縮すること、データを復元すること、データを読み出すこと、データを書き込むこと、データを伝送すること、及び処理を実行することを含む、本明細書で説明される機能を実行することが可能ないずれかのタイプのコンピューティングデバイスであってもよい。図４に示されるように、コンピューティングデバイス４００は、中央処理装置（ＣＰＵ）４０２、メインメモリ４０４、入力／出力（Ｉ／Ｏ）サブシステム４０６、通信回路４０８、及び１つ以上のデータ記憶装置４１２を含む。他の実施形態では、コンピューティングデバイスは、コンピュータにおいて一般的に発見される構成要素など（例えば、ディスプレイ、周辺デバイスなど）、他の構成要素または追加の構成要素を含んでもよい。加えて、いくつかの実施形態では、例示的な構成要素のうちの１つ以上は、別の構成要素に組み込まれてもよく、またはそうでなければ別の構成要素の一部を形成してもよい。例えば、いくつかの実施形態では、メインメモリ４０４、またはその一部は、ＣＰＵ４０２に組み込まれてもよい。
【００４８】
ＣＰＵ４０２は、本明細書で説明される機能を実行することが可能ないずれかのタイプのプロセッサとして具体化されてもよい。そのようにして、ＣＰＵ４０２は、シングルコアプロセッサもしくはマルチコアプロセッサ（複数可）、マイクロコントローラ、または他のプロセッサもしくは処理／制御回路として具体化されてもよい。いくつかの実施形態では、ＣＰＵ４０２は、本明細書で説明される機能の実行を促進するために、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、再構成可能ハードウェアもしくはハードウェア回路、または他の特殊化ハードウェアとして具体化されてもよく、それらを含んでもよく、またはそれらに結合されてもよい。ＣＰＵ４０２は、特殊化圧縮ロジック４２０を含んでもよく、特殊化圧縮ロジック４２０は、ＣＰＵ４０２の他の構成要素から、データの圧縮をオフロードすることが可能な、ＦＰＧＡ、ＡＳＩＣ、またはコプロセッサなどのいずれかの回路またはデバイスとして具体化されてもよい。メインメモリ４０４は、本明細書で説明される機能を実行することが可能な、いずれかのタイプの揮発性メモリ（例えば、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）など）もしくは不揮発性メモリ、またはデータ記憶装置として具体化されてもよい。いくつかの実施形態では、メインメモリ４０４の全てまたは一部は、ＣＰＵ４０２に統合されてもよい。動作中、メインメモリ４０４は、例えば、圧縮されていない入力データ、ハッシュテーブルデータ、圧縮された出力データ、オペレーティングシステム、アプリケーション、プログラム、ライブラリ、及びドライバなど、動作の間に使用される様々なソフトウェア及びデータを記憶してもよい。Ｉ／Ｏサブシステム４０６は、ＣＰＵ４０２、メインメモリ４０４、及びコンピューティングデバイス４００の他の構成要素による入力／出力動作を促進するために、回路及び／または構成要素として具体化されてもよい。例えば、Ｉ／Ｏサブシステム４０６は、入力／出力動作を促進するために、メモリコントローラハブ、入力／出力制御ハブ、統合センサハブ、ファームウェアデバイス、通信リンク（例えば、ポイントツーポイントリンク、バスリンク、ワイヤ、ケーブル、光ガイド、プリント回路基板トレースなど）、及び／または他の構成要素及びサブシステムとして具体化されてもよく、またはそうでなければそれらを含んでもよい。いくつかの実施形態では、Ｉ／Ｏサブシステム４０６は、ＣＰＵ４０２、メインメモリ４０４、及びコンピューティングデバイス４００の他の構成要素と共に、単一の集積回路チップ上でシステムオンチップ（ＳｏＣ）の一部を形成してもよく、単一の集積回路チップ上に組み込まれてもよい。
【００４９】
通信回路４０８は、コンピューティングデバイス４００と別のコンピューティングデバイスとの間のネットワークを通じた通信を有効にすることが可能な、いずれかの通信回路、デバイス、またはそれらの集合として具体化されてもよい。通信回路４０８は、そのような通信に影響を与えるために、いずれかの１つ以上の通信技術（例えば、有線通信または無線通信）及び関連するプロトコル（例えば、イーサネット、Ｂｌｕｅｔｏｏｔｈ、ＲＴＭ、Ｗｉ−Ｆｉ、ＷｉＭＡＸなど）を使用するように構成されてもよい。
【００５０】
例示的な通信回路４０８は、ネットワークインタフェースコントローラ（ＮＩＣ）４１０を含み、ＮＩＣ４１０は、１つ以上のアドインボード、ドータカード、ネットワークインタフェースカード、コントローラチップ、チップセット、または別のコンピューティングデバイスと接続するためにコンピューティングデバイス４００によって使用され得る他のデバイスとして具体化されてもよい。いくつかの実施形態では、ＮＩＣ４１０は、１つ以上のプロセッサを含むシステムオンチップ（ＳｏＣ）の部品として具体化されてもよく、または１つ以上のプロセッサをも包含するマルチチップパッケージ上に含まれてもよい。いくつかの実施形態では、ＮＩＣ４１０は、ＮＩＣ４１０にローカルなプロセッサ（図示せず）を含んでもよい。そのような実施形態では、ＮＩＣ４１０のローカルプロセッサは、本明細書で説明されるＣＰＵ４０２の機能のうちの１つ以上を実行することが可能であってもよい。
【００５１】
データ記憶装置４１２は、例えば、ソリッドステートドライブ（ＳＳＤ）、ハードディスクドライブ、メモリカード、及び／または他のメモリデバイス及び回路など、データの短期間の記憶または長期間の記憶に対して構成されたいずれかのタイプのデバイスとして具体化されてもよい。各々のデータ記憶装置４１２は、データ記憶装置４１２に対してデータ及びファームウェアコードを記憶するシステムパーティションを含んでもよい。各々のデータ記憶装置４１２はまた、オペレーティングシステムに対してデータファイル及び実行可能なものを記憶するオペレーティングシステムパーティションを含んでもよい。例示的な実施形態では、各々のデータ記憶装置４１２は、不揮発性メモリを含む。不揮発性メモリは、永続的な方式においてデータを記憶することが可能な（不揮発性メモリへの電力が中断される場合でさえ）いずれかのタイプデータ記憶装置として具体化されてもよい。例えば、例示的な実施形態では、不揮発性メモリは、フラッシュメモリ（例えば、ＮＡＮＤメモリもしくはＮＯＲメモリ）、または上記のいずれかの組み合わせ、または他のメモリとして具体化される。加えて、コンピューティングデバイス４００は、１つ以上の周辺デバイス４１４を含んでもよい。そのような周辺デバイス４１４は、ディスプレイ、スピーカ、マウス、キーボード、及び／または他の入力／出力デバイス、インタフェースデバイス、及び／または他の周辺デバイスなど、コンピューティングデバイスにおいて一般的に発見されるいずれかのタイプの周辺デバイスを含んでもよい。
【００５２】
上述したことが開示の例示的な特定の実施形態の完全な説明であるが、追加の実施形態も可能である。よって、上記説明は、開示の範囲を限定するとして解釈されるべきではなく、開示の範囲は、同等物のそれらの全範囲と共に、添付の特許請求の範囲によって定義される。
【００５３】
以下の別表（辞書一致疑似コード）は、この詳細な説明の統合部分を形成する疑似コード及び関連する説明を包含し、それらを全体的に本明細書で参照することによって組み込まれる。この別表は、いくつかの実施形態において実行されるものとして上記説明されたアクションの例示的な実施態様を包含する。以下の疑似コードは、いずれかの特定のコンピュータプログラミング言語において記述されていないことに留意されよう。代わりに、疑似コードは、オブジェクトコードにコンパイルするための適切なソースコードに疑似コードを変換するための十分な情報を当業者に対して提供する。
別表（辞書一致疑似コード）
static  const   uint    MinDictLen      =4；// Min dictionary word length
static  const   uint    MaxDictLen      = 12；// Max dictionary word length
static  const   uint    DictBits        = 16；// number of bits for dictionary space
static  const   uint    HashExtBits     = l；// extra bits to reduce Hash collision
static  const   uint    DictMask        = (1<<DictBits) -1；// mask for dictionary index
uint *dictHash2Ind；// map table of hashldx -> dictID, with size of 1<<(DictBits + HashExtBits)
typedef struct word_dict {      // dictionary entry
uint    wordLenCnt；// [word length (4-12), reference count]
uint    word[3]；// up to 12-byte word
uint    hashIdx；// corresponding hash index
} Word_Dict;
Word_Dict       *wordDict；// word dictionary, with size of 1<<DictBits
Struct Dict_Stat {      // dictionary status tracker
uint wordIndPtr；// rotational pointer to the current word index
uint is Full；// indicator of dictionary is full
uint useBits；// dictionary words in use and its number of bits
} dictStat;
typedef struct dict_match {     // dictionary match output
uint len；// matched word length
uint wordInt；// matched word index
Word_Dict *wordPtr；//matched word pointer} Dict_Match;
//This function attempts to insert matchStr to the dictionary void Dict_Insert (uint8*matchStr, uint matchLen)
{
uint i, h, *dictHashPtr;
Word_Dict *wordDictPtr;
uint *matchIntStr = (uint *)matchStr;
h = hash(matchStr, matchLen);
h = ((h ^h>>DictBits) &DictMask) << HashExtBits;
dcitHashPtr = dcitHash2Ind + h;
for (i=O；! (i>>HashExtBits)；i++, dictHashPtr++) {
if (*dictHashPtr) continue；// the slot is occupied
if (!dictStat. isFull) {
wordDictPtr ->word[O] = matchIntStr [O];
wordDictPtr ->word[l] = matchIntStr [1];
wordDictPtr ->word[2]
= matchIntStr [2];
// set length in upper 8-bit and O reference count
wordDictPtr ->wordLenCnt = matchLen <<8;
// update useBits, which tracks the bit number ofwordIntPtr
dictStat.useBits += dictStat.wordIndPtr >> dictStat.useBits;
wordDictPtr ->hashIdx = h ^i；//set hash index
*dictHashPtr = dictStat.wordIndPtr;
}
else {
if (wordDictPtr ->wordLenCnt &0xFF) // non-zero reference count
wordDictPtr ->wordLenCnt --；// decrease the reference count by 1
}
else {          // reference count is zero, then invalidate the entry
wordDictPtr ->word[O] = matchIntStr [O];
wordDictPtr ->word[1]
= matchIntStr [1];
wordDictPtr ->word[2]
= matchIntStr [2];
wordDictPtr ->wordLenCnt = matchLen <<8;
dictHash2Ind[wordDictPtr=>hashIdx] = O；//invalidate the outdated entry
wordDictPtr ->hashldx = h ^i；//set hash index
*dictHashPtr = dictStat.wordlndPtr;
}
}
break;
}
if (i>>HashExtBits) {// all slots are fukk then update the current dictionary entry
if (!dictStat.isFull)
return;
if(wordDictPtr->wordLenCnt & OxFF) reference count is positive then decrease it
wordDictPtr->wordLenCnt --;
else dictHash2Ind [owrdDictPtr->hashIdx] = O；// invalidate the outdated entry
}
wordDictPtr++;
if(++dictStat.wordIndPtr >> DictBits) {// cyclically rotate wordDictPtr
wordDictPtr -= DictMask;
dictStat.wordIndPtr = 1；// note zero index is reserved for fast initialization
dictStat. IsFull = 1;
dictStat.useBits = DictBits;
}
}
//This function searches the dictionary to find the longest string match.
//It returns hashDict pointer and the maximum match length void Dict_Search9uint8 *rawBufPtr, Dict_Match *dictMatch)
{
uint i, h, hashVec[16];
uint DictLen;
uint *dictHashPtr;
Word_Dict * dictPtr;
Uint curStrInt = *(uint *) rawBufPtr;
dictMatch->len = O;
hash_seq(rawBufPtr, MaxDictLen, hashVec)；// compute the hash sequence for(dictLen=MaxDictLen；dictLen>=MinDictLen；dictLen--) {
//search from max down to min
h = (hashVec[dcitLen] ^ hashVec[dictLen]>>DictBits) & DictMask;
dictHashPtr = dictHash2Ind + (h<<HashExtBits);
// note hashDict is created with a small margin to avoid crossing boundary
for(i = O；!(i>>HashExtBits)；i++, dictHashPtr；{
if (!*dictHashPtr) continue；// skip empty slot
dcitPtr = wordDict + *dictHashPtr;
if (dictPtr->wordLenCnt>>8 ! = dictLen 11 dictPtr->word[O] ! = curStrInt)
continue；// preprocessing
if (dictLen= =4 || 0= =memcmp (dictPtr->word+1, rawBufPtr+4, dictLen-4)) {      // matched
dictMatch=>wordPtr = dictPtr;
dictMatch=>wordInd = *dictHashPtr;
dictMatch=>len = dictLen;
return;
}
}
}
}
【図１】
2021527376.tif 000003
【図２】
2021527376.tif 000004
【図３】
2021527376.tif 000005
【図４】
2021527376.tif 000006
【国際調査報告】
2021527376.tif 000007