(57)【要約】  一連の値を含んでなるデータのソースストリームからのデータを、１つ以上の個別のコンピュータアドレスをワークスペースとして用いて圧縮する方法を提供し、各コンピュータメモリアドレスは、１つ以上の個別の値を保持する１つ以上の位置を有する。当該方法は、Ｋビット長およびＮビット長からなる２つの近接するデータ値を、ソースデータストリームから、それぞれメモリアドレス参照先および現在のシンボル値として読み出すことによって動作する。当該現在のシンボル値がメモリアドレス参照先のいかなる値にも一致しない場合に、現在のシンボル値が書き込まれ、メモリアドレス参照先の１つの値と置換され、現在のシンボル値が後続するMISSコードが圧縮データストリームに付加される。または、現在のシンボル値がメモリアドレス参照先の値のいずれかに一致する場合、ヒットコードが被圧縮データストリームに付加される。当該ヒットコードは、メモリアドレス参照先において値が見つかった位置またはその位置に関連する属性を示す。ソースストリームから読み出されたすべてのシンボルに対して本方法が繰り返される。同等、対称的かつ可逆的な伸張または復元方法により、もとのソースストリームに等しい非圧縮データストリームが生成される。圧縮方法に用いられたワークスペースは、コンピュータアーキテクチャに使用されるキャッシュメモリのワークスペースと同様の挙動を有し、ハードウェア設計における連想メモリまたはインテリジェントメモリ、またソフトウェア実行における連想配列である連想メモリを用いた圧縮方法を実行可能とする。
2009531976.tif 000002
【特許請求の範囲】
【請求項１】
一連の値を含んでなるソースストリームデータからのデータを圧縮する方法であって、前記圧縮方法は１つ以上の個別のコンピュータメモリアドレスをワークスペースとして用い、各コンピュータメモリアドレスは１つ以上の個別の値を保持する１つ以上の位置（location）を有しており
（ａ）  Ｋがゼロより大きい場合、前記ソースストリームデータから、前記ソースストリームにおける現在の読み出しポイントの直前にあるＫビットをメモリアドレス参照先として読み出し、
（ｂ）  前記ソースストリームからＮビットを現在のシンボル値として読み出し、
（ｃ）  前記現在のシンボル値が、前記メモリアドレス参照先における値のいずれにも一致しない場合、前記メモリアドレス参照先の値のひとつと置換すべく前記現在のシンボル値を被圧縮データストリームに書き込み、かつ、MISSコード／値を前記現在のシンボル値の前に書き込み、
（ｄ）  前記現在のシンボル値が、前記メモリアドレス参照先のいずれかの値に一致する場合、前記メモリアドレス参照先において値が存在する位置を示すHITコードを、前記被圧縮データストリームに書き込む圧縮方法。
【請求項２】
各メモリアドレスにおけるすべての値を初期化した後に、ソースデータストリームにおけるすべての値に対して（ａ）から（ｄ）を繰り返すことをさらに含み、（ａ）において、メモリアドレス参照先がソースデータストリームからの読み出しに使用できない場合は、メモリアドレス参照先の左端のビットが適切に初期化される請求項１に記載の圧縮方法。
【請求項３】
（ａ）において、読み出されたＫビットは、同等のまたは少ないビット数に変換され、前記メモリアドレス参照先として使用されるワードが生成される請求項２に記載の圧縮方法。
【請求項４】
それぞれの前記メモリアドレスはステータスフィールドを含み、そのステータスフィールドは、前記メモリアドレス内における位置の使用を把握するための状態監視に用いられかつ前記メモリアドレスにおける値の読み出し／書き込み後に（ｃ）または（ｄ）にて更新される請求項３に記載の圧縮方法。
【請求項５】
前記ステータスフィールドは、値を置換する際に使用すべき位置を決定する置換ポリシーと併せて使用される請求項４に記載の圧縮方法。
【請求項６】
置換ポリシーは、最近最も使われなかった（近時最少使用、LRU）、先入れ先出し（FIFO）または最も古くに使用された、最も使用頻度が低い（LFU）、およびランダムからなる群から選ばれる請求項５に記載の圧縮方法。
【請求項７】
ワークスペースとして使用される各メモリアドレスは、１つの値のみを保持する位置を１つのみ有し、（ｄ）において、HITコードは、前記現在のシンボル値が前記メモリアドレス参照先に存在する値と一致することを示す請求項３に記載の圧縮方法。
【請求項８】
１つのメモリアドレスは、それぞれ個別の値を保持する多数の位置を有し、前記メモリアドレスはワークスペースとして使用され、（ａ）において、Ｋの値がゼロであるため前記ソースストリームからビットが読み出されず、唯一のメモリアドレスが存在し、そのメモリアドレス参照先がゼロである請求項５に記載の圧縮方法。
【請求項９】
前記１つのメモリアドレスは、個別の値に予め初期化された２N個の位置を有し、（ｃ）において、シンボル値は、前記位置ですでに初期化された値のいずれかに常に一致するため、MISSコードおよび前記現在のシンボル値のいずれも前記被圧縮データストリームに追加されない請求項８に記載の圧縮方法。
【請求項１０】
（ｄ）において、可変長符号化スキームがHITおよびMISSのコード／値に対して用いられ、その可変長符号化スキームは、最も頻繁に使用される下方の位置は短いコードで示され、使用頻度の低い上方の位置は長いコードが割り当てられる請求項５に記載の圧縮方法。
【請求項１１】
各位置の使用頻度を計算する第１の段階（pass）と、最も頻繁に使用する位置には短いコードを割り当て、使用頻度が最も低い位置には長いコードを割り当てるように、各位置を示す可変長コードを割り当てる第２の段階との２つの段階を使用する請求項１０に記載の圧縮方法。
【請求項１２】
符号化された各位置につき１つずつ、近時最少使用カウンタの値を前記ステータスフィールドに記録し、前記近時最少使用カウンタを用いて、近時最少使用置換ポリシーを実行して、より大きい値が最近より多く使用された位置であることを示し、またその逆も示すように各位置の使用ランクを表し、近時最少使用カウンタ値が大きい場合は、短いコードが割り当てられ、小さい値には長いコードが割り当てられる請求項５に記載の圧縮方法。
【請求項１３】
ワークスペースとして使用されるコンピュータメモリは、前記現在のシンボル値の入力として使用されるＮビット、メモリアドレス参照先の入力として使用されるＫビット、メモリアドレス参照先において値が存在する位置を示す出力として使用されるＬビット、およびヒットまたはミスが生じたかどうかを示す出力として使用される１ビットを含む擬似キャッシュメモリとして実行される請求項１に記載の圧縮方法。
【請求項１４】
MISSコードおよびHITコードを含んでなる圧縮コードを伴うソースデータの少なくともいくつかを含む被圧縮データから非圧縮ソースデータストリームを復元する方法であり、前記復元方法はそれぞれ１つ以上の個別の値を保持する１つ以上の位置（location）を有する１つ以上の個別のコンピュータメモリアドレスをワークスペースとして用い、
（ａ）  Ｋがゼロより大きい場合、前記非圧縮データストリームから、前記非圧縮ストリームにおける現在の挿入ポイントの直前にあるＫビットを、メモリアドレス参照先として読み出し、
（ｂ）  前記被圧縮データストリームから、HITの符号化された位置またはMISSの発生を示すコードの値を読み出し、
（ｃ）  前記値がMISSコードの場合、前記被圧縮ストリームから現在のシンボル値としてＮビットを読み出し、（ａ）で取得したメモリアドレス参照先における値の１つを置換すべく前記現在のシンボル値を書き込み、前記非圧縮ストリームに前記現在のシンボル値を書き込み、
（ｄ）  前記値がHITコードの場合、（ａ）で取得したメモリアドレス参照先における復号されたHITコードによって与えられる位置から、前記現在のシンボル値としてＮビットを読み出し、前記現在のシンボル値を前記非圧縮ストリームに書き込む復元方法。
【請求項１５】
各メモリアドレスにおけるすべての値を適切に初期化した後に、前記被圧縮データストリームにおける各値に対して（ａ）から（ｄ）を繰り返すことをさらに含み、（ａ）において、メモリアドレス参照先における左端のビットは、前記メモリアドレス参照先が前記ソースデータストリームからの読み出しに使用できない場合に、適切に初期化される請求項１４に記載の復元方法。
【請求項１６】
（ａ）にて、読み出し／入力されたＫビットは、より少ない／同等のビット数に減少／変換され、その結果生じるワードは、メモリアドレス参照先として使用される請求項１５に記載の復元方法。
【請求項１７】
前記メモリアドレスはそれぞれ、前記メモリアドレス内における位置使用を把握するための状態監視として用いられかつ前記メモリアドレスにおける値の読み出し／書き込み後に（ｃ）または（ｄ）で更新されるステータスフィールドを含む請求項１６に記載の復元方法。
【請求項１８】
前記ステータスフィールドは、値を置換する際に使用する位置を決定する置換ポリシーと併せて使用される請求項１７に記載の復元方法。
【請求項１９】
前記置換ポリシーは、最近最も使われなかった（近時最少使用、LRU）、先入れ先出し（FIFO）または最も古くに使用された、最も使用頻度が低い（LFU）、およびランダムからなる群から選ばれる請求項１８に記載の復元方法。
【請求項２０】
ワークスペースとして使用される各メモリアドレスは、１つの値のみを保持する位置を１つのみ有し、（ｄ）において、HITコードは、前記現在のシンボル値が前記メモリアドレス参照先に存在する値と一致することを示す請求項１６に記載の復元方法。
【請求項２１】
それぞれ個別の値を保持する多数の位置を有する１つのメモリアドレスは、ワークスペースとして使用され、（ａ）において、Ｋの値がゼロであるために、前記ソースストリームからビットが読み出されず、存在するメモリアドレスは１つのみで、前記メモリアドレス参照先はゼロである請求項１８に記載の復元方法。
【請求項２２】
前記１つのメモリアドレスは、予め個別の値に初期化された２N個の位置を有し、（ｃ）において、現在のシンボル値は、前記２N個の位置の予め初期化された値のいずれかに常に一致するため、MISSコードおよび前記現在のシンボル値のいずれも前記被圧縮データストリームにおいて読み出されない、または存在しない請求項２１に記載の復元方法。
【請求項２３】
（ｄ）において、前記被圧縮ストリームから読み出された、すでに符号化されたHITおよびMISSのコード／値に対して、可変長符号化スキームが用いられる請求項１８に記載の方法。
【請求項２４】
復号されたそれぞれのHITコードは、位置そのものを示さず、任意のメモリアドレスにおいてヒットとなった位置に対応する近時最少使用（LRU）のカウンタ値を示し、さらに、前記復元方法は
（ａ）LRUカウンタ値に関連する位置を検索し、
（ｂ）（ａ）において取得した前記位置から、前記現在のシンボル値を読み出すことを含み、
LRUカウンタは、ステータスフィールドに記録され、LRU置換ポリシーを実行し、各位置の使用ランクを示すために用いられる請求項２３に記載の復元方法。
【請求項２５】
ワークスペースとして使用されるコンピュータメモリは、前記現在のシンボル値の入力として使用されるＮビット、メモリアドレス参照先の入力として使用されるＫビット、前記現在のシンボル値が読み出されるべきメモリアドレス参照先における位置を示す入力として使用されるＬビット、および前記現在のシンボル値を出力するＮビットを含む擬似キャッシュメモリとして実行される請求項１４に記載の復元方法。
【請求項２６】
前記HITコードおよびMISSコードは、Ｎバイトのトークン（token）に分類される請求項１に記載の圧縮方法。
【請求項２７】
ｎは２のべき乗であり、前記ソースストリームまたは被圧縮ストリームから読み出された値のバイト配列は、前記被圧縮ストリームにコピーされる際にそのまま維持される請求項２６に記載の復元方法。
【請求項２８】
前記HITコードおよびMISSコードは、Ｎバイトのトークンに分類される請求項１４に記載の復元方法。
【請求項２９】
ｎは２のべき乗であり、前記ソースストリームまたは被圧縮ストリームから読み出された値のバイト配列は、前記非圧縮ストリームにコピーする際にそのまま維持される請求項２８に記載の復元方法。
【請求項３０】
ソフトウェアまたはハードウェア成果物としての有限状態オートマトンとして実行（implement）される請求項１に記載の圧縮方法。
【請求項３１】
ソフトウェアまたはハードウェア成果物としての有限状態オートマトンとして実行（implement）される請求項２４に記載の復元方法。
【請求項３２】
前記HITコードおよびMISSコードは、Ｎビットの倍数であるトークンに分類され、前記ソースストリームから読み出された値は、前記被圧縮ストリームにコピーされる際に、Ｎビットの倍数のままで配列される請求項１に記載の圧縮方法。
【請求項３３】
Ｎは８ビット長で、前記HITコードおよびMISSコードは、セット（set）からの自然数であるｎバイトのトークンに分類され、前記ソースストリームまたは被圧縮ストリームから読み出された値のバイト配列は、前記被圧縮ストリームにコピーされる際にそのまま維持される請求項３２に記載の圧縮方法。
【請求項３４】
前記HITおよびMISSのコード／値は、Ｎビットの倍数であるトークンに分類され、前記ソースストリームまたは被圧縮ストリームから読み出された値は、前記非圧縮ストリームにコピーされる際にＮビットの倍数のままで配列される請求項１４に記載の復元方法。
【請求項３５】
Ｎは８ビット長であり、前記HITコードおよびMISSコードは、ｎバイトのトークンに分類され、ｎはセットからの自然数であり、前記ソースストリームまたは被圧縮ストリームから読み出された値のバイト配列は、非圧縮ストリームにコピーされる際にそのまま維持される請求項３４に記載の復元方法。
【請求項３６】
連想メモリスキーム（associative memory scheme）が実行され、それによって任意のメモリアドレスからの複数の位置が、並列的にまたは同時に比較される請求項１に記載の圧縮方法。
【請求項３７】
連想メモリスキームが実行され、それによって任意のメモリアドレスからの複数の位置が、並列的にまたは同時に比較される請求項１４に記載の復元方法。
【発明の詳細な説明】
【技術分野】
【０００１】
〔関連出願の相互参照〕
本願は、２００６年３月２４日に出願された米国仮出願第６０／７８５，５７２号の優先権を主張するものであり、またその内容を本願に引用して援用する。
〔背景技術〕
【０００２】
情報の進歩的なデジタル化により、無数の通信技術、マルチメディアアプリケーション、新たなデータ形式、および新たな記憶装置が生まれ、過去２０年にわたり発展を遂げてきた。ウェブ上に送信されるテキスト、イメージおよびビデオ、サーバーベースのファイルアクセス、文書転送、データベース問い合わせ、および地理的マッピング技術は、ますます増えつつあるデータアプリケーションおよびマルチメディアアプリケーションの一例であり、それらは、デジタル情報をすぐに利用可能なフォーマットに変換し、かつ通信する。これら過剰なマルチメディア能力を、保存、通信、および計算能力の面において駆動するために必要なリソースの量は、厄介な問題となりうる。
【０００３】
データ集約やマルチメディアアプリケーションの展開を可能にした技術的躍進のひとつがデータ圧縮である。例えば、科学情報、高品質画像、および生中継ビデオコンテンツを含む大容量のファイルをウェブ上または企業ネットワーク上に配信する場合、なんらかのデータ圧縮を使用することになる。また、携帯電話およびその他の無線技術上に同様のサービスを送信する場合にも、データ圧縮のおかげで、利用可能な通信帯域幅を効率よく利用することができる。
【０００４】
データ圧縮は、ファイル、メモリバッファ、データストリームに保存されたメッセージやビットシーケンスの情報内容における冗長を取り除く技術である。情報をより少ないビットで表わすことは、記憶媒体の容量スペースをより節約し、単位時間当たりにより多くのデータを提供することにより送信に利用可能な有効な帯域幅を広げることにつながる。従ってデータ圧縮は、通信およびマルチメディアをすべての人々に身近な技術とする上で重要な役割を果たしてきており、また今後も引き続き重要な役割を果たすであろう。
【０００５】
データ圧縮において、データ圧縮方法には２つの異なる処理が関わる。２つの方法とは、圧縮器と復元器である。文字通り、後者はより一般的には伸張器または拡張器と呼ばれるが、純粋主義者は、圧縮されたデータの復元処理を明確に示すため、復元器という用語を用いる場合がある。復元プロセスを明確に示すために、本発明を通して復元という用語が好ましく、当該用語を使用する。
【０００６】
圧縮器は、その名称が示す通り、入力ソースを処理し、好ましくは小さいサイズで、オリジナルとは別のデジタル表現に変換する。対称的に復元器は、被圧縮データを処理し、オリジナルの復元版を生成する。ソースと復元内容がぴったり一致すれば、当該方法は損失がないとされ、そうでなければ損失が多いとみなされる。通常、損失の多い技術は、品質の劣化を代償にして、損失の少ない技術よりも圧縮率が高い。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
過去数年にわたり、多数の圧縮技術が開発され、導入されたが、その多くは圧縮ゲインの改善にのみ重きを置いている。しかし、概して見過ごされているのは、圧縮・復元処理の速度である。マルチメディアストリーミング、ビデオプロセッシング、データの無線送信など、速度重視のアプリケーションにおいては、圧縮・復元（以下「コーデック」という）の速度がゲイン圧縮と同じくらい、ことによるとそれ以上に重要となりうる。圧縮または復元に長時間を費やすのは、ほとんどのリアルタイムなシナリオにおいては無駄なことである。データを用いたアプリケーションの応答時間を最終的に判断し、そのパフォーマンスを具現化するのは、チャネル帯域幅、コーデックゲインおよびコーデック速度の組み合わせによるものである。すなわち、データがより早く送信されると、より早く当該データは処理され、使用される。その結果、データがより早く圧縮されれば、速度重視のアプリケーションが可能となる、または当該アプリケーションがより最適に動作する。
【課題を解決するための手段】
【０００８】
〔発明の概要〕
本発明は、データ圧縮方法およびその反対に相当する復元方法に関する。本方法は、効率的、高速、軽量、リアルタイム、および高度に設定可能な損失の少ないデータ圧縮であることを特徴とし、従って様々な通信要件を伴う多数のアプリケーションに適している。本発明の新規な一側面は、被圧縮データの生成および復元のために、擬似キャッシュメモリをワークスペースとして使用することである。本技術の基礎は、自然に圧縮速度を好適にする固有の能力と、固有の並行的圧縮処理によりハードウェアに用いられる潜在性とを有する新たなキャッシュマッピング圧縮（ＣＭＣ）モデルに基づく。従って、速度が最適化されたハードウェア・コーデックが可能となり、同じ帯域幅条件のもとでは、ほとんどの最新鋭の圧縮器よりも極めて早くデータストリームを処理できる。基本的に、本発明の明白な特徴は以下の通りである。
（ａ）メモリ消費が非常に低い
（ｂ）システムリソースの使用量が非常に低い
（ｃ）圧縮および復元の両方法において実行速度が非常に速い
（ｄ）ほとんどのデータフォーマットに対して競争力のある圧縮率を呈する、および
（ｅ）圧縮時間＋転送時間＋復元時間を合計したことによる、高帯域通信における最小の配信時間。
【０００９】
以上の特徴により、本方法は、組み込み型システム、ＰＤＡ、システムオンチップ（ＳＯＣ）設計、およびその他限定的なシステムリソースを有するハードウェア機器の対象となる。さらに、ＣＭＣ方法の簡易性により、安価なハードウェアまたはソフトウェアの実行が可能となる。従って、本発明は、無線型、組み込み型および電子型のハードウェアおよびソフトウェア産業にとって潜在的に高い商業的価値を有する。
【００１０】
多くの従来の圧縮方法と同様に、本発明の方法は、文字の連続および／または部分的文字列一致により生成される冗長、繰り返し、または反復使用のデータを排除することにより、ソースデータストリームのサイズを縮小し、被圧縮データストリームを生成する。ソースデータストリームは、圧縮される値、すなわちＮビットの列またはシーケンスを含んでなる。被圧縮データストリームは、後述する本発明の圧縮方法に基づいて被圧縮データストリームに挿入された圧縮コード（MISSおよびHIT）と、もとのデータストリームのサブセットを含んでなる。ソースデータストリームにおける値の冗長および繰り返しを排除する目新しい方法によって、圧縮は部分的に実現され、MISSまたはHITの圧縮コードを被圧縮データストリームに挿入して当該被圧縮ストリームからソースデータの復元が導かれる。
【００１１】
例えば、次の入力ソースストリーム「ＡＢＣＣＣＣＡＢＤＤＤＤ」は、次の被圧縮データストリーム「＜ｍ＞Ａ＜ｍ＞Ｂ＜ｍ＞Ｃ＜ｍ＞Ｃ＜ｍ＞Ｃ＜ｈ（Ｃ）＞＜ｈ（Ｃ）＞、＜ｍ＞Ａ＜ｈ（Ｂ）＞＜ｍ＞Ｄ＜ｍ＞Ｄ＜ｈ（Ｄ）＞＜ｈ（Ｄ）＞」に処理される。ここで、「＜ｍ＞」はMISSコードで、「＜ｈ（Ｘ）＞」は、それぞれの文字ＸのHITコードである。
【００１２】
本発明の最も顕著な効果のひとつは、上記例に示すように、長い文字列のように大きく、または１文字のように小さくというように、サイズ変更可能なブロックにデータを圧縮することである。一度ブロックサイズを設定すると、本方法は、１ブロックの入力データを受け取った直後に被圧縮データストリームを出力し始め、当該出力はいつでも、またいかなるブロックサイズでも停止され、また再開されるという柔軟性を有する。これは、短い文字列境界、または１つの文字境界においても必要に応じていつでも処理を再開できることを示す。これらの特徴は、まとめて動作の「排他的ストリーム」モードを構成し、特定のデータ要件に応じて特定の圧縮パラメータのカスタマイズを可能にすることにより、アプリケーションに優れた柔軟性を与えている。排他的ストリームモード動作は、標準ストリームモードまたはブロックコードと明らかに異なる。ブロックモードでは、通常は数キロバイト長のデータのブロックが圧縮器によって読み出されて処理され、その後に被圧縮データが出力される。標準ストリームモードでは、圧縮器は一つずつ文字を読み出すが、不定の数の文字が処理されるまでは被圧縮データを出力しない。この不確定性は、アプリケーションのパフォーマンスに影響を与える可能性があり、また標準ストリームまたはブロックに基づく圧縮技術では、アプリケーションが不能となる場合がある。本発明の排他的ストリームモードは、すべての被圧縮データの通信を、文字列境界または文字境界において、空間的および時間的に確定的とならしめるものである。デジタル通信における、またチャットソフトウェアアプリケーションに対する排他的ストリームモードのさらなる使用例は、詳細な説明に記述する。
【００１３】
圧縮および復元は、対称的かつ可逆的処理であり、擬似キャッシュメモリをワークスペースとして使用する。当該ワークスペースは、状態および挙動において、コンピュータアーキテクチャで使用される実際のキャッシュメモリの動作に類似する。ワークスペースの構造は、１つ以上のメモリアドレスからなり、各メモリアドレスは、それぞれ１つ以上の個別の値を保持する１つ以上の位置（location）を有し、その後に値の置換を決定する位置選択ポリシーに使用する選択的ステータスフィールドが続く。圧縮のために、ソースデータストリームから一つずつ値が読み出され、ワークスペースにマップされる。同様に、被圧縮データストリームから読み出された値は、ワークスペースにマップされ、もとの非圧縮データストリームが復元される。
【００１４】
ソースストリーム、または被圧縮ストリームから読み出される各値、またはシンボルのビット長は、定数Ｎによって決定される。ワークスペースにおけるメモリアドレス数は、定数Ｋによって決定され、最大２K個の個別のアドレスが生成される。各メモリアドレス内の位置の数は、定数Lineによって決定され、各メモリアドレスにつき最大でそれと同数の個別の位置が生成される。Ｎ、Ｋ，およびLineのすべての定数は、本圧縮および復元方法によって定義され、各方法を適宜分類するために具体的なメトリクス＜Ｎ、Ｋ，Line＞としてグループ化される。
【００１５】
メモリアドレス数および位置数を変えることにより、３種類のワークスペース配置が可能になる。すなわち、メトリクス＜Ｎ、Ｋ、１＞によって定義されるダイレクトマップ方式は、多数のメモリアドレスを使用し、それぞれのアドレスは１つの値のみを保持する。フルアソシアティブ方式は、＜Ｎ、０、Line＞によって定義され、１つのメモリアドレスのみを使用し、多くの値を保持する。そして、セットアソシアティブ方式は、メトリクス＜Ｎ、Ｋ、Line＞によって定義され、多くのアドレスを使用し、また各アドレスは多数の値を保持する。これらの配置それぞれをワークスペースとして使用し、基本的な圧縮および復元処理を行い、付加的な拡張および変更とともに、新たな系統のキャッシュマッピング圧縮（ＣＭＣ）および復元方法が導き出される。
【００１６】
本データ圧縮方法は、特定のマトリクス＜Ｎ、Ｋ、Line＞を有するワークスペース配置を用いて、データストリーム内における冗長を排除する方法である。複数のビット長の対、すなわちＫビットおよびＮビットの値が、ソースデータストリームからバッファまたはウィンドウに読み出され、それぞれメモリアドレス参照先および現在のシンボル値にコピーされる。従って、第１のＫビットはメモリアドレス参照先として読み出され、その直後に続くＮビットは現在のシンボル値として読み出されて処理される。Ｋがゼロの場合、メモリアドレス参照先はゼロである。
【００１７】
処理可能な現在のシンボル値およびメモリアドレス参照先を用いて、現在のシンボル値がメモリアドレス参照先の各値と比較される。現在のシンボル値が当該メモリアドレス参照先のいずれの値とも一致しない場合、
【００１８】
（ａ）  被圧縮データストリームにMISSコード／値が付加され、
【００１９】
（ｂ）  現在のシンボル値が被圧縮データストリームに付加され、
【００２０】
（ｃ）  現在のシンボル値がメモリアドレス参照先の１つの値に置換され、そして
【００２１】
（ｄ）  選択的に、メモリアドレス参照先のステータスフィールドが更新され、位置使用の変更が反映される。
【００２２】
しかしながら、現在のシンボル値が当該メモリアドレス参照先のいずれかの値に一致する場合は、
【００２３】
（ａ）  値が存在するメモリアドレス参照先における位置を示すHITコード／値が符号化され、被圧縮ストリームに付加され、
【００２４】
（ｂ）  選択的に、当該メモリアドレス参照先におけるステータスフィールドが更新され、位置使用の変更が反映される。
【００２５】
メモリアドレス参照先をコンテキストとして用いて、現在のシンボル値を処理すると、次のデータ値対のために、バッファまたはウィンドウはＮビット分だけ右に移動され、ソースデータストリームがすべて使われて完全な被圧縮データストリームが生成するまでそれが繰り返される。
【００２６】
ソースデータは、上述の通り、圧縮方法を逆にすることで被圧縮データから復元される。復元方法は、圧縮方法において使用したものと同じワークスペースを再利用し、また、圧縮方法について上述の通り特定のメトリクス＜Ｎ、Ｋ、Line＞を用いる。復元方法では、非圧縮ストリームにメモリアドレス参照先としてすでに出力しているＫビットを読み出す。Ｋがゼロの場合、ビットは読み出されず、メモリアドレス参照先もゼロになる。次に復元方法では、一度に１ビットずつ、HITコードまたはMISSコードが復号されるまで被圧縮データが読み出される。
【００２７】
復号した値がMISSコードの場合、
【００２８】
（ａ）被圧縮ストリームからＮビットが現在のシンボル値として読み出され、
【００２９】
（ｂ）現在のシンボル値は、非圧縮ストリームに付加され、
【００３０】
（ｃ）現在のシンボル値が、メモリアドレス参照先における１つの値と置換され、
【００３１】
（ｄ）選択的に、当該メモリアドレス参照先のステータスフィールドを更新し、位置使用の変更を反映する。
【００３２】
復号した値がHITコードの場合、
【００３３】
（ａ）当該復号した値が示す位置にて、メモリアドレス参照先から、Ｎビットが現在のシンボル値として読み出され、
【００３４】
（ｂ）選択的に、当該メモリアドレス参照先のステータスフィールドが更新され、位置使用の変更を反映する。
【００３５】
（ｃ）現在のシンボル値は、最終的に非圧縮ストリームに付加される。
【００３６】
メモリアドレス参照先をコンテキストとして用いて、現在のシンボル値を処理した後、メモリアドレス参照先は、非圧縮ストリームに先に出力されたＫビットで更新される。本方法において、被圧縮データストリームが完全に処理され、完全に復元された非圧縮データストリームが生成されるまで、HITまたはMISSのコード／値の読み出し、および復号化が続けられる。メモリアドレス参照先を生成するＫビットを読み出すために非圧縮データストリームに対して行われる入力動作は、被圧縮ストリームが基本的に「出力」ストリームであることから、好ましくない、またはまったく不可能な場合もある。現在のシンボル値からメモリアドレス参照先へ、Ｎビット分だけ左移動することにより、この出力ストリームに対する入力動作の発生を防ぐことができ、結果としてメモリアドレス参照先もＮビット分だけ左に移動する。
【００３７】
本発明は、１つの形態において、それぞれ１つ以上の個別の値を保持する１つ以上の位置を用いて、一連の値を含んでなるデータのソースストリームからのデータを圧縮する方法に関する。当該圧縮方法は、
【００３８】
（ａ）Ｋがゼロより大きい場合、ソースデータストリームから、当該ソースストリームにおける現在の読み出しポイントの直前にあるＫビットを、メモリアドレス参照先として読み出し／入力し、
【００３９】
（ｂ）ソースストリームから、現在のシンボル値としてＮビットを読み出し／入力し、
【００４０】
（ｃ）現在のシンボル値が、メモリアドレス参照先のいずれの値にも一致しない場合、メモリアドレス参照先の値のひとつと置換すべく現在のシンボル値を被圧縮データストリームに書き込み、かつ、MISSコード／値を現在のシンボル値の前に書き込み、
【００４１】
（ｄ）現在のシンボル値がメモリアドレス参照先のいずれかの値に一致する場合、メモリアドレス参照先において値が存在する位置を示すHITコード／値を被圧縮データストリームに書き込む。
【００４２】
長所として、各メモリアドレスにてすべての値を初期化した後に、（ａ）から（ｄ）が繰り返され、（ａ）において、メモリアドレス参照先の左端のビットがソースデータストリームからの読み出しに利用できない場合は、適宜初期化される。
【００４３】
本発明は、他の形態において、MISSコードおよびHITコードを含んでなる圧縮コードと併せて、少なくともいくつかのソースデータを含んでなる被圧縮データから、１つ以上の個別のコンピュータメモリアドレスをワークスペースとして用いて、非圧縮ソースデータストリームを復元する方法に関し、各コンピュータメモリアドレスは、１つ以上の個別の値を保持する１つ以上の位置を有する。当該方法は、
【００４４】
（ａ）Ｋがゼロより大きい場合、非圧縮データストリームから、当該非圧縮ストリームにおける現在の入力ポイントの直前にあるＫビットをメモリアドレス参照先として読み出し／入力し、
【００４５】
（ｂ）被圧縮データストリームから、HITが符号化された位置またはMISSの発生を示すコード値を読み出し／入力し、
【００４６】
（ｃ）当該値がMISSコードの場合、被圧縮ストリームからＮビットを現在のシンボル値として読み出し、当該シンボル値を書き込み、（ａ）にて取得したメモリアドレス参照先の１つの値と置換し、また非圧縮ストリームに書き込み、
【００４７】
（ｄ）当該値がHITコードの場合、（ａ）にて取得したメモリアドレス参照先にて復号化されたHITコードが与えられた位置から、現在のシンボル値としてＮビットを読み出し、当該現在のシンボル値を非圧縮ストリームに書き込む。
【発明を実施するための最良の形態】
【００４８】
〔発明の詳細な説明〕
本キャッシュマッピング圧縮（ＣＭＣ）方法は、コンピュータ内、すなわち中央処理装置（ＣＰＵ）とメインメモリの間で生じる内部データキャッシング機構に類似するモデルに基づく。ひとつの相違点は、本ＣＭＣ方法は、コンピュータアーキテクチャで行われるようなメモリアクセスの高速化よりも、圧縮を行うためにキャッシュのデータ局所性特性を利用することである。ここで説明するＣＭＣ方法は、有限状態オートマトンの状態を示すものであり、それ自体として、ソフトウェア成果物またはハードウェア成果物として実現されうる。本明細書を通して、データの圧縮について言及する場合、入力ストリームはソースストリームを、出力ストリームは被圧縮ストリームをそれぞれ示すものとする。同様に、復元の場合、入力ストリームは被圧縮ストリームを、出力ストリームは復元ストリームをそれぞれ示すものとする。
【００４９】
本方法では、ソースストリームおよび復元ストリームの両方を、ブロックと称する固定長Ｎビット値を有するシーケンスとして考える。ソースシンボルを直接処理せずに、Ｎビットのデータブロックで動作する理由は２つある。第１に、１つのブロックは、キャッシュ内の最小データ転送単位であるキャッシュラインと同じサイズである。第２に、ブロックのサイズは、ソースシンボルのビット長と関係なく設定される。すなわち、圧縮パラメータを制御し、ソースストリームの特徴とよりよく一致させることができ、従ってより高い圧縮率を図ることができる。しかし、提示する請求項群が理解しやすいように、Ｎビットのデータブロックは、現在のシンボル値ともいう。
【００５０】
ＣＭＣ圧縮方法は、ソースストリームから、一度にＮビットのデータブロックを読み出す。現在のブロックが、キャッシュ内の特定の位置にある場合、ヒットとなる。そうでない場合は、ミスとなる。次に、当該圧縮方法は、最大２つのシーケンス、すなわちＨビットからなるＨｉｔコード、または現在のデータブロックが後続し、かつＭビットからなるＭｉｓｓコードの一方を出力する。当該圧縮方法は、ソースストリームからのすべてのブロックが処理されるまで続けられる。
【００５１】
図１は、圧縮前および圧縮後におけるブロックＢ、Ａ、Ｂ、Ｃからなる任意のストリームの状態を示す。例えば、入力シーケンスが｛Ｂ、Ａ、Ｂ、Ｃ・・・｝である場合、仮想被圧縮出力シーケンスは、｛＜miss＞＜Ｂ＞、＜hit＞（Ａに対して）、＜hit＞（Ｂに対して）、＜miss＞＜Ｃ＞・・・｝である。両方のシーケンスを比較すると、最初と最後のブロックは、それぞれのミスにつきＭビットの拡張となり、間の２個のブロックは、それぞれのブロックに対して（Ｎ−Ｈ）ビットの圧縮要素として寄与している。従って、ヒットの総数を知ることにより、圧縮率を正確に計算できる。
【００５２】
ミスコードとヒットコードには概念的差異がある。ミスコードは、単純にブーリアンマーカー（boolean marker）の役割を果たす。当該ミスコードは、復元器に対してミスが発生したことを通知し、従ってミスしたブロックが次に続くことを通知する。対照的に、ヒットコードは、ブロックがきちんとキャッシュされたことを示すだけではなく、当該キャッシュのメトリクスに応じて、ヒットコードは、ヒットが生じたセット内のライン番号を符号化する必要がある。ミスコードは、便宜上１ビット値として定義されるが、両方のコードの平均長を最小限にするために、ヒットコード長と折り合いをつけてもよい。ライン番号およびセットは、それぞれ位置番号およびメモリアドレス参照先ともいう。
【００５３】
図１の出力シーケンスを視覚的に調べると、出力に多くのヒットコードが現れるほど、圧縮が向上し、ヒットおよびミスのコード長が増加すると圧縮が低下することがわかる。セット当たりに配置するライン数を増やすことにより、ヒット数を最大にすることができるが、それにより残念ながら、ヒットコード長も増加する。従って、明らかにここに最小化の問題が生じる。
【００５４】
現在のブロックがキャッシュ内の特定の位置にある場合、ヒットが生じる。現在のブロックが実際にマッピングされる特定の位置が重要となる。マッピングは、第一にヒットを生じさせ、図１からわかるように、圧縮を達成するために出力シーケンスのサイズを縮小させる。ブロックをキャッシュするために、２つの入力、すなわちブロックとアドレスの入力が必要である。アドレスは、ブロックをマップするキャッシュセットを決定するものであり、そのため、「キャッシュマッピング・アドレス」ともいう。
【００５５】
入力されるブロックに対する適切なマッピングアドレス関数を抽出するために、一般的にテキストで用いられるデータの冗長のタイプ、すなわち文字列の一致と文字の連続を描出することは有用である。以下のシーケンスを考える。
ＡＢＣＣＣＣＡＢＤＤＤＤ…
【００５６】
当該シーケンスには、１つの文字列一致（サブ文字列「ＡＢ」は２番目のサブ文字列「ＡＢ」と一致している）と、２つの文字連続（「ＣＣＣ…」と「ＤＤＤ…」）がある。ＣＭＣ圧縮器を効果的なもととするために、キャッシュ内ですでに遭遇したブロックに対して、入力されるブロック（文字）をヒットさせ、この冗長を利用する必要がある。すなわち、それぞれのブロックの内容を比較した場合に一致するように、両方に対して同一のマッピングアドレスを取得する。シーケンスにおける最初の３文字「ＡＢＣ」がすでに処理されたとする。そのキャッシュ状態を表１に示す。
【表１】
2009531976.tif 000003
【００５７】
次に続く「ＣＣＣ…」の文字連続に対するヒットを取得するために、入力されるそれぞれの「Ｃ」は、すでに遭遇した「Ｃ」と同じマッピングアドレスにキャッシュされる。これは、先行する文字自体をキャッシュマッピング・アドレスへの入力として用いることになり、すなわち先行する文字に対応するコンピュータ２進数表示を用いてキャッシュマッピング・アドレスを生成することになる。その結果、マッピングアドレスが先行する文字「Ｃ」の関数となるラインに文字「Ｃ」がキャッシュされる場合、新たな「Ｃ」の連続文字は、マッピングアドレスが同じであるため、比較した際にヒットとなる。
【００５８】
図２は、ＣＭＣ圧縮方法をより詳しく示すものであり、マッピングアドレスＫが８ビット長で、現在のブロックサイズＮもまた８ビット長であり、それぞれのメモリアドレスはデータブロックを保持する位置を１つだけ含む場合である。ソースストリームから読み出された現在のブロックは、現在の文字（８ビット）を受け取り、マッピングアドレスには前の文字（８ビット）が割り当てられている。本圧縮方法は、ソースストリームの最初の８文字を処理し、処理したシーケンスを被圧縮ストリームに出力している。ミスコードおよびヒットコードは、それぞれ＜ｍ＞Ｘおよび＜ｈ（Ｘ）＞として示され、Ｘはミスまたはヒットとなったブロックである。図２はまた、キャッシュの現在の（２番目のサブ文字列「ＡＢ」が処理された後の）状態、および最後の（最後の「Ｄ」文字が処理された後の）状態をも示している。ヒットはキャッシュ内において丸で示され、その他はミスである。
【００５９】
図２に示すように、圧縮処理は、文字連続「ＣＣＣ…」および「ＤＤＤ…」を検出するだけでなく、２番目のサブ文字列「ＡＢ」を検出し、文字「Ｂ」に対応するヒットを生成することにより文字列の一致も検出している。キャッシュラインは、常に１つのブロックのみを保持する。これはダイレクトマップされたキャッシュ配置の場合であり、図４を参照して、より詳しく後述する。右端の文字は、キャッシュ内の最新のブロックであることを示す。ヒットが生じた場合、現在のブロックは、キャッシュ内において説明のためにヒットとなったことを示す丸を付しているが、再びキャッシュされない。マッピングアドレスは、キャッシュ内の特定のセットを実際に指している。
【００６０】
ＣＭＣコーデックは、使用する内部キャッシュ構造と密接に関連している。従って、キャッシュのメトリクス、例えばセット当たりのライン数を修正すると、本圧縮方法の挙動が劇的に変わるという効果をもたらす。
【００６１】
本ＣＭＣ方法は、３つのパラメータ（Ｎ、Ｋ、Line）と１つのコードで定義される。パラメータは、内部キャッシュのメトリクス（ブロック当たりのビット数、セットのアドレス設定用ビット数、ライン数）を記述し、当該コードは被圧縮ストリームにおけるヒットおよびミスを示すために使用される符号化を定義する。Lineはまた、２Lライン数の符号化に必要なビット数であるＬで定義してもよい。
【００６２】
本ＣＭＣ圧縮方法は、３つの特定のキャッシュ構造の１つを用いて、効果的に実行されてもよい。３つのキャッシュ構造は、本圧縮方法の３つの特定の形態を定義するものであり、ダイレクトマップ方式、セットアソシアティブ方式、またはフルアソシアティブ方式という。当該３つの方式を、説明のために擬似コードを用いて記述することにより、本圧縮方式と、詳細ではないが当業者には明らかであろう当該３つの方式の効果的な実行について、よりよい理解を提供する。
【００６３】
概ね図３を参照して、方法１０は、本ＣＭＣ方法の一般的な実行を示す。方法１０は、一連の値を含んでなるデータのソースストリームからのデータを、１つ以上の個別のコンピュータメモリアドレスをワークスペースとして用いて圧縮する。各コンピュータメモリアドレスは、それぞれ１つ以上の個別の値を保持する位置を１つ以上有する。
【００６４】
ソースデータストリームにおける現在の読み出しポイントの直前にあるＫビットは、Ｋがゼロより大きい場合、当該ソースデータストリームから、メモリアドレス参照先として読み出される、あるいは入力される（ステップ２０）。現在の読み出しポイントの前にビットが存在しない場合、Ｋビットは読み出されず、Ｋにはゼロの値が割り当てられる。例えば、図３と合わせて図２を参照して、ソースデータストリームが「ＡＢＣＣＣＣＡＢＤＤＤ」の場合、最初の読み出しポイントは最初のＡである。Ａは最初の位置にあるため、Ａに先行するビットは存在しない。従ってソースデータストリームからはＫビットは読み出されない。そこでＫにはゼロ値が割り当てられる。
【００６５】
次に、Ｎビットは、現在のシンボル値、本例の場合Ａとして、ソースストリームから読み出される（ステップ３０）。
【００６６】
当該シンボル値がメモリアドレス参照先のいずれの値にも一致しない場合に、現在のシンボル値、すなわちＡを書き込み、メモリアドレスのいずれかの１つの値と置換する。また、現在のシンボル値が後続するミスコード＜ｍ＞が、被圧縮データストリームに書き込まれる。本実施例において、現在のシンボル値、すなわちＡは、メモリアドレスのすべての値、実際はゼロである１つの値に一致しない。従ってＡが後続するミスコード＜ｍ＞が被圧縮データストリームに書き込まれる（ステップ４０）。
【００６７】
当該現在のシンボル値がメモリアドレスのいずれかの値に一致する場合、値が見つかったメモリアドレス参照先の位置を示すヒットコードが被圧縮ストリームに書き込まれる（ステップ５０）。本実施例の場合、値Ａはメモリアドレスがゼロであるメモリアドレスにおけるいずれの位置にも存在しないので、ヒット値は被圧縮データストリームに書き込まれない。
【００６８】
ステップ６０において、それぞれのメモリアドレスにおけるすべての値を初期化した後に、ソースデータストリームにおける各値に対して、本方法が繰り返される。各メモリアドレス参照先の左端のビットは、ソースデータストリームから入手できない場合は、適切に初期化される（ステップ６０）。従って、最初にステップ２０が繰り返され、現在の読み出しポイントであるＢの直前のＫビットが、ソースデータストリームから読み出されまたは入力され、メモリアドレス参照先には、現在の読み出しポイントの直前にある値、すなわちＡが割り当てられる（ステップ２０）。次に、値Ｂは、ソースデータストリームからＮビットとして読み出され、現在のシンボル値に割り当てられる（ステップ３０）。ステップ４０にて、現在のシンボル値、すなわちＢは、メモリアドレスＡのすべての値、実際は１つの値に一致しないため、現在のシンボル値が書き込まれ、メモリアドレスＡの値と置換される（ステップ４０）。続いて、現在のシンボル値、すなわちＢが後続するミスコードが、被圧縮データストリームに書き込まれる。その結果、現在の被圧縮ストリームは＜ｍ＞Ａ＜ｍ＞Ｂとなる。
【００６９】
方法１０は、次の２つの値、すなわちＣとＣのために、さらに２回繰り返される。方法１０を５回目繰り返す際、５番目の値、すなわち左から３番目のＣがソースストリームからＮビットとして読み出され（ステップ３０）、直前の値、それもまたＣである値がメモリアドレス参照先として入力される（ステップ２０）。ステップ４０にて、現在のシンボル値Ｃが、実際Ｃに対応するメモリアドレスの現在値に一致するため、被圧縮ストリームにはミスコードおよび現在シンボル値は書き込まれない。その代わりに、ステップ５０にて、現在のシンボル値Ｃがメモリアドレス参照先Ｃの値のうちひとつに一致するため、値Ｃが存在するメモリアドレス参照先における位置を示すヒットコードが、被圧縮ストリームに書き込まれる。これにより、現在の被圧縮データストリームは、＜ｍ＞Ａ、＜ｍ＞Ｂ、＜ｍ＞Ｃ、＜ｍ＞Ｃ、＜ｈ（Ｃ）＞となる。方法１０は、すべての値が処理されるまで繰り返される。
【００７０】
処理時間および効率、さらに圧縮ゲイン、すなわちソースデータストリームのサイズに対する被圧縮データストリームのサイズの最適化のために、所望通りに方法１０を修正してもよい。例えば、ステップ２０において、読み出されたＫビットは、同数の、あるいはそれより少ないビット数に減少／変換させて、メモリアドレス参照先として使用されるワードを生成してもよい。例えば、読み出されたＫビットは、おそらくはワークスペースサイズを小さくするためのハッシュストラテジ（hashing strategy）を施して、同数またはそれより少ないビット数に変換され、その後の圧縮方法および復元方法におけるステップでメモリアドレス参照先として使用される。
【００７１】
Ｋビットを少ないビット数に変換するひとつの方法、従ってワークスペースとして必要なメモリ量を抑える方法は、ハッシュストラテジを用いることであり、それに基づいてＫビットはハッシュ関数に入力され、Ｋビット値がそれより小さいＲビット値に変換されてメモリアドレス参照先として使用される。単純であるが強力なハッシュ関数を説明するために、２つの整数の間における除算の剰余を返すモジュロ演算を考える。すなわち、Ｄおよびｄが整数で、Ｄ＞ｄの関係にある場合、「D modulus d」は、Ｄ／ｄの剰余を返し、０からｄ−１の間における他の整数となることが確実である。これは、ソースストリームから読み出されたすべての２Kメモリアドレスが利用可能なワークスペースメモリにおいてアドレス指定されない場合に非常に便利である。この場合、Ｄは、もとのメモリアドレス参照先に割り当てられ、ｄは、実際に利用可能なメモリアドレスの総数、２Rに割り当てられ、「D modulus d」の結果は、新たな小さいサイズのメモリアドレス参照先に割り当てられ、その後ワークスペースのアドレス指定に用いられる。
【００７２】
さらに、ステップ２０において、メモリアドレス内の位置使用を把握するために、メモリアドレスのオプションステータスフィールドを使用してもよい。本方法の処理が進行し、ステップ４０または５０のいずれかにおいて、値がメモリアドレスとして読み出し／書き込みされた後に、ステータスフィールドが更新される。ステータスフィールドは、ミスが生じた際にどのように値が置換されるかを把握するために、セットアソシアティブ方式の圧縮方法において使用される。
【００７３】
ステータスフィールドは、ミスが生じた場合、すなわち現在のシンボル値がメモリアドレス参照先のいずれの値にも一致しない場合に、値を置換するために使用されるストラテジに応じて異なって使用されてもよい。ストラテジに関わらず、ステータスフィールドによって、特定のメモリアドレスに対して、値を置換する場合に使用される位置を最適に推測できることが期待される。実際のところ、ステータスフィールドは、メモリアドレスに存在する位置と同数のカウンタを含む。それぞれのカウンタは、設定されている特定の置換ポリシーに基づいて、各位置の置換される順番を示すランクを保存することにより、特定位置の把握を記録する。例えば、各メモリアドレスは４個の位置を有し、ステータスフィールドは、ある時点において、３、１、０、２の４個の値をそれぞれ保存し、かつ各位置に関連づけられた４個のカウンタを有する近時最少使用（LRU）の置換ストラテジを仮定する。すなわち、メモリアドレス内における位置番号０、１、２、３は、ステータスフィールド内においてそれぞれ３、１、０、２の値を有するLRUカウンタに関連づけられる。LRUストラテジにおいて、位置０は、値３と最もLRUカウンタの値が高いため、最も直近に使用されたことを示す。次は、LRUカウンタが２である位置３で、LRUカウンタが１である位置１がそれに続き、最後はLRUカウンタが０である位置２である。従って、値が置換される場合、最も低いLRUカウンタ値に関連付けられている位置の番号、この場合、位置２が置換のために選択される。それは、置換ストラテジ自体が示すように、最近最も使われなかった位置を示すからである。他方、最も古い値の置換ポリシーのように、他のストラテジを用いる場合、ステータスフィールドは、異なって実行される。それにより、ステータスフィールドは、カウンタではなく、新たに置換された位置が列の先頭に配置され、最も古くに置換された位置が列の末尾から得られ、好ましくは先入れ先出し（FIFO）列と考えられる。使用する置換ストラテジに関わらず、ミスが生じた時に値を置換する位置として選択される位置を決定する際に、ステータスフィールドが用いられる。
【００７４】
方法１０は、様々なキャッシュ構造を用いた様々な圧縮スキームを含むように修正されてもよく、ダイレクトマップ方式のＣＭＣ方法１００（図４）、セットアソシアティブ方式のＣＭＣ方法２００（図５）および、フルアソシアティブ方式のＣＭＣ方法３００（図６）が含まれる。
【００７５】
図４について言及すると、通常、方法１００は単純なキャッシュ配置を用いる。当該配置において、キャッシュは１セット当たり１つのライン数からなり、いずれの特定セットにおいても１つのデータブロックが保存される。従って、キャッシュのメトリクスは＜Ｎ、Ｋ、１＞である。この構造では、置換ポリシーが関与しない、または逆にストラテジが最小であるため、内部のブロック処理が簡素化される。すなわちミスが生じた場合、セット内で利用可能なブロックのみ置換される。ダイレクトマップ方式のキャッシュには、セットアソシアティブ方式の圧縮方法２００やフルアソシアティブ方式の圧縮方法３００では実行される置換ポリシー用のステータスビットが必要ない。従って、ダイレクトマップ方式のキャッシュは、本発明の他の態様と比して、セットアソシアティブ式またはフルアソシアティブ方式のキャッシュより高速で、また多くのリソースを利用しない。しかしながら代償として、他の配置と比較するとヒットの割合が低い。
【００７６】
具体的に図４を参照して、ダイレクトマップ方式のＣＭＣ圧縮方法１００には、宣言された現在のBlock、Line、およびSetを有する位置決め変数が含まれる。改めて、これらは、それぞれ現在のシンボル値、位置番号、およびメモリアドレス参照先を示す。方法１０（図３）と同様のステップが、図４では１００に増加している。Setは、ゼロに初期化される（ステップ１０５）。ソースデータストリームからＮビットが読み出され、Blockにコピーされる。当該ストリームがファイルを示す場合、対応付けられたファイルポインタが更新される。すなわちＮビット分だけ前進する（ステップ１３０）。データストリームの末尾に到達するまで、データブロックはソースストリームから読み出される（ステップ１３０）。
【００７７】
現在のブロックが特定のセットから検索され、ダイレクトマップ方式のキャッシュでは、１セットにつき１ラインしか存在しないため、当該唯一のラインが検索される（ステップ１３４）。ブロックが当該ラインの内容と一致しない場合、ミスが発生し、当該ブロックがキャッシュラインに書き込まれる（ステップ１３６）。
【００７８】
さらに、ブロックが見つからない場合、「miss」コードまたはマーカーとなる１ビット値が被圧縮ストリームに書き込まれる（ステップ１４０）。マーカーの値は、定数MISSとなる（ステップ１４０）。さらに、現在のブロックが被圧縮ストリームに書き込まれる（ステップ１４２）。詳細は後述するが、被圧縮データストリームの復元または伸張中において、ミスが生じた場合は、当該復元方法ではキャッシュからブロックを取得できない。それ故に、後で再生できるように、被圧縮ストリームにブロックを複製する必要がある（ステップ１４２）。
【００７９】
ブロックが見つかった場合（ステップ１３６）、ヒットしたことを示す１ビット値が被圧縮ストリームに書き込まれる（ステップ１５０）。復元方法において、ヒットマーカーを用いてキャッシュからブロックが抽出される。ダイレクトマップ方式の方法１００では、１セット当たり１つのラインしか存在しないため、ステップ１５０にて被圧縮ストリームのライン番号を符号化する必要はない。
【００８０】
現在のセットの値は、方法１００の次の繰り返しのために用意される（ステップ１６０）。更新処理は、概念的にはソースストリーム上のプレースホルダを移動すること、すなわち図２に示すように、各繰り返しの最後にＮビットを右に移動し、ストリームのそのポイントからＫビットを読み出すことに類似する。この動作は、基本的には、セットの変数Ｎビットの内容を左に移動し、ブロックからＮビットを読み出すことに等しい。現在のブロックには、ソースストリームから読み出した同じＮビットが含まれるためである。
【００８１】
ダイレクトマップ方式の圧縮方法１００は、マトリクス＜Ｎ、Ｋ、１＞を有する特定のダイレクトマップされたワークスペースを使用する。この配置において、１つのメモリアドレスにつき１つの位置あるいは１つのラインのみが使用され、１つの値のみが保存される。これにより、ポリシーもステータスフィールドも不要のため、ミスした値の置換は簡単となる。また、各メモリアドレスは、１つの値のみを保存する１つの位置を有するため、HITコードは、単純に、現在のメモリアドレス参照先に存在する値の発生、すなわちヒットの発生を示す。
【００８２】
図５を参照して、方法２００は、本圧縮方法を形成するセットアソシアティブ方式のＣＭＣ圧縮方法で、方法１０および１００と同様のステップが、それぞれ１００および２００に上がっている。方法１００と同様に、ステップ２０５において、Block、Line、およびSetは初期化される。次に、データブロックはソースデータストリームから読み出される。ダイレクトマップ方式の方法１００と異なり、検索されるラインは１つより多い。それ故に、特定のセットからすべてのラインが検索される（ステップ２３４）。ブロックがいずれのラインの内容にも一致しない場合、ミスが生じ、ブロックはキャッシュに書き込まれる（ステップ２３６）。
【００８３】
方法１００と同様に、ブロックが見つかった場合、ヒットを示す１ビット値が被圧縮ストリームに書き込まれる（ステップ２５０）。しかし、１セットに複数のラインが存在するため、非圧縮データストリームの復元の間において、復元方法がどのラインからブロックを取り出すべきかわからない。その結果、ヒットマーカーでは不十分で、復元方法には、ヒットが生じたライン番号が必要となり、当該ライン番号が次のステップに渡される。
【００８４】
ヒットマーカーが書き込まれた後、ヒットが生じたライン番号が符号化され、被圧縮ストリームに書き込まれる（ステップ２５２）。符号化は、当該ラインの特定のために十分であればよく、そのため簡単なライン番号のバイナリ表示であるＬビットからなる固定コード長でよい（ステップ２５２）。
【００８５】
しかし、ミスが生じた場合、ステップ２００は、ステップ１００と同様の処理を進める。すなわちミスマーカーを被圧縮ストリームに書き込み（ステップ２４０）、ミスブロックを被圧縮ストリーム（ステップ２４２）に書き込み、次の繰り返し用に現在のセットの値を作成する（ステップ２６０）。
【００８６】
方法２００のさらなる具体的実行のひとつにおいて、方法２００が、値を置換する際にどの位置を使用するかを決定する置換ポリシーをさらに含んでもよい。これはSearchBlock_WriteIfMiss()のメソッドまたは関数によって内部的に行われる（ステップ２３６）。代表的な置換ポリシーには、最も好ましいものから最も好ましくないもの順で、近時最少使用（LRU）、先入れ先出し（FIFO）または最も古くに使用、最も使用頻度が低い（LFU）、ランダムなどが含まれる。これら置換ポリシーに関連づけられたメソッドは、なんらかの理由によりキャッシュ内でブロックへのアクセスがある毎に、ReadBlock()およびSearchBlock_WriteIfMiss()のメソッド内で呼び出される（ステップ２３０および２３６）。
【００８７】
置換ストラテジがどのように機能するかを理解するために、以下の具体例を用いて、近時最少使用（LRU）の置換ポリシーを説明する。メモリアドレスが４個の位置を有し、従ってそれぞれに関連づけられた４個のLRUカウンタをステータスフィールドが含む場合を考える。圧縮処理のある時点において、LRUカウンタは、それぞれ値３、０、２、１を含むと仮定する。すなわち、位置０は、それに関連づけられたLRUカウンタが最大値３を有するため、最も直近に使用した位置であり、位置１は、それに関連づけられたLRUカウンタが最小値０を含むことから、最近最も使われなかった位置であることを示す。従って、ミスが生じた場合、最近最も使われなかったことを示す、LRUカウンタが０である位置１が置換用に選択される。ここで、位置３においてヒットが生じた場合を考える。
【００８８】
本実施例において、LRUカウンタは、以下のように更新される。位置３は、最も直近に使用されているため、すべてのLRUカウンタを適宜更新し、位置使用における新たな変更を反映させる必要がある。これはLRUカウンタの一般的な更新処理であり、ヒットが生じた位置に関連づけられた現在のLRUカウンタ値は、Ｔとして読み出される。次に、Ｔより大きい値を有するすべてのLRUカウンタは、値を１ずつ減らされる。最後に、現在のLRUカウンタに最大値が割り当てられ、最も直近に使用された位置としてタグが付される。従って、現在のLRUカウンタ値が３、０、２、１で、位置３においてヒットが生じた場合、当該カウンタは以下の通り更新される。すなわち、Ｔに位置３のLRUカウンタ値である１が割り当てられる。次に、Ｔ＝１より大きい値を有するすべてのLRUカウンタの値は１ずつ減らされる。従って、LRUカウンタの値は、２、０、１、１となる。最後に現在のLRUカウンタには最大値３が割り当てられる。従って、LRUカウンタは、２、０、１、３となる。要するに、各位置の使用ランクを示すLRUカウンタ値が常に異なるようにLRU置換ポリシーは機能する。
【００８９】
さらに別の形態において、最も定期的に使用される低い位置が短いコードで示され、使用頻度の低い高い位置に対して長いコードが割り当てられるように、ヒットコードおよびミスコードの割り当てにおいて、可変長符号化スキームを用いてもよい。
【００９０】
文字通り、いくつかの可変長符号化スキームを、ヒットコードおよびミスコードの割り当てに利用できる。例えば、メモリアドレス当たりの位置数が少ない場合、例えば、２、３、または４個である場合、各位置の番号を示すためにハフマンを用いることができる。位置数がそれよりも多い場合、ハフマンスキームより生成が非常に速いことから、スタートステップストップ(start-step-stop)符号が好ましいと思われる。
【００９１】
例えば、可変長符号化スキームには２個の段階（pass）が含まれる。第１の段階は、各位置における使用頻度を計算するために用いられ、第２の段階は、最も頻繁に使用する位置にはより短いコードを、使用頻度が低い位置にはより長いコードを割り当てるように、各位置を示す可変長コードを割り当てるために用いられる。例えば、メモリアドレス当たり２つの位置が使用されると仮定する。第１の段階は、位置０および位置１に発生するミスの確率およびヒットの確率をカウントするために、圧縮方法を実行することにより実行される。従って第１の段階の間においては、いかなる出力も被圧縮ストリームに書き込まれない。
【００９２】
ｐＡがミスの確率、ｐＢが位置０におけるヒットの確率、およびｐＣが位置１におけるヒットの確率として、ｐＡ、ｐＢ、およびｐＣとして確率を取得すると、ｐＡ、ｐＢ、およびｐＣに関するハフマン木が生成され、図１１のハフマン木に示されるように、ミス（Ａ）、位置０におけるヒット（Ｂ）、および位置１におけるヒット（Ｃ）を示すハフマン符号が割り当てられる。Ａ＜Ｂ＜Ｃである場合、ｐＡ＜ｐＢ＜ｐＣであり、従って、Ａ、Ｂ、およびＣには、次のハフマン符号、すなわち、１１、１０、および０が割り当てられる。
【００９３】
さらに、他の方法として、位置番号を符号化するのではなく、各位置につき１つのステータスフィールドに保持されるLRUカウンタの値を符号化する。LRUカウンタは、LRU置換ポリシーを実行するために用いられ、より大きい値がより最近使用された位置を示し、またその逆をも示すように、各位置の使用ランクを示している。従って、より大きいLRUカウント値には、より短いコードが割り当てられ、小さい値にはより長いコードが割り当てられる。キャッシュライン番号自体を符号化せずに、キャッシュラインに関連づけられたLRUカウンタを符号化する理由は次の通りである。すなわち、より最近使用されたラインは、最近使用されていないラインよりも今後においてヒットを取得する確率が高いため、各ラインの使用ランクは、そのラインのヒット発生確率に相関するといえる。それ故に、このような仮定において、最も高いランクを有するカウンタのラインは、次のヒットを取得する確率が高く、２番目に高いランクが次に続くという具合に、ブロックが一致する確率が最も低いラインを示すランク０まで続く。LRUカウント値がより高い（より最近アクセスされた）ラインは、LRUカウント値が低いラインよりも多くのヒットを生成することが期待される。この傾向が満たされるならば、ヒットを示す平均コード長が減少され、圧縮が改善される。
【００９４】
圧縮方法１０、１００および２００は、コンピュータメモリをワークスペースとして利用することもでき、現在のストリーム値に対する入力として利用されるＮビット、メモリアドレスへの入力として利用されるＫビット、メモリアドレス参照先にて値が見つけられた位置を示すＬビット、およびヒットまたはミスが生じたかを示す出力として利用される１ビットを有する擬似キャッシュとして実行される。
【００９５】
すべてのライン番号が均一に配分される場合、固定長コードを用いてライン番号を示すことは有効である。しかし実際のところ、この不変性は好ましくない場合がある。キャッシュラインが、不均一配分となる場合、より頻繁にアクセスされるラインに対してより短いコードを割り当てることにより、ヒットおよびミスの平均コード長を減らすことができる。キャッシュセット当たり複数のキャッシュラインが存在する圧縮方法を選択する場合、ヒットを示す１ビットを利用することの有意性が失われる。ミスの発生およびヒットが生じたライン番号に関して、符号化の問題を改めて述べる必要がある。それ故に、基本的には、（１＋LINE）の符号化シンボル、すなわちMISSを示す符号「１」とそれぞれのHITが生じるキャッシュラインを示す符号「LINE」が存在する。
【００９６】
ひとつの制限として、セット内における位置、すなわちライン番号によるラインの符号化は、ライン番号に相関関係がほとんどない場合、すなわちラインが均一配分である場合、コード長の縮小の点においてまったく利得がない。これは、例えば、方法２００について上述したように、LRUカウンタの値を使用するなど、キャッシュラインに関わる別の属性を代わりに使用することで克服できる。他の制限は、ヒットおよびミスの符号化、復号化により時間がかかることである。しかし、これは符号化およびモデル化を考慮したすべての方法に関して一般的なことである。そのような時間的オーバーヘッドは、ヒットコードの非均一配分を実施するための、前述した変動性と併せて、ヒットおよびミスコードの静的割り当てを利用することによって抑えることができ、可変長符号化スキームを最大限に活用して、平均コード長を縮小し、かつ圧縮を改善できる。
【００９７】
ここで、図６および７について、フルアソシアティブ方式のＣＭＣ方法３００は、２K個のセットを示すビット数であるＫが最小値、すなわちゼロビットに減少した場合のケースに向けられている。その結果は、キャッシュ全体において１つのみのセットを含むフルアソシアティブキャッシュである。図７は、メトリクスが＜Ｎ、０、２L＞であるフルアソシアティブキャッシュ配置の一例を示す。方法３００によって実行される内部キャッシュ処理の重要な効果のひとつは、マッピングアドレスが原則的に取り除かれることである。その結果、ＣＭＣコーデック方法３００は、キャッシュにおいてブロックの検索（ステップ３３４）、ブロックの読み出し（ステップ３３０）、およびブロックの書き込み（ステップ３４０、３４２および３５０）を行う際に、現在のブロックのみを必要とする。セットの変数は常にゼロである。尚、方法１００および２００と異なり、方法３００はループの最終ステップ、すなわちステップ３４２、３５２の後に、変数の更新を行う必要がない。
【００９８】
フルアソシアティブ方式の圧縮方法３００は、方法１００および２００よりも多くのヒットを生成するが、方法３００はより高い圧縮率をもたらさない。それには２つの理由がある。第１に、良好なヒット率を得るために十分なブロックを収容できるように、セット内におけるラインの数は多くなければならない。第２に、ヒット数が多い場合でも、符号化されたそれぞれのヒットラインが被圧縮ストリームで同一の長さを有するため、固定長符号化ではヒット数の多さを生かすことができず、キャッシュセット当たり２N個のキャッシュラインを使用した場合、結果的に入力されるデータブロックの長さは同じ、すなわちＮビットになる。しかしながら後者の変形は有効な方法であり、以下により詳しい説明をする。
【００９９】
フルアソシアティブ方法３００において、メトリクスが＜Ｎ、０、Line＞のフルアソシアティブワークスペースを使用する。この配置において、複数の位置を有する１つのメモリアドレスを使用し、同一のメモリアドレスに複数の値を同時に保存する。これにより、伸張器がもとのデータストリームを復元するための、被圧縮ストリームにおけるヒットが生じる位置の符号化がさらに複雑になる。従ってこの場合、位置を示すためにHITコードが用いられる。
【０１００】
さらに、フルアソシアティブ方式の方法３００は、メモリアドレス当たり少なくとも２N個の位置を用いて、各位置を特定の値０、１、２…、２N−２，２N−１に初期化することにより、MISSコードをまったく排除してパフォーマンスを向上させるような変更を施すこともできる。従って、入力される値はＮビット長であるため、最大２N個の値のうち１つは常に、ワークスペースにおいてすでに初期化された位置のいずれかの値に一致する。この場合においても、当該位置を示すためにHITコードが用いられる。この場合にワークスペースに用いられる具体的なメトリクスは、＜Ｎ、０、Line＞で、Lineは２のＮ乗に等しく、すなわち＜Ｎ、０、Line＞＝＜Ｎ、０、２N＞となる。
【０１０１】
ここで、図８を参照して、一般的なＣＭＣ圧縮方法４００は、方法１００、２００および３００を含むが、これは本発明から容易に察することができる。方法４００は、前述の方法１００、２００および３００のステップを含み、それぞれ１００〜３００に上がったている。
【０１０２】
方法４００において、データブロックはソースストリームから読み出され（ステップ４３０）、見つからない場合はキャッシュされ（ステップ４３４、４３６）、ヒット（ステップ４５０、４５２）およびミス（ステップ４４０，４４２）は、それぞれ符号化される。セットアソシアティブスキームにさらにラインが追加される場合（ステップ４３９）、ヒットラインも符号化する必要がある（ステップ４５２）。当該アソシアティブスキームにセットが１つのみの場合は、セットアドレスは関係ないため、ステップ４６０および４６２は実行されない。具体的に示したキャッシュ方法との主な違いを、図８において強調太字で示している。
【０１０３】
方法４００と方法１０、１００、２００、および３００とのさらなる違いは、ヒットマーカーがヒットラインの符号化と統合され、また符号化そのものはヒットとミスの両方に開放される。これは、無数の符号化の可能性へと展開し、可変長スキームが最も有効となりうる。対照的に、セットアソシアティブ方式およびフルアソシアティブ方式、すなわち方法２００および３００の場合、ラインのバイナリ表示を有するＬビットからなる固定長スキームによって、符号化が明白に規定される。
【０１０４】
方法４００において、ヒットおよびミスは符号化される、または方法２００において割り当てられたと同様に割り当てられる。例えばヒットおよびミスは、最も定期的に使用される下方の位置が短いコードで示され、あまり頻繁に使用されない上方の位置は長いコードで示されるように符号化される。HITコードに対する可変長コードは、現在のシンボル値が存在するメモリアドレス参照先における位置、すなわちヒットが起こった位置を示し、LRU置換ポリシーと合わせて、不一致（ミス）が生じた際にどの値が示されるかを決定する。圧縮方法４００は、ヒットに対する可変長コードを符号化する。同様に、復元方式は、当該コードを復号する。これは、各メモリアドレスが２個以上の位置を有する場合、すなわち複数の値を同時に保存できる場合に適用される。従ってLineが、厳密に１より大きい特定のメトリクス＜Ｎ、Ｋ，Line＞を有するセットアソシアティブ構成の場合に適用可能である。
【０１０５】
ワークスペースとして使用されるコンピュータメモリは、現在のシンボル値に対して入力されるＮビット、メモリアドレス参照先に入力されるＫビット、メモリアドレス参照先にて値が存在する位置を示すために出力されるＬビット、およびヒットまたはミスのいずれかが生じたことを示す出力として使用される１ビットを含む擬似キャッシュメモリとして実行される。擬似キャッシュメモリは、圧縮方法１０、１００、２００、３００および４００のワークスペースを実行するために用いられる。ここで、擬似キャッシュメモリとは、コンピュータアーキテクチャで使用されるような、実際のアーキテクチャキャッシュメモリと、キャッシュマッピング圧縮（ＣＭＣ）系を含むすべての圧縮および復元方法において用いられる内部ワークスペースとの間における類似性を強調する意味で用いられる。特に、擬似キャッシュは、コンピュータの中央処理装置（ＣＰＵ）とメインメモリの間において生じる内部データのキャッシュ機構に類似するが、ＣＰＵを入力ストリームに、またメインメモリを出力ストリームに置き換えている。その結果、各キャッシュの異なるデータ局所性特性が引き出される。擬似キャッシュメモリは、圧縮のために当該データ局所性の空間的側面および時間的側面を用いるが、他方アーキテクチャキャッシュは、メモリアクセスの高速化を図る。擬似キャッシュメモリに関して、圧縮および復元方法を実行するために、実行されたワークスペースに必要と思われる特定の入力および出力について記述する。
【０１０６】
図９を参照して、一般に、ＣＭＣ復元方法５００は、本圧縮方法を用いて先に生成された被圧縮データストリームから、もとのソースデータとまったく同じコピーを生成する。方法５００は、圧縮の際に用いられたものと同じキャッシュ履歴手法など、圧縮方法１０、１００、２００、３００および４００と同様の側面を含み、それらは復元方式５００において複製される。
【０１０７】
具体的に図９を参照して、様々な変数、すなわちBlock、Line、SetおよびTokenが初期化される（ステップ５０５）。方法５００の各ループまたは繰り返しにおいて、１つのデータブロックが抽出され、復元または非圧縮ストリームに書き込まれる。当該ブロックは、ミスコードが複号化された場合は被圧縮ストリームから、あるいはヒットラインが復号化された場合はキャッシュから生じたものである。ミスマーカーが検出された場合、ブロックは最初に被圧縮ストリームから読み出され、キャッシュされる。そうでない場合は、復号されたヒットラインをインデックスとして用いて、キャッシュ内の現在のセットから直接ブロックが取り出される。
【０１０８】
さらに図９を参照して、（一時的なヒットコードおよびミスコードを有する）現在のブロック、ライン、セットおよびトークンに対するローカル変数が宣言される（ステップ５０５）。セットは、最初にゼロに初期化される。
【０１０９】
次に、トークンが、ミスマーカーまたはヒットラインのいずれかを保持している場所において、読み出され、かつ復号される（ステップ５３０）。被圧縮ストリームは、ストリームの末尾まで完全に読み出される（ステップ５３２）。ミスマーカーが検出された場合（ステップ５３８）、必然的にミスブロックが後続する。従って、当該ミスが次にソースストリームから読み出され（ステップ５４０）、キャッシュの現在のLRUラインに書き込まれる（ステップ５４２）。あるいは、ブロックは、キャッシュの復号されたヒットラインから直接読み出される（ステップ５５０）。
【０１１０】
次に、ステップ５４２または５５０から取得したブロックが復元または非圧縮のデータストリームに書き込まれる（ステップ５５５）。妥当であれば、現在のセットは更新され（ステップ５６０）、ステップ５３０にて方法５００が再開される。
【０１１１】
別の形態において、HITおよびMISSのコード／値は、トークン、すなわちデータ復元において伸張方法を導くために使用される制御ビットに分類される。当該トークンは、Ｎビットの倍数であり、従って、ソースストリームあるいは被圧縮ストリームから読み出された値は、被圧縮ストリームまたは非圧縮ストリームにコピーされる際にＮビットの倍数のまま配列される。Ｎビットが８ビット長、すなわち文字バイトである場合、ヒットコードおよびミスコードは、ｎバイトのトークンに分類される。この際、ｎはセット｛１、２、３・・・｝の自然数であるため、図１２の被圧縮出力データに示されるように、ソースストリームまたは被圧縮ストリームから読み出された値は、それぞれ被圧縮ストリームまたは非圧縮ストリームにコピーされる際にそのバイト配列が維持される。その結果、被圧縮データストリームにおいて選択的最適化が実行され、リアルタイムに圧縮データの配列が再設定されることにより、個別のビットの入力／出力動作が簡素化される。すなわち、すべてのHITコードおよびMISSコードが、一定サイズのトークンに統合される。各トークンは、ソースデータストリームから読み出された各入力値のビット長であるＮの倍数になる。
【０１１２】
典型例として、Ｎを８ビット長とする。すなわち、それぞれの入力ビットは文字バイトであり、各トークンは、バイトの倍数、すなわちｎが｛１、２、３…｝のセットからの自然数であるｎバイト長である。この最適化は、Ｎビット境界におけるトークン（ヒット／ミスコード）とソースストリームの値とをそろえ、被圧縮および非圧縮データストリームの両方における入力／出力動作を簡素化する効果がある。これにより、本圧縮および復元方法の全体の速度が向上する。
【０１１３】
本圧縮方法は、従来の圧縮方法に見られない特徴と長所を提供することが、ここで明らかになるであろう。本ＣＭＣコーデックは普遍的であり、すべてのソースに対してほぼ同様に、また入力データの特徴に関わらず、入力ストリームから受け取ったデータブロックを処理する。
【０１１４】
本方法のさらなる特徴は、対称であることである。これは、ＣＭＣ圧縮方法と復元方法が、相対的作用、時間的および空間的計算量等に関して、基本的に同じ処理を行うことを意味する。このような対称挙動は、ＣＭＣコーデックにおける時間的／空間的計算量を分析するとさらに明確になる。
【０１１５】
さらに、本ＣＭＣコーデックは、「排他的ストリーム」モードで動作する。すなわち、入力ストリームから受け取ったすべてのシンボルは「一度につき１つ」処理され、さらに重要な点として、当該シンボルの処理後直ちに出力が生成される。これは、従来のほとんどの圧縮方法と異なる点であり、一般的に、従来の圧縮方法は、標準ストリームモードあるいはブロックモードで動作する。標準ストリームモードにおいては、シンボルは一度に１つ処理されるが、その出力はその直後に生成されない。処理可能となるような所定数の入力シンボルが内部で蓄積されるまで、出力は遅らされる。ブロックモードにおいては、圧縮器は、一定数、通常は数キロバイトのシンボルを、ソースデータストリームから読み出して処理し、同等の圧縮ブロックを生成する。
【０１１６】
本願方法によって実行される「排他的ストリーム」モードからは、いくつかの効果が得られる。例えば、デジタル通信において、送信器から受信器への断続的なデータの流れを維持するために、所定の通信処理が必要となりうる。一定間隔で送信器からデータが送信されない場合、受信器は送信器とのデータ同期（シンクロ）を失う可能性がある。当該通信処理が、標準ストリームモードあるいはブロックモードにて動作する圧縮技術に依存する場合、送信器が待機中で、圧縮器が内部で入力シンボルを蓄積し処理する間に、受信器はデータシンクロを失う可能性がある。対照的に、ＣＭＣ技術を伴う本願方法を代わりに用いた場合、本方法は、受け取った入力シンボルそれぞれに対応する出力を即時に生成するため、データシンクロを失う可能性がない。これは、標準ストリームモードまたはブロックモードと対比した排他的ストリームモードの長所を強調するための、デジタル通信という特定領域における一例にすぎない。
【０１１７】
排他的ストリームモードによる同様の効果は、リアルタイムの対応が必要とされるその他の領域でも得られる。例えば、ユーザーが文字を入力し、文字がインターネット（またはその他のチャネル）上に送信され、チャット画面上で当該文字を見ることが予定されている受信者が最終的に文字を受け取る、簡単なチャットアプリケーションを考える。ストリームモードまたはブロックモードにおいては、（送信器側の）圧縮器が文字を放出しない間は、当該文字はまったく表示されない。それは、圧縮器が文字の処理を開始するために数個の文字を最初に受信する必要があるためである。対照的に、ＣＭＣ圧縮器の排他的ストリームモードにおいては、圧縮器が圧縮した文字を直ちに放出し、チャネルを介して送信され、その後伸張器がもとの文字を復元して、チャットアプリケーションに放出し、表示が行われる。
【０１１８】
ＣＭＣコーデックの対称挙動は、独特な実用的効果を有し、それはコーデックが用いる内部リソースの大部分の「共有化」である。これは逆方向において、同一の方法が用いられるからである。したがって、他方が待機中に、共有リソースを用いて１つの動作モードを行うことができる。これにより、動作および設計の両方の費用を最小限に抑えられる。
【０１１９】
フルアソシアティブＣＭＣスキームの一側面は、キャッシュメトリクスを任意の条件に適合させることにより、ミスの可能性を文字通り０％にできることである。すなわち、キャッシュの中には、常にソースストリームから読み出した現在のブロックに一致するブロックが存在する。それ故に、常にヒットが生成されれば、ヒットまたはミスをマークする必要はまったく無くなり、圧縮された出力は、符号化されたヒットラインのみで構成されることになる。LRUスキームと組み合わせた場合、またより短いコードが最も直近に使用されたラインに割り当てられ、最終的に出力ストリームで符号化される場合、その結果生じる方法は、先頭移動法(Move-To-Front)と呼ばれる符号化技術に後退する。
【０１２０】
Move-To-Front方法は、フルアソシアティブＣＭＣコーデックの変形と考えられ、既存のワークスペースインフラを利用して容易に実行可能で、キャッシュ抽出データ型（ＡＤＴ）を通してモデル化することができる。この処理を説明するために、メトリクス＜Ｎ、０、２N＞を用いて、フルアソシアティブ方式のキャッシュを生成すると仮定する。すなわち、LINE（キャッシュラインの数）は、存在しうるすべての個別のデータブロック数である２Nに等しい（例えば、Ｎ＝８の場合、セット内には２５６のラインが存在する）。すべてのキャッシュラインが初期化され、個別のデータブロックを有すると、０〜２Nのラインには、それぞれ０〜２Nの値を有するブロックが存在することになる。そして、ソースストリームからブロックが読み出される毎に、キャッシュ内のいずれかのラインに一致するブロックが存在するため、常にヒットが生成される。
【０１２１】
動作的観点から、ＣＭＣコーデックは、キャッシュメトリクスの境界条件に従って機能性を「変える」。図１０は、本方法における当該側面を示す図である。キャッシュライン数が減少すると、圧縮器は基本的に符号化を行わずにキャッシュのみを実行し、データブロックはダイレクトマップキャッシュにマップされ、ライン番号の符号化は行われない。同様に、セット数が１までに減少すると、本圧縮方法は、フルエンコーダーとなり、すなわち、キャッシュにおいてヒットを生成するよりも最適のコードを生成することが重要となるため、キャッシュ処理の有意性を失う。セットおよびラインの両方の数が増加し、キャッシュと符号化の両方が圧縮処理において重要となり、高圧縮率のために相対的関連性を共有する時が分岐点となる。
【０１２２】
圧縮方法１０、１００、２００、３００、４００および、復元方法５００は、有限状態オートマトンとして実現され、ソフトウェアまたはハードウェア成果物として実行される。当該成果物には、連想スキームまたはインテリジェントメモリスキームを用いて本方法固有の並列性を活用したサイズ／速度の最適化が含まれ、それにより、任意のメモリアドレスから複数の位置を並列的に、すなわち同時に比較できる。換言すれば、有限状態オートマトンとしての本発明の圧縮方法および復元方法の実行は、当該圧縮方法および復元方法の各ステップを示す有限数の状態からなる仮想記憶装置として実現することができる。これは、本発明開示において提示されたすべての圧縮方法および復元方法に適用される。また、メモリアドレスの複数の位置に同時に保存されているすべての値を、特別なハードウェア回路を用いて、現在のシンボル値と並列式に比較する特殊な場合も含まれ、従って、連想データワードを含む連想メモリまたはインテリジェントメモリの挙動が実行されることになり、各データワードは、入力ストリームからの、すでに保存されているシンボル値を示す。このような並列的最適化は、特定のメトリクス＜Ｎ、Ｋ、Line＞（Lineは１より大きい）を有するセットアソシアティブワークスペース構成においてのみ可能となる。
【０１２３】
この処理は、メモリアドレス参照先における各位置の各ビットと、現在のシンボル値の各ビットとを同時に比較する特別なハードウェア回路によって実行され、最大Ｎ個の比較で位置の一致が得られる。ここで、Ｎは現在シンボル値のビットサイズである。連想メモリを使用しない場合、各位置における値を現在シンボル値と１つずつ比較しなければならず、「Line」の「Ｎ」倍の比較回数となる。Line数は各メモリアドレスにおける位置の総数を示す。
【０１２４】
本発明は、特定の実施形態に関して非常に詳細に記述してきたが、本発明の精神および特許請求の範囲を超えることなく本発明の多くの変形例が実現可能であることは、当業者には明らかであろう。
【図面の簡単な説明】
【０１２５】
図１は、本発明にかかるキャッシュマッピング圧縮方法における入力および出力のシーケンスを示し、表示が付されたブロックは、ソースデータストリームから読み出されたシンボル値を示す。
【０１２６】
図２は、本発明にかかるキャッシュマッピング圧縮を示し、ラインと表示されたBlockとＡｄｄｒｅｓｓとは、それぞれ現在のシンボル値およびメモリアドレス参照先を示す。
【０１２７】
図３は、本発明にかかる一般的なキャッシュマッピング圧縮（ＣＭＣ）方法を示すフローチャートである。
【０１２８】
図４は、本発明にかかるダイレクトマップされたＣＭＣ圧縮方法を示すフローチャートであり、変数であるBlock、Line、およびSetは、それぞれ現在のシンボル値、（メモリアドレス内の）位置番号、およびメモリアドレス参照先を示す。
【０１２９】
図５は、本発明にかかるセットアソシアティブ方式のＣＭＣ圧縮方法を示すフローチャートであり、変数であるBlock、Line、およびSetは、それぞれ現在のシンボル値、（メモリアドレス内の）位置番号、およびメモリアドレス参照先を示す。
【０１３０】
図６は、本発明にかかるフルアソシアティブ方式のＣＭＣ圧縮方法を示すフローチャートであり、変数であるBlock、Line、およびSetは、それぞれ現在のシンボル値、（メモリアドレス内の）位置番号、およびメモリアドレス参照先を示す。
【０１３１】
図７は、本発明に開示されたすべての圧縮および復元方法において使用されるワークスペース、または擬似キャッシュメモリを示す図である。
【０１３２】
図８は、本発明にかかる一般なキャッシュマッピング圧縮方法を示すフローチャートであり、変数であるBlock、Line、およびSetは、それぞれ現在のシンボル値、（メモリアドレス内の）位置番号、およびメモリアドレス参照先を示す。
【０１３３】
図９は、本発明にかかる復元方法を示すフローチャートであり、変数であるBlock、Line、およびSetは、それぞれ現在のシンボル値、（メモリアドレス内の）位置番号、およびメモリアドレス参照先を示す。
【０１３４】
図１０は、本発明にかかるダイレクトマップ方式、フルアソシアティブ方式、およびセットアソシアティブ方式の方法に関して、符号化処理およびキャッシング処理の関係を示す比較図である。
【０１３５】
図１１は、本発明に基づいてハフマン符号がどのように割り当てられるかを示すハフマン木を示す。
【０１３６】
図１２は、Ｎが８で、各トークン、すなわちデータ復元で伸張方法を導くために用いられるHITコードおよびMISSコード、または制御ビットを含む場合における、本発明に基づく、出力された被圧縮データの配列を示す。
【図１】
2009531976.tif 000004
【図２】
2009531976.tif 000005
【図３】
2009531976.tif 000006
【図４】
2009531976.tif 000007
【図５】
2009531976.tif 000008
【図６】
2009531976.tif 000009
【図７】
2009531976.tif 000010
【図８】
2009531976.tif 000011
【図９】
2009531976.tif 000012
【図１０】
2009531976.tif 000013
【図１１】
2009531976.tif 000014
【図１２】
2009531976.tif 000015
【国際調査報告】
2009531976.tif 000016