(57)【要約】【課題】木構造データにおける共通部分木について、適切な出現回数を高速に得る。【解決手段】部分木出現回数補正装置４０は、木構造データにおける等価な部分木ごとに、補正前出現回数を計数する補正前出現回数計数部４１Ａと、高さが１以上の等価な部分木ごとに補正用出現回数を計数する補正用出現回数計数部４１Ｂと、補正用出現回数が２以上の等価な部分木である第１部分木と該第１部分木の直接の子であって等価な部分木である第２部分木とについて、該第２部分木が該第１部分木の直接の子として出現する子出現回数を計数する子出現回数計数部４２と、第１部分木と第２部分木との全ての組み合わせについて、第１部分木の補正用出現回数と子出現回数とに基づいて第２部分木の補正前出現回数を補正することで、第２部分木の補正後出現回数を得る出現回数補正部４３と、を備える。【選択図】図２
2014021909.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、１９９９年発行、ｐ．２８７−２９５
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、Ｈｕｆｆｍａｎ符号を有効に動作させるには、各々の「共通部分木」の出現回数を適切に検出する必要がある。これは、より出現回数の多い「共通部分木」により短い符号を割り当てるほど、Ｈｕｆｆｍａｎ符号による圧縮効果が高まるためである。
【０００６】
しかしながら、「共通部分木」の出現回数を適切に検出するには、木構造データ特有の問題を考慮する必要がある。例えば図１の状況では、「中間ａ」、「中間ｂ」、及び、「“ｆｏｏ”」を根ノードとする、それぞれ高さが「２」、「１」、「０」であり、出現回数が２回である「共通部分木」が存在する。しかし図１の状況では、「中間ａ」を根ノードとする「共通部分木」のみを検出して辞書テーブルを構築すれば事足りる。なぜならば、「中間ｂ」および「“ｆｏｏ”」を根ノードとする部分木は「中間ａ」を根ノードとする部分木に包含されているためである。図１の「中間ｂ」や「“ｆｏｏ”」を辞書テーブルに含める（辞書項目とする）ことは、以下の２つの理由から避けるべきである。
【０００７】
第一に、辞書テーブルのサイズを無駄に肥大化させないためである。辞書テーブルを用いたＨｕｆｆｍａｎ符号を行う場合、何らかの手段を用いて符号化側と復号化側とで辞書テーブルを共有する必要があるが、辞書テーブルのサイズが小さい程、辞書テーブルの移動、辞書テーブルへのアクセス、辞書テーブル保存領域などの観点から有利となる。
【０００８】
第二に、「共通部分木」に割り当てる符号を無駄使いしないためである。例えば符号長がバイト単位に整列されている場合、１バイトで表現できる符号の数は限られている。そのような場合、本来辞書項目とする必要のないものに符号が割り当てられると、符号が無駄に消費されてしまう。
【０００９】
上記の観点から「共通部分木」の適切な出現回数を計数する方法として、まず木構造データ全体を巡回してユニーク（等価）な部分木を全て検出し、等価な部分木ごとに各１回ずつ、それらの直接の子として出現する部分木のみについて出現回数をカウントする方法が考えられる。図１の例では、等価な部分木は「根」、「中間ａ」、「中間ｂ」、及び「“ｆｏｏ”」を根ノードとする部分木である。この場合、「中間ａ」は「根」の直接の子として２回、「中間ｂ」は「中間ａ」の直接の子として１回、「“ｆｏｏ”」は「中間ｂ」の直接の子として１回、出現する。従って、辞書テーブルに含めるために検出すべき「共通部分木」は、「中間ａ」を根ノードとする部分木のみであり、その出現回数は２回であることがわかる。
【００１０】
しかしながら、上記の方法では、まず等価な部分木を全て把握するために木構造データ全体を少なくとも１回巡回した後に、等価な部分木の直接の子として出現する部分木の出現回数を計数するために、木構造データをもう一度巡回する必要が生じる。特に、共通部分木が存在しない場合には、結果的に、全てのノードを２回巡回する必要が生じてしまう。例えばビッグデータ処理では、膨大な数のレコードからなるデータを扱うため、個々のレコードの処理時間を少しでも短縮することが、全体として大きな処理時間短縮に寄与する。このような観点から、木構造データ中に共通部分木が存在しない場合には、２回目の木構造データの巡回を省略し、共通部分木が存在する場合には、当該共通部分木についてのみ、必要な計数処理を行うことが望ましい。
【００１１】
そこで、本発明は、木構造データにおける共通部分木ごとに適切な出現回数を高速に得ることを目的とする。
【課題を解決するための手段】
【００１２】
本発明に係る部分木出現回数補正装置は、値を保持する葉ノードと、葉ノード又は他の中間ノードを子ノードとして保持する中間ノードと、親ノードを持たない唯一の中間ノードである根ノードと、を備える木構造データにおける部分木の出現回数を補正する部分木出現回数補正装置であって、木構造データにおける等価な部分木ごとに、該等価な部分木の出現回数を該等価な部分木の補正前出現回数として計数する補正前出現回数計数部と、高さが１以上の等価な部分木ごとに、該等価な部分木の出現回数を該等価な部分木の補正用出現回数として計数する補正用出現回数計数部と、補正用出現回数が２以上の等価な部分木である第１部分木と、該第１部分木の直接の子であって等価な部分木である第２部分木とについて、該第２部分木が該第１部分木の直接の子として出現する子出現回数を計数する子出現回数計数部と、第１部分木と第２部分木との全ての組み合わせについて、第１部分木の補正用出現回数と子出現回数とに基づいて第２部分木の補正前出現回数を補正することで、第２部分木の補正後出現回数を得る出現回数補正部と、を備える。
【００１３】
本発明に係る部分木出現回数補正方法は、上記の部分木出現回数補正装置により実行される部分木出現回数補正方法であって、木構造データにおける等価な部分木ごとに、該等価な部分木の出現回数を該等価な部分木の補正前出現回数として計数する補正前出現回数計数ステップと、高さが１以上の等価な部分木ごとに、該等価な部分木の出現回数を該等価な部分木の補正用出現回数として計数する補正用出現回数計数ステップと、補正用出現回数が２以上の等価な部分木である第１部分木と、該第１部分木の直接の子であって等価な部分木である第２部分木とについて、該第２部分木が該第１部分木の直接の子として出現する子出現回数を計数する子出現回数計数ステップと、第１部分木と第２部分木との全ての組み合わせについて、第１部分木の補正用出現回数と子出現回数とに基づいて第２部分木の補正前出現回数を補正することで、第２部分木の補正後出現回数を得る出現回数補正ステップと、を含む。
【００１４】
本発明に係る部分木出現回数補正プログラムは、上記の部分木出現回数補正装置に設けられたコンピュータを、木構造データにおける等価な部分木ごとに、該等価な部分木の出現回数を該等価な部分木の補正前出現回数として計数する補正前出現回数計数部と、高さが１以上の等価な部分木ごとに、該等価な部分木の出現回数を該等価な部分木の補正用出現回数として計数する補正用出現回数計数部と、補正用出現回数が２以上の等価な部分木である第１部分木と、該第１部分木の直接の子であって等価な部分木である第２部分木とについて、該第２部分木が該第１部分木の直接の子として出現する子出現回数を計数する子出現回数計数部と、第１部分木と第２部分木との全ての組み合わせについて、第１部分木の補正用出現回数と子出現回数とに基づいて第２部分木の補正前出現回数を補正することで、第２部分木の補正後出現回数を得る出現回数補正部、として機能させる。
【００１５】
このような形態では、高さが１以上且つ出現回数が２以上の等価な部分木ごとに、その直接の子であって等価な部分木の出現回数（補正前出現回数）を、木構造データを巡回して算出した値（補正用出現回数、子出現回数）に基づいて計算（補正）することで、木構造データを再度巡回することなく、適切な出現回数（補正後出現回数）を高速に得ることができる。
【００１６】
上記の部分木出現回数補正装置では、補正前出現回数計数部は、等価な部分木が任意の中間ノードの直接の子として複数回連続して出現する場合に、該連続に係る出現をまとめて１回の出現として、補正前出現回数を計数し、子出現回数計数部は、第２部分木が第１部分木の直接の子として複数回連続して出現する場合に、該連続に係る出現をまとめて１回の出現として、子出現回数を計数してもよい。
【００１７】
このような形態では、補正前出現回数及び子出現回数について、複数回連続して出現する箇所をまとめて１回の出現として計数することで、連長圧縮（ＲＬＥ：Ｒｕｎ  Ｌｅｎｇｔｈ  Ｅｎｃｏｄｉｎｇ）を適用する場合に適した補正後出現回数を得ることができる。ここで、連長圧縮とは、連続して出現する等価なデータを、当該データ及び連続長（連続回数）により表現することでデータを圧縮する技術である。なお、補正用出現回数については、連長圧縮を用いるか否かにかかわらず、正味の出現回数が計数される。
【００１８】
本発明に係るデータ圧縮処理装置は、請求項１に記載の部分木出現回数補正装置と、補正後出現回数が２以上の部分木を符号化対象部分木とし、該符号化対象部分木に対応するデータのデータ長よりも短い符号を該符号化対象部分木に割り当て、該符号を該符号化対象部分木に紐づけて格納した辞書テーブルを生成する辞書テーブル生成部と、辞書テーブルを参照して、符号化対象部分木に対応するデータを、該符号化対象部分木に紐づけられた符号に置き換えることでデータを圧縮する辞書式圧縮処理部と、を備える。
【００１９】
このような形態では、補正後出現回数が２以上である辞書項目とすべき部分木（符号化対象部分木）のみを対象として、符号の割当及び辞書テーブルへの格納を行った上で、データを圧縮することができる。これにより、辞書式圧縮処理において、不要なデータへの符号の割当及び不要なデータの辞書テーブルへの格納を防止できる。従って、辞書テーブルのサイズが無駄に肥大化してしまうのを防ぐと共に、無駄な処理の発生を抑え、効率的かつ高速に辞書式圧縮を行うことができる。
【００２０】
本発明に係るデータ圧縮処理装置は、請求項２に記載の部分木出現回数補正装置と、補正後出現回数が２以上の部分木を符号化対象部分木とし、該符号化対象部分木に対応するデータのデータ長よりも短い符号を該符号化対象部分木に割り当て、該符号を該符号化対象部分木に紐づけて格納した辞書テーブルを生成する辞書テーブル生成部と、辞書テーブルを参照して、符号化対象部分木に対応するデータを、該符号化対象部分木に紐づけられた符号に置き換えることでデータを圧縮する辞書式圧縮処理部と、任意の中間ノードの子として複数回連続して出現する部分木に対応するデータに対して連長圧縮を行う連長圧縮処理部と、を備える。
【００２１】
このような形態では、連長圧縮を適用することができ、且つ、辞書テーブルのサイズが無駄に肥大化してしまうのを防ぐと共に、無駄な処理の発生を抑え、効率的かつ高速に辞書式圧縮を行うことができる。さらに、連長圧縮を行うことにより、連長圧縮を行わない場合よりも、データ圧縮効率を高めることができる。
【発明の効果】
【００２２】
本発明によれば、木構造データにおける共通部分木について、適切な出現回数を高速に得ることができる。
【図面の簡単な説明】
【００２３】
【図１】本発明の課題を説明するために用いる木構造データを示す図である。
【図２】実施形態に係る部分木出現回数補正装置の機能構成を示すブロック図である。
【図３】実施形態に係る部分木出現回数補正装置のハードウェア構成を示すブロック図である。
【図４】実施形態に係る木構造データを示す図である。
【図５】実施形態に係る部分木出現回数補正装置の動作を示すフロー図である。
【図６】実施例１に係る出現回数の計数結果を示す図である。
【図７】実施例１に係る木構造データと圧縮処理との対応を示す図である。
【図８】実施例２に係る出現回数の計数結果を示す図である。
【図９】実施例２に係る木構造データと圧縮処理との対応を示す図である。
【図１０】実施形態に係る部分木出現回数補正プログラムの機能構成を示すブロック図である。
【発明を実施するための形態】
【００２４】
以下、添付図面を参照しながら本発明の実施形態を詳細に説明する。なお、図面の説明において同一又は同等の要素には同一の符号を付し、重複する説明を省略する。
【００２５】
まず、図１を用いて、本実施形態における処理対象となる木構造データについて説明する。図１に示すように、木構造データは、値を保持する葉ノードと、葉ノード又は他の中間ノードを子ノードとして保持する中間ノードと、親ノードを持たない唯一の中間ノードである根ノードと、各ノード間を結ぶエッジとからなるデータ構造である。木構造データの実装方法としては、各ノードに子ノードへのポインタを保持させる方法や各ノードに親ノードへのポインタを保持させる方法などのいくつかの方法があるが、実装方法はこれらの方法のいずれかに限定されない。
【００２６】
次に、本明細書で用いるいくつかの表現について定義する。本明細書中において、「部分木」とは、木構造データにおける任意のノード以下の要素（ノード、エッジ）のみによって構成される木のことをいう。すなわち、部分木とは、当該任意のノードを根ノードとする木を意味する。また、ノードＡを根ノードとする部分木Ａと、ノードＢを根ノードとする部分木Ｂについて、ノードＢがノードＡの子ノードに該当する場合に、「部分木ＡはノードＢ（又は部分木Ｂ）の子である」と表現する。
【００２７】
また、単に「子」又は「子ノード」と記載した場合には、「孫」又は「孫ノード」が含まれてもよく、「直接の子」又は「直接の子ノード」と記載した場合には、直接の親子関係にある「子」又は「子ノード」のみを意味し、「孫」又は「孫ノード」は含まれないものとする。また、任意の２つの部分木について、各部分木のノード構成、すなわち、全てのノード要素の位置、種別（葉又は中間）、及び値（葉ノードの場合）が完全一致するときに、これらの部分木は「等価」であるという。
【００２８】
次に、実施形態に係るデータ圧縮処理装置１００の機能要素について、図２を用いて説明する。データ圧縮処理装置１００は、木構造構築部１０、木構造巡回部２０、部分木等価性判定部３０、部分木出現回数補正装置４０、辞書テーブル生成部５０、及び圧縮処理部６０を備える。部分木出現回数補正装置４０は、補正前出現回数計数部４１Ａ及び補正用出現回数計数部４１Ｂを備えた出現回数計数部４１と、子出現回数計数部４２と、補正後出現回数テーブル４３Ａを備えた出現回数補正部４３とを備える。補正前出現回数計数部４１Ａ及び補正用出現回数計数部４１Ｂはそれぞれ、補正前出現回数テーブル４１ａ及び補正用出現回数テーブル４１ｂを備える。圧縮処理部６０は、辞書式圧縮処理部６０Ａと、連長圧縮処理部６０Ｂとを備える。
【００２９】
部分木出現回数補正装置４０のハードウェア構成を図３に示す。図３に示すように、部分木出現回数補正装置４０は、オペレーティングシステムやアプリケーションプログラムなどを実行するＣＰＵ４０１と、ＲＯＭ及びＲＡＭで構成される主記憶部４０２と、ハードディスクメモリなどで構成される補助記憶部４０３と、データ通信を行う通信制御部４０４と、液晶モニタなどで構成される出力部４０５と、入力デバイスであるキーボード及びマウス等で構成される操作部４０６と、ＣＤ−ＲＯＭやＤＶＤなどの記録媒体４１０を読み取る記録媒体読取部４０７とを備える。
【００３０】
図２に示す部分木出現回数補正装置４０の各機能は、ＣＰＵ４０１の制御の下で、主記憶部４０２に所定のソフトウェアプログラムを読み込ませて実行することにより実現される。その際、ＣＰＵ４０１は、ソフトウェアプログラムの処理手順に従い、主記憶部４０２及び補助記憶部４０３におけるデータの読み出し及び書き込み動作を制御し、操作部４０６、出力部４０５及び通信制御部４０４の動作を制御する。
【００３１】
図２の木構造構築部１０は、木構造データを構築する機能要素である。木構造構築部１０は、オブジェクト構造を有するデータについて、各オブジェクトを木構造における各ノードに対応させるように木構造データを構築する。
【００３２】
木構造巡回部２０は、木構造構築部１０により構築された木構造データを巡回する機能要素である。木構造巡回部２０の巡回処理により、部分木等価性判定部３０及び出現回数計数部４１が、巡回先のノードについて各処理を行う。木構造巡回部２０は、木構造データの全てのノードを少なくとも１回巡回することで、部分木等価性判定部３０及び出現回数計数部４１が全てのノードについての処理を完了できるように巡回処理を行う。
【００３３】
部分木等価性判定部３０は、処理対象のノードを根ノードとする部分木が既に巡回したノードを根ノードとする部分木と等価な部分木であるか否かを判定する。このような判定を行う方法は特に限定されないが、本実施形態においては、部分木等価性判定部３０の判定結果に基づいて、木構造データにおける等価な部分木ごとにユニークな値となる識別ＩＤを割り当てることにより、木構造データにおける全ての部分木を、等価な部分木ごとに分類するものとする。
【００３４】
部分木出現回数補正装置４０は、木構造データにおける各部分木について、最初に計数した出現回数（補正前出現回数）を補正し、適切な出現回数（補正後出現回数）を得る装置である。補正後出現回数は、部分木に対応するデータ（以下、「部分木に対応するデータ」のことを単に「部分木」と表記する。）を辞書項目とすべきか否かを判定し、辞書項目とすべきと判定した部分木に対して割り当てるべき符号を決定するための判断材料となる。
【００３５】
出現回数計数部４１は、木構造データにおける等価な部分木ごとの出現回数（補正前出現回数）を計数する補正前出現回数計数部４１Ａと、高さが１以上の等価な部分木ごとの出現回数（補正用出現回数）を計数する補正用出現回数計数部４１Ｂとを備えた機能要素である。補正前出現回数計数部４１Ａ及び補正用出現回数計数部４１Ｂは、木構造巡回部２０が巡回したノード（以下、巡回したノードを根ノードとする部分木を「巡回部分木」と表記する。）について、部分木等価性判定部３０による判定結果に基づいて、巡回部分木と等価な部分木の出現回数を計数する。
【００３６】
補正前出現回数計数部４１Ａは、後述する連長圧縮（ＲＬＥ：Ｒｕｎ  Ｌｅｎｇｔｈ  Ｅｎｃｏｄｉｎｇ）が用いられない場合には、等価な部分木ごとの正味の出現回数を補正前出現回数として計数する。補正前出現回数計数部４１Ａは、連長圧縮が用いられる場合には、等価な部分木が任意の中間ノードの直接の子として複数回連続して出現する箇所についてはまとめて１回の出現として補正前出現回数を計数する。補正用出現回数計数部４１Ｂは、連長圧縮が用いられるか否かにかかわらず、等価な部分木ごとの正味の出現回数を補正用出現回数として計数する。
【００３７】
補正前出現回数及び補正用出現回数の計数方法は特に限定されないが、本実施形態においては、補正前出現回数計数部４１Ａ及び補正用出現回数計数部４１Ｂは、巡回部分木の識別ＩＤと既に巡回された部分木の識別ＩＤを参照することにより、同じ識別ＩＤを持つ部分木（等価な部分木）ごとの補正前出現回数及び補正用出現回数を計数するものとする。補正前出現回数計数部４１Ａ及び補正用出現回数計数部４１Ｂは、上記計数処理により得た補正前出現回数及び補正用出現回数をそれぞれ、補正前出現回数テーブル４１ａ及び補正用出現回数テーブル４１ｂに格納する。
【００３８】
子出現回数計数部４２は、補正用出現回数が２以上の等価な部分木（第１部分木）とその直接の子である等価な部分木（第２部分木）とについて、第２部分木が第１部分木の直接の子として出現する回数（子出現回数）を計数する機能要素である。子出現回数計数部４２は、補正前出現回数計数部４１Ａと同様に、連長圧縮が用いられる場合には、第２部分木が第１部分木の直接の子として複数回連続して出現する箇所についてはまとめて１回の出現として、子出現回数を計数する。第２部分木が第１部分木の直接の子であるか否か、すなわち、第２部分木の根ノードが第１部分木の根ノードの直接の子であるか否かについては、例えば、木構造データに実装されているポインタ（親ノードから子ノードへのポインタ、又は、子ノードから親ノードへのポインタ）などを参照することにより、判定することができる。また、任意の２つの部分木が等価であるか否かは、上述した識別ＩＤにより判定することができる。子出現回数計数部４２は、上記のような判定を行うことなどにより、子出現回数を計数する。
【００３９】
出現回数補正部４３は、第１部分木と第２部分木との全ての組み合わせについて、第２部分木の補正前出現回数を補正し、補正後出現回数を得る機能要素である。第２部分木の補正前出現回数をＬとし、第１部分木の補正用出現回数をＭとし、第１部分木に対する第２部分木の子出現回数をＮとすると、出現回数補正部４３は、「Ｌ−Ｎ×（Ｍ−１）」の数式で表される計算を行うことにより、第１部分木の補正前出現回数を補正（更新）する。出現回数補正部４３は、このような補正処理を第１部分木と第２部分木との全ての組み合わせについて行うことにより、各第２部分木についての補正後出現回数（全ての補正処理がされた後の補正前出現回数）を得る。出現回数補正部４３は、当該補正後出現回数を補正後出現回数テーブル４３Ａに格納する。
【００４０】
辞書テーブル生成部５０は、辞書式圧縮処理に用いるための辞書テーブルを生成する機能要素である。辞書テーブル生成部５０は、補正後出現回数テーブル４３Ａを参照して、補正後出現回数が２以上の部分木（符号化対象部分木）を抽出すると共に、当該符号化対象部分木に対応するデータのデータ長よりも短い符号を当該符号化対象部分木に割り当てる。辞書テーブル生成部５０は、上記のように符号化対象部分木に割り当てた符号を、当該符号化対象部分木に紐づけて格納した辞書テーブルを生成する。ここで、辞書テーブル生成部５０は、補正後出現回数が多い符号化対象部分木に優先的に短い符号を割り当てることにより、後述する辞書式圧縮処理部６０Ａの辞書式圧縮による圧縮効率を高めることができる。
【００４１】
圧縮処理部６０は、辞書式圧縮を行う辞書式圧縮処理部６０Ａと連長圧縮を行う連長圧縮処理部６０Ｂとをまとめた機能要素である。
【００４２】
辞書式圧縮処理部６０Ａは、辞書テーブルを参照して、木構造データにおける符号化対象部分木に対応するデータを対応する符号に置き換えることでデータを圧縮する辞書式圧縮処理を行う機能要素である。
【００４３】
連長圧縮処理部６０Ｂは、木構造データにおける任意の中間ノードの子として複数回連続して出現する部分木について連長圧縮を行う機能要素である。連長圧縮とは、連続するデータを、データ一つ分の情報と連続回数とで表現することにより、データを圧縮する方法である。例えば、辞書式圧縮処理部６０Ａにより「Ａ」という符号に置き換えられた部分木が任意の中間ノードの子として５回連続で出現した場合には、連長圧縮処理部６０Ｂは、当該連続部分を「ＡＡＡＡＡ」ではなく「Ａ５」と表現することにより、データサイズを縮小する。
【００４４】
上記のような連長圧縮を行う場合には、正味の出現回数が多い等価な部分木であっても、連続して出現する回数が多い場合には、連長圧縮によりデータ表現を短くすることができるため、辞書式圧縮処理により優先的に短い符号を割り当てる必要がなくなる場合がある。すなわち、正味の出現回数がより少ない等価な部分木であっても、連続して出現する部分がより少ない（連長圧縮による圧縮効果が期待できない）等価な部分木に対して、より短い符号を割り当てた方が、全体として圧縮効率が高まる場合がある。
【００４５】
上記の理由により、連長圧縮を行う場合には、補正前出現回数計数部４１Ａ及び子出現回数計数部４２は、連続して出現する部分をまとめて１回として計数する。これにより、データ圧縮処理装置１００が辞書式圧縮処理と併せて連長圧縮を行う場合であっても、辞書テーブル生成部５０が補正後出現回数のより多いものから順により短い符号を割り当てることで、辞書式圧縮と連長圧縮を併せた圧縮処理全体における圧縮効果を最大化することができる。
【００４６】
次に、図４に示す実施例に係る木構造データを用いて、図５に示すデータ圧縮処理装置１００の動作を説明する。実施例１で、圧縮処理として辞書式圧縮のみを行う場合について説明する。実施例２で、圧縮処理として辞書式圧縮と共に連長圧縮を行う場合について説明する。
【００４７】
（実施例１）
木構造構築部１０は、処理対象のデータ構造に基づいて、図４に示すような木構造データを構築する（ステップＳ１）。その後、木構造巡回部２０は、当該木構造データにおける全ての部分木について、等価な部分木の検出と補正前出現回数及び補正用出現回数の計数とを行うために、木構造の巡回を開始する（ステップＳ２）。
【００４８】
部分木等価性判定部３０は、巡回された部分木について等価性判定及び識別ＩＤの割当を行う（ステップＳ３）。続いて、補正前出現回数計数部４１Ａは、巡回された部分木について補正前出現回数を計数し、補正前出現回数テーブル４１ａに格納し、当該部分木が高さ１以上の部分木である場合には、補正用出現回数計数部４１Ｂは、補正用出現回数を計数し、補正用出現回数テーブル４１ｂに格納する（ステップＳ４、補正前出現回数計数ステップ、補正用出現回数計数ステップ）。部分木等価性判定部３０及び出現回数計数部４１による上記処理が木構造データにおける全ての部分木について完了するまで、木構造巡回部２０が巡回処理を行う（ステップＳ５：ＹＥＳ、ステップＳ６）。上記の処理が全ての部分木について完了した時点（ステップＳ５：ＮＯ）で、各等価な部分木について、図６に示す補正前出現回数が格納された補正前出現回数テーブル４１ａと、補正用出現回数が格納された補正用出現回数テーブル４１ｂが得られる。
【００４９】
続いて、出現回数補正部４３による処理が行われる。まず、出現回数補正部４３は、補正用出現回数テーブル４１ｂを参照して、補正用出現回数が２以上の部分木（第１部分木）である「中間ａ」を選択する（ステップＳ７：ＹＥＳ、ステップＳ８）。次に、出現回数補正部４３は、第１部分木（中間ａ）の直接の子である未処理の部分木（第２部分木）である「“ｆｏｏ”」を選択する（ステップＳ９：ＹＥＳ、ステップＳ１０）。
【００５０】
出現回数補正部４３は、子（“ｆｏｏ”）の補正前出現回数Ｌ（１０回）を補正前出現回数テーブル４１ａから取得し（ステップＳ１１）、親（中間ａ）の補正用出現回数Ｍ（４回）を補正用出現回数テーブル４１ｂから取得する（ステップＳ１２）。また、子出現回数計数部４２が、子（“ｆｏｏ”）が親（中間ａ）の直接の子として出現する子出現回数Ｎ（２回）を計数する（ステップＳ１３、子出現回数計数ステップ）。出現回数補正部４３は、「Ｌ−Ｎ×（Ｍ−１）」の計算により、子（“ｆｏｏ”）の補正前出現回数Ｌを４回（「１０−２×（４−１）＝４」）に補正する（ステップＳ４）。
【００５１】
その後、「中間ａ」の直接の子である「１．２３」についても同様の処理（ステップＳ９：ＹＥＳ、ステップＳ１０〜ステップＳ１４）が行われ、「中間ａ」の直接の子である未処理の部分木がなくなると（ステップＳ９：ＮＯ）、出現回数補正部４３は、補正用出現回数が２以上の未処理の部分木である「中間ｂ」を選択する（ステップＳ７：ＹＥＳ、ステップＳ８）。続いて、「中間ｂ」の未処理の部分木「“ｆｏｏ”」を選択する（ステップＳ９：ＹＥＳ、ステップＳ１０）。
【００５２】
出現回数補正部４３は、上述した処理と同様の処理により、子（“ｆｏｏ”）の補正前出現回数Ｌ（４回：「中間ａ」の子として補正された後の値）、及び親（中間ｂ）の補正用出現回数Ｍ（２回）を取得し（ステップＳ１１、ステップＳ１２）、子出現回数計数部４２は、子（“ｆｏｏ”）が親（中間ｂ）の直接の子として出現する子出現回数Ｎ（１回）を計数する（ステップＳ１３、子出現回数計数ステップ）。続いて、出現回数補正部４３は、「Ｌ−Ｎ×（Ｍ−１）」の計算により、子（“ｆｏｏ”）の補正前出現回数Ｌを３回（「４−１×（２−１）＝３」）に補正する（ステップＳ１４、出現回数補正ステップ）。
【００５３】
その後、「中間ｂ」の直接の子である「９８７」についても同様の処理（ステップＳ９：ＹＥＳ、ステップＳ１０〜ステップＳ１４）が行われ、「中間ｂ」の直接の子である未処理の部分木がなくなり（ステップＳ９：ＮＯ）、補正用出現回数が２以上の未処理の部分木がなくなると（ステップＳ７：ＮＯ）、辞書テーブル生成部５０による辞書テーブル生成処理がされる（ステップＳ１５）。上記の出現回数補正処理により、図６に示す補正後出現回数が格納された補正後出現回数テーブル４３Ａが得られる。
【００５４】
辞書テーブル生成部５０は、補正後出現回数テーブル４３Ａを参照して、補正後出現回数が２以上である部分木について、補正後出現回数が多い部分木から順に、より短い符号を割り当てることにより、辞書テーブルを生成する（ステップＳ１５）。本実施形態では、辞書テーブル生成部５０は、「中間ａ」→「“ｆｏｏ”」→「中間ｂ」→「１．２３」の順に、より短い符号を割り当て、これらを辞書項目として辞書テーブルに格納する。辞書テーブル生成部５０は、補正後出現回数が１回である「９８７」には符号を割り当てず、辞書項目として辞書テーブルに格納しない。
【００５５】
続いて、辞書式圧縮処理部６０Ａが、辞書テーブルを参照して、木構造データに対して辞書式圧縮を行う（ステップＳ１６）。図７に、木構造データと辞書式圧縮との対応を示す。ここで、図７において「参照」と表記されている部分木が、辞書式圧縮により符号に置き換えられた部分木を示している。
【００５６】
ここで、辞書テーブル生成部５０が単純な出現回数（補正される前の「補正前出現回数」）に基づいて辞書テーブルを生成した場合には、「中間ａ」よりも「１．２３」に短い符号が割り当てられてしまう可能性がある。さらに、「９８７」についても符号の割当及び辞書テーブルへの格納がされてしまう。しかし、より上位の部分木において辞書式圧縮されることを考慮すると、「１．２３」に「中間ａ」よりも短い符号を割り当ててしまうと、「中間ａ」に「１．２３」よりも短い符号を割り当てる場合よりも、圧縮効率が悪化する。さらに、「９８７」に符号を割り当て、辞書テーブルに格納することは無駄な処理である。
【００５７】
以上のように、辞書テーブル生成部５０が、単純な出現回数ではなく、適切な出現回数（補正後出現回数）に基づいて、辞書テーブルを生成することで、データの圧縮効率及び処理効率を高めることができる。
【００５８】
（実施例２）
実施例２は、圧縮処理において、辞書式圧縮処理と併せて連長圧縮を行う点、及び、補正前出現回数計数部４１Ａ及び子出現回数計数部４２が、等価な部分木が複数回連続して出現する場合に、当該連続に係る出現をまとめて１回の出現として補正前出現回数及び子出現回数を計数する点において、実施例１とは異なる。以下、実施例２について、実施例１と異なる部分についてのみ説明する。
【００５９】
「中間ｂ」は、根ノードの直接の子として２回連続して出現する。そのため、補正前出現回数計数部４１Ａは、「中間ｂ」について、上記の連続して出現する部分をまとめて１回の出現として計数することで、補正前出現回数「１回」を得る。同様に、補正前出現回数計数部４１Ａは、「１．２３」についても２回連続して出現する部分をまとめて１回の出現として計数することで、補正前出現回数「４回」を得る（ステップＳ４、補正前出現回数計数ステップ）。
【００６０】
「１．２３」は「中間ａ」の直接の子として２回出現するが、当該出現は連続している。そのため、子出現回数計数部４２は、「１．２３」が「中間ａ」の直接の子として出現する子出現回数Ｎを「１回」と計数する（ステップＳ１３、子出現回数計数ステップ）。続いて、出現回数補正部４３は、「１．２３」の補正前出現回数Ｌ（４回）を、「中間ａ」の補正用出現回数Ｍ（４回）と子出現回数計数部４２が上述のように計数した子出現回数Ｎ（１回）に基づいて、１回（「４−１×（４−１）＝１」）に補正する（ステップＳ１４、出現回数補正ステップ）。
【００６１】
図８に、実施例２における各等価な部分木の補正用出現回数、補正前出現回数、及び補正後出現回数を示す。
【００６２】
辞書テーブル生成部５０は、図８に示す補正後出現回数に基づいて辞書テーブルを生成し（ステップＳ１５）、辞書式圧縮処理部６０Ａが当該辞書テーブルを参照して辞書式圧縮処理を行った後に、連長圧縮処理部６０Ｂが連長圧縮処理を行う（ステップＳ１６）。
【００６３】
図９に、実施例２における木構造データと辞書式圧縮との対応を示す。ここで、図９において「参照」と表記されている部分木が、辞書式圧縮により符号に置き換えられた部分木を示しており、「ＲＬＥ」と表記されている部分木が、連長圧縮により省略された部分木を示している。
【００６４】
以上のように、実施例２では、実施例１において符号が割り当てられ、辞書項目として辞書テーブルに格納されていた「中間ｂ」及び「１．２３」について、符号が割り当てられず、辞書項目として辞書テーブルに格納されない。これは、上述のように、補正前出現回数計数部４１Ａ及び子出現回数計数部４２が、連長圧縮されることまで考慮して、各計数処理を行った結果、辞書項目とする必要がない「中間ｂ」及び「１．２３」については、補正後出現回数が「１回」と計数されたからである。
【００６５】
次に、図１０を用いて、コンピュータを部分木出現回数補正装置４０として機能させるための部分木出現回数補正プログラムＰ４０について説明する。
【００６６】
図１０は、部分木出現回数補正方法を実行することができる部分木出現回数補正プログラムＰ４０のモジュールを示すブロック図である。図１０に示すように、部分木出現回数補正プログラムＰ４０は、補正前出現回数計数モジュールＰ４１Ａ、補正用出現回数計数モジュールＰ４１Ｂ、子出現回数計数モジュールＰ４２、及び出現回数補正モジュールＰ４３を備える。上記各モジュールが実行されることにより実現される機能は、上述した部分木出現回数補正装置４０において対応する補正前出現回数計数部４１Ａ、補正用出現回数計数部４１Ｂ、子出現回数計数部４２、及び出現回数補正部４３の機能と同様である。
【００６７】
このように構成された部分木出現回数補正プログラムＰ４０は、図３に示す記録媒体４１０に記憶され、部分木出現回数補正装置４０として用いられるコンピュータにより実行される。当該コンピュータは、記録媒体４１０が記録媒体読取部４０７に挿入されると、記録媒体読取部４０７から記録媒体４１０に格納された部分木出現回数補正プログラムＰ４０にアクセス可能となり、当該部分木出現回数補正プログラムＰ４０を実行することによって、本実施形態に係る部分木出現回数補正装置４０として動作することが可能となる。
【００６８】
部分木出現回数補正プログラムＰ４０は、搬送波に重畳されたコンピュータデータ信号としてネットワークを介して提供されるものであってもよい。この場合、部分木出現回数補正装置４０として用いられるコンピュータは、通信制御部４０４によって受信した部分木出現回数補正プログラムＰ４０を主記憶部４０２に格納することにより、当該部分木出現回数補正プログラムＰ４０を実行することができる。
【００６９】
以上説明したように、本実施形態によれば、部分木出現回数補正装置４０により、木構造データにおける各等価な部分木の適切な出現回数（補正後出現回数）を、木構造データの巡回を行うことなく、計算（補正）のみで高速に得ることができる。また、辞書テーブル生成部５０が、補正後出現回数が２以上の部分木について、補正後出現回数が多い順により短い符号を割り当てることで、圧縮処理部６０による圧縮効率を高めることができる。さらに、不要な部分木要素を辞書項目とすることを防止することができるため、無駄な処理（符号割当及び辞書テーブルへの格納）を省くことで処理効率を向上させることができる。さらに、不要な部分木要素が辞書テーブルへ格納されないことで、辞書テーブルのデータサイズを必要最小限のものとすることができる。
【００７０】
以上、本発明に係る実施形態について詳細に説明した。しかし、本発明は、上記実施形態に限定されるものではない。本発明は、その要旨を逸脱しない範囲において様々な変形が可能である。
【符号の説明】
【００７１】
４０…部分木出現回数補正装置、４１Ａ…補正前出現回数計数部、４１Ｂ…補正用出現回数計数部、４１ａ…補正前出現回数テーブル、４１ｂ…補正用出現回数テーブル、４２…子出現回数計数部、４３…出現回数補正部、４３Ａ…補正後出現回数テーブル、５０…辞書テーブル生成部、６０…圧縮処理部、６０Ａ…辞書式圧縮処理部、６０Ｂ…連長圧縮処理部、Ｐ４０…部分木出現回数補正プログラム、Ｐ４１Ａ…補正前出現回数計数モジュール、Ｐ４１Ｂ…補正用出現回数計数モジュール、Ｐ４２…子出現回数計数モジュール、Ｐ４３…出現回数補正モジュール。
【図１】
2014021909.tif 000003
【図２】
2014021909.tif 000004
【図３】
2014021909.tif 000005
【図４】
2014021909.tif 000006
【図５】
2014021909.tif 000007
【図６】
2014021909.tif 000008
【図７】
2014021909.tif 000009
【図８】
2014021909.tif 000010
【図９】
2014021909.tif 000011
【図１０】
2014021909.tif 000012