(57)【要約】【課題】データの圧縮及び復元ができることを担保しつつ、辞書テーブルの格納及びその参照に要するデータのサイズを削減する。【解決手段】符号割当装置２０は、木構造データにおける共通部分木を、出現回数の多い順にソートし、出現回数が同一である複数の共通部分木については、最初の出現位置の出現順序の若い順にソートする第一ソート部２１と、第一ソート部２１によりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い仮符号を割り当てる仮符号割当部２２と、全ての共通部分木を仮符号の符号長の短い順にソートし、符号長が同一である複数の共通部分木については、出現順序の若い順にソートする第二ソート部２３と、第二ソート部２３によりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い符号を割り当てる符号割当部２４と、を備える。【選択図】図１
2014023101.tif 000002
【特許請求の範囲】
【請求項１】
木構造データにおいて複数回出現する等価な部分木である共通部分木を、前記木構造データにおける出現回数の多い順にソートし、該出現回数が同一である複数の共通部分木については、前記木構造データにおける最初の出現位置の出現順序の若い順にソートする第一ソート部と、
前記第一ソート部によりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い仮符号を割り当てる仮符号割当部と、
全ての共通部分木を前記仮符号の符号長の短い順にソートし、該符号長が同一である複数の共通部分木については、前記出現順序の若い順にソートする第二ソート部と、
前記第二ソート部によりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い符号を割り当てる符号割当部と、
を備える符号割当装置。
【請求項２】
木構造データにおいて複数回出現する等価な部分木である共通部分木ごとに、請求項１に記載の符号割当装置により割り当てられた符号と該共通部分木に対応するデータとの組を含む辞書テーブルを生成する辞書テーブル生成部と、
共通部分木ごとに、該共通部分木の最初の出現位置における部分木である第１部分木に対応するデータに対し、前記共通部分木に割り当てられた前記符号の符号長に対応する符号長マーカを付与する符号長マーカ付与部と、
共通部分木ごとに、該共通部分木の２回目以降の出現位置における部分木である第２部分木に対応するデータを、前記辞書テーブルを参照して、前記共通部分木に割り当てられた前記符号に置き換えることで圧縮する辞書式圧縮処理部と、
を備えるデータ圧縮処理装置。
【請求項３】
請求項２に記載のデータ圧縮処理装置により圧縮された圧縮データを部分木ごとに読み込む圧縮データ読込部と、
前記圧縮データ読込部が読み込んだ部分木に対応するデータに前記符号長マーカが付与されているか否かを判定し、該部分木に対応するデータに前記符号長マーカが付与されていると判定した場合には、該部分木に対応するデータ及び前記符号長マーカを抽出する辞書項目抽出部と、
前記符号長マーカの符号長ごとに、符号の初期値である符号ベースと、符号の復元回数を記憶する符号カウンタとを備え、前記符号長マーカの符号長に対応する前記符号ベース及び前記符号カウンタを用いて、符号を復元する符号復元部と、
前記部分木に対応するデータと前記符号との組から前記辞書テーブルを復元する辞書テーブル復元部と、
を備えるデータ復元処理装置。
【請求項４】
請求項１に記載の符号割当装置と、
請求項２に記載のデータ圧縮処理装置と、
請求項３に記載のデータ復元処理装置と、
を備えるデータ処理システム。
【請求項５】
木構造データにおいて複数回出現する等価な部分木である共通部分木を、前記木構造データにおける出現回数の多い順にソートし、該出現回数が同一である複数の共通部分木については、前記木構造データにおける最初の出現位置の出現順序の若い順にソートする第一ソートステップと、
前記第一ソートステップによりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い仮符号を割り当てる仮符号割当ステップと、
全ての共通部分木を前記仮符号の符号長の短い順にソートし、該符号長が同一である複数の共通部分木については、前記出現順序の若い順にソートする第二ソートステップと、
前記第二ソートステップによりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い符号を割り当てる符号割当ステップと、
を含む符号割当方法。
【請求項６】
木構造データにおいて複数回出現する等価な部分木である共通部分木ごとに、請求項５に記載の符号割当方法により割り当てられた符号と該共通部分木に対応するデータとの組を含む辞書テーブルを生成する辞書テーブル生成ステップと、
共通部分木ごとに、該共通部分木の最初の出現位置における部分木である第１部分木に対応するデータに対し、前記共通部分木に割り当てられた前記符号の符号長に対応する符号長マーカを付与する符号長マーカ付与ステップと、
共通部分木ごとに、該共通部分木の２回目以降の出現位置における部分木である第２部分木に対応するデータを、前記辞書テーブルを参照して、前記共通部分木に割り当てられた前記符号に置き換えることで圧縮する辞書式圧縮処理ステップと、
を含むデータ圧縮処理方法。
【請求項７】
請求項６に記載のデータ圧縮処理方法により圧縮された圧縮データを部分木ごとに読み込む圧縮データ読込ステップと、
前記圧縮データ読込ステップが読み込んだ部分木に対応するデータに前記符号長マーカが付与されているか否かを判定し、該部分木に対応するデータに前記符号長マーカが付与されていると判定した場合には、該部分木に対応するデータ及び前記符号長マーカを抽出する辞書項目抽出ステップと、
前記符号長マーカの符号長ごとに、符号の初期値である符号ベースと、符号の復元回数を記憶する符号カウンタとを備え、前記符号長マーカの符号長に対応する前記符号ベース及び前記符号カウンタを用いて、符号を復元する符号復元ステップと、
前記部分木に対応するデータと前記符号との組から前記辞書テーブルを復元する辞書テーブル復元ステップと、
を含むデータ復元処理方法。
【請求項８】
符号割当装置に設けられたコンピュータを、
木構造データにおいて複数回出現する等価な部分木である共通部分木を、前記木構造データにおける出現回数の多い順にソートし、該出現回数が同一である複数の共通部分木については、前記木構造データにおける最初の出現位置の出現順序の若い順にソートする第一ソート部と、
前記第一ソート部によりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い仮符号を割り当てる仮符号割当部と、
全ての共通部分木を前記仮符号の符号長の短い順にソートし、該符号長が同一である複数の共通部分木については、前記出現順序の若い順にソートする第二ソート部と、
前記第二ソート部によりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い符号を割り当てる符号割当部、
として機能させる符号割当プログラム。
【請求項９】
データ圧縮処理装置に設けられたコンピュータを、
木構造データにおいて複数回出現する等価な部分木である共通部分木ごとに、請求項８に記載の符号割当プログラムを実行することにより割り当てられた符号と該共通部分木に対応するデータとの組を含む辞書テーブルを生成する辞書テーブル生成部と、
共通部分木ごとに、該共通部分木の最初の出現位置における部分木である第１部分木に対応するデータに対し、前記共通部分木に割り当てられた前記符号の符号長に対応する符号長マーカを付与する符号長マーカ付与部と、
共通部分木ごとに、該共通部分木の２回目以降の出現位置における部分木である第２部分木に対応するデータを、前記辞書テーブルを参照して、前記共通部分木に割り当てられた前記符号に置き換えることで圧縮する辞書式圧縮処理部と、
として機能させるデータ圧縮処理プログラム。
【請求項１０】
データ復元処理装置に設けられたコンピュータを、
請求項９に記載のデータ圧縮処理プログラムを実行することにより圧縮された圧縮データを部分木ごとに読み込む圧縮データ読込部と、
前記圧縮データ読込部が読み込んだ部分木に対応するデータに前記符号長マーカが付与されているか否かを判定し、該部分木に対応するデータに前記符号長マーカが付与されていると判定した場合には、該部分木に対応するデータ及び前記符号長マーカを抽出する辞書項目抽出部と、
前記符号長マーカの符号長ごとに、符号の初期値である符号ベースと、符号の復元回数を記憶する符号カウンタとを備え、前記符号長マーカの符号長に対応する前記符号ベース及び前記符号カウンタを用いて、符号を復元する符号復元部と、
前記部分木に対応するデータと前記符号との組から前記辞書テーブルを復元する辞書テーブル復元部、
として機能させるデータ復元処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号割当装置、データ圧縮処理装置、データ復元処理装置、及びこれらの装置を備えるデータ処理システムに関する。また、本発明は、符号割当方法、データ圧縮処理方法、データ復元処理方法、符号割当プログラム、データ圧縮処理プログラム、及びデータ復元処理プログラムに関する。
【背景技術】
【０００２】
木構造データは従来から広く研究され、また、様々な用途に利用されている。例えば最近注目を集めているビッグデータ処理システムであるオープンソースソフトウェアHadoop（下記非特許文献１参照）では、SequenceFileという枠組みを用い、木構造データとして表現した個々のレコードを直列化した上でストレージに保存する。ビッグデータ処理システムでは大量のデータを保存するため、ストレージ容量を節約するために、個々のレコードは少しでもデータサイズを縮小することが要請される。そのため、SequenceFileでは、直列化した結果をGzip等の従来の圧縮技術で圧縮をしてから保存するのが慣習となっている。
【０００３】
下記非特許文献２には、テキストデータを対象として、従来の圧縮技術では上手く利用できない「長い共通文字列」による冗長性を利用した独自の「事前圧縮」を行った後、従来の圧縮技術で圧縮することにより、単に従来の圧縮技術だけで圧縮するよりも高い圧縮率を達成する旨が述べられている。この考え方を木構造データに応用する場合、できるだけ大きな「共通部分木」を探し出し、その冗長性を利用した独自の「事前圧縮」を行うことが考えられる。具体的には、出現回数が２回以上である「共通部分木」に対して、より出現回数の多いものに、より短い符号を割り当てて「辞書テーブル」を構築し、木構造データ中における当該「共通部分木」の出現箇所を当該符号で置換するような、いわゆるＨｕｆｆｍａｎ符号などが考えられる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】“Hadoop”、［ｏｎｌｉｎｅ］、インターネット＜ＵＲＬ：http://hadoop.apache.org/＞
【非特許文献２】Jon  Bentley，Douglas  McIlroy著、“Data  Compression  Using  Long  Common  Strings”、Proceeding．DCC'99  Proceedings  of  the  Conference  on  Data  Compression、１９９９年発行、ｐ．２８７−２９５
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、Ｈｕｆｆｍａｎ符号で符号化した圧縮データを正常に復号化するには、何らかの手段を用いて符号化側と復号化側とで辞書テーブルを共有する必要がある。最も簡単な方法は、辞書テーブルを圧縮データの中に格納することである。例えば、符号化側において圧縮データにヘッダ部を設け、そこに辞書テーブルを格納する方法が考えられる。この場合、圧縮データの最終的なサイズを小さくするために、辞書テーブルを少ないデータ量で格納できることが好ましい。
【０００６】
圧縮データのサイズを小さくするための第一の方法として、共通部分木に割り当てる符号をある定数（典型的には「０」）から始めて一定幅（典型的には「１」）ずつインクリメントすることで、出現回数の多い共通部分木に、より短い符号を割り当て、辞書テーブルには、共通部分木のみを符号の値の小さい（符号長が短い）順に格納する方法が考えられる。この場合、復号化側では、ヘッダ部の辞書テーブルから共通部分木を１つ読み込むごとに、符号化側と事前に合意した定数から始めて、事前に合意した更新幅ずつインクリメントした符号を共通部分木に対応付けることで、辞書テーブルを復元できる。これにより、ヘッダ部に符号を格納する必要がなくなるため、それだけ辞書テーブルのサイズを削減でき、圧縮データのサイズを小さくできる。
【０００７】
しかし、本発明者は、第一の方法には、まだ削減できるデータサイズ上の無駄があると考えた。そこで、本発明者は、木構造データにおいて最初に出現する共通部分木に対応するデータを符号に置き換えずに圧縮データにそのまま埋め込むことで、圧縮データに設けたヘッダ部に辞書テーブルを格納する方法を回避する第二の方法を着想した。第二の方法によれば、当該共通部分木の符号の参照を１回減らすことができ、「共通部分木に割り当てられる符号１つ当たりのサイズ」と「共通部分木の総数」の積のオーダに比例するデータサイズの削減が期待できる。
【０００８】
しかしながら、共通部分木が圧縮データに埋め込まれる順序（木構造データにおいて最初に出現する順序）と、第一の方法での符号の順序（出現回数により昇順にソートした順序）とは同一となる保証はないため、第一の方法と第二の方法とを単純に組み合わせた場合には、復号化の際に辞書テーブルの復元（符号の復元）をうまく行うことができないおそれがある。
【０００９】
そこで、本発明は、データの圧縮及び復元ができることを担保しつつ、辞書テーブルの格納及びその参照に要するデータのサイズを削減することを目的とする。
【課題を解決するための手段】
【００１０】
本発明に係る符号割当装置は、木構造データにおいて複数回出現する等価な部分木である共通部分木を、木構造データにおける出現回数の多い順にソートし、該出現回数が同一である複数の共通部分木については、木構造データにおける最初の出現位置の出現順序の若い順にソートする第一ソート部と、第一ソート部によりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い仮符号を割り当てる仮符号割当部と、全ての共通部分木を仮符号の符号長の短い順にソートし、該符号長が同一である複数の共通部分木については、出現順序の若い順にソートする第二ソート部と、第二ソート部によりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い符号を割り当てる符号割当部と、を備える。
【００１１】
本発明に係る符号割当方法は、木構造データにおいて複数回出現する等価な部分木である共通部分木を、木構造データにおける出現回数の多い順にソートし、該出現回数が同一である複数の共通部分木については、木構造データにおける最初の出現位置の出現順序の若い順にソートする第一ソートステップと、第一ソートステップによりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い仮符号を割り当てる仮符号割当ステップと、全ての共通部分木を仮符号の符号長の短い順にソートし、該符号長が同一である複数の共通部分木については、出現順序の若い順にソートする第二ソートステップと、第二ソートステップによりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い符号を割り当てる符号割当ステップと、を含む。
【００１２】
本発明に係る符号割当プログラムは、請求項１に記載の符号割当装置に設けられたコンピュータを、木構造データにおいて複数回出現する等価な部分木である共通部分木を、木構造データにおける出現回数の多い順にソートし、該出現回数が同一である複数の共通部分木については、木構造データにおける最初の出現位置の出現順序の若い順にソートする第一ソート部と、第一ソート部によりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い仮符号を割り当てる仮符号割当部と、全ての共通部分木を仮符号の符号長の短い順にソートし、該符号長が同一である複数の共通部分木については、出現順序の若い順にソートする第二ソート部と、第二ソート部によりソートされた全ての共通部分木に対して、ソート順で先の共通部分木から優先して、符号長の短い符号を割り当てる符号割当部、として機能させる。
【００１３】
このような形態では、第一の処理（第一ソート部、仮符号割当部）により、出現回数が多い順（出現回数が同じ場合は出現順序の若い順）に、符号長の短い符号（仮符号）が各共通部分木に対して割り当てられる。続いて、第二の処理（第二ソート部、符号割当部）により、符号長の短い順（符号長が同じ場合は出現順序の若い順）に、符号長の短い符号が各共通部分木に対して再割当される。このような二段階の処理により、出現回数が多い共通部分木から優先して符号長の短い符号を割り当てるようにしつつ、同一符号長となる共通部分木に対しては、出現順序が若い順に、符号を割り当てることができる。これにより、対応するデータ圧縮処理において、圧縮データのサイズをより効率的に削減することを可能にすると共に、対応するデータ復元処理において、圧縮データを復元することを可能にすることができる。
【００１４】
本発明に係るデータ圧縮処理装置は、木構造データにおいて複数回出現する等価な部分木である共通部分木ごとに、請求項１に記載の符号割当装置により割り当てられた符号と該共通部分木に対応するデータとの組を含む辞書テーブルを生成する辞書テーブル生成部と、共通部分木ごとに、該共通部分木の最初の出現位置における部分木である第１部分木に対応するデータに対し、共通部分木に割り当てられた符号の符号長に対応する符号長マーカを付与する符号長マーカ付与部と、共通部分木ごとに、該共通部分木の２回目以降の出現位置における部分木である第２部分木に対応するデータを、辞書テーブルを参照して、共通部分木に割り当てられた符号に置き換えることで圧縮する辞書式圧縮処理部と、を備える。
【００１５】
本発明に係るデータ圧縮処理方法は、木構造データにおいて複数回出現する等価な部分木である共通部分木ごとに、請求項５に記載の符号割当方法により割り当てられた符号と該共通部分木に対応するデータとの組を含む辞書テーブルを生成する辞書テーブル生成ステップと、共通部分木ごとに、該共通部分木の最初の出現位置における部分木である第１部分木に対応するデータに対し、共通部分木に割り当てられた符号の符号長に対応する符号長マーカを付与する符号長マーカ付与ステップと、共通部分木ごとに、該共通部分木の２回目以降の出現位置における部分木である第２部分木に対応するデータを、辞書テーブルを参照して、共通部分木に割り当てられた符号に置き換えることで圧縮する辞書式圧縮処理ステップと、を含む。
【００１６】
本発明に係るデータ圧縮処理プログラムは、データ圧縮処理装置に設けられたコンピュータを、木構造データにおいて複数回出現する等価な部分木である共通部分木ごとに、請求項８に記載の符号割当プログラムを実行することにより割り当てられた符号と該共通部分木に対応するデータとの組を含む辞書テーブルを生成する辞書テーブル生成部と、共通部分木ごとに、該共通部分木の最初の出現位置における部分木である第１部分木に対応するデータに対し、共通部分木に割り当てられた符号の符号長に対応する符号長マーカを付与する符号長マーカ付与部と、共通部分木ごとに、該共通部分木の２回目以降の出現位置における部分木である第２部分木に対応するデータを、辞書テーブルを参照して、共通部分木に割り当てられた符号に置き換えることで圧縮する辞書式圧縮処理部、として機能させる。
【００１７】
このような形態では、共通部分木ごとに、共通部分木の最初の出現位置における第１部分木に対応するデータについては、符号長マーカを付与した上で圧縮データにそのまま埋め込むことで、辞書テーブルに相当する情報を圧縮データに埋め込むことができる。これにより、圧縮データに埋め込む辞書テーブルに相当する情報から符号を省略できる。さらに、第１部分木１つ分の符号の参照（符号への置き換え）が減ることにより、共通部分木１つにつき、符号のサイズと符号長マーカのサイズとの差分だけ、データサイズを削減することができる。以上により、辞書テーブルのサイズの格納及びその参照に要するデータのサイズを削減することができる。
【００１８】
本発明に係るデータ復元処理装置は、請求項２に記載のデータ圧縮処理装置により圧縮された圧縮データを部分木ごとに読み込む圧縮データ読込部と、圧縮データ読込部が読み込んだ部分木に対応するデータに符号長マーカが付与されているか否かを判定し、該部分木に対応するデータに符号長マーカが付与されていると判定した場合には、該部分木に対応するデータ及び符号長マーカを抽出する辞書項目抽出部と、符号長マーカの符号長ごとに、符号の初期値である符号ベースと、符号の復元回数を記憶する符号カウンタとを備え、符号長マーカの符号長に対応する符号ベース及び符号カウンタを用いて、符号を復元する符号復元部と、部分木に対応するデータと符号との組から辞書テーブルを復元する辞書テーブル復元部と、を備える。
【００１９】
本発明に係るデータ復元処理方法は、請求項６に記載のデータ圧縮処理方法により圧縮された圧縮データを部分木ごとに読み込む圧縮データ読込ステップと、圧縮データ読込ステップが読み込んだ部分木に対応するデータに符号長マーカが付与されているか否かを判定し、該部分木に対応するデータに符号長マーカが付与されていると判定した場合には、該部分木に対応するデータ及び符号長マーカを抽出する辞書項目抽出ステップと、符号長マーカの符号長ごとに、符号の初期値である符号ベースと、符号の復元回数を記憶する符号カウンタとを備え、符号長マーカの符号長に対応する符号ベース及び符号カウンタを用いて、符号を復元する符号復元ステップと、部分木に対応するデータと符号との組から辞書テーブルを復元する辞書テーブル復元ステップと、を含む。
【００２０】
本発明に係るデータ復元処理プログラムは、データ復元処理装置に設けられたコンピュータを、請求項９に記載のデータ圧縮処理プログラムを実行することにより圧縮された圧縮データを部分木ごとに読み込む圧縮データ読込部と、圧縮データ読込部が読み込んだ部分木に対応するデータに符号長マーカが付与されているか否かを判定し、該部分木に対応するデータに符号長マーカが付与されていると判定した場合には、該部分木に対応するデータ及び符号長マーカを抽出する辞書項目抽出部と、符号長マーカの符号長ごとに、符号の初期値である符号ベースと、符号の復元回数を記憶する符号カウンタとを備え、符号長マーカの符号長に対応する符号ベース及び符号カウンタを用いて、符号を復元する符号復元部と、部分木に対応するデータと符号との組から辞書テーブルを復元する辞書テーブル復元部、として機能させる。
【００２１】
このような形態では、符号長マーカの符号長ごとに、符号ベース及び符号カウンタを備えることで、圧縮データにおける符号長マーカが付与された部分木を読み込んだ際に、当該部分木に対応するデータ及び符号を復元することができる。これにより、圧縮データの圧縮に用いられた辞書テーブルを復元し、復元した辞書テーブルを用いて圧縮データから元のデータを復元することができる。
【００２２】
本発明に係るデータ処理システムは、請求項１に記載の符号割当装置と、請求項２に記載のデータ圧縮処理装置と、請求項３に記載のデータ復元処理装置と、を備える。
【００２３】
このような形態では、データ処理システムは、上記の符号割当装置、データ圧縮処理装置、及びデータ復元処理装置を備えることにより、データの圧縮及び復元ができることを担保しつつ、辞書テーブルの格納及びその参照に要するデータのサイズを削減することができる。
【発明の効果】
【００２４】
本発明によれば、データの圧縮及び復元ができることを担保しつつ、辞書テーブルの格納及びその参照に要するデータのサイズを削減することができる。
【図面の簡単な説明】
【００２５】
【図１】実施形態に係るデータ処理システム全体の機能構成を示すブロック図である。
【図２】実施形態に係るデータ復元処理装置の機能構成を示すブロック図である。
【図３】実施形態に係る符号割当装置、データ圧縮処理装置、及びデータ復元処理装置のハードウェア構成を示すブロック図である。
【図４】実施形態に係る木構造データを示す図である。
【図５】実施形態に係る符号割当装置の動作を示すフロー図である。
【図６】第一ソート部によりソートされた後の共通部分木の各値を示す図である。
【図７】第二ソート部によりソートされた後の共通部分木の各値を示す図である。
【図８】実施形態に係るデータ圧縮処理装置の動作を示すフロー図である。
【図９】データ圧縮処理装置により圧縮されたデータの状態を示す概念図である。
【図１０】実施形態に係るデータ復元処理装置の動作を示すフロー図である。
【図１１】符号の復元処理を説明するために用いる図である。
【図１２】符号割当プログラム、データ圧縮処理プログラム、及びデータ復元処理プログラムの機能構成を示すブロック図である。
【発明を実施するための形態】
【００２６】
以下、添付図面を参照しながら本発明の実施形態を詳細に説明する。なお、図面の説明において同一又は同等の要素には同一の符号を付し、重複する説明を省略する。
【００２７】
まず、図４を用いて、本実施形態における処理対象となる木構造データについて説明する。図４に示すように、木構造データは、値を保持する葉ノードと、葉ノード又は他の中間ノードを子ノードとして保持する中間ノードと、親ノードを持たない唯一の中間ノードである根ノードと、各ノード間を結ぶエッジとからなるデータ構造である。木構造データの実装方法としては、各ノードに子ノードへのポインタを保持させる方法や各ノードに親ノードへのポインタを保持させる方法などのいくつかの方法があるが、実装方法はこれらの方法のいずれかに限定されない。
【００２８】
次に、本明細書で用いるいくつかの表現について定義する。本明細書中において、「部分木」とは、木構造データにおける任意のノード以下の要素（ノード、エッジ）のみによって構成される木のことをいう。すなわち、部分木とは、当該任意のノードを根ノードとする木を意味する。また、ノードＡを根ノードとする部分木Ａと、ノードＢを根ノードとする部分木Ｂについて、ノードＢがノードＡの子ノードに該当する場合に、「部分木ＡはノードＢ（又は部分木Ｂ）の子である」と表現する。また、任意のノードを指して部分木といった場合には、当該部分木は、「任意のノードを根ノードとする部分木」であることを意味する。
【００２９】
また、単に「子」又は「子ノード」と記載した場合には、「孫」又は「孫ノード」が含まれてもよく、「直接の子」又は「直接の子ノード」と記載した場合には、直接の親子関係にある「子」又は「子ノード」のみを意味し、「孫」又は「孫ノード」は含まれないものとする。また、任意の２つの部分木について、各部分木のノード構成、すなわち、全てのノード要素の位置、種別（葉又は中間）、及び値（葉ノードの場合）が完全一致するときに、これらの部分木は「等価」であるという。
【００３０】
次に、実施形態に係るデータ処理システム１の機能要素について、図１を用いて説明する。データ処理システム１は、木構造構築部１１、部分木等価性判定部１２、共通部分木検出部１３、出現回数計数部１４、出現順序検出部１５、符号割当装置２０、データ圧縮処理装置３０、データ保存部４０、及びデータ復元処理装置５０を備える。
【００３１】
符号割当装置２０、データ圧縮処理装置３０、及びデータ復元処理装置５０のハードウェア構成を図３に示す。図３に示すように、符号割当装置２０、データ圧縮処理装置３０、及びデータ復元処理装置５０はそれぞれ、オペレーティングシステムやアプリケーションプログラムなどを実行するＣＰＵ１０１と、ＲＯＭ及びＲＡＭで構成される主記憶部１０２と、ハードディスクメモリなどで構成される補助記憶部１０３と、データ通信を行う通信制御部１０４と、液晶モニタなどで構成される出力部１０５と、入力デバイスであるキーボード及びマウス等で構成される操作部１０６と、ＣＤ−ＲＯＭやＤＶＤなどの記録媒体１１０を読み取る記録媒体読取部１０７とを備える。
【００３２】
図１に示す符号割当装置２０、データ圧縮処理装置３０、及びデータ復元処理装置５０の各機能は、ＣＰＵ１０１の制御の下で、主記憶部１０２に所定のソフトウェアプログラムを読み込ませて実行することにより実現される。その際、ＣＰＵ１０１は、ソフトウェアプログラムの処理手順に従い、主記憶部１０２及び補助記憶部１０３におけるデータの読み出し及び書き込み動作を制御し、操作部１０６、出力部１０５及び通信制御部１０４の動作を制御する。
【００３３】
図１の木構造構築部１１は、木構造データを構築する機能要素である。木構造構築部１１は、オブジェクト構造を有するデータについて、各オブジェクトを木構造における各ノードに対応させるように木構造データを構築する。
【００３４】
部分木等価性判定部１２は、木構造データにおける全ての部分木の等価性を判定し、等価な部分木ごとに分類する機能要素である。部分木等価性判定部１２は、例えば、木構造データの全てのノードを巡回しつつ、各ノードを根とする部分木に対して、木構造データにおける等価な部分木ごとにユニークな値となる識別ＩＤを割り当てることにより、木構造データにおける全ての部分木を等価な部分木ごとに分類する。
【００３５】
共通部分木検出部１３は、木構造データにおいて複数回出現する部分木を共通部分木として検出する機能要素である。共通部分木検出部１３は、例えば、部分木等価性判定部１２が各部分木に割り当てた識別ＩＤにより、同一の識別ＩＤを持つ部分木が複数存在するような等価な部分木を共通部分木として検出する。
【００３６】
出現回数計数部１４は、共通部分木検出部１３が検出した共通部分木ごとの出現回数を計数する機能要素である。出現回数計数部１４は、例えば、木構造データを巡回し、巡回先の部分木の識別ＩＤを参照し、識別ＩＤごとの出現回数を順次加算していくことにより計数することができる。
【００３７】
出現順序検出部１５は、共通部分木検出部１３が検出した全ての共通部分木について、各共通部分木が木構造データにおいて最初に出現する位置における出現順序を検出する機能要素である。より具体的には、出現順序検出部１５は、木構造データを一定の規則に基づいて巡回した際に巡回される順序に基づいて、各共通部分木の最初の出現位置同士を比較し、共通部分木の出現順序を検出する。本実施形態においては、木構造データの巡回は、深さ優先で行われるものとする。
【００３８】
符号割当装置２０は、共通部分木ごとに適切な符号を割り当てる機能要素である。符号割当装置２０は、第一ソート部２１、仮符号割当部２２、第二ソート部２３、及び符号割当部２４を備える。以下、各機能要素について説明する。
【００３９】
第一ソート部２１は、出現回数計数部１４により計数された各共通部分木の出現回数を参照して、全ての共通部分木を出現回数の多い順にソートする。この際、出現回数が同一の共通部分木同士については、出現順序検出部１５が検出した出現順序を参照して、出現順序の若い順にソートする。
【００４０】
仮符号割当部２２は、全ての共通部分木に対して、第一ソート部２１によるソート順で先の共通部分木から優先して、符号長の短い仮符号を割り当てる。ここで、仮符号のセットは、後述する符号割当部２４により割り当てられる符号のセットと同一である。また、符号及び仮符号は、符号化側の符号割当装置２０と復号化側のデータ復元処理装置５０との間で、事前に合意した番号（典型的には「０」）から開始され、事前に合意した更新幅（典型的には「１」）ずつインクリメントされつつ、各共通部分木に割り当てられるものとする。また、符号及び仮符号は、バイト単位で整列されているものとし、各バイト数で表現できる符号の最大値等の情報についても符号化側と復号化側とで事前に合意されているものとする。
【００４１】
第二ソート部２３は、全ての共通部分木を、各共通部分木に割り当てられた仮符号を参照して、仮符号の符号長の短い順にソートする。この際、仮符号の符号長が同一の共通部分木同士については、出現順序検出部１５が検出した出現順序を参照して、出現順序の若い順にソートする。
【００４２】
符号割当部２４は、全ての共通部分木に対して、第二ソート部２３によるソート順で先の共通部分木から優先して、符号長の短い符号を割り当てる。
【００４３】
以上のように、符号割当装置２０は、第一ソート部２１及び仮符号割当部２２による第一の処理と、第二ソート部２３及び符号割当部２４による第二の処理との二段階の処理により、出現回数が多い共通部分木から優先して符号長の短い符号を割り当てるようにしつつ、同一符号長となる共通部分木に対しては、出現順序が若い順に、符号を割り当てることができる。これにより、後述するデータ圧縮処理装置３０において、圧縮データに埋め込む辞書テーブルの情報において符号を省略することができる。
【００４４】
データ圧縮処理装置３０は、木構造データを、共通部分木に対応するデータ（以下、部分木に対応するデータを指す際に、誤解が生じない場合には、単に「部分木」と表記する。）を当該データよりも短い符号（符号割当部２４により割り当てられた符号）に置き換えることで圧縮する機能要素である。データ圧縮処理装置３０は、辞書テーブル生成部３１、符号長マーカ付与部３２、及び辞書式圧縮処理部３３を備える。
【００４５】
辞書テーブル生成部３１は、共通部分木ごとに、符号割当部２４により割り当てられた符号と当該共通部分木との組（辞書項目）を含む辞書テーブルを生成する。
【００４６】
符号長マーカ付与部３２は、共通部分木ごとに、当該共通部分木の木構造データにおける最初の出現位置における部分木（第１部分木）に対して、当該共通部分木に割り当てられている符号の符号長に対応する符号長マーカを付与する。符号長マーカを付与された第１部分木は、後述する辞書式圧縮処理部３３により符号に置き換えられず、元のデータに符号長マーカが付与された状態で、圧縮後のデータ（圧縮データ）に埋め込まれる。
【００４７】
辞書式圧縮処理部３３は、共通部分木ごとに、当該共通部分木の木構造データにおける２回目以降の出現位置における部分木（第２部分木）を、辞書テーブルを参照し、対応する符号に置き換えることで圧縮する。
【００４８】
ここで、処理対象の部分木が最初の出現（第１部分木）であるか、又は、２回目以降の出現（第２部分木）であるかの判定は、例えば、以下のように辞書テーブル内の辞書項目にフラグを設けることで実現してもよい。すなわち、辞書項目のフラグが未設定であれば、最初の出現（第１部分木）であると判定しつつフラグを設定し、辞書項目のフラグが設定済みであれば、２回目以降の出現（第２部分木）であると判定する方法が考えられる。ただし、処理対象の部分木が第１部分木であるか第２部分木であるかの判定方法は、上記方法に限定されない。
【００４９】
データ保存部４０は、圧縮データを保存する機能要素である。データ保存部４０は、圧縮データをファイルとして保存してもよいし、ネットワーク上で伝送するために、何らかの方法によりバイト列に直列化（シリアライズ）した上で保存してもよい。
【００５０】
図２を用いて、データ復元処理装置５０について説明する。データ復元処理装置５０は、圧縮データを復元する機能要素である。具体的には、データ復元処理装置５０は、圧縮データから辞書テーブルを復元しつつ、辞書テーブル上に復元された情報に基づいて圧縮データから元のデータを復元（復号）する。データ復元処理装置５０は、圧縮データ読込部５１、辞書項目抽出部５２、符号復元部５３、辞書テーブル復元部５４、及び復号処理部５５を備える。辞書項目抽出部５２は、符号長マーカ判定部５２Ａ、符号長マーカ抽出部５２Ｂ、及び部分木抽出部５２Ｃを備え、符号復元部５３は、符号ベース５３Ａ及び符号カウンタ５３Ｂを備える。
【００５１】
圧縮データ読込部５１は、データ保存部４０に保存された圧縮データを部分木ごとに順次読み込む。ここで、圧縮データが直列化された状態でデータ保存部４０に保存されている場合には、圧縮データ読込部５１は、圧縮データを何らかの方法により非直列化（デシリアライズ）した上で、部分木ごとに読み込む。非直列化の具体的な方法については、本発明の範囲外であり、特定の方法に限定されない。
【００５２】
辞書項目抽出部５２は、符号長マーカ判定部５２Ａ、符号長マーカ抽出部５２Ｂ、及び部分木抽出部５２Ｃを備える。まず、符号長マーカ判定部５２Ａが、圧縮データ読込部５１が読み込んだ部分木を、木構造データにおける出現順（出現順序検出部１５と同様の深さ優先での巡回順）に抽出し、当該部分木に符号長マーカが付与されているか、符号長マーカが付与されていない通常ノードか、又は符号の参照であるかを判定する。符号長マーカ判定部５２Ａが当該部分木に符号長マーカが付与されていると判定した場合には、符号長マーカ抽出部５２Ｂが当該符号長マーカを抽出し、部分木抽出部５２Ｃが当該部分木を抽出する。
【００５３】
符号復元部５３は、辞書項目抽出部５２が抽出した符号長マーカを参照して、当該符号長マーカごとに予め用意されている符号ベース５３Ａと符号カウンタ５３Ｂとを用いて、符号を復元する。符号ベース５３Ａは、符号長マーカ（符号長）ごとに、最初に復元される符号の値を保持したものである。符号カウンタ５３Ｂは、符号長マーカの種類（符号長）ごとに、符号を復元した回数（カウンタ値）を保持したものであり、同一の符号長マーカに対する符号を復元する度に符号カウンタ値を一定の更新幅でインクリメントする。ここで、各符号長に対する符号ベース及び符号カウンタの更新幅は、符号化側の符号割当装置２０と復号化側のデータ復元処理装置５０との間で、事前に合意している必要がある。
【００５４】
辞書テーブル復元部５４は、部分木抽出部５２Ｃにより抽出された部分木と符号復元部５３により復元された符号との組から辞書テーブルを復元する。具体的には、上記部分木と符号との組（辞書項目）を辞書テーブルに登録する。この復元処理が全ての共通部分木に対して完了した時点で、辞書テーブルの復元が完了する。
【００５５】
復号処理部５５は、辞書テーブル復元部５４により復号に必要な辞書項目が復元された辞書テーブルを用いて、圧縮データ読込部５１が読み込んだ部分木のうち復号対象の部分木を復号する。ここで、圧縮データ読込部５１が読み込んだ部分木が復号対象であるか否かの判定は、符号長マーカ判定部５２Ａにより行われる。すなわち、符号長マーカ判定部５２Ａにより符号の参照であると判定された部分木が復号対象とされる。
【００５６】
以上のように、データ復元処理装置５０は、符号長マーカの符号長ごとに、符号ベース５３Ａ及び符号カウンタ５３Ｂを備えることで、圧縮データにおける符号長マーカが付与された部分木を読み込んだ際に、当該部分木に対応するデータ及び符号を復元することができる。これにより、圧縮データが圧縮される際に用いられた辞書テーブルを復元することができ、復元した辞書テーブルを用いて、圧縮データから元のデータを復元することができる。
【００５７】
次に、図４に示す木構造データについて、符号割当装置２０、データ圧縮処理装置３０、及びデータ復元処理装置５０の動作を順に説明する。図４に示す木構造データは、中間ノード（「中間ａ」、「中間ｂ」）と葉ノード（「９８７」、「“ｆｏｏ”」、「１．２３」、「“ｂａｒ”」）とを備え、「根」を根ノードとする木構造データである。ここで、各ノードの左側の角括弧付数字は、本実施形態における当該木構造データの巡回順を示す。
【００５８】
図５を用いて、符号割当装置２０の動作について説明する。まず、木構造構築部１１が、処理対象のデータ構造に基づいて、図４に示す木構造データを構築する（ステップＳ５０１）。続いて、部分木等価性判定部１２及び共通部分木検出部１３が、木構造データにおける全ての共通部分木を検出する（ステップＳ５０２）。その後、出現回数計数部１４が、共通部分木ごとの出現回数を計数し（ステップＳ５０３）、出現順序検出部１５が、共通部分木の最初の出現位置において共通部分木間で比較した際の出現順序を検出する（ステップＳ５０４）。
【００５９】
続いて、第一ソート部２１が、出現回数及び出現順序に基づいて、共通部分木をソートし（ステップＳ５０５、第一ソートステップ）、仮符号割当部２２が、各共通部分木へ仮符号を割り当てる（ステップＳ５０６、仮符号割当ステップ）。図６に、各共通部分木の根ノード、出現回数、出現順序、仮符号割当部２２が割り当てた仮符号、及び当該仮符号の符号長を、第一ソート部２１によるソート順に並べたものを示す。なお、本実施形態では、符号「０」及び「１」の符号長は１バイト、「２」以上の符号の符号長は２バイトとする。従って、本実施形態では、符号化側及び復号化側で事前に合意しておくべき符号ベースは、符号長１バイトについては「０」、符号長２バイトについては「２」となる。ここで、符号カウンタの初期値は「０」、更新幅は「１」とする。
【００６０】
続いて、第二ソート部２４が、仮符号の符号長及び出現順序に基づいて、共通部分木をソートし（ステップＳ５０７、第二ソートステップ）、符号割当部２５が、各共通部分木へ符号を割り当てる（ステップＳ５０８、符号割当ステップ）。図７に、各共通部分木の根ノード、符号長、出現順序、符号割当部２５が割り当てた符号、及び後述する符号長マーカ付与ステップにおいて付与される符号長マーカを、第二ソート部２４によるソート順に並べたものを示す。
【００６１】
図８を用いて、データ圧縮処理装置３０の動作について説明する。まず、符号割当部２５が各共通部分木に割り当てた符号に基づいて、辞書テーブル生成部３１が、辞書テーブルを生成する（ステップＳ８０１、辞書テーブル生成ステップ）。続いて、符号長マーカ付与部３２が、木構造データを深さ優先で巡回し、巡回先の部分木が共通部分木であるか否かを判定する（ステップＳ８０２、ステップＳ８０３）。当該部分木が共通部分木である場合には、符号長マーカ付与部３２は、当該共通部分木における最初の出現か否かを判定する（ステップＳ８０３：ＹＥＳ、ステップＳ８０４）。
【００６２】
最初の出現である場合には、符号長マーカ付与部３２は、当該部分木に符号長マーカを付与する（ステップＳ８０４：ＹＥＳ、ステップＳ８０５、符号長マーカ付与ステップ）。２回目以降の出現である場合には、辞書式圧縮処理部３３が、辞書テーブルを参照して、当該部分木を対応する符号に置き換えることで圧縮する（ステップＳ８０４：ＮＯ、ステップＳ８０６、辞書式圧縮処理ステップ）。上記の符号長マーカ付与部３２及び辞書式圧縮処理部３３による処理がされたデータ（圧縮データ）は、データ保存部４０に保存される（ステップＳ８０７）。
【００６３】
以上の処理は、全ての部分木に対して完了するまで行われる（ステップＳ８０８：ＹＥＳ、ステップＳ８０９）。全ての部分木に対して処理が完了したら、処理を終了する（ステップＳ８０８：ＮＯ）。
【００６４】
図９は、図８のデータ圧縮処理後の圧縮データを木構造データとして概念的に表した図である。ここで、山括弧「＜＞」付数字で表される部分木は、辞書式圧縮処理部３３により対応する符号に置き換えられた部分木を示す。また、丸括弧「（）」付数字は、各部分木に付与された符号長マーカを示す。ここで、「“ｂａｒ”」については、木構造データにおいて１回しか出現しないため、辞書式圧縮処理の対象とならず、元のデータのままとなっている。
【００６５】
図１０は、データ復元処理装置５０の動作を示すフロー図である。まず、圧縮データ読込部５１が、復元すべき圧縮データを部分木ごとに順次読み込む（ステップＳ１０１：ＹＥＳ、ステップＳ１０２、圧縮データ読込ステップ）。続いて、符号長マーカ判定部５２Ａが、部分木に符号長マーカが付与されているか否かを判定する（ステップＳ１０３、辞書項目抽出ステップ）。符号長マーカ判定部５２Ａが、部分木に符号長マーカが付与されていると判定した場合（ステップＳ１０３：ＹＥＳ）には、符号長マーカ抽出部５２Ｂが符号長マーカを抽出し（ステップＳ１０４、辞書項目抽出ステップ）、部分木抽出部５２Ｃが部分木を抽出する（ステップＳ１０５、辞書項目抽出ステップ）。
【００６６】
続いて、符号復元部５３が、符号ベース５３Ａ及び符号カウンタ５３Ｂを用いて、符号を復元する（ステップＳ１０６、符号復元ステップ）。図１１を用いて、符号復元部５３が各共通部分木の符号を復元する仕組みについて説明する。図１１は、共通部分木を、符号が復元される順に並べたものであり、各共通部分木の符号長マーカ（「（１）」、「（２）」）と、符号長マーカに対応する符号ベース５２Ｂ（「０」、「２」）及び符号カウンタ５２Ｃ（「カウンタ（１）」、「カウンタ（２）」）と、符号復元部５３により復元される符号とを示す。
【００６７】
図１１に示すように、符号復元部５３は、「中間ｂ」を根ノードとする部分木について、符号ベース（「２」）と「カウンタ（２）」のカウンタ値（「０」）との和を算出することで、当該和に対応する符号（「＜２＞」）を当該部分木の符号として復元する。この際、符号復元部５３は、「カウンタ（２）」のカウンタ値を、更新幅（「１」）だけインクリメントすることで、カウンタ値を「１」に更新する。続いて、符号復元部５３は、「９８７」を根ノードとする部分木（この場合は、「９８７」の葉ノードのみ）について、符号ベース（「２」）と「カウンタ（２）」のカウンタ値（「１」）との和を算出し、符号（「＜３＞」）を復元する。その後、同様の処理が繰り返されることで、図１１に示すように、各共通部分木の符号が復元される。以上により、符号復元部５３は、各共通部分木の符号を正しく復元する（図９及び図１１参照）。
【００６８】
続いて、辞書テーブル復元部５４が、部分木抽出部５２Ｃが抽出した部分木と符号復元部５３が復元した符号との組を辞書テーブルに登録する（ステップＳ１０７、辞書テーブル復元ステップ）。また、抽出された部分木は、木構造データの復号結果に含める必要があるため、ステップＳ１１０にて復号結果にそのまま出力される。
【００６９】
また、符号長マーカ判定部５２Ａが、部分木に符号長マーカが付与されていないと判定した場合（ステップＳ１０３：ＮＯ）には、引き続き、符号の参照か否かの判定がされる（ステップＳ１０８）。ここで、符号の参照である場合（ステップＳ１０８：ＹＥＳ）には、復号処理部５５が辞書テーブルを参照して復号処理を行う（ステップＳ１０９）。符号の参照でない場合、すなわち、通常ノードの場合（ステップＳ１０８：ＮＯ）には、そのまま出力される（ステップＳ１１０）。
【００７０】
データ復元処理装置５０は、以上の処理が復元すべき圧縮データの全てについて完了したら、処理を完了する（ステップＳ１０１：ＮＯ）。
【００７１】
次に、図１２を用いて、コンピュータを符号割当装置２０、データ圧縮処理装置３０、及びデータ復元処理装置５０として機能させるための符号割当プログラムＰ２０、データ圧縮処理プログラムＰ３０、及びデータ復元処理プログラムＰ５０について説明する。
【００７２】
図１２（ａ）は、符号割当方法を実行することができる符号割当プログラムＰ２０のモジュールを示すブロック図である。図１２（ａ）に示すように、符号割当プログラムＰ２０は、第一ソートモジュールＰ２１、仮符号割当モジュールＰ２２、第二ソートモジュールＰ２３、及び符号割当モジュールＰ２４を備える。上記各モジュールが実行されることにより実現される機能は、上述した符号割当装置２０において対応する第一ソート部２１、仮符号割当部２２、第二ソート部２３、及び符号割当部２４の機能と同様である。
【００７３】
図１２（ｂ）は、データ圧縮処理方法を実行することができるデータ圧縮処理プログラムＰ３０のモジュールを示すブロック図である。図１２（ｂ）に示すように、データ圧縮処理プログラムＰ３０は、辞書テーブル生成モジュールＰ３１、符号長マーカ付与モジュールＰ３２、及び辞書式圧縮処理モジュールＰ３３を備える。上記各モジュールが実行されることにより実現される機能は、上述したデータ圧縮処理装置３０において対応する辞書テーブル生成部３１、符号長マーカ付与部３２、及び辞書式圧縮処理部３３の機能と同様である。
【００７４】
図１２（ｃ）は、データ復元処理方法を実行することができるデータ復元処理プログラムＰ５０のモジュールを示すブロック図である。図１２（ｃ）に示すように、データ復元処理プログラムＰ５０は、圧縮データ読込モジュールＰ５１、辞書項目抽出モジュールＰ５２、符号復元モジュールＰ５３、及び辞書テーブル復元モジュールＰ５４を備える。上記各モジュールが実行されることにより実現される機能は、上述したデータ復元処理装置５０において対応する圧縮データ読込部５１、辞書項目抽出部５２、符号復元部５３、及び辞書テーブル復元部５４の機能と同様である。
【００７５】
このように構成された符号割当プログラムＰ２０、データ圧縮処理プログラムＰ３０、及びデータ復元処理プログラムＰ５０はそれぞれ、図３に示す記録媒体１１０に記憶され、符号割当装置２０、データ圧縮処理装置３０、又はデータ復元処理装置５０として用いられるコンピュータにより実行される。当該コンピュータは、記録媒体１１０が記録媒体読取部１０７に挿入されると、記録媒体読取部１０７から記録媒体１１０に格納された符号割当プログラムＰ２０、データ圧縮処理プログラムＰ３０、又はデータ復元処理プログラムＰ５０にアクセス可能となり、符号割当プログラムＰ２０、データ圧縮処理プログラムＰ３０、又はデータ復元処理プログラムＰ５０を実行することによって、本実施形態に係る符号割当装置２０、データ圧縮処理装置３０、又はデータ復元処理装置５０として動作することが可能となる。
【００７６】
符号割当プログラムＰ２０、データ圧縮処理プログラムＰ３０、及びデータ復元処理プログラムＰ５０はそれぞれ、搬送波に重畳されたコンピュータデータ信号としてネットワークを介して提供されるものであってもよい。この場合、符号割当装置２０、データ圧縮処理装置３０、又はデータ復元処理装置５０として用いられるコンピュータは、通信制御部１０４によって受信した符号割当プログラムＰ２０、データ圧縮処理プログラムＰ３０、又はデータ復元処理プログラムＰ５０を主記憶部１０２に格納することにより、符号割当プログラムＰ２０、データ圧縮処理プログラムＰ３０、又はデータ復元処理プログラムＰ５０を実行することができる。
【００７７】
以上説明したように、本実施形態におけるデータ処理システム１は、上記の符号割当装置２０を備えることにより、第一の処理（第一ソート部２１、仮符号割当部２２）により、出現回数が多い順（出現回数が同じ場合は出現順序の若い順）に、符号長の短い符号（仮符号）が各共通部分木に対して割り当てられる。続いて、第二の処理（第二ソート部２３、符号割当部２４）により、符号長の短い順（符号長が同じ場合は出現順序の若い順）に、符号長の短い符号が各共通部分木に対して再割当される。このような二段階の処理により、出現回数が多い共通部分木から優先して符号長の短い符号を割り当てるようにしつつ、同一符号長となる共通部分木に対しては、出現順序が若い順に、符号を割り当てることができる。これにより、データ圧縮処理装置３０において、圧縮データのサイズをより効率的に削減することを可能にすると共に、データ復元処理装置５０において、圧縮データを復元することを可能にすることができる。
【００７８】
また、本実施形態におけるデータ処理システム１は、上記のデータ圧縮処理装置３０を備えることにより、共通部分木の最初の出現位置における第１部分木に対応するデータについては、符号長マーカ付与部３２が符号長マーカを付与した上で圧縮データにそのまま埋め込むことで、辞書テーブルに相当する情報を圧縮データに埋め込むことができる。これにより、圧縮データに埋め込む辞書テーブルに相当する情報から符号を省略できる。さらに、第１部分木１つ分の符号の参照（符号への置き換え）が減ることにより、共通部分木１つにつき、符号のサイズと符号長マーカのサイズとの差分だけ、データサイズを削減することができる。以上により、辞書テーブルのサイズの格納及びその参照に要するデータのサイズを削減することができる。
【００７９】
また、本実施形態におけるデータ処理システム１は、上記のデータ復元処理装置５０を備えることにより、符号長マーカの符号長ごとに、符号ベース５３Ａ及び符号カウンタ５３Ｂを備えることで、圧縮データにおける符号長マーカが付与された部分木を読み込んだ際に、当該部分木に対応するデータ及び符号を復元することができる。これにより、圧縮データの圧縮に用いられた辞書テーブルを復元し、復元した辞書テーブルを用いて圧縮データから元のデータを復元することができる。
【００８０】
以上により、本実施形態におけるデータ処理システム１によれば、データの圧縮及び復元ができることを担保しつつ、辞書テーブルの格納及びその参照に要するデータのサイズを削減することができる。
【００８１】
以上、本発明に係る実施形態について詳細に説明した。しかし、本発明は、上記実施形態に限定されるものではない。本発明は、その要旨を逸脱しない範囲において様々な変形が可能である。
【符号の説明】
【００８２】
１…データ処理システム、２０…符号割当装置、２１…第一ソート部、２２…仮符号割当部、２３…第二ソート部、２４…符号割当部、３０…データ圧縮処理装置、３１…辞書テーブル生成部、３２…符号長マーカ付与部、３３…辞書式圧縮処理部、５０…データ復元処理装置、５１…圧縮データ読込部、５２…辞書項目抽出部、５３…符号復元部、５３Ａ…符号ベース、５３Ｂ…符号カウンタ、５４…辞書テーブル復元部、Ｐ２０…符号割当プログラム、Ｐ３０…データ圧縮処理プログラム、Ｐ５０…データ復元処理プログラム。
【図１】
2014023101.tif 000003
【図２】
2014023101.tif 000004
【図３】
2014023101.tif 000005
【図４】
2014023101.tif 000006
【図５】
2014023101.tif 000007
【図６】
2014023101.tif 000008
【図７】
2014023101.tif 000009
【図８】
2014023101.tif 000010
【図９】
2014023101.tif 000011
【図１０】
2014023101.tif 000012
【図１１】
2014023101.tif 000013
【図１２】
2014023101.tif 000014