(57)【要約】【課題】本発明の課題は、記憶容量を節約することができ、ハフマンエンコーディング効率を向上させるハフマン木の記憶方法及びアレイでデータデコーディングする方法を提供することである。【解決手段】本発明に係るハフマン木の記憶方法は、幅優先探索計算方法によってハフマン木の各々のノードの索引値を順番に作成するステップと、第一ノードから始めて索引値の前記ハフマン木の各々のノードを順番に読み取るステップと、各々のノードの情報を第一部分情報及び第二部分情報に分割してアレイに記憶するステップと、を備え、各々のノードは戻り値を含む。また、本発明は、アレイでデータデコーディングする方法にも関する。【選択図】図２
2011244447.tif 000002
【特許請求の範囲】
【請求項１】
幅優先探索計算方法によってハフマン木の各々のノードの索引値を順番に作成するステップと、
第一ノードから始めて索引値の前記ハフマン木の各々のノードを順番に読み取るステップと、
各々のノードの情報を第一部分情報及び第二部分情報に分割してアレイに記憶するステップと、
を備え、
前記ハフマン木の各々のノードは戻り値を含むことを特徴とするハフマン木の記憶方法。
【請求項２】
各々のノードの情報を第一部分情報及び第二部分情報に分割してアレイに記憶するステップは、
各々のノードの第一部分情報の２進法の数値及び第二部分情報の２進法の数値を合計するステップと、
前記合計された２進法の数値に対応する１０進法の数値をアレイに記憶するステップと、
を備えることを特徴とする請求項１に記載のハフマン木の記憶方法。
【請求項３】
各々のノードの情報を第一部分情報及び第二部分情報に分割してアレイに記憶するステップは、
現在のノードが内部ノードである場合、前記現在のノードの第一部分情報の値が前記現在のノードの左の子ノードの索引値と前記現在のノードの索引値の差値であり、前記現在のノードの第二部分情報の値が１であるステップと、
現在のノードが外部ノードである場合、前記現在のノードの第一部分情報の値が前記現在のノードの戻り値であり、前記現在のノードの第二部分情報の値が０であるステップと、
を備えることを特徴とする請求項２に記載のハフマン木の記憶方法。
【請求項４】
前記第一部分情報の記憶長さが７ｂｉｔｓであり、前記第二部分情報の記憶長さが１ｂｉｔであることを特徴とする請求項４に記載のハフマン木の記憶方法。
【請求項５】
アレイ第一部分情報及び第二部分情報を含むハフマン木の各々のノードの情報を記憶するアレイでデータデコーディングする方法において、
（ａ）デコーディングされるビットストリームを獲得するステップと、
（ｂ）ハフマン木から第一ノードを読み取るステップと、
（ｃ）前記ノードは葉ノードであるかどうかを判断するステップと、
（ｄ）前記ノードが葉ノードではない場合、前記ビットストリームから１つのビットを順番に読み取り、読み取られたビットの値に基づいて次の捜そうとするノードを確定し、次いで、ステップ（ｃ）に戻り、次の捜そうとするノードが葉ノードであるかどうかを判断するステップと、
（ｅ）前記ノードが葉ノードである場合、前記ノードの索引値に基づいて、ハフマンアレイから前記ノードの記憶値を捜し、前記ノードの記憶値から前記ノードの第一部分情報の値を獲得して前記ノードの戻り値とするステップと、
（ｆ）前記ビットストリームの読取を完成したかどうかを判断するステップと、
（ｇ）前記ビットストリームの読取を完成しなかった場合、ステップ（ｂ）に戻るステップと、
（ｈ）前記ビットストリームの読取を完成した場合、ステップ（ｅ）で獲得した各々のノードの戻り値を出力して、前記ビットストリームのデコーディング過程を完成するステップと、
を備えることを特徴とするアレイでデータデコーディングする方法。
【請求項６】
各々のノードの情報を第一部分情報及び第二部分情報に分割してアレイに記憶するステップは、
各々のノードの第一部分情報の２進法の数値及び第二部分情報の２進法の数値を合計するステップと、
前記合計された２進法の数値に対応する１０進法の数値をアレイに記憶するステップと、
を備えることを特徴とする請求項５に記載のアレイでデータデコーディングする方法。
【請求項７】
各々のノードの情報を第一部分情報及び第二部分情報に分割してアレイに記憶するステップは、
現在のノードが内部ノードである場合、前記現在のノードの第一部分情報の値が前記現在のノードの左の子ノードの索引値と前記現在のノードの索引値の差値であり、前記現在のノードの第二部分情報の値が１であるステップと、
現在のノードが外部ノードである場合、前記現在のノードの第一部分情報の値が前記現在のノードの戻り値であり、前記現在のノードの第二部分情報の値が０であるステップと、
を備えることを特徴とする請求項６に記載のアレイでデータデコーディングする方法。
【請求項８】
前記ノードは葉ノードであるかどうかを判断するステップは、
前記ノードの第二部分情報の値が１である場合、前記ノードは、内部ノードであると判断するステップと、
前記ノードの第二部分情報の値が０である場合、前記ノードは、葉ノードであると判断するステップと、
を備えることを特徴とする請求項７に記載のアレイでデータデコーディングする方法。
【請求項９】
ビットの値に基づいて次の捜そうとするノードを確定するステップは、
前記ビットの値が０である場合、次の捜そうとするノードの索引値は、現在のノードの索引値＋現在のノードの第一部分情報の値であるステップと、
前記ビットの値が１である場合、次の捜そうとするノードの索引値は、現在のノードの索引値＋現在のノードの第一部分情報の値＋１であるステップと、
を備えることを特徴とする請求項７に記載のアレイでデータデコーディングする方法。
【請求項１０】
現在のノードの第一部分情報の値を獲得するステップは、
現在のノードの記憶値に対応する２進法の数値を右へ１位移動してから２進法の数値を得るステップと、
右へ移動された２進法の数値を１０進法の数値に変換してから現在のノードの第一部分情報の値を獲得するステップと、
を備えることを特徴とする請求項９に記載のアレイでデータデコーディングする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データエンコーディング／デコーディング方法に関し、特にハフマン木の記憶方法及びアレイ（ａｒｒａｙ）でデータデコーディングする方法に関する。
【背景技術】
【０００２】
従来のハフマンエンコーディングしている過程において、ハフマン木のノード（ｎｏｄｅ）情報は、ハフマンフォームによって記憶される。各々のノードは、戻り値（Ｖａｌｕｅ）、エンコード、エンコードの長さ（Ｌｅｎｇｔｈ）のような三種の情報を含む。デコーディング中に、エンコードに基づいてハフマンフォームから対応する戻り値を捜すことができる。各々のノードが三種の情報を含むため、ハフマンフォームの中の各々のデータは、三つのフィールド（Ｆｉｅｌｄ）に記憶することを必要として、記憶容量を節約することができず、且つハフマンエンコーディング効率が低い。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明の第一の目的は、前記問題を解決し、記憶容量を節約することができ、ハフマンエンコーディング効率を向上させるハフマン木の記憶方法を提供することである。
【０００４】
本発明の第二の目的は、前記問題を解決し、記憶容量を節約することができ、ハフマンエンコーディング効率を向上させるアレイでデータデコーディングする方法を提供することである。
【課題を解決するための手段】
【０００５】
前記第一の目的を達成するため、本発明に係るハフマン木の記憶方法は、幅優先探索計算方法によってハフマン木の各々のノードの索引値を順番に作成するステップと、第一ノードから始めて索引値の前記ハフマン木の各々のノードを順番に読み取るステップと、各々のノードの情報を第一部分情報及び第二部分情報に分割してアレイに記憶するステップと、を備え、前記各々のノードは戻り値を含む。
【０００６】
前記第二の目的を達成するため、本発明に係るアレイでデータデコーディングする方法は、そのアレイには、第一部分情報及び第二部分情報を含むハフマン木の各々のノードの情報を記憶する。（ａ）デコーディングされるビットストリームを獲得するステップと、（ｂ）ハフマン木から第一ノードを読み取るステップと、（ｃ）前記ノードは葉ノードであるかどうかを判断するステップと、（ｄ）前記ノードが葉ノードではない場合、前記ビットストリームから１つのビットを順番に読み取り、読み取られたビートの値に基づいて次の捜そうとするノードを確定し、次いで、ステップ（ｃ）に戻り、次の捜そうとするノードが葉ノードであるかどうかを判断するステップと、（ｅ）前記ノードが葉ノードである場合、前記ノードの索引値に基づいて、ハフマンアレイから前記ノードの記憶値を捜し、前記ノードの記憶値から前記ノードの第一部分情報の値を獲得して前記ノードの戻り値とするステップと、（ｆ）前記ビットストリームの読取を完成したかどうかを判断するステップと、（ｇ）前記ビットストリームの読取を完成しなかった場合、ステップ（ｂ）に戻るステップと、（ｈ）前記ビットストリームの読取を完成した場合、ステップ（ｅ）で獲得した各々のノードの戻り値を出力して、前記ビットストリームのデコーディング過程を完成するステップと、を備える。
【発明の効果】
【０００７】
本発明に係るハフマン木の記憶方法及びアレイでデータデコーディングする方法は、アレイでハフマン木のノード情報を記憶することができる。デコーディング中に、再び前記アレイを利用してハフマン木のノードの戻り値を捜す。従って、記憶容量を節約し、ハフマンエンコーディング効率を向上させる。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施形態に係る記憶モジュール及びデコーディングモジュールの応用環境を示す図である。
【図２】本発明の実施形態に係るハフマン木の記憶方法のフローチャートである。
【図３】従来のハフマンフォームを示す図である。
【図４】図３に示すハフマンフォームに基づいて獲得したハフマン木を示す図である。
【図５】図４に示すハフマン木に対して索引値編号を行う図である。
【図６】本発明の実施形態に係る記憶された各々のノード情報のデータ構造を示す図である。
【図７】本発明の実施形態に係るアレイでデータデコーディングする方法のフローチャートである。
【発明を実施するための形態】
【０００９】
図１は、本発明の実施形態に係る記憶モジュール及びデコーディングモジュールの応用環境を示す図である。前記記憶モジュール２２及び前記デコーディングモジュール２３は、表示装置１及び入力装置４に接続しているコンピューター２で実行される。前記コンピューター２は、記憶装置２０及び中央演算処理装置（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２４をさらに備える。本実施形態において、前記記憶モジュール２２は、アレイでハフマン木のノード情報を記憶する。前記デコーディングモジュール２３は、前記アレイに基づいてデータ（ビットストリーム）をデコーディングする。本実施形態において、前記アレイは、１次元のアレイである。
【００１０】
前記記憶装置２０は、前記コンピューター２のハードディスク又はデータベース等であってもよく、情報２１を記憶することに用いられる。本実施形態において、前記情報２１は、デコーディングされるデータ（ビットストリーム）等を含む。前記中央演算処理装置２４は、前記記憶モジュール２２及び前記デコーディングモジュール２３の実行状態を制御することに用いられる。
【００１１】
前記表示装置１は、前記デコーディングモジュール２３によってデコーディングされたデータ等を表示することに用いられる。前記入力装置４は、キーボード又はマウス等であってもよく、データを入力することに用いられる。
【００１２】
図２は、本発明の実施形態に係るハフマン木の記憶方法のフローチャートである。
【００１３】
ステップＳ１０：前記記憶モジュール２２は、幅優先探索（Ｂｒｅａｄｔｈ  Ｆｉｒｓｔ  Ｓｅａｒｃｈ、ＢＦＳ）計算方法によって、ハフマン木の各々のノードの索引値を順番に作成する。例えば、図３に示したハフマンフォームに基づいて図４に示したハフマン木を作成した場合、幅優先探索計算方法によって、左上から右下に至る順序で前記ハフマン木の各々のノードに対して番号を付ける（０から始める）ことによって、各々のノードの索引値を作成して、図５に示した索引値を有するハフマン木を得る。図中、各々のノードの索引値は、前記ノードの上方に下線付きの太字で表示する。
【００１４】
ステップＳ１２：前記記憶モジュール２２は、第一ノードから始めて索引値の前記ハフマン木の各々のノードを順番に読み取る。本実施形態において、前記記憶モジュール２２は、索引値の昇順にしたがって前記ハフマン木の各々のノードを読み取る。
【００１５】
ステップＳ１４：前記記憶モジュール２２は、各々のノードの情報を第一部分情報Ｖａｌｕｅ２及び第二部分情報ＬｅａｆＢｉｔ（図６のＡ部分を参照する）に分割し、且つ各々のノードの第一部分情報Ｖａｌｕｅ２の２進法の数値及び第二部分情報ＬｅａｆＢｉｔの２進法の数値を合計してから、合計された２進法の数値に対応する１０進法の数値をアレイに記憶する。以下、合計された２進法の数値に対応する１０進法の数値を記憶値と呼び、前記アレイをハフマンアレイと呼ぶ。具体的に説明すると、現在のノードが内部ノードである場合、第一部分情報Ｖａｌｕｅ２の値が前記ノードの左の子ノードの索引値と現在のノードの索引値との差値であり、第二部分情報ＬｅａｆＢｉｔの値が１である。現在のノードが外部ノード（葉ノード）である場合、第一部分情報Ｖａｌｕｅ２の値が現在のノードの戻り値であり、第二部分情報ＬｅａｆＢｉｔの値が０である。
【００１６】
図５に示したハフマン木を例として説明すると、前記ハフマン木のノードの戻り値は、−３〜３の範囲にある。全ての内部ノードに対して、各々のノードの左の子ノードの索引値とこのノードの索引値との差値の最大値は３である。従って、前記ハフマン木の１つのノードを記憶する際、占用する位数は、少なくとも３Ｂｉｔ（Ｖａｌｕｅ２）＋１Ｂｉｔ（ＬｅａｆＢｉｔ）＝４Ｂｉｔである。ソフトでハフマン木のアレイを記憶する場合、アレイは少なくとも１ｂｙｔｅであるため、Ｃ言語で以下のようなハフマンアレイを作成することができる。
【００１７】
ｃｈａｒ  Ｈｕｆｆｍａｎ＿Ａｒｒａｙ[１３]＝｛３，５，７，−２，２，５，０，４，３，５，−４，−６，６｝。
【００１８】
索引値が５であるノードを例として説明すると、これが内部ノードであるので、前記ノードの第一部分情報Ｖａｌｕｅ２の値が左の子ノードの索引値と前記ノードの索引値との差値であり、前記差値が２である。前記ノードの第二部分情報ＬｅａｆＢｉｔの値が１である。図６のＢ部分に示したように、もし各々のノードを８Ｂｉｔｓで記憶する際、その中の第一部分情報Ｖａｌｕｅ２の値は７Ｂｉｔｓで記憶し、即ち（０００００１０）２であり、第二部分情報ＬｅａｆＢｉｔの値は１Ｂｉｔで記憶すると、アレイＨｕｆｆｍａｎ＿Ａｒｒａｙにおける前記ノードの記憶値Ｈｕｆｆｍａｎ＿Ａｒｒａｙ[５]が５であり、即ち（０００００１０１）２である。
【００１９】
索引値が１０であるノードを例として説明すると、これが外部ノードであるので、図６のＣ部分に示したように、前記ノードの第一部分情報Ｖａｌｕｅ２の値が戻り値であり、前記戻り値が−２であり、即ち（１１１１１１０）２であり、第二部分情報ＬｅａｆＢｉｔの値が０である。アレイＨｕｆｆｍａｎ＿Ａｒｒａｙにおける前記ノードの記憶値Ｈｕｆｆｍａｎ＿Ａｒｒａｙ[１０]が−４であり、即ち、（１１１１１１００）２である。
【００２０】
図７は、本発明の実施形態に係るアレイでデータデコーディングする方法のフローチャートである。
【００２１】
ステップＳ２０：デコーディングモジュール２３は記憶装置２０からデコーディングされるビットストリームを獲得する。
【００２２】
ステップＳ２１：前記デコーディングモジュール２３はハフマン木から第一ノードを読み取ってデコーディングする。
【００２３】
ステップＳ２２：前記デコーディングモジュール２３は、前記ノードが葉ノードであるかどうかを判断する。前記ノードが葉ノードではない場合、ステップＳ２３を行う。前記ノードが葉ノードである場合、ステップＳ２４を行う。具体的に説明すると、前記ノードの第二部分情報ＬｅａｆＢｉｔの値が１である場合（即ち、ハフマンアレイにおける前記ノードの記憶値に対応する２進法の数値の最後の位が１である場合）、前記デコーディングモジュール２３は前記ノードが内部ノードだと判定する。前記ノードの第二部分情報ＬｅａｆＢｉｔの値が０である場合（即ち、ハフマンアレイにおける前記ノードの記憶値に対応する２進法の数値の最後の位が０である場合）、前記デコーディングモジュール２３は前記ノードが葉ノードだと判定する。
【００２４】
ステップＳ２３：前記デコーディングモジュール２３は、前記ビットストリームから１つのビットを順番に読み取り、読み取られたビートの値に基づいて次の捜そうとするノードを確定し、次いで、ステップＳ２２に戻り、次の捜そうとするノードが葉ノードであるかどうかを判断する。具体的に説明すると、前記ビットの値が０である場合、次の捜そうとするノードの索引値は、現在のノードの索引値＋現在のノードの第一部分情報Ｖａｌｕｅ２の値である。前記ビットの値が１である場合、次の捜そうとするノードの索引値は、現在のノードの索引値＋現在のノードの第一部分情報Ｖａｌｕｅ２の値＋１である。
【００２５】
現在のノードの第一部分情報Ｖａｌｕｅ２の値は、以下の方法を採用して獲得することができる。現在のノードの索引値に基づいて、ハフマンアレイから現在のノードの記憶値を捜し、現在のノードの記憶値から現在のノードの第一部分情報Ｖａｌｕｅ２の値を獲得する。具体的に説明すると、前記デコーディングモジュール２３は、現在のノードの記憶値に対応する２進法の数値を右へ１位移動してから２進法の数値を得る。右へ移動された２進法の数値を１０進法の数値に変換してから現在のノードの第一部分情報Ｖａｌｕｅ２の値を獲得する。
【００２６】
ステップＳ２４：前記デコーディングモジュール２３は、前記ノードの索引値に基づいて、ハフマンアレイから現在のノードの記憶値を捜し、現在のノードの記憶値から現在のノードの第一部分情報Ｖａｌｕｅ２の値を獲得して前記ノードの戻り値とする。
【００２７】
ステップＳ２５：前記デコーディングモジュール２３は、前記ビットストリームの読取を完成したかどうかを判断する。前記ビットストリームの読取を完成した場合、ステップＳ２６を行う。前記ビットストリームの読取を完成しなかった場合、ステップＳ２１に戻す。
【００２８】
ステップＳ２６：前記デコーディングモジュール２３は、ステップＳ２４で獲得した各々のノードの戻り値を出力して、前記ビットストリームのデコーディング過程を完成する。本実施形態において、前記デコーディングモジュール２３は、獲得した各々のノードの戻り値を前記表示装置１に出力する。
【００２９】
以下、例を挙げてデコーディング過程に対して具体的に説明する。
【００３０】
デコーディングされるビットストリームが０１０１０００１１０１１０１１１である場合、図５に示したハフマン木を使用して前記ビットストリームに対してデコーディングする。図６を参照すると、前記ハフマン木を記憶するアレイは、Ｈｕｆｆｍａｎ＿Ａｒｒａｙ[１３]＝｛３，５，７，−２，２，５，０，４，３，５，−４，−６，６｝に定義される。デコーディング過程が以下のステップを含む。
【００３１】
１.ルートノード（ｒｏｏｔ  ｎｏｄｅ）から始め、索引値Ｉｎｄｅｘ＝０である。
【００３２】
２.前記ノードが葉ノードであるかどうかを判断し、Ｈｕｆｆｍａｎ＿Ａｒｒａｙ[０]の最小位が１であるため、前記ノードは葉ノードではない。
【００３３】
３.ビットストリーム
【００３４】
【数１】
2011244447.tif 000003
【００３５】
から１つのビットを順番に読み取る。具体的には、最初に第一個目のビットを読み取り、次に第二個目のビットを読み取り、・・・第ｎ番目に第ｎ個目のビットを読み取る。第一個目のビットが０であるため、索引値Ｉｎｄｅｘ＝（０＋（Ｈｕｆｆｍａｎ＿Ａｒｒａｙ[０]＞＞１））＝０＋１＝１である。次の捜そうとするノードの索引値が１である。その中、Ｈｕｆｆｍａｎ＿Ａｒｒａｙ[０]）＞＞１は、索引値が“Ｉｎｄｅｘ”であるノードの第一部分情報Ｖａｌｕｅ２を表示する。
【００３６】
４.Ｉｎｄｅｘ＝１であるノードが葉ノードであるかどうかを判断し、Ｈｕｆｆｍａｎ＿Ａｒｒａｙ[１]の最小位が１であるため、前記ノードは葉ノードではない。
【００３７】
５. ビットストリーム
【００３８】
【数２】
2011244447.tif 000004
【００３９】
から次のビットを読み取り、次のビットが１であるため、索引値Ｉｎｄｅｘ＝（１＋（Ｈｕｆｆｍａｎ＿Ａｒｒａｙ[１]＞＞１）＋１）＝１＋２＋１＝４であり、次の捜そうとするノードの索引値が４である。
【００４０】
６. Ｉｎｄｅｘ＝４であるノードが葉ノードであるかどうかを判断し、Ｈｕｆｆｍａｎ＿Ａｒｒａｙ[４]の最小位が０であるため、前記ノードは葉ノードであり、戻り値＝（Ｈｕｆｆｍａｎ＿Ａｒｒａｙ[４] ＞＞１）＝１である。
【００４１】
７.上記の１〜６のステップによって、前記ビットストリームの読取を完成するまでに、ビットストリーム０１０１０００１１０１１０１１１の中の他のデータ（
【００４２】
【数３】
2011244447.tif 000005
【００４３】
、下線の部分である）に対してデコーディングし、獲得したデコーディング値は、｛１，１，−１，１，−２，０｝である。
【００４４】
以上、本発明を実施形態に基づいて具体的に説明したが、本発明は、上述の実施形態に限定されるものではなく、その要旨を逸脱しない範囲において、種々の変更が可能であることは勿論であって、本発明の保護範囲は、添付の特許請求の範囲によって決まる。
【符号の説明】
【００４５】
１  表示装置
２  コンピューター
４  入力装置
２０  記憶装置
２１  情報
２２  記憶モジュール
２３  デコーディングモジュール
２４  中央演算処理装置
【図１】
2011244447.tif 000006
【図２】
2011244447.tif 000007
【図３】
2011244447.tif 000008
【図４】
2011244447.tif 000009
【図５】
2011244447.tif 000010
【図６】
2011244447.tif 000011
【図７】
2011244447.tif 000012