(57)【要約】【課題】ハフマン符号長リストの入力とハフマンテーブルの生成とを順次実行する場合と比べて、その入力から生成完了までに要する時間を短くする。【解決手段】分離部１０は、圧縮データ４０をハフマン符号長リストとハフマン符号列とに分離する。ハフマン符号長リストは各シンボルの符号長を示すリストである。ハフマンテーブル生成部２０は、処理対象となる１シンボル分の符号長が分離部１０から入力される度に、当該符号長に基づいてハフマンテーブルにおけるインデックス番号を決定し、ハフマンテーブル中の当該インデックス番号に対応する位置に処理対象のシンボルを設定する。ハフマンテーブル生成部２０は、１シンボル分の符号長が入力される度に上記の処理を実行し、これにより、ハフマンテーブルにおける個々のシンボルを符号長の小さい順に順次並び変えてハフマンテーブルを順次更新する。【選択図】図１
2016139958.tif 000002
【特許請求の範囲】
【請求項１】
ハフマン符号化処理によって生成されたハフマン符号列と、各シンボルの符号長を示すハフマン符号長リストと、を含む圧縮データを受け付ける受付手段と、
インデックス番号とシンボルとの対応付けを示し前記圧縮データの復号処理に使用されるハフマンテーブルを生成する生成手段であって、前記ハフマン符号長リストに含まれる個々のシンボルの符号長を１シンボルずつ前記受付手段から取得し、前記受付手段から処理対象となる１シンボル分の符号長が入力される度に、当該符号長に基づいてハフマンテーブルにおけるインデックス番号を決定し、ハフマンテーブルにおいて当該インデックス番号に対応する設定位置に前記処理対象のシンボルを設定し、ハフマンテーブルにおける個々のシンボルを符号長の小さい順に順次並び変えていき、これによりハフマンテーブルを順次更新する生成手段と、
を有する情報処理装置。
【請求項２】
前記生成手段は、ハフマンテーブルにおいて、前記処理対象のシンボルの符号長に対応するインデックス番号以降の各インデックス番号に対応する設定位置に設定されている各シンボルを、それぞれ１つ後の順番のインデックス番号に対応する設定位置に再設定し、これにより、ハフマンテーブルにおける個々のシンボルの並び順を変えてハフマンテーブルを更新する、
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
符号長毎のインデックス番号を示す設定位置情報を記憶する記憶手段と、
前記生成手段によって１シンボル分の処理が実行される度に、前記設定位置情報において、前記処理対象のシンボルの符号長以上の各符号長に対応する各インデックス番号をインクリメントし、これにより前記設定位置情報を順次更新する設定位置更新手段と、
を更に有し、
前記生成手段は、前記処理対象のシンボルの符号長に対応するインデックス番号を、前記記憶手段に記憶されている前記設定位置情報に基づいて決定する、
ことを特徴とする請求項１又は請求項２に記載の情報処理装置。
【請求項４】
前記ハフマン符号長リスト中の各符号長の出現数をカウントするカウント手段と、
前記ハフマン符号列と前記出現数とに基づいて復号用インデックス番号を決定し、当該復号用インデックス番号に対応するシンボルを、前記生成手段によって生成されたハフマンテーブルから抽出して出力する復号手段と、
を更に有する、
ことを特徴とする請求項１から請求項３のいずれか一項に記載の情報処理装置。
【請求項５】
コンピュータを、
ハフマン符号化処理によって生成されたハフマン符号列と、各シンボルの符号長を示すハフマン符号長リストと、を含む圧縮データを受け付ける受付手段と、
インデックス番号とシンボルとの対応付けを示し前記圧縮データの復号処理に使用されるハフマンテーブルを生成する生成手段であって、前記ハフマン符号長リストに含まれる個々のシンボルの符号長を１シンボルずつ前記受付手段から取得し、前記受付手段から処理対象となる１シンボル分の符号長が入力される度に、当該符号長に基づいてハフマンテーブルにおけるインデックス番号を決定し、ハフマンテーブルにおいて当該インデックス番号に対応する設定位置に前記処理対象のシンボルを設定し、ハフマンテーブルにおける個々のシンボルを符号長の小さい順に順次並び変えていき、これによりハフマンテーブルを順次更新する生成手段と、
として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置及びプログラムに関する。
【背景技術】
【０００２】
デフレート圧縮データフォーマット（ＲＦＣ１９５１）に代表されるような圧縮データフォーマットに従った圧縮データストリームには、一般的に、ハフマン符号長リストとハフマン符号列との組（ブロック）が複数個含まれている。
【０００３】
特許文献１には、ハフマン符号の復号処理を実行する場合において、２分木探索法よりも、データの読み出し回数及び判定処理回数を少なくする方法が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００９−２６７８１３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ハフマン符号長リストとハフマン符号列との組（ブロック）が複数個含まれているような圧縮データストリームを伸長処理する場合、ハフマン復号処理に先立ってハフマン符号長リストを基にハフマンテーブルを生成する処理を、ブロックの個数分、実行する必要がある。ブロックの個数を増やすほどデータ圧縮率が向上するが、その反面、ハフマンテーブルの生成回数が増大する。それ故、情報処理装置へのハフマン符号長リストの入力と、情報処理装置によるハフマンテーブルの生成処理と、を順次実行する場合、ブロックの個数が増大するほど、伸長処理に要する時間が増大する問題が生じる。
【０００６】
本発明の目的は、ハフマン符号長リストの入力とハフマンテーブルの生成とを順次実行する場合と比べて、ハフマン符号長リストの入力からハフマンテーブルの生成完了までに要する時間を短くすることである。
【課題を解決するための手段】
【０００７】
請求項１に係る発明は、ハフマン符号化処理によって生成されたハフマン符号列と、各シンボルの符号長を示すハフマン符号長リストと、を含む圧縮データを受け付ける受付手段と、インデックス番号とシンボルとの対応付けを示し前記圧縮データの復号処理に使用されるハフマンテーブルを生成する生成手段であって、前記ハフマン符号長リストに含まれる個々のシンボルの符号長を１シンボルずつ前記受付手段から取得し、前記受付手段から処理対象となる１シンボル分の符号長が入力される度に、当該符号長に基づいてハフマンテーブルにおけるインデックス番号を決定し、ハフマンテーブルにおいて当該インデックス番号に対応する設定位置に前記処理対象のシンボルを設定し、ハフマンテーブルにおける個々のシンボルを符号長の小さい順に順次並び変えていき、これによりハフマンテーブルを順次更新する生成手段と、を有する情報処理装置である。
【０００８】
請求項２に係る発明は、前記生成手段は、ハフマンテーブルにおいて、前記処理対象のシンボルの符号長に対応するインデックス番号以降の各インデックス番号に対応する設定位置に設定されている各シンボルを、それぞれ１つ後の順番のインデックス番号に対応する設定位置に再設定し、これにより、ハフマンテーブルにおける個々のシンボルの並び順を変えてハフマンテーブルを更新する、ことを特徴とする請求項１に記載の情報処理装置である。
【０００９】
請求項３に係る発明は、符号長毎のインデックス番号を示す設定位置情報を記憶する記憶手段と、前記生成手段によって１シンボル分の処理が実行される度に、前記設定位置情報において、前記処理対象のシンボルの符号長以上の各符号長に対応する各インデックス番号をインクリメントし、これにより前記設定位置情報を順次更新する設定位置更新手段と、を更に有し、前記生成手段は、前記処理対象のシンボルの符号長に対応するインデックス番号を、前記記憶手段に記憶されている前記設定位置情報に基づいて決定する、ことを特徴とする請求項１又は請求項２に記載の情報処理装置である。
【００１０】
請求項４に係る発明は、前記ハフマン符号長リスト中の各符号長の出現数をカウントするカウント手段と、前記ハフマン符号列と前記出現数とに基づいて復号用インデックス番号を決定し、当該復号用インデックス番号に対応するシンボルを、前記生成手段によって生成されたハフマンテーブルから抽出して出力する復号手段と、を更に有する、ことを特徴とする請求項１から請求項３のいずれか一項に記載の情報処理装置である。
【００１１】
請求項５に係る発明は、コンピュータを、ハフマン符号化処理によって生成されたハフマン符号列と、各シンボルの符号長を示すハフマン符号長リストと、を含む圧縮データを受け付ける受付手段と、インデックス番号とシンボルとの対応付けを示し前記圧縮データの復号処理に使用されるハフマンテーブルを生成する生成手段であって、前記ハフマン符号長リストに含まれる個々のシンボルの符号長を１シンボルずつ前記受付手段から取得し、前記受付手段から処理対象となる１シンボル分の符号長が入力される度に、当該符号長に基づいてハフマンテーブルにおけるインデックス番号を決定し、ハフマンテーブルにおいて当該インデックス番号に対応する設定位置に前記処理対象のシンボルを設定し、ハフマンテーブルにおける個々のシンボルを符号長の小さい順に順次並び変えていき、これによりハフマンテーブルを順次更新する生成手段と、として機能させるプログラムである。
【発明の効果】
【００１２】
請求項１，２，５に係る発明によると、ハフマン符号長リストの入力とハフマンテーブルの生成とを順次実行する場合と比べて、ハフマン符号長リストの入力からハフマンテーブルの生成完了までに要する時間が短くなる。
【００１３】
請求項３に係る発明によると、ハフマンテーブルにおいて個々のシンボルが符号長の小さい順に並べられる。
【００１４】
請求項４に係る発明によると、ハフマンテーブルを用いた復号処理が実現される。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施形態に係る情報処理装置を示すブロック図である。
【図２】圧縮データの構造の一例を示す図である。
【図３】ハフマン符号長リストのフォーマットの一例を示す図である。
【図４】伸長処理の流れを説明するための図である。
【図５】ハフマン符号長リスト及びハフマン符号列の一例を示す図である。
【図６】ハフマンテーブル生成処理を説明するための図である。
【図７】ハフマンテーブルの一例を示す図である。
【図８】符号出現数情報の一例を示す図である。
【図９】本実施形態に係る情報処理装置による処理の一例を示すフローチャートである。
【図１０】復号処理を説明するための図である。
【図１１】復号処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１６】
図１には、本発明の実施形態に係る情報処理装置の一例が示されている。本実施形態に係る情報処理装置は、ハフマン符号化処理によって圧縮された圧縮データ４０を受け、その圧縮データ４０を復号して伸長データ５０を生成する機能を備えている。なお、ハフマン符号化とは、出現数の多いシンボル（記号）ほど符号を短くする周知の圧縮技術である。ハフマン符号化によると、出現数の多いシンボルほど符号長が短くなり、出現数の少ないシンボルほど符号長が長くなる。
【００１７】
圧縮データ４０には、ハフマン符号長リストとハフマン符号列とが含まれている。ハフマン符号長リストは、各シンボルの符号長が記述されたリストである。つまり、ハフマン符号長リストは、個々のシンボルを示すシンボル値と個々のシンボルの符号長（ｂｉｔ数）との対応関係を示すリストである。符号長は、ハフマン符号化処理によって生成された符号値のｂｉｔ数である。ハフマン符号列は、ハフマン符号化処理によって生成された符号値の列である。本実施形態に係る情報処理装置は、ハフマン符号長リストに基づいてハフマンテーブルを生成し、そのハフマンテーブルを用いてハフマン符号列を復号する機能を備えている。ハフマンテーブルは、インデックス番号とシンボル値との対応関係を示すルックアップテーブル（ＬＵＴ）である。復号処理においては、インデックス番号が決定され、そのインデックス番号に対応するシンボル値がハフマンテーブルから抽出される。これにより、ハフマン符号列が復号される。
【００１８】
また、ハフマン符号長リストとハフマン符号列との組（ブロック）が形成され、複数のブロックが圧縮データ４０に含まれている場合がある。この場合、ブロック毎に復号処理が行われる。もちろん、ハフマン符号長リストとハフマン符号列との組が１つのみであり、その１つの組が圧縮データ４０に含まれていてもよい。以下、情報処理装置の各部について説明する。
【００１９】
分離部１０は圧縮データ４０を受け、圧縮データ４０に含まれるハフマン符号長リストとハフマン符号列とを分離し、ハフマン符号長リストをハフマンテーブル生成部２０に出力する。本実施形態では、分離部１０は、ハフマン符号長リストに含まれるシンボル値と符号長値（符号長を示す値）とを１シンボル毎に順次、ハフマンテーブル生成部２０に出力する。後述するように、ハフマンテーブル生成部２０は、１シンボル毎に処理を行うことにより、シンボル値と符号長値とに基づいてハフマンテーブルを生成する。その生成処理が完了した場合、分離部１０は、ハフマン符号列をインデックス決定部１２に出力する。
【００２０】
圧縮データ４０に複数のブロックが含まれている場合、分離部１０は、ブロック毎に順次処理を実行する。具体的には、分離部１０は、１番目のブロックを構成するハフマン符号長リストをハフマンテーブル生成部２０に出力する。そのハフマン符号長リストに基づくハフマンテーブルの生成処理が完了した場合、つまり、１ブロック目のハフマンテーブルの生成処理が完了した場合、分離部１０は、１番目のブロックを構成するハフマン符号列をインデックス決定部１２に出力する。そのハフマン符号列に対する復号処理が完了した場合、つまり、１ブロック目のハフマン符号列に対する復号処理が完了した場合、分離部１０は、２番目のブロックを構成するハフマン符号長リストをハフマンテーブル生成部２０に出力する。以降についても同様の処理が実行される。なお、ハフマン符号列の復号処理は、後述するインデックス決定部１２及びＬＵＴ部１４によって実行される。また、各ブロックの復号処理の完了は、終端検知部１６によって検知される。
【００２１】
インデックス決定部１２は、分離部１０から供給されたハフマン符号列と、後述するハフマンテーブル生成部２０から供給される符号長出現数情報と、に基づいて、ＬＵＴ部１４に出力するインデックス番号を決定する。インデックス決定部１２による処理については、後で詳しく説明する。
【００２２】
ＬＵＴ部１４は、ルックアップテーブルとしてのハフマンテーブルを格納しており、ハフマンテーブルを参照することにより、インデックス決定部１２から供給されるインデックス番号に対応するシンボル値を終端検知部１６に出力する。ハフマンテーブルを構成するデータ（シンボル値）は、後述するハフマンテーブル生成部２０によって設定される。ＬＵＴ部１４による処理については、後で詳しく説明する。
【００２３】
終端検知部１６は、ＬＵＴ部１４から出力されるシンボル値を監視する。シンボル値が１ブロックの終端のシンボル値に該当しない場合、終端検知部１６は、そのシンボル値を伸長データ５０として出力する。一方、シンボル値が１ブロックの終端のシンボル値に該当する場合、終端検知部１６は、そのシンボル値を伸長データ５０として出力するとともに、終端を検知したことを示す終端検知情報を分離部１０に出力する。分離部１０は、終端検知情報を受けると、次のブロックを構成するハフマン符号長リストをハフマンテーブル生成部２０に出力する。
【００２４】
ハフマンテーブル生成部２０は、符号出現数記憶部２２、設定位置記憶部２４及び生成制御部２６を含み、ハフマン符号長リストに基づいてハフマンテーブル（ルックアップテーブル）を生成する。生成されたハフマンテーブルはＬＵＴ部１４に格納される。本実施形態では、ハフマンテーブル生成部２０は、ハフマン符号長リストを１シンボル分毎に処理することにより、１シンボル毎にハフマンテーブルを順次更新していく。つまり、ハフマン符号長リストに含まれる個々のシンボルのシンボル値及び符号長値が、分離部１０からハフマンテーブル生成部２０に１シンボル分ずつ順次入力され、ハフマンテーブル生成部２０は、１シンボル分ずつ処理を実行することにより、ハフマンテーブルを順次更新していく。これにより、ＬＵＴ部１４に格納されているハフマンテーブルが順次更新されていく。圧縮データ４０に複数のブロックが含まれている場合、ハフマンテーブル生成部２０は、ブロック毎にハフマンテーブルを生成する。以下、ハフマンテーブル生成部２０に含まれる各部の機能について説明する。
【００２５】
符号出現数記憶部２２は、ハフマン符号長リストに含まれている個々の符号長の出現数を示す符号出現数情報を記憶する。この情報は、１シンボル分の処理毎に生成制御部２６によって更新される。
【００２６】
設定位置記憶部２４は、ハフマンテーブルにおいてシンボル値が設定される位置を示す設定位置情報（インデックス番号）を記憶する。インデックス番号は、シンボルの符号長（ｂｉｔ数）に対応している。すなわち、符号長毎にルックアップテーブルの設定位置が決められている。設定位置情報は、１シンボル分の処理毎に生成制御部２６によって更新される。
【００２７】
生成制御部２６は、ハフマン符号長リストに含まれる個々のシンボルのシンボル値を符号長の小さい順に順次並び変えることにより、ハフマンテーブルを順次生成していく。ハフマンテーブルにおいては、インデックス番号とシンボル値とが対応付けられており、大きいインデックス番号ほど符号長の大きいシンボル値が対応付けられる。本実施形態では、生成制御部２６は、１シンボル分のシンボル値及び符号長値が分離部１０から入力される度に、１シンボル毎にハフマンテーブル中の設定位置（インデックス番号）を決定し、ハフマンテーブルにおける個々のシンボル値の並び順を順次変えていく。具体的には、生成制御部２６は、処理対象となる１シンボルのシンボル値及び符号長値が分離部１０から入力されると、設定位置記憶部２４に記憶されている設定位置情報を参照することにより、処理対象のシンボルの符号長に基づいて、ハフマンテーブル中の設定位置（インデックス番号）を決定し、その設定位置に当該シンボルのシンボル値を設定する。このとき、生成制御部２６は、ハフマンテーブルにおいて処理対象のシンボルの符号長に対応するインデックス番号から最終インデックス番号までの各設定位置に設定されている各シンボル値を、元々のインデックス番号に＋１加算した新たなインデックス番号に対応する設定位置に再設定する。つまり、生成制御部２６は、ハフマンテーブルにおいて、処理対象のシンボルの符号長に対応するインデックス番号以降の各インデックス番号に対応する設定位置に設定されている各シンボル値を、元々のインデックス番号よりも、それぞれ１つ後の順番のインデックス番号に対応する設定位置に再設定する。
【００２８】
また、生成制御部２６は、ハフマン符号長リストに含まれる個々の符号長の出現数をカウントし、符号出現数記憶部２２に記憶されている符号出現数情報を更新する。本実施形態では、生成制御部２６は、１シンボル分の処理を行う度に符号長の出現数をカウントし、符号出現数情報を更新する。
【００２９】
また、生成制御部２６は、設定位置記憶部２４に記憶されている設定位置情報において、処理対象のシンボルの符号長以上の符号長に対応する各インデックス番号を１つインクリメントする。これにより、設定位置情報が更新される。本実施形態では、生成制御部２６は、１シンボル分の処理を行う度にインクリメント処理を行い、設定位置情報を更新する。
【００３０】
生成制御部２６は、１ブロックのハフマン符号長リストに含まれる全シンボルを対象にして、１シンボル分毎に上記の処理を行う。全シンボル分の処理が完了することによって、そのブロックのハフマンテーブル生成処理が完了する。１ブロック分のハフマンテーブルの生成が完了した場合、生成制御部２６は、ハフマンテーブル生成完了を示す情報を分離部１０に出力する。この情報を受けた分離部１０は、そのブロックに含まれるハフマン符号列をインデックス決定部１２に出力する。
【００３１】
図２には、圧縮データ４０の構造の一例が示されている。図２に示す例では、圧縮データ４０は、複数のブロック（ブロック４０Ａ，４０Ｂ，・・・，４０Ｍ）を含む。個々のブロックは、ハフマン符号長リストとハフマン符号列とによって構成されている。この圧縮データ４０を伸長処理する場合、分離部１０は、１番目のブロック４０Ａに含まれるハフマン符号長リストをハフマンテーブル生成部２０に出力する。このとき、分離部１０は、シンボル値と符号長値とを１シンボル毎に順次、ハフマンテーブル生成部２０に出力する。ハフマンテーブル生成部２０は、分離部１０から出力されるシンボル値と符号長値とに基づき、１シンボル毎にハフマンテーブルを順次生成していく。分離部１０からハフマンテーブル生成部２０に対して、ブロック４０Ａの全シンボル分のシンボル値及び符号長値の入力が完了し、ハフマンテーブル生成部２０において全シンボル分の処理が完了すると、ブロック４０Ａについてのハフマンテーブルの生成処理が完了する。このハフマンテーブルはＬＵＴ部１４に格納される。ハフマンテーブルの生成処理が完了した場合、分離部１０は、ブロック４０Ａに含まれるハフマン符号列をインデックス決定部１２に出力する。インデックス決定部１２によってインデックス番号が決定され、ＬＵＴ部１４においてハフマンテーブルが参照されることにより、そのインデックス番号に対応するシンボル値が出力される。このようにして、ブロック４０Ａに対する復号処理が実行される。ブロック４０Ａに対する復号処理が完了した場合、分離部１０は、２番目のブロック４０Ｂに含まれるハフマン符号長リストをハフマンテーブル生成部２０に出力する。以降、１番目のブロック４０Ａと同様の処理が繰り返される。このようにして、ブロック４０Ａ，４０Ｂ，・・・，４０Ｍに含まれるハフマン符号列が順次復号され、これにより伸長データ５０が生成される。
【００３２】
なお、図２に示す例では、複数のブロックが圧縮データ４０に含まれているが、もちろん、圧縮データ４０に１つのブロックのみが含まれていてもよい。
【００３３】
図３には、ハフマン符号長リストのフォーマットの一例が示されている。「Ｓｙｍｂｏｌ＃１」、・・・、「Ｓｙｍｂｏｌ＃Ｍ」は、シンボル値を表している。各シンボル値には符号長（ｂｉｔ数）が対応付けられている。
【００３４】
図４には、伸長処理の流れが示されている。横軸は時間軸である。符号６０（図面下側）は、本実施形態に係る処理のシーケンスを示しており、符号７０（図面上側）は、比較例に係る処理のシーケンスを示している。本実施形態では、ブロック４０Ａのハフマン符号長リストに含まれるシンボル値及び符号長値が、１シンボル毎に順次、分離部１０からハフマンテーブル生成部２０に入力される。ハフマンテーブル生成部２０は、１シンボル分のシンボル値及び符号長値が入力される度に、ブロック４０Ａのハフマンテーブルを順次生成していく。これにより、ハフマンテーブル生成部２０へのハフマン符号長リストの入力処理と、ハフマンテーブル生成部２０によるハフマンテーブルの生成処理と、が並列して実行される。ブロック４０Ａのハフマンテーブルの生成が完了すると、ブロック４０Ａのハフマン符号列が分離部１０からインデックス決定部１２に入力される。そして、インデックス番号の決定、ハフマンテーブル（ＬＵＴ）の参照、及び、ハフマンテーブルからのシンボル値の出力、が順次実行され、これにより、ブロック４０Ａの伸長データが生成されていく。ブロック４０Ａに対する処理が完了すると、次に、ブロック４０Ｂに対して同様の処理が実行される。
【００３５】
一方、比較例においては、ブロック４０Ａのハフマン符号長リストに含まれる全シンボル値及び全符号長値が情報処理装置に入力され、その入力が完了した後に、ハフマンテーブルの生成処理が開始される。つまり、全シンボル値及び全符号長値の入力処理と、ハフマンテーブルの生成処理と、が順次実行される。
【００３６】
本実施形態と比較例とを比べると、本実施形態では並列処理を実行しているため、比較例よりも早い段階でハフマンテーブルの生成処理が完了し、その結果、伸長処理に要する時間が短くなる。図４に示す例で説明すると、比較例ではブロック４０Ａに対する伸長処理が完了していない段階で、本実施形態によると、ブロック４０Ｂのハフマンテーブルの生成処理が開始されている。
【００３７】
次に、ハフマンテーブル生成処理について具体例を挙げて説明する。図５には、ハフマン符号長リスト及びハフマン符号列の一例が示されている。ハフマン符号長リストにおいては、シンボル値と符号長（ｂｉｔ数）とが対応付けられている。符号長は、ハフマン符号化処理によって生成された符号値のｂｉｔ数である。例えば、シンボル値Ａの符号長は４ｂｉｔ長である。また、シンボル値Ａの符号値（ハフマン符号化処理によって生成された符号値）は、２進数の表現形式で「１０００」であり、１０進数の表現形式で「８」である。本実施形態では、シンボル値Ａ，Ｂ，Ｃ，・・・の順番に従って、シンボル値及びその符号長値が、分離部１０からハフマンテーブル生成部２０に順次入力される。
【００３８】
図６には、ハフマンテーブル生成処理の手順の一例が示されている。図６には、ハフマン符号長リスト、ＬＵＴ（ハフマンテーブル）及び設定位置情報（インデックス番号）が示されている。ハフマン符号長リストは、図５に示されているリストと同じものである。ＬＵＴは、生成制御部２６によって順次生成されるテーブルである。ＬＵＴにおいてはインデックス番号（０，１，２，・・・）が規定されており、そのインデックス番号に対応する位置にシンボル値が設定（挿入）される。ＬＵＴ中の「×」は、シンボル値が入力されていない設定位置である。設定位置情報（ＩＮＳＰＯＳ［１］，ＩＮＳＰＯＳ［２］，・・・）は、ＬＵＴにおいてシンボル値が設定される位置に対応するインデックス番号を示す情報である。設定位置情報においては、符号長毎に設定位置が決定されている。例えば、ＩＮＳＰＯＳ［１］は、１ビット長のシンボル値の設定位置に対応するインデックス番号を示しており、ＩＮＳＰＯＳ［２］は、２ビット長のシンボル値の設定位置に対応するインデックス番号を示している。他のＩＮＳＰＯＳにおいても同様である。例えば、インデックス番号が「０」の場合、ＬＵＴにおいてインデックス番号「０」に対応する位置にシンボル値が設定される。図６において、縦軸が時間軸であり、上から下（時点０〜８）にかけて時間が流れているものとする。時点０は初期段階である。この時点では、全インデックス番号は「０」に設定されており、また、符号出現数も「０」に設定されている。以下、ハフマンテーブル生成処理について時系列に沿って説明する。
【００３９】
まず、時点１の段階で、シンボル値Ａ及びその符号長値「４」が、分離部１０からハフマンテーブル生成部２０に入力される。時点０の設定位置情報を参照すると、符号長値「４」に対応するＩＮＳＰＯＳ［４］は「０」を示している（四角のマークで囲った部分を参照）。従って、生成制御部２６は、ＬＵＴにおいてインデックス番号「０」に対応する位置にシンボル値Ａを設定する。そして、生成制御部２６は、設定位置情報において、符号長値「４」以上の符号長値に対応するインデックス番号を１つインクリメントする。時点１の段階では、ＩＮＳＰＯＳ［４］、ＩＮＳＰＯＳ［５］及びＩＮＳＰＯＳ［６］の値が１つインクリメントされて「１」になっている。これにより、次の時点２で入力される符号長値が「４」以上の場合、そのシンボル値は、インデックス番号「１」に対応する位置に設定されることになる。つまり、次の時点２で入力される符号長値が「４」以上の場合、そのシンボル値は、時点１で入力されたシンボル値Ａに対するインデックス番号よりも大きいインデックス番号に対応する位置に設定されることになる。これにより、個々のシンボル値が符号長の小さい順に並び変えられる。このように、インデックス番号をインクリメントすることにより、先の時点で入力されたシンボル値の符号長以上の符号長を有するシンボル値が後の時点で入力された場合に、後の時点で入力されたシンボル値が、先の時点で入力されたシンボル値よりも後のインデックス番号の位置に設定される。なお、時点０の設定位置情報においては、いずれのＩＮＳＰＯＳも「０」を示している。それ故、時点１で入力されたシンボル値Ａは、ＬＵＴにおいてインデックス番号「０」の位置に設定されることになる。
【００４０】
次に、時点２の段階で、シンボル値Ｂ及びその符号長値「３」が、分離部１０からハフマンテーブル生成部２０に入力される。時点１の設定位置情報を参照すると、符号長値「３」に対応するＩＮＳＰＯＳ［３］は「０」を示している（四角のマークで囲った部分を参照）。従って、シンボル値Ｂは、ＬＵＴにおいてインデックス番号「０」に対応する位置に設定される。このとき、生成制御部２６は、インデックス番号「０」以降の各インデックス番号に対応する設定位置に設定されている各シンボル値を、元々のインデックス番号に＋１加算した新たなインデックス番号に対応する設定位置に再設定する。つまり、生成制御部２６は、インデックス番号「０」以降の各インデックス番号に対応する設定位置に設定されている各シンボル値を、元々のインデックス番号よりも、それぞれ１つ後の順番のインデックス番号に対応する設定位置に再設定する。図６に示す例では、インデックス番号「０」に対応する位置にシンボル値Ａが既に設定されている。この場合、シンボル値Ａは、インデックス番号「０＋１＝１」に対応する位置に移動させられる。上記の処理の結果、時点２の段階では、インデックス番号「０」の位置にシンボル値Ｂ（符号長３ｂｉｔ）が設定されており、インデックス番号「１」の位置にシンボル値Ａ（符号長４ｂｉｔ）が設定されている。そして、設定位置情報において、符号長値「３」以上の符号長値に対応するインデックス番号が１つインクリメントされる。時点２の段階では、ＩＮＳＰＯＳ［３］〜［６］の値が１つインクリメントされている。その結果、ＩＮＳＰＯＳ［３］の値が「１」になっており、ＩＮＳＰＯＳ［４］〜［６］の値が「２」になっている。
【００４１】
次に、時点３の段階で、シンボル値Ｃ及びその符号長値「５」が、分離部１０からハフマンテーブル生成部２０に入力される。時点２の設定位置情報を参照すると、符号長値「５」に対応するＩＮＳＰＯＳ［５］は「２」を示している（四角のマークで囲った部分）。従って、シンボル値Ｃは、ＬＵＴにおいてインデックス番号「２」に対応する位置に設定される。シンボル値Ａ，Ｂは、インデックス番号「２」よりも小さいインデックス番号「０」及びインデックス番号「１」に対応する位置にそれぞれ設定されている。それ故、シンボル値Ａ，Ｂの設定位置は変わらず維持される。上記の処理の結果、時点３の段階では、インデックス番号「０」の位置にシンボル値Ｂ（符号長３ｂｉｔ）が設定されており、インデックス番号「１」の位置にシンボル値Ａ（符号長４ｂｉｔ）が設定されており、インデックス番号「２」の位置にシンボル値Ｃ（符号長５ｂｉｔ）が設定されている。そして、設定位置情報において、符号長値「５」以上の符号長値に対応するインデックス番号が１つインクリメントされる。時点３の段階では、ＩＮＳＰＯＳ［５］及びＩＮＳＰＯＳ［６］の値が１つインクリメントされて「３」になっている。
【００４２】
時点４以降についても同様に１シンボル毎に処理が実行され、これによりハフマンテーブルが順次生成されていく。
【００４３】
例えば、時点８の段階では、シンボル値Ｈ及びその符号長値「３」が、分離部１０からハフマンテーブル生成部２０に入力される。時点７の設定位置情報を参照すると、符号長値「３」に対応するＩＮＳＰＯＳ［３］は「２」を示している。従って、シンボル値Ｈは、ＬＵＴにおいてインデックス番号「２」に対応する位置に設定される。このとき、インデックス番号「６」の位置に設定されていたシンボル値Ｇは、インデックス番号「７」の位置に移動させられる。同様に、インデックス番号「５」の位置に設定されていたシンボル値Ｆは、インデックス番号「６」の位置に移動させられる。インデックス番号「４」の位置に設定されていたシンボル値Ｅは、インデックス番号「５」の位置に移動させられる。インデックス番号「３」の位置に設定されていたシンボル値Ｃは、インデックス番号「４」の位置に移動させられる。インデックス番号「２」の位置に設定されていたシンボル値Ａは、インデックス番号「３」の位置に移動させられる。インデックス番号「０」及びインデックス番号「１」にそれぞれ設定されているシンボル値Ｄ，Ｂの設定位置は変わらず維持される。そして、設定位置情報において、符号長値「３」以上の符号長値に対応するインデックス番号が１つインクリメントされる。時点８の段階では、ＩＮＳＰＯＳ［３］〜［６］の値が１つインクリメントされている。
【００４４】
図７には、時点８の段階におけるハフマンテーブルの一例が示されている。時点８の段階では、以下のようにシンボル値が設定されている。
インデックス番号「０」の位置にシンボル値Ｄ（符号長２ｂｉｔ）が設定されている。
インデックス番号「１」の位置にシンボル値Ｂ（符号長３ｂｉｔ）が設定されている。
インデックス番号「２」の位置にシンボル値Ｈ（符号長３ｂｉｔ）が設定されている。
インデックス番号「３」の位置にシンボル値Ａ（符号長４ｂｉｔ）が設定されている。
インデックス番号「４」の位置にシンボル値Ｃ（符号長５ｂｉｔ）が設定されている。
インデックス番号「５」の位置にシンボル値Ｅ（符号長５ｂｉｔ）が設定されている。
インデックス番号「６」の位置にシンボル値Ｆ（符号長５ｂｉｔ）が設定されている。
インデックス番号「７」の位置にシンボル値Ｇ（符号長６ｂｉｔ）が設定されている。
【００４５】
以上のように、ハフマンテーブルにおいては、符号長の小さい順にシンボル値が配列される。このハフマンテーブルはＬＵＴ部１４に格納され、復号処理の際に利用される。
【００４６】
図７に示す例では、インデックス番号「１」及び「２」に、符号長が３ｂｉｔのシンボル値が設定されている。また、インデックス番号「４」、「５」及び「６」に、符号長が５ｂｉｔのシンボル値が設定されている。
【００４７】
また、生成制御部２６は、個々の符号長の出現数をカウントする。図８には、その出現数の一例が示されている。例えば、符号長が１ｂｉｔのシンボル値の出現数は「０」である。符号長が２ｂｉｔのシンボル値の出現数は「１」である。出現数を示す符号出現数情報は、符号出現数記憶部２２に記憶される。
【００４８】
次に、図９に示されているフローチャートを参照して、ハフマンテーブル生成処理の流れを説明する。まず、生成制御部２６は、符号出現数記憶部２２に記憶されている符号出現数、及び、設定位置記憶部２４に記憶されている設定位置情報を初期化する（Ｓ０１）。これにより、符号化出現数、及び、設定位置に対応するインデックス番号が、「０」に設定される。次に、１シンボル分のシンボル値及び符号長値が分離部１０から生成制御部２６に入力されると（Ｓ０２）、生成制御部２６は、その符号長の出現数を１つインクリメントし（Ｓ０３）、その符号長に対応するインデックス番号を設定位置記憶部２４から取得する（Ｓ０４）。生成制御部２６は、ＬＵＴ（ハフマンテーブル）において、そのインデックス番号以降の各インデックス番号に対応する設定位置に設定されている各シンボル値を、元々のインデックス番号よりも、それぞれ１つ後の順番のインデックス番号に対応する設定位置に移動させる（Ｓ０５）。そして、生成制御部２６は、ＬＵＴにおいて、取得されたインデックス番号に対応する位置に処理対象のシンボル値を設定する（Ｓ０６）。また、生成制御部２６は、処理対象のシンボルの符号長以上の符号長に対応するインデックス番号を１つインクリメントし、設定位置記憶部２４に記憶されている設定位置情報を更新する（Ｓ０７）。ハフマン符号長リストに含まれる全シンボルについてＳ０１〜Ｓ０７の処理が完了した場合（Ｓ０８，Ｙｅｓ）、ハフマンテーブル生成処理は終了する。生成されたハフマンテーブルはＬＵＴ部１４に格納される。全シンボルについてＳ０１〜Ｓ０７の処理が完了していない場合（Ｓ０８，Ｎｏ）、処理はステップＳ０１に戻る。この場合、次のシンボルを対象にしてＳ０１〜Ｓ０７の処理が実行される。
【００４９】
以上のように、本実施形態によると、シンボル値及び符号長値が１シンボル毎にハフマンテーブル生成部２０に順次入力され、１シンボル分ずつハフマンテーブルが順次生成されていく。これにより、ハフマンテーブル生成部２０に対して全シンボル分のシンボル値及び符号長値の入力が完了し、最後のシンボルに対する処理が終了した時点で、ハフマンテーブルの生成処理が完了する。それ故、ハフマン符号長リストの入力処理とハフマンテーブルの生成処理とを順次実行する場合（全シンボルの入力処理が完了してからハフマンテーブルの生成処理を開始する場合）と比較して、早い段階でハフマンテーブルの生成処理が完了し、その結果、伸長処理に要する時間が短くなる。
【００５０】
次に、インデックス決定部１２及びＬＵＴ部１４による復号処理について説明する。この復号処理は、一般的なハフマン復号処理によって実現される。復号処理においては、第１段階の処理として、インデックス決定部１２は、符号出現数情報に基づいて、「各符号長の最初の符号値」と、「ハフマンテーブルにおける各符号長の開始インデックス番号」と、を求める。
【００５１】
ここで、「最初の符号値」は、同一符号長の複数のシンボル値がハフマンテーブルに設定されている場合において、それら複数のシンボル値の中で最小のインデックス番号に設定されているシンボル値の符号値である。ハフマンテーブルにおいて、同一符号長のシンボル値が１つのみ存在する場合、そのシンボル値の符号値が「最初の符号値」である。
【００５２】
また、「開始インデックス番号」は、同一符号長の複数のシンボル値がハフマンテーブルに設定されている場合において、それら複数のシンボル値が設定されている複数のインデックス番号の中の最小のインデックス番号である。ハフマンテーブルにおいて、同一符号長のシンボル値が１つのみ存在する場合、そのシンボル値が設定されているインデックス番号が「開始インデックス番号」である。
【００５３】
図７に示す例で説明すると、符号長が３ｂｉｔである２つのシンボル値（シンボル値Ｂ，Ｈ）が、インデックス番号「１」及び「２」に設定されている。この場合、符号長が３ｂｉｔのシンボル値の「開始インデックス番号」は、「１」である。「最初の符号値」は、インデックス番号「１」に設定されているシンボル値Ｂの符号値（１０進数の表現形式で「２」、２進数の表現形式で「０１０」）である。
【００５４】
また、符号長が５ｂｉｔである３つのシンボル値（シンボル値Ｃ，Ｅ，Ｆ）が、インデックス番号「４」、「５」及び「６」に設定されている。この場合、符号長が５ｂｉｔのシンボル値の「開始インデックス番号」は、「４」である。「最初の符号値」は、インデックス番号「４」に設定されているシンボル値Ｃの符号値（１０進数の表現形式で「１８」、２進数の表現形式で「１００１０」）である。
【００５５】
また、符号長が２ｂｉｔのシンボル値Ｄがインデックス番号「０」に設定されている。この場合、「開始インデックス番号」は「０」であり、「最初の符号値」は、シンボル値Ｄの符号値（１０進数の表現形式で「０」、２進数の表現形式で「００」）である。
【００５６】
インデックス決定部１２は、以下の式（１）に従って「符号長ｎの最初の符号値」を求める。ｎは整数である。
（符号長ｎの最初の符号値）＝
｛（符号長（ｎ−１）の最初の符号値）＋（符号長（ｎ−１）の符号出現数）｝×２
・・・（１）
【００５７】
また、インデックス決定部１２は、以下の式（２）に従って「符号長ｎの開始インデックス番号」を求める。
（符号長ｎの開始インデックス番号）＝
｛（符号長１の符号出現数）〜（符号長（ｎ−１）の符号出現数）｝の積算値（総和）
・・・（２）
【００５８】
図１０には、上記の式（１）及び（２）による演算結果が示されている。図１０に示されている符号出現数情報は、図８に示されている情報と同じものである。
【００５９】
図１０に示すように、各符号長の最初の符号値は、以下のようになっている。
符号長が１ｂｉｔ：最初の符号値は「０」である。
符号長が２ｂｉｔ：最初の符号値は「０」である。
符号長が３ｂｉｔ：最初の符号値は「２」である。
符号長が４ｂｉｔ：最初の符号値は「８」である。
符号長が５ｂｉｔ：最初の符号値は「１８」である。
符号長が６ｂｉｔ：最初の符号値は「４２」である。
この演算結果は、図７に示されているハフマンテーブル中のシンボル値の符号値と一致している。
【００６０】
また、開始インデックス番号は、以下のようになっている。
符号長が１ｂｉｔ：開始インデックス番号は「０」である。
符号長が２ｂｉｔ：開始インデックス番号は「０」である。
符号長が３ｂｉｔ：開始インデックス番号は「１」である。
符号長が４ｂｉｔ：開始インデックス番号は「３」である。
符号長が５ｂｉｔ：開始インデックス番号は「４」である。
符号長が６ｂｉｔ：開始インデックス番号は「７」である。
この演算結果は、図７に示されているハフマンテーブル中のシンボル値のインデックス番号に一致している。
【００６１】
上記の演算結果は、インデックス決定部１２に記憶される。
【００６２】
次に、第２段階の処理として、インデックス決定部１２は、分離部１０から入力される符号値を各符号長の最初の符号値と比較していき、これにより、符号長及び符号値を決定する。そして、インデックス決定部１２は、決定された符号長に基づいて最初の符号値と開始インデックス番号とを求める。以下、図１１に示すフローチャートを参照して、第２段階の処理について説明する。
【００６３】
一例として、以下に示す入力符号値が、分離部１０からインデックス決定部１２に入力されたものとする。
入力符号値＝１００１１１１（２進数で表現された値）
【００６４】
また、最初の符号値及び開始インデックス番号として、図１０に示されている情報を用いるものとする。
【００６５】
まず、インデックス決定部１２は、入力符号値の２ｂｉｔ分の値Ａ２と、符号長２ｂｉｔの最初の符号値Ｂ２と、を比較する（Ｓ１０）。値Ａ２，Ｂ２は以下の通りである。
値Ａ２：２進数で「１０」、１０進数で「０」
値Ｂ２：２進数で「００」、１０進数で「０」
Ａ２≧Ｂ２の関係が成立するため（Ｓ１０，Ｙｅｓ）、処理はステップＳ１２に移行する。なお、Ａ２＜Ｂ２の関係が成立する場合（Ｓ１０，Ｎｏ）、処理はステップＳ１１に移行する。
【００６６】
次に、インデックス決定部１２は、入力符号値の３ｂｉｔ分の値Ａ３と、符号長３ｂｉｔの最初の符号値Ｂ３と、を比較する（Ｓ１２）。値Ａ３，Ｂ３は以下の通りである。
値Ａ３：２進数で「１００」、１０進数で「４」
値Ｂ３：２進数で「１０」、１０進数で「２」
Ａ３≧Ｂ３の関係が成立するため（Ｓ１２，Ｙｅｓ）、処理はステップＳ１４に移行する。なお、Ａ３＜Ｂ３の関係が成立する場合（Ｓ１２，Ｎｏ）、処理はステップＳ１３に移行する。
【００６７】
次に、インデックス決定部１２は、入力符号値の４ｂｉｔ分の値Ａ４と、符号長４ｂｉｔの最初の符号値Ｂ４と、を比較する（Ｓ１４）。値Ａ４，Ｂ４は以下の通りである。
値Ａ４：２進数で「１００１」、１０進数で「９」
値Ｂ４：２進数で「１０００」、１０進数で「８」
Ａ４≧Ｂ４の関係が成立するため（Ｓ１４，Ｙｅｓ）、処理はステップＳ１６に移行する。なお、Ａ４＜Ｂ４の関係が成立する場合（Ｓ１４，Ｎｏ）、処理はステップＳ１５に移行する。
【００６８】
次に、インデックス決定部１２は、入力符号値の５ｂｉｔ分の値Ａ５と、符号長５ｂｉｔの最初の符号値Ｂ５と、を比較する（Ｓ１６）。値Ａ５，Ｂ５は以下の通りである。
値Ａ５：２進数で「１００１１」、１０進数で「１９」
値Ｂ５：２進数で「１００１０」、１０進数で「１８」
Ａ５≧Ｂ５の関係が成立するため（Ｓ１６，Ｙｅｓ）、処理はステップＳ１８に移行する。なお、Ａ５＜Ｂ５の関係が成立する場合（Ｓ１６，Ｎｏ）、処理はステップＳ１７に移行する。
【００６９】
次に、インデックス決定部１２は、入力符号値の６ｂｉｔ分の値Ａ６と、符号長６ｂｉｔの最初の符号値Ｂ６と、を比較する（Ｓ１８）。値Ａ６，Ｂ６は以下の通りである。
値Ａ６：２進数で「１００１１１」、１０進数で「３９」
値Ｂ６：２進数で「１０１０１０」、１０進数で「４２」
Ａ６＜Ｂ６の関係が成立するため（Ｓ１８，Ｎｏ）、符号長及び符号値は以下の値となる（Ｓ１９）。
符号長：５ｂｉｔ
符号値：２進数で「１００１１」、１０進数で「１９」（入録符号値の５ｂｉｔ分の値）
【００７０】
また、「最初の符号値」及び「開始インデックス番号」は以下に示すように、符号長が５ｂｉｔのときの値となる。
最初の符号値：２進数で「１００１０」、１０進数で「１８」
開始インデックス番号：「４」
【００７１】
なお、Ａ６≧Ｂ６の関係が成立する場合（Ｓ１８，Ｙｅｓ）、処理はステップＳ２０に移行する。ステップＳ２０では、入力符号値の７ｂｉｔ分の値Ａ７と、符号長７ｂｉｔの最初の符号値Ｂ７と、が比較される。それ以降においても同様の処理が行われる。
【００７２】
以上のように、符号長、符号値、最初の符号値及び開始インデックス番号が特定されると、次は、第３段階の処理が実行される。第３段階の処理においては、インデックス決定部１２は、符号値、最初の符号値及び開始インデックス番号に基づいて、ハフマンテーブルのインデックス番号を求め、そのインデックス番号に対応するシンボル値をハフマンテーブルから抽出する。
【００７３】
インデックス決定部１２は、以下の式（３）に従って、ハフマンテーブルのインデックス番号を求める。
（ハフマンテーブルのインデックス番号）＝
（開始インデックス番号）＋（符号値−最初の符号値）・・・（３）
【００７４】
上記の例では、符号値、最初の符号値及び開始インデックス番号は、以下の通りになっている。
符号値：２進数で「１００１１」、１０進数で「１９」
最初の符号値：２進数で「１００１０」、１０進数で「１８」
開始インデックス番号：「４」
【００７５】
上記の値を式（３）に代入すると、ハフマンテーブルのインデックス番号は以下の通りとなる。
ハフマンテーブルのインデックス番号＝４＋（１９−１８）＝５
【００７６】
上記のようにして求められたインデックス番号「５」を示す情報は、インデックス決定部１２からＬＵＴ部１４に出力される。ＬＵＴ部１４は、インデックス番号「５」に対応するシンボル値をハフマンテーブルから抽出して出力する。図７に示されているハフマンテーブルを参照すると、インデックス番号「５」に対応するシンボル値は「Ｅ」である。従って、シンボル値「Ｅ」が抽出されて出力される。
【００７７】
以上のようにして、インデックス決定部１２によってインデックス番号が求められ、そのインデックス番号に対応するシンボル値がハフマンテーブルから抽出されて出力される。以降の処理についても同様に実行され、これにより、伸長データ５０が順次生成されていく。
【００７８】
上述した本実施形態に係る情報処理装置は、一例としてハードウェア資源とソフトウェアとの協働により実現される。具体的には、情報処理装置は、図示しないＣＰＵ等のプロセッサを備えている。当該プロセッサが、図示しない記憶装置に記憶されたプログラムを読み出して実行することにより、情報処理装置の各部の機能が実現される。上記プログラムは、ＣＤやＤＶＤ等の記録媒体を経由して、又は、ネットワーク等の通信経路を経由して、記憶装置に記憶される。または、情報処理装置の各部は、例えばプロセッサや電子回路等のハードウェア資源により実現されてもよい。その実現においてメモリ等のデバイスが利用されてもよい。別の例として、情報処理装置の各部は、ＤＳＰ（Digital Signal Processor）やＦＰＧＡ（Field Programmable Gate Array）等によって実現されてもよい。
【符号の説明】
【００７９】
１０  分離部、１２  インデックス決定部、１４  ＬＵＴ部、１６  終端検知部、２０  ハフマンテーブル生成部、２２  符号出現数記憶部、２４  設定位置記憶部、２６  生成制御部、４０  圧縮データ、５０  伸長データ。
【図１】
2016139958.tif 000003
【図２】
2016139958.tif 000004
【図３】
2016139958.tif 000005
【図４】
2016139958.tif 000006
【図５】
2016139958.tif 000007
【図７】
2016139958.tif 000008
【図８】
2016139958.tif 000009
【図９】
2016139958.tif 000010
【図１０】
2016139958.tif 000011
【図１１】
2016139958.tif 000012
【図６】
2016139958.tif 000013