(57)【要約】【課題】木構造データの直列化処理を高速化する。【解決手段】データ直列化装置１は、各ノードを根ノードとする部分木毎に、当該部分木の大きさに基づく重みを決定する重み決定部１０４と、重み決定部１０４により決定された各部分木の重みに基づいて、木構造データを、それぞれ直列化順序が連続する一以上のノードからなる複数のノード列に分割する分割部１０５と、分割部１０５により分割されて生成された複数のノード列のそれぞれに対して１つのスレッドを割り当てるスレッド割当部１０６と、スレッド毎に並列して、ノード列に含まれる各ノードに対応するデータを直列化順序でバイト列に直列化する直列化部１０７と、直列化部１０７によって得られたスレッド毎の直列化結果を直列化順序で結合する結合部１０８と、結合部１０８により結合された直列化結果を出力する出力部１０９と、を備える。【選択図】図１
2014206828.tif 000002
【特許請求の範囲】
【請求項１】
値を保持する葉ノードと、葉ノード又は他の中間ノードを子ノードとして保持する中間ノードと、親ノードを持たない唯一の中間ノードである根ノードと、を有する木構造データを、予め定めた直列化順序で直列化するデータ直列化装置であって、
各ノードを根ノードとする部分木毎に、当該部分木の大きさに基づく重みを決定する重み決定手段と、
前記重み決定手段により決定された各部分木の重みに基づいて、前記木構造データを、それぞれ前記直列化順序が連続する一以上のノードからなる複数のノード列に分割する分割手段と、
前記分割手段により分割されて生成された前記複数のノード列のそれぞれに対して１つのスレッドを割り当てるスレッド割当手段と、
前記スレッド毎に並列して、前記ノード列に含まれる各ノードに対応するデータを前記直列化順序でバイト列に直列化する直列化手段と、
前記直列化手段によって得られた前記スレッド毎の直列化結果を前記直列化順序で結合する結合手段と、
前記結合手段により結合された直列化結果を出力する出力手段と、
を備えるデータ直列化装置。
【請求項２】
前記直列化手段が、前記木構造データにおいて複数回出現する等価な部分木を示す重複部分木単位に所定の圧縮処理を実行した上で直列化を実行し、
前記分割手段が、前記重複部分木に含まれるノードと、前記直列化順序における当該ノードの直前のノードとを分割しないように、前記木構造データを分割する、
請求項１記載のデータ直列化装置。
【請求項３】
前記直列化手段が、前記所定の圧縮処理のうちに含まれる圧縮処理の一つとして、前記重複部分木に対応するデータと符号とを予め対応付けて記憶している辞書テーブルに基づいて前記重複部分木に対応するデータを前記符号に置き換える辞書式圧縮を実行し、
前記分割手段が、前記直列化手段により前記辞書式圧縮が実行される対象となる部分木の根ノードと、前記直列化順序における当該根ノードの直前のノードとを分割することを許容して、前記木構造データを分割する、
請求項２記載のデータ直列化装置。
【請求項４】
前記重み決定手段が、前記所定の圧縮処理が実行される対象となる前記重複部分木の重みを、前記所定の圧縮処理が実行されない場合よりも小さくする、
請求項２又は３記載のデータ直列化装置。
【請求項５】
前記分割手段が、前記重み決定手段により決定された各部分木の重みに基づいて定まる前記ノード列毎の重みが前記ノード列間で均等化されるように、前記木構造データを分割する、
請求項１〜４の何れか一項記載のデータ直列化装置。
【請求項６】
前記分割手段が、前記重み決定手段により決定された各部分木の重みに基づいて定まる前記ノード列毎の重みが前記直列化順序の若い前記ノード列ほど小さくなるように、前記木構造データを分割する、
請求項１〜４の何れか一項記載のデータ直列化装置。
【請求項７】
前記結合手段が、前記スレッド毎の直列化結果を前記直列化順序で一つずつ入力して所定のデータ圧縮処理を実行した上で、前記スレッド毎の直列化結果を結合する、
請求項６記載のデータ直列化装置。
【請求項８】
値を保持する葉ノードと、葉ノード又は他の中間ノードを子ノードとして保持する中間ノードと、親ノードを持たない唯一の中間ノードである根ノードと、を有する木構造データを、予め定めた直列化順序で直列化するデータ直列化装置により実行されるデータ直列化方法であって、
各ノードを根ノードとする部分木毎に、当該部分木の大きさに基づく重みを決定する重み決定ステップと、
前記重み決定ステップにおいて決定された各部分木の重みに基づいて、前記木構造データを、それぞれ前記直列化順序が連続する一以上のノードからなる複数のノード列に分割する分割ステップと、
前記分割ステップにおいて分割されて生成された前記複数のノード列のそれぞれに対して１つのスレッドを割り当てるスレッド割当ステップと、
前記スレッド毎に並列して、前記ノード列に含まれる各ノードに対応するデータを前記直列化順序でバイト列に直列化する直列化ステップと、
前記直列化ステップにおいて得られた前記スレッド毎の直列化結果を前記直列化順序で結合する結合ステップと、
前記結合ステップにおいて結合された直列化結果を出力する出力ステップと、
を含むデータ直列化方法。
【請求項９】
値を保持する葉ノードと、葉ノード又は他の中間ノードを子ノードとして保持する中間ノードと、親ノードを持たない唯一の中間ノードである根ノードと、を有する木構造データを、予め定めた直列化順序で直列化するデータ直列化装置に設けられたコンピュータを、
各ノードを根ノードとする部分木毎に、当該部分木の大きさに基づく重みを決定する重み決定手段と、
前記重み決定手段により決定された各部分木の重みに基づいて、前記木構造データを、それぞれ前記直列化順序が連続する一以上のノードからなる複数のノード列に分割する分割手段と、
前記分割手段により分割されて生成された前記複数のノード列のそれぞれに対して１つのスレッドを割り当てるスレッド割当手段と、
前記スレッド毎に並列して、前記ノード列に含まれる各ノードに対応するデータを前記直列化順序でバイト列に直列化する直列化手段と、
前記直列化手段によって得られた前記スレッド毎の直列化結果を前記直列化順序で結合する結合手段と、
前記結合手段により結合された直列化結果を出力する出力手段、
として機能させるためのデータ直列化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特に木構造データを直列化するデータ直列化装置、データ直列化方法、及びデータ直列化プログラムに関する。
【背景技術】
【０００２】
近年、ビッグデータと呼ばれる膨大な量のデータを扱うための大規模データ処理基盤として、例えばオープンソースソフトウェアのHadoop等が広く利用されている。ビッグデータの処理においては、少しでもデータサイズを縮小するために、データをテキスト形式ではなくバイナリ形式で保存する方法が主流である。そのために、Hadoopでは、SequecneFile（下記非特許文献１参照）及びProtocolBuffers（下記非特許文献２参照）等のシリアライザ／デシリアライザ（Serializer/Deserializer）が用いられる。シリアライザは、HDD（Hard Disk Drive）やSSD(Solid State Drive)といったストレージへの保存及びネットワーク上での送受信等のために、計算機内のメモリ上のデータをバイト列に変換（直列化）する技術である。デシリアライザは、シリアライザにより直列化されたバイト列から元のデータを復元する技術である。SequenceFile及びProtocolBuffers等は、木構造データとして表現した個々のレコード（葉ノード、及び、根ノードを含む中間ノード）を、TLV（Type-Length-Value）形式によるバイナリ形式のバイト列に直列化する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Tom  White著、“Hadoop:  The  Definitive  Guide”、O'Reilly  Media、２００９年５月発行、ｐ.１１１
【非特許文献２】Google、“ProtocolBuffers”、［ｏｎｌｉｎｅ］、インターネット＜ＵＲＬ：http://code.google.com/p/protobuf/＞
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、直列化すべき元データのサイズが大きい場合、直列化に要する処理時間も当然長くなる。近年、一台の計算機に搭載されるＣＰＵコアの数が増えてきており、その計算資源を有効活用するために複数スレッドを使用したプログラムが開発されている。そこで、バイナリ形式への直列化処理を複数スレッドで並列処理することで処理を高速化できると考えられる。しかしながら、非特許文献１及び２に示されるSequenceFile及びProtocolBuffers等は、単一スレッドで動作するように設計及び実装されており、直列化処理を複数スレッドで並列処理することはできないという問題がある。
【０００５】
そこで、本発明は、木構造データの直列化処理を高速化することができるデータ直列化装置、データ直列化方法、及びデータ直列化プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明に係るデータ直列化装置は、値を保持する葉ノードと、葉ノード又は他の中間ノードを子ノードとして保持する中間ノードと、親ノードを持たない唯一の中間ノードである根ノードと、を有する木構造データを、予め定めた直列化順序で直列化するデータ直列化装置であって、各ノードを根ノードとする部分木毎に、当該部分木の大きさに基づく重みを決定する重み決定手段と、重み決定手段により決定された各部分木の重みに基づいて、木構造データを、それぞれ直列化順序が連続する一以上のノードからなる複数のノード列に分割する分割手段と、分割手段により分割されて生成された複数のノード列のそれぞれに対して１つのスレッドを割り当てるスレッド割当手段と、スレッド毎に並列して、ノード列に含まれる各ノードに対応するデータを直列化順序でバイト列に直列化する直列化手段と、直列化手段によって得られたスレッド毎の直列化結果を直列化順序で結合する結合手段と、結合手段により結合された直列化結果を出力する出力手段と、を備える。
【０００７】
本発明に係るデータ直列化方法は、値を保持する葉ノードと、葉ノード又は他の中間ノードを子ノードとして保持する中間ノードと、親ノードを持たない唯一の中間ノードである根ノードと、を有する木構造データを、予め定めた直列化順序で直列化するデータ直列化装置により実行されるデータ直列化方法であって、各ノードを根ノードとする部分木毎に、当該部分木の大きさに基づく重みを決定する重み決定ステップと、重み決定ステップにおいて決定された各部分木の重みに基づいて、木構造データを、それぞれ直列化順序が連続する一以上のノードからなる複数のノード列に分割する分割ステップと、分割ステップにおいて分割されて生成された複数のノード列のそれぞれに対して１つのスレッドを割り当てるスレッド割当ステップと、スレッド毎に並列して、ノード列に含まれる各ノードに対応するデータを直列化順序でバイト列に直列化する直列化ステップと、直列化ステップにおいて得られたスレッド毎の直列化結果を直列化順序で結合する結合ステップと、結合ステップにおいて結合された直列化結果を出力する出力ステップと、を含む。
【０００８】
本発明に係るデータ直列化プログラムは、値を保持する葉ノードと、葉ノード又は他の中間ノードを子ノードとして保持する中間ノードと、親ノードを持たない唯一の中間ノードである根ノードと、を有する木構造データを、予め定めた直列化順序で直列化するデータ直列化装置に設けられたコンピュータを、各ノードを根ノードとする部分木毎に、当該部分木の大きさに基づく重みを決定する重み決定手段と、重み決定手段により決定された各部分木の重みに基づいて、木構造データを、それぞれ直列化順序が連続する一以上のノードからなる複数のノード列に分割する分割手段と、分割手段により分割されて生成された複数のノード列のそれぞれに対して１つのスレッドを割り当てるスレッド割当手段と、スレッド毎に並列して、ノード列に含まれる各ノードに対応するデータを直列化順序でバイト列に直列化する直列化手段と、直列化手段によって得られたスレッド毎の直列化結果を直列化順序で結合する結合手段と、結合手段により結合された直列化結果を出力する出力手段、として機能させる。
【０００９】
このような形態によれば、木構造データの各部分木の大きさに基づく重みに基づいて分割境界が決定され、当該分割境界で分割されたノード列毎に、それぞれ独立したスレッドが割り当てられる。これにより、ノード列毎の直列化処理が各スレッドにおいて並列実行され、最終的に、スレッド毎に得られた直列化結果が結合されて出力される。このように木構造データの直列化処理を複数スレッドで並列的に処理することにより、木構造データの直列化処理を高速化することができる。
【００１０】
上記データ直列化装置では、直列化手段が、木構造データにおいて複数回出現する等価な部分木を示す重複部分木単位に所定の圧縮処理を実行した上で直列化を実行し、分割手段が、重複部分木に含まれるノードと、直列化順序における当該ノードの直前のノードとを分割しないように、木構造データを分割する構成としてもよい。
【００１１】
重複部分木単位の圧縮処理としては、例えば、辞書式圧縮及び連長圧縮（ＲＬＥ：Ｒｕｎ−Ｌｅｎｇｔｈ−Ｅｎｃｏｄｉｎｇ）等がある。直列化処理をこのような圧縮処理と併せて実行する場合において、連長圧縮対象となる複数の重複部分木が別々のスレッドに割り当てられると、各スレッドは独立して処理を行うため、連長圧縮が適切に実行されないおそれがある。また、辞書式圧縮対象となる同一の重複部分木に含まれる複数のノードが別々のスレッドに割り当てられると、一方のスレッドと他方のスレッドとで矛盾する処理がされてデータに矛盾が生じる問題を惹き起こすおそれがある。上記データ直列化装置では、分割手段が、重複部分木に含まれるノードと、直列化順序における当該ノードの直前のノードとを分割しないように木構造データを分割することにより、上述の問題を回避することができる。
【００１２】
上記データ直列化装置では、直列化手段が、所定の圧縮処理のうちに含まれる圧縮処理の一つとして、重複部分木に対応するデータと符号とを予め対応付けて記憶している辞書テーブルに基づいて重複部分木に対応するデータを符号に置き換える辞書式圧縮を実行し、分割手段が、直列化手段により辞書式圧縮が実行される対象となる部分木の根ノードと、直列化順序における当該根ノードの直前のノードとを分割することを許容して、木構造データを分割する構成としてもよい。
【００１３】
木構造データが、辞書式圧縮が実行される対象となる部分木の根ノードの直前位置で分割されたとしても、上述のような圧縮処理における問題は生じない。したがって、上記データ直列化装置によれば、このような位置での分割を許容することで、木構造データの分割位置をより柔軟に決定することができる。
【００１４】
上記データ直列化装置では、重み決定手段が、所定の圧縮処理が実行される対象となる重複部分木の重みを、所定の圧縮処理が実行されない場合よりも小さくする構成としてもよい。
【００１５】
直列化処理において併せて重複部分木に対する圧縮処理がされる場合には、重複部分木単位で所定の符号及び記号等に置き換えられる。すなわち、圧縮処理が実行される対象となる重複部分木に対する直列化処理は、実質的に当該重複部分木の根ノードに対してのみ行われることなるため、圧縮処理がされない場合と比較して、処理量が減少することが期待される。したがって、上記データ直列化装置によれば、所定の圧縮処理が実行される対象となる重複部分木に対して、直列化における実際の処理量に応じたより適切な重み付けを決定することができる。
【００１６】
上記データ直列化装置では、分割手段が、重み決定手段により決定された各部分木の重みに基づいて定まるノード列毎の重みがノード列間で均等化されるように、木構造データを分割する構成としてもよい。
【００１７】
上記データ直列化装置によれば、分割手段によって各スレッドに割り当てられるノード列毎の重みを均等化するように木構造データを分割することで、各スレッドに割り当てられる処理量を均等化できる。これにより、特定のスレッドに処理負荷が偏ってしまうことを回避し、全スレッドの処理が完了するまでの時間を短縮することができる。
【００１８】
上記データ直列化装置では、分割手段が、重み決定手段により決定された各部分木の重みに基づいて定まるノード列毎の重みが直列化順序の若いノード列ほど小さくなるように、木構造データを分割する構成としてもよい。
【００１９】
例えば、直列化結果同士の結合方法として、スレッド毎に得られた直列化結果を入力し、入力された直列化結果に対して所定の処理（例えば圧縮処理）を順次実行した上で、直列化結果を結合することが考えられる。このような場合には、例えば、木構造データの一部分の直列化結果に対する所定の処理が完了する前に、当該木構造データの一部分に結合される次の部分についての直列化処理が完了してしまうと、当該次の部分に対する所定の処理を直ちに開始することができないため処理待ち時間が発生する。上記データ直列化装置によれば、木構造データの直列化順序の若いノード列ほど処理量（重み）が小さくなるように木構造データを分割することで、木構造データの前方に位置するノード列に対する直列化処理が、後方に位置するノード列よりも先に完了するようになる。これにより、全体の処理において、直列化処理と所定の処理とを一部並列的に実行させることができ、全体の処理効率を向上させることができる。
【００２０】
上記データ直列化装置では、結合手段が、スレッド毎の直列化結果を直列化順序で一つずつ入力して所定のデータ圧縮処理を実行した上で、スレッド毎の直列化結果を結合する構成としてもよい。
【００２１】
スレッド毎に得られた直列化結果同士を結合する方法としては、単純にこれらを結合する以外に、例えば、前方部分の直列化結果から順次ＺＩＰ圧縮等の従来のデータ圧縮処理を実行した上で結合する方法等がある。上記データ直列化装置によれば、木構造データの直列化順序の若い部分ほど処理量（重み）が小さくなるように木構造データを分割することで、木構造データの前方部分から先に直列化処理を完了させることができる。これにより、全体の処理において、直列化処理と所定のデータ圧縮処理とを一部並列的に実行させることができ、全体の処理効率を向上させることができる。
【発明の効果】
【００２２】
本発明によれば、木構造データの直列化処理を高速化することができる。
【図面の簡単な説明】
【００２３】
【図１】本発明の一実施形態に係るデータ直列化装置の機能構成を示すブロック図である。
【図２】データ直列化装置のハードウェア構成を示す図である。
【図３】木構造データの例を示す図である。
【図４】図３に示す木構造データを単一スレッドで直列化した場合における直列化結果を示す図である。
【図５】図３に示す木構造データを３つのノード列に分割する場合の分割境界の例を示す図である。
【図６】図３に示す木構造データを図５に示す分割境界で分割したスレッド毎に直列化した場合における直列化結果を示す図である。
【図７】図３に示す木構造データを単一スレッドで辞書式圧縮及び連長圧縮した上で直列化した場合における直列化結果を示す図である。
【図８】図３に示す木構造データを図５に示す分割境界で分割したスレッド毎に辞書式圧縮及び連長圧縮した上で直列化した場合における直列化結果を示す図である。
【図９】図３に示す木構造データを辞書式圧縮及び連長圧縮を考慮して分割する場合の分割境界の例を示す図である。
【図１０】図３に示す木構造データを図９に示す分割境界で分割したスレッド毎に辞書式圧縮及び連長圧縮した上で直列化した場合における直列化結果を示す図である。
【図１１】各スレッド間で負荷が均等になるように決定した分割境界の例を示す図である。
【図１２】図３に示す木構造データを図１１に示す分割境界で分割したスレッド毎に辞書式圧縮及び連長圧縮した上で直列化した場合における直列化結果を示す図である。
【図１３】スレッド間での負荷に傾斜をつけることによる効果を説明するための図である。
【図１４】データ直列化装置の動作を示すフロー図である。
【図１５】図９に示す分割境界を決定する処理を含む分割処理を示すフロー図である。
【図１６】実施形態に係るデータ直列化プログラムの機能構成を示す図である。
【発明を実施するための形態】
【００２４】
以下、添付図面を参照しながら本発明の実施形態を詳細に説明する。なお、図面の説明において同一又は同等の要素には同一の符号を付し、重複する説明を省略する。
【００２５】
図１は、本発明の一実施形態に係るデータ直列化装置の機能構成を示すブロック図である。図１に示すように、本実施形態に係るデータ直列化装置１は、木構造構築部１０１、重複部分木検出部１０２、辞書テーブル生成部１０３、重み決定部１０４、分割部１０５、スレッド割当部１０６、直列化部１０７、結合部１０８、及び出力部１０９を備える。
【００２６】
図２は、データ直列化装置１のハードウェア構成を示す図である。図２に示すように、データ直列化装置１は、オペレーティングシステム及びアプリケーションプログラム等を実行するＣＰＵ１１と、ＲＯＭ及びＲＡＭで構成される主記憶部１２と、ハードディスクメモリ等で構成される補助記憶部１３と、データ通信を行う通信制御部１４と、液晶モニタ等で構成される出力部１５と、入力デバイスであるキーボード及びマウス等で構成される操作部１６と、ＣＤ−ＲＯＭ及びＤＶＤ等の記録媒体１８を読み取る記録媒体読取部１７とを備える。
【００２７】
図１に示すデータ直列化装置１の各機能は、ＣＰＵ１１の制御の下で、主記憶部１２に所定のソフトウェアプログラムを読み込ませて実行することにより実現される。その際、ＣＰＵ１１は、ソフトウェアプログラムの処理手順に従い、主記憶部１２及び補助記憶部１３におけるデータの読み出し及び書き込み動作を制御し、操作部１６、出力部１５及び通信制御部１４の動作を制御する。
【００２８】
図１に戻り、データ直列化装置１を構成する各機能要素について説明する。
【００２９】
木構造構築部１０１は、データ直列化装置１による直列化処理を実行する対象となる木構造データを構築する機能要素である。木構造構築部１０１は、例えばオブジェクト構造を有するデータについて、各オブジェクトを木構造における各ノードに対応させるようにして、図３に示すような木構造データを構築する。
【００３０】
図３に示すように、木構造データは、値を保持する葉ノード（「１２３」、「４５６」、「９．８７」、「６．５４」、「ｈｏｇｅ」、「ｆｏｏ」）と、葉ノード又は他の中間ノードを子ノードとして保持する中間ノード（「中間」）と、親ノードを持たない唯一の中間ノードである根ノード（「根」）と、各ノード間を結ぶエッジとからなるデータ構造である。木構造データの実装方法としては、各ノードに子ノードへのポインタを保持させる方法、及び各ノードに親ノードへのポインタを保持させる方法等のいくつかの方法があるが、実装方法はこれらの方法のいずれかに限定されない。
【００３１】
本明細書中において、「部分木」とは、木構造データにおける任意のノード以下の要素（ノード、エッジ）のみによって構成される木を意味する。すなわち、部分木とは、当該任意のノードを根ノードとする木を意味する。また、同一の木構造データにおいて複数回出現し、部分木の根ノード配下のノードの位置、型、及び値が互いに完全一致する部分木（等価な部分木）を「重複部分木」（「共通部分木」ともいう）という。
【００３２】
図３において、各ノードの左上に記載した数字は、親ノード優先かつ前方ノード優先かつ深さ優先といった条件に則って決定される各ノードの直列化順序の一例を示す。図３に示すように、この直列化順序は、任意の部分木について、親ノードが一番先となり、子ノード同士では前方（左側）に位置するノードの方が先となるような順序である。また、各ノードの右上に記載した数字は、当該ノードを根ノードとする部分木に含まれるノード数を示す。
【００３３】
重複部分木検出部１０２は、木構造データに含まれる重複部分木を検出する機能要素である。より具体的には、重複部分木検出部１０２は、例えば以下のようにして重複部分木を検出する。すなわち、重複部分木検出部１０２は、木構造構築部１０１により構築された木構造データを、例えば深さ優先探索等の予め定めた巡回順で巡回し、巡回先の各中間ノードにおいて、当該中間ノードを根ノードとする部分木の構成情報（当該部分木に含まれるノードの位置、型、及び値を示す情報）を取得する。重複部分木検出部１０２は、各中間ノードにおいて取得した部分木の構成情報同士を比較することにより、互いに構成情報が一致する部分木同士を重複部分木として検出する。ただし、上記方法は一例であり、重複部分木検出部１０２による重複部分木の検出方法は、特に限定されない。例えば、重複部分木検出部１０２は、特願２０１２−１６４０００号に記載されている方法等を用いて重複部分木を検出してもよい。
【００３４】
図３の例では、直列化順序が２のノード（以下、「直列化順序がＸのノード」を単に「ノードＸ」と表記する）を根ノードとする部分木とノード１８を根ノードとする部分木とは、根ノード配下のノードの位置、型、及び値が互いに完全一致しており、互いに等価な重複部分木を成している。同様に、ノード８を根ノードとする部分木とノード１１を根ノードとする部分木とは、互いに等価な重複部分木を成している。重複部分木検出部１０２は、木構造データに含まれる互いに等価な重複部分木の組を検出する。
【００３５】
辞書テーブル生成部１０３は、重複部分木検出部１０２により検出された重複部分木の各組について、当該組に関連付けられる重複部分木に対応するデータに対して、当該データよりもデータ長が短い符号が対応付けられた辞書テーブルを生成する機能要素である。図３の例において、辞書テーブル生成部１０３は、例えば、ノード２を根ノードとする部分木に対応するデータに対して符号Ｔ１が対応付けられ、ノード８を根ノードとする部分木に対応するデータに対して符号Ｔ２が対応付けられた辞書テーブルを生成する。
【００３６】
重複部分木検出部１０２による重複部分木の検出結果は、直列化部１０７が、木構造データを直列化する際に重複部分木単位の冗長性を利用した連長圧縮（ＲＬＥ：Ｒｕｎ−Ｌｅｎｇｈｔ−Ｅｎｃｏｄｉｎｇ）を行う場合に、分割部１０５及び直列化部１０７により参照される。また、辞書テーブル生成部１０３により生成された辞書テーブルは、直列化部１０７が、木構造データを直列化する際に重複部分木単位の冗長性を利用した辞書式圧縮を行う場合に、分割部１０５及び直列化部１０７により参照される。辞書式圧縮とは、重複部分木に対応するデータを辞書テーブルにおいて当該データに対応付けられた符号に置換することでデータサイズを縮小する圧縮処理である。連長圧縮とは、同一の根ノードを有し且つ連続して出現する互いに等価な重複部分木に対応するデータを、その連続長（繰り返し回数）により表現することでデータサイズを縮小する圧縮処理である。
【００３７】
重み決定部１０４は、木構造データにおける各ノードを根ノードとする部分木毎に、当該部分木の大きさに基づく重みを決定する重み決定手段である。重み決定部１０４は、各ノードを根ノードとする部分木に対して決定した重みを、当該ノードについての付加情報として当該ノードに関連付ける。各ノードに関連付けられた重みは、分割部１０５が木構造データを分割する際に参照される。
【００３８】
重み決定部１０４による重みの決定方法は特に限定されないが、重み決定部１０４は、例えば部分木に含まれるノード数を当該部分木の重みとして決定する。この際、重み決定部１０４は、ノードの型に関わらずノード一つ分を「１」として部分木の重みを決定してもよいし、例えばノードの型に応じてノード毎の重み付けを変えて部分木の重みを決定してもよい。例えば、重み決定部１０４は、４バイト長の整数型の葉ノードには「４」、８バイト長の実数型の葉ノードには「８」、文字列型の葉ノードには文字列長に比例する大きさ、上記の型のようなデータ（整数値、実数値、文字列）を格納しない中間ノードには「１」といった重み付けを行った上で、部分木の重みを決定してもよい。
【００３９】
例えば図３のノード４を根ノードとする部分木について、重み決定部１０４が前者の方法で重みを決定する場合には、当該部分木の重みは、「３」となる。一方、重み決定部１０４が後者の方法で当該部分木の重みを決定する場合には、当該部分木の重みは、当該部分木に含まれる各ノード（「中間」、「ｆｏｏ」、「１２３」）の重み付け（１，３，４）を足し合わせた「８」となる。本実施形態では、前者の方法で部分木の重みを決定するものとして説明する。したがって、図３の各ノードの右上の数字は、前者の方法で決定された重みを示している。
【００４０】
分割部１０５は、重み決定部１０４により決定された各部分木の重みに基づいて、木構造データを、それぞれ直列化順序が連続する一以上のノードからなる複数のノード列に分割する分割手段である。分割部１０５には、例えば分割数や各ノード列の重み（各ノード列に含まれる部分木の重み）の配分方法等を規定した分割戦略を示す情報が予め読み込まれている。
【００４１】
分割部１０５は、予め読み込まれている分割戦略を示す情報に基づいて木構造データを分割する。分割戦略を示す情報が分割部１０５に読み込まれる方法は何でもよい。例えば、分割戦略を示す情報は、分割部１０５による分割処理を実行するプログラムにおいてハードコーディングされてもよいし、分割処理実行時にオペレータ等に分割部１０５に入力させてもよいし、予め分割戦略を示す情報が指定された設定ファイルを分割部１０５に読み込ませてもよい。
【００４２】
分割部１０５に読み込まれる分割戦略は特に限定されないが、例えば、分割部１０５は、分割数を「３」とし、各ノード列の重みがノード列間で均等化されるように分割するといった分割戦略に基づいて、木構造データを分割することができる。図３の例では、木構造データの総重み（根ノード１に関連付けられた重み）が２８であるため、分割部１０５は、例えば各ノード列の重みが「１０」、「９」、「９」となるように木構造データを分割する。すなわち、分割部１０５は、図５に示す分割境界Ｄ１，Ｄ２で木構造データを分割することにより、木構造データをノード１〜１０からなる重みが１０のノード列（以下「ノード列１」と表記）と、ノード１１〜１９からなる重みが９のノード列（以下「ノード列２」と表記）と、ノード２０〜２８からなる重みが９のノード列（以下「ノード列３」と表記）とに分割する。
【００４３】
スレッド割当部１０６は、分割部１０５により分割されて生成された複数のノード列のそれぞれに対して１つのスレッドを割り当てるスレッド割当手段である。図５に示す分割境界Ｄ１，Ｄ２で分割部１０５によって木構造データが分割される場合には、スレッド割当部１０６は、ノード列１に対してスレッド１、ノード列２に対してスレッド２、ノード列３に対してスレッド３といったように各ノード列に対して異なるスレッドを割り当てる。スレッドとは、データ直列化装置１のＣＰＵ１１の制御の下で、それぞれ独立して並列的に処理を実行することが可能な実行単位をいう。各スレッドは、スレッド毎の処理結果を一時的に記憶するための記憶領域であるバッファを備える。
【００４４】
直列化部１０７は、スレッド割当部１０６により複数のノード列のそれぞれに対して割り当てられたスレッド毎に並列して、ノード列に含まれる各ノードに対応するデータを直列化順序でバイト列に直列化する直列化手段である。直列化部１０７は、各スレッドにおける直列化処理において、例えばノード列に含まれる各ノードに対応するデータを型（Ｔｙｐｅ）、長さ（Ｌｅｎｇｔｈ）、値（Ｖａｌｕｅ）の３つのフィールドからなるＴＬＶ形式で直列化する。
【００４５】
まず、重複部分木単位の辞書式圧縮及び連長圧縮を実行しない場合における、直列化部１０７による直列化について説明する。図４は、図３に示す木構造データを単一スレッドによりＴＬＶ形式で直列化した直列化結果の例を示す図である。図４の各ボックスの上に記載されている数字は、当該数字で示される直列化順序のノードに対応するデータの直列化結果の先頭位置を示している。また、各ボックス内の値は、ＴＬＶ形式における各フィールド値（型、長さ、値）を示している。
【００４６】
図４に示す直列化結果の例では、各ノードの型として、中間ノードを示す「Ｃ」、整数型を示す「Ｉ」、実数型を示す「Ｄ」、文字列型を示す「Ｓ」のいずれかが格納される。また、各ノードの長さとして、中間ノードでは「直接の子ノードの数」、文字列型では「文字列長」が格納され、４バイト固定長の整数型及び８バイト固定長の実数型ではノードの型とノードの長さとが一意に対応付けられるため省略される。また、各ノードの値としては、中間ノード以外の型では、それぞれの型に対応する値（整数値、実数値、文字列）が格納され、中間ノードでは省略される。
【００４７】
例えば、ノード１（「根」）は、中間ノードであり、直接の子ノードの数は４であるため、当該ノードに対応する直列化結果は「Ｃ，４」となる。また、ノード３（「ｈｏｇｅ」）は、文字列型であり、文字列長は４であるため、当該ノードに対応する直列化結果は「Ｓ，４，ｈｏｇｅ」となる。なお、直列化部１０７がノードの型、長さ、値等を示す情報を上記のように並べてＴＬＶ形式に直列化する処理自体は、従来周知の任意の手法により実行される。
【００４８】
直列化部１０７がスレッド割当部１０６によって割り当てられたスレッド１〜３による並列処理によって、スレッド毎に取得した直列化結果を、図６に示す。このようなスレッド毎の直列化結果は、各スレッドが備えるバッファに一時的に記憶される。
【００４９】
結合部１０８は、直列化部１０７によって得られたスレッド毎の直列化結果を直列化順序で結合する結合手段である。結合部１０８は、図６に示すようなスレッド毎の直列化結果を直列化順序（この場合には、スレッド１の直列化結果→スレッド２の直列化結果→スレッド３の直列化結果の順序）で結合することにより、図４に示すような分割前の木構造データに対応する一つの直列化結果を得る。また、結合部１０８は、用途に応じて様々な種類の結合処理を実行することができる。例えば、結合部１０８は、直列化結果を単に結合するのではなく、スレッド毎の直列化結果を直列化順序で一つずつ入力してＺＩＰ圧縮等のデータ圧縮処理（所定のデータ圧縮処理）を実行すると共に結合してもよい。このように具体的に実行する結合処理を示す情報は、結合部１０８による結合処理を実行するプログラムにおいてハードコーディングされてもよいし、結合処理実行時にオペレータ等によって結合部１０８に入力させてもよいし、予め結合処理を示す情報が指定された設定ファイルを結合部１０８に読み込ませてもよい。結合部１０８がＺＩＰ圧縮等のデータ圧縮処理を実行しつつ直列化結果を結合する場合の詳細については後述する。
【００５０】
出力部１０９は、結合部１０８により結合された直列化結果を出力する出力手段である。出力部１０９は、例えば、通信ネットワークを介して直列化結果を利用する所定のサーバ装置（不図示）等に出力したり、直列化結果を一定期間保存しておくためのストレージ（不図示）に出力したりといった出力処理を行う。
【００５１】
以上のように、データ直列化装置１によれば、重み決定部１０４によって決定された木構造データの各部分木の大きさ（本実施形態では「部分木に含まれるノード数」）に基づく重みに基づいて、分割部１０５によって分割境界Ｄ１，Ｄ２が決定される。続いて、当該分割境界Ｄ１，Ｄ２で分割されたノード列１〜３に対して、スレッド割当部１０６によってそれぞれ異なるスレッド１〜３が割り当てられる。これにより、直列化部１０７によって、ノード列毎の直列化処理が、各スレッドにおいて並列的に実行される。最終的に、スレッド毎に得られた直列化結果が結合部１０８によって結合され、結合された直列化結果が出力部１０９によって出力される。このように木構造データの直列化処理を複数スレッドで並列的に処理することにより、木構造データの直列化処理を高速化することができる。
【００５２】
また、分割部１０５によって各スレッドに割り当てられるノード列毎の重みを均等化するように木構造データを分割することで、各スレッドに割り当てられる処理量（ノード数）を均等化できる。これにより、特定のスレッドに処理負荷が偏ってしまうことを回避し、全スレッドの処理が完了するまでの時間を短縮することができる。
【００５３】
次に、直列化部１０７が重複部分木単位に辞書式圧縮及び連長圧縮を実行した上で直列化を実行する場合について説明する。
【００５４】
この場合、直列化部１０７は、直列化対象の各ノードを根ノードとする部分木について、例えば辞書テーブル生成部１０３によって生成された辞書テーブルを参照することで、当該部分木に対して辞書式圧縮を実行することができるか否かを判定する。また、直列化部１０７は、直列化対象の各ノードを根ノードとする部分木について、例えば当該部分木の構成を当該部分木と共通の親ノードを有し且つ当該部分木の直前に位置する部分木の構成と比較することによって、当該部分木に対して連長圧縮を実行することができるか否かを判定する。そして、直列化部１０７は、これらの圧縮処理を実行することが可能と判定した場合には、該当する部分木に対して当該圧縮処理を実行した上で直列化を実行する。
【００５５】
より具体的には、直列化部１０７は、ＴＬＶ形式への直列化において、辞書式圧縮により符号に置き換える対象となるデータ内容を示す辞書項目、辞書式圧縮対象の部分木に対応するデータ、及び連長圧縮対象の部分木に対応するデータに対して、特別な型を用いることにより圧縮処理を実現する。
【００５６】
また、本実施形態では、辞書式圧縮を用いた直列化の一例として、互いに等価な重複部分木の組において最初に出現する部分木に対応するデータ（図３の例では、ノード２又はノード８を根ノードとする部分木に対応するデータ）については、符号に置換せずに、辞書項目に対応する符号の符号長を示す符号長マーカを付与した上で辞書項目として直列化結果に含める方式を採用する。この方式では、復号側で符号長マーカと当該符号長マーカに続く辞書項目に対応するデータを抽出することで辞書テーブルを作成（復元）することができる。これにより、直列化結果を格納するデータのヘッダ部分等に辞書テーブルを含める必要がなくなり、その分直列化結果のデータサイズを縮小することができる（特願２０１２−１６２７００号参照）。
【００５７】
したがって、本実施形態では、辞書項目を示す型として符号長マーカ（「Ｍ」と表記）を用いる。また、辞書項目については、長さは省略し、当該重複部分木に含まれるノードをＴＬＶ形式で直列化したものを値とする。また、互いに等価な重複部分木の組において２回目以降に出現する重複部分木であって辞書式圧縮対象となる部分木に対応するデータについては、型として当該重複部分木に対応する符号を用い、長さと値は省略する。また、連長圧縮対象の部分木については、連長圧縮対象であることを示す「Ｒ」を型とし、直前の兄弟部分木の繰り返し回数を長さとし、値は省略する。
【００５８】
図７は、直列化部１０７が図３に示す木構造データを単一スレッドで辞書式圧縮及び連長圧縮を実行した上で直列化した場合における直列化結果を示す図である。図７に示すように、例えばノード２を根ノードとする部分木に対応する辞書項目については、型として「Ｍ」が用いられ、長さは省略され、当該部分木に含まれるノードを直列化したもの（Ｃ，２，Ｓ，４，ｈｏｇｅ，Ｃ，２，Ｓ，３，ｆｏｏ，Ｉ，１２３）が値となる。
【００５９】
また、辞書式圧縮対象となる部分木（ノード１８を根ノードとする部分木及びノード２３を根ノードとする部分木）に含まれる全てのノードが、それぞれ対応する符号「Ｔ１」及び「Ｔ２」に置き換えられる。また、連長圧縮対象となる部分木（ノード１１を根ノードとする部分木）に含まれる全てのノードが、「Ｒ，１」に置き換えられる。以上のように、直列化部１０７は、辞書式圧縮及び連長圧縮を実行した上で木構造データを直列化することにより、辞書式圧縮及び連長圧縮を実行せずに木構造データを直列化した場合（図４参照）と比較して、直列化結果のサイズを短くすることができる。
【００６０】
ここで、辞書式圧縮及び連長圧縮を実行した上で直列化を実行する場合の失敗例として、分割部１０５が図５に示す分割境界Ｄ１，Ｄ２を分割境界として木構造データを分割し、スレッド割当部１０６が各ノード列に対してそれぞれ１つのスレッドを割り当て、直列化部１０７が当該スレッド毎に並列して、辞書式圧縮及び連長圧縮を実行した上で直列化を実行する場合について説明する。この場合におけるスレッド毎の直列化結果を図８に示す。図８に示すように、分割境界Ｄ１，Ｄ２を分割境界として分割された各ノード列に対する各スレッド（スレッド１〜３）における直列化処理が適切に実行されておらず、データに矛盾が生じていることがわかる。具体的には以下の２つの問題点が発生している。
【００６１】
１つ目の問題点は、連長圧縮対象となるノード１１を根ノードとする部分木について連長圧縮されていない点である。これは、同一の根ノードを有し且つ連続して出現する互いに等価な重複部分木同士（ノード８を根ノードとする部分木及びノード１１を根ノードとする部分木）が、互いに別のスレッド（スレッド１及びスレッド２）に割り当てられたためである。すなわち、スレッド２は、ノード１１を根ノードとする部分木がスレッド１に割り当てられたノード８を根ノードとする部分木と同一の構成であることを認識することができないため、連長圧縮が適切に実行されていない。
【００６２】
２つ目の問題点は、辞書式圧縮対象となるノード１８を根ノードとする部分木に含まれるノード１８〜２２について、ノード１８，１９がスレッド２に割り当てられ、ノード２０〜２２がスレッド３に割り当てられたことによりデータの矛盾が生じている点である。これについて、以下詳細に説明する。
【００６３】
重複部分木検出部１０２によって、ノード１８を根ノードとする部分木がノード２を根ノードとする部分木に対応する重複部分木であることが検出されている。したがって、スレッド２は、当該検出結果及び辞書テーブル生成部１０３によって生成された辞書テーブルに基づいて、ノード１８を根ノードとする部分木に含まれるノード１８，１９を、ノード２を根ノードとする部分木に対応する符号Ｔ１に置換する辞書式圧縮を実行する。ここで、符号Ｔ１は、ノード２を根ノードとする部分木に対応する符号であり、ノード１８〜２２の全てのノードに対応するデータを示すものである。一方、スレッド３は、ノード２０〜２２について辞書式圧縮処理を実行せずにノード毎に直列化する。したがって、スレッド２の直列化結果及びスレッド３の直列化結果の両方にノード２０〜２２に対応するデータを示す部分が含まれ、元のデータとの矛盾が生じている。
【００６４】
なお、直列化部１０７がスレッド間を跨いだノードのチェック処理等を実行するようにすれば上記の問題点を解消できる可能性があるが、そのようにした場合にはスレッド毎に独立した並列処理によって全体の処理効率を高めるというメリットが損なわれてしまうという問題がある。
【００６５】
そこで、直列化部１０７が辞書式圧縮及び連長圧縮等の圧縮処理を実行した上で直列化を実行する場合において上述の２つの問題点を回避するために、データ直列化装置１は、以下の処理を実行する。すなわち、分割部１０５は、重複部分木に含まれるノードと直列化順序における当該ノードの直前のノードとを分割しないように、木構造データを分割する。ただし、辞書式圧縮対象の部分木の根ノードと直列化順序における当該根ノードの直前のノードとを分割しても上述のような問題点は生じないため、分割部１０５は、このように分割することについては許容してもよい。
【００６６】
図９に、分割部１０５が上述のように木構造データを分割する場合における分割境界の例（分割境界Ｄ３，Ｄ４）を示す。分割部１０５は、図９に示す分割境界Ｄ３，Ｄ４で木構造データを分割することにより、木構造データをノード１〜１３からなるノード列（以下「ノード列４」と表記）と、ノード１４〜２２からなるノード列（以下「ノード列５」と表記）と、ノード２３〜２８からなるノード列（以下「ノード列６」と表記）とに分割する。なお、分割部１０５が分割境界Ｄ３，Ｄ４を決定するための具体的な処理については、後述するデータ直列化装置１のフローを説明する際に併せて説明する。
【００６７】
図１０は、木構造データを図９に示す分割境界Ｄ３，Ｄ４で分割したスレッド毎に辞書式圧縮及び連長圧縮した上で直列化した場合における直列化結果を示す図である。図１０に示すように、ノード列４に割り当てられたスレッド１において、ノード１１を根ノードとする部分木について連長圧縮されている。また、ノード列５が割り当てられたスレッド２及びノード列６が割り当てられたスレッド３において、ノードの重複はなく、データに矛盾は生じていない。すなわち、上述した２つの問題点は発生していない。
【００６８】
以上のように、データ直列化装置１によれば、分割部１０５が重複部分木に含まれるノードと直列化順序における当該ノードの直前のノードとを分割しないように木構造データを分割することにより、上述した２つの問題を回避することができる。また、分割部１０５は、辞書式圧縮が実行される対象となる部分木の根ノードの直前位置での分割については許容することで、木構造データの分割位置をより柔軟に決定することができる。
【００６９】
ただし、図１０においては、スレッド間において直列化の処理対象とされたノードの数が均等化されていない。すなわち、スレッド１では、１１個のノードに対する直列化処理がされているのに対し、スレッド２及び３では、それぞれ５個及び４個のノードに対する直列化処理しかされておらず、各スレッドが処理するノード数について不均衡が生じている。スレッド毎の並列処理によって全体の処理をより高速に完了するには、全てのスレッドにほぼ均等な数のノードが割り当てられることがより好ましい。
【００７０】
本実施形態において、直列化部１０７による直列化処理において併せて重複部分木に対する辞書式圧縮及び連長圧縮が実行される場合には、互いに等価な重複部分木のうち直列化順序において２回目以降に出現する重複部分木が、当該重複部分木単位で所定の符号及び記号等に置き換えられる。すなわち、本実施形態では、互いに等価な重複部分木のうち直列化順序において２回目以降に出現する重複部分木が、圧縮処理が実行される対象となる重複部分木（以下「圧縮対象重複部分木」と表記する）に相当する。ここで、圧縮対象重複部分木に対する直列化処理は、実質的に当該圧縮対象重複部分木の根ノードに対してのみ行われることなるため、圧縮処理がされない場合と比較して、処理量が減少することが期待される。
【００７１】
そこで、重み決定部１０４は、圧縮対象重複部分木の重みを、圧縮処理が実行されない場合よりも小さい値に決定してもよい。重み決定部１０４は、例えば重複部分木検出部１０２の検出結果を参照することにより、圧縮対象重複部分木を特定することができる。
【００７２】
重み決定部１０４による圧縮対象重複部分木に対する重み決定方法の最も簡単な方法の一つは、重みを「１」に決定することである。図１１に、このようにして重み決定部１０４が決定した部分木毎の重みを示す。図１１に示すように、重み決定部１０４は、圧縮対象重複部分木の根ノード（ノード１１、ノード１８、ノード２３）の重みを「１」としている。また、重み決定部１０４は、圧縮対象重複部分木の根ノード以外のノードについては、重みの決定を省略している。これは、圧縮対象重複部分木の根ノード以外のノードについては実質的に直列化処理が実行されないため、処理量に相当する重みを関連付ける必要がないからである。
【００７３】
このような重み決定部１０４による重み決定方法によれば、木構造データの総重みは２０となる。分割部１０５は、例えば、辞書式圧縮対象の部分木の根ノードと直列化順序における当該根ノードの直前のノードとを分割することを許容しつつ、重複部分木に含まれるノードと直列化順序における当該ノードの直前のノードとを分割しないようにすると共に、ノード列毎の重みがノード列間で均等化されるように木構造データを分割する。すなわち、分割部１０５は、図１１に示す分割境界Ｄ５，Ｄ６で木構造データを分割することにより、各ノード列の重みが「７」、「７」、「６」と均等になるように木構造データを分割する。
【００７４】
図１２は、木構造データを図１１に示す分割境界Ｄ５，Ｄ６で分割したスレッド毎に辞書式圧縮及び連長圧縮した上で直列化した場合における直列化結果を示す図である。図１２に示すように、重み決定部１０４が上述のように決定した重みに基づいて分割部１０５が分割境界Ｄ５，Ｄ６で木構造データを分割することによって、スレッド間における直列化の処理対象とされたノードの数が、図１０に示す場合と比較して均等化されている。
【００７５】
以上のように、データ直列化装置１によれば、圧縮対象重複部分木に対して、処理量に応じたより適切な重み付けを決定することができる。そして、分割部１０５がこのような重み付けの結果を利用して、ノード列毎の重みがノード列間で均等化されるように木構造データを分割することができる。これにより、スレッド間の処理量を均等化し、全体の処理時間をより短縮することができる。
【００７６】
次に、結合部１０８が、スレッド毎の直列化結果を直列化順序で一つずつ入力して所定のデータ圧縮処理を実行した上で、スレッド毎の直列化結果を結合する場合を考える。より具体的には、結合部１０８が、直列化部１０７による各スレッドにおける直列化処理により得られた直列化結果について、前方部分の直列化結果から順次ＺＩＰ圧縮等のデータ圧縮処理を実行した上で、スレッド毎の直列化結果を結合する場合を考える。
【００７７】
例えば、部分バイト列を順番に入力し、入力したバイト列をＺＩＰ圧縮した上で結合した結果を出力する技術として、Ｊａｖａ（登録商標）言語におけるＧＺＩＰＯｕｔｐｕｔＳｔｒｅａｍオブジェクト等が存在する。結合部１０８は、例えば、ＧＺＩＰＯｕｔｐｕｔＳｔｒｅａｍオブジェクトにスレッド毎の直列化結果を一つずつ入力することにより、ＺＩＰ圧縮がされた上でスレッド毎の直列化結果が全て結合された一つの直列化結果を取得することができる。ここで、結合部１０８は、スレッド毎の直列化結果をいったん結合してからＧＺＩＰＯｕｔｐｕｔＳｔｒｅａｍオブジェクトに入力する必要がなく、スレッド毎の直列化結果をＧＺＩＰＯｕｔｐｕｔＳｔｒｅａｍオブジェクトに順次入力するだけでよい。
【００７８】
本実施形態では、結合部１０８が、上記のようなＧＺＩＰＯｕｔｐｕｔＳｔｒｅａｍオブジェクト等を用いて、スレッド毎の直列化結果をＺＩＰ圧縮した上で結合した一つの直列化結果を取得する場合について考える。
【００７９】
ＧＺＩＰＯｕｔｐｕｔＳｔｒｅａｍオブジェクトによるＺＩＰ圧縮処理は、先に入力されたバイト列から順次直列的に実行される。したがって、スレッド毎の処理負荷が均等化されていると、図１３（ａ）に示すように、スレッド１の直列化結果に対するＺＩＰ圧縮処理（所定のデータ圧縮処理）が完了する前に、スレッド２の直列化処理が完了してしまう場合が生じ得る。この場合、スレッド２の直列化結果に対するＺＩＰ圧縮処理を直ちに開始することができないため「１」の処理待ち時間が発生する。スレッド３についても同様に「２」の処理待ち時間が発生する。図１３（ａ）に示すように、スレッド間の処理負荷が均等化されてスレッド毎の直列化処理時間が「３」と等しくなる場合には、全スレッドの直列化結果に対するＺＩＰ圧縮処理が完了するまでに合計で「６」の処理時間がかかる。ここで、ＺＩＰ圧縮処理にかかる処理時間は「１」としている。
【００８０】
そこで、分割部１０５は、重み決定部１０４により決定された各部分木の重みに基づいて定まるノード列毎の重みが直列化順序の若いノード列（すなわち番号が若いスレッドに割り当てられるノード列）ほど小さくなるように、木構造データを分割してもよい。この場合、図１３（ｂ）に示すように、スレッド番号が若いスレッドほど、直列化処理の処理負荷が少なくなり、直列化処理が早く完了することとなる。これにより、直列化部１０７による直列化処理と結合部１０８によるＺＩＰ圧縮処理とが部分的に並列実行される。図１３（ｂ）に示すように、スレッド間の処理負荷に傾斜がつけられてスレッド１〜３の直列化処理時間がそれぞれ「２」、「３」、「４」となる場合には、全スレッドの直列化結果に対するＺＩＰ圧縮処理が完了するまでの処理時間を「５」に短縮することができる。
【００８１】
以上のように、分割部１０５が、スレッド間の処理負荷にあえて傾斜をつけるように木構造データを分割することにより、全体の処理において、直列化処理とＺＩＰ圧縮処理とを一部並列的に実行させることができ、全体の処理効率を向上させることができる。
【００８２】
次に、図１４及び図１５を用いて、データ直列化装置１の動作（本実施形態に係るデータ直列化方法を含む）について説明する。図１４は、データ直列化装置の動作を示すフロー図である。図１５は、分割部１０５が図９に示す分割境界Ｄ３，Ｄ４を決定する処理を含む分割処理を示すフロー図である。
【００８３】
まず、木構造構築部１０１によって木構造データが構築される（ステップＳ１０１）。続いて、重複部分木検出部１０２によって木構造データに含まれる重複部分木が検出され（ステップＳ１０２）、重複部分木検出部１０２により検出された重複部分木に対応するデータと符号とを対応付けた辞書テーブルが、辞書テーブル生成部１０３によって生成される（ステップＳ１０３）。
【００８４】
続いて、重み決定部１０４によって、各ノードを根ノードとする部分木毎に、当該部分木の大きさに基づく重みが決定される（ステップＳ１０４、重み決定ステップ）。直列化部１０７による直列化において辞書式圧縮及び連長圧縮が併せて実行される場合には、ステップＳ１０４において、重み決定部１０４は、これらの圧縮処理が実行される対象となる重複部分木の重みを、これらの圧縮処理が実行されない場合よりも小さくしてもよい。
【００８５】
続いて、重み決定部１０４により決定された各部分木の重みに基づいて、木構造データをそれぞれ直列化順序が連続する一以上のノードからなる複数のノード列に分割する分割処理が、分割部１０５によって実行される（ステップＳ１０５、分割ステップ）。
【００８６】
図１５を用いて、分割部１０５が図９に示す分割境界Ｄ３，Ｄ４を決定し、当該分割境界Ｄ３，Ｄ４で木構造データを分割する処理について説明する。
【００８７】
まず、分割部１０５は、分割境界の候補を仮決定する（ステップＳ２０１）。ここでは一例として、図５に示す分割境界Ｄ１，Ｄ２が分割境界の候補として仮決定されるものとする。続いて、分割部１０５は、未確定の分割境界の候補（分割境界Ｄ１，Ｄ２）のうち最も前方の候補（分割境界Ｄ１）を選択する（ステップＳ２０２）。続いて、分割部１０５は、確定済みの分割境界があるか否かを判定する（ステップＳ２０３）。ここでは、確定済みの分割境界はないため（ステップＳ２０３：ＮＯ）、分割部１０５は、ステップＳ２０２で選択した分割境界Ｄ１の直後のノード１１（候補ノード）の先祖系列を抽出する（ステップＳ２０６）。
【００８８】
先祖系列とは、木構造データの根ノードであるノード１から候補ノードであるノード１１までの接続関係を直列化順序の系列で表したものである。ただし、ノード１を根ノードとする木（木構造データそのもの）全体が辞書式圧縮及び連長圧縮等の対象となることはないため、先祖系列から除外する。したがって、例えば、ノード１１の先祖系列は、「ノード７、ノード１１」となり、ノード２０の先祖系列は、「ノード１７、ノード１８、ノード２０」となる。
【００８９】
続いて、分割部１０５は、候補ノードであるノード１１の先祖系列から自ノード（ノード１１）を除いた先祖（ノード７）のうちに、辞書式圧縮又は連長圧縮の対象となる部分木の根ノードがあるか否かを判定する（ステップＳ２０７）。ここで、ノード７は、重複部分木の根ノードではなく、いずれの圧縮対象ともならないため（ステップＳ２０７：ＮＯ）、分割部１０５は、候補ノードであるノード１１が連長圧縮対象となる部分木の根ノードであるか否かを判定する（ステップＳ２０８）。ここで、ノード１１を根ノードとする部分木は、ノード８を根ノードとする部分木との連長圧縮対象となるため（ステップＳ２０８：ＹＥＳ）、分割部１０５は、分割境界の候補（分割境界Ｄ１）を連長圧縮対象の部分木の直後、すなわちノード１３とノード１４とを分割する位置に移動する（ステップＳ２０９）。なお、分割部１０５は、例えば辞書テーブルの参照及び木構造データの巡回走査等により、ステップＳ２０７及びステップＳ２０８の判定を実行する。
【００９０】
続いて、分割部１０５は、移動させた後の分割境界（図９の分割境界Ｄ３）に基づいて定まる候補ノード（ノード１４）について、ステップＳ２０６〜ステップＳ２０８を実行する。ノード１４の先祖系列はノード１４のみであり（ステップＳ２０７：ＮＯ）、ノード１４は連長圧縮対象となる部分木の根ノードではないため（ステップＳ２０８：ＮＯ）、分割部１０５は、移動させた後の分割境界Ｄ３を分割境界として確定させる（ステップＳ２１０）。
【００９１】
続いて、未確定の分割境界の候補Ｄ２が残っているため（ステップＳ２１１：ＹＥＳ）、分割部１０５は、分割境界Ｄ２を選択する（ステップＳ２０２）。続いて、分割部１０５は、確定済みの分割境界があるか否かを判定する（ステップＳ２０３）。ここでは、確定済みの分割境界Ｄ３があるため（ステップＳ２０３：ＹＥＳ）、分割部１０５は、候補ノードであるノード２０が、直前の確定済み分割境界Ｄ３よりも後方にあるか否かを判定する（ステップＳ２０４）。ここで、ノード２０は分割境界Ｄ３よりも後方にあるため（ステップＳ２０４：ＹＥＳ）、分割部１０５は、候補ノードであるノード２０の先祖系列を抽出する（ステップＳ２０６）。
【００９２】
なお、ステップＳ２０４の判定において仮に候補ノードが直前の確定済み分割境界よりも後方にないと判定された場合（ステップＳ２０４：ＮＯ）には、分割部１０５は、分割境界の候補を直前の確定済み分割境界よりも後方の任意の位置に移動させた上で（ステップＳ２０５）、ステップＳ２０６の処理を実行する。
【００９３】
続いて、分割部１０５は、候補ノードであるノード２０の先祖系列から自ノード（ノード２０）を除いた先祖（ノード１７、ノード１８）のうちに、辞書式圧縮又は連長圧縮の対象となる部分木の根ノードがあるか否かを判定する（ステップＳ２０７）。ここで、ノード１８を根ノードとする部分木は、ノード２を根ノードとする部分木と重複する重複部分木であり、辞書式圧縮の対象となっている（ステップＳ２０７：ＹＥＳ）。したがって、分割部１０５は、分割境界の候補（分割境界Ｄ２）を辞書式圧縮対象の部分木の直後、すなわちノード２２とノード２３とを分割する位置に移動する（ステップＳ２０９）。
【００９４】
続いて、分割部１０５は、移動させた後の分割境界（図９の分割境界Ｄ４）に基づいて定まる候補ノード（ノード２３）について、ステップＳ２０６〜ステップＳ２０８を実行する。ノード２３の先祖系列は（ノード１７、ノード２３）であるが、いずれのノードも辞書式圧縮又は連長圧縮の対象となる部分木の根ノードではない（ステップＳ２０７：ＮＯ）。また、ノード２３を根ノードとする部分木は、ノード８を根ノードとする部分木と重複する重複部分木であり、辞書式圧縮の対象となるものの、連長圧縮対象となる部分木の根ノードではない（ステップＳ２０８：ＮＯ）。したがって、分割部１０５は、移動させた後の分割境界Ｄ４を分割境界として確定させる（ステップＳ２１０）。
【００９５】
以上の処理により、未確定の分割境界の候補がなくなったため（ステップＳ２１１：ＮＯ）、分割部１０５は、確定した分割境界Ｄ３，Ｄ４で木構造データを分割する（ステップＳ２１２）。
【００９６】
続いて、スレッド割当部１０６によって、分割部１０５により分割されて生成された複数のノード列のそれぞれに対して１つのスレッドが割り当てられる（ステップＳ１０６、スレッド割当ステップ）。
【００９７】
続いて、直列化部１０７によって、スレッド毎に並列して、ノード列に含まれる各ノードに対応するデータが直列化順序でバイト列に直列化される（ステップＳ１０７、直列化ステップ）。ステップＳ１０５において分割部１０５がステップＳ２０１〜Ｓ２１２に示される分割処理を実行して木構造データを分割している場合には、ステップＳ１０７において、直列化部１０７は、重複部分木単位に辞書式圧縮及び連長圧縮（所定の圧縮処理）を実行した上で直列化を実行することができる。
【００９８】
続いて、結合部１０８によって、直列化部１０７によって得られたスレッド毎の直列化結果が、直列化順序で結合される（ステップＳ１０８〜Ｓ１１０、結合ステップ）。例えばスレッドが３つ（処理対象のノード列の直列化順序が若い順にスレッド１、スレッド２、スレッド３）であり、スレッド毎の直列化結果が３つ得られた場合を考える。この場合、結合部１０８は、まず先頭の直列化結果（スレッド１の直列化結果）に対する未結合部分（スレッド２以降の直列化結果）のうち最も前方のスレッド２の直列化結果を選択し（ステップＳ１０８）、選択したスレッド２の直列化結果をスレッド１の直列化結果の後方に結合する（ステップＳ１０９）。続いて、結合部１０８は、未結合部分があるか否かを判定する（ステップＳ１１０）。ここで、未結合部分（スレッド３の直列化結果）が存在するため（ステップＳ１１０：ＹＥＳ）、結合部１０８は、既に結合済みの部分（スレッド１及び２の直列化結果を結合した部分）の後方に、スレッド３の直列化結果を結合する（ステップＳ１０８，Ｓ１０９）。これにより、全ての直列化結果が結合され、未結合部分がなくなるため（ステップＳ１１０：ＮＯ）、結合部１０８は、結合処理を完了する。
【００９９】
ステップＳ１０９において、結合部１０８は、結合対象の直列化結果を入力してＺＩＰ圧縮等の所定のデータ圧縮処理を実行した上で結合することができる。
【０１００】
最後に、出力部１０９によって、結合部１０８により結合された直列化結果が、直列化結果を利用する所定のサーバ装置（不図示）及び直列化結果を一定期間保存しておくためのストレージ（不図示）等に出力される（ステップＳ１１１、出力ステップ）。
【０１０１】
次に、図１６を用いて、コンピュータをデータ直列化装置１として機能させるためのデータ直列化プログラムＰ１について説明する。図１６は、データ直列化プログラムＰ１のモジュール構成を示すブロック図である。図１６に示すように、データ直列化プログラムＰ１は、重み決定モジュールＰ１１、分割モジュールＰ１２、スレッド割当モジュールＰ１３、直列化モジュールＰ１４、結合モジュールＰ１５、及び出力モジュールＰ１６を備える。上記重み決定モジュールＰ１１、分割モジュールＰ１２、スレッド割当モジュールＰ１３、直列化モジュールＰ１４、結合モジュールＰ１５、及び出力モジュールＰ１６が実行されることにより実現される機能は、上述したデータ直列化装置１において対応する重み決定部１０４、分割部１０５、スレッド割当部１０６、直列化部１０７、結合部１０８、及び出力部１０９の機能と同様である。
【０１０２】
このように構成されたデータ直列化プログラムＰ１は、図２に示す記録媒体１８に記憶され、データ直列化装置１として用いられるコンピュータにより実行される。当該コンピュータは、記録媒体１８が記録媒体読取部１７に挿入されると、記録媒体読取部１７から記録媒体１８に格納されたデータ直列化プログラムＰ１にアクセス可能となり、当該データ直列化プログラムＰ１を実行することによって、本実施形態に係るデータ直列化装置１として動作することが可能となる。
【０１０３】
データ直列化プログラムＰ１は、搬送波に重畳されたコンピュータデータ信号としてネットワークを介して提供されるものであってもよい。この場合、データ直列化装置１として用いられるコンピュータは、通信制御部１４によって受信したデータ直列化プログラムＰ１を主記憶部１２に格納することにより、当該データ直列化プログラムＰ１を実行することができる。
【０１０４】
以上、本実施形態に係るデータ直列化装置１について詳細に説明した。データ直列化装置１によれば、木構造データのバイナリ形式への直列化処理を複数スレッドで並列的に処理することにより、木構造データの直列化処理を高速化することができる。データ直列化装置１は、木構造データをバイナリ形式で直列化するあらゆる用途に用いることができる。例えば、ビッグデータを保存する用途では、保存するデータサイズを削減するために圧縮処理（辞書式圧縮、連長圧縮、ＺＩＰ圧縮等）を併用した直列化を適切かつ高速に実行することができる。また、データをネットワーク上で伝送する用途では、元データ（木構造データ）からバイト列に高速に直列化することにより、伝送するバイナリデータ（直列化結果）を高速に生成することができる。
【符号の説明】
【０１０５】
１…データ直列化装置、１０１…木構造構築部、１０２…重複部分木検出部、１０３…辞書テーブル生成部、１０４…重み決定部、１０５…分割部、１０６…スレッド割当部、１０７…直列化部、１０８…結合部、１０９…出力部、Ｄ１〜Ｄ６…分割境界、Ｐ１…データ直列化プログラム、Ｐ１１…重み決定モジュール、Ｐ１２…分割モジュール、Ｐ１３…スレッド割当モジュール、Ｐ１４…直列化モジュール、Ｐ１５…結合モジュ
ール、Ｐ１６…出力モジュール。
【図１】
2014206828.tif 000003
【図２】
2014206828.tif 000004
【図３】
2014206828.tif 000005
【図４】
2014206828.tif 000006
【図５】
2014206828.tif 000007
【図６】
2014206828.tif 000008
【図７】
2014206828.tif 000009
【図８】
2014206828.tif 000010
【図９】
2014206828.tif 000011
【図１０】
2014206828.tif 000012
【図１１】
2014206828.tif 000013
【図１２】
2014206828.tif 000014
【図１３】
2014206828.tif 000015
【図１４】
2014206828.tif 000016
【図１５】
2014206828.tif 000017
【図１６】
2014206828.tif 000018