(57)【要約】スライディング・ウインドウ・タイプの圧縮方式が統計型圧縮方式と結合されて、データ記憶装置内のオペレーティング・コードを圧縮するのに使用するために最適化されたデュアル・モード圧縮方式を供給する。圧縮方式のスライディング・ウインドウ部において、ルート項目とコピー項目が生成され、このコピー項目は、長さ値とオフセット値を含む。長さ値と、オフセット値の最上位部は、それから圧縮方式の統計部において別々に圧縮されて、圧縮出力を形成し、この圧縮出力は、ルート項目と結合した時に、二重に圧縮された圧縮出力を形成する。それから相補的な復元方式が使用されて、この二重に圧縮された出力を復元する。
2004507145.tif 000002
【特許請求の範囲】
【請求項１】
データ入力ファイルを圧縮して、圧縮データ出力ファイルを生成する方法であって、
ａ）　スライディング・ウィンドウ圧縮方式を使用して入力ファイルを逐次に検査して、複数のルート項目とコピー項目を生成するステップであって、前記コピー項目の各々は長さ値とオフセット値を有し、前記オフセット値の各々は最上位部と最下位部を有する、前記ステップと、
ｂ）　短縮ルート／コピー・ファイルを生成するステップであって、前記短縮ルート／コピー・ファイルが前記ルート項目と前記コピー項目の前記オフセット値の最下位部を含む、前記ステップと、
ｃ）　前記コピー項目の前記オフセット値の最上位部を圧縮して、圧縮オフセットファイルを生成するステップと、
ｄ）　前記コピー項目の前記長さ値を圧縮して、圧縮長さファイルを生成するステップと、
ｅ）　前記短縮ルート／コピー・ファイル、前記圧縮オフセット・ファイル、前記圧縮長さファイルを結合して、前記圧縮データ出力ファイルを生成するステップとを含む前記方法。
【請求項２】
前記圧縮するステップｃ）が、ハフマン・エンコーディング・アルゴリズムとを使用して実行され、また前記圧縮オフセット・ファイルは、第１ハフマン辞書と、前記第１ハフマン辞書によりエンコードされたハフマン・エンコーデッド・オフセット・ファイルとを含み、
前記圧縮するステップｄ）が、ハフマン・エンコーディング・アルゴリズムとを使用して実行され、また前記圧縮長さ・ファイルは、第２ハフマン辞書と、前記第２ハフマン辞書によりエンコードされたハフマン・エンコーデッド・長さ・ファイルとを含む、請求項１記載の前記方法。
【請求項３】
前記データ入力ファイルが、ディスク・ドライブのために実行可能なオペレーティング・コードを含む、請求項１記載の方法。
【請求項４】
圧縮データ入力ファイルを復元するデータ復元方法であって、前記圧縮データ入力ファイルは、圧縮長さファイルと、圧縮オフセット・ファイルと、短縮ルート／コピー・ファイルとを含み、前記短縮ルート／コピー・ファイルはルート項目および圧縮コピー項目を有し、各圧縮コピー項目は非圧縮コピー項目のオフセット値の最下位部を含み、各非圧縮コピー項目が長さ値とオフセット値を含み、
ａ）　圧縮データ入力ファイルを受信するステップと、
ｂ）　前記圧縮長さファイルを復元して長さ値を得るステップと、
ｃ）　圧縮オフセット・ファイルを復元して、前記オフセット値の最上位部を得るステップと、
ｆ）　前記オフセット値の最下位部、前記オフセット値の最上位部、および前記長さ値から非圧縮コピー項目を形成するステップと、
ｇ）　前記非圧縮コピー項目により識別される一致データ・ストリングを決定するステップと、
ｈ）　前記ルート項目および一致データ・ストリングを含む復元データ出力ファイルを出力するステップとを含む前記方法。
【請求項５】
ｉ）　長さバッファ内に前記長さ値を記憶するステップと、
ｊ）　オフセット・バッファ内に前記オフセット値の第２部分を記憶するステップとを更に含む、請求項４記載の方法。
【請求項６】
前記決定するステップｇ）が、
ｇ）（１）　１つのスライディング・ウィンドウへ前記ルート項目を書込むステップと、
ｇ）（２）　前記スライディング・ウィンドウへ前記一致データ・ストリングを書込むステップとを更に含む、請求項４記載の方法。
【請求項７】
前記圧縮オフセット・ファイルが第１ハフマン辞書および該第１ハフマン辞書によりエンコードされたハフマン・エンコーディッド・オフセット・バッファ・ファイルを含み、また前記圧縮長さファイルが第２ハフマン辞書および該第２ハフマン辞書によりエンコードされたハフマン・エンコーディッド長さバッファ・ファイルを含む、請求項４記載の方法。
【請求項８】
前記圧縮データ入力がディスク・ドライブの圧縮オペレーティング・コードを含む、請求項４記載の方法。
【請求項９】
マイクロプロセッサ、不揮発性メモリ、揮発性メモリ、不揮発性メモリ内に記憶される圧縮オペレーティング・コード・ファイル、および前記圧縮オペレーティング・コード・ファイルを復元するデコンプッサ・モジュールを含み、前記圧縮オペレーティング・コード・ファイルが、第１圧縮ファイル、第２圧縮ファイル、および短縮ルート／コピー・ファイルを含む、データ記憶装置。
【請求項１０】
前記第１圧縮ファイルが、第１ハフマン辞書および該第１ハフマン辞書によりエンコードされたハフマン・エンコーディッド長さデータを含み、前記第２圧縮ファイルが、第２ハフマン辞書および該第２ハフマン辞書によりエンコードされたハフマン・エンコーディッド・オフセット・データを含む、請求項９記載のデータ記憶装置。
【発明の詳細な説明】
【０００１】
（関連出願）
本出願は、米国仮特許出願番号６０／２２５，２５６、出願日２０００年８月１５日の優先権を主張する。
【０００２】
（発明の分野）
本発明は、一般にデータの圧縮および復元（ｄｅｃｏｍｐｒｅｓｓｉｏｎ）に関し、より詳しくはディスク・ドライブに使用されるファームウエアのデータ圧縮および復元に関する。
【０００３】
（発明の背景）
ディスク・ドライブ産業の継続的な動きとして、ハイ・エンド・システムおよびロウ・エンド・システムを含むディスク・ドライブ・システムのサイズとコストを一般に削減する動きが存在してきた。顕著なコストとサイズの削減をなし得る一つの領域は、不揮発性メモリ構成要素の領域であって、これはしばしばディスク・ドライブ・システムのもっとも高価な構成要素である。ＲＯＭまたはフラッシュＲＡＭなどの非揮発性メモリ要素は、ディスク・ドライブのオペレーティング・コードの記憶のためにディスク・ドライブに典型的に組み込まれる。ドライブの始動に際して、迅速にアクセスされなければならないディスク・ドライブ・オペレーティング・コードの諸部分は、ディスク・ドライブ内で典型的にＲＯＭまたはフラッシュＲＡＭから（標準的なＲＡＭなどの）揮発性メモリへ転送される。その時オペレーティング・コードの諸部分は実行のためにディスク・ドライブ・マイクロプロセッサにより迅速にアクセスされる。ディスク・ドライブ・オペレーティング・コードの残りの部分は、不揮発性メモリ内に残されて、そこからアクセスされ実行される。
【０００４】
ディスク・ドライブ内の不揮発性メモリの使用を削減して、これによりディスク・ドライブのコストを削減するのに向けられた数多くの解決法が提案され、実施されてきた。そのような解決法の一つには、ディスク・ドライブのオペレーティング・コードを圧縮して、圧縮されたオペレーティング・コードをディスク・ドライブの不揮発性メモリに記憶することが含まれる。ドライブの起動に際して、小さなブートストラップ・プログラムが使用されて、圧縮オペレーティング・コードを復元して、復元されたオペレーティング・コードをディスク・ドライブの揮発性メモリに記憶する。それからこのディスク・ドライブ・オペレーティング・コードが揮発性メモリからアクセスされて、ディスク・ドライブ・マイクロプロセッサにより、実行される。ディスク・ドライブのファームウエアを圧縮することにより、ファームウエアを記憶するのに使用される不揮発性メモリのサイズに顕著な削減が達成され、不揮発性メモリのコストの対応する削減およびディスク・ドライブ全体としてのコスト削減がこれに伴う。そうした一つの解決法は、２台のプロセッサ復元方法における単一モードのハフマン型圧縮技法を使用し、そこでは一つのプロセッサがオペレーティング・コードの復元を遂行して、第２のプロセッサが使用するためにそれをＲＡＭへロードする。
【０００５】
一般にデータ圧縮は、所与のフォーマットで定義されたデータを、他のフォーマットへ変換し、その結果の圧縮フォーマットは、元のフォーマットよりも少ないデータ・ビット（すなわちデジタル・データを定義する１と０）を含む。従って、このデータがより小さな表現に圧縮される。元のデータが必要な時は、圧縮アルゴリズムに対して相補的なアルゴリズムを使用して、この圧縮データが復元される。
【０００６】
二つの主要なタイプのデータ圧縮／復元方式（以下に単に圧縮方式という）があり、それは損失なし圧縮方式と損失付き圧縮方式である。損失付き圧縮は、復元されるデータが元のデータと正確に同一でない方式を言う。損失付き型圧縮方式においては、データ圧縮および復元の処理の間にデータのある要素が意識的に省略または損失される。損失付き圧縮データは、典型的に画像または音響の圧縮に使用され、そこでは復元データにおける限られた冗長データの損失が、典型的に重要でなく、従って受け入れ可能である。しかしながら損失付き圧縮方式は、オペレーティング・コード・ファイルのような実行可能ファイルの圧縮に適当でなく、ここでは情報中の単一ビットの損失さえファイルを使用不可能にするからである。データの損失を受け入れられないアプリケーションにおいては、損失なし圧縮方式が、必要でないにしても、好ましい。
【０００７】
損失無しデータ圧縮の分野には、二つの一般的なタイプの圧縮技法があり、それは（１）辞書ベース（またはスライディング・ウインドウ）圧縮と（２）統計的圧縮である。辞書ベース圧縮方式は、入力データ・ストリームを検査して、すでに圧縮済みのデータを使用して構築された辞書の中に現れる記号（シンボル）または文字のグループを探す。一致が発見されれば、記号のグループの代わりに、辞書への単一のポインタまたはインデックスが圧縮データ・ストリームへ出力される。この方法で、一般的に起こる信号グループをより小さなインデックス値へ置き換えることができる。多くの辞書ベース諸方式間の主要な相違は、辞書がどのように構築され、維持され、またどのように一致が発見されるかである。
【０００８】
よく知られた辞書ベース方式にＬＺ７７アルゴリズムがある。基本的なＬＺ７７方式は、Ｚｉｖ，Ｊ．およびＬＥＭＰＥＬ，Ａ．による「逐次データ圧縮のための汎用アルゴリズム」、情報理論についてのＩＥＥＥ紀要、第２３巻、１９７７年５月、３３７ページから３４３ページまでに記述されている。このＬＺ７７方式は、単一パス・リテラル／コピー・アルゴリズムを使用して、一つのデータ・シーケンスを圧縮すなわちエンコード（符号化）、および復元すなわちデコード（復号化）する。簡単に言えば、ＬＺ７７方式は、入ってくるデータ・ストリーム内に反復するデータ・パターンを、圧縮出力データ・ストリームの短いコードに置き換えることにより、データ・ストリームを圧縮する。典型的にＬＺ７７方式は、長さが３つの記号またはバイトであるデータの反復するストリングを探索する。非圧縮入力データ・ストリーム内の記号は、非圧縮ストリング（「ルート項目（ｒｏｏｔ ｉｔｅｍｓ）」または「リテラル（ｌｉｔｅｒａｌｓ）」と呼ばれる）として、圧縮データ出力ストリームへ直接に組み込まれたり、または代わりに、圧縮データ出力ストリームへ組み込み済みのルート項目の一致セット（ｍａｔｃｈｉｎｇ ｓｅｔ）に対するポインタ（すなわち「コピー項目（ｃｏｐｙ ｉｔｅｍｓ）」として）に置き換えられる。コピー項目は、置き換えられたリテラルデータと同一またはより少ない数のバイトを必要とするオフセットと長さの情報を含む。オフセットまたはオフセット値は、その以前の発生に関して、エンコードされたストリングのオフセットを規定する。たとえば、エンコードされる同一の発生よりも１０バイト以前に５つの記号の特定リテラル・ストリングが発生すれば、このオフセットは１０である。長さは、コピー項目により置き換えられるストリングの長さを規定する。この例では、長さフィールドは５であって、一致データ・シーケンスの長さを記号またはバイトで規定する。圧縮は、可能なできるだけ多くの非圧縮データ・シーケンスをコピー項目として表現することにより実現される。ルート項目は、典型的に３つまたはそれ以上の記号の一致が発見されない場合にのみ、圧縮データ・シーケンスへ組み込まれる。
【０００９】
ハフマン方式などの統計的圧縮方式は、ストリームを圧縮するのに先立って、データ・ストリーム全体を読んで評価することにより、データ・ストリームの統計的モデルを構築する。たとえばあるデータ・ストリームの初期評価の間に、ハフマン・エンコーディングは、各記号の発生の数に基づく統計的「ツリー」（ハフマン・ツリー）すなわちランキングを生成する。このハフマン・ツリーは、データ・ストリーム内の各記号を、発生頻度により識別する。ツリーが生成された後は、ストリーム中に反復される記号は、その特定記号のハフマン・ツリー内の値に対応する可変長コードに置き換えられて、データの圧縮ストリームを生成する。たとえば、もっとも頻度の大きい記号は、ツリー内の最小コードに割り当てられ、こうして最大頻度で発生する記号が、可能な最小コードで置き換えられる。
【００１０】
上記のＬＺ７７およびハフマン・エンコーディング方式のいずれかのみを使用する代わりに、これらの方式を組み合わせれば、単独の圧縮方式を使用して達成できるよりも大きなデータ・ストリーム圧縮を達成できることが発見された。このタイプの「デュアル・モード」圧縮方式の典型的な例には、事前にＬＺ７７方式により出力されたデータ・ストリームを、ハフマン・エンコーディングを使用して更に圧縮して、ハフマン／ＬＺ７７圧縮データ・ストリームを生成することが含まれる。デュアル・モード圧縮方式の使用は、その高い圧縮度、単純性、速い圧縮速度のために、典型的なデータ圧縮アプリケーションにおいて、ますます一般に用いられるようになった。
【００１１】
典型的なデュアル・モード圧縮方式またはアルゴリズムは、一定のアプリケーションにおいてはシングル・モード圧縮方式よりも一層効果的であるが、この典型的なデュアルモード圧縮方式にはいくつかの欠点があって、典型的なディスク・ドライブにおける使用のためにその効果を厳しく制限されることがあり得る。典型的なデュアル・モード圧縮方式をディスク・ドライブに使用するときに起こりうる一つの欠点は、復元速度に関係する。典型的なデュアル・モード圧縮アルゴリズムは、パーソナル・コンピュータやワークステーションに見られるようなプロセッサ上で実行するように設計されており、実行プログラムのために相当なスタック空間を有する。言い換えれば、デュアル・モード圧縮アルゴリズムは、典型的にかなりのスタック空間を有して、割り込みと文脈切り替えの待ち時間（レイテンシー）が少なくて済むプロセッサで実行されるように最適化されている。これは、典型的なハフマンツリーを処理またはナビゲートするための再帰的（ｒｅｃｕｒｓｉｖｅ）アルゴリズムを使用するハフマン・モードを含むデュアル・モード圧縮方式において特に真実である。
【００１２】
パーソナル・コンピュータまたはワークステーションに使用されるプロセッサと反対に、典型的なディスク・ドライブは、非常に限られたスタック空間を有する小さなプロセッサを使用する。たとえば、ディスク・ドライブは、しばしば一次プロセッサとして、デジタル信号プロセッサ（ＤＳＰ）を使用する。ＤＳＰは、典型的に高い計算速度を有するが、しばしば非常に限られたスタック・サポートと、非常に長い割り込みと文脈切り替えの待ち時間を有する。この理由により、通常ディスク・ドライブに使用されるプロセッサは、かなりのスタック空間と少ない割り込みおよび文脈切り替えの待ち時間に依存する典型的なデュアル・モード圧縮アルゴリズムに一般に適合しない。特に典型的にディスク・ドライブに使用されるプロセッサは、再帰的アルゴリズムを使用する典型的なハフマン方式を含むデュアル・モード圧縮アルゴリズムに適合しない。
【００１３】
ディスク・ドライブにおいて、典型的なデュアル・モード圧縮方式を使用するについてのさらに起こりうるもう一つの問題は、ディスク・ドライブ中に使用されるオペレーティング・コードの小さなサイズに関係する。デュアル・モード圧縮方式は、一般に画像、データ・ベース、オーディオ・ファイルのような大きなデータ・ファイルを圧縮するのに最適化されている。それ自体として、これらの圧縮方式は典型的に、デュアル圧縮方式が必要とする辞書またはハフマン・ツリーのような「オーバーヘッド」のために、小さなデータ・ブロックをより小さなデータ・ブロックへ圧縮するためには、効果的でない。たとえば、典型的なハフマン・ツリーは、大きなデータ・ファイルの圧縮と圧縮ステップの速度の両方を最適化するために構築される。これは、ハフマン・ツリーをかなり大きくすることにより、典型的に達成される。画像ファイルのような比較的大きなデータ・ファイルについては、このオーバー・ヘッドのレベルは、最適圧縮速度により充分に補償され、全体的な圧縮が達成される。しかし、ディスク・ドライブのオペレーティング・コードのような小さなデータ・ファイルのためには、典型的なハフマン・ツリーのサイズによるオーバー・ヘッドは受け入れられないものである。実際、データの小ブロックについて、ハフマン・ツリーのサイズに追加されたときの圧縮データのサイズは、元のデータ・ファイルよりも大きくなって、こうして小さなデータ・ファイルを圧縮する利益を無効にすることになる。
【００１４】
本発明が開発されたのは、これら考察およびその他の事柄についてである。
【００１５】
（発明の要約）
データ記憶装置のオペレーティング・コードを圧縮するのに使用するために、デュアル・モード圧縮／復元方式が開発された。敏速な復元を実行できるような形式で、デュアル・モード圧縮方式を介して圧縮データが生成され、特にデータ記憶装置など処理リソースが限られているアプリケーションに特に適合する。一つの実施例において修正ＬＺ７７タイプの圧縮／復元方式が、独自のハフマン・タイプ圧縮／復元方式と組み合わせられて、ディスク・ドライブのオペレーティング・コードを圧縮し、復元するのに使用するために最適化されている。
【００１６】
もう一つの実施例は、データ入力ファイルを圧縮して圧縮データ出力ファイルを生成する方法に関する。この方法は、スライディング・ウインドウ圧縮方式を使用してデータ入力ファイルを逐次的に検査して、ルート項目とコピー項目を生成する方法を含む。各コピー項目は、長さ値とオフセット値を有する。オフセット値は、最上位部と最下位部に細分されるが、これらはこの方法により、異なった仕方で処理される。この方法は、ルート項目およびコピー項目のオフセット値の最下位部を含む短縮ルート／コピー・ファイルを生成する。この方法は、コピー項目のオフセット値の最上位部を圧縮して、圧縮オフセット・ファイルを生成する。この方法はまたコピー項目の長さ値を圧縮して圧縮長さファイルを生成する。この方法の一部分として短縮ルート／コピー・ファイル、圧縮オフセット・ファイルおよび圧縮長さファイルが組み合わせられて、圧縮データ出力ファイルを生成する。
【００１７】
上記の方法を補足するものとして、もう一つの実施例は、圧縮長さファイル、圧縮オフセットファイルおよび短縮ルート／コピー・ファイルを含む圧縮データ入力ファイルを復元する方法に関する。この方法において、短縮ルート／コピー・ファイルがルート項目と圧縮コピー項目を有する。各圧縮コピー項目は、非圧縮コピー項目のオフセット値の最下位部を含む。各非圧縮コピー項目は、長さ値とオフセット値を含む。
【００１８】
復元方法の最初のステップにおいて、圧縮データ入力ファイルが受信中であり、圧縮長さファイルが復元されて、長さ値を獲得する。同様に圧縮オフセット・ファイルが復元されて、オフセット値の最上位部を獲得する。それから短縮ルート／コピー・ファイル、オフセット値の最上位部および長さ値から得られたオフセット値の最下位部から非圧縮コピー項目が形成される。この方法は、非圧縮コピー項目により識別される一致データ・ストリングを決定して、ルート項目と一致データ・ストリングを含む復元データ出力ファイルを出力する。
【００１９】
もう一つの実施例は、内蔵する不揮発性メモリに記憶された圧縮オペレーティング・コード・ファイルを有するデータ記憶装置、および圧縮オペレーティング・コード・ファイルを復元するように動作可能な復元モジュールに関する。この実施例において、圧縮オペレーティング・コード・ファイルは、第１圧縮ファイル、第２圧縮ファイルおよび短縮ルート／コピー・ファイルを含む。
【００２０】
これらおよび他の諸特徴は本発明を象徴する諸利点と共に、以下の詳細な説明を読み、添付図面を参照することにより明らかになる。
【００２１】
（詳細な説明）
一般にこの開示は、デジタル・データを圧縮し展開する（ｅｘｐａｎｄｉｎｇ）方法とシステムを説明する。一層詳しくは、この開示は独自なデュアル・モードの圧縮方式と復元方式を使用するデータ圧縮モジュールとデータ復元モジュールを説明する。更に詳しく言えばこの開示は、データ記憶装置のメモリ内の記憶域のためにオペレーティング／ファームウエア・コード（オペレーティング・コード）を圧縮するデータ圧縮器モジュール、および前記データ記憶装置のメモリから圧縮されたコードを復元するためにデータ記憶装置内で動作できるデータ復元器モジュールを説明する。
【００２２】
図１は、本発明の実施例による圧縮器モジュール１００の簡略化された表現を図示する。図１に示すように、圧縮器モジュール１００は非圧縮データ１０２の入来ストリームを受信して、圧縮データ１０４のストリームを出力する。詳細は後述するが、圧縮器モジュール１００が独自なデュアル・モード圧縮方式を使用して、非圧縮データ・ストリーム１０２をコンパクト化して、圧縮データ・ストリーム１０４にする。
【００２３】
図２は、本発明の実施例による復元器モジュール２００の簡略化表現を図示する。図２に示すように本発明の一つの実施例において、復元器モジュール２００が圧縮データ２０２のストリームを受信して、上記の独自なデュアル・モード圧縮方式に対して相補的な独自なデュアル・モード復元方式を使用して、圧縮データ・ストリーム２０２を展開して、非圧縮データ２０４の出力ストリームにする。
【００２４】
図３に示すように一つの実施例において、圧縮器モジュール１００が汎用コンピュータ３００内で実施されて、ディスク・ドライブ３２０のようなデータ記憶装置のためにオペレーティング・コードを圧縮する。それからディスク・ドライブ３２０内に復元器モジュール２００（図２）が使用されて、たとえばディスク・ドライブ３２０の起動に際して、ディスク・ドライブ・オペレーティング・コードを展開する。
【００２５】
この実施例および本書に説明する他の実施例において、圧縮器モジュール１００の論理演算は、コンピュータで実施する一連のステップまたはマイクロ・プロセッサ上で実施するプログラム・モジュールとして実施され、たとえばパーソナル・コンピュータまたはワーク・ステーション内のプロセッサで実施できるが、これに限定されない。この実施例において、復元器２００の論理演算は、プロセッサ上で実行する一連のコンピュータ実施ステップまたはプログラム・モジュールとして実施され、このプロセッサは、たとえばディスク・ドライブ３２０内の専用プロセッサまたはデジタル信号プロセッサ（ＤＳＰ）であるが、これに限定されない。本発明の圧縮器モジュールおよび復元器モジュールを計算システム内の相互接続機械論理回路または回路モジュールとしても実施できることが当業者に理解される。この実施は、圧縮機モジュール１００および／または復元器モジュール２００を実施する計算システムの性能要件による選択事項である。本書に説明する演算、構造装置、動作および／またはモジュールは、本書に添付の特許請求の範囲に述べられた本発明の精神と範囲から逸脱することなしに、ソフトウエア、ファームウエア、特殊目的のデジタル論理回路、および／またはそれらの任意の組み合わせにより実施できる。その上本書に説明する種々のソフトウエア・ルーチンまたはソフトウエア・モジュールは、この技術に公知のいずれかのの手段により実施できる。たとえば「Ｃ」、「Ｃ＋＋」、Ｐａｓｃａｌ、ＦＯＲＴＲＡＮ、アセンブリ言語、Ｊａｖａ（登録商標）など任意の数のコンピュータ・プログラミング言語を使用できる。さらに手順的技法、オブジェクト指向技法または人口知能技法のような種々なプログラミング解決法（アプローチ）を使用できる。
【００２６】
コンピュータ読取可能媒体は、コンピュータまたはプロセッサによりアクセス可能なあらゆる利用可能な媒体であり得る。たとえば、コンピュータ読み取り可能媒体は、コンピュータ記憶媒体および／または通信媒体を含み得る。
【００２７】
コンピュータ記憶媒体は、コンピュータ読み取り可能な命令、データ構造、プログラム・モジュールまたは他のデータなどの情報を記憶するためのあらゆる方法または技法で実施される、揮発性または不揮発性の、交換可能なまたは交換不可能な媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＰＲＯＭ、フラッシュ・メモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、ディジタル万能ディスク（ＤＶＤ）または他の光学記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置または他の磁気記憶装置、または希望する情報を記憶するのに使用できるあらゆる他の媒体およびオペレーティング・コードを実行するコンピュータまたはプロセッサによりアクセスできるあらゆる他の媒体を含むが、これらに限定されない。
【００２８】
通信媒体は、典型的に搬送波または他の伝送機構のような変調されたデータ信号におけるコンピュータ読取可能な命令、データ構造、プログラム・モジュールまたは他のデータを実施し、いずれかの情報配信媒体を含む。「変調されたデータ信号」という用語は、信号内のエンコード情報に関して、一つまたはそれ以上の特性セットを有するかまたはそうした仕方で変更される信号を意味する。たとえば通信媒体は、有線ネットワークまたは直接配線接続、および音声、ＲＦ、赤外線などの無線媒体、および他の無線媒体を含むが、これに限定されない。上記のいずれかの組み合わせもまたコンピュータ読み取り可能媒体の範囲に含まれる。コンピュータ読み取り可能媒体は、またコンピュータ・プログラム製品とも呼ばれる。
【００２９】
図３に示すように、圧縮器モジュール１００は、汎用コンピュータ３００により実行されるソフトウエア・モジュールとして実施される。詳細は後述するが、圧縮器１００は、ディスク・ドライブ３２０内のメモリへ配信または記憶するために、ディスク・ドライブ・オペレーティング・コード・データなどの非圧縮すなわち生のデータのストリームを圧縮するために使用される。図３に示すシステムにおいて、ディスク・ドライブ３２０のオペレーティング・コードがコンピュータ３００へインプットされ、コンピュータ３００は、圧縮モジュール１００を使用して、ディスク・ドライブへの転送のためのオペレーティング・コードを圧縮する。図３に示す汎用コンピュータ３００のいくつかの要素には、モニタ３０２、キーボード３０４、入出力（Ｉ／Ｏ）部３０８を有するプロセッサ３０６、中央処理装置（ＣＰＵ）３１０、メモリ部３１２、ディスク・ドライブ、ＣＤ−ＲＯＭなどの不揮発性記憶装置３１４が含まれる。汎用コンピュータ３００の多くの他の内部構成要素が示されていないが、当技術の通常の技能を有する人は、そうした構成要素とそれらの相互接続が公知であることを理解するであろう。
【００３０】
この実施例において、復元器モジュール２００が、ディスク・ドライブ３２０内のプロセッサまたはＤＳＰに実装されていて、圧縮オペレーティング・コードを復元するが、詳細は後述する。復元器モジュール２００をその中に使用または実装した例示的なディスク・ドライブ３２０が図４に示される。ディスク・ドライブ３２０は基礎４０２を含み、それへディスク・ドライブ３２０の種々な構成部品が装着される。一部切り欠きで示す上部カバー４０４が基礎４０２と共同して、通常の仕方でディスク・ドライブ３２０の内部密封環境を形成する。構成要素には高速で一つまたはそれ以上のディスク４０８を一定の高速度で回転させるスピンドル・モータが含まれる。アクチュエータ・アセンブリ４１０を使用することによりディスク４０８上のトラックから情報が読み書きされるが、アクチュエータ・アセンブリ４１０は、シーク動作中にディスク４０８に隣接して位置するベアリング・シャフト・アセンブリ４１２の周りを回転する。アクチュエータ・アセンブリ４１０は、ディスク４０８へ向かって伸びる複数のアクチュエータ・アーム４１４を含み、各アクチュエータ・アーム４１４から伸びる一つまたはそれ以上のフレクシャ４１６を有する。各フレクシャ４１６の末端にヘッド４１８が装着され、ヘッド４１８は空気ベアリング・スライダを有し、これによりヘッド４１８が関連ディスク４０８の対応表面上に近接して飛行することができる。
【００３１】
フレックス・アセンブリ４３０が、アクチュエータ・アセンブリ４１０の必須電気接続パスを供給すると共に、動作中にアクチュエータ・アセンブリ４１０のピボット動作を可能にする。フレックス・アセンブリはまた印刷回路板４３２を含み、これにヘッド配線（図示なし）が接続されている。ヘッド配線は、アクチュエータ・アーム４１４およびフレクシャ４１６に沿った経路を取り、ヘッド４１８へ至る。プリント回路版４３２は、典型的に書き込み動作の間にヘッド４１８へ加えられる書き込み電流を制御する回路と、読み取り動作中にヘッド４１８により発生される読み取り信号を増幅するための前置増幅器を含む。フレックス・アセンブリは、フレックス・ブラケット４３４で終端をなして、基礎４０２を通じてディスク・ドライブ３２０の底側へ装着されたディスク・ドライブ印刷回路板（図示無し）へ連絡する。
【００３２】
さて図５を参照すると、図４のディスク・ドライブ３２０の機能的なブロック図が示され、ディスク・ドライブ印刷回路板に典型的に常駐して、ディスク・ドライブ３２０の動作を制御するのに使用される主な機能構成部品またはモジュールを一般的に示す。図５に示すように、ディスク・ドライブ３２０との連絡は、インターフェイス・アプリケーション特定集積回路（インターフェイス）５０２を介して、供給される。インターフェイス５０２は、典型的に付属のバッファ５１０を含み、このバッファ５１０が、ディスク・ドライブ３２０とホスト・コンピュータ５００など、データの記憶のためにディスク・ドライブを使用するシステムとの間の高速データ転送を容易にする。通常のオペレーションにおいて、ディスク・ドライブ３２０へ書き込まれるデータは、ホスト・コンピュータ５００からインターフェイス５０２へ送られ、それから読み書きチャネル５１２へ送られ、読み書きチャネル５１２がデータをエンコードし、直列にして、ヘッド４１８へ必須書き込み電流信号を供給する。ディスク・ドライブ３２０によりあらかじめ記憶されているデータを検索するために、ヘッド４１８により読み取り信号が発生されて読み書きチャネル５１２へ供給され、読み書きチャネル５１２がデコーディングとエラー検出と訂正のオペレーションを遂行して、ホスト・コンピュータ５００への次の転送のために、インターフェイス５０２へ検索されたデータを出力する。ディスク・ドライブ３２０のそうしたオペレーションは当技術においてよく知られており、たとえば米国特許公報第５，２７６，６６２号、１９９４年１月４日発行、発明者Ｓｈａｖｅｒ他に議論されている。
【００３３】
再び図５を参照すると、（ＤＳＰなどの）プロセッサ５１６がインターフェイス５０２へ動作可能に接続されている。マイクロ・プロセッサ５１６は、ディスク・ドライブ３２０へ最上位の通信と制御を供給する。その上プロセッサ５１６は、スピンドル・コントロール５２６とサーボ・コントロール５２８へ制御信号を供給する。非揮発性メモリ（ＮＶＭ）５２４と揮発性メモリ（ＶＭ）５３０の二つのタイプのメモリが、プロセッサ５１６へ動作可能に接続されている。ＮＶＭ５２４は、リード・オンリー・メモリ（ＲＯＭ）またはフラッシュＲＯＭを含むが、これに限定されない。ＶＭ５３０は、ダイナミックＲＡＭまたはスタティックＲＡＭなどのランダム・アクセス・メモリ（ＲＡＭ）を含むが、これらに限定されない。
【００３４】
一つの実施例においてディスク・ドライブ３２０の動作は、「ブート・コード（ｂｏｏｔ ｃｏｄｅ）」と呼ばれるオペレーティング・コードにより制御されるが、このブート・コードは、圧縮形式で最初からＮＶＭ５２４内に記憶されている。一つの実施例において、ディスク・ドライブ３２０の起動の一部分として読み込まれ実行されるこのブート・コードは、復元器モジュール２００の動作を制御する命令を含む。ディスク・ドライブ３２０の起動は、ブート・ストラップ手順と呼ばれる。
【００３５】
ブート・ストラップ手順は、一般に３つの顕著なステップとして説明できる。第１にプロセッサ、メモリ、および拡張メモリ・コントローラ、チップ・コントローラ、バス・コントローラ、タイマなど他のいずれかの必要なハード・ウエア周辺装置を初期化する命令を記憶するメモリ内の既知の位置から、プロセッサ５１６が実行を開始する。第２にオペレーティング・コードを書き込むのに使用される特定のプログラミング言語により定義される実行時初期化を、それからブート・コードが実行する。これは、プログラム・スタック、ヒープ（ｈｅａｐｓ）の初期化、スタティック初期化変数の初期化を含み、いずれかの他のリンケージまたは言語またはオペレーティング・カーネルに依存するオペレーションは、オペレーティング・コードが実施可能になる以前に必要である。最後のステップは、媒体アクセスと外部アクセス機構との通信方法を初期化するノーマル・オペレーティング・コードにより特徴づけられ、このノーマル・オペレーティング・コードは、このドライブが（たとえばコンピュータの）一部分である外部システムにより要求される活動を、このディスク・ドライブが遂行できるようにする。
【００３６】
本書に議論する諸実施例は、ブート・ストラップ手順の第２ステップの後に圧縮オペレーティング・コードの復元を遂行する。復元モジュール２００により使用されるスタティック・メモリを、ノーマル・オペレーティング・コードによりいくらか再生（ｒｅｃｌａｉｍｅｄ）しなければならないので、この追加のステップは、ノーマル・オペレーティング・コードから見た時に、先行のステップの拡張である。言い換えれば、復元器モジュール２００により使用されるオペレーティング・バッファと変数は、単にこれらのデータを上書きするオペレーティング・コードの方法により、オペレーティング・コードが「再生」する。実際は、ノーマル・オペレーティング・コードが実行を開始すると、（不揮発性メモリ内の元の復元ブート・コードおよび圧縮オペレーティング・コード以外は）復元モジュール２００の全ての痕跡が消滅する。
【００３７】
本発明の一つの実施例において、オペレーティング・コードは、圧縮器モジュール１００を使用して圧縮される。上記のように圧縮器モジュール１００は、第１モードと第２モードを含む独自なデュアル・モード圧縮方式を使用する。一つの実施例において、第１モードは修正ＬＺ７７タイプ圧縮方式（ＬＺ７７モード）を含み、これは生の入力データ１０２上で動作して、ルート項目（ｒｏｏｔ ｉｔｅｍｓ）とコピー項目（ｃｏｐｙ ｉｔｅｍｓ）を含む予備圧縮ファイルを発生する。後述するが、この予備圧縮ファイルは、デュアル・モード圧縮方式の第２モード（ハフマン・モード）において更に圧縮される。本書においてはＬＺ７７モードに対して第１モードが説明されるが、ルート項目とコピー項目を含む予備圧縮ファイルを出力するあらゆる圧縮方式が使用できることを理解すべきである。
【００３８】
図６は、本発明の１つの実施例により、入力データをエンコードして圧縮データを発生させる高レベルの例示的な処理を示す一般的なフロー図である。図６に示すように、圧縮器モジュール１００がエンコードされる入力データ・ストリーム６１２を受信する。入力データ・ストリーム６１２は、コンピュータ読み取り可能データの非圧縮ストリームである。圧縮器モジュール１００は、本書に説明する独自なデュアル・モード圧縮方式を使用して、入力データ・ストリーム６１２をエンコードして、圧縮ファイル６２０を出力する。圧縮ファイル６２０は、入力データ・ストリーム６１２の圧縮形式を表現し、重要な事に、入力データ・ストリーム６１２よりもかなり小さい。圧縮ファイル６２０が次に復元モジュール２００により使用されて、入力ストリーム６１２内にコンピュータ読み取り可能データを回復する。
【００３９】
圧縮ファイル６２０は、３つのデータ・セットからなる：すなわち、ハフマンエンコーディッド・オフセット・ファイル６１４、短縮（ａｂｒｉｄｇｅｄ）ルート／コピー・ファイル６１６、およびハフマンエンコーディッド長さファイル６１８である。短縮ルート／コピー・ファイル６１６はルート項目と部分コピー項目を含み、これらは図７と図８に関して後述する。ハフマン・エンコーディッド長さファイル６１８はエンコーディッド長さデータ６１７のエンコーディッド長さ値を含み、これは短縮ルート／コピー・ファイル６１６内のルート項目とコピー項目に関連する。ハフマン・エンコーディッド長さファイル６１８はまたハフマン長さ辞書６１９を含み、これはエンコーディッド長さデータ６１７内のエンコーディッド長さ値をデコードするハフマン・デコーディング・データを含む。第３のデータセットはハフマン・エンコーディッド・オフセット・ファイル６１４であって、これは短縮ルート／コピー・ファイル６１６に関連する。ハフマン・エンコーディッド・オフセット・ファイル６１４は、エンコーディッド・オフセット・データ６１３およびこのエンコーディッド・オフセット・データ６１３をデコードするのに使用されるハフマン・オフセット辞書６１５を含む。これら３つのファイル６１４、６１６、６１８が圧縮ファイル６２０内で一連の別個のものとして図示されているが、圧縮ファイル６２０をメモリ内のどこにも記憶できることを理解すべきである。
【００４０】
上記のように圧縮器モジュール１００の実施例は、デュアル・モード方式を使用して、圧縮ファイル６２０を生成する。その第１のモードはＬＺ７７モードであって、これは図７に関して説明したように、予備圧縮ファイルを生成する。予備圧縮ファイルは、圧縮の第２のモードすなわちハフマン・エンコーディング・モードへの入力である。ハフマン・エンコーディング・モードの実施例を、図８に関連して説明する。
【００４１】
ＬＺ７７モード７００がどのように入力データ・ストリームを圧縮して、予備圧縮ファイルにするかの例示的な図示が図７に供給される。この予備圧縮ファイルは本書において予備ルート／コピー・ファイルと呼ばれるが、その理由は、それがルート項目とコピー項目を含み、これらが入力データ・ストリームの圧縮版であるからである。入力データ・ストリームは、コンピュータ読み取り可能データの非圧縮ストリームである。コンピュータ読み取り可能なデータは、図３のディスク・ドライブ３２０のメモリに記憶されるコードまたはファームウエアのような、マイクロプロセッサで実行可能なコードまたはファームウエアを含むが、これに限定されない。図７の目的は、ＬＺ７７モード７００内でどのように入力データが圧縮されるかを読者にわかりやすくすることであり、いかなる方法でもこの発明の範囲を限定するのが目的ではない。ＬＺ７７の多くの変化形が当技術分野に知られている。ＬＺ７７アルゴリズムの変化形には、ＬＺ７８、ＬＺＨ、ＬＺＢ、ＬＺＳＳおよびＬＺＦＧが含まれるが、これらに限定されない。しかし、もっとも広く知られている圧縮方式は、ＬＺ７７タイプの変化形である。広く知られたＬＺ７７タイプの圧縮方式の例には、ＡＲＪ、ＬＨＡ、ＺＩＰ、ＺＯＯがある。ＬＺ７７モード７００は、本書に説明する実施例によるルート項目とコピー項目を発生するあらゆる圧縮方式を使用できることを理解すべきである。
【００４２】
図７は、複数の記号からなる入力データ・ストリーム７０４を図示し、これらはクロック・サイクル（ＣＬＫ）０　７１２およびＣＬＫ３　７１４のような時間における多数のインスタンス若しくは例において処理される。ある記号は、一般にいずれかのコンピュータ読み取り可能情報を表現するのに使用できるいずれかの短縮表現を意味する。記号（シンボル）の例には、文字と数字が含まれる。ある記号は、典型的に一つまたはそれ以上のコンピュータ読み取り可能なビットの形式で、コンピュータ・メモリ内でバイナリ・エンコードされる。クロック・サイクルは、一般にコンピュータ演算の発生をトリガする周期的な時間基準のことを言う。たとえば各クロック・サイクル上で、入力データ・ストリーム７０４内の一つまたはそれ以上の記号がメモリから読み取られてエンコードされると共に、圧縮データがメモリへ書き込まれる。
【００４３】
どのように入力データ・ストリーム７０４がエンコードされるかをわかりやすくするために、スライディング・ウインドウ７０５が、入力データ・ストリーム７０４の上に、重ねあわされる。スライディング・ウインドウ７０５は、リーディング・エッジ（前縁）７１６とトレイリング・エッジ（後縁）を有し、その中に記号が含まれるとみなされる。リーディング・エッジ７１６とトレイリング・エッジ７１７は、そこに含まれる記号を記憶するいずれかのメモリ（マイクロ・プロセッサ内のレジスタを含む）内の位置を論理的に表現する。スライディング・ウインドウは、いずれかのメモリ参照方式を使用することにより、ソフトウエア内に定義されて、リーディング・エッジ７１６およびトレイリング・エッジ７１７を入力データ・ストリーム７０４内の記号と結合することが想定される。任意の数の記号がスライディング・ウインドウ７０５内に含まれる。
【００４４】
例示のためのみであるが、図７のスライディング・ウインドウ７０５は、９個の記号を含む。実際の実施例においては、スライディング・ウインドウ７０５は、あらゆるサイズ（たとえば１０２４）であり得る。スライディング・ウインドウ７０５のサイズは、典型的に実施例に使用されるマイクロ・プロセッサまたはデジタル信号プロセッサ内のレジスタのサイズによって異なる。スライディング・ウインドウ７０５は、またスライディング・ウインドウ７０５を二つの部分またはバッファへ分割するパーティション７２０を含む。リーディング・エッジ７１６と同様に、パーティション７２０は入力データ・ストリーム７０４の記号を記憶するメモリ内のメモリ位置への基準とみなされる。スライディング・ウインドウ７０５の二つのバッファは、ルック・アヘッド・バッファ７１８およびサーチ・バッファ７２１と呼ばれる。サーチ・バッファ７２１は、最近エンコードされた記号を含む。ルック・アヘッド・バッファ７１８は、なおエンコードされるべき信号を含む。
【００４５】
たとえば一つの実施例において、ルック・アヘッド・バッファは１２８バイトに制限される。このサイズは、長さフィールドまたはエクステント・フィールド内のビット数の関数である。スライディング・ウインドウ内に位置するストリングの長さを表現するのに必要なビット数が多くなればなるほど、このエクステントが表現のためにビットの全てを必要とはしない時に、浪費されるビットの数が多くなる。ルック・アヘッド・バッファのサイズは、アプリケーション、環境、圧縮すべき特定データなどに適するように任意に選択され、または経験的に導き出される。
【００４６】
各クロックサイクルと共にスライディング・ウインドウ７０５が、入力データストリーム７０４のもう一つの記号情報の上にリーディング・エッジ７１６の方向に進行またはスライドする。たとえば、ＣＬＫ０　７１２において、スライディング・ウインドウ７０５は、入力データ・ストリーム７０４の記号「Ａ」に重ね合わされる。クロック１　７１３でスライディング・ウインドウ７０５は、記号「Ａ」および記号「Ａ」に隣接する記号、たとえば記号「Ｂ」に重ねあわされる。スライディング・ウインドウ７０５が入力データ・ストリーム７０４の諸記号の上を進行するにつれて、諸記号がルック・アヘッド・バッファ７１８に入る。ルック・アヘッド・バッファ７１８内の諸記号がエンコードされる。実際の実施例において、スライディング・ウインドウ７０５内の諸記号はメモリ内にあり、ルック・アヘッド・バッファ７１８内に含まれる記号シーケンスがエンコードされる。記号シーケンスは、一つまたはそれ以上の論理的に隣接する記号である。記号の最大数は、いずれかの数にセットでき、スライディング・ウインドウ７０５のサイズによって異なる。
【００４７】
圧縮器モジュール１００は、ルック・アヘッド・バッファ７１８内の信号シーケンスを読み取って、サーチ・バッファ７２１内のそれらの信号シーケンスをサーチする。サーチ・バッファ７２１内にルック・アヘッド・バッファ７１８の信号シーケンスが何もなければ、圧縮器モジュール１００がルート項目７０８のようにルート項目として、記号シーケンスを出力する。ルート項目７０８は、一般にルック・アヘッド・バッファ７１８からの記号シーケンスであって、これに対してサーチ・バッファ７２１内に二つまたはそれ以上の信号の一致が存在しない。ルック・アヘッド・バッファ７１８の信号シーケンスがサーチ・バッファ７２１内に発見されれば、コピー項目７１０などのコピー項目を圧縮器モジュールが発生する。コピー項目７１０のようなコピー項目は、一つのオフセット値７３０と長さ値７３２を含む。図示においてコピー項目７１０とルート項目７１８を区別しやすくするために、コピー項目７１０を括弧で囲んで示す。
【００４８】
実際の実施例において、ルート項目７０８とコピー項目７１０はバイナリ・エンコードされて、識別アイデンティファイアーと共にメモリ内の予備ルート／ファイル・コピーに記憶される。各ルート項目７０８は、その項目をルート項目７０８として単独に識別するコンピュータ読み取り可能な関連のアイデンティファイアーと共に、予備ルート／コピー・ファイル内に記憶される。同様に各コピー項目７１０は、その項目をコピー項目７１０として単独に識別するコンピュータ読み取り可能な関連のアイデンティファイアーと共に、予備ルート／コピー・ファイル内に記憶される。こうしてこの関連のアイデンティファイアーが、ルート項目７０８をコピー項目７１０から識別する。この関連アイデンティファイアーは、いずれかの単独なバイナリ・エンコーディッド・アイデンティファイアーである。たとえばこの関連アイデンティファイアーは、単一のビットであって、ビット値の１はその項目がルート項目７０８であることを示し、またビット値の０はその項目がコピー項目７１０であることを示す。
【００４９】
ＣＬＫ０　７１２において、サーチ・バッファ７２１内に記号が何も収納されていない。こうして、圧縮器モジュールは、サーチ・バッファ７２１内にルック・アヘッド・バッファの記号「Ａ」を配置しない。こうしてＣＬＫ０　７１２において、ルート項目Ａ　７３４がメモリ位置へ出力され、好ましくは、圧縮データを保持するためのファイルの中にある。クロック１　７１３において、ルック・アヘッド・バッファ７１８の記号シーケンス「Ｂ」がサーチ・バッファ７２１内に発見されない。従って、記号「Ｂ」が出力されて先行のルート項目Ａ　７３４と共に記憶されて、ルート項目ＡＢ　７３６を形成する。この仕方で処理がＣＬＫ３　７１４を通じて継続し、そのときにルート項目ＡＢＣＤ　７０８が圧縮データ・ファイル内に記憶される。クロック４　７３８において、記号「Ａ」が、ルック・アヘッド・バッファ７１８内にある。記号「Ａ」はまたサーチ・バッファ内にも発見されるが、クロック４　７３８で何の項目も出力されない。むしろ処理は継続されて、スライディング・ウインドウ７０５内に複写されたシンボル・シーケンスが識別される。
【００５０】
ＣＬＫ８　７４０まで、出力なしに処理が続く。ＣＬＫ８　７４０でルック・アヘッド・バッファの記号シーケンス「ＡＢＣＤ」が、サーチ・バッファ７２１内の記号シーケンスと一致する。記号シーケンス「ＡＢＣＤ」が圧縮されてコピー項目７１０になり、以前に記憶されたルート項目７０８と共に記憶される。前述のようにコピー項目７１０は、オフセット値７３０と長さ値７３２を含む。長さ値７３２は、コピー項目７１０で表現される記号シーケンス内の記号の数を表現する。オフセット値７３０は、コピー項目７１０により複写された（ｄｕｐｌｉｃａｔｅｄ）ルート項目７０８の、相対的な近接を表現する。図７の実施例においてオフセットは、０（すなわちもっとも近接したルート項目が、０のオフセット値にある）でスタートする。他の実施例のオフセット値が任意の数の方法で表現されることを当業者は理解するであろう。たとえば、このオフセット値は、入力データ・ストリームを含むファイルへのオフセットを表現し得る。また、このオフセット値は、コピー項目からルート記号シーケンスの開始またはルート・シーケンスの終了までの相対的な距離を表現し得る。好ましい実施例においてオフセット値は、データ圧縮を最大にするように選択される。
【００５１】
クロック８　７４０で、ルート項目ＡＢＣＤ７０８は、ルック・アヘッド・バッファ７１８の記号シーケンス「ＡＢＣＤ」に関連するルート項目である。クロック８　７４０におけるサーチ・バッファ７２１の記号シーケンス「ＡＢＣＤ」は、ルック・アヘッド・バッファ７１８内の記号シーケンス「ＡＢＣＤ」に直接に隣接する。したがって、コピー項目７１０のオフセット値７３０が０であり、関連項目がルート項目７０８であって、これはコピー項目７１０に直接に隣接することを示す。
【００５２】
一つの実施例においてオフセット値７３０は、完全な一致が配置され尽くした時のスライディング・ウインドウにおけるインデックス位置のことを言う。言い換えれば、新しい候補記号が入力ストリームによりルック・アヘッド・ストリングへ導入されるときに、スライディング・ウインドウ７０５は前進しない。スライディング・ウインドウ・インデックスが前進され、ルックアヘッド・ストリングがウインドウ７０５へコピーされるのは、次の二つの場合のいずれかが起きる場合である：１．スライディング・ウインドウの中のいずれかのストリングとルック・アヘッド・ストリングの中に一致が何もなく、そしてルック・アヘッド・ストリングが最小候補ストリングよりも短い場合；または、２．一致が発見され尽くした場合である。これらの場合の両方において、ルック・アヘッド・ストリングがスライディング・ウインドウ７０５へコピーされて、コピー項目７１０が計算され出力され終わった後に、すなわちスライディング・ウインドウ７０５の更新が終わりまで行われた後に、このスライディング・ウインドウ・インデックスが前進する。この場合でなければ、考察中の一致が部分的にウインドウ７０５の外へスライドして、一致を完了できなくする。
【００５３】
ＣＬＫ８　７４０において、同様にルート項目７０８およびコピー項目７１０と共に記憶されるのは、ルート項目Ｅ　７４４であり、これはルック・アヘッド・バッファ７１８の単一信号であり、ルック・アヘッド・バッファ７１８はサーチ・バッファ７２１の中にはない。結合されたコピー項目７１０、ルート項目７０８、および第２ルート項目７４４は、共にルート／コピー項目７４２を形成する。上記のようにルート／コピー項目７４２は、好ましくは、ファイル内に記憶される。言い換えれば、クロック８　７４０の間に、すなわちルート項目Ｅ　７４４が決定されるときに、ルック・アヘッド・ストリームがもはやスライディング・ウインドウ内のいずれのストリングとも一致しないことが注目される。このクロック・サイクル中に圧縮ファイルが更新されて、ルック・アヘッド・バッファの内容により、スライディング・ウインドウ・バッファが更新される。
【００５４】
さらに処理を例示すると、図７は、追加のクロック・サイクルであるＣＬＫ９、ＣＬＫ１０、ＣＬＫ１１、およびＣＬＫ１２　７５０を含む。ＣＬＫ８　７４０の後に、上述の仕方で処理が継続して、最大の複写記号シーケンスを入力データ・ストリーム７０４内に配置して、ルート／コピー項目を使用して、それらをエン・コードする。圧縮器モジュール１００は、次に長い複写記号シーケンスをクロック１２　７５０で配置するが、これは、ルック・アヘッド・バッファ７１８の記号シーケンス「ＡＢＣＤ」である。ＣＬＫ１２　７５０において、ルック・アヘッド・バッファ７１８の記号シーケンス「ＡＢＣＤ」がサーチされて、サーチ・バッファ７２１内に発見される。
【００５５】
ＣＬＫ１２　７５０において、もう一つのオフセット値７５４ともう一つの長さ値を有するもう一つのコピー項目７５２が、発生される。長さ値７５６は４であるが、その理由はＣＬＫ１２　７５０におけるルック・アヘッド・バッファ７１８の複写記号シーケンス「ＡＢＣＤ」が４記号長であり、また関連のルート項目ＡＢＣＤ７０８が４記号長だからである。オフセット値７５４は１であるが、その理由は１ルート項目だからであって、このルート項目Ｅ　７４４は、コピー項目７５２とコピー項目７５２の関連ルート項目ＡＢＣＤ７０８の間にある。コピー項目７５２は、あらかじめ記憶されたルート／コピー項目７４２と共に記憶されてルート／コピー項目７６０を形成する。予備ルート／コピー・ファイル内に好ましく記憶されたルート／コピー項目へ全ての入力データがエンコードされるまで、上記の仕方で処理が継続する。注意すべきは、ルート項目とコピー項目を発生し表現する多くの他の技法が存在して、当技術分野に公知であり、また使用可能であることを注意すべきである。後述するが、予備ルート／コピー・ファイルは、ハフマン圧縮モードへの入力として使用されて、入力データをさらに圧縮する。
【００５６】
図８は、圧縮器モジュール１００のハフマン・エンコーディング・モードの演算モード８００の一例を図示する。一般にハフマン・エンコーディング・モードは、（図７に関して説明した）予備ルート／データ・ファイルからルート／コピー項目を読み取って、一つまたはそれ以上の関連のハフマン・エンコーディッド・データ・ファイルを発生することを含む。結果として、予備ルート／コピー・ファイルは、圧縮ファイル６２０（図６）のような最終圧縮データ・ファイルへ圧縮される。起動演算８０１が、ハフマン・エンコーディッド・モードを開始する。入力演算８０８が、ＬＺ７７モードにより生成された予備ルート／コピー・ファイルから、所定の数のビットを読み取る。一つの実施例において、入力演算８０８で９個のビットが読み込まれ、その８ビットが記号を表現し、１ビットは、この記号がルート項目であるかコピー項目であるかを指示する。他の諸実施例は、より多くのまたはより少ないビットを使用して、ルート／コピー項目を表現し、またそれぞれのインディケータとする。
【００５７】
入力演算８０８の後に、決定演算８０２は、入力演算８０８からの入力記号がルート項目であるかどうかを決定する。この記号がルート項目であるかどうかの決定は、好ましくは入力演算８０８で、検索された一つまたはそれ以上のインディケータ・ビットを検査することを含む。インディケータ・ビットのテストの多くの方法を使用できるが、その中には記号ビットをマスキング・オフして、インディケータ・ビットのみを得ること、または他の公知のビット操作が含まれるが、これに限定されない。この記号がルート項目であると決定されれば、そのときは、書き込み演算８０４がこのルート項目を、短縮ルート／コピーファイル、たとえば図６に説明した短縮ルート・コピーファイル６１６などに書き込む。インディケータ・ビットは、短縮ルート／コピー・ファイル６１６へも書き込まれ、これにより復元器モジュール２００は、どの項目がルート項目であり、どの項目がコピー項目であるかを、復元処理内において後に決定できるようになる。
【００５８】
ルート項目が短縮ルート／コピー・ファイル６１６へ書き込み済みになった後で、ハフマン・エンコードされるか、または短縮ルート／コピー・ファイル６１６へ書き込まれるべき記号が、予備ルート／コピー・ファイル内に残っているかどうかを、完了決定演算８０６が決定する。もし、決定演算８０６が予備ルート／コピー・ファイル内に処理すべき記号が更にあると決定すれば、演算フロー８００は、入力演算８０８へ戻る。しかしながら、完了決定演算８０６が予備ルート／コピー・ファイル内にもはや処理すべき記号が存在しないと決定すれば、ハフマン長さエンコーディング演算８５０が遂行される。これについては詳細を後述する。
【００５９】
さて、決定オペレーション８０２に戻ると、決定オペレーション８０２がこの記号をルート項目でないと決定すれば、この記号はコピー項目でなければならず、その場合長さ除去演算８１０が長さ値（図７の長さ値７５６など）をコピー項目から除去して、これにより、長さ値を次にハフマン・エンコードできるようになる。次に長さ値は、長さバッファ内に記憶されるが、この長さバッファは、長さ記憶演算８１２により、短縮ルート／コピー・ファイル６１６から識別される。長さ記憶演算８１２において、長さ値はまた次のハフマン・エンコーディングに必要な統計値を開発するためにカウントされる。長さ記憶演算８１２におけるカウントは、好ましくは各単独の長さ値に対応するカウンタを維持することと、記憶される長さ値に対応するカウンタをインクリメントすることを含む。
【００６０】
長さ記憶演算８１２の後で、オフセット除去演算８１４がコピー項目から（図７のオフセット値７５４のような）オフセット値の最上位部（ＭＳＰ）を除去する。オフセット値の最上位部は、オフセット値の最上位ビットを含む。オフセット除去演算８１４において、オフセット値から除去される最上位ビットの数は、特定の実施例および圧縮ファイル６２０の希望する圧縮比によって異なる。テストにより示されたことは、オフセット値の最上位の５ビットを除去しハフマン・エンコーディングするとかなりの圧縮比を達成できることであるが、その理由は、最上位部の好ましい統計的特性（変化における頻度の低さ）のためである。オフセット値の最上位部のサイズは、希望する圧縮／復元時間および希望する圧縮比など（に限定されない）特定アプリケーションのための希望する測度により、異なり得ることを当業者が理解するであろう。
【００６１】
オフセット除去演算８１４の後に、ＭＳＰオフセット記憶演算８１６がＭＳＰをオフセット・バッファ内に記憶する。このＭＳＰオフセット記憶演算８１６はカウンティング演算を含み、そこで後続のハフマン・エンコーディングのためにＭＳＰがカウントされる。好ましくは、カウンティングは、各独自なＭＳＰに対応する一つのカウンタを維持することと、ＭＳＰオフセット記憶演算８１６で記憶される各ＭＳＰに対応するカウンタをインプリメントすることを含む。オフセット・バッファは、長さバッファおよび短縮ルート／コピー・ファイル６１６から区別される。それから最下位部（ＬＳＰ）オフセット記憶演算８１８は、圧縮コピー項目としての短縮ルート／コピー・ファイル６１６内に、コピー項目の何が残っているか、どれがオフセット値の最下位部であるかを記憶する。このＬＳＰオフセット記憶演算８１８が完了すると、完了決定演算８１６が、予備ルート／コピー・ファイル内にエンコードすべきルート項目またはコピー項目がまだ残っていないかどうかを決定する。
【００６２】
完了決定演算８１６が、処理すべきルート項目またはコピー項目が何も残っていないと決定すれば、ハフマン長さエンコーディング演算８５０が、長さ記憶演算８１２であらかじめ生成された長さバッファの内容を、ハフマン・エンコードする。ハフマン長さエンコーディング演算８５０は、図６のエンコーディッド長さデータ６１７のようなエンコードされた長さデータを生成する。この長さバッファのハフマン・エンコーディングは、一般に長さバッファの読み取りと長さバッファ内における全ての長さ値の発生をカウンすることを含む。こうして、各長さ値について統計的尤度値が計算されて、各長さ値が起きるであろう尤度を表現する。それから長さ値は、最も起こりそうなものから殆ど起こりそうもないものへと、尤度に従ってソートされる。図１は、ハフマン・エンコード中に発生されるデータの例を図示する。
2004507145.tif 000003
【００６３】
第１コラムはオプションであって、表１のデータを含むテーブルへインデックスするのに使用できるインデックス値を提供する。第２コラムは、エンコードされていないデータ（１６進フォーマットで表現された長さ値またはＭＳＰオフセット値）をリストする。第３コラムは、第２コラムの値の各々について関連の発生の尤度をリストする。第３コラムに与えられた確率の各々は、エンコードされたオフセット値６１３のハフマン・エンコーディッド値またはエンコードされた長さデータ６１７が、関連のエンコードされていないデータを表現する尤度を示す。第３コラムのデータは、最高確率から最低確率へソートされている。第５コラムの値は、第２コラムの関連のエンコードされていない値の各々の（バイナリにおける）ハフマン・エンコーディッド・バージョンである。第５コラムのコードは、圧縮中にエンコーディッド長さデータ６１７とエンコーディッド・オフセット・データ６１３内に記憶される。第４コラムは、第５コラムの各コードに関連する長さ値をリストする。第４コラムの各長さ値は、第５コラムの関連のハフマン・コード内のビットの数を示す。
【００６４】
表１に見えるように、最も起こり得る長さすなわちＭＳＰ値（０００３）は、ビットの最小値を有して、ハフマン・コード（００）に対応する。各長さすなわちＭＳＰ１について（第３コラムの確率値減少により示されるように）、生起の確率が少なくなるにつれて、（第４コラムのビット長さの増加により示されるように）対応するハフマン・コードのビット・サイズが大きくなる。ハフマン・コーディングの利点には、エンコードされたデータを記憶するために元のデータよりも、全体的な平均で、より少ないメモリしか必要なく、また各ハフマン・コードが独自であることが含まれる。図６のハフマン長さ辞書６１９のようなハフマン長さ辞書を、ハフマン長さエンコーディング演算１５０で構築することが望ましい。ハフマン長さ辞書６１９の構築は、各ハフマン・コード（たとえば表１の第５コラム）、およびその対応する長さ（たとえば表１の第４コラム）および長さ値（たとえば表１の第２コラム）を、長さ辞書バッファまたはファイルにパックすることを含む。続いてハフマン長さ辞書６１９が復元器モジュール２００により使用されて、ハフマン長さコードを対応する長さ値に結合する。
【００６５】
長さ記憶演算８１２で生成される長さバッファは、ハフマン長さエンコーディング演算８５０でハフマン・エンコードされて、エンコーディッド長さデータ６１７を生成する。この長さバッファをハフマン・エンコードする一つの方法には、ハフマン・ツリーの構築が含まれ、当技術分野において知られている。一般に長さバッファについてハフマン・ツリーを構築するために全てのリーフ若しくは葉において独自な長さ値を有するように、ツリーが建設される。長さ値の最も起こりそうもないペアがペアにされて、それらの確率が互いに加算される。それからその次に起こりそうもない長さ値が、以前にペアにされた長さ値とペアにされ、これら３つの長さ値の確率が加算される。このペアリングと確率の合計は、全ての長さ値がペアにされ、それらの対応する可能性が合計されるまで継続される。注意すべきは、確率の最終合計値が１．０であることである。それからバイナリ・コードがツリーの各ブランチへ割り当てられる。各長さ値についてハフマン・コードを得るために、このハフマン・コードへ集められた各バイナリ・コードと共に、このブランチが長さ値からツリーのベースへ「トラバース」される。ハフマン長さエンコーディング演算８５０で生成されたハフマン長さ辞書６１９は、エンコーディッド長さデータ６１７に結合される。ハフマン長さ辞書６１９とエンコーディッド長さデータ６１７の組み合わせは、図６の説明に議論したようにハフマン・エンコーディッド長さファイル６１８である。
【００６６】
ハフマン長さエンコーディング演算８５０の後に、ハフマン・オフセット・エンコーディング演算８５２が、オフセット・バッファの内容、すなわちＭＳＰオフセット記憶演算８１６で生成されたオフセット値のＭＳＰを、ハフマン・エンコードする。ハフマン・オフセット・エンコーディング演算８５２がハフマン・オフセット辞書６１５を生成して、このハフマン・オフセット辞書６１５が、記憶演算８１６で以前に記憶したオフセット値の各独自なＭＳＰに対応するハフマン・コードを供給する。ハフマン・オフセット辞書６１５は、上記のようにハフマン長さエンコーディング演算８５０において長さ辞書６１９が生成されたのと同一の仕方で、生成される。ＭＳＰオフセット記憶演算８１６で生成されるオフセット・バッファがエンコードされて、エンコーディッド・オフセット・データ６１３が生成される。オフセット・バッファのエンコーディングは、エンコーディッド長さデータ６１７に関して説明したのと類似の方法で達成される。ハフマン・オフセット・エンコーディング８５２内で生成されるハフマン・オフセット辞書６１５は、エンコーディッド・オフセット・データ６１３と結合される。オフセット辞書６１５とエンコーディッド・オフセット・データ６１３の組み合わせは、図６に示すようにハフマン・エンコーディッド・オフセット・ファイル６１４を含む。
【００６７】
ハフマン・エンコーディッド・オフセット・ファイル６１４とハフマン・エンコーディッド長さファイル６１８が生成された後に、出力演算８５４がハフマン・エンコーディッド・オフセット・ファイル６１４とハフマン・エンコーディッド長さファイル６１８を短縮ルート／コピー・ファイル６１６へ結合して、圧縮データ・ファイル６２０を形成する。圧縮データ・ファイル６２０は、メモリ内に記憶され、続いて復元器モジュール２００により使用されて、元の生入力データを検索する。
【００６８】
図９は、復元モジュール２００により採用されるデコーディング処理の演算フロー９００の一例を図示する。本書において、アンパックされた辞書実施例と呼ばれる一つの実施例において、全てのハフマン辞書入力は復元により継続する以前にアンパックされる。パックされた辞書実施例と本書で呼ばれるもう一つの実施例においては、全てのハフマン・エンコーディッド・データが最初にデコードされる。こうしてデコーディングと復元の順序は、一般に厳密なものではなく、むしろ実施例から実施例へと変わり得る。当業者は、本書に説明される細部の多くを遂行するために、細部を変更しても説明された復元出力ファイルが達成されることを理解するであろう。
【００６９】
図９に示す実施例は、パックされた辞書の実施例を図示する。図９に示す実施例においてハフマン・デコーディングが起きると、パックされたハフマン辞書がアクセスされる。演算フロー９００の開始９０１において、読み取り演算９１０がルート項目と部分コピー項目からなる短縮ルート／コピー・ファイル６１６の第１記号を読み込む。それからルート項目決定演算が、読み取り演算９１０で読み込まれた記号がルート項目であるかどうかを決定する。図８の説明で議論したように記号がルート項目であるか、コピー項目であるかを示すインディケータと共に、記号が記憶されることが望ましい。一つの実施例において短縮ルート／コピー・ファイル６２０内の各ルート項目とコピー項目に単一のインディケータ・ビットが添付されて、このインディケータ・ビットを決定演算９１２が読み取ることができ、この記号がルート項目であるかまたはコピー項目であるかを決定する。たとえば、もしインディケータ・ビットが１であれば、この記号はコピー項目であるが、インディケータ・ビットが０であれば、この記号は、ルート項目である。
【００７０】
読み取り演算９１０で、読み込まれた記号がルート項目であることを決定演算９１２が決定すれば、書き込み演算９１４がこのルート項目をスライディング・ウインドウ・バッファへと書き込む。書き込み演算９１４におけるスライディング・ウインドウ・バッファは、図７の説明で議論したスライディング・ウインドウに類似のスライディング・ウインドウである。圧縮スライディング・ウインドウ・バッファと復元スライディング・ウインドウ・バッファは、圧縮データ内にエンコードされる長さ値が一致するためには、同一サイズでなければならない。書き込み演算９１４は、スライディング・ウインドウ・バッファの論理端へ記号を添付するのが好ましい。バッファがいっぱいの時は、新しい記号が書き込み演算９１４に追加される度に最も古い記号がバッファから除去される。こうして、スライディング・ウインドウ・バッファは、「先入れ先出し」バッファとみなされる。
【００７１】
書き込み演算９１４に続いて、出力演算９１６が信号をマイクロ・プロセッサ読み取り可能なデータ・ファイルへ出力するが、本書ではこのデータ・ファイルを復元出力ファイルと呼ぶ。復元出力ファイルが、出力演算９１６以前に生成されてない場合は、出力演算９１６が、それへルート項目を書き込む以前に復元出力ファイルを生成して、開く。後述するように、出力演算は、復元出力ファイルへ、短縮ルート／コピー・ファイル６１６内のコピー項目から圧縮された他の記号を出力する。結果として、演算フロー９００の終わりにおいて、図６、図７、図８の説明で議論したように、圧縮器モジュール１００へもともとインプットされた全ての信号を、復元ファイルが含む。
【００７２】
出力演算９１６の後に、完了決定演算９１８が、短縮ルート／コピー・ファイル６１６から読み取るべき記号が何か残っているかどうかを決定する。読み取るべき信号が更にあるならば、読み取り演算９１６が、短縮ルート／コピー・ファイル６１６から次の信号を入力または読み取る。それからルート項目決定演算９１２が、読み取り演算９１０で読み取る次の記号がルート記号であるかどうかを決定する。こうして、演算９１０、９１２、９１４、９１６、および９１８からなるループは、短縮ルート／コピー・ファイル６１６内に含まれるルート項目を共に復元して、短縮ルート／コピー・ファイル６１６でコピー項目を復元するのに使用されるスライディング・ウインドウ・バッファを構築する。
【００７３】
再び決定演算９１２を参照すると、読み取り演算９１０で、あらかじめ読まれた記号がルート項目ではないと決定されれば、それは、一つの圧縮されたコピー項目である。詳しくは、読み取り演算９１０で読まれた記号がルート項目でなければ、それはコピー項目のオフセット値の最下位部（ＬＳＰ）であると仮定されて、それから復元若しくは再構成演算９２２がこのＬＳＰを使用して、このコピー項目を復元し再構成し（ｒｅｃｏｎｓｔｒｕｃｔ）、このコピー項目は、オフセット値と長さ値を含む。復元演算９２２で、コピー項目を再構成することは、一般にこのコピー項目のオフセット値と長さ値を生成することを含む。オフセット値を生成することは、読み取り演算９１０で読まれたＬＳＰをオフセット値の最上位部（ＭＳＰ）と結合する。前述のようにＭＳＰは、圧縮処理中にあらかじめエンコードされており、ハフマン・エンコーディッド・オフセット・ファイル６１４内に記憶されている。ＭＳＰは、ハフマン・エンコーディッド・オフセット・ファイル６１４のエンコーディッド・オフセット・データ６１３内の入力をデコードすることにより、復元演算９２２内で得られる。復元演算９２２は、ハフマン・エンコーディッド長さファイル６１４にあらかじめ記憶されたエンコーディッド長さデータ６１７内の入力をデコードすることにより、コピー項目の長さ値を獲得する。こうして、コピー項目を復元するために、復元演算９２２は２つの値、すなわちオフセット値のエンコードされたＭＳＰと、エンコードされた長さ値をデコードする。これらの値をデコードする処理は、図１０の説明の中で詳細を議論するが、図１０は、ＭＳＰ値と長さ値をデコードするのに使用できる演算フロー１０００の実施例を説明する。演算フロー１０００に示すルーチンのようなデコーディング・サブルーチンを使用することにより、再構成演算９２２が一つのコピー項目を発生する。
【００７４】
再構成演算９２２によりコピー項目が再構成されると、このコピー項目は、検索演算９２４により使用されて、コピー項目により表現される元の入力記号を検索する。検索演算９２４において、書き込み演算９１４で生成されたスライディング・ウインドウ・バッファ内の一致記号シーケンスを識別することにより、一つの記号シーケンスが生成される。一致記号シーケンスは、再構成演算９２２により発生されるコピー項目のオフセット値で与えられるスライディング・ウインドウ・バッファへのオフセットに位置する。記号シーケンス内の記号の数は、再構成演算９２２より発生されるコピー項目の長さ値で与えられる。検索演算９２４で検索される記号シーケンスは、書き込み演算９１４でスライディング・ウインドウ・バッファへ書き込まれて、出力演算９１６で復元出力ファイルへ出力される。出力演算９１６の後で、演算フロー９００は決定演算９１８へ続く。決定演算９１８が、短縮ルート／コピー・ファイル６１６の全ての記号が処理済みであると決定すれば、デコーディング処理が完了して、出力演算９１６が、マイクロ・プロセッサで読み取りと実施が可能な復元ファイルを生成済みにする。
【００７５】
図１０は、図９に関して示され説明された再構成演算９２２の一つの可能な演算フロー１０００を示す。前述のようなハフマン・エンコーディッド・オフセット・ファイル６１４は、好ましくはエンコーディッド・オフセット・データ６１３を含み、このエンコーディッド・オフセット・データ６１３は、コピー項目オフセット値の最上位部（ＭＳＰ）のエンコーディッド・バージョンとエンコードされたＭＳＰをデコードするためのパックされたハフマン・オフセット辞書６１５を保持する。同様にハフマン・エンコーディッド長さファイル６１８は、エンコーディッド長さデータ６１７を含み、このエンコーディッド長さデータ６１７は、コピー項目長さ値のエンコーディッド・バージョンと、エンコーディッド長さ値をデコードするためのパックされたハフマン長さ辞書６１９を記憶する。オフセット辞書６１５と長さ辞書６１９は全てのあり得るハフマン・コードを含み、各コードの（ビットによる）関連長さと、コードにより置き換えられる（表１の第２コラムのような）値とが、図８の説明で議論したように含まれている。これらの辞書内のデータは、パックされているので、各データ項目の開始は必ずしもバイト（８ビット）境界上にあるわけではない。むしろこれらのビットは、並べてパックされて、その間に浪費されるメモリが何もない。結果として、これらのパックされた辞書はメモリに最適な小量を必要とするだけである。
【００７６】
図８の実施例において、エンコーディッドＭＳＰとエンコーディッド長さ値が、それぞれのハフマン・エンコーディッド・データ（６１３および６１７）内に、それらの関連項目が短縮ルート／コピー・ファイル６１６内に記憶されるのと同一順序で記憶される。結果として、短縮ルート／コピー・ファイル６１６のコピー項目は、ハフマン・エンコーディッド・データにおけるそれらに関連のエンコーディッド値の順序に配置される。こうして一般に（演算９１０においてのように）短縮ルート／コピー・ファイル６１６から部分コピー項目が検索される度に、次のエンコーディッドＭＳＰと次のエンコーディッド長さ値がそれぞれのハフマン・エンコーディッド・データ（６１３および６１７）から検索されて、このコピー項目を復元する。
【００７７】
図１０において、開始演算１００２が初期化処理を遂行する。オフセット・デコーディング演算１００４が、ハフマン・エンコーディッド・オフセット・ファイル６１４のエンコーディッド・オフセット・データ６１３から、次のエンコーディッドＭＳＰをデコードする。一つの実施例において、エンコーディッドＭＳＰの長さは、ハフマン・エンコーディッド・オフセット・ファイル６１４の中に記憶されない。むしろあり得る各コードは、その関連の長さと共にパックされたハフマン・オフセット辞書６１５に記憶される。デコーディング演算１００４は、エンコーディッド・オフセット・データ６１３からビットを繰返し読み込んで、一時的に記憶する。もう一つのビットをデコーディング演算１００４が読むたびに、デコーディング演算１００４は読まれたビットの数に等しい関連の長さを有するハフマン・オフセット辞書６１５のコードをサーチする。ハフマン・オフセット辞書６１５のコードの一つがエンコーディッド・オフセット・データ６１３から読まれたビットに一致（マッチ）すれば、（図１の第２コラムでのように）そのコードに関連のコピー項目により置き換えられた値が、ハフマン・エンコーディッド・オフセット辞書６１５から読まれる。この置き換えられた値は、コピー項目のオフセット値のＭＳＰを表現する。それから前置き演算１００６が、読み取り演算９１０で得られたＬＳＰに対してＭＳＰを前置きする。こうして、前置き演算１００６が、コピー項目のオフセット値全体を再構成する。
【００７８】
前置き演算１００６に続いて、長さデコーディング演算１００８が、一つのコピー項目に関連する一つのエンコード長さ値をデコードする。関連のエンコーディッド長さ値が、ハフマン・エンコーディッド長さファイル６１８のエンコーディッド長さデータ６１７から読まれる。長さデコーディング演算１００８において、エンコーデッド長さ値をデコードすることにより、デコーディッド長さ値が得られる。そうした演算において、オフセット・デコーディング演算１００４で説明した技法に類似の技法を使用して、エンコーディッド長さ値がデコードされる。長さデコーディング演算１００８は、エンコーディッド長さデータ６１７から１回に１ビットずつ繰返し読みとって、読み取られたビットの数をカウントする。ハフマン長さ辞書６１９内に記憶されたコードに関連の長さが、読み取られたビットに等しいかどうかが決定される。読み取られたビットの数に等しい関連の長さを有する全てのコードについて、エンコーディッド長さデータ６１７から読み取られたビットに対して、これらのコードが比較される。これらのコードの一つが一致すれば、一致コードに関連する（表１の第２コラムのような）コピー項目の長さ値が、ハフマン長さ辞書６１９から検索される。検出されたコピー項目は、そのコピー項目の長さ値であって、演算フロー１０００が終了する。
【００７９】
重要なことに、ハフマン・オフセット辞書６１５およびハフマン長さ辞書６１９を使用することにより、ハフマン・デコーディング処理は、他の従来の方法よりもかなり少ないスタック空間しか必要としない。ハフマン辞書は、平坦化されたハフマン・ツリーとして見られ得る。本書に説明する実施例において、ハフマン・ツリーが平坦化されているので、デコーディングのコンピュータ処理は、ハフマン・ツリーを「横切る（トラバースする）」必要がない。結果として、トラバースする方式に典型的な多くのスタック・ポップ（ｓｔａｃｋ ｐｏｐｓ）とスタック・プッシュ（ｓｔａｃｋ ｐｕｓｈｅｓ）が、本発明の実施例においては不必要である。さらにハフマン辞書６１５および６１９の最初の部分に一層ふさわしい記号が記憶されているので、一致コードのために辞書をサーチする時間が最小化される。
【００８０】
例示のためであって限定のためではないが、図１１は、ハフマン長さエンコーディング演算８５０のようなエンコーディング演算と、復元器モジュール２００によるその使用の、パックされた出力１１００の一例を図示する。上述のようにエンコーディング演算の出力は、ハフマン辞書、およびたとえば図６に示したハフマン長さ辞書６１９とエンコーディッド長さデータ６１７のような一組のハフマンエンコーディッド・データからなる。図１１は、エンコーディング演算の出力をパックすることにより、更なる圧縮を達成する実施例を図示する。
【００８１】
パックされた辞書１１０４の理解を読者に支援するために、表１に示したものに類似する長さ値の例示的なハフマン辞書１１０２が、図１１内に表として含まれている。ハフマン辞書１１０２は、一連の長さすなわちＭＳＰ値（１６進表記で示されている）１１０６、コード長さ（バイナリ表記による）１１０８、および対応する独自なハフマン・コード（バイナリ表記による）１１１０を含む。長さすなわちＭＳＰ値１１０６、コード長さ１１０８、ハフマン・コード１１１０の各セットは、ハフマン辞書１１０２の一つの入力１１１２と考えられる。
【００８２】
ハフマン・ツリー１１０２のパックされたハフマン辞書１１０４形式を、図１１の表の下に示す。パックされた辞書１１０４は、別々の辞書入力１１１２の各々に対応するパックされた入力１１１４を含む。図１１に示すようにパックされたハフマン辞書は、バイナリ・データの連続的なストリームであるが、読者を支援するために各パックされた入力の間に１スペースをあけて、パックされた辞書を示す。この例において各パック入力１１１４の最初の８ビットは、パック値１１１６（読者に見やすくするために太字で１１図に示されている）を含み、長さのバイナリ形式すなわちＭＳＰ値１１０６に対応する。パック値１１１６を表現するために、この例では８ビットが使用されているが、これ以下またはこれ以上のビットを使用でき、またハフマン・コード１１１０の全ての値１１０６を表現するのに充分な数のビットでさえあれば使用できることが、当技術分野に熟達した人々に理解されよう。
【００８３】
次の５ビット（各パック入力１１１４を読者に見やすくするために図１１でアンダーラインして、示されている）は、パックされたコード長さであり、その入力１１１２のコード長さ１１０８に対応する。ここでもこの例では５ビットを使用するが、ハフマン辞書１１０２に見出される最大長さを表現するのに充分ならば、どんな数のビットも使用される。
【００８４】
各パック入力１１１４の残りのビット（読者に見やすくするために図１１にイタリック体で示されている）は、各入力１１１２の関連ハフマン・コード１１１０である。上述のように各ハフマン・コード１１１０のビットの長さは、パック入力１１１４の間で異なり、各々の先行するコード長さ１１１６により指示される値に等しい。したがって、各パック入力１１１４は、また各入力１１１４におけるハフマン・コード１１１０のサイズによっても異なる。
【００８５】
それから図１１に図示する例において、パックされた辞書１１０４の後で、ハフマン・エンコーディング演算は、たとえば図６のハフマン・エンコーディッド長さデータ６１７のようなエンコードされたデータのパックされた形式であるパックされたハフマン・エンコーディッド・データ１１２０を出力する。このパックされたハフマン・エンコーディッド・データ１１２０は、独自なハフマン・コード１１１０のストリームのみから構成される。パックされたハフマン・エンコーディッド・データ１１２０における各個別のハフマン・コード１１１０を読者に識別しやすくするために、各ハフマン・コード１１１０の間に１スペースが挿入されている。
【００８６】
図１１はまた、パックされたハフマン・エンコーディッド・データ１１２０から元の長さすなわちＭＳＰ値１１０６を得るために、パックされたハフマン辞書１１０４がどのように使用されるかを図示する。上述のように各ハフマン・コード１１１０が独自であることがハフマン・コード１１１０の特性である。たとえば「１００」は、３ビット長バイナリ・ハフマン・コード１１１０であるから、他のいずれのハフマン・コード１１１０もその最初の３ビットとして、「１００」を含まない。この特性により、パックされたハフマン・エンコーディッド・データ１１２０をサーチ・バッファへ１ビットずつ読み込むことが出来る。各ビットを読み込んだ後に、サーチ・バッファ内に現在含まれているビットの数と等しいコード長さ１１１８を有するハフマン辞書入力１１１４を、復元器モジュール２００が逐次的にサーチする。一致ハフマン・コード１１１０が発見されなければ、ハフマン・エンコーディッド・データ１１２０から次のビットがサーチ・バッファへ読み取られる。それから復元器モジュール２００は、一致ハフマン・コード１１１０のために、サーチ・バッファ内の現在のビット値を有するパックされた入力１１１４をサーチする。この処理は、サーチ・バッファの内容がハフマン・コード１１１０と一致するまで繰り返される。サーチ・バッファの内容がハフマン・コード１１１０と一致すれば、復元器モジュール２００が、パック入力１１１４内のハフマン・コード１１１０について対応する長さすなわちＭＳＰ値１１１６を獲得して、そのハフマン・コード１１１０を対応する値１１１６へデコードする。この値１１１６を獲得した後に、サーチ・バッファがクリアされて、パックされたハフマン・エンコーディッド・データ１１２０の次のビットがサーチ・バッファ内に読み込まれて、このサーチが繰り返される。
【００８７】
たとえば図１１のパックされたハフマン・エンコーディッド・データ１１２０に着目すると、復元器モジュール２００は、パックされたエンコーディッド・データ１１２０の最初のビットをサーチ・バッファへ読み取る。次に復元器モジュール２００が、最初に長さ「１」の長さコードを探して、パックされた辞書１１０４をサーチする。単独ビットのハフマン・コード１１１０が何も発見されないので、サーチが停止されて、それから復元器モジュール２００が、パックされたハフマン・エンコーディッド・データ１１２０の次のビットをサーチ・バッファへ読み込む。いまやサーチ・バッファは、二つのビット・コード「１１」を含む。次に、サーチは、パックされた辞書１１０４内で、サーチをやめた場所から始まるパックされた辞書１１０４に着目する。パックされた辞書内の最初の２ビット長ハフマン・コード１１１０は、「００」であり、これは、サーチ・バッファの内容と一致しない。次のパック入力１１１４は、３ビット・コード長１１１８を有するので、復元器モジュール２００は、辞書サーチを停止して、パックされたエンコーディッド・データ１１２０の次のビットを、サーチ・バッファ内へ読み込む。サーチ・バッファは、今や３ビット・コード「１１１」を含む。復元器モジュール２００は、それが中止した場所でパック辞書１１０４のサーチを再開する。パックされた辞書１１０４内の次のパック入力１１１４は、３のコード長１１１８を有し、サーチ・バッファの内容が、ハフマン・コード１１１０と一致する。この時点において、復元器モジュール２００は、ハフマン・エンコーディッド・データ１１２０内のハフマン・コード１１１０を、パックされた辞書１１０４内のハフマン・コード１１１０へ一致済みである。それから復元器モジュール２００は、一致したパック入力１１１４から対応する値１１１６を読み取って、それを出力するかまたは後に使用するために記憶する。それからサーチ・バッファが、クリアされて全てのパックされたハフマン・エンコーディッド・データ１１２０がデコード済みになるまでパックされたハフマン・エンコーディッド・データ１１２０内の次のハフマン・コード１１１０を発見することが繰り返される。
【００８８】
さて、図１２へ移るとパックされたハフマン辞書１２０４の代わりの実施例を使用して、パックされたハフマン・エンコーディッド・データ１２２０から長さまたはＭＳＰ値１２１６を得ることが、図示１２００されている。図１２は、パックされたハフマン辞書とパックされたハフマン・エンコーディッド・データ１２２０を例示のために示し、これらは、図１１に示したそれらのものに同一である。ここでもパックされた辞書は、図１１に示した別々の辞書入力１１１２の各々に対応するパック入力１２１４を含むものと考えられる。パックされたハフマン辞書１２０４は、バイナリ・データの連続的なストリームであるが、ユーザを支援するために各パック入力１２１４の間に１スペースをあけて、パックされた辞書１２１４を示してある。図１１に示した例と一致して、各パック入力１２１４の最初の８ビットは、パックされた長さすなわちＭＳＰ値であって、（ユーザが見やすいように太字で示す）、次の５ビットは、パックされたコード長１２１８（アンダーラインを付けて示す）であり、また各パック入力１２１４の残りのビットは、関連のハフマン・コード１２１０（イタリック体で示す）である。
【００８９】
図１２に図示する実施例において、復元器モジュール２００は、最初にパックされたハフマン辞書１２０４をアンパックして、アンパックされた辞書１２２２を生成する。このアンパックされた辞書１２２２は、アンパックされたハフマン辞書が読み込まれるときに作動中に形成される。アンパックされた辞書１２２２は、アンパック入力１２２４へのパックされたハフマン辞書の各パック入力をアンパックすることにより生成される。パック入力１２１４は、メモリへのパック入力１２１４のパック値１２１６を記憶して、コード長１２１８からのパック入力１２１４のハフマン・コードの長さを決定して、それから一つのアンパックされたハフマン・コード１２３０をメモリ中に記憶することによりアンパックされるが、ハフマン・コード１２３０はハフマン・コード１２１０の８ビット・バージョンであり、そこでは、ハフマン・コード１２１０は、８ビットのアンパックされたハフマン・コード１２３０の最上位ビットである。たとえば、あるハフマン・コード１２１０「１１０１０」が、アンパックされたハフマン・コード１２３０「１１０１００００」になる。パック入力１２１４をアンパックして、アンパック入力１１４１２１４にするこの処理は、パックされた辞書１２０４全体がアンパックされ終わって、メモリに記憶されるまで繰り返される。こうして、アンパックされた辞書１２２２は、二つの項目すなわちアンパックされた値１２１６とアンパックされたハフマン・コード１２３０を含む。このアンパックされた辞書は、アンパックされた辞書１２２２内の各項目が、固定長ワードで記憶されている点において、パックされたハフマン辞書１２０４と異なる。この例は、アンパックされた辞書１２２２の各項目を、８ビットであるとして示すが、しかし、注意すべきは、パックされた辞書１２０４内の最長項目と同等またはより長い長さである限りどのような固定長も使用可能なことである。アンパックされた辞書１２２２が固定長を使用するので、各アンパック入力１２２４のハフマン・コードを識別するためにコード長さ１２１８は、もはや必要でない。
【００９０】
アンパックされた辞書１２２２は、下記のようにパックされたハフマン・エンコーディッド・データ１２２０から長さすなわちＭＳＰ値１２１６を得るために使用できる。前述のように各コードが独自なことがハフマン・コード１２１０の特性である。従って各アンパックされたハフマン・コード１２３０もまた独自である。アンパックされた辞書１２２２を使用する復元器モジュール２００は、その時、一致が発見されるまでアンパックされたハフマン・コードをサーチするだけでよい。８ビット・サーチ・バッファは、最初に６ビットの「０」をロードされ、それからこのバッファの最上位ビットとして、２ビットのハフマン・エンコーディッド・データ１２２０が読み込まれる。たとえば「１１」が８ビット・バッファへ読み込まれて、「１１００００００」を得る。この例では、最小ハフマン・コード１２１０が２ビット長であるので、２ビットが読み込まれる。次に復元器モジュール２００がアンパックされた辞書入力１２２４を逐次的にサーチして、一致する８ビットのアンパックされたハフマン・コード１２３０を探す。一致するアンパック・ハフマン・コード１２３０が発見されなければ、次のビットがハフマン・エンコーディッド・データ１２２０から８ビット・サーチ・バッファへ読み込まれる。それから復元器モジュール２００がアンパック入力１２２４をサーチして、一致するアンパック・ハフマン・コード１２３０を探す。一致が何も発見されなければ、もう一つのビットがサーチ・バッファへ読み込まれて、サーチ・バッファの内容がアンパックされたハフマン・コード１２３０に一致するまで処理が繰り返される。サーチ・バッファの内容が、アンパックされたハフマン・コード１２３０と一致すると、復元器モジュール２００がアンパック入力１２２４におけるアンパックされたハフマン・コード１２３０の一致について対応する長さすなわちＭＳＰ値１２１６を獲得して、パックされたハフマン・エンコーディッド・データ１２２０のハフマン・コード１２１０をデコードして、その対応する値１２１６にする。値１２１６を獲得した後にサーチ・バッファがクリアされて、パックされたハフマン・エンコーディッド・データ１２２０の次の２ビットが、サーチ・バッファへ読み込まれて、サーチ処理が繰り返される。理解すべきは、８ビット・サーチ・バッファについての上述の議論は、単に例示的なものに留まることである。あらゆるサイズのサーチ・バッファが使用可能であり、多重サーチ・バッファも同様に使用可能である。
【００９１】
要約すると、本発明の一つの実施例はデータ入力ファイル（６１２など）を圧縮して、圧縮データ出力ファイル（６２０など）を生成する方法と見ることができる。この方法は、スライディング・ウインドウ（７００など）圧縮方式を使用して、データ入力ファイル（６１２など）を逐次的に検査して、これによりルート項目（７０８など）とコピー項目（７１０など）を生成することを含む。生成されたコピー項目（７１０など）は、各々長さ値（７３２など）およびオフセット値（７３０など）を含む。オフセット値（７３０など）は、さらに最上位部と最下位部に細分され、これらは、この方法により異なった仕方で取り扱われる。この方法は、ルート項目（７０８など）を含む短縮ルート／コピー・ファイル（６１６など）およびコピー項目（７１０など）のオフセット値（７３０）の最上位部を生成する。この方法は、コピー項目（７１０など）のオフセット値（７３０など）の最上位部を圧縮して、圧縮オフセット・ファイル（６１４など）を生成する。この方法は、またコピー項目（７１０など）の長さ値（７３２など）を圧縮して、圧縮長さファイル（６１８など）を生成する。この方法の一部分として、短縮ルート／コピー・ファイル（６１６など）、圧縮オフセット・ファイル（６１４など）および圧縮長さファイル（６１８など）が結合されて、圧縮データ出力ファイル（６２０など）を生成する。
【００９２】
もう一つの実施例は、圧縮データ入力ファイル（６２０など）を復元するデータ復元方法とみなされ、圧縮長さファイル（６１８など）、圧縮オフセット・ファイル（６１４など）、短縮ルート／コピー・ファイル（６１６）を含む。短縮ルート／コピー・ファイル（６１６など）は、ルート項目（７０８など）と圧縮コピー項目を含む。圧縮コピー項目の各々は、非圧縮コピー項目（７１０など）のオフセット値（７３０など）の最下位部である。各非圧縮コピー項目（７１０など）は、長さ値（７３２など）およびオフセット値（７３０）を含む。
【００９３】
データ復元方法の一つのステップは、圧縮データ入力ファイル（６２０など）を受信することである。この方法は、圧縮長さファイル（６１８など）を圧縮して、長さ値（７３２など）を獲得する。同様にこの方法は、圧縮オフセット・ファイル（６１４など）を復元して、オフセット値（７３０など）の最上位部を獲得する。この方法は、オフセット値（７３０など）の最下位部、オフセット値（７３０など）の最上位部、および長さ値（７３２など）から非圧縮コピー項目（７１０など）を形成する。この方法は、非圧縮コピー項目（７１０など）により、識別される一致データ・ストリングを決定して、ルート項目（７０８など）および一致データ・ストリングを含む復元データ出力ファイル（２０４など）を出力する。
【００９４】
もう一つの実施例は、データ記憶装置（３２０など）とみなされ、マイクロプロセッサ（５１６など）、非揮発性メモリ（５２４など）、揮発性メモリ（５３０など）、非揮発性メモリ（５２４など）に記憶された圧縮オペレーティング・コード・ファイル（６２０など）、および前記圧縮オペレーティング・コード・ファイル（６２０など）を復元する復元器モジュール（２００など）を含み、前記圧縮オペレーティング・コード・ファイル（６２０など）は、第１圧縮ファイル（６１８など）、第２圧縮ファイル（６１４など）、および短縮ルート／コピー・ファイル（６１６など）を含む。
【００９５】
このように考えると、第１圧縮ファイル（６１８など）は、第１ハフマン辞書（６１９など）および前記第１ハフマン辞書（６１９など）によりエンコードされたハフマン・エンコーディッド長さデータ（６１７など）を含む。同様に第２圧縮ファイル（６１４など）は、第２ハフマン辞書（６１５など）および第２ハフマン辞書（６１５など）によりエンコードされるハフマン・エンコーディッド・オフセット・データ（６１３など）を含む。
【００９６】
さらにもう一つの実施例は、データ記憶装置（３２０など）内の圧縮オペレーティング・コード・ファイル（６２０など）を復元して、実行可能なオペレーティング・コード・ファイルにするシステムと見ることができる。データ記憶装置（３２０など）は、データ記憶装置（３２０など）上の非揮発性メモリ（５２４など）内の圧縮オペレーティング・コード・ファイル（６２０など）を記憶する。圧縮オペレーティング・コード・ファイル（６２０など）は、短縮ルート／コピー・ファイル（６１６など）、第１ハフマン辞書（６１９など）、第１ハフマン辞書（６１９など）によりエンコードされる第１ハフマン・エンコーディッド・データ（６１７など）、第２ハフマン辞書（６１５など）、第２ハフマン辞書（６１５など）によりエンコードされる第２ハフマン・エンコーディッド・データ（６１３など）を含む。データ記憶装置（３２０など）は、また、圧縮オペレーティング・コード・ファイル（６２０など）を復元して、実行可能なオペレーティング・コード（６１２など）にする復元器手段（２００など）を含む。その上、復元器手段は、圧縮オペレーティング・コード・ファイル（６２０など）を復元して実行可能なオペレーティング・コード（６１２など）にする命令を含む、非揮発性メモリ（５２４など）に記憶された実行可能な命令ファイルと、これらの命令（１００など）を実行する手段を含む。
【００９７】
本書に指摘した長所と本書に固有の長所を共に達成するのに本発明がよく適合することは、明らかである。この開示のために現に好ましい実施例を説明してきたが、本発明の範囲内で種々の変更と修正、たとえば、発生されたファイル内の特定のデータ・ブロック（たとえば、第１ハフマン・ツリー）の厳密な位置における変化があり得る。たとえば、本発明の諸実施例は、コンパクト・ディスク・ドライブ、テープ・ドライブ、ディスケット・ドライブ、プリンタ、スキャナなど、通常運転中に始動および停止を繰り返す小型コンピュータ周辺装置において使用できる。なおまた有用な実施例には、パーソナル・データ・アシスタント、移動電話、全地球測位装置など限られた処理能力を有するより小さな計算装置における利用がある。開示された本発明の精神の内に含まれ、前記の特許請求の範囲に定義される多くの他の変更がなし得るが、これらは、当技術分野に熟達した人々にとって自明なことであろう。
【図面の簡単な説明】
【図１】
本発明の実施例による圧縮器モジュールのブロック図である。
【図２】
本発明の実施例による復元器モジュールのブロック図である。
【図３】
図１に示した圧縮器モジュールと図２に示した復元器モジュールのための例示的な動作環境である。
【図４】
図２に示した復元器モジュールの実施例を組み込んだディスク・ドライブの平面図である。
【図５】
図４に示したディスク・ドライブの簡単な機能ブロック図である。
【図６】
入力データをエンコードして圧縮データを発生するために、図１の圧縮モジュールにより使用される高レベルの例示的な処理を図示する一般的な演算フロー・チャートである。
【図７】
図１に示した圧縮器モジュールのＬＺ７７モードが、どのように入力データ・ストリームを圧縮して、予備圧縮ファイルにするかを示す例示的な図示である。
【図８】
図１の圧縮器モジュールのハフマン・エンコーディング・モードの演算フローの一例を図示する。
【図９】
図２の復元器モジュールにより使用されるデコーディング処理の演算フローの一例を図示する。
【図１０】
オフセット値とコピー項目の長さ値を検索するために図２の復元器モジュールにより使用される一つのあり得る処理の演算フローを図示する。
【図１１】
図７に示したようなハフマン・エンコーディング演算のパックされた出力を図示し、また、どのようにパックされた出力が図２の復元器モジュールにより、デコードされるかを図示する。
【図１２】
図１１に示したパック出力から図２に示した復元器モジュールにより生成されるアンパック辞書を図示し、またどのようにこのアンパック辞書が図２の復元器モジュールにより使用されるかを図示する。
【図１】
2004507145.tif 000004
【図２】
2004507145.tif 000005
【図３】
2004507145.tif 000006
【図４】
2004507145.tif 000007
【図５】
2004507145.tif 000008
【図６】
2004507145.tif 000009
【図７】
2004507145.tif 000010
【図８】
2004507145.tif 000011
【図９】
2004507145.tif 000012
【図１０】
2004507145.tif 000013
【図１１】
2004507145.tif 000014
【図１２】
2004507145.tif 000015
【国際公開パンフレット】
2004507145.tif 000016
2004507145.tif 000017
2004507145.tif 000018
2004507145.tif 000019
2004507145.tif 000020
2004507145.tif 000021
2004507145.tif 000022
2004507145.tif 000023
2004507145.tif 000024
2004507145.tif 000025
2004507145.tif 000026
2004507145.tif 000027
2004507145.tif 000028
2004507145.tif 000029
2004507145.tif 000030
2004507145.tif 000031
2004507145.tif 000032
2004507145.tif 000033
2004507145.tif 000034
2004507145.tif 000035
2004507145.tif 000036
2004507145.tif 000037
2004507145.tif 000038
2004507145.tif 000039
2004507145.tif 000040
2004507145.tif 000041
2004507145.tif 000042
2004507145.tif 000043
2004507145.tif 000044
2004507145.tif 000045
2004507145.tif 000046
2004507145.tif 000047
2004507145.tif 000048
2004507145.tif 000049
2004507145.tif 000050
2004507145.tif 000051
2004507145.tif 000052
2004507145.tif 000053
2004507145.tif 000054
2004507145.tif 000055
2004507145.tif 000056
2004507145.tif 000057
2004507145.tif 000058
2004507145.tif 000059
2004507145.tif 000060
2004507145.tif 000061
2004507145.tif 000062
2004507145.tif 000063
【国際公開パンフレット（コレクトバージョン）】
2004507145.tif 000064
【国際調査報告】
2004507145.tif 000065
2004507145.tif 000066
2004507145.tif 000067