(57)【要約】【課題】ツリー構造データをデータサイズを小さくして可読性のある文字列データに変換およびその逆変換ができる。【解決手段】データ変換部２によるツリー構造データ１から文字列データへの変換は、先頭にツリー要素名を配置し、その次にツリー属性名とツリー属性値を配置し、その次にツリー要素値識別子を配置し、その次にツリー要素値を配置し、最後にツリー要素セパレータを配置したデータ構造に変換する。  ツリー要素属性値が共通する場合、親子関係の要素がある場合、ツリー構造データが行列構造となる場合、ツリー構造が親と子と孫要素になる場合の変換方法も含む。文字列データからツリー構造データに復元する方法も含む。【選択図】  図１
2005148970.tif 000002
【特許請求の範囲】
【請求項１】
ツリー構造を持つツリー構造データを、ツリー構造の階層を表しかつ可読性のある文字列データに変換、およびその逆変換をするデータ変換方法であって、
前記文字列データは、先頭にツリー要素名を配置し、その次にツリー属性名とツリー属性値を配置し、その次にツリー要素値識別子を配置し、その次にツリー要素値を配置し、最後にツリー要素セパレータを配置したデータ構造に変換することを特徴とするデータ変換方法。
【請求項２】
前記ツリー要素値は、ツリー要素属性が無い場合や有る場合でもそのツリー要素属性値が共通する場合は、ツリー要素名を一つ表示し、その後ろにツリー要素値識別子を用いてツリー要素値を連結配置したデータ構造に変換することを特徴とする請求項１に記載のデータ変換方法。
【請求項３】
前記ツリー構造データが、あるツリー要素Ａについてそのツリー要素の子階層に属するツリー要素Ｂがある場合、前記文字列データは「Ａ，Ｂ」という順で配置し、子階層のツリー要素がない場合はツリー要素Ａの後ろにそれを示す識別子を配置したデータ構造に変換することを特徴とする請求項１に記載のデータ変換方法。
【請求項４】
前記ツリー構造データは、階層を示す行ｍと、一つの階層におけるツリー要素を表す列ｎとした、ｍ＊ｎの行列として配置した構造とし、
このツリー構造データを使用して前記文字列データに変換することを特徴とする請求項１に記載のデータ変換方法。
【請求項５】
前記文字列データは、初めにツリー階層先頭識別子を配置し、その次には親ツリー要素を配置し、それ以降はその親ツリー要素の子ツリー要素を配置し、子ツリー要素の終わりにツリー階層最後尾識別子を配置したデータ構造とし、各ツリー要素とその子要素にあたる全てのツリー要素の先頭と最後尾に識別子を配置したデータ構造に変換することを特徴とする請求項１に記載のデータ変換方法。
【請求項６】
前記ツリー構造データが、前記子ツリー要素の子ツリー要素になる孫ツリー要素がある場合、前記文字列データは、子ツリー要素の前に再度ツリー階層先頭識別子を配置し、その後ろに子ツリー要素を配置し、その後ろに孫ツリー要素を配置し、孫ツリー要素の最後にツリー階層最後尾識別子を配置したことを特徴とする請求項１に記載のデータ変換方法。
【請求項７】
請求項３のデータ変換方法により変換された前記文字列データからツリー構造データへの復元は、
文字列データから先頭の要素を取得し、それをルートツリー要素としてスタックエリアに入れて保存する第１の処理と、
前記ツリー文字列データ中の次の要素を取得してその種別をチェックする第２の処理と、
前記要素の種別がツリー要素である場合、取得した要素を子ツリー要素とし、スタックエリアから最後に入れた要素を一つ取り出し、それを親ツリー要素とする第３の処理と、
前記親ツリー要素に子ツリー要素を加えてスタックエリアに入れて保存する第４の処理と、
前記子ツリー要素をスタックエリアに入れて保存し、前記第２の処理に戻って次の要素を取得する第５の処理と、
前記第２の処理で、要素の種別が階層識別子である場合、スタックエリアから最後に入れた要素を取り出し、前記第２の処理に戻る第６の処理と、
を文字列データの要素がなくなるまで繰り返すことを特徴とする請求項３に記載のデータ変換方法。
【請求項８】
請求項４のデータ変換方法により変換された文字列データからツリー構造データへの復元は、
ツリー文字列データからｍ行ｎ列のマトリックスデータを作成する第１の処理と、
前記マトリックスデータの１行１列目の要素をツリー構造データのルート要素として決定する第２の処理と、
前記列ｎおよび行ｍを順次インクリメントしながら、ｍ行目ｎ列目のデータをｎ−１列目のうちｍ行より小さくかつその値が最大となるような要素の子ツリー要素として追加する第３の処理と、
を前記マトリックスデータの要素がなくなるまで繰り返すことを特徴とする請求項４に記載のデータ変換方法。
【請求項９】
請求項５または６のデータ変換方法により変換された文字列データからツリー構造データへの復元は、
ツリー文字列データ全体の先頭のツリー要素を親ツリー要素（ｃａｒ要素）とし、その他の要素を子ツリー要素（ｃｄｒ要素）とする第１の処理と、
前記子ツリー要素がある限り、その先頭から順に一つずつ子ツリー要素を取り出す第２の処理と、
前記取り出した子ツリー要素が前記ｃａｒ要素とｃｄｒ要素から成り立っているか否かをチェックする第３の処理と、
前記子ツリー要素が前記ｃａｒ要素とｃｄｒ要素から成り立っていれば、親ツリー要素に子ツリー要素中のｃａｒ要素を追加する第４の処理と、
前記子ツリー要素中の前記ｃａｒ要素を親ツリー要素とし、子ツリー要素中の前記ｃｄｒ要素を子ツリー要素とする第５の処理と、
前記第５の処理で区分した親ツリー要素と子ツリー要素を復元した要素として決定し、前記第２の処理に戻って次の要素についての繰り返し処理に入る第６の処理と、
前記第３の処理において、子ツリー要素が前記ｃａｒ要素とｃｄｒ要素から成り立っていない場合、親ツリー要素に子ツリー要素を追加し、前記第２の処理に戻る第７の処理と、
を文字列データの要素がなくなるまで繰り返すことを特徴とする請求項５または６に記載のデータ変換方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本提案は、ツリー構造を持つデータ（以下、ツリー構造データと呼ぶ）を可読性の文字列データに変換、およびその逆変換をするデータ変換方法に関するものである。
【背景技術】
【０００２】
近年、データ形式としてＸＭＬ（Extensible Markup Language）が用いられることが多くなってきた。ＸＭＬは文書フォーマット規定の国際標準であるＳＧＭＬをインターネットでの配信に適したものにしたドキュメント記述言語であり、データをツリー構造で表現することができる。ツリー構造で表現するとデータの意味付けを行いやすく、データの作成、編集、検索が行いやすいという長所がある。また、ＸＭＬはテキストで表されるので可読性がある（例えば、非特許文献１参照）。
【０００３】
ツリー構造データを図で表現した例を図９に、それをＸＭＬで記述した例を図１０に示す。
【非特許文献１】技術評論社出版、「改訂版  標準ＸＭＬ完全解説（上）、中山幹敏、奥井康弘  著」、初版２００１年４月発行
【発明の開示】
【発明が解決しようとする課題】
【０００４】
データベース等に構築されるツリー構造データをＸＭＬによる方法で文字列データとして記述した場合、そのデータサイズが大きくなるという問題点が有る。データサイズが大きいとデータの送受信に時間がかかる、データの保存コストが大きいなどの影響がある。
【０００５】
本発明の目的は、ツリー構造データをデータサイズを小さくして可読性文字列データに変換およびその逆変換ができるデータ変換方法を提供することにある。
【課題を解決するための手段】
【０００６】
本発明は、前記の課題を解決するため、以下の方法を特徴とする。
【０００７】
（１）ツリー構造を持つツリー構造データを、ツリー構造の階層を表しかつ可読性のある文字列データに変換、およびその逆変換をするデータ変換方法であって、
前記文字列データは、先頭にツリー要素名を配置し、その次にツリー属性名とツリー属性値を配置し、その次にツリー要素値識別子を配置し、その次にツリー要素値を配置し、最後にツリー要素セパレータを配置したデータ構造に変換することを特徴とする。
【０００８】
（２）前記ツリー要素値は、ツリー要素属性が無い場合や有る場合でもそのツリー要素属性値が共通する場合は、ツリー要素名を一つ表示し、その後ろにツリー要素値識別子を用いてツリー要素値を連結配置したデータ構造に変換することを特徴とする。
【０００９】
（３）前記ツリー構造データが、あるツリー要素Ａについてそのツリー要素の子階層に属するツリー要素Ｂがある場合、前記文字列データは「Ａ，Ｂ」という順で配置し、子階層のツリー要素がない場合はツリー要素Ａの後ろにそれを示す識別子を配置したデータ構造に変換することを特徴とする。
【００１０】
（４）前記ツリー構造データは、階層を示す行ｍと、一つの階層におけるツリー要素を表す列ｎとした、ｍ＊ｎの行列として配置した構造とし、
このツリー構造データを使用して前記文字列データに変換することを特徴とする。
【００１１】
（５）前記文字列データは、初めにツリー階層先頭識別子を配置し、その次には親ツリー要素を配置し、それ以降はその親ツリー要素の子ツリー要素を配置し、子ツリー要素の終わりにツリー階層最後尾識別子を配置したデータ構造とし、各ツリー要素とその子要素にあたる全てのツリー要素の先頭と最後尾に識別子を配置したデータ構造に変換することを特徴とする。
【００１２】
（６）前記ツリー構造データが、前記子ツリー要素の子ツリー要素になる孫ツリー要素がある場合、前記文字列データは、子ツリー要素の前に再度ツリー階層先頭識別子を配置し、その後ろに子ツリー要素を配置し、その後ろに孫ツリー要素を配置し、孫ツリー要素の最後にツリー階層最後尾識別子を配置したことを特徴とする。
【００１３】
（７）前記（３）により変換された前記文字列データからツリー構造データへの復元は、
文字列データから先頭の要素を取得し、それをルートツリー要素としてスタックエリアに入れて保存する第１の処理と、
前記ツリー文字列データ中の次の要素を取得してその種別をチェックする第２の処理と、
前記要素の種別がツリー要素である場合、取得した要素を子ツリー要素とし、スタックエリアから最後に入れた要素を一つ取り出し、それを親ツリー要素とする第３の処理と、
前記親ツリー要素に子ツリー要素を加えてスタックエリアに入れて保存する第４の処理と、
前記子ツリー要素をスタックエリアに入れて保存し、前記第２の処理に戻って次の要素を取得する第５の処理と、
前記第２の処理で、要素の種別が階層識別子である場合、スタックエリアから最後に入れた要素を取り出し、前記第２の処理に戻る第６の処理と、
を文字列データの要素がなくなるまで繰り返すことを特徴とする。
【００１４】
（８）前記（４）により変換された前記文字列データからツリー構造データへの復元は、
ツリー文字列データからｍ行ｎ列のマトリックスデータを作成する第１の処理と、
前記マトリックスデータの１行１列目の要素をツリー構造データのルート要素として決定する第２の処理と、
前記列ｎおよび行ｍを順次インクリメントしながら、ｍ行目ｎ列目のデータをｎ−１列目のうちｍ行より小さくかつその値が最大となるような要素の子ツリー要素として追加する第３の処理と、
を前記マトリックスデータの要素がなくなるまで繰り返すことを特徴とする。
【００１５】
（９）前記（５）または（６）により変換された文字列データからツリー構造データへの復元は、
ツリー文字列データ全体の先頭のツリー要素を親ツリー要素（ｃａｒ要素）とし、その他の要素を子ツリー要素（ｃｄｒ要素）とする第１の処理と、
前記子ツリー要素がある限り、その先頭から順に一つずつ子ツリー要素を取り出す第２の処理と、
前記取り出した子ツリー要素が前記ｃａｒ要素とｃｄｒ要素から成り立っているか否かをチェックする第３の処理と、
前記子ツリー要素が前記ｃａｒ要素とｃｄｒ要素から成り立っていれば、親ツリー要素に子ツリー要素中のｃａｒ要素を追加する第４の処理と、
前記子ツリー要素中の前記ｃａｒ要素を親ツリー要素とし、子ツリー要素中の前記ｃｄｒ要素を子ツリー要素とする第５の処理と、
前記第５の処理で区分した親ツリー要素と子ツリー要素を復元した要素として決定し、前記第２の処理に戻って次の要素についての繰り返し処理に入る第６の処理と、
前記第３の処理において、子ツリー要素が前記ｃａｒ要素とｃｄｒ要素から成り立っていない場合、親ツリー要素に子ツリー要素を追加し、前記第２の処理に戻る第７の処理と、
を文字列データの要素がなくなるまで繰り返すことを特徴とする。
【発明の効果】
【００１６】
以上のとおり、本発明によれば、ツリー構造データをデータサイズを小さくして可読性文字列データに変換およびその逆変換ができる効果がある。具体的には、以下の効果がある。
【００１７】
（１）請求項１の方法を用いることで、ツリー要素値を表現するツリー文字列データのサイズをＸＭＬより小さくすることができる。
【００１８】
（２）請求項２の方法を用いることで、属性値が同じツリー要素が連続する場合は実施形態１よりもさらに小さいデータサイズとすることができる。
【００１９】
（３）ツリー要素中に子供のツリー要素がある場合は、ツリー文字列データ中にツリー階層を表現する必要がある。この場合には請求項３の方法を用いることで、閉じタグを省略でき、ツリー文字列データのサイズを小さくすることができる。
【００２０】
（４）請求項４の方法を用いることで、ツリー構造データの構造によっては請求項３の方法よりもさらにツリー文字列データのサイズを小さくできる場合がある。
【００２１】
（５）請求項５または６の方法を用いることで、ツリー構造データの構造によっては請求項３の方法よりもさらにツリー文字列データのサイズを小さくできる場合がある。
【００２２】
（６）請求項７または８の方法を用いることで、文字列データからツリー構造データを復元できる。
【発明を実施するための最良の形態】
【００２３】
上記の問題点を解決するため、ツリー構造データを文字列データ（以下、ツリー文字列データと呼ぶ）に変換する方法およびその逆変換方法の実施形態を以下に説明する。
【００２４】
初めに本実施形態で使用する語句を次のように定義する。
【００２５】
「ツリー構造データ」：ツリー構造を持つデータ。例えば図９のデータ。
【００２６】
「ツリー要素」：ツリー構造データを構成するツリーの要素。例えば図９における網掛け部分。
【００２７】
「ツリー要素名」：ツリー要素の名前。例えば図９の“経理部”など。
【００２８】
「ツリー要素属性」：ツリー要素の属性。例えば図９の“郵便番号”など。
【００２９】
「ツリー要素属性値」：ツリー要素属性の値。例えば図９の”２７１−００６７”など。
【００３０】
「ツリー要素値」：ツリー要素の値。例えば図９の”福沢諭吉”など。
【００３１】
「ツリー文字列データ」：ツリー構造データを文字列に変換したデータ。
【００３２】
「ツリー要素セパレータ」：ツリー文字列データ中でツリー要素を区分する特定の文字。
【００３３】
本発明は、ツリー構造データがもつ階層を記述でき、しかもデータサイズを小さくしたツリー文字列データに変換するため、ツリー要素値やツリー属性値のデータ構造、およびツリー要素の親子関係のデータ構造を提供する。前者のデータ構造による変換方法を実施形態１と２で示し、後者のデータ構造による変換方法を実施形態３〜５で示す。
【００３４】
（実施形態１）ツリー要素値、ツリー要素属性、ツリー要素属性値のデータ構造と変換方法
ＸＭＬではツリー要素の初めと終わりにそれぞれタグを用いてその間にツリー要素値を記述するが、終わりにもタグを用いるため、その分データサイズが大きくなる。そこで、本実施形態は、ツリー構造データがもつ階層を記述したツリー要素値を表すデータ構造として、ツリー要素の終わりにはタグを用いない構造を提案する。
【００３５】
図１は、本実施形態により変換したツリー構造データとツリー文字列データ構造の例を示す。ツリー構造データ１を構成してデータベース等に格納される各ツリー要素は、ツリー要素名、ツリー要素属性、ツリー要素属性値、ツリー要素値などのデータをもつ。
【００３６】
データ変換部２は、ツリー構造データ１から目的とするツリー要素をツリー文字列データに変換して出力する。なお、データ変換部２は、ツリー文字列データをツリー構造データに逆変換する機能も持つ。
【００３７】
このデータ変換部２で変換したツリー文字列データ３は、初めにツリー要素名を配置する。その次にツリー属性名とツリー属性値をＸＭＬと同様な記述方法で配置する。その次にツリー要素値識別子を配置する。これは、この識別子の次にツリー要素値を配置するという目印になるもので専用文字を用いる。そしてその次にツリー要素値を配置する。最後にツリー要素セパレータを配置し、ツリー要素の終わりを示す。これらを模式的に表すと下記のようになる。
【００３８】
ツリー文字列データの構造＝「ツリー要素名＋ツリー要素属性名とツリー要素属性値＋ツリー要素値識別子＋ツリー要素値＋ツリー要素セパレータ」
例えば、図９に示すツリー構造データに対して、図１０に示すＸＭＬの例は下記のようになる。
【００３９】
［１］ＸＭＬによるツリー文字列データの例
＜部員番号＝”１”＞福沢諭吉＜／部員＞
＜部員番号＝”２”＞新渡戸稲造＜／部員＞
＜部員番号＝”３”＞夏目漱石＜／部員＞
これを本実施形態では下記のようなデータ構造に変換する。ここでは、ツリー要素値識別子に記号「％」を用い、ツリー要素セパレータに記号「，」を用いた場合である。
【００４０】
［２］本実施形態によるツリー文字列データの例
部員番号＝”１”％福沢諭吉，
部員番号＝”２”％新渡戸稲造，
部員番号＝”３”％夏目漱石，
上記のように本実施形態では、タグの終わりを示す部分にタグ名を用いない。そのため、ツリー文字列データのデータサイズが小さくなる。例えば、上記の［１］ＸＭＬによるツリー文字列データの例では９０バイトであったものが、上記の［２］本実施形態の例では７１バイトになっており、データサイズを約２１％縮小することができる。
【００４１】
（実施形態２）リレー要素値の統合方法
本実施形態は、ツリー構造データがもつ階層を記述したツリー要素値を表すデータ構造として、ツリー要素属性が無い場合や有る場合でもそのツリー要素属性値が共通する場合は、ツリー要素名を一つ配置し、その後ろにツリー要素値識別子を用いてツリー要素値を連結配置した構造とする。
【００４２】
実施形態１と同様に、初めにツリー要素名を配置する。その次にツリー属性名とツリー属性値をＸＭＬと同様な記述方法で配置する。その次にツリー要素値識別子を配置する。これは、この識別子の次にツリー要素値を配置するという目印になるもので専用文字を用いる。そしてその次にツリー要素値を配置する。ここでツリー要素名、ツリー要素属性名、ツリー要素属性値が同一のツリー要素値がある場合には、その後ろにツリー要素値識別子を加え、その後ろにツリー要素値を配置する。この組み合わせを繰り返す。これらを模式的に表すと下記のようになる。
【００４３】
ツリー文字列データの構造＝「ツリー要素名＋ツリー要素属性とツリー要素属性値＋ツリー要素値識別子＋ツリー要素値＋ツリー要素値識別子＋ツリー要素値＋ツリー要素値識別子＋ツリー要素値＋……＋ツリー要素セパレータ」
例えばツリー要素名が「部員入社年」のＸＭＬの例は下記のようになる。
【００４４】
［３］ＸＭＬによるツリー文字列データの例
＜部員入社年＝”２００３”＞福沢諭吉＜／部員＞
＜部員入社年＝”２００３”＞新渡戸稲造＜／部員＞
＜部員入社年＝”２００３”＞夏目漱石＜／部員＞
これを本実施形態では下記のようなデータ構造に変換する。ここでは、ツリー要素値識別子に％を用い、ツリー要素セパレータに記号「，」を用いた。
【００４５】
［４］本実施形態によるツリー文字列データの例
部員入社年＝”２００３”％福沢諭吉％新渡戸稲造％夏目漱石，
上記のように本実施形態では、ツリー要素名が複数ある場合でもそれを一つで記述できる。そのため、ツリー文字列データのデータサイズが小さくなる。例えば、上記のＸＭＬの例になる［３］では１０７バイトあったものが、本実施形態の例になる［４］の例８では４８バイトになっており、データサイズを約５５％縮小することができる。
【００４６】
（実施形態３）深さ優先方法
ツリー構造データでは各ツリー要素に親子関係（ツリー階層）が存在する。ＸＭＬではツリー要素の始まりと終わりにタグを用いてその間に子タグを書くことでツリー階層を表現している（図１０参照）。本実施形態は、ツリー階層を表すのにツリー要素の終わりのタグを不要にした方法を提案する。
【００４７】
（１）ツリー階層関係のデータ変換方法
本実施形態では、ツリー構造データの階層を表すデータ構造として、あるツリー要素（ここではＡと呼ぶ）についてそのツリー要素の子階層に属するツリー要素（ここではＢと呼ぶ）がある場合には、ツリー文字列データ中において「Ａ，Ｂ」という順で配置した構造とする。子階層のツリー要素がない場合はそれを示す識別子を配置した構造とする。なお、ツリー要素値、ツリー要素属性、ツリー要素属性値については、実施形態１と２で示した方法で配置する。
【００４８】
図１のデータ変換部２によるデータ変換手順を以下に示す。
【００４９】
（Ｓ１）初めにルートツリー要素を取得する。
【００５０】
（Ｓ２）データ変換が指定されたツリー要素をツリー文字列データに追加する。
【００５１】
（Ｓ３）データ変換が指定されたツリー要素に対して子ツリー要素がなければ、固有の識別子をツリー文字列データに追加する。この識別子をツリー階層識別子と呼ぶ。
【００５２】
（Ｓ４）子ツリー要素があれば、それを指定して処理（Ｓ２）、（Ｓ３）を再帰的に繰り返す。子ツリー要素が複数ある場合には、一つずつ（Ｓ２）、（Ｓ３）を再帰的に繰り返す。
【００５３】
（Ｓ５）全ての子ツリー要素についての処理が終われば、ツリー階層識別子をツリー文字列データに追加する。
【００５４】
例えば、図２の（ａ）に示すように、あるツリー要素Ａの１つ下の階層にツリー要素Ｂとツリー要素Ｃがある場合には、ツリー階層識別子に記号「＠」を用い、ツリー要素セパレータには記号「，」を用いると、図２の（ｂ）に示すようになる。
【００５５】
同様に図９のデータ変換結果は下記のような記述になる。
【００５６】
［５］本実施形態によるツリー階層をもつツリー要素のデータ変換例
会社組織，東京本社，経理部住所＝”７階”郵便番号＝”２７１−００６７”，部員番号＝”１”％福沢諭吉，＠，部員番号＝”１”％新渡戸稲造，＠，部員番号＝”１”％夏目漱石，＠，＠，＠，沼津工場，技術部，＠，試験部，＠，＠，関西支社，営業部，＠，＠，＠，
（２）ツリー文字列データからツリー構造データへの復元方法
データ変換部２は、ツリー文字列データからツリー構造データへの復元機能を設け、この処理は図３に示し、以下の手順で実現される。
【００５７】
まず、ツリー文字列データから先頭の要素を取得し、それをルートツリー要素とする。その要素をスタックエリアに入れて保存する（Ｓ１１）。次に、ツリー文字列データ中の次の要素を取得し（Ｓ１２）、その要素の種別をチェックする（Ｓ１３）。当該要素がツリー要素である場合、取得した要素を子ツリー要素とし、スタックエリアから最後に入れた要素を一つ取り出し、それを親ツリー要素とする（Ｓ１４）。当該、親ツリー要素に子ツリー要素を加え（Ｓ１５）、当該親ツリー要素をスタックエリアに入れて保存し（Ｓ１６）、子ツリー要素をスタックエリアに入れて保存し、処理Ｓ２に戻って次の要素を取得する（Ｓ１７）。
【００５８】
取得した要素の種別が階層識別子である場合、スタックエリアから最後に入れた要素を取り出し、処理Ｓ１２に戻って次の要素を取得する（Ｓ１８）。
【００５９】
以上の処理（Ｓ１２）〜（Ｓ１８）を要素がなくなるまで繰り返し、要素がなくなったときに処理を終了する。
【００６０】
（３）本実施形態の特徴
本実施形態では、ツリー文字列データ中に各要素を１回配置するため、ツリー要素数が増加した場合のツリー文字列データサイズの増加の度合いはＸＭＬに比べて低くすることができる。また、実施形態１や２と併用することでツリー要素に要素値や属性値を持たせることが可能なのでＸＭＬと同様なツリー構造データへの逆変換ができる。
【００６１】
（４）本実施形態におけるデータ量
本実施形態では、深さ優先方法でのデータ量は下記のようになる。
【００６２】
データ量＝各要素サイズの合計＋ツリー階層識別子サイズ＊ツリー階層識別子数＋ツリー要素セパレータサイズ＊ツリー要素セパレータ数
上記のツリー文字列データのデータ量ｄは、全要素数をｘ、要素サイズをｅ、ツリー階層識別子サイズを１、ツリー要素セパレータサイズを１とすると、下記の式から求めることができる。
【００６３】
ｄ＝（ｅ＋３）ｘ−１
なぜならば
ｄ＝要素サイズ＊全要素数＋ツリー階層識別子サイズ＊ツリー階層識別子数＋ツリー要素セパレータサイズ＊ツリー要素セパレータ数
であり、この式において、要素サイズ＝ｅ、ツリー階層識別子サイズ＝１，ツリー階層識別子数＝全要素数＝ｘ、ツリー要素セパレータサイズ＝１、ツリー要素セパレータ数＝全要素数＋ツリー階層識別子数−１＝２ｘ−１となり、よって、
ｄ＝ｅｘ＋ｘ＋２ｘ−１＝（ｅ＋３）ｘ−１
になる。
【００６４】
（実施形態４）マトリックス
（１）ツリー階層関係のデータ変換方法
本実施形態では、ツリー構造データの階層を表すデータ構造として、ツリー構造データをｍ＊ｎの行列として配置した構造とする。列は階層を示し、行は一つの階層におけるツリー要素を割り当てるか、または、行と列が逆になってもよい。行数と列数は行列の先頭に位置させる。また、ツリー要素の区分にはツリー要素セパレータを用いる。なお、ツリー要素値、ツリー要素属性、ツリー要素属性値については、実施形態１と２で示した方法で配置する。
【００６５】
例えば、あるツリー要素Ａの１つ下の階層にツリー要素Ｂとツリー要素Ｃがある場合には、行数２階数２の行列として記述し、模式的に示すと図４の（ａ）に示すようになる。
【００６６】
これをツリー文字列データで記述するとツリー要素セパレータに記号「，」を用いて以下のようになる。
【００６７】
［６］本実施形態によるツリー文字列データの例。
【００６８】
２，２，Ａ，Ｂ，，Ｃ
同様にして図９のデータは図４の（ｂ）に示すようになる。図中の数字は便宜上、行番号と列番号を示すもので、実際のデータには含まれない。これを文字列で示すと、下記のようになる。
【００６９】
［７］本実施形態によるツリー文字列データの例。
【００７０】
６，４，会社組織，東京本社，経理部住所＝”７階”郵便番号＝”２７１−００６７”，部員番号＝”１”％福沢諭吉，，，，部員番号＝”２”％新渡戸稲造，，，，部員番号＝”３”％夏目漱石，，沼津工場，技術部，，，，試験部，，，関西支社，営業部，
（２）ツリー文字列データからツリー構造データへの復元方法
データ変換部２は、ツリー文字列データからツリー構造データへの復元機能を設け、この処理は図５に示し、以下の手順で実現される。
【００７１】
（Ｓ２１）ツリー文字列データから図４の（ｂ）のようなｍ行ｎ列のマトリックスデータを作成する。
【００７２】
（Ｓ２２）マトリックスデータの１行１列目の要素をツリー構造データのルート要素として決定する。
【００７３】
（Ｓ２３）ｍ＝１，ｎ＝２の初期設定をする。
【００７４】
（Ｓ２４）マトリックスデータのｍ行ｎ列目の要素を取得し、それをｍ行（ｎ−１）列目の子ツリー要素として追加する。
【００７５】
（Ｓ２５）ｎをインクリメント（＋１）する。
【００７６】
（Ｓ２６）ｎが最大値ｍａｘを越えたか否かチェックし、越えていなければＳ２４に戻って次のｍ行ｎ列目の要素を追加する。
【００７７】
（Ｓ２７）ｎが最大値ｍａｘを越えていれば、ｍをインクリメントし、ｎ＝２に戻し、次のｍ行の２列目の要素を追加対象として設定する。
【００７８】
（Ｓ２８）ｍのインクリメント結果が最大行ｍａｘを越えたか否かをチェックし、越えていなければＳ２４に戻って次のｍ行ｎ列目の要素を追加する。
【００７９】
上記のように、ツリー文字列データからツリー構造データへの復元には、ツリー文字列データからｍ行ｎ列のマトリックスデータを作成し、マトリックスデータの１行１列目の要素をツリー構造データのルート要素として決定する。その後は、列ｎおよび行ｍを順次インクリメントしながら、ｍ行目ｎ列目のデータをｎ−１列目のうちｍ行より小さくかつその値が最大となるような要素の子ツリー要素として追加する処理を、マトリックスデータの要素がなくなるまで繰り返すことで実現される。
【００８０】
（３）本実施形態の特徴
マトリックス方法では実施形態３に示すツリー階層識別子の指定は不要であり、その分ツリー文字列データのデータ量が少なくなる。マトリックス方法を用いれば、ツリー構造データの構造によっては、ツリー文字列データのデータ量が深さ優先方法よりも少なくなる場合がある。実施形態１や２と併用することでツリー要素に要素値や属性値を持たせることが可能なのでＸＭＬと同様なツリー構造データを記述することができる。欠点としては、データサイズがデータ構造により大きく変化することがある。
【００８１】
（４）データ量
マトリックス方法でのデータ量は以下のようになる（行数と列数を除く）。
【００８２】
データ量＝各要素サイズの合計＋ツリー要素セパレータサイズ＊ツリー要素セパレータ数
データ量ｄは、全要素数をｘ、要素サイズをｅ、ツリー要素セパレータサイズを１とすると次式のように表現できる。
【００８３】
ｄ＝（１／４）＊ｘ＾２＋（ｅ＋１／２）＊ｘ−（３／４）（最大時）
ｄ＝（ｅ＋１）ｘ−１（最小時）
（注）最小時とは、マトリックス中に空白要素が無い場合である。最大時とは、ｍ＊ｎの行列で１行とｎ列のみに要素があり、他は空白要素の場合である。
【００８４】
なぜならば、
ｄ＝要素サイズ＊全要素数＋ツリー要素セパレータサイズ＊ツリー要素セパレータ数
ここで最小時には、
ツリー要素セパレータ数＝全要素数一１となり
ｄ＝ｅ＊ｘ＋ｘ−１＝（ｅ＋１）ｘ−１
最大時には、
ツリー要素セパレータ数＝（（全要素数＋１）／２）＾２−１
となり、以下のようになる。
【００８５】
ｄ＝ｅ＊ｘ＋（（ｘ＋１）／２）＾２−１＝（１／４）＊ｘ＾２＋（ｅ＋１／２）＊ｘ−（３／４）
（実施形態５）リスト
（１）ツリー階層関係のデータ変換方法
本実施形態では、ツリー構造データの階層を表すデータ構造として、あるツリー要素とその子要素にあたる全てのツリー要素の先頭と最後尾を識別子で区切って配置した構造とする。ここでは、先頭の識別子をツリー階層先頭識別子と呼び、最後尾の識別子をツリー階層最後尾識別子と呼び、合わせてツリー階層識別子と呼ぶ。
【００８６】
初めにツリー階層先頭識別子を配置し、その次には親ツリー要素を配置し、それ以降はその親ツリー要素の子ツリー要素を配置し、子ツリー要素の終わりにツリー階層最後尾識別子を配置する。ツリー要素やツリー階層識別子の区分にはツリー要素セパレータを用いる。
【００８７】
子ツリー要素にさらに子ツリー要素（孫ツリー要素と呼ぶ）がある場合には、その子ツリー要素の前に再度ツリー階層先頭識別子を配置し、その後ろに子ツリー要素を配置し、その後ろに孫ツリー要素を配置し、孫ツリー要素の最後にツリー階層最後尾識別子を配置する。ツリー要素とツリー階層識別子の区分にもツリー要素セパレータを用いる。
【００８８】
こうすることで、ツリー要素名中にツリー階層識別子と同じ文字を記述することができる。
【００８９】
ツリー階層識別子に囲まれた中で先頭のツリー要素をｃａｒ要素と呼び、それ以外のツリー要素をｃｄｒ要素と呼ぶ。
【００９０】
なお、ツリー要素値、ツリー要素属性、ツリー要素属性値については、実施形態１と２で示した方法で配置する。
【００９１】
例えば、あるツリー要素Ａの一つ下の階層にツリー要素Ｂとツリー要素Ｃがある場合には、ツリー階層先頭識別子に記号「（」を用い、ツリー階層最後尾識別子に記号「）」を用い、ツリー要素セパレータには記号「，」を用いた場合に、図６の（ａ）のようになる。ｃａｒ要素はツリー要素Ａであり、ｃｄｒ要素はツリー要素ＢとＣになる。
【００９２】
同様にして、あるツリー要素Ａの一つ下の階層にツリー要素Ｂがあり、その下にツリー要素Ｃがある場合には、図６の（ｂ）のようになる。ｃａｒ要素はツリー要素Ａであり、ｃｄｒ要素は（，Ｂ，Ｃ，）になる。
【００９３】
同様にして、あるツリー要素Ａの一つ下の階層にツリー要素ＢとＥがあり、ツリー要素Ｂの一つ下にツリー要素Ｃ、さらに一つ下にツリー要素Ｄがある場合には、図６の（ｃ）のようになる。ｃａｒ要素はツリー要素Ａであり、ｃｄｒ要素は（，Ｂ，（，Ｃ，Ｄ，），）とＥになる。
【００９４】
同様に図９のデータ変換結果は下記のような記述になる。
【００９５】
［８］本実施形態によるツリー文字列データの例。
【００９６】
（，会社組織，（，東京本社，（，経理部住所＝”７階”郵便番号＝”２７１−００６７”，部員番号＝”１”％福沢諭吉，部員番号＝”２”％新渡戸稲造，部員番号＝”２”％夏目漱石，），），（，沼津工場，技術部，試験部，），（，関西支社，営業部，），）
（２）ツリー文字列データからツリー構造データへの復元方法
データ変換部２は、ツリー文字列データからツリー構造データへの復元機能を設け、この処理は図７に示し、以下の手順で実現される。
【００９７】
ツリー文字列データ全体の先頭のツリー要素（ｃａｒ要素）を親ツリー要素とし、そのｃｄｒ要素を子ツリー要素とする（Ｓ３１）。この親ツリー要素と子ツリー要素を処理Ａに渡して実行する（Ｓ３２）。処理Ａの開始で、指定された子ツリー要素がある限り、その先頭から順に一つずつ子ツリー要素を取り出す（Ｓ３３）。なお、「一つずつ」とは、例えば、子ツリー要素がＢ，（Ｃ，Ｃ，）Ｅとすると、１番目がＢで、２番目が（，Ｃ，Ｄ，）で、３番目がＥである。
【００９８】
次に、取り出した子ツリー要素がｃａｒ要素とｃｄｒ要素から成り立っているか否かをチェックする（Ｓ３４）。子ツリー要素がｃａｒ要素とｃｄｒ要素から成り立っていれば、親ツリー要素に子ツリー要素中のｃａｒ要素を追加する（Ｓ３５）。さらに、子ツリー要素中のｃａｒ要素を親ツリー要素とし、子ツリー要素中のｃｄｒ要素を子ツリー要素とする（Ｓ３６）。このＳ３６で区分した親ツリー要素と子ツリー要素を復元した要素として決定し、処理Ｓ３３に戻って次の要素についての繰り返し処理に入る（Ｓ３７）。処理Ｓ３４において、子ツリー要素がｃａｒ要素とｃｄｒ要素から成り立っていない場合、親ツリー要素に子ツリー要素を追加し、処理Ｓ３３に戻って次の要素についての繰り返し処理に入る（Ｓ３８）。
【００９９】
（３）本実施形態の特徴
本実施形態では、ツリー文字列データのサイズが実施形態３よりも小さくなる場合がある。ただし、データのサイズは、変換するツリー構造データの構造により変化する。その変化の度合いは、最小の場合は実施形態３よりも小さく実施形態４の最小値とほぼ同じである。最大の場合でも実施形態４の最大の場合よりも小さくなる。データサイズの比較は後に説明する。
【０１００】
また、本実施形態では、実施形態１や２と併用することでツリー要素に要素値や属性値を持たせることが可能なのでＸＭＬと同様なツリー構造データを得ることができる。
【０１０１】
短所としては、ツリー文字列データをツリー構造データにする場合に、ツリー文字列データの先頭から順に処理するだけではなく、あるツリー階層先頭識別子に対応したツリー階層最後尾識別子を探す必要があるなど、処理が複雑になる。そのため、変換する際の処理負荷が大きくなることが挙げられる。
【０１０２】
（４）データ量
本実施形態でのデータ量は以下のようになる。
【０１０３】
データ量＝各要素サイズの合計＋ツリー階層識別子サイズ＊ツリー階層識別子数＋ツリー要素セパレータサイズ＊ツリー要素セパレータ数
データ量ｄは、全要素数をｘ、要素サイズをｅ、識別子サイズを１、ツリー要素セパレータサイズを１とすると次式のように表現できる。
【０１０４】
ｄ＝（ｅ＋５）ｘ−５（最大時）
ｄ＝（ｅ＋１）ｘ＋３（最小時）
（注）最小時とは、親ツリー要素が一つであり他のツリー要素は全てその子ツリー要素の場合である。最大時とは、親ツリー要素が一つあり、その子要素ツリー要素が一つあり、その子要素ツリーに子要素ツリーが一つあり、…を繰り返す場合である。
【０１０５】
なぜならば、
最小時には、識別子数＝２となり、
ｄ＝ｅｘ＋２＋（ｘ＋２−１）
＝（ｅ＋１）ｘ＋３
最大時には、識別指数＝（ｘ一１）＊２となり、
ｄ＝ｅｘ＋（ｘ−１）＊２＋｛ｘ＋（ｘ−１）＊２−１｝
＝（ｅ＋５）ｘ−５
また、ＸＭＬのデータサイズは省略タグ「／」を用いた場合で、ヘッダーや属性を除いた部分のデータサイズは次のようになる。
【０１０６】
最小時：（ｅ＋３）ｘ−１
最大時：２ｘ＋７ｅ−２
（各実施形態のデータ量比較）
ツリー階層を表現する方法として実施形態３〜５を示したが、これとＸＭＬでツリー階層を表したときのツリー文字列データのサイズ比較を下記の表に示す。
【０１０７】
【表１】
2005148970.tif 000003
【０１０８】
比較に使用したツリー構造データは、図９に示したデータである。これを見るといずれの場合もＸＭＬよりデータサイズが２０％以上小さくなっていることが分かる。
【０１０９】
実施形態３〜５とＸＭＬについて、ツリー要素数とツリー文字列データのサイズの関係をグラフにしたものを図８に示す。ここでは、各ツリー要素名のサイズを２４、ツリー要素セパレータサイズを１、終端識別子サイズを１とした。また、実施形態４と５それからＸＭＬの各方法はツリー構造データによりデータ量が異なるので、ある要素数のときにデータ数が最小（マトリックスが最も密になっている）、データ数が最大（マトリックスが最も疎になっている）、ツリー構造データが２分木（一つのツリー要素は二つの子ツリー要素を持つ）、の三つの場合について示した。
【０１１０】
図８を見ると、実施形態３（深さ優先）はＸＭＬよりもデータサイズが小さいことが分かる。実施形態４（マトリックス）と実施形態５（リスト）では、実施形態３よりもさらにデータサイズが小さくなる場合があることが分かる。
【図面の簡単な説明】
【０１１１】
【図１】本発明の実施形態１におけるデータ変換したツリー構造データとツリー文字列データ構造の例。
【図２】実施形態３におけるツリー階層関係のデータ変換例。
【図３】実施形態３におけるツリー文字列データからツリー構造データへの変換処理手順。
【図４】実施形態４における行列構造とマトリックス方式の記述例。
【図５】実施形態４におけるツリー文字列データからツリー構造データへの復元処理手順。
【図６】実施形態５における階層構造と文字列データ例。
【図７】実施形態５におけるツリー文字列データからツリー構造データへの変換処理手順。
【図８】ＸＭＬと実施形態における要素数とツリー文字列データサイズの例。
【図９】ツリー構造データの例。
【図１０】ＸＭＬの記述例。
【符号の説明】
【０１１２】
１  ツリー構造データ
２  データ変換部
３  ツリー文字列データ
【図１】
2005148970.tif 000004
【図２】
2005148970.tif 000005
【図３】
2005148970.tif 000006
【図４】
2005148970.tif 000007
【図５】
2005148970.tif 000008
【図６】
2005148970.tif 000009
【図７】
2005148970.tif 000010
【図８】
2005148970.tif 000011
【図９】
2005148970.tif 000012
【図１０】
2005148970.tif 000013