JP6681313B2 - データを符号化するための方法、コンピュータ・プログラムおよびシステム - Google Patents

Description

本発明は、ハフマンベースのデータ符号化に関し、より詳細には、動的ハフマン・テーブルをハードウェア中で作成する技法に関する。

多くのハードウェアおよびソフトウェア・アプリケーションは、データ圧縮を使用して、ストレージおよびメモリ容量を削減し、また、ネットワークおよび入出力帯域幅を削減する。ハフマン符号化がしばしば使用されて、データが例えばＤｅｆｌａｔｅ（ｇｚｉｐ）標準で圧縮される。ハフマン符号は、最も頻繁なデータ・アイテムがより少数のビットで符号化される、可変長符号である。動的ハフマン符号は、データ・アイテムの頻度に基づいて進行中に構築されるカスタム符号である。

米国特許第５，７４４，８４４号

動的ハフマン（ＤＨ）テーブルをハードウェア中で作成することは、時間および領域を消費するプロセスである。例えば、従来のＤＨベースの圧縮は、ソフトウェア介入の関与を必要とするか、または、Ｄｅｆｌａｔｅソフトウェア・アルゴリズムの、ハードウェアへの複雑なマッピングを必要とする。これらは、性能または圧縮率またはシリコン面積の不利益につながることがある。

結果として、多くのハードウェア実装は、動的ハフマン（ＤＨ）方法の代わりに固定ハフマン（ＦＨ）方法を使用することを選ぶ。ＦＨの欠点は、ＤＨと比較して圧縮が少ないことである。

したがって、動的ハフマン・テーブルをハードウェア中で作成するための、単純化された高速な技法が望ましいであろう。

本発明は、動的ハフマン・テーブルをハードウェア中で作成する技法を提供する。本発明の一態様では、データを符号化する方法が提供される。この方法は、サンプル・データ・セットから事前計算された複数のハフマン木形状を表す動的ハフマン・テーブルをハードウェア中で実装するステップであって、ハフマン木形状が動的ハフマン・テーブル中で符号長値によって表される、実装するステップと；入力データの受取り時に、入力データからのシンボルおよびそれらのカウントを動的ハフマン・テーブルに書き込むステップと；入力データからのシンボルおよびカウントを用いて、動的ハフマン・テーブルのそれぞれについてのスコアを算出するステップであって、スコアが、事前計算されたハフマン木形状の符号長値と、入力データからのカウントとに基づく、算出するステップと；動的ハフマン・テーブルのうちで最も低いスコアを有する所与の１つを、入力データの符号化のために選択するステップとを含む。

本発明の別の態様では、データを符号化するための、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）ベースの方法が提供される。この方法は、サンプル・データ・セットから事前計算された複数のハフマン木形状を表す動的ハフマン・テーブルをハードウェア中で実装するステップであって、ハフマン木形状が動的ハフマン・テーブル中で符号長値によって表され、ハードウェアがＳＲＡＭモジュールを含み、動的ハフマン・テーブルが、動的ハフマン・テーブルのうちの１つについての符号長値のソート済みリストでＳＲＡＭモジュールのそれぞれを初期化することによってハードウェア中で実装される、実装するステップと；入力データの受取り時に、入力データからのシンボルおよびそれらのカウントをＳＲＡＭモジュールのそれぞれの中の動的ハフマン・テーブルに書き込むステップと；入力データからのシンボルおよびカウントを用いて、動的ハフマン・テーブルのそれぞれについてのスコアを算出するステップであって、スコアが、事前計算されたハフマン木形状の符号長値と、入力データからのカウントとに基づく、算出するステップと；動的ハフマン・テーブルのうちで最も低いスコアを有する所与の１つを、入力データの符号化のために選択するステップとを含む。

本発明のより完全な理解、ならびに本発明のさらに他の特徴および利点は、後続の詳細な記述および図面を参照することによって得られるであろう。

本発明の一実施形態による、ハフマン・アルゴリズムを使用して構築される例示的なプレフィックス符号を示す図である。 本発明の一実施形態による、高度に歪んだシンボル分布のヒストグラムを示す図である。 本発明の一実施形態による、高度に歪んだシンボル分布のハフマン木形状を示す図である。 本発明の一実施形態による、高度に歪んだシンボル分布の事前計算済みテーブルを示す図である。 本発明の一実施形態による、中程度に歪んだシンボル分布のヒストグラムを示す図である。 本発明の一実施形態による、中程度に歪んだシンボル分布のハフマン木形状を示す図である。 本発明の一実施形態による、中程度に歪んだシンボル分布の事前計算済みテーブルを示す図である。 本発明の一実施形態による、低程度に歪んだシンボル分布のヒストグラムを示す図である。 本発明の一実施形態による、低程度に歪んだシンボル分布のハフマン木形状を示す図である。 本発明の一実施形態による、低程度に歪んだシンボル分布の事前計算済みテーブルを示す図である。 本発明の一実施形態による、図２ｃのテーブルに書き込まれたシンボルおよびカウントを示す図である。 本発明の一実施形態による、図３ｃのテーブルに書き込まれたシンボルおよびカウントを示す図である。 本発明の一実施形態による、図４ｃのテーブルに書き込まれたシンボルおよびカウントを示す図である。 本発明の一実施形態による、動的ハフマン・テーブルを作成するための例示的な方法を示す図である。 本発明の一実施形態による、本明細書に提示される方法の１つまたは複数を実施するための例示的な装置を示す図である。

上に提供したように、従来の動的ハフマン（ＤＨ）ベースの圧縮は、ソフトウェア介入を必要とする。有利なことに、本明細書では、ＤＨテーブルをハードウェア中で作成するための単純化された高速な技法が提供される。以下に詳細に述べるように、本技法は一般に、プレフィックス木を作成するためのハードウェア方法に関係し、この場合、シンボル頻度を表す複数の木形状およびテーブル、ならびにいくつかのテーブル作成ステップが、プレシリコン（pre-silicon）ステップ中に事前計算され、したがってその結果、ハードウェア実装が単純化される。各テーブルの総ビット・コストが算出され、最も小さい出力サイズのテーブルが、圧縮において使用されるために選択される。

当技術分野で知られているように、ハフマン・アルゴリズムは、圧縮中に使用されて、可変長プレフィックス符号を生み出す。より頻繁なシンボルはより少数のビットを得て、したがって、よりよい圧縮を達成する。図１は、ハフマン・アルゴリズムを使用して構築されるプレフィックス符号の例である。符号化されることになるシンボル（この例ではＡ、Ｂ、およびＺ）が、２進木の葉に割り当てられる。根からシンボルの葉まで枝を辿ることによって、プレフィックス符号が導出される。例えば、シンボルＡは、２進ビット「０」で符号化され、Ｂは、２進ビット「１０」で符号化され、Ｚは「１１」で符号化される。ハフマン・アルゴリズムは、総ビットが最も少数となる最適化された２進木形状を作成する。この例では、シンボル確率は、データ・ストリーム中でシンボルＡが１／２の確率で発生し、ＢおよびＺが１／４の確率で発生する、といった確率である。木形状は、Ａの符号が、ＢおよびＺの符号よりも少ないビットを有する、といった形状である。

従来のプロセスによれば、これらのシンボル確率を使用して、カスタム木が実行時に生成される。比較すると、本技法は、従来のプロセスにおけるように木を実行時に作成しようとする代わりに、木形状をそれぞれが表すテーブルのセットを事前計算することによって、ＤＨハードウェアを単純化する。これらの複数の事前計算されたテーブルは、ハードウェアに組み込まれ、どんな圧縮動作が開始される前にも、使用される準備ができている。本明細書で提示される例示的な実装形態では、各テーブルは、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）中にある。

各テーブルは、シンボルの分布を表す。事前計算されたテーブルは、複数のシンボル分布を表すように選ばれる。圧縮されることになる入力データ中のシンボルの分布に応じて、あるテーブルが他のテーブルよりもよい圧縮率をもたらすことになる。

図２〜４は、異なる３つのシンボル分布、すなわち高度に、中程度に、低程度に歪んだシンボル分布をそれぞれ表す。図２〜４のそれぞれにおいて、シンボルのヒストグラムが提供されており、最も頻繁なシンボルが原点にあり、最も頻繁でないシンボルがｘ軸上で原点から最も遠くにある。また、それぞれの（高、中、または低）シンボル分布によって生成されるはずのハフマン木形状を表す木形状も提供されている。最後に、図２〜４のそれぞれは、目下の事前計算されたテーブルを提供する。これらのヒストグラム、ハフマン木形状、および事前計算済みテーブル・フィーチャには、図２〜４で参照番号ａ、ｂ、およびｃがそれぞれ与えられている。

図２ａ〜ｃは、高度に歪んだシンボル分布を表し、この場合、いくつかのシンボルが他のシンボルよりもずっと多く発生する。例示的な高度に歪んだ分布は、いくつかのシンボルが、次のシンボルの発生の２倍、３倍、４倍、さらにはそれ以上発生するときのものである。例えば、圧縮されていないグラフィックス・ファイル中では、背景色など、最も一般的な色が、次に頻繁な色の数百倍多く発生することがある。別の例では、２進ファイルは通常、１６進数「００」を、次に頻繁なバイト文字の数十倍から数百倍多く含む。図３ａ〜ｃは、中程度に歪んだ分布を表す。図４ａ〜ｃは、低程度に歪んだ分布を表し、この場合、入力ストリーム中でシンボルがおよそ同じ頻度で発生する。低程度に歪んだ分布では、ファイル中のシンボル頻度は、相互のわずかなパーセンテージ・ポイント内である。例えば、標準的な英語テキスト中では、最も頻繁な文字「ｅ」、「ｔ」、「ａ」は、それぞれ１２、９、８パーセントの確率で発生する。図２ａ、３ａ、および４ａで提供されるヒストグラムは、各ケースにおけるカウントによってソートされたシンボルの関数として、全体的なカウントをプロットしている。前述のように、最も頻繁なシンボルが原点にあり、最も頻繁でないシンボルがｘ軸上で原点から最も遠くにある。したがって、予想されるように、ヒストグラムは、シンボルの発生の頻度の差が少ないほど、より平坦になる（すなわち、対応する高度に歪んだシンボル分布から、対応する低程度に歪んだシンボル分布に移る）。図２ｂ、３ｂ、および４ｂで提供される木形状は、これらの高度、中程度、低程度に歪んだシンボル分布によって生成されるはずのハフマン木形状を表す。

図２ｃ、３ｃ、および４ｃには、それぞれの木形状およびシンボル分布をそれぞれが表す、目下の事前計算されたテーブルが提供されている。入力ストリームは図示のテーブルのいずれによっても符号化され得るが、シンボル分布に応じて、テーブルのうちの１つが、最良の圧縮率、すなわち最も小さい圧縮出力をもたらすことになる。

有利なことに、シンボルをハフマン木の葉（すなわちテーブル）に割り当てることは、圧縮時に行われる。言い換えれば、木の形状（すなわちそれぞれのテーブルによって表される）は事前計算済みだが、ハフマン木の葉にあるはずのシンボルは、最初は割り当てられず、実際の圧縮ステップまで延期される。図２〜４で提供される例は、図１に示されるハフマン木の例とは異なり、シンボルが木の葉に割り当てられていない（すなわち疑問符「？」が使用されている）ことによって、この初期状況を表す。

木のテーブル表現（図２ｃ、３ｃ、および４ｃ参照）では、符号長（「Ｌｅｎ」のラベルが付いている）は、木の形状を記述するのに十分である。すなわち、木の根からの木の各葉の距離が、最も短い符号から最も長い符号（この例示的なＤｅｆｌａｔｅ実装形態ではそれぞれ１ビットおよび１５ビット）まで順番にリストされている。例えば、図１に示されるハフマン木の例は、符号長値１、２、２で表すことができる。

本技法によれば、各テーブル・エントリは、３つ組｛ＣｏｄｅＬｅｎｇｔｈ，Ｃｏｕｎｔ，Ｓｙｍｂｏｌ｝からなり、ＣｏｄｅＬｅｎｇｔｈは、そのそれぞれの木形状の事前計算された符号長である。ＣｏｕｎｔおよびＳｙｍｂｏｌは、最初はそれぞれ０およびＮＵＬＬである。これらは、圧縮のＤＨ計算ステップの間に更新されることになる。

圧縮動作が開始されると、入力データが走査され、シンボル頻度が決定される。例えば、文字「Ａ」が入力データ中で１０００回発生する場合、そのカウントは１０００である。シンボルカウントは、最も高いカウントから最も低いカウントへとソートされる。ソートは、当技術分野で知られている多くの異なる方法のうちの１つを使用して行われてよい。例えば、適切なソート・アルゴリズムは、挿入ソート、クイック・ソート、またはバイトニック（Bitonic）ソート・アルゴリズムを含むが、これらに限定されない。

ハードウェアをさらに一層単純化するために、概略ソート・アルゴリズムを使用してシンボルカウントを半ソートすることもできる。その場合、最も頻繁なシンボルだけが正しい順序でソートされ、頻繁でないシンボルは、必ずしも正しい順序でソートされない。例えば、標準的な英語テキスト中では、最も頻繁な文字「ｅ、ｔ、ａ、ｏ、ｉ、ｎ、ｓ、ｈ、ｒ」は、７０％の確率で発生する。この９つの文字を正しい順序でソートすれば、圧縮タスクの７０％が正しく達成されることになり、一方、残りの文字の順序を得ることは、圧縮率の改善にとって重要性がより低い。後続の記述から、頻繁でないシンボルは圧縮率への寄与が減少することが明らかになるであろう。したがって、実行時間の短縮およびシリコン面積の削減のためには、圧縮率のわずかな増加は許容可能である場合がある。

次いで、ソートまたは半ソートされたシンボルカウントは、事前計算されたテーブルのフィールドＣｏｕｎｔおよびＳｙｍｂｏｌに書き込まれる。したがって、３つ組｛ＣｏｄｅＬｅｎｇｔｈ，Ｃｏｕｎｔ，およびＳｙｍｂｏｌ｝は、最も高いカウントのシンボルが最も短い符号長とペアにされ、２番目に高いカウントのシンボルが２番目に短い符号長とペアにされ、以下同様となるように書き込まれる。このステップは、複数のテーブルについて並行して実施される。例えば、図５ａ、ｂ、およびｃを参照されたいが、これらの図は、シンボルおよびカウントが図２ｃ、３ｃ、および４ｃのテーブルに書き込まれたものをそれぞれ示す。

各テーブルがＣｏｕｎｔおよびＳｙｍｂｏｌの値でポピュレートされていくのに伴い、ＣｏｄｅＬｅｎｇｔｈ×Ｃｏｕｎｔの積の合計もまた、ＴｏｔａｌＬｅｎｇｔｈと言う名前のレジスタに蓄積される。例示的な一実施形態によれば、１つのテーブルにつき１つのアキュムレータ・レジスタが存在する。積の値の合計は、入力データをハフマン符号化するのにその特定のテーブルが使用された場合の、圧縮データのサイズである。したがって、最良の圧縮率は、最も小さいＴｏｔａｌＬｅｎｇｔｈ値を有するテーブルが圧縮に使用されたときに達成される。例えば、図５ａ〜ｃで提供される例では、最も小さいＴｏｔａｌＬｅｎｇｔｈ値を有するテーブルは、２９２０ビットの長さ総計（ＴｏｔａｌＬｅｎ）を有する図５ａのテーブルである（図５ｂおよび５ｃのテーブル中の４４１５ビットおよび１２６３５ビットと比較して）。

事前計算された各木形状が、他の多くの部分木を含むことは、留意に値する。したがって、各木（したがってテーブル）は、実際には、複数の木を表す。したがって、有利なことに、ハードウェア中で実装される限られた数のテーブルによって、ずっと多くのシンボル分布が表される。例えば、事前計算された木形状がＮ個の葉を有する場合、この木形状は、有利なことに、Ｎ、Ｎ−１、Ｎ−２、Ｎ−３、．．．３、２、１個の葉を有する約Ｎ個の異なる木を表す。符号化されているデータシンボルの数に応じて、実際上、各テーブルは、その木の形状をとる。例えば、入力データは４つのシンボルＡ、Ｚ、Ｂ、およびＱしか含まないが、テーブルは１５個のシンボルのための空間を有すると仮定する。例えば、図５ａ〜ｃを参照されたい。テーブルは、上から下に、シンボルカウント１０００、５００、３００、および５でポピュレートされる。すべてのテーブルのカウントに対する残りのテーブル・エントリは、０のままとなる。したがって、実際上、各テーブルによって実現される木形状は、元のより大きい１５要素の木の部分木である、４葉の木の木形状である。

上の記述を前提として、次に、図６の方法６００を参照することによって、動的ハフマン・テーブルを作成するための本技法の例示的な一実装形態について述べる。上で強調したように、このプロセスの一部を遂行して、ハードウェア中で実装される木形状が事前計算される。したがって、これらの事前計算ステップは、ハードウェア設計中やハードウェア電源投入初期化中などに、１回だけ実施されれば済む。圧縮動作が開始されると、圧縮動作ごとに、事前計算された木形状にシンボルが割り当てられる。テーブル作成ステップのいくつかを（ハードウェア中で）事前計算することで、圧縮中に必要とされる動作が単純化され、それにより、他のＤＨ技法と比較して、本プロセスの速度および効率が著しく改善される。

図６に示すように、木形状を事前計算するプロセスは、ステップ６０２で、データ・ファイルのサンプル・セットについてシンボル分布のセットを識別することによって開始する。すなわち、これは事前計算動作なので（すなわち、そして圧縮のための特定の入力データ・ストリームはまだ存在しないので）、サンプル・データ・セットを使用して複数の木形状が計算される。例示的な一実施形態によれば、サンプル・データ・セットは、一般的に使用されるデータ・ファイルを含む。一般的に使用されるファイルは、概して各領域に特有である。例えば、英語テキストを扱うコンピューティング・システム中では、サンプル・ファイルが統計的に分析されてよく、木形状が英語アルファベットの文字の頻度に従って構築されてよい。別の例では、グラフィックス・ファイルを扱うコンピューティング・システム中では、サンプル・ファイルが統計的に分析されてよく、木形状が色情報の頻度に従って構築されてよい、等である。

ステップ６０４で、やはり事前計算される動作として、サンプル・データ・セット中で見つかったシンボル分布にマッチするＤＨ符号テーブルが作成される。上に提供したように、符号長（ＣｏｄｅＬｅｎｇｔｈ）は、木形状を記述するのに十分である。したがって、ステップ６０４で、ＤＨ符号テーブルのＣｏｄｅＬｅｎｇｔｈフィールドが、サンプル・データ・セットを使用してポピュレートされる。ＣｏｕｎｔおよびＳｙｍｂｏｌフィールド（最初はそれぞれ０およびＮＵＬＬに設定されている）は、圧縮動作中に更新されることになる（以下参照）。

ステップ６０６で、やはり事前計算される動作として、可変長符号および符号長だけが残るようにＤＨハフマン符号テーブル（ステップ６０４で作成された）からシンボルが除去される。すなわち、上で強調したように、本技法は、圧縮中にテーブルをポピュレートすることを必要とし、したがって、ステップ６０６でシンボル−長さ割当てを除去することによって、残されるのは木形状だけになる。実際のシンボル−長さ割当ては、圧縮中に行われることになる。

ステップ６０８で、やはり事前計算される動作として、符号長をソート・キーとして使用して、符号および符号長が、最も短いものから最も長いものへの順でソートされる。すなわち、上に提供したように、ここでのタスクは、木の根からの木の各葉の距離を、最も短い符号から最も長い符号へと順番にリストすることである。例えば、図２ｃ、３ｃ、および４ｃを参照されたいが、これらの図では、ＣｏｄｅＬｅｎｇｔｈが、最も短いものから最も長いものへと順序付けられている。

ステップ６１０で、ＤＨ符号テーブルがハードウェア中で実装される。ハードウェア中での実装は、ハードウェア中でロジックを再現するソフトウェア実装とは反対に、ハードウェア回路自体が動作を実施することを意味する。例示的な一実施形態によれば、本技法は、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）モジュールを使用してハードウェア中で実装される。当技術分野で知られているように、ＳＲＡＭは、フリップフロップ回路を使用してデータの各ビットを記憶する。例えば、樋口に発行された、「CMOS SRAM Cell」という名称の米国特許第５，７４４，８４４号を参照されたい。

上で強調したように、ハードウェア中で実装される各ＤＨ符号テーブルは、Ｃｏｄｅ、ＣｏｄｅＬｅｎｇｔｈ、Ｓｙｍｂｏｌ、およびＣｏｕｎｔという、４つのフィールドを含む。プロセス中のこの段階では、ＣｏｄｅおよびＣｏｄｅＬｅｎｇｔｈフィールドだけがポピュレートされる。ＣｏｕｎｔおよびＳｙｍｂｏｌフィールドは、圧縮動作中に更新されることになる（以下参照）。

例示的な一実施形態によれば、ＳＲＡＭ中で実装されるときは、ステップ６１０は、第１のＳＲＡＭエントリから順次、符号および符号長のソート済みリストで各ＳＲＡＭモジュールを初期化するステップを含む。すなわち、例えば１つのシンボル分布につき１つのアキュムレータを初期化することによって、ステップ６０２からの各シンボル分布が１つのＳＲＡＭモジュールに書き込まれる。当技術分野で知られているように、アキュムレータは、中間ロジック結果がその中に記憶されることが可能なレジスタである。

プロセスの事前計算段階が、今や完了している。ステップ６０２〜６１０は、例えばハードウェア設計中または初期化中に、１回だけ実施されれば済む。圧縮動作は、ステップ６１２で、例えば入力データ・ストリームの受取り時に開始する。事前計算動作と比較して、圧縮ステップ６１２〜６２６は、各圧縮動作につき実施されることになる。

ステップ６１４で、ＤＨ符号テーブルのＳｙｍｂｏｌおよびＣｏｕｎｔフィールドが、それぞれＮＵＬＬおよび０に初期化される。したがって、現在、ＣｏｄｅおよびＣｏｄｅＬｅｎｇｔｈフィールド（事前計算ステップからの）だけがポピュレートされている。

圧縮されることになる入力データ・ストリームの処理を開始するために、ステップ６１６で、入力データ・ストリーム中のシンボルがカウントされる。ステップ６１８で、カウントをソート・キーとして使用して、入力データ・ストリーム中のシンボルおよびそれらのそれぞれのカウントが、最も頻繁なカウントから最も頻繁でないカウントへの順でソートされる。

ステップ６２０で、入力データ・ストリームからのシンボルおよびカウントが、ハードウェア中のＤＨ符号テーブルに書き込まれる。ここまでに、テーブルのＣｏｄｅおよびＣｏｄｅＬｅｎｇｔｈフィールドだけがポピュレート済みである。例示的な一実施形態によれば、ＳＲＡＭ中で実装されるときは、ステップ６２０は、第１のＳＲＡＭエントリから順次前進しながら、ＤＨ符号テーブルのＳｙｍｂｏｌおよびＣｏｕｎｔフィールドをＳＲＡＭに書き込むことを含む。上に提供したように、これらのテーブルをＳＲＡＭハードウェア中で実装することは、符号および符号長のソート済みリストで各ＳＲＡＭモジュールを初期化することを含んでいた。この場合、各シンボル分布が１つのＳＲＡＭモジュールに書き込まれる。次に、シンボルおよびカウントが、各ＳＲＡＭモジュールに書き込まれる。後で詳細に述べるが、ここでの目標は、入力データ・ストリームの可変長符号化のために、最も小さいカウントを有するシンボル分布を選択することである。各ＳＲＡＭモジュールに異なるシンボル分布が書き込まれるので、次いで（ステップ６２０により）シンボルカウントをこれらの分布のそれぞれに適用することを使用して、これらの分布のうちのどれが最も小さいカウントを与えるかを決定することができる。

ステップ６２０で書き込まれている各エントリにつき、ステップ６２２で、符号長（ステップ６１０（上記参照）による）が読み取られる。ステップ６２４で、符号長にカウントが掛けられ、この値がアキュムレータ・レジスタに書き込まれる。すべてのシンボルおよびカウントが例えばＳＲＡＭモジュールに書き込まれるまで、ステップ６２２および６２４が繰り返される。

ステップ６２６で、最も低いカウントをもたらすＤＨ符号テーブルが、入力データ・ストリームの符号化のために選択される。ＳＲＡＭ中での例示的な実装では、最も小さいカウントを有するアキュムレータ・レジスタをステップ６２６で識別することができ、それぞれのＳＲＡＭモジュール内容、すなわち符号および符号長が、入力データの可変長符号化に使用される。

入力データからのシンボルおよびカウントをハードウェア中の事前計算済みＤＨテーブルに書き込み、最も小さいカウントのテーブルを入力データの符号化における使用のために選択するという本概念について、後続の非限定的な例を参照することによってさらに例証する。この例では、簡単にするために、図２ｃ、３ｃ、および４ｃに示されるＤＨテーブルが、サンプル・データから導出されるものであり、これらのテーブルが前述のようにＳＲＡＭモジュール中で実装されると仮定する。入力データが受け取られると、次いで、シンボルおよびそれらのそれぞれのカウントが、図２ｃ、３ｃ、および４ｃのテーブルに書き込まれる。目標は、各テーブルが入力データに使用された場合の出力のサイズを最初に算出し、次いで、最も低い出力を生み出すテーブル（すなわち最も小さいテーブル）をデータの符号化のために選択することである。したがって、例えば、図２ｃのテーブルをポピュレートすることは、次のように進行する可能性がある。すなわち、シンボルＡが符号長１およびカウント１０００を有する場合は、テーブル中の第１のエントリは｛ＣｏｄｅＬｅｎｇｔｈ，Ｃｏｕｎｔ，Ｓｙｍｂｏｌ｝＝｛１，１０００，Ａ｝となり、シンボルＢが符号長２およびカウント５００を有する場合は、テーブル中の第２のエントリは｛ＣｏｄｅＬｅｎｇｔｈ，Ｃｏｕｎｔ，Ｓｙｍｂｏｌ｝＝｛２，５００，Ｂ｝となり、以下同様となる。同じプロセスが、図３ｃおよび図４ｃのテーブルをポピュレートするために実施される。次いで、符号長とカウントとの積に基づいて、各テーブル中の総カウントについてのスコアが生み出される。例えば、この例では、図２ｃのテーブルについてのスコアは、１×１０００（シンボルＡについてのテーブル中のエントリに対する）＋２×５００（シンボルＢについてのテーブル中のエントリに対する）．．．以下同様として計算されることになる。これから、図２ｃのテーブルが使用された場合の出力のサイズを表す単一のスコアが生み出される。次いで、同じプロセスを使用して、図３ｃのテーブルについてのスコア、および図４ｃのテーブルについてのスコアが算出される。ＳＲＡＭ中で実装されるときは、各スコアは、それぞれのモジュールのアキュムレータ・レジスタに記憶されてよい。各テーブルについてのスコアが他のスコアと比較され、入力データに対して最も低いスコアを生み出すテーブルが、符号化のために選択される。この最も低いスコアを有するテーブルは、入力データに対して最も低い出力を生み出すことになる。

本発明は、システム、方法、またはコンピュータ・プログラム製品、あるいはそれらの組合せとすることができる。コンピュータ・プログラム製品は、本発明の態様をプロセッサに遂行させるためのコンピュータ可読プログラム命令を有するコンピュータ可読ストレージ媒体（１つまたは複数）を含むことができる。

コンピュータ可読ストレージ媒体は、命令実行デバイスによって使用される命令を保持および記憶できる有形デバイスとすることができる。コンピュータ可読ストレージ媒体は、例えば、電子ストレージ・デバイス、磁気ストレージ・デバイス、光学ストレージ・デバイス、電磁ストレージ・デバイス、半導体ストレージ・デバイス、またはこれらの任意の適切な組合せとすることができるが、これらに限定されない。コンピュータ可読ストレージ媒体のより具体的な例の非網羅的なリストは、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読取専用メモリ（ＲＯＭ）、消去可能プログラム可能な読取専用メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、ポータブル・コンパクト・ディスク読取専用メモリ（ＣＤ−ＲＯＭ）、ディジタル多用途ディスク（ＤＶＤ）、メモリ・スティック、フロッピー（Ｒ）・ディスク、機械的にエンコードされたデバイス（命令が記録された、パンチカード、または溝の中の隆起構造）、およびこれらの任意の適切な組合せを含む。本明細書におけるコンピュータ可読ストレージ媒体は、電波もしくは他の自由伝搬する電磁波、導波管もしくは他の伝送媒体を介して伝搬する電磁波（例えば、光ファイバ・ケーブルの中を通る光パルス）、またはワイヤを介して伝送される電気信号など、一時的な信号自体であると解釈されるべきではない。

本明細書に記載のコンピュータ可読プログラム命令は、コンピュータ可読ストレージ媒体からそれぞれのコンピューティング／処理デバイスにダウンロードされてよく、あるいは、ネットワーク（例えば、インターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、もしくはワイヤレス・ネットワーク、またはそれらの組合せ）を介して外部コンピュータまたは外部ストレージ・デバイスにダウンロードされてよい。ネットワークは、銅伝送ケーブル、光伝送ファイバ、ワイヤレス伝送、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータ、またはエッジ・サーバ、あるいはそれらの組合せを含むことができる。各コンピューティング／処理デバイス中の、ネットワーク・アダプタ・カードまたはネットワーク・インタフェースが、コンピュータ可読プログラム命令をネットワークから受け取り、これらのコンピュータ可読プログラム命令を、それぞれのコンピューティング／処理デバイス内のコンピュータ可読ストレージ媒体に記憶されるように転送する。

本発明の動作を遂行するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セット・アーキテクチャ（ＩＳＡ）命令、機械命令、機械依存命令、マイクロコード、ファームウェア命令、状態設定データであってよく、または、Ｓｍａｌｌｔａｌｋ（Ｒ）やＣ＋＋などのオブジェクト指向プログラミング言語、および、「Ｃ」プログラミング言語や類似のプログラミング言語などの従来の手続き型プログラミング言語を含めた、１つもしくは複数のプログラミング言語の任意の組合せで書かれたソース・コードとオブジェクト・コードとのいずれかであってよい。コンピュータ可読プログラム命令は、完全にユーザのコンピュータ上で実行されるか、スタンドアロンソフトウェアパッケージとして部分的にユーザのコンピュータ上で実行されるか、部分的にユーザのコンピュータ上で実行され部分的にリモート・コンピュータ上で実行されるか、または完全にリモート・コンピュータもしくはサーバ上で実行される場合がある。後者のシナリオでは、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）もしくはワイド・エリア・ネットワーク（ＷＡＮ）を含めた任意のタイプのネットワークを介してユーザのコンピュータに接続されてもよく、または、接続は、外部コンピュータに対して（例えば、インターネット・サービス・プロバイダを使用してインターネット経由で）行われてもよい。いくつかの実施形態では、プログラマブル・ロジック回路、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、またはプログラマブル・ロジック・アレイ（ＰＬＡ）を例えば含む電子回路が、本発明の態様を実施するために、コンピュータ可読プログラム命令の状態情報を利用して電子回路を個人化することによって、コンピュータ可読プログラム命令を実行することができる。

本明細書では、本発明の態様を、本発明の実施形態による方法、装置（システム）、およびコンピュータ・プログラム製品の、フローチャート説明またはブロック図あるいはその両方に関して述べている。フローチャート説明またはブロック図あるいはその両方の各ブロック、ならびに、フローチャート説明またはブロック図あるいはその両方の中のブロックの組合せを、コンピュータ可読プログラム命令によって実現できることは理解されるであろう。

これらのコンピュータ可読プログラム命令は、コンピュータまたは他のプログラム可能データ処理装置のプロセッサを介して実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロック中で指定される機能／行為を実現する手段をもたらすように、汎用コンピュータ、専用コンピュータ、または他のプログラム可能データ処理装置のプロセッサに提供され、マシンを生み出すものであってよい。これらのコンピュータ可読プログラム命令はまた、命令が記憶されたコンピュータ可読ストレージ媒体が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロック中で指定される機能／行為の態様を実現する命令を含む製造品を含むように、コンピュータ可読ストレージ媒体に記憶され、コンピュータ、プログラム可能データ処理装置、または他のデバイス、あるいはそれらの組合せに、特定の方式で機能するよう指示するものであってもよい。

コンピュータ可読プログラム命令はまた、コンピュータ、他のプログラム可能装置、または他のデバイス上で実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロック中で指定される機能／行為を実現するように、コンピュータ実装プロセスを生み出すべく、コンピュータ、他のプログラム可能データ処理装置、または他のデバイスにロードされ、コンピュータ、他のプログラム可能装置、または他のデバイス上で一連の動作ステップを実行させるものであってもよい。

図中のフローチャートおよびブロック図は、本発明の様々な実施形態によるシステム、方法、およびコンピュータ・プログラム製品の可能な実装形態の、アーキテクチャ、機能、および動作を示す。これに関して、フローチャートまたはブロック図の中の各ブロックは、モジュール、セグメント、または命令の一部を表すことができ、これは、指定される論理機能を実現するための１つまたは複数の実行可能命令を含む。いくつかの代替実装形態では、ブロック中で示される機能は、図中で示される順序とは異なる順序で生じる場合がある。例えば、関連する機能に応じて、連続して示される２つのブロックが実際にはほぼ同時に実行される場合もあり、またはこれらのブロックが逆の順序で実行されることもある。また、ブロック図またはフローチャート説明あるいはその両方の各ブロック、および、ブロック図またはフローチャート説明あるいはその両方の中のブロックの組合せは、指定される機能もしくは行為を実施するかまたは専用ハードウェアとコンピュータ命令との組合せを遂行する、専用ハードウェアベースのシステムによって実現できることにも気付くであろう。

次に図７に移ると、本明細書で提示される方法の１つまたは複数を実現するための装置７００のブロック図が示されている。例に過ぎないが、装置７００は、図６の方法６００のステップの１つまたは複数を実現するように構成されてよい。

装置７００は、コンピュータ・システム７１０および取外し可能媒体７５０を備える。コンピュータ・システム７１０は、プロセッサ・デバイス７２０、ネットワーク・インタフェース７２５、メモリ７３０、媒体インタフェース７３５、およびオプションのディスプレイ７４０を備える。ネットワーク・インタフェース７２５は、コンピュータ・システム７１０がネットワークに接続するのを可能にし、媒体インタフェース７３５は、コンピュータ・システム７１０がハード・ドライブや取外し可能媒体７５０などの媒体と対話するのを可能にする。

プロセッサ・デバイス７２０は、本明細書で開示される方法、ステップ、および機能を実現するように構成されてよい。メモリ７３０は、分散型またはローカルであってよく、プロセッサ・デバイス７２０は、分散型または単一であってよい。メモリ７３０は、電気、磁気、もしくは光学メモリ、またはこれらもしくは他のタイプのストレージ・デバイスの任意の組合せとして実現されてよい。さらに、用語「メモリ」は、プロセッサ・デバイス７２０によってアクセスされるアドレス指定可能な空間中のアドレスに対して読取りまたは書込みができる任意の情報を包含するのに十分なくらい広く解釈されるべきである。この定義によれば、ネットワーク・インタフェース７２５を介してアクセス可能なネットワーク上の情報もなお、メモリ７３０内にある。というのは、プロセッサ・デバイス７２０がネットワークから情報を取り出すことができるからである。プロセッサ・デバイス７２０を構成する各分散プロセッサは一般に、それ自体のアドレス指定可能なメモリ空間を含むことに留意されたい。また、コンピュータ・システム７１０のいくらかまたはすべてが、特定用途向けまたは汎用の集積回路に組み込まれてもよいことにも留意されたい。

オプションのディスプレイ７４０は、装置７００の人間ユーザとの対話に適した任意のタイプのディスプレイである。一般に、ディスプレイ７４０は、コンピュータ・モニタまたは他の類似のディスプレイである。

本発明の例証的な実施形態について本明細書に述べたが、本発明はこれらの正確な実施形態に限定されないこと、および、本発明の範囲を逸脱することなく他の様々な変更および修正が当業者によって加えられてもよいことを理解されたい。

７００ 装置
７１０ コンピュータ・システム
７２０ プロセッサ・デバイス
７２５ ネットワーク・インタフェース
７３０ メモリ
７３５ 媒体インタフェース
７４０ ディスプレイ
７５０ 取外し可能媒体

Claims (16)

1. データを符号化する方法であって、
   サンプル・データ・セットから事前計算された複数のハフマン木形状を表す動的ハフマン・テーブルをハードウェア中で実装するステップであって、前記ハフマン木形状が前記動的ハフマン・テーブル中で符号長値によって表される、前記実装するステップと、
   入力データの受け取りに応じて、前記入力データからのシンボルおよびそれらのカウントを前記動的ハフマン・テーブルに書き込むステップと、
   前記入力データからの前記シンボルおよびカウントを用いて前記動的ハフマン・テーブルのそれぞれについてのスコアを算出するステップであって、前記スコアが、前記事前計算されたハフマン木形状の前記符号長値と前記入力データからの前記カウントとに基づく、前記算出するステップと、
   前記動的ハフマン・テーブルのうちで最も低いスコアを有する所与の１つを、前記入力データの符号化のために選択するステップと
   を含む方法。
2. 前記動的ハフマン・テーブルがスタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）モジュール中で実装される、請求項１に記載の方法。
3. 前記動的ハフマン・テーブルをハードウェア中で実装する前記ステップが、
   前記ＳＲＡＭモジュールのそれぞれを、前記動的ハフマン・テーブルのうちの１つについての前記符号長値のソート済みリストで初期化するステップを含む、請求項２に記載の方法。
4. 前記入力データからの前記シンボルおよびそれらのカウントを前記動的ハフマン・テーブルに書き込む前記ステップが、
   前記入力データからの前記シンボルおよびそれらのカウントを前記ＳＲＡＭモジュールのそれぞれに書き込むステップを含む、請求項２または３に記載の方法。
5. 前記動的ハフマン・テーブルのそれぞれについての前記スコアを算出する前記ステップが、
   前記動的ハフマン・テーブルのそれぞれの中のエントリごとの、事前計算された符号長値と前記入力データからのカウントとの積の、合計を決定するステップを含む、請求項１ないし４のいずれかに記載の方法。
6. 前記動的ハフマン・テーブルをハードウェア中で実装する前記ステップがさらに、
   前記サンプル・データ・セットについてのシンボル分布のセットを識別するステップを含む、請求項１ないし５のいずれかに記載の方法。
7. 前記動的ハフマン・テーブルをハードウェア中で実装する前記ステップがさらに、
   可変符号長値だけが残るように前記動的ハフマン・テーブルからシンボルを除去するステップを含む、請求項１ないし６のいずれかに記載の方法。
8. 前記動的ハフマン・テーブルをハードウェア中で実装する前記ステップがさらに、
   前記動的ハフマン・テーブル中の前記符号長値を最短から最長へとソートするステップを含む、請求項１ないし７のいずれかに記載の方法。
9. 入力データの受け取りに応じて、前記動的ハフマン・テーブル中のシンボルフィールドをＮＵＬＬに初期化し、前記動的ハフマン・テーブル中のカウント・フィールドを０に初期化するステップをさらに含む、請求項１ないし８のいずれかに記載の方法。
10. 前記入力データ中の前記シンボルをカウントするステップをさらに含む、請求項１ないし９のいずれかに記載の方法。
11. 前記入力データ中の前記シンボルを、それらのカウントによって、最も頻繁なカウントから最も頻繁でないカウントへの順でソートするステップをさらに含む、請求項１ないし１０のいずれかに記載の方法。
12. データを符号化する方法であって、
    サンプル・データ・セットから事前計算された複数のハフマン木形状を表す動的ハフマン・テーブルをハードウェア中で実装するステップであって、前記ハフマン木形状が前記動的ハフマン・テーブル中で符号長値によって表され、前記ハードウェアがＳＲＡＭモジュールを含み、前記動的ハフマン・テーブルが、前記動的ハフマン・テーブルのうちの１つについての前記符号長値のソート済みリストで前記ＳＲＡＭモジュールのそれぞれを初期化することによって前記ハードウェア中で実装される、前記実装するステップと、
    入力データの受取り時に、前記入力データからのシンボルおよびそれらのカウントを前記ＳＲＡＭモジュールのそれぞれの中の前記動的ハフマン・テーブルに書き込むステップと、
    前記入力データからの前記シンボルおよびカウントを用いて、前記動的ハフマン・テーブルのそれぞれについてのスコアを算出するステップであって、前記スコアが、前記事前計算されたハフマン木形状の前記符号長値と前記入力データからの前記カウントとに基づく、前記算出するステップと、
    前記動的ハフマン・テーブルのうちで最も低いスコアを有する所与の１つを、前記入力データの符号化のために選択するステップと
    を含む方法。
13. データを符号化するためのコンピュータ・プログラムであって、
    サンプル・データ・セットから事前計算された複数のハフマン木形状を表す動的ハフマン・テーブルをハードウェア中で実装することであって、前記ハフマン木形状が前記動的ハフマン・テーブル中で符号長値によって表される、前記実装することと、
    入力データの受取り時に、前記入力データからのシンボルおよびそれらのカウントを前記動的ハフマン・テーブルに書き込むことと、
    前記入力データからの前記シンボルおよびカウントを用いて前記動的ハフマン・テーブルのそれぞれについてのスコアを算出することであって、前記スコアが、前記事前計算されたハフマン木形状の前記符号長値と前記入力データからの前記カウントとに基づく、前記算出することと、
    前記動的ハフマン・テーブルのうちで最も低いスコアを有する所与の１つを、前記入力データの符号化のために選択することと
    をコンピュータに実行させる、コンピュータ・プログラム。
14. 請求項１ないし１２のいずれかに記載の方法の各ステップをコンピュータに実行させる、コンピュータ・プログラム。
15. 請求項１ないし１２のいずれかに記載の方法の各ステップを実行するための手段を備える、システム。
16. プロセッサと前記プロセッサに接続可能な第二のメモリであり、前記動的ハフマン・テーブルが実装されない前記第二のメモリを備えるシステムであって、
    前記第二のメモリがコンピュータ・プログラムを含み、前記プロセッサが前記第二のメモリから前記コンピュータ・プログラムを読み出して、請求項１ないし１２のいずれかに記載の方法の各ステップを実行する、
    システム。