(57)【特許請求の範囲】
【請求項１】
ＸＭＬ（Extensible Markup Language）文書を保管するＸＭＬ文書格納部から前記ＸＭＬ文書を取り出し、当該前記ＸＭＬ文書から各ノードのノード名称を抽出するノード名称抽出部と、
ｎ個のノードを持つ前記ＸＭＬ文書から各ノードのノード種類を抽出し、当該各ノードの前記ノード種類と前記ノード名称抽出部で抽出した各ノードの前記ノード名称とを含む情報リストをリスト格納部に出力するノード種類抽出部と、
前記ＸＭＬ文書の各ノードを木構造で表した場合のノード深さを測定し、測定した前記ノード深さを順に並べた数列を求めるノード深さ測定部と、
縦横ｎ本ずつの格子に沿って左上端点から右上半分には決して入らないように右下端点に至る全ての最短経路を求め、該全ての最短経路各々における各縦の経路には、左上は２から始まり、真下の縦の経路には１足した数字、右隣の縦の経路には１引いた数字が順に割り振られ、前記ノード深さ測定部により得られた前記数列から先頭の１を除いた数列における前記ノード深さ各々と前記各縦の経路に割り振られた数字とが等しくなる経路を順次選択することによって前記数列を前記最短経路に変換する折れ線変換部と、
前記折れ線変換部により前記求められた前記全ての最短経路のそれぞれを識別する複数の構造番号のうち、前記折れ線変換部により前記変換された前記最短経路に対応する前記構造番号を数値格納部に出力する数値変換部と、を備えるＸＭＬ文書変換装置。
【請求項２】
請求項１に記載のＸＭＬ文書変換装置であって、
前記全ての最短経路それぞれを識別する複数の前記構造番号各々は、前記格子における縦横の経路が交差する点において下に行く選択肢と右に行く選択肢とが選べる場合に、前記選択肢の一方に行くよりも他方に行く方が順番が早いという規則の下で設定された数値を前記選択肢の一方の経路の全てに記した前記格子において、前記全ての最短経路各々内における前記選択肢の一方の経路に記された数値の和である、ＸＭＬ文書変換装置。
【請求項３】
ｎ個のノードを持つＸＭＬ（Extensible Markup Language）文書の構造を、縦横ｎ本ずつの格子に沿って左上端点から右上半分には決して入らないように右下端点に至る全ての最短経路のいずれかに対応させた構造番号として格納している数値格納部から、前記構造番号を取り出し、前記全ての最短経路それぞれを識別する複数の前記構造番号のうち前記数値格納部から取り出した前記構造番号と一致するものに対応する前記最短経路を選択する折れ線復元部と、
前記全ての最短経路各々における各縦の経路には、左上は２から始まり、真下の縦の経路には１足した数字、右隣の縦の経路には１引いた数字が順に割り振られ、前記折れ線復元部により選択された前記最短経路における前記縦の経路に割り振られた数字の列に対してさらに先頭に１を付与することにより、前記ＸＭＬ文書の各ノードを木構造で表した場合における当該各ノードのノード深さを並べた数列を復元する数列復元部と、
前記数列復元部により復元された前記数列に基づき、前記ＸＭＬ文書の木構造を復元する木構造復元部と、
前記ＸＭＬ文書の各ノードのノード名称及びノード種類を有する情報リストを格納したリスト格納部から前記情報リストを取り出し、当該前記情報リストに基づき、前記木構造復元部により復元された前記ＸＭＬ文書の木構造における各ノードに前記ノード種類を付与するノード種類付与部と、
当該前記情報リストに基づき、前記木構造復元部により復元された前記ＸＭＬ文書の前記木構造における各ノードにさらに前記ノード名称を付与することにより得られる前記ＸＭＬ文書をＸＭＬ文書格納部に出力するノード名称付与部と、を備えるＸＭＬ文書復元装置。
【請求項４】
請求項３に記載のＸＭＬ文書変換装置であって、
前記全ての最短経路それぞれを識別する複数の前記構造番号各々は、前記格子における縦横の経路が交差する点において下に行く選択肢と右に行く選択肢とが選べる場合に、前記選択肢の一方に行くよりも他方に行く方が順番が早いという規則の下で設定された数値を前記選択肢の一方の経路の全てに記した前記格子において、前記全ての最短経路各々内における前記選択肢の一方の経路に記された数値の和である、ＸＭＬ文書復元装置。
【請求項５】
ＸＭＬ文書を格納するＸＭＬ文書格納部と、
前記ＸＭＬ文書の各ノードのノード名称及びノード種類を有する情報リストを格納したリスト格納部と、
ｎ個のノードを持つ前記ＸＭＬ文書の構造を、縦横ｎ本ずつの格子に沿って左上端点から右上半分には決して入らないように右下端点に至る最短経路に対応させた構造番号として格納している数値格納部と、
請求項１又は請求項２に記載のＸＭＬ文書変換装置と、
請求項３に記載のＸＭＬ文書復元装置とを備えるＸＭＬ文書処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＸＭＬ文書変換装置、ＸＭＬ文書復元装置及びＸＭＬ文書処理装置に係る発明である。
【背景技術】
【０００２】
近年、インターネットの普及により、ＨＴＭＬ（Hyper Text Markup Language）文書やＸＭＬ（Extensible Markup Language）文書などの構造化文書が用いられる機会が増加している。特に、ＸＭＬ文書は、ＨＴＭＬ文書を補う次世代の言語として注目を集めており、構造を圧縮する仕組みとしても、従来から様々な手法が用いられている。
【０００３】
代表的な圧縮手法としては、ＸＭＬ文書の構造のうち同じ構造が繰り返される部分を抽出し、当該部分に別名をつけて置換して圧縮する方法がある。例えば、特許文献１では、ＸＭＬ文書を検索して複数の箇所で共通する文書の構造をテンプレートとして作成し、当該テンプレートと同じ構造の箇所をテンプレート名に置換し、さらに置換後のＸＭＬ文書に対しても再びテンプテートで再置換を行っている。
【０００４】
【特許文献１】特開２００５−２０２５０７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、従来のＸＭＬ文書の圧縮手法は、ＸＭＬ文書中に同じ構造がないと圧縮ができない。このため、従来のＸＭＬ文書の圧縮手法は、ＸＭＬ文書で同じ構造が繰り返されているような特定のＸＭＬ文書にしか適用できない課題があった。
【０００６】
また、従来のＸＭＬ文書の圧縮手法では、置換後のＸＭＬ文書及びテンプレートの両方に木構造のデータが最終的に残る。そのため、従来のＸＭＬ文書の圧縮手法を用いても、最終的に得られるＸＭＬ文書の構造は複雑で、結果的に多くの情報量が必要になる課題があった。
【０００７】
そこで、本発明は、上記のような課題を解決するためになされたもので、任意のＸＭＬ文書に対して、文書構造を数値に変換できるＸＭＬ文書変換装置、数値を文書構造に復元できるＸＭＬ文書復元装置、さらに両装置を含むＸＭＬ文書処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る解決手段は、ＸＭＬ（Extensible Markup Language）文書を保管するＸＭＬ文書格納部からＸＭＬ文書を取り出し、当該ＸＭＬ文書から各ノードのノード名称を抽出するノード名称抽出部と、ｎ個のノードを持つＸＭＬ文書から各ノードのノード種類を抽出し、当該各ノードのノード種類をノード名称抽出部で抽出した各ノードのノード名称を含む情報リストをリスト格納部に出力するノード種類抽出部と、ＸＭＬ文書の各ノードを木構造で表した場合のノード深さを測定し、測定したノード深さを順に並べた数列を求めるノード深さ測定部と、縦横ｎ本ずつの格子に沿って左上端点から右上半分には決して入らないように右下端点に至る全ての最短経路を求め、該最短経路各々における各縦の経路には、左上は２から始まり、真下の縦の経路には１足した数字、右隣の縦の経路には１引いた数字が順に割り振られ、前記ノード深さ測定部により得られた前記数列から先頭の１を除いた数列における前記ノード深さ各々と前記各縦の経路に割り振られた数字とが等しくなる経路を順次選択することによって数列を最短経路に変換する折れ線変換部と、折れ線変換部により求められた全ての最短経路それぞれに構造番号を付し、折れ線変換部により変換された最短経路に対応する構造番号を数値格納部に出力する数値変換部とを備える。
【発明の効果】
【０００９】
本発明に記載のＸＭＬ文書変換装置は、ノード深さを順に並べて数列を縦横格子の最短経路に変換する折れ線変換部と、最短経路に対応する構造番号を数値格納部に出力する数値変換部とを備えので、任意のＸＭＬ文書に対して、文書構造を数値に変換でき、情報量を少なくすることができる。
【発明を実施するための最良の形態】
【００１０】
（実施の形態１）
まず、本発明で取り扱うＸＭＬ文書の構成について説明する。ＸＭＬ文書は、構成する要素や属性としてノードを有している。本発明で取り扱うＸＭＬ文書のノードでは、「空でない要素」，「空要素」，「属性」，「要素のテキスト」，「属性のテキスト」の５種類から構成されているものとする。「空でない要素」は、ＸＭＬ文書において最も基本となる情報単位である。「空要素」は、内容を持たない空の要素である。「属性」は、ＸＭＬ文書の中で要素に対して付加的な情報を付け加える。「要素のテキスト」は、要素の値である。「属性のテキスト」は、属性の値である。
【００１１】
なお、ＸＭＬ文書のノードとしては、他に「ＸＭＬ宣言」，「処理命令」，「ＣＤＡＴＡセクション」，「コメント」，「文字参照」，「エンティティ参照」等があるが、ＸＭＬ文書中の主要なノードではないので、本発明で取り扱うＸＭＬ文書ではノードとして考慮しない。ここで、「ＸＭＬ宣言」は、ＸＭＬ文書がＸＭＬ文書であることを宣言する。「処理命令」は、アプリケーションへの処理命令を記述する。「ＣＤＡＴＡセクション」は、ＸＭＬ文書要素として論理や意味構造を無視する文を記述する。「コメント」は、ＸＭＬ文書要素として解釈されない注釈文を記述する。「文字参照」は、文字コードによる文字の参照を記述する。「エンティティ参照」は、文字列やファイルを参照するエンティティを記述する。
【００１２】
さらに、本発明で取り扱うＸＭＬ文書では、ノード間の改行及び空白（いわゆるIgnorable White Space）をノードとして扱わず無視する。例えば、後述する図２に示すＸＭＬ文書では、<aaa bbb="ccc">から<ddd>eee</ddd>まで、<ddd>eee</ddd>から</aaa>までのそれぞれに改行や空白を有しているが、本発明で取り扱うＸＭＬ文書では、当該改行や空白をノードとして扱わず無視する。
【００１３】
図１に、本実施の形態に係るＸＭＬ文書処理装置の概略図を示す。図１に示すＸＭＬ文書処理装置は、ＸＭＬ文書格納部１０，リスト格納部２０，ＸＭＬ文書変換装置３０，ＸＭＬ文書復元装置４０，数値格納部５０を備えている。
【００１４】
ここで、ＸＭＬ文書格納部１０は、ＸＭＬ文書変換装置３０によってテーブル形式のデータに変換する前のＸＭＬ文書や、ＸＭＬ文書復元装置４０によってテーブル形式のデータから復元されたＸＭＬ文書を格納するための格納部である。リスト格納部２０は、ＸＭＬ文書のうちノード名称及びノード種類をリスト形式の情報リストに格納するための格納部である。
【００１５】
ＸＭＬ文書変換装置３０は、ＸＭＬ文書格納部１０に格納されているＸＭＬ文書からノード名称及びノード種類をリスト形式の情報リストに変換してリスト格納部２０に送出し、ノードの構造を数値に変換して数値格納部５０に送出する。ＸＭＬ文書変換装置３０は、ノード名称抽出部３１、ノード種類抽出部３２、ノード深さ測定部３３、折れ線変換部３４，数値変換部３５を備えている。
【００１６】
ノード名称抽出部３１は、ＸＭＬ文書格納部１０から取り出したＸＭＬ文書から各ノードのノード名称を抽出する。ノード種類抽出部３２は、ＸＭＬ文書からノード種類を表す情報（具体的には「空でない要素」「空要素」「属性」「要素のテキスト」「属性のテキスト」）を抽出する。抽出されたノード種類は、ノード名称抽出部３１で抽出されたノード名称とともに情報リストとしてリスト格納部２０へ出力される。
【００１７】
ノード深さ測定部３３は、ＸＭＬ文書の各ノードを木構造で表した場合に、当該各ノードのノード深さを測定する。折れ線変換部３４は、ノード深さ測定部３３で測定したノード深さを順に並べて数列として表し、当該数列を縦横格子の左上端点から右下端点までの最短経路に変換する。ここで、最短経路とは、縦横ｎ本の格子の左上端点から、端点間を右に（ｎ−１）回、下に（ｎ−１）回だけそれぞれ移動することにより右下端点に到着できる経路である。数値変換部３５は、縦横格子の左上端点から右下端点までの最短経路のそれぞれに構造番号を付し、折れ線変換部３４で変換した最短経路に対応する構造番号を数値格納部５０に出力する。
【００１８】
なお、ＸＭＬ文書のノード名称，ノード種類及びノード深さ等をＸＭＬ文書から抽出又は測定するには、ＤＯＭ（Document Object Model）と呼ばれるＡＰＩによって実現することができる。このＤＯＭは、Ｗｅｂの標準化団体であるＷ３Ｃ（The World Wide Web Consortium）により規格化されたＡＰＩであり、当該分野においてデファクトスタンダードである。
【００１９】
但し、このＤＯＭでは、「属性」を「要素」の子ノードとして扱わないが、本発明でＸＭＬ文書を取り扱う場合には、「属性」を「要素」の子ノードとして扱う。
【００２０】
ＸＭＬ文書復元装置４０は、リスト格納部２０に格納されているノード名称及びノード種類のリスト形式の情報リストと、数値格納部５０に格納されているノードの構造を表す数値（構造番号）とからＸＭＬ文書を復元する。ＸＭＬ文書復元装置４０は、ノード名称付与部４１，ノード種類付与部４２，木構造復元部４３，数列復元部４４，折れ線復元部４５を備えている。これらノード名称付与部４１〜折れ線復元部４５のそれぞれは、ノード名称抽出部３１〜数値変換部３５におけるそれぞれの変換動作に対応した復元動作を行うものである。
【００２１】
折れ線復元部４５は、数値格納部５０から取り出した数値（構造番号）を、縦横格子に沿った左上端点から右下端点までの最短経路に復元する。数列復元部４４は、折れ線復元部４５で復元された最短経路を、ＸＭＬ文書の各ノードを木構造で表した場合に、当該各ノードのノード深さを並べた数列に復元する。木構造復元部４３は、数列復元部４４で復元された数列から、ＸＭＬ文書の各ノードの木構造を復元する。ノード種類復元部４２は、情報リストとしてリスト格納部２０に格納されたノード種類を取り出し、木構造復元部４３で復元された各ノードに対して、ノード種類である「空でない要素」「空要素」「属性」「要素のテキスト」「属性のテキスト」を付与する。ノード名称付与部４１は、木構造復元部４３で復元された各ノードに対して、ノード名称を付与してＸＭＬ文書を復元し、当該ＸＭＬ文書をＸＭＬ文書格納部１０に出力する。
【００２２】
数値格納部５０は、縦横格子の左上端点から右下端点までの最短経路のそれぞれに構造番号を付し、ＸＭＬ文書の構造に対応する構造番号を格納するための格納部である。
【００２３】
次に、本実施の形態に係るＸＭＬ文書処理装置の動作について説明する。まず、ＸＭＬ文書からテーブル形式のデータへ変換するＸＭＬ文書変換装置３０の動作について説明する。
【００２４】
最初に、ＸＭＬ文書変換装置３０は、ＸＭＬ文書格納部１０から、テーブル形式のデータ（情報リスト及び構造番号）に変換したいＸＭＬ文書を取り出す。そして、ＸＭＬ文書変換装置３０は、ＸＭＬ文書を取り出した後、ＸＭＬ文書の各ノードに対して、ノード名称抽出部３１、ノード種類抽出部３２，ノード深さ測定部３３がそれぞれ以下の操作を行う。
【００２５】
まず、（１）ノード名称抽出部３１が、取り出したＸＭＬ文書の各ノードからノード名称を取得する。（２）ノード種類抽出部３２が、取り出したＸＭＬ文書の各ノードからノード種類を取得する。（３）ノード深さ測定部３３が、ルートノードの深さを１として、各ノードのノード深さを測定する。つまり、ルートノードの子ノードのノード深さは２、その子ノードの深さは３、というようになる。
【００２６】
さらに、（４）折れ線変換部３４では、ノード深さ測定部３３でノード深さを測定したノード数ｎのＸＭＬ文書を、ルートノード以外の各ノードについてノード深さ順に並べた長さｎ−１の数列で表す。そして、折れ線変換部３４では、当該数列を、縦横ｎ本ずつの格子に沿って左上端点から右上半分に決して入らないような右下端点まで至る最短経路に対応させる。ここで、右上半分に決して入らないような右下端点まで至る最短経路とは、左上端点から右下端点に至る最短経路のうち、端子間を下に移動する回数を、端子間を右に移動する回数が常に上回らないように至る最短経路である。折れ線変換部３４で用いる格子の縦経路には、所定の基準に基づき数字が順に割り振られており、当該数字とＸＭＬ文書の長さｎ−１の数列とが同じになるように最短経路を選択する。
【００２７】
（５）数値変換部３５は、格子の左上端点から右下端点までの最短経路のそれぞれに構造番号を付し、折れ線変換部３４で変換した最短経路に対応する構造番号を数値格納部５０に出力する。なお、最短経路のそれぞれに付す構造番号は、所定の基準に基づき格子の横経路のいくつかに割り当てられた数字を、最短経路に沿って足した値となる。
【００２８】
具体的に、図２に示すＸＭＬ文書をＸＭＬ文書格納部１０から取り出した場合に、ＸＭＬ文書変換装置３０が行う（１）〜（５）の操作について説明する。図３は、図２に示すＸＭＬ文書の木構造を示す説明図である。図４は、図２に示すＸＭＬ文書から抽出した情報リスト（ノード名称及びノード種類）の説明図である。
【００２９】
まず、図２に示すaaaのノードでは、ノード名称抽出部３１がノード名称aaaを抽出する。そして、ノード種類抽出部３２が当該ノード（aaa）のノード種類「空でない要素」を抽出する。aaaのノードは、ルートノードであり、ルートノードの深さを１としているので、ノード深さ測定部３３ではノード深さ１を得ることになる。以上の操作により、ＸＭＬ文書変換装置３０は、図４に示す情報リストの１行目の１番目にaaaを、２行目の１番目に「空でない要素」を格納する。
【００３０】
次に、図２に示すbbbのノードでは、ノード名称抽出部３１がノード名称bbbを抽出する。そして、ノード種類抽出部３２が当該ノード（bbb）のノード種類「属性」を抽出する。上述したように本願では、「属性」が「要素」の子ノードという約束であるから、bbbのノードの深さは２となり、ノード深さ測定部３３はノード深さ２を得る。以上の操作により、ＸＭＬ文書変換装置３０は、図４に示す情報リストの１行目の２番目にbbbを、２行目の２番目に「属性」を格納する。
【００３１】
次に、図２に示すcccのノードでは、ノード名称抽出部３１がノード名称cccを抽出する。そして、ノード種類抽出部３２が当該ノード（ccc）のノード種類「属性のテキスト」を抽出する。cccのノードの深さは３であり、ノード深さ測定部３３はノード深さ３を得る。以上の操作により、ＸＭＬ文書変換装置３０は、図４に示す情報リストの１行目の３番目にcccを、２行目の１番目に「属性のテキスト」を格納する。
【００３２】
次に、図２に示すdddのノードでは、ノード名称抽出部３１がノード名称dddを抽出する。そして、ノード種類抽出部３２が当該ノード（ddd）のノード種類「空でない要素」を抽出する。dddのノードの深さは２であり、ノード深さ測定部３３はノード深さ２を得る。以上の操作により、ＸＭＬ文書変換装置３０は、図４に示す情報リストの１行目の４番目にdddを、２行目の４番目に「空でない要素」を格納する。
【００３３】
次に、図２に示すeeeのノードでは、ノード名称抽出部３１がノード名称eeeを抽出する。そしてノード種類抽出部３２が当該ノード（eee）のノード種類「要素のテキスト」を抽出する。eeeのノードの深さは３であり、ノード深さ測定部３３はノード深さ３を得る。以上の操作により、ＸＭＬ文書変換装置３０は、図４に示す情報リストの１行目の５番目にeeeを、２行目の５番目に「要素のテキスト」を格納する。
【００３４】
以上のように、ノード（aaa）は、ノード深さが「１」でルートノード（親ノード）であり、この親ノードに対する子ノードは、ノード深さが「２」であるノード（bbb）とノード（ddd）である。そのため、当該関係を図３の木構造で表せば、ノード（aaa）にノード（bbb）及びノード（ddd）がぶら下がる関係となる。さらに、ノード（bbb）に対する子ノード（ノード（aaa）に対する孫ノード）は、ノード深さが「３」であるノード（ccc）である。そのため、当該関係を図３の木構造で表せば、ノード（bbb）にノード（ccc）がぶら下がる関係となる。同様に、ノード（ddd）に対する子ノード（ノード（aaa）に対する孫ノード）は、ノード深さが「３」であるノード（eee）である。そのため、当該関係を図３の木構造で表せば、ノード（ddd）にノード（eee）がぶら下がる関係となる。
【００３５】
また、以上の操作により、図４に示すような情報リストが作成され、リスト格納部２０に格納される。さらに、ノード深さ測定部３３では、各ノードのノード深さについてノード深さ順に並べた数列１２３２３を得る。
【００３６】
次に、折れ線変換部３４では、数列１２３２３のうち、ルートノードの深さ１を除いた数列２３２３（長さｎ−１）を、縦横５本（ｎ本）ずつの格子に沿って左上端点から右上半分には決して入らないように右下端点に至る最短経路に変換する。そして、数値変換部３５は、折れ線変換部３４で変換した最短経路を、複数ある最短経路のうちから識別できるように番号（構造番号）を付して数値化する。なお、これらの処理には、以下に説明する数学的知見が必要となる。
【００３７】
まず、（ア）ＸＭＬ文書はラベル付き順序木（ordered tree）である。従って、ＸＭＬ文書の構造は順序木となる。（イ）ｎ個のノードを持つ順序木とｎ個のノードを持つ２分木は１対１に対応することが数学的に知られている。（ウ）ｎ個のノードを持つ２分木の場合の数は、カタラン数Ｃｎ−１であることが数学的に知られている。ここでカタラン数Ｃｎ（ｎ≧０）の一般式は、Ｃｎ＝（２ｎ）！／（（ｎ＋１）！ｎ！）で与えられる。（エ）カタラン数Ｃｎは、縦横ｎ＋１本ずつの格子に沿って左上端点から右上半分には決して入らないように右下端点に至る最短経路の数に等しいことが数学的に知られている。
【００３８】
以上の（ア）〜（エ）条件により、ｎ個のノードを持つＸＭＬ文書の取りうる構造の場合の数は、縦横ｎ本ずつの格子に沿って左上端点から右上半分には決して入らないように右下端点に至る最短経路の数に等しいことが分かる。
【００３９】
上述した一般式でカタラン数Ｃｎ−１を計算することができるが、帰納的に求めることもできる。具体的に、ｎ＝５の場合のカタラン数Ｃ４は、図５に示す縦横５本ずつの格子の左上端点から右下端点までの最短距離の場合の数で求めることができる。
【００４０】
なお、左上端点から右下端点までの最短経路は、右下端点から左上端点までの最短経路に等しい。そのため、図５では、右下端点である頂点Ａから左上端点である頂点Ｏに至る最短距離を説明する。まず、頂点Ａから頂点Ｂまでの経路は１通りなので、図５に示すように頂点Ｂに１を記す。頂点Ａから頂点Ｃまでの経路は、頂点Ｂを経由する場合しかなく１通りであり、図５に示すように頂点Ｃに１を記す。頂点Ａから頂点Ｆまでの経路は、頂点Ｂを経由する場合しかなく１通りであり、図５に示すように頂点Ｆに１を記す。
【００４１】
頂点Ａから頂点Ｇまでの経路は、頂点Ｃを経由する場合と頂点Ｆを経由する場合で２通りある。よって、頂点Ａから頂点Ｇまでの経路は、頂点Ｃに記されている値１と頂点Ｆに記されている値１を足した値になり、図５に示すように頂点Ｇに２を記す。以上の関係に基づき、頂点Ａからある頂点までの経路は、頂点Ａからある頂点のすぐ下の頂点までの経路と、頂点Ａからある頂点のすぐ右の頂点までの経路の和に等しいことが分かる。
【００４２】
この法則に基づき、各頂点に値を順番に記していくと、図５に示すように頂点Ｎには１４が記される。従って、頂点Ａから頂点Ｏまでの経路は１４通りとなる。
【００４３】
以上の知見を踏まえ、折れ線変換部３４の動作を説明する。図６に示す格子では、各縦の経路には数字が順に割り振られている。つまり、図６の左端の縦の経路には２，３，４，５が、次の縦の経路には２，３，４が割り振られている。そして、折れ線変換部３４は、ノード深さ測定部３３で得た数列２３２３と縦の経路に割り振られた数字とが等しくなるように最短経路を選択する。具体的には、左上端点から図６の左端の縦の経路に割り振られた数字を２，３と進み、横方向に２頂点分進み、さらに縦の経路に割り振られた数字を２，３と進み、そして横方向に進んで右下端点に至ることで、数列２３２３と等しくなる。図６の左上端点から右下端点に至る全ての最短経路及び当該経路で得られる数列を図７に示す。図７において実線で囲まれた最短経路が、数列２３２３の最短経路を表している。なお、図７に示す数列は、ルートノードの深さ１を付加した表記となっている。
【００４４】
次に、数値変換部３５の動作について説明する。まず、数値変換部３５は、格子の最短経路に番号（構造番号）付す。図５に示す格子に対しては、１４通りある最短経路のそれぞれに０番目から１３番目までの番号を付ける。具体的に説明すると、まず頂点Ｏから頂点Ｎに進むと、頂点Ｎから下に進み頂点Ｌを経由する選択肢と、頂点Ｎから右に進み頂点Ｍを経由する選択肢とがある。図５で説明したように、頂点Ｎから下に進み頂点Ｌを経由して頂点Ａまで到達する経路は９通り、頂点Ｎから右に進み頂点Ｍを経由して頂点Ａまで到達する経路は５通りある。ここで、右に進むより下に進む方ほど順番が早いという規則を設けると、頂点Ｎから右に進み頂点Ｍを経由する経路は、頂点Ｎから下に進み頂点Ｌを経由する経路より、少なくとも順番が９番遅いということになるので、頂点Ｎから頂点Ｍに向かう経路に図８に示すように９と記す。
【００４５】
さらに、頂点Ｎから下に進み頂点Ｌに進むと、頂点Ｌから下に進み頂点Ｉを経由する選択肢と、頂点Ｌから右に進み頂点Ｋを経由する選択肢とがある。図５で説明したように、頂点Ｌから下に進み頂点Ｉを経由して頂点Ａまで到達する経路は４通り、頂点Ｌから右に進み頂点Ｋを経由して頂点Ａまで到達する経路は５通りある。すると、頂点Ｌから右に進み頂点Ｋを経由する経路は、頂点Ｌから下に進み頂点Ｉを経由する経路より、少なくとも順番が４番遅いということになるので、ＬからＫに向かう経路に図８に示すように４と記す。
【００４６】
さらに、頂点Ｌから右に進み頂点Ｋに進む、あるいは頂点Ｎから右に進み頂点Ｍを経由して頂点Ｋに進むと、頂点Ｋから下に進み頂点Ｈを経由する選択肢と、頂点Ｋから右に進み頂点Ｊを経由する選択肢とがある。図５で説明したように、頂点Ｋから下に行き頂点Ｈを経由して頂点Ａまで到達する経路は３通り、頂点Ｋから右に行き頂点Ｊを経由して頂点Ａまで到達する経路は２通りある。すると、頂点Ｋから右に行き頂点Ｊを経由する経路は、頂点Ｋから下に行き頂点Ｈを経由する経路より少なくとも順番が３番遅いということになるので、頂点Ｋから頂点Ｊまでの経路に図８に示すように３と記す。
【００４７】
以下、同じように下に行く選択肢と右に行く選択肢が選べる場合、右に行くと少なくとも順番が何番遅いかを経路に全て記すと、図８のようになる。
【００４８】
そして、図８に示す横の経路に割り当てられた数値を用いて、図５に示す格子の各最短経路に番号（構造番号）を付す。つまり、各最短経路に番号（構造番号）は、最短経路で通った軌跡の横の経路に割り当てられた数値を足した値になる。具体的には、頂点Ｏから頂点Ａに至る最短経路のうち、頂点Ｎ，Ｌ，Ｉ，Ｅ，Ｄ，Ｃ，Ｂを通過する最短経路は、図８に示す横の経路に割り振られた数値を足した値が０となるので、当該最短経路の番号（構造番号）は０となる。同様に、図２のＸＭＬ文書に対応する数列２３２３の最短経路は、頂点Ｎ，Ｌ，Ｋ，Ｊ，Ｇ，Ｃ，Ｂを通過するので、図８に示す横の経路に割り振られた数値を足した値が７となり、当該最短経路の番号（構造番号）は７となる。なお、図７に示す全ての最短経路に対して番号を付した結果は、図９のようになる。
【００４９】
数値変換部３５は、上述のように図２のＸＭＬ文書に対応する数列２３２３の最短経路の構造番号が７と得られた場合、当該番号を数値格納部５０に格納する。以上の処理により、「空でない要素」「空要素」「要素のテキスト」「属性」「属性のテキスト」からなる任意のＸＭＬ文書の構造を、情報リストや構造番号からなるテーブル形式のデータに変換することができる。
【００５０】
次に、テーブル形式のデータ（情報リスト及び構造番号）からＸＭＬ文書へ復元するＸＭＬ文書復元装置４０の動作について説明する。まず、ＸＭＬ文書復元装置４０は、数値格納部５０から、復元したいＸＭＬ文書の構造番号を取り出す。そして、折れ線復元部４５は、取得した構造番号を格子の左上端点から右下端点に至る最短経路の番号と対応させて、取得した構造番号に対応する最短経路に変換する。ここで、数値格納部５０から取得した構造番号は、図８で示したように格子の最短経路を通った軌跡上の横経路に割り当てられた数値を足した値で決められている。
【００５１】
図８に示す格子を用いて、構造番号７の最短経路を復元する折れ線復元部４５での処理例を説明する。まず、頂点Ｏから頂点Ｎに進むと、頂点Ｎから右に進み頂点Ｍを経由する経路は、頂点Ｎから下に進み頂点Ｌを経由する経路より少なくとも順番が９番遅い。これは、頂点Ｎから下に進み頂点Ｌを経由する経路は９番目より早く、頂点Ｎから右に進み頂点Ｍを経由する経路は９番目もしくはそれより遅いということになる。従って、構造番号７（７番目）の最短経路は、頂点Ｎから下に進み頂点Ｌを経由する経路となる。
【００５２】
次に、頂点Ｎから頂点Ｌに進むと、頂点Ｌから右に進み頂点Ｋを経由する経路は、頂点Ｌから下に進み頂点Ｉを経由する経路より少なくとも順番が４番遅い。これは、頂点Ｌから下に進み頂点Ｉを経由する経路は４番目より早く、頂点Ｌから右に進み頂点Ｋを経由する経路は４番目もしくはそれより遅いということになる。従って、構造番号７（７番目）の最短経路は、頂点Ｎから右に進み頂点Ｋを経由する経路となる。
【００５３】
さらに、頂点Ｌから頂点Ｋへ進むと、頂点Ｋから右に進み頂点Ｊを経由する経路は、頂点Ｋから下に進み頂点Ｈを経由する経路より少なくとも順番が３番遅い。既に、頂点Ｌ，Ｋを通過する最短経路は、４番目もしくはそれ以降であるため、頂点Ｋから下に進み頂点Ｈを経由する経路は４＋３＝７番目より早く、頂点Ｋから右に進み頂点Ｊを経由する経路は４＋３＝７番目もしくはそれより遅いということになる。従って、構造番号７（７番目）の最短経路は、頂点Ｋから右に進み頂点Ｊを経由する経路となる。
【００５４】
頂点Ｋから頂点Ｊを経由して頂点Ｇへ進むと、頂点Ｇから右に進み頂点Ｆを経由する経路は、頂点Ｇから下に進み頂点Ｃを経由する経路より少なくとも順番が１番遅い。既に、頂点Ｌ，Ｋ，Ｊ，Ｇを通過する最短経路は、７番目もしくはそれ以降であるため、頂点Ｇから下に進み頂点Ｃを経由する経路は７＋１＝８番目より早く、頂点Ｇから右に進み頂点Ｆを経由する経路は７＋１＝８番目もしくはそれより遅いということになる。従って、構造番号７（７番目）の最短経路は、頂点Ｋから下に進み頂点Ｃを経由する経路となる。
【００５５】
頂点Ｇから下に進むと、最短経路の選択肢はなく、頂点Ｃ，Ｂを経由し頂点Ａに到達する。以上のように、選択肢のある頂点で順番の計算することで、構造番号７（７番目）の最短経路は図９において実線で囲まれた経路であることが分かる。
【００５６】
折れ線復元部４５で最短経路が復元された後に、数列復元部４４では、復元された最短経路を、ノード数ｎのＸＭＬ文書においてルートノード以外の各ノードについてノード深さ順に並べた長さｎ−１の数列に復元する。数列復元部４４の処理を具体的に説明すると、構造番号７（７番目）の最短経路である図９において実線で囲まれた最短経路が、図７において実線で囲まれた最短経路に対応し、その数列が２３２３となる。さらに、ルートノードの深さは１であるから、復元すべきＸＭＬ文書の構造の数列は１２３２３となる。
【００５７】
数列復元後に、木構造復元部４３が、復元した数列に対応するＸＭＬ文書の木構造を復元する。数列１２３２３は、ＸＭＬ文書の木構造で表すと図３のようになる。木構造を復元した後に、ＸＭＬ文書復元装置４０は、リスト格納部２０からＸＭＬ文書の各ノードのノード名称とノード種類が格納された情報リストを取り出し、ノード種類付与部４２が、当該情報リストに基づき、ＸＭＬ文書の各ノードに対してノード種類を付与する。
【００５８】
ノード種類付与部４２の処理を、図４の例に基づいて説明する。まず、図４に示す情報リストの２行目の１番目の値が「空でない要素」であるから、ＸＭＬ文書の１番目のノードに「空でない要素」のノード種類が付与される。さらに、図４に示す情報リストの２行目の２〜６番目についても同様に、ＸＭＬ文書の２〜６番目の各ノードに対してノード種類がそれぞれ付与される。
【００５９】
ＸＭＬ文書の各ノードにノード種類を付与した後、ノード名称付与部４１は、当該情報リストに基づき、ＸＭＬ文書の各ノードにノード名称を付与する。ノード名称付与部４１の処理を、の例に基づいて説明する。まず、図４に示す情報リストの１行目の１番目の値がaaaであるから、ＸＭＬ文書の１番目のノードにはaaaのノード名称が付与される。さらに、図４に示す情報リストの２行目の２〜６番目についても同様に、ＸＭＬ文書の２〜６番目の各ノードに対してノード名称がそれぞれ付与される。
【００６０】
そして、ＸＭＬ文書復元装置４０は、ノード名称付与部４１乃至折れ線復元部４５の処理により得られたノードの木構造、各ノード種類、各ノード名称により、ＸＭＬ文書を復元することができる。なお、復元されたＸＭＬ文書は、ＸＭＬ文書復元装置４０から文書格納部１０へ格納される。
【００６１】
以上のように、本実施の形態に係るＸＭＬ文書復元装置４０は、情報リストと構造番号から、「空でない要素」「空要素」「属性」「要素のテキスト」「属性のテキスト」のノードからなる任意のＸＭＬ文書を復元することができる。
【００６２】
本実施の形態のＸＭＬ文書変換装置３０は、上述したようにＸＭＬ文書を情報リスト及び構造番号に変換することができる。また、本実施の形態に係るＸＭＬ文書変換装置３０は、格子の最短経路にＸＭＬ文書の構造を対応させて数値（構造番号）に変換することができる。また、本実施の形態１に係るＸＭＬ文書変換装置３０は、ノード種類を、空でない要素、空要素、属性、要素のテキスト、属性のテキストとしたので、ＸＭＬ文書で最も基本となる情報単位でＸＭＬ文書の構造を数値（構造番号）化できる。さらに、数値（構造番号）でＸＭＬ文書の構造を保持できるので、ＸＭＬ文書の操作に必要となるメモリが少なくてすむ。
【００６３】
本実施の形態のＸＭＬ文書復元装置４０は、上述したように情報リスト及び構造番号からＸＭＬ文書を復元することができる。また、本実施の形態に係るＸＭＬ文書復元装置４０は、格子の最短経路にＸＭＬ文書の構造を対応させた数値（構造番号）から簡単な処理で元のＸＭＬ文書の構造に復元することができる。さらに、本実施の形態に係るＸＭＬ文書復元装置４０は、ノード種類を、空でない要素、空要素、属性、要素のテキスト、属性のテキストとしたので、ＸＭＬ文書で最も基本となる情報単位で数値（構造番号）からＸＭＬ文書の構造を復元できる。
【００６４】
（実施の形態２）
実施の形態１では、数値変換部３５及び折れ線復元部４５において、右に進むよりも下に進む方が最短経路の順番が早い規則を設定していた。しかし、本発明に係る数値変換部３５及び折れ線復元部４５は当該規則に限定されない。そこで、本実施の形態に係る数値変換部３５及び折れ線復元部４５では、下に進むよりも右に進む方が最短経路の順番が早い規則を設定している。この場合、格子の縦経路のいくつかに数字が割り当てられており、最短経路で通った軌跡上にある当該数字を足した値が最短経路の番号（構造番号）となる。なお、本実施の形態に係るＸＭＬ文書処理装置は、上記規則以外実施の形態１と同じ構成であるため、同じ要素には同一符号を付し、詳細な説明は省略する。
【００６５】
本実施の形態において、図５に示す格子の最短経路に対して０番目から１３番目までの番号（構造番号）を付与する方法を以下に説明する。まず、図５に示す頂点Ｏから頂点Ｎに進むと、頂点Ｎから下に進み頂点Ｌを経由する選択肢と、頂点Ｎから右に進み頂点Ｍを経由する選択肢とがある。頂点Ｎから下に進み頂点Ｌを経由して頂点Ａまで到達する経路は９通り、頂点Ｎから右に進み頂点Ｍを経由して頂点Ａまで到達する経路は５通りある。ここで、本実施の形態では、下に進むよりも右に進む方が最短経路の順番が早い規則を設定しているので、頂点Ｎから下に進み頂点Ｌを経由する経路は、頂点Ｎから右に進み頂点Ｍを経由する経路より、少なくとも順番が５番遅いということになり、頂点Ｎから頂点Ｌに向かう経路に図１０に示すように５を記す。
【００６６】
次に、頂点Ｎから下に進み頂点Ｌに進むと、頂点Ｌから下に進み頂点Ｉを経由する選択肢と、頂点Ｌから右に進み頂点Ｋを経由する選択肢とがある。図５において説明したように、頂点Ｌから下に進み頂点Ｉを経由して頂点Ａまで到達する経路は４通り、頂点Ｌから右に進み頂点Ｋを経由して頂点Ａまで到達する経路は５通りある。従って、頂点Ｌから下に進み頂点Ｉを経由する経路は、頂点Ｌから右に進み頂点Ｋを経由する経路より、少なくとも順番が５番遅いということになるので、頂点Ｌから頂点Ｉに向かう経路に図１０に示すように５を記す。
【００６７】
さらに、頂点Ｌから右に進み頂点Ｋに進む、あるいは頂点Ｎから頂点右に進み頂点Ｍを経由して頂点Ｋに進むと、頂点Ｋから下に進み頂点Ｈを経由する選択肢と、頂点Ｋから右に進み頂点Ｊを経由する選択肢とがある。図５において説明したように、頂点Ｋから下に行き頂点Ｈを経由して頂点Ａまで到達する経路は３通り、頂点Ｋから右に行き頂点Ｊを経由して頂点Ａまで到達する経路は２通りある。従って、頂点Ｋから下に行き頂点Ｈを経由する経路は、頂点Ｋから右に行き頂点Ｊを経由する経路より少なくとも順番が２番遅いということになるので、頂点Ｋから頂点Ｈに向かう経路に図１０に示すように２を記す。
【００６８】
以下、同じように下に行く選択肢と右に行く選択肢とが選べる場合、下に行くと少なくとも順番が何番遅くなるのかを縦経路に全て記す。図５に示す格子に対して、上述の方法で縦経路に数字を割り当てた結果が図１０のようになる。
【００６９】
そして、最短経路の番号（構造番号）は、最短経路で通った軌跡上の縦経路に割り当てられた数字を足した値となる。図２に示したＸＭＬ文書では、最短経路が図７において実線で囲まれた経路のようになり、この経路（頂点Ｏ，Ｎ，Ｌ，Ｋ，Ｊ，Ｇ，Ｃ，Ｂ，Ａ）上にある縦経路に割り当てられた数字の合計は６となる。従って、図２に示したＸＭＬ文書の最短経路の番号（構造番号）は、６である。なお、なお、本実施の形態において、図７に示す全ての最短経路に対する番号は、図１１に示すようになる。
【００７０】
次に、折れ線復元部４５の処理において、番号（構造番号）６から図１０に示す格子での最短経路を復元する場合を説明する。まず、頂点Ｏから頂点Ｎに進むと、頂点Ｎから下に進み頂点Ｌを経由する経路は、頂点Ｎから右に進み頂点Ｍを経由する経路より少なくとも順番が５番遅い。これは、頂点Ｎから右に進み頂点Ｍを経由する経路が５番目より早く、頂点Ｎから下に進み頂点Ｌを経由する経路が５番目もしくはそれより遅いということになる。従って、６番目の経路は、頂点Ｎから下に進み頂点Ｌを経由する経路となる。
【００７１】
次に、頂点Ｎから頂点Ｌに進むと、頂点Ｌから下に進み頂点Ｉを経由する経路は、頂点Ｌから右に進み頂点Ｋを経由する経路より少なくとも順番が５番遅い。既に、頂点Ｎ，Ｌを通過する最短経路は５番目もしくはそれ以降であるため、頂点Ｌから右に進み頂点Ｋを経由する経路が５＋５＝１０番目より早く、頂点Ｌから下に進み頂点Ｉを経由する経路が５＋５＝１０番目もしくはそれより遅いということになる。従って、６番目の経路は、頂点Ｎから右に進み頂点Ｋを経由する経路となる。
【００７２】
さらに、頂点Ｌから頂点Ｋへ進むと、頂点Ｋから下に進み頂点Ｈを経由する経路は、頂点Ｋから右に進み頂点Ｊを経由する経路より少なくとも順番が２番遅い。既に、頂点Ｎ，Ｌ，Ｋを通過する最短経路は５番目もしくはそれ以降であるため、頂点Ｋから右に進み頂点Ｊを経由する経路が５＋２＝７番目より早く、頂点Ｋから下に進み頂点Ｈを経由する経路が５＋２＝７番目もしくはそれより遅いということになる。従って、６番目の経路は、頂点Ｋから右に進み頂点Ｊを経由する経路となる。
【００７３】
さらに、頂点Ｋから頂点Ｊを経由して頂点Ｇへ進むと、頂点Ｇから下に進み頂点Ｃを経由する経路は、頂点Ｇから右に進み頂点Ｆを経由する経路より少なくとも順番が１番遅い。既に、頂点Ｎ，Ｌ，Ｋ，Ｊ，Ｇを通過する経路が５番目もしくはそれ以降であるため、頂点Ｇから右に進み頂点Ｆを経由する経路が５＋１＝６番目より早く、頂点Ｇから下に進み頂点Ｃを経由する経路が５＋１＝６番目もしくはそれより遅いということになる。従って、６番目の経路は、頂点Ｋから下に進み頂点Ｃを経由する経路となる。
【００７４】
頂点Ｇから下に進むと、最短経路の選択肢はなく、頂点Ｃ及び頂点Ｂを経由して頂点Ａに到達する。以上のように、選択肢のある頂点で順番の計算することで、構造番号６（６番目）の最短経路は図１１において実線で囲まれた経路であることが分かる。
【００７５】
以上のように、本実施の形態に係るＸＭＬ文書変換装置３０及びＸＭＬ文書復元装置４０では、数値格納部３５が最短経路の順番について下に進むより右に進むほど順番が早い規則に基づいており、折れ線復元部４５が当該規則に基づいて最短経路を復元するので、実施の形態１と同様の効果を期待できる。
【図面の簡単な説明】
【００７６】
【図１】本発明の実施の形態１に係るＸＭＬ文書処理装置のブロック図である。
【図２】本発明の実施の形態１に係るＸＭＬ文書を説明するための図である。
【図３】本発明の実施の形態１に係るＸＭＬ文書の木構造を説明するための図である。
【図４】本発明の実施の形態１に係るＸＭＬ文書の情報リストを説明するための図である。
【図５】本発明の実施の形態１に係るＸＭＬ文書に対応する格子の最短経路を説明するための図である。
【図６】本発明の実施の形態１に係るＸＭＬ文書に対応する数列を説明するための図である。
【図７】本発明の実施の形態１に係るＸＭＬ文書に対応する数列を説明するための図である。
【図８】本発明の実施の形態１に係るＸＭＬ文書の構造番号を説明するための図である。
【図９】本発明の実施の形態１に係るＸＭＬ文書の構造番号を説明するための図である。
【図１０】本発明の実施の形態２に係るＸＭＬ文書の構造番号を説明するための図である。
【図１１】本発明の実施の形態２に係るＸＭＬ文書の構造番号を説明するための図である。
【符号の説明】
【００７７】
１０  ＸＭＬ文書格納部、２０  リスト格納部、３０  ＸＭＬ文書変換装置、３１  ノード名称抽出部、３２  ノード種類抽出部、３３  ノード深さ測定部、３４  折れ線変換部、３５  数値変換部、４０  ＸＭＬ文書復元装置、４１  ノード名称付与部、４２  ノード種類復元部、４３  木構造復元部、４４  数列復元部、４５  折れ線復元部、５０  数値格納部。
【図１】
0005100220.tif 000002
【図２】
0005100220.tif 000003
【図３】
0005100220.tif 000004
【図４】
0005100220.tif 000005
【図５】
0005100220.tif 000006
【図６】
0005100220.tif 000007
【図７】
0005100220.tif 000008
【図８】
0005100220.tif 000009
【図９】
0005100220.tif 000010
【図１０】
0005100220.tif 000011
【図１１】
0005100220.tif 000012