JP3974036B2 - ハフマン・デコーディングを実施する方法 - Google Patents

Description

【０００１】
（関連出願）
本特許出願は、Ａｃｈａｒｙａらによる、同時出願された米国特許出願第０９／７０４，３９２号、「Ａ Ｍｅｔｈｏｄ ｏｆ Ｇｅｎｅｒａｔｉｎｇ Ｈｕｆｆｍａｎ Ｃｏｄｅ Ｌｅｎｇｔｈ Ｉｎｆｏｒｍａｔｉｏｎ」（代理人整理番号第０４２３９０号、Ｐ９８０４）に関するものであり、本発明の譲受人に譲受され、かつ参照により、本明細書に組み込んである。
【０００２】
（背景）
本開示は、ハフマン・デコーディングに関する。
【０００３】
周知のように、ハフマン・コーディングは、普及している可変長統計エンコーディング・スキームである。またこれも周知のように、ハフマン・コードの生成は、それぞれの個々のシンボルに対する統計的確率に依拠する。たとえば、Ｄ．Ａ．Ｈｕｆｆｍａｎによる、「Ａ Ｍｅｔｈｏｄ ｆｏｒ ｔｈｅ Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ Ｍｉｎｉｍｕｍ Ｒｅｄｕｎｄａｎｃｙ Ｃｏｄｅｓ」（Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＲＥ、Ｖｏｌｕｍｅ ４０、Ｎｏ．９、ｐａｇｅｓ １０９８〜１１０１，１９５２）を参照されたい。従来のテーブル・ルックアップ・ベースのエンコーディング・スキームが、少なくとも部分的に、効率性がよく、かつ比較的実装が簡単であるために、ハフマン・エンコーディングに広く使用されている。しかし、テーブル・サーチ・ベースのデコーディングは、通常、ソフトウェアとハードウェアの両方の実装の点において非効率的である。これは、実用的な応用例に典型的であるように、テーブル内のエントリの数がかなり高い場合に、特にそうである。ハフマン・デコーディングに用いられる別のアプローチが、「木をトラバースする技術」を用いるハフマン木の生成である。しかし、このデコーディング技術はまた欠点も有する。この特定の技術はビット・シーケンシャルであり、ハフマン木生成プロセスのためおよびデコーディング・プロセスのためのメモリ割当および計算の実行の両方で、余分な「オーバヘッド」を導入する。
【０００４】
本発明と考えられる主題については、本明細書の結論部分において、詳細に記載しかつ明確に特許請求することとする。しかし、本発明は、構成およびオペレーションの方法と、その目的、特徴、利点の両方に関して、以下の詳細な説明を添付図面と合わせて参照することにより、最も良く理解されるであろう。
【０００５】
（詳細な説明）
以下の詳細な説明において、本発明を完全に理解するために、多数の具体的な詳細事項を記載する。しかし、これらの具体的な詳細事項なしに本発明を実践できることを、当業者なら理解するであろう。他の例においては、本発明の意味が不明確とならないように、周知の方法、手順、構成要素、回路について詳細に記述していない。
【０００６】
上記に表示したように、１組のシンボルのハフマン・コードの生成が、ソース・シンボルの出現確率に基づく。通常、本状況下でハフマン木と呼ぶ２分木の構築が用いられる。上述の文書で、Ｄ．Ａ．Ｈｕｆｆｍａｎは、このようにプロセスを記述している。
・すべての可能なシンボルを、その確率とともに列挙する。
・最小の確率を有する２つのシンボルを見つける。
・これらを、その確率が個々の確率の合計である、両方のシンボルを含む単一の集合と置き換える。
・リストがただ１つのメンバしか含まなくなるまで繰り返す。
この手順により、複数の集合の再帰的に構造化された集合が作成され、そのそれぞれが正確に２つのメンバを含む。したがって、それは、「葉」としてのシンボルを有する２分木（「ハフマン木」）として表すことができる。次いで、特定のシンボルのコード（「ハフマン・コード」）を形成するために、２分木をルートからそのシンボルまでトラバースし、左の枝には「０」を、右の枝には「１」を記録する。しかし、この手順についての１つの問題点は、得られるハフマン木が一意ではないことである。このようなコードの応用例の一例が、ＧＺＩＰなどのテキスト圧縮である。ＧＺＩＰは、「無料の」または自由に使用可能なＵＮＩＸ（登録商標）のようなオペレーション・システムを開発するという目標を有するＧＮＵ（Ｇｎｕ’ｓ Ｎｏｔ Ｕｎｉｘ）プロジェクトの下で開発されたテキスト圧縮ユーティリティであり、ＵＮＩＸオペレーション・システム上で「ｃｏｍｐｒｅｓｓ」テキスト圧縮ユーティリティを置き換えるためのものである。たとえば、ウェブサイト「ｈｔｔｐ：／／ｗｗｗ．ｇｚｉｐ．ｏｒｈ／」のｇｚｉｐ−１．２．４．ｔａｒとして使用可能なＧａｉｌｌｙ，Ｊ．Ｌ．およびＡｄｌｅｒ，Ｍ．による「ＧＺＩＰ ｄｏｃｕｍｅｎｔａｔｉｏｎ ａｎｄ ｓｏｕｒｃｅｓ」を参照されたい。
【０００７】
周知のように、結果として生じるハフマン・コードはプリフィックス・コードであり、より頻繁に現れるシンボルに、より少ない数のビットが割り当てられて、可変長ハフマン・コードを形成する。その結果、シンボルの出現頻度を利用することから、最終的に平均コード長が減少される。
【０００８】
図１は、３つのソース・シンボルを有するハフマン木の簡単な一例を示す図である。異なる２値シンボルを木の縁に割り当てることにより、いくつかの２進コードを使用して、同じハフマン木を表すことができる。
【０００９】
このハフマン木のための可能な集合のハフマン・コードが、図２に例示してある。図２から、ハフマン・コードは一意ではないことが示されているが、この例からは、それぞれのシンボルの個々のコード長が一意であるように見える。
【００１０】
対応するハフマン木を構築することにより、ハフマン・コードの長さ情報を生成できる。しかし、上記に表示したように、ハフマン・コードはこの方式で生成された場合は一意ではない。しかし、２つの制約を課すことにより、ハフマン木を用いて作成されたハフマン・コードが一意であると保証できることが分かる。
これらの制約とは、
１．所与のビット長のすべてのコードが、それらが表すシンボルと同じ順序で、辞書式順序で連続した値を有する。
２．より短いコードが、より長いコードより辞書式順序で先行する。
【００１１】
これらの制約に基づいて、ハフマン・コードが一意的に判断できる。図３は、たとえば、これらの制約を用いる１９シンボルのハフマン・コード集合を示す図であり、ここで、コード長はハフマン木を使用して事前に判断されている。図３の表については、ハフマン・コード・テーブル内のエントリ内のダッシュが、シンボルおよび現在のソース・アルファベットによるコードが存在せず、その長さ情報がゼロであることを示している。
【００１２】
本発明の範囲がこの点に限定されるものではないが、上述した制約は、たとえば上記に記述したユーティリティ、ＧＺＩＰなどのさまざまな圧縮アプローチおよび標準において用いられてきた。通常このような応用例では、ハフマン木情報は、圧縮されたテキスト・データとともに１組のコード長情報で通過する。したがって、その集合のコード長情報は、一意のハフマン木を再構築するのに十分である。たとえば、図３に例示されているハフマン・コード・テーブルを、ＧＺＩＰで実施されるような以下のプロセスを使用して生成できる。
【００１３】
コード長は、最初、長さ［ｌ］である。
１）それぞれのコード長のためのコードの数をカウントする。
長さＮ（Ｎ＞＝１）のコードの数を「カウント［Ｎ］」とする。
２）それぞれのコード長のための最小コードの数値を見つける。

３）２で判断された連続した値を使用して、すべてのコードに数値を割り当てる。
【００１４】
上記に表示したように、ハフマン・エンコーディングが、テーブル・ルックアップ技術を使用して比較的簡単に達成できる。しかし、ハフマン・コードのデコーディングは、通常はより計算集約的である。なぜなら、コード・ワードがデコードすべき圧縮されたビット・ストリーム内で受け取られた場合、コード・ワード間には定義済み境界がないからである。上記に記述したように、ハフマン・コードは可変長コードである。
【００１５】
一定入力レート・デコーダと呼ぶ１つのアプローチまたは技術が入力ビット・ストリームを一度に１ビットずつシリアルに処理する。この方法は、デコーディングまたはハフマン木の構築を用いる。したがって、ルートから開始し、その技術には、終端ノードに到達するまで、デコーディング木の枝をトラバースすることが必要となる。終端ノードでは、コード・ワードは完全にデコードされ、したがって、対応するシンボルを所望のように作成または出力できる。次いで、このプロセスは、再び木のルートから開始する。たとえば、Ｂ．ＢｈａｓｋａｒｉｎおよびＫ．Ｋｏｎｓｔａｎｔｉｎｉｄｅｓによる「Ｉｍａｇｅ ａｎｄ Ｖｉｄｅｏ Ｃｏｍｐｒｅｓｓｉｏｎｓ Ｓｔａｎｄａｒｄｓ：Ａｌｇｏｒｉｔｈｍｓ ａｎｄ Ａｒｃｈｉｔｅｃｔｕｒｅｓ」（Ｋｌｕｗｅｒ Ａｃａｄｅｍｉｃ Ｐｕｂｌｉｓｈｅｒｓ、１９９５）を参照されたい。
【００１６】
図４は、対応するデコーディング木を有するハフマン・エンコーディング・テーブルの一例を示す図である。ハードウェアまたはソフトウェアにおけるこのようなデコーダに関連する１つの問題が、どのようにしてデコーディング木をメモリに効率的にマッピングするかである。たとえば、図５は、図４のデコーディング木を使用するビット・シリアル・ハフマン・デコーディングのための読取専用メモリ（ＲＯＭ）エントリのテーブルを示す図である。メモリを効率的にマッピングするための１つのアプローチが、たとえば、Ｍｕｋｈｅｒｊｅｅらによる「ＭＡＲＶＬＥ：ａ ＶＬＳＩ ｃｈｉｐ ｆｏｒ ｄａｔａ ｃｏｍｐｒｅｓｓｉｏｎ ｕｓｉｎｇ ｔｒｅｅ ｂａｓｅｄ ｃｏｄｅｓ」（ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｖｅｒｙ Ｌａｒｇｅ Ｓｃａｌｅ Ｉｎｔｅｇｒａｔｉｏｎ（ＶＬＳＩ）Ｓｙｓｔｅｍ、１（２）：２０３−２１４、Ｊｕｎｅ １９９３）に提案されている。
【００１７】
特に効率的というわけではないが、ハフマン・コードをデコードするための別のアプローチが、ハフマン・テーブルのそれぞれのエントリを入力バッファ内の入力ビットと比較することである。このアプローチでは、最悪の場合、エンコーディング・テーブル内のＮエントリが比較される。ここで、Ｎとはシンボルの総数である。その上、そのエントリのためのコード長情報は周知である。
【００１８】
データ構造を使用して一連のバイナリ・デジタル信号をデコードする方法の一実施形態では、以下のアプローチを用いることができる。データ構造を、デコードされているサブグループのバイナリ・デジタル信号の長さに少なくとも部分的に基づいてサーチできる。この特定の実施形態では、エンコードされるハフマンなどの一連のバイナリ・デジタル信号がエンコードされるが、本発明の範囲は、ハフマン・コーディングまたはデコーディングに限定されるものではない。この特定の実施形態では、本発明の範囲がこの点に限定されるものではないが、サーチする前に、系列内の第１のＮバイナリ・デジタル信号はサブグループとして選択される。ここで、Ｎとは最短コードの長さである。さらに、サブグループの長さが、長さＮを有するデータ構造内のコードがそのサブグループに一致しない場合は、系列内の次のバイナリ・デジタル信号によって増加される。同様に、このアプローチが用いられるこの特定の実施形態では、サブグループと同じ長さを有するデータ構造内の全コードが、一致するかどうかチェックされる。以下にさらに詳細に記述するが、データ構造は、少なくとも部分的に、コード長に基づいて構成されることに留意されたい。さらに、データ構造は、同じコード長を有するコードが順次に格納されるように構成される。
【００１９】
本発明の範囲がデータ構造のこの特定の実施形態に限定されるものではないが、この特定の実施形態は、テーブル内に冗長を示すためにいくつかのシンボルを再配置した後の、図３のハフマン・コード・テーブルに関係することがある。このことは、たとえば、図６に例示してある。たとえば、ハフマン・コード長ゼロを有するシンボルとは、これらのシンボルが用いられないということである。同様に、上記の第１の制約に基づき、所与のビット長のすべてのコードが、辞書式順序で連続した値を有する。したがって、長さ情報を追跡することにより、この長さのハフマン・コードを有する辞書式順序の第１のシンボルのハフマン・コード、および同じ長さを有する最後のシンボルまでのハフマン・コードの数のハフマン・コードが情報の冗長がほとんどない情報を提供する。
【００２０】
データ構造のこの特定の実施形態が、図７に示してある。図７は図６と同じ情報を有するが、話を簡単にするためおよび使用しやすくするために再配置してあることに留意されたい。したがって、図７はより少ないメモリを用いており、以下にさらに詳細に記述するように、ビット・パラレル・デコーディング・スキームが適用できる。
【００２１】
図７に例示したデータ構造の実施形態では、図７の実施形態で示したように、ハフマン・コードのデコーディングを、それぞれのコード長のためのハフマン・コードのコード長および範囲についての情報に少なくとも部分的に基づいて、ビット・パラレル・アプローチで実施できる。このことは、擬似コードの実施を使用して以下に例示し記述する。繰り返すが、本発明の範囲が提供される特定の擬似コードに限定されるものではない。
【００２２】
この状況では、合成データ構造をＮＤＳ（ＮＤＣ）と呼ぶ。これは、プログラミング言語Ｃのための合成データ構造の定義に対応するが、本発明の範囲がこのプログラミング言語または特定のプログラミング言語に限定されるものではない。この特定の実施形態では、繰り返すが、本発明の範囲がこの点に限定されるものではないが、この特定の実施形態では、ＮＤＳのそれぞれのエントリが、図７に示されているように、４つのフィールド、つまりそれぞれ、指定された長さ、開始コード、終了コード、ベース・インデックスを有する。もちろん、開始コードおよび終了コードではなく、開始コードおよび開始コードと終了コードとの差を用いることなどの、多くの均等データ構造が可能であることが理解されよう。
【００２３】
しかし、この特定の実施形態では、ＮＤＣは、互いに異なったコード長を有するエントリの数である。それぞれのエントリが、同じコード長を有する１グループの連続したハフマン・コードを表す。開始コードはこのグループの第１のハフマン・コードであり、終了コードはこのグループの最後のハフマン・コードである。図６に示されているように、ベース・インデックスは、対応するシンボルのためのハフマン・テーブル内の第１のハフマン・コードのインデックス値である。上記に表示したように、本発明の範囲は、この特定のデータ構造に限定されるものではないことに留意されたい。この特定のデータ構造に対する多くの修正形態が可能であり、上記に記述してきた内容の趣旨および範囲内に含まれることは明らかである。
【００２４】
図７に例示したデータ構造の実施形態を用いて、一連のバイナリ・デジタル信号をデコードするための本発明による一実施形態の擬似コード表示を以下に示す。

【００２５】
この特定の実施形態では、本発明の範囲がこの点に限定されるものではないが、データ構造をサーチする前に、系列内の第１のＮバイナリ・デジタル信号がサブグループとして選択されるが、ここでＮとは最短コードの長さである。次いで、その長さを有するすべてのコードを一致するかどうかチェックする。一致が出現しなかった場合は、サブグループの長さを系列内の次のバイナリ・デジタル信号によって増加させ、次いで、増加した長さを有するコードを一致するかどうかチェックする。このプロセスを一致が出現するまで続行する。上記に注記したように、データ構造が少なくとも部分的にコード長に基づいて構成され、データ構造は、同じコード長を有するコードが辞書式順序で順次格納されるよう構成される。このことにより、所望のままに効率的なオペレーションが可能となる。
【００２６】
一代替実施形態では、最長コードでサーチを開始し、一致が出現しなかった場合は、サブグループの長さを減少させることが可能であることに留意されたい。しかし、通常、より短いハフマン・コードがより高い出現確率を有するために、このような状況では最短コードからサーチを開始することがより効率的である。
【００２７】
一連のバイナリ・デジタル信号をデコードする方法のこの特定の実施形態は、メモリの利用、計算の複雑さおよび実施の面で、いくつかの利点を有する。上記に提案したように、データ構造のためのエントリの数は、シンボルの数ではなく、ハフマン・コードのための最大コード長に依存する。したがって、このことによりメモリが削減される。たとえば、ＧＺＩＰなどの固定限度コード長を用いる応用例の場合、代表的なハフマン木が２８５シンボルを有し、コード長は１５ビットに制限される。それと対称的に、この実施形態のために用いるエントリの数は、データによって異なるが、せいぜい１５エントリを有し、その結果この例では、１９ｘメモリ利用の削減が生じる。
【００２８】
同様に、ビット・シリアル・サーチ・プロセスではなく、ビット・パラレル・サーチ・プロセスを使用することにより、計算の複雑さが減少される。ここで、この実施形態は、少なくとも部分的にデータ構造内のコード長情報に基づく。そのコード長を有するグループのための開始および終了コードの範囲をチェックすることにより、既存アプローチに比べてサーチ手順が向上する。１９シンボルおよび７ビットの最大コード長を用いるこの実施形態の実験結果から、ハフマン・コード・テーブルのサーチを用いるデコーディングと比較して、複雑さの点で５．５倍削減される。同様に、ハフマン木が構築される場合に生じるような２分木の構築が起きないために、かつ動的なメモリ割当がほとんどまたは全くないために、ハードウェアとソフトウェアの両方で、本発明によるデコーディングの実施が比較的簡単となる。
【００２９】
特定の実施形態のみを記述してきたが、本発明の範囲が特定の実施形態または実装形態に限定されるものではないことが、もちろん、理解されるであろう。たとえば、一実施形態はハードウェアでなされ、別の実施形態はソフトウェアでなされるてもよい。同様に、一実施形態が、たとえば、ファームウェア、あるいはハードウェア、ソフトウェア、またはファームウェアの組合せでもよい。同様に、本発明の範囲がこの点に限定されるものではないが、一実施形態が、記憶媒体などの製品を備えることができる。たとえば、ＣＤ−ＲＯＭやディスクなどの記憶媒体が、それに命令を格納していることがあり、コンピュータ・システムやプラットフォームまたは画像作成システムなどのシステムによって実行された場合、その結果、たとえば、上記に記述したようなハフマン・デコーディングを実施する方法などの、本発明による方法の一実施形態を実行できる。同様に、データ構造を作成する方法の実施形態を、本発明に従って実行できる。
【００３０】
本発明のある特徴について、本明細書に例示し記述してきたが、当業者には、多くの修正形態、置換形態、変更形態、均等物が考えられるであろう。したがって、頭記の特許請求の範囲は、すべてのこのような修正形態および変更形態を、本発明の真の趣旨内に入るものとして、包含することを意図することを理解されるであろう。
【図面の簡単な説明】
【図１】 ハフマン木構築および関連するハフマン木の一例を示す図である。
【図２】 図１のハフマン木のための可能なハフマン・コードを示す表である。
【図３】 選択されたルールを適用して、一意的にハフマン・コードを判断するハフマン・コードの一例を示す表である。
【図４】 対応するデコーディング木を有するハフマン・エンコーディング・テーブルの一例を示す図である。
【図５】 ビット・シリアル・ハフマン・デコーディングのための読取専用メモリ（ＲＯＭ）エントリを示す表である。
【図６】 異なる構成が適用されている、図３の表からの情報を使用する表である。
【図７】 本発明によるデータ構造の一実施形態を示す表である。

Claims (2)

1. コード長、開始コードと終了コードとを表す値及びベース・インデックスをそれぞれ保持するフィールドを有したテーブルを備えたデータ構造を使用して、エンコードされている第１のバイナリ・デジタル信号をデコードする方法であって、
   （ａ）前記テーブルの最短のコード長に関する、開始コードと終了コードとを表す値から得られる開始コードから終了コードまでの複数の第２のバイナリ・デジタル信号のいずれかと前記第１のバイナリ・デジタル信号とが一致するか否か判定し、
   （ｂ）前記第１のバイナリ・デジタル信号と一致する第２のバイナリ・デジタル信号が存在する場合には、その一致した第２のバイナリ・デジタル信号とそれに対応するベース・インデックスとから決定されるメモリ場所に格納されているデータを前記第１のバイナリ・デジタル信号の復号値として取り出して出力し、
   （ｃ）前記第２のバイナリ・デジタル信号のいずれも前記第１のバイナリ・デジタル信号と一致しない場合には、次に短いコード長に関してステップ（ａ）〜（ｃ）を繰り返し、この繰り返しのステップでマッチが見つかった場合に前記第１のバイナリ・デジタル信号の復号値を出力する
   方法。
2. コード長、開始コードと終了コードとを表す値及びベース・インデックスをそれぞれ保持するフィールドを有したテーブルを備えたデータ構造を使用して、エンコードされている第１のバイナリ・デジタル信号をデコードする命令を格納した記憶媒体であって、
   その命令が実行されたときにコンピュータに、
   （ａ）前記テーブルの最短のコード長に関する、開始コードと終了コードとを表す値から得られる開始コードから終了コードまでの複数の第２のバイナリ・デジタル信号のいずれかと前記第１のバイナリ・デジタル信号とが一致するか否か判定させ、
   （ｂ）前記第１のバイナリ・デジタル信号と一致する第２のバイナリ・デジタル信号が存在する場合には、その一致した第２のバイナリ・デジタル信号とそれに対応するベース・インデックスとから決定されるメモリ場所に格納されているデータを前記第１のバイナリ・デジタル信号の復号値として取り出して出力させ、
   （ｃ）前記第２のバイナリ・デジタル信号のいずれも前記第１のバイナリ・デジタル信号と一致しない場合には、次に短いコード長に関してプロセス（ａ）〜（ｃ）を繰り返させ、この繰り返しのプロセスでマッチが見つかった場合に前記第１のバイナリ・デジタル信号の復号値を出力させる
   ための命令を格納した記憶媒体。

Images