(57)【要約】      （修正有）【課題】超大規模集積回路（ＶＬＳＩ）を用いて正則ハフマン符号を実装するための手法を提供する。【解決手段】ＬＶアルゴリズムに従い、オフセットと長さを含むコピー命令で重複データを置き換えるように、データファイルを処理する。その後、ファイルの諸部分に対してハフマン符号を生成する。ハフマン符号は、まず先にリテラル統計量をソートすることなしに、データファイル内のリテラルに対するハフマン符号長を生成する。最大長より長くならないようにハフマン符号長を制約してもよく、ハフマン符号は、許容可能なオーバーフロー確率を与えつつ正規順になるように、改変されてもよい。リテラルとオフセットと長さを、別々に符号化してもよい。これらのデータセットに対する異なる値は、ハフマン符号を生成するのに使われる使用統計量を生成する目的で、限られた個数のビンに割り当てられる。【選択図】図４
2019054532.tif 000002
【特許請求の範囲】
【請求項１】
データファイルを処理し、各リテラルに対して、一つ以上の非重複リテラルでできたリテラル・グループの、複数個のうちの一つの一部、および、一つ以上のリテラルでできたコピー・グループの、複数個のうちの一つとして、フラグを付けることであって、
前記データファイルにおいて、各リテラル・グループの前記一つ以上のリテラルには、一つ以上のリテラルでできた同一グループが先行しておらず、
前記データファイルにおいて、各コピー・グループの前記一つ以上のリテラルには、一つ以上のリテラルでできた同一グループが先行しており、
各コピー・グループは、当該コピー・グループ内のリテラルの数を示す長さと、前記データファイル内で当該各コピー・グループに先行する、一つ以上のリテラルでできた前記同一グループまでのオフセットとの、双方を有しており、
各リテラル・グループは、当該リテラル・グループ内のリテラルの数を示す長さを有することを特徴とする過程と、
前記データファイルの第１部分に含まれる、前記複数のリテラル・グループのうちの第１部分をハフマン符号化して、ハフマン符号化済みリテラル・グループを求めることと、
前記ハフマン符号化済みリテラル・グループを出力ファイルに含めることと、
前記データファイルのうちの、前記データファイルにおいて前記第１部分の後に出現する第２部分にある、前記複数のリテラル・グループのうちの第２部分を、ハフマン符号化せずに前記出力ファイルに含めることと、
を含む、コンピュータ・システムによる、圧縮のための方法。
【請求項２】
前記第１部分と前記第２部分における、コピー・グループに対するリテラル・グループの平均個数を評価することにより、前記データファイルを前記第１部分と前記第２部分に分割することをさらに含む、請求項１の方法。
【請求項３】
前記複数のコピー・グループの前記オフセットをハフマン符号化して、ハフマン符号化済みオフセットを求めることと、
前記ハフマン符号化済みオフセットを前記出力ファイルに含めることと、
前記複数のコピー・グループの前記オフセットの前記ハフマン符号化とは別に、前記複数のコピー・グループの前記長さをハフマン符号化して、ハフマン符号化済み長さを求めることと、
前記ハフマン符号化済み長さを前記出力ファイルに含めることと、
をさらに含む、請求項１もしくは２に記載の方法。
【請求項４】
前記複数のコピー・グループの前記オフセットおよび前記長さの前記ハフマン符号化についてのハフマン符号長をＮビットに制限することをさらに含む、請求項１から３のいずれか１項に記載の方法。
【請求項５】
Ｎが８である、請求項１から４のいずれか１項に記載の方法。
【請求項６】
前記複数のコピー・グループの前記オフセットおよび前記長さの前記ハフマン符号化についての前記ハフマン符号長をＮビットに制限することが、前記長さとオフセットの各データセットに対して、
前記各データセットにおけるデータ語の第１の正則ハフマン符号を生成することであって、前記第１の正則ハフマン符号が各データ語の符号長を含み、前記符号長が順に配列されていることを特徴とする生成と、
Ｎより長いすべての符号長をＮに等しくなるように設定して、第２の正則ハフマン符号を求めることと、
１だけインクリメントされると前記第２の正則ハフマン符号のオーバーフロー確率を０以下にするような、Ｎよりも短いもののうちでは最長の符号長である、ベンチマーク符号を特定することと、
前記ベンチマーク符号よりも長さが短い被調整符号の長さを１だけインクリメントして、第３の正則ハフマン符号を生成することと、
前記第３の正則ハフマン符号により前記データファイルをハフマン符号化することと、
Ｎ以下のハフマン符号でのハフマン符号化を実行するようにプログラムされた超大規模集積回路（ＶＬＳＩ）を用いて、前記オフセットと前記長さをハフマン符号化することと、を実行することをさらに含む、
請求項１から４のいずれか１項に記載の方法。
【請求項７】
前記複数のコピー・グループの前記長さの前記ハフマン符号化についての前記ハフマン符号長を制限することが、１からＭまでの長さを２＊Ｎ個のビンのうちの一つにマッピングすることを含み、Ｍが２＊Ｎより大きい、
請求項１から４のいずれか１項に記載の方法。
【請求項８】
データファイルを処理し、各リテラルに対して、一つ以上の非重複リテラルでできたリテラル・グループの、複数個のうちの一つの一部、および、一つ以上のリテラルでできたコピー・グループの、複数個のうちの一つとして、フラグを付けるよう構成された統計量生成モジュール
を含み、
前記データファイルにおいて、各リテラル・グループの前記一つ以上のリテラルには、一つ以上のリテラルでできた同一グループが先行しておらず、
前記データファイルにおいて、各コピー・グループの前記一つ以上のリテラルには、一つ以上のリテラルでできた同一グループが先行しており、
各コピー・グループは、当該コピー・グループ内のリテラルの数を示す長さと、前記データファイル内で当該各コピー・グループに先行する、一つ以上のリテラルでできた前記同一グループまでのオフセットとの、双方を有しており、
各リテラル・グループは、当該リテラル・グループ内のリテラルの数を示す長さを有する
電子装置。
【請求項９】
前記データファイルの第１部分に含まれる、前記複数のリテラル・グループのうちの第１部分を符号化して、ハフマン符号化済みリテラル・グループを求めることと、
前記ハフマン符号化済みリテラル・グループを出力ファイルに含めることと、
前記データファイルのうちの、前記データファイルにおいて前記第１部分の後に出現する第２部分にある、前記複数のリテラル・グループのうちの第２部分を、ハフマン符号化せずに前記出力ファイルに含める
ように構成されたハフマン符号化モジュール
をさらに含む請求項８に記載の電子装置。
【請求項１０】
前記ハフマン符号化モジュールは、
前記第１部分と前記第２部分における、コピー・グループに対するリテラル・グループの平均個数を評価することにより、前記データファイルを前記第１部分と前記第２部分に分割する
ようにさらに構成される請求項９に記載の電子装置。
【請求項１１】
前記ハフマン符号化モジュールは、
複数のコピー・グループのオフセットを符号化して、ハフマン符号化済みオフセットを求め、
前記ハフマン符号化済みオフセットを前記出力ファイルに含める
ようにさらに構成される請求項９に記載の電子装置。
【請求項１２】
前記複数のコピー・グループの前記オフセットの前記ハフマン符号化とは別に、前記複数のコピー・グループの前記長さをハフマン符号化して、ハフマン符号化済み長さを求め、
前記ハフマン符号化済み長さを前記出力ファイルに含める
ように構成された長さモジュール
をさらに含む請求項１１に記載の電子装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データのロスレス圧縮のためのシステムと方法に関する。
【背景技術】
【０００２】
ハフマン符号は、ロスレスなデータ圧縮に使われるエントロピー符号化アルゴリズムである（D. A. Huffman, “A method for the construction of minimum-redundancy codes” Proc. IRE 40 (9). pp. 1098-1101. 1952を参照）。ハフマン符号は、（ファイル内の文字などの）ソース・リテラルを符号化するための可変長符号テーブルを使うことを意味し、その可変長符号テーブルとは、ソース・リテラルの取り得るそれぞれの値についての推定出現確率に基づく、特定の方法で導出されたものである。ハフマン符号は、各リテラルについての表現を選ぶための特定の方法を用いており、結果として、最もよくあるソース・リテラルを、それよりありふれていないソース・リテラルに使われるものよりも短いビット列を用いて表現する、接頭符号になる（ときには「接頭辞不要（prefix-free）符号」とも呼ばれるが、これはつまり、ある特定のリテラルを表すビット列は、決して、他のどのリテラルを表すビット列の接頭辞にもならない、ということである）。ハフマンは、次のような種類の――つまり、実際のリテラル頻度が、符号を作成するのに使われたリテラル頻度に一致する場合には、個々のソース・リテラルから一意なビット列への他のいかなる写像も、より小さな平均出力サイズをもたらすことはない、といったような――最も効率的な圧縮方法を、設計することができた。ハフマン・アルゴリズムの擬似コードを以下に示す。
【０００３】
［アルゴリズム１：二元ハフマン符号を計算する］
入力：Ｎ組の（リテラル，カウント／確率）というペアの集合
出力：Ｎ組の（リテラル，ハフマン符号（hufcode））というペアの集合
１  カウントの降順でリテラル全体をソートする。
２  確率が低い方から二つのリテラルを選択し、各々に対して、それぞれ、０および１というビットを割り当てる。
３  選択したリテラルを、それらのカウントを足し合わせる合成リテラルで置き換え、それを順序付けしなおす。
４  一つよりも多くのリテラルが残っている間は、６までのステップを行う。
５    確率が低い方から二つのリテラルを選択し、０と１をそれぞれ付加する。
６    選択したリテラルを、それらのカウントを足し合わせる合成リテラルで置き換え、それを順序付けしなおす。
７  各リテラルのハフマン符号が、総ビットの連結によって与えられる。
【０００４】
上記のハフマン木は、符号化スキームの実装に、二つの決定的な非効率性を導入してしまう。第一に、木の各ノードは、自分の子ノードへの参照、または、自分が表すリテラルのいずれかを、格納せねばならない。これはメモリ使用の点において高くつくし、もし、一回しか出現しないリテラルがソース・データの大部分を占めていれば、符号木の全体的な大きさが、符号化されたデータ全体のうちの著しい量を占めることになりかねない。第二に、木をトラバースすることは、符号化されたデータの各ビットが読み込まれるにつれてメモリ内で構造体のあちこちをランダムにジャンプするアルゴリズムを必要とするため、コンピュータでの計算上、高くつく。
【０００５】
正則（canonical）ハフマン符号は、明快な標準化された形式の符号を生成することで、これら二つの問題に対処している。つまり、ある一定の長さのすべての符号には、値が連続的に割り当てられるのである。これは、伸長のために符号木の構造体を格納する代わりに、符号の長さだけが必要であることを意味しており、符号化されたデータのサイズを減らすことになる。しかも、符号が連続的であるので、コンピュータ計算上の効率が良くなるように復号アルゴリズムを劇的に簡素化することができる。
【０００６】
ハフマン符号長（Ｌで示される）により昇順にソートされたリテラルのリストが与えられると、以下の擬似コードが正則ハフマン符号一覧を印字するだろう。
【０００７】
［アルゴリズム２：正則ハフマン符号を、そのビット長を通じて計算する］
2019054532.tif 000003
【０００８】
ソフトウェア圧縮は非常によく理解されているし、ＧＺＩＰのようなプログラムのためのソースコードは、パブリック・ドメインでたやすく入手することができる。ＧＺＩＰ圧縮がデフレート・アルゴリズムとハフマン符号に基づいているということを考えると（DEFLATE Compressed Data Format Specification version 1.3. IETF. May 1996. p. 1. sec. Abstract. RFC 1951.  ２０１２年１１月１１日に取得）、圧縮を実装するためのアルゴリズムは、広帯域幅アプリケーション用にハードウェアで実行するには比較的複雑である。圧縮の背後にある考えは、データ・ストリームの後ろの方では、データ・ストリームの前の方に現れるリテラルに対するコピー命令を使う、というものである。このようであるため、圧縮の実装はすべて、検索履歴バッファと、コピー命令に使える最長の長さを判定するための、ある種の長さ比較関数とを必要とする。以前の履歴における検索マッチングを実装するための一つの方法は、ハッシュ関数を実装することであり、そのハッシュ関数は可変長の列を固定値に写像し、その固定値は、圧縮中のデータ・ストリームを比較するのに使える。データは、レンペル・ジブ（Lempel-Ziv）アルゴリズムまたはそれに匹敵するアルゴリズム（Ziv, J.; Lempel, A. (1978). "Compression of individual sequences via variable-rate coding". IEEE Transactions on Information Theory 24 (5): 530）にしたがってコピー命令またはリテラル命令を生成するために、ハッシュ化されて比較される。圧縮すべきデータの統計量が、一旦、集められると、それらはそれからハフマン符号化され、そして、送出するために圧縮される。
【０００９】
上記で概要を示したとおり、ハフマン符号は、ハードウェアで実装するのに簡単なアルゴリズムというわけではない。本明細書で開示するシステムと方法は、超大規模集積回路（ＶＬＳＩ）を用いて正則ハフマン符号を実装するための、改良された手法を提供する。
【００１０】
本発明の利点が容易に理解されるようにするため、簡単に上述した本発明についての更に詳細な記述が、添付の図面に図示された具体的な実施形態への参照により与えられるだろう。これらの図面は、単に本発明の典型的実施形態を図示するに過ぎず、したがって、本発明の範囲を限定していると考えられるべきではない、ということを理解しつつも、本発明は、下記の付属の図面を使って、追加的な具体性および詳細ととともに、記述され、かつ、説明されるであろう。
【図面の簡単な説明】
【００１１】
【図１】本発明の諸実施形態による方法を実装するのに適したコンピュータ・システムの模式的ブロック図である。
【図２】本発明の一実施形態による、ハフマン符号化のＶＬＳＩでの効率的な実装のための構成要素の、模式的ブロック図である。
【図３】本発明の一実施形態によって、入力ファイルに対してソートを行うと同時にハフマン符号長を生成する方法の、プロセス流れ図である。
【図４】本発明の一実施形態によって、正則ハフマン・ビット長を、指定された長さに正規化する方法の、プロセス流れ図である。
【図５】本発明の一実施形態によってデータファイルをハフマン符号化する方法の、プロセス流れ図である。
【発明を実施するための形態】
【００１２】
本明細書の図面に一般的に記述され、図示されているような、本発明の構成要素を、多種多様な異なる構成で配置したり設計したりすることができるだろう、ということは、すぐに理解されるだろう。よって、図面に表されているような、本発明の実施形態についての以下のより詳細な記述は、請求項に記載されているような本発明の範囲を限定することを意図したものではなく、ただ、本発明によって現在のところ想定されている実施形態の、ある種の例を代表するに過ぎない。現在記述されている実施形態は、図面を参照することで最も良く理解されるだろうし、図面においては、全体を通じて、類似の部分が類似の番号によって指し示される。
【００１３】
本発明は、現在の最新技術水準に応じて、とりわけ、現在利用可能な装置や方法によっては未だ完全に解決されていない、本技術分野における問題および必要性に応じて、開発されてきた。したがって、本発明は、ＶＬＳＩでの実装に十分に適したハフマン符号化を実行する装置と方法を提供するために、開発された。
【００１４】
正則ハフマン符号を用いると、伸長側がハフマン木を再構築するのにはハフマン符号長を送信すれば十分であり、さらには、背景セクションで論じたように構築アルゴリズムを容易に実装することができる、ということは、よく理解されている。以下のシステムと方法は、本節において、ハフマン符号長を計算するうえでの、改良された実装を提供する。特に、開示されるシステムと方法には、二つの態様がある。第一の態様は、超大規模集積（ＶＬＳＩ）設計を用いてより容易に実装されるように、ハフマン・アルゴリズムを変形する。第二の態様は、（ハフマン符号長を送信するためのビット数を制限するように）最大ハフマン長を制限するための、ハードウェアで受け入れ可能なアルゴリズムを導き出す。
【００１５】
本発明による実施形態は、装置、方法、またはコンピュータ・プログラム製品として、実施され得る。したがって、本発明は、本明細書においてはどれも「モジュール」または「システム」と一般的に呼ぶことのある、完全にハードウェア的な実施形態、完全にソフトウェア的な実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、または、ソフトウェアの態様とハードウェアの態様とを結合する実施形態、といった形をとり得る。さらに、本発明は、媒体内に具現化されたコンピュータ使用可能なプログラム・コードを有する任意の有形な表現媒体に具現化された、コンピュータ・プログラム製品の形をとることもある。
【００１６】
一つ以上のコンピュータ使用可能またはコンピュータ読み取り可能な媒体の、任意の組み合わせが利用されてもよく、これには非一時的な媒体も含む。例えば、コンピュータ読み取り可能な媒体が、可搬型コンピュータ・ディスケット、ハードディスク、ランダムアクセスメモリ（ＲＡＭ）装置、リードオンリーメモリ（ＲＯＭ）装置、イレーサブル・プログラマブル・リードオンリーメモリ（ＥＰＲＯＭまたはフラッシュメモリ）装置、可搬型コンパクトディスク・リードオンリーメモリ（ＣＤＲＯＭ）、光学式記憶装置、および磁気記憶装置のうちの、一つ以上を含んでもよい。選択された実施形態では、命令実行のシステム、装置、もしくは機器によって使うために、または、それらと接続して使うために、プログラムを含み、格納し、通信し、伝播し、または輸送することのできる、任意の非一時的な媒体を、コンピュータ読み取り可能な媒体が含んでいてもよい。
【００１７】
ＪａｖａやＳｍａｌｌｔａｌｋやＣ＋＋などのようなオブジェクト指向プログラミング言語、および、「Ｃ」プログラミング言語または類似のプログラミング言語のような従来の手続き型プログラミング言語を含む、一つ以上のプログラミング言語の任意の組み合わせで、本発明の演算を実行するためのコンピュータ・プログラム・コードが書かれていてもよい。そのプログラム・コードは、スタンドアロンのソフトウェア・パッケージとして全てコンピュータ・システム上で実行してもよいし、スタンドアロンのハードウェア・ユニット上で実行してもよいし、部分的に、そのコンピュータから幾らかの距離だけ離れたリモート・コンピュータ上で実行してもよいし、あるいは、全面的に、リモートのコンピュータまたはサーバ上で実行してもよい。後者のシナリオにおいて、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）もしくはワイド・エリア・ネットワーク（ＷＡＮ）を含む任意の種類のネットワークを介して、上記コンピュータに接続されていてもよく、または、その接続が（例えば、インターネット・サービス・プロバイダを使って、インターネットを介して）外部のコンピュータに対してなされていてもよい。
【００１８】
本発明の実施形態による方法や装置（システム）やコンピュータ・プログラム製品の、フローチャート図面および／またはブロック図を参照して、以下で本発明を説明する。フローチャート図面および／またはブロック図の各ブロック、ならびに、フローチャート図面および／またはブロック図のブロック同士の組み合わせを、コンピュータ・プログラムの命令またはコードによって実装することができる、ということが理解されるだろう。これらのコンピュータ・プログラム命令は、汎用コンピュータ、専用コンピュータ、またはその他のプログラマブルなデータ処理装置の、プロセッサに供給されてマシンを作り出してもよく、するとその結果、それらの命令、つまり、コンピュータまたはその他のプログラマブルなデータ処理装置のプロセッサを介して実行される命令が、フローチャートおよび／またはブロック図の一つまたは複数のブロックにおいて明細が規定されている機能／行為を実施する手段を、創造する。
【００１９】
また、これらのコンピュータ・プログラム命令は、特定の方法で機能するようにコンピュータまたはその他のプログラマブルなデータ処理装置に命令することのできる、非一時的なコンピュータ読み取り可能な媒体に格納されていてもよく、するとその結果、コンピュータ読み取り可能な媒体に格納されている命令は、フローチャートおよび／またはブロック図の一つまたは複数のブロックにおいて明細が規定されている機能／行為を実施する命令手段を含む製造品を、作り出す。
【００２０】
また、フローチャートおよび／またはブロック図の一つまたは複数のブロックにおいて明細が規定されている機能／行為を実施するプロセスを、コンピュータ上またはその他のプログラマブルな装置上で実行される命令が提供するように、コンピュータ・プログラム命令が、コンピュータまたはその他のプログラマブルなデータ処理装置にロードされて、コンピュータで実装されたプロセスを作り出すために一連の演算ステップをコンピュータ上またはその他のプログラマブルな装置上で実行させてもよい。
【００２１】
図１は、例示的コンピューティング装置１００を示すブロック図である。コンピューティング装置１００は、本明細書で論じる手続きなどの、種々の手続きを実行するのに使われてもよい。コンピューティング装置１００は、サーバ、クライアント、または任意の他のコンピューティング・エンティティとして、機能することができる。コンピューティング装置は、本明細書で論じるように種々の監視機能を実行することができ、本明細書に記述されるアプリケーション・プログラムなどの、一つ以上のアプリケーション・プログラムを実行することができる。コンピューティング装置１００は、デスクトップ型コンピュータ、ノートブック型コンピュータ、サーバ・コンピュータ、携帯型コンピュータ、タブレット型コンピュータなどの、多種多様なコンピューティング装置のうちの、いずれとすることもできる。
【００２２】
コンピューティング装置１００は、一つ以上のプロセッサ１０２と、一つ以上のメモリ装置１０４と、一つ以上のインタフェイス１０６と、一つ以上の大容量記憶装置１０８と、一つ以上の入出力（Ｉ／Ｏ）装置１１０と、ディスプレイ装置１３０とを含み、これらすべてがバス１１２に結合されている。一つ以上のプロセッサ１０２は、一つ以上のメモリ装置１０４および／または一つ以上の大容量記憶装置１０８に格納されている命令を実行する、一つ以上のプロセッサまたはコントローラを含む。また、一つ以上のプロセッサ１０２は、キャッシュメモリなどの、様々な種類のコンピュータ読み取り可能な媒体を含んでいてもよい。
【００２３】
一つ以上のメモリ装置１０４は、揮発性メモリ（例えば、ランダムアクセスメモリ（ＲＡＭ）１１４）および／または不揮発性メモリ（例えば、リードオンリーメモリ（ＲＯＭ）１１６）などの、様々なコンピュータ読み取り可能な媒体を含む。また、一つ以上のメモリ装置１０４は、フラッシュメモリなどの書き換え可能ＲＯＭを含んでいてもよい。
【００２４】
一つ以上の大容量記憶装置１０８は、磁気テープ、磁気ディスク、光学式ディスク、ソリッドステート・メモリ（例えば、フラッシュメモリ）などの、様々なコンピュータ読み取り可能な媒体を含む。図１に示すとおり、ある特定の大容量記憶装置は、ハードディスクドライブ１２４である。様々なコンピュータ読み取り可能な媒体からの読み取り、および／または、そこへの書き込みを可能とするため、一つ以上の大容量記憶装置１０８には様々なドライブも含まれていてよい。一つ以上の大容量記憶装置１０８は、リムーバブルな媒体１２６および／またはリムーバブルでない媒体を含む。
【００２５】
一つ以上のＩ／Ｏ装置１１０は、データおよび／または他の情報を、コンピューティング装置１００に入力したり、あるいはコンピューティング装置１００から取り出したりすることを可能とする、様々な装置を含む。例示的な一つ以上のＩ／Ｏ装置１１０は、カーソル制御装置、キーボード、キーパッド、マイク、モニタまたは他のディスプレイ装置、スピーカ、プリンタ、ネットワーク・インタフェイス・カード、モデム、レンズ、ＣＣＤまたは他の画像キャプチャ装置、などを含む。
【００２６】
ディスプレイ装置１３０は、コンピューティング装置１００の一人以上のユーザに対して情報を表示することのできる、任意の種類の装置を含む。ディスプレイ装置１３０の例は、モニタ、ディスプレイ端末、ビデオ投影装置などを含む。
【００２７】
一つ以上のインタフェイス１０６は、コンピューティング装置１００が他のシステム、装置、またはコンピューティング環境と相互作用することを可能にする、様々なインタフェイスを含む。例示的な一つ以上のインタフェイス１０６は、ローカル・エリア・ネットワーク（ＬＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、無線ネットワーク、およびインターネットに対するインタフェイスなどの、任意の個数の異なるネットワーク・インタフェイス１２０を含む。別の一つ以上のインタフェイスは、ユーザ・インタフェイス１１８と周辺機器インタフェイス１２２とを含む。一つ以上のインタフェイス１０６が一つ以上のユーザ・インタフェイス要素１１８を含むこともあり得る。一つ以上のインタフェイス１０６が、プリンタやポインティング・デバイス（マウスやトラックパッドなど）やキーボードなどに対するインタフェイスのような、一つ以上の周辺機器インタフェイスを含むこともあり得る。
【００２８】
バス１１２は、一つ以上のプロセッサ１０２と一つ以上のメモリ装置１０４と一つ以上のインタフェイス１０６と一つ以上の大容量記憶装置１０８と一つ以上のＩ／Ｏ装置１１０が互いに通信することを可能とし、また、これらが、バス１１２に結合された他の装置または構成要素と通信することも可能とする。バス１１２は、システム・バス、ＰＣＩバス、ＩＥＥＥ  １３９４バス、ＵＳＢバスなどの、数種類のバス構造のうちの、一つ以上を表している。
【００２９】
例示の目的のため、プログラムおよびその他の実行可能なプログラム・コンポーネントは、本明細書においては個別のブロックとして示されている。もっとも、そうしたプログラムやコンポーネントは、様々な時点において、コンピューティング装置１００のうちの異なる記憶コンポーネントに存在し得るし、一つ以上のプロセッサ１０２により実行されるのだ、ということは理解される。あるいは、本明細書に記述されるシステムと手続きを、ハードウェアで実装することもでき、または、ハードウェア、ソフトウェア、および／もしくはファームウェアの組み合わせで実装することもできる。例えば、本明細書に記述されるシステムと手続きのうちの一つ以上を実行するように、一つ以上の特定用途向け集積回路（ＡＳＩＣ）をプログラムすることができる。
【００３０】
元々のハフマン・アルゴリズムには、二つのソート操作が存在する。第一に、リテラルがカウントの降順にソートされ、その後、段階的に、最少の二つのものの合算カウントに基づいてメッセージが並べなおされる。これは、各々が専用のハードウェア設計を必要とするので、望ましくない。等価的には、確率が低い方から二つのメッセージを段階的に特定するので十分であり、するとその結果、双方のソート操作が排除される。さらに、いくつかのメッセージはカウントがゼロかもしれないという、隠れたシナリオがある。これらのメッセージは、ハフマン符号から除外する必要がある。自然な方法は、まず、それらの存在しないメッセージを除外して、それから、ハフマン・アルゴリズムを実行することである。しかし、これは除外のための余計なステップを必要とするし、元のリテラル列は（任意に）短縮される（それを記憶するための専用メモリを必要とする）。
【００３１】
いくつかの実施形態において、より簡潔で均質な方法は、最小の二つのカウントを特定する際に、ゼロ・カウントを選択するのを避けることである。擬似コードを以下に示す。
【００３２】
［アルゴリズム３：ハフマン符号長を計算する］
2019054532.tif 000004
【００３３】
なおここで、Ｓｉはリテラルであり、ＰｉはリテラルＳｉのカウント（例えば確率）であり、ＬｉはリテラルＳｉのビット長であり、Ｉｉは、一つずつ作成される、Ｌｉビットの符号に対するマップ値である。それぞれの反復において、二つのカウント値が併合され、それらのマップ値も同様に併合されて、お互いに等しくなるよう設定される。例えば、１回が、０と１という値を作り出す可能性がある。次の回では、併合されたカウントおよびマップが、別のリテラルについての、または、併合済みの値の他の一組についての、カウントおよびマップ値と、併合されることがある。それぞれの反復においては、最小の二つのカウントを有する、リテラルまたは併合済みの値に対して、もう一つのビットが割り当てられる。実質的には、左から開始して、値同士を併合しつつ前進する。併合の後、マップ値Ｉｉは、木の完全な枝を表している。マップ値Ｉｉに対するビット長がインクリメントされるときは、その値を有するすべての符号長のビット長が、インクリメントされる。
【００３４】
最適なハフマン符号長を計算したら、長さ制限の執行に取り掛かる。Ｌを、許される最大の長さとする。まず、次の長さ制限を確認して執行する。
Ｉｆ  Ｌｉ＞Ｌ，  ｔｈｅｎ  ｓｅｔ  Ｌｉ←Ｌ，  ｉ＝０，１，２，……，Ｎ−１
【００３５】
２Ｌ倍に変倍したオーバーフロー確率を、Ｐｏによって数学的に示す。
2019054532.tif 000005
【００３６】
正のオーバーフロー確率は、結果として生じるハフマン長が無効であって、いくつかの長さを増すことによってオーバーフロー確率が非正となるように（ゼロが最適である）修正する必要がある、ということを示す。
【００３７】
その後、第一には長さの値を増してゆくことにより、また、第二には（長さ同士が等しい場合に）アルファベット順位を増してゆくことにより、長さＬｉ（ただしｉ＝０，１，２，……，Ｎ−１）をソートする。これにより直ちに、正則ハフマン符号を構築することが可能となる（アルゴリズム２）。最大の長さがＬ＝Ｏ（ｌｏｇ  Ｎ）を満たすことに注意すると、以下によって、ソートをより効率的に実装することができる。
【００３８】
［アルゴリズム４：昇順でのハフマン長のソート］
2019054532.tif 000006
【００３９】
L. L. Larmore and D. S. Hirschberg, “A fast algorithm for optimal length-limited Huffman codes,” Journal of the Association for Computing Machinery, (37)3, pp. 464-473, July 1990 において、その著者らは、Ｏ（ＬＮ）の時間計算量とＯ（Ｎ）の空間計算量で最適な長さ制限ハフマン符号を計算する高速なアルゴリズムを提案した。しかし、そのアルゴリズムは、依然として、ハードウェアで実装するには複雑すぎる。我々は次に、（正則ハフマン符号を容易に構築することができるように）ソートされた順序を維持しつつ、Ｐｏを非正に帰着させるための、準最適なアルゴリズムを提案する。その狙いは、最新の長さを１だけ増やすことで、Ｐｏを抑えるのに（ちょうど）十分なだけの確率を解放するような、最新の長さを見つけることである。アルゴリズム的な手続きを、図４に関して以下に示す。
【００４０】
［アルゴリズム５：長さが制限されたハフマン符号の準最適な構築］
2019054532.tif 000007
【００４１】
上記アルゴリズム５の第２部分では、増加させた長さ
2019054532.tif 000008
のリテラルを、同じ長さになるリテラル同士の間で適切なアルファベット順を遵守させるように、挿入する。アルゴリズム５は、オーバーフロー確率を抑制し、それと同時にリテラルを順序どおりに保つので、対応する正則ハフマン符号を計算するために、前の節でのアルゴリズム２が容易に活用される。
【００４２】
図２を参照すると、上記アルゴリズムは、個別の電子的コンポーネントまたはソフトウェアモジュールのいずれかとしての、図示されたモジュールを使って、組み込まれてもよい。上述のとおり、本明細書で記述する方法は、ＶＬＳＩ設計技法を用いて容易に実装される。
【００４３】
入力ファイル２０２が、コピー／リテラル命令生成器２０４に入力されてもよい。コピー／リテラル命令は、ＬＺ７７（Lempel and Ziv）アルゴリズムまたはＬＺ７８アルゴリズムなどの従来の重複文字列削除アルゴリズムにしたがって、生成されてもよい。本技術分野で知られるように、重複文字列削除は、ファイルのリテラルを処理する。もし、（一つ以上の）リテラルの列に先行して、ファイル内には同一のリテラル列があると判明したら、そのリテラル列は、それがコピーであることを示すフラグと、その列の中のリテラルの数を示す長さと、同一のリテラル列の始まり（または終わり）までファイル内でどれほど遡るのかを示すオフセットと、に置き換えられる。ファイル内において同一リテラルが先行していないようなリテラルには、「リテラル」フラグのような違う方法で、フラグを付けてもよい。いくつかの例では、リテラルには１というビットでフラグが付けられて、コピーには０というビットでフラグが付けられるか、あるいは、その逆である。
【００４４】
コピー／リテラル命令を含むように、コピー／リテラル命令生成器２０４により処理された入力ファイル２０２（「処理済みファイル」）は、統計量生成器２０６へ入力されてもよい。統計量生成器は、処理済みファイル内で表現されている各リテラルの、事例の数を数える。いくつかの実施形態では、異なる種類のデータに対して、使用統計量の別々の組を生成してもよい。例えば、使用統計量が、各リテラル命令に対して測定されてもよい（例えば、リテラルとしてフラグが付けられた各リテラルの、出現回数を数える）。使用統計量が、各コピー命令に対して測定されてもよい。使用統計量の別々の組が、長さの値に対して測定される（例えば、表現された各々の長さの値の、出現回数を数える）とともに、コピー命令のオフセット値に対して測定されてもよい（例えば、表現された各オフセット値の、出現回数を数える）。
【００４５】
例えば、ＦｌａｇＲｕｎとオフセット（Ｏｆｆｓｅｔ）と長さ（Ｌｅｎｇｔｈ）とリテラル（Ｌｉｔｅｒａｌ）からなるＬＺ命令のために、統計量が集められてもよい。ＦｌａｇＲｕｎ命令は、後続のバイトのうちのＮバイトがリテラルとして扱われるべきである、ということを示す命令であってもよく、それにより、各リテラルに「リテラル」とフラグを付ける必要性をなくすものである。ＦｌａｇＲｕｎ命令は、２０１４年５月９日に出願され、IMPROVED DEFLATE COMPRESSION ALGORITHMと題された米国出願番号１４／２７４，３６４号に記述されたようにして、割り当てられてもよい。
【００４６】
動的ハフマン符号化のために、統計量を多くの異なるビンに集めることができる。いくつかの実施形態では、各ＬＺ命令について集められる統計量は、最大で１６個のビンに制限される。
【００４７】
データ・ストリームを圧縮するのに使われる動的ハフマン符号を生成するために、統計量が集められる。動的ハフマン符号は、図２に示すような二段階エンジンを使って生成される。第１のエンジン（ハフマン・ビット長エンジン２０８）は、伸長用の圧縮ヘッダの一部として送られることになる、ハフマン・ビット長を生成する。第２のエンジン（ハフマン符号生成エンジン）は、たとえ動的ハフマン符号化のために木の深さがＮビットより長くなり得るとしても、ハフマン木符号長がＮビットより長くならない（例えば、７、１５、３１、または何らかの他の値となる）ように、ハフマン木符号長を強制する。
【００４８】
ハフマン符号生成エンジン２１０により出力される正則ハフマン符号は、処理済みファイルとともにハフマン符号化器２１２へと入力されてもよく、ハフマン符号化器２１２は、その正則ハフマン符号を用いて処理済みファイルのハフマン符号化を行って、圧縮した出力ファイルを作り出す。
【００４９】
ハフマン・ビット長エンジン２０８は、図３の方法３００を実行してもよい。正則ハフマン・ビット長を生成するための従来の手法は、データをすべてソートすることである。方法３００は、最初にソートすることを必要とはしない。よって、ハフマン・ビット長が生成されている間、それぞれの反復においてノード群に対して最小のものを見つけるだけのものへと、ハードウェアが簡素化され得る。フローチャートで示唆されているマップ値は、ハフマン符号化されている最中のシンボルを指している。シンボルは、リテラルか、オフセットか、ｆｌａｇＲｕｎか、長さであり得る。カウントは、ハフマン符号化すべきシンボルの頻度カウントを指している。
【００５０】
方法３００は、データセット（リテラル、ｆｌａｇＲｕｎ、オフセット、または長さ）の各シンボルＳ（０）からＳ（Ｎ）について、カウントＰ（０）からＰ（Ｎ）をそれぞれ求めること３０２を、含んでもよい。各カウントＰ（ｉ）は、データセット内でのシンボルＳ（ｉ）の出現数を表す。各シンボルＳ（０）からＳ（Ｎ）についての、それぞれのビット長Ｌ（０）からＬ（Ｎ）は、ゼロに初期化３０４されてもよく、無効なエントリは除かれてもよい。無効なエントリとは、対応するカウントＰ（ｉ）がゼロに等しいシンボルＳ（ｉ）のことであってもよい。方法３００の残りの部分では、考慮されるシンボルＳ（０）からＳ（Ｎ）が、有効なもののみを、すなわち、非ゼロのカウントＰ（０）からＰ（Ｎ）を有するもののみを、含むのであってもよい。同様に、各シンボルＳ（０）からＳ（Ｎ）についてのそれぞれのマップ値Ｉ（０）からＩ（Ｎ）が、初期化３０６されてもよい。マップ値Ｉ（０）からＩ（Ｎ）を初期化することが、ｉ＝０からＮとして、各マップ値Ｉ（ｉ）をｉに等しくなるよう設定することを含んでいてもよい。
【００５１】
方法３００は、その後、小さい方から二つの対応するカウントＰ（ａ）とＰ（ｂ）を有する、二つのシンボルＳ（ａ）とＳ（ｂ）を見つけること３０８を含んでもよい。これらのカウントの和Ｐｔ＝Ｐ（ａ）＋Ｐ（ｂ）が、その後、確定３１０されてもよい。シンボルＳ（ａ）とＳ（ｂ）のうちで、マップ値Ｉ（ａ）、Ｉ（ｂ）が小さい方のシンボルＳ（ｍｉｎ）も、特定３１２されてもよい。小さい方のマップ値に対応するカウントＰ（ｍｉｎ）が、カウントの和（Ｐｔ）に等しくなるよう設定３１４されてもよい。シンボルＳ（ａ）、Ｓ（ｂ）のうちで、マップ値Ｉ（ａ）、Ｉ（ｂ）が大きい方のシンボルＳ（ｍａｘ）のカウントＰ（ｍａｘ）が、ゼロに等しくなるように設定３１６されてもよい。マップ値Ｉ（ａ）とＩ（ｂ）が双方とも小さい方のマップ値に等しくなるように設定３１８されてもよく、すなわち、Ｉ（ｍａｘ）がＩ（ｍｉｎ）と等しくなるように設定されてもよい。本実施形態では、双方のカウントＰ（ａ）とＰ（ｂ）についての双方のマップ値Ｉ（ａ）とＩ（ｂ）が、小さい方のマップ値に等しくなるように設定されるが、他の実施形態では、Ｉ（ａ）とＩ（ｂ）が互いに等しくなる限りは、Ｉ（ａ）とＩ（ｂ）をそれと等しくなるように設定する対象のマップ値は、いかなる方法で選ばれたいずれのマップ値であってもよい。同様に、どのマップ値が選ばれようとも、選択されたマップ値Ｉ（ｉ）に対応するカウントＰ（ｉ）は、Ｐｔに等しくなるように設定されてよい。
【００５２】
双方のシンボルＳ（ａ）とＳ（ｂ）に対応するビット長Ｌ（ａ）とＬ（ｂ）が、１だけインクリメント３２０されてもよい。後続の反復においては、カウントＰ（ａ）とＰ（ｂ）のうちの一方または双方が、以前に処理されたことのある一つ以上のシンボルに対応することがある。したがって、ステップ３０８からステップ３２２の後続の反復の際には、マップ値Ｉ（ａ）またはＩ（ｂ）のいずれかに合致するマップ値Ｉ（ｉ）を有するすべてのシンボルＳ（ｉ）のビット長Ｌ（ｉ）が、インクリメント３２０されることもある。
【００５３】
その後、方法３００は、カウントＰ（０）からＰ（Ｎ）のすべてがゼロに等しいか否かを判定すること３２２を含んでもよい。もしそうでなければ、方法はステップ３０８で続行する。もしそうであれば、方法３００は終了してもよい。いくつかの実施形態では、すべてのカウントがゼロであるか否かを判定するのではなく、むしろ、ステップ３２２が、すべての非ゼロのカウントが処理済みか否かを判定するためのカウンタを評価することを含んでいてもよく、そのカウンタとは、ステップ３０８からステップ３２２の反復のたびにインクリメントされるものであるか、または、非ゼロのカウントの個数に初期化されて、ステップ３０８からステップ３２２の反復のたびにデクリメントされるものである。
【００５４】
方法３００によって決定されたビット長Ｌ（０）からＬ（Ｎ）は、それから、正則順にソートされてもよく、また、データファイルを伸長するための伸長エンジンによる使用に備えて、圧縮ファイルのヘッダとして格納されてもよい。ビット長Ｌ（０）からＬ（Ｎ）は、正則ハフマン符号を用いた従来のハフマン符号化によってデータファイルを圧縮するためにも、使われる。
【００５５】
方法３００により決定されたビット長Ｌ（０）からＬ（Ｎ）は、その後、ビット長の長さを、ある固定値Ｌｍａｘに制限するために、さらに処理されてもよい。例えば、Ｌｍａｘは７ビットに等しくてもよい
【００５６】
図４は、ハフマン符号の長さを制限するための例示的方法４００を示す。方法４００は、長さの制限なしにハフマン符号を構築すること４０２と、そのハフマン符号を正則順にソートすること４０４を含んでもよく、例えば、方法３００を用いて生成とソートを同時に行うこと、または、別々のステップで符号を生成してソートする従来の手法などを、含んでもよい。
【００５７】
Ｌｍａｘより大きいビット長は、Ｌｍａｘへと変換４０６される。例えば、Ｌｍａｘ（例えば７）より大きい元の値を有する各ビット長Ｌ（ｉ）は、７に等しくなるように設定されてもよい（Ｌ（ｉ）＝Ｌｍａｘ）。
【００５８】
ステップ４０６で制限されたビット長Ｌ（０）からＬ（Ｎ）に対するオーバーフロー確率が、その後、計算４０８されてもよい。オーバーフロー確率Ｐｏは、
2019054532.tif 000009
のように計算されてもよい。
【００５９】
インクリメントされるとオーバーフロー確率をゼロ未満に変化させるような長さＬｍｉｎを、その後、見つけてもよい４１０。上述のとおり、正のオーバーフロー確率は、ハフマン符号が無効であることを示す。とりわけ、Ｌｍｉｎは、１だけインクリメントされるとオーバーフロー確率を正から０以下へと変化させる、最大のビット長Ｌ（ｉ）であってもよい。２番目のビット長Ｌ（ｊ）＝Ｌｍｉｎ−１が、その後、インクリメント４１２されてもよい。ある種の例では、同じ長さの複数のビット長Ｌ（ｉ）が存在し得る。この場合、同じ長さのビット長同士は、バイト長のリストでのアルファベット順に配列されていてもよい。したがって、インクリメントされる、２番目のビット長Ｌ（ｊ）＝Ｌｍｉｎ−１は、Ｌｍｉｎ−１に等しい最後のビット長として、選択されることがある。
【００６０】
上述のとおり、正規順では、同じ長さのビット長同士がアルファベット順に順序づけられる。したがって、方法４００は、Ｌ（ｊ）がもはや正規順にはなっていないのか否かを評価すること４１４を含んでもよい。もし、Ｌ（ｊ）が正規順にはなっていないと判明４１６したら、これを右へ移動４１８してもよい。例えば、インクリメントする前のビット長が、Ｌ（‘Ｂ’）＝４、Ｌ（‘Ｅ’）＝４、Ｌ（‘Ａ’）＝５という順になっているとする。もし、Ｌ（‘Ｅ’）が５にインクリメントされると、順序は、今度は、Ｌ（‘Ｂ’）＝４、Ｌ（‘Ｅ’）＝５、Ｌ（‘Ａ’）＝５となるだろう。もはやＬ（‘Ｅ’）とＬ（‘Ａ’）は、正規順になっていない。よって、順序が今度はＬ（‘Ｂ’）＝４、Ｌ（‘Ａ’）＝５、Ｌ（‘Ｅ’）＝５となるようにＬ（‘Ｅ’）を右へ移動することを、右移動４１８が含んでいてもよい。右移動は、インクリメントされたビット長Ｌ（ｊ）が正規順になるまで続き得る。
【００６１】
正規順に順序づけられたビット長Ｌ（０）からＬ（Ｎ）は、その後、例えばアルゴリズム２に従うなどして正しい符号を作成４２０するのに使われてもよい。
【００６２】
図５を参照すると、上述のとおり、データセット（ｆｌａｇｒｕｎ、オフセット、長さ、リテラル）のシンボルについての動的ハフマン符号を生成するときには、使用統計量の蓄積され得るビンの数が制限されてもよい。このことを容易にするために、バイトとして符号化されるシンボルが、ＭＳＢＨｕｆｆｌｉｔｓ（上位４ビット）およびＬＳＢＨｕｆｆＬｉｔｓ（下位４ビット）とラベルづけされた、二つの４ビットの量として、扱われてもよい。これは、収集されるリテラル統計量についての総ビットが、１６個のビンへの分類を行う統計にだけ完全に合うだろう、ということを保証する。
【００６３】
Ｎが、方法４００により課された最大ハフマン符号長であるものとして、処理済みファイルを符号化するための方法５００は、Ｍキロバイトのファイルの第１部分についてのみ、ｆｌａｇＲｕｎリテラルをＮ＋１個のビンに割り当てることを含んでもよい。例えば、下記の表１に示すように、１個から８個のリテラルのｆｌａｇＲｕｎ値が、ビン０からビン７に割り当てられるだろう。方法５００は、データファイルの第２部分についてはｆｌａｇＲｕｎリテラルの圧縮を省略５０４することを含んでもよく、このことは、データファイルの第２部分についてｆｌａｇＲｕｎリテラルを数えることを省略することを含んでもよい。
【００６４】
【表１】
2019054532.tif 000010
【００６５】
ファイルの第２部分（例えば後半）の中のＦｌａｇＲｕｎシンボルが、ハフマン符号化されてもよい。例えば、リテラル対コピー命令という平均的な定式化を利用して、もしくは、圧縮符号化フレームの単なる半分ではなく、むしろ他の何らかの定式化を利用して、ｆｌａｇＲｕｎリテラルを動的に符号化することができ、または、半分以外の、圧縮フレームのうちの固定の割合に対して、ｆｌａｇＲｕｎリテラルを動的に符号化することができる。
【００６６】
方法５００は、２＊（Ｎ＋１）個のビンといったような、または、Ｎ＝７に対しては１６個のビンといったような、固定数のビンに、オフセット値をマッピングすること５０６を含んでもよい。例えば、オフセット・マップは、表２にしたがって区分された、統計量の集まりに対する１６個のビンから、成っていてもよい。ある種の実施形態では、オフセットのビンへの分類のために、「直近のコピー・オフセットと同じ」が、１５、または、０と１５の間の任意の値といったような、０以外の他のビン分類値を使うことができる。同様に、「辞書」コピー用に使われるビンが、０以外の何らかの別のビン値を使ってもよい。
【００６７】
【表２】
2019054532.tif 000011
【００６８】
容易に明らかとなるように、オフセットについて可能な値の個数は、ビンの個数を大幅に上回る。しかし、上述のとおり、オフセット値を固定数のビンへと制限することにより、ＶＬＳＩデバイスを用いてオフセット値を動的にハフマン符号化することが可能となる。
【００６９】
方法５００は、２＊（Ｎ＋１）個のビン、または、Ｎ＝７に対して１６個のビンに、長さの値をマッピングすること５０８を、含んでもよい。例えば、長さの値は、表３にしたがって、１６個のビンのうちの一つに割り当てられてもよい。
【００７０】
【表３】
2019054532.tif 000012
【００７１】
方法５００は、２＊（Ｎ＋１）個のビン、または、Ｎ＝７に対して１６個のビンに、長さの値をマッピングすること５０８を、含んでもよい。例えば、長さの値は、表３にしたがって、１６個のビンのうちの一つに割り当てられてもよい。
【００７２】
方法５００は、それぞれのビン集合に対して正則ハフマン符号を生成すること５１０を、含んでもよい。例えば、それぞれのビン集合（ｆｌａｇＲｕｎ、長さ、オフセット、およびリテラル）に対するカウントに対して、方法３００にしたがって正則ハフマン符号を生成してもよい。ステップ５１０で生成されるハフマン符号が、その後、正規化５１２されてもよい。正規化は、図４の方法４００にしたがって、ビット長がＮを超えないようにハフマン符号を変換することを、含んでもよい。各データセット（ｆｌａｇＲｕｎ、長さ、オフセット、およびリテラル）のシンボルは、その後、ステップ５１２で各データセットに対して決定されたハフマン符号を使って、ハフマン符号化５１４されてもよい。
【００７３】
ハフマン符号化されたデータセットは、各データセットを符号化するのに使われたハフマン符号を含むヘッダとともに、出力ストリームに書き出されて受信側装置へと送信されてもよい。入力データファイルに対する出力ストリームまたは出力ファイルは、リテラルのＭＳＢとリテラルのＬＳＢと長さとオフセットとの各々について決定されたハフマン符号については長さが６バイトである、ヘッダ・ツリー・ヘッダの形式で、書かれていてもよい。ヘッダ・ツリー・ヘッダは、リテラルに対するｆｌａｇＲｕｎについては、長さが３バイトであってもよく、つまり、７ビットのためには３バイトしか必要ではないためである。
【００７４】
上述の例では、４キロバイトの入力データファイルだが、８キロ、１６キロ、３２キロ、６４キロ、または他の何らかのサイズ、といったような、別のファイルサイズが使われてもよい。同様に、符号長を７ビットに制限するのではなく、１５ビット、３１ビット、または他の何らかの値、といったような、他の何らかの値に符号長を制限してもよく、そうした他の何らかの値は、入力ファイルのサイズに依存していてもよい。同様に、４キロのオフセットに対するコピー命令用のオフセット値の表について、部分的なマッピングを行ってもよい。同様に、４キロのセクタのうちの２キロバイトに対するリテラル命令の、動的ハフマン符号化を行ってもよい。
【００７５】
以下の参考文献は、その全体が本明細書に取り込まれる。
[1]. D. A. Huffman, “A method for the construction of minimum-redundancy codes” Proc. IRE 40 (9). pp. 1098-1101. 1952.
[2]. L. L. Larmore and D. S. Hirschberg, “A fast algorithm for optimal length-limited Huffman codes,” Journal of the Association for Computing Machinery, (37)3, pp. 464-473, July 1990.
[3]. DEFLATE Compressed Data Format Specification version 1.3. IETF. May 1996. p. 1. sec. Abstract. RFC 1951. ２０１２年１１月１１日取得
[4]. Ziv, J.; Lempel, A. (1978). "Compression of individual sequences via variable-rate coding". IEEE Transactions on Information Theory 24 (5): 530.
【００７６】
本発明は、その精神ないし本質的特質から逸脱することなく、他の特定の形態で実施され得る。記述された実施形態は、あらゆる点において、単に例示的であると考えられるべきであり、制限的なものだと考えられるべきではない。したがって、前述の記述によってではなく、付属の請求項によって、本発明の範囲が示される。請求項の均等物の意味と範囲の中に入る、すべての変更は、請求項の範囲内に含まれるべきである。
【図１】
2019054532.tif 000013
【図２】
2019054532.tif 000014
【図３】
2019054532.tif 000015
【図４】
2019054532.tif 000016
【図５】
2019054532.tif 000017