(57)【要約】【課題】  構造化文書の圧縮および変換をともに行い、その変換の際には構造情報を解凍しなくても、圧縮および変換を効率よく行える文書変換装置を提供する。【解決手段】  文書変換装置１０１は、蓄積手段１０２により、特定パターンを有する構造情報をテンプレートとして蓄積し、一致箇所検出手段１０３により、構造情報１０６とその変換箇所を示す変換位置情報１１０とを入力し、構造情報１０６のうち、変換位置情報１１０が示す変換箇所を検出対象から除外して、構造情報１０６とテンプレートとの一致箇所を検出し、置換手段１０４により、構造情報１０６のうちの一致箇所をテンプレートで置換して置換後構造情報１１２を出力し、変換手段１０５により、変換規則１１３にしたがい、置換後構造情報１１２と文字列情報１０７を変換して、第１の出力データ１０８と、第２の出力データ１０９を出力する。【選択図】  図１
2005100057.tif 000002
【特許請求の範囲】
【請求項１】
構造情報と文字列情報とを有する構造化文書を変換する文書変換装置であって、
特定のパターンを有する構造情報をテンプレートとして蓄積するテンプレート蓄積手段と、
前記構造化文書を構成する構造情報と、該構造情報の変換箇所を示す変換位置情報とを入力し、前記構造情報のうち、前記変換位置情報が示す変換箇所を検出対象から除外するようにして、前記構造情報と前記テンプレートとの一致箇所を検出するテンプレート一致箇所検出手段と、
前記構造化文書を構成する構造情報と前記一致箇所を示す一致箇所情報とを入力し、前記構造情報のうち、前記一致箇所情報が示す一致箇所を前記テンプレートで置換し、置換後構造情報を出力するテンプレート置換手段と、
前記構造化文書を構成する文字列情報と、前記置換後構造情報と、前記構造化文書を構成する構造情報および文字列情報を変換するための変換規則とを入力し、該変換規則にしたがい、その入力した前記置換後構造情報と前記文字列情報とを変換し、変換後構造情報と変換後文字列情報とを出力する変換手段とを有することを特徴とする文書変換装置。
【請求項２】
前記変換規則が変換位置識別子を含み、
前記変換規則から前記変換位置識別子を前記変換位置情報として検出し、その検出した変換位置識別子を前記一致箇所検出手段に入力する変換位置検出手段を更に有することを特徴とする請求項１記載の文書変換装置。
【請求項３】
前記変換規則が変換位置識別子を含み、
前記変換規則に含まれる変換位置識別子を蓄積する変換規則蓄積手段と、
該変換規則蓄積手段に蓄積されている前記変換位置識別子の利用頻度に応じて、前記変換位置情報を検出する変換位置検出手段とを更に有することを特徴とする請求項１記載の文書変換装置。
【請求項４】
前記変換規則が変換位置識別子を含み、
前記変換規則に含まれる変換位置識別子を蓄積する変換規則蓄積手段と、
該変換規則蓄積手段に蓄積されている前記変換位置識別子を前記変換位置情報として検出する変換位置検出手段とを更に有することを特徴とする請求項１記載の文書変換装置。
【請求項５】
前記変換規則が変換後構造化文書を含み、
前記変換規則から前記変換後構造化文書の構造情報を抽出し、前記テンプレートとして前記テンプレート蓄積手段に蓄積させるテンプレート発見手段を更に有することを特徴とする請求項１〜４のいずれか一項記載の文書変換装置。
【請求項６】
前記テンプレート発見手段により発見された前記テンプレートの蓄積要否を判断するテンプレート検証手段を更に有し、
該テンプレート検証手段の判断に応じて、前記テンプレート発見手段が前記テンプレートを蓄積することを特徴とする請求項５記載の文書変換装置。
【請求項７】
前記テンプレート検証手段が、前記テンプレート発見手段により発見された前記テンプレートと同型のテンプレートの前記テンプレート蓄積手段における蓄積有無により、前記蓄積要否を判断することを特徴とする請求項６記載の文書変換装置。
【請求項８】
前記テンプレート一致箇所検出手段が前記変換後構造情報と前記テンプレートとの一致箇所を検出し、
前記テンプレート置換手段が、前記テンプレート一致箇所検出手段から出力される前記一致箇所情報が示す一致箇所を前記テンプレートで置換することを特徴とする請求項１〜７のいずれか一項記載の文書変換装置。
【請求項９】
構造情報と文字列情報とを有する構造化文書を変換する文書変換装置であって、
特定のパターンを有する構造情報をテンプレートとして蓄積するテンプレート蓄積手段と、
変換後構造化文書を含み、前記構造化文書を構成する構造情報および文字列情報を変換するための変換規則を入力し、該変換規則から前記変換後構造化文書の構造情報を抽出して、その構造情報と一致する前記テンプレートを検出し、前記構造情報を前記検出されたテンプレートで置換した置換後変換規則を出力する変換規則テンプレート置換手段と、
前記構造化文書を構成する構造情報および文字列情報と、前記置換後変換規則とを入力し、該置換後変換規則にしたがい、その入力した前記構造情報と文字列情報を変換し、変換後構造情報と変換後文字列情報とを出力する変換手段とを有することを特徴とする文書変換装置。
【請求項１０】
前記変換規則テンプレート置換手段が、前記変換後構造化文書の構造情報との差分が最も小さい近似テンプレートを検出し、前記差分を示す差分情報を抽出し、前記置換後変換規則を前記差分情報と前記近似テンプレートとに置換することを特徴とする請求項９記載の文書変換装置。
【請求項１１】
構造情報と文字列情報とを有する構造化文書を変換する文書変換装置であって、
特定のパターンを有する構造情報をテンプレートとして蓄積するテンプレート蓄積手段と、
前記構造化文書を構成する構造情報と、該構造情報の変換箇所を示す変換位置情報とを入力し、前記構造情報のうち、前記変換位置情報が示す変換箇所を検出対象から除外するようにして、前記構造情報と前記テンプレートとの一致箇所を検出するテンプレート一致箇所検出手段と、
前記構造化文書を構成する構造情報と前記一致箇所を示す一致箇所情報とを入力し、前記構造情報のうち、前記一致箇所情報が示す一致箇所を前記テンプレートで置換し、置換後構造情報を出力するテンプレート置換手段と、
変換後構造化文書を含み、前記構造化文書を構成する構造情報および文字列情報を変換するための変換規則を入力し、該変換規則から前記変換後構造化文書の構造情報を抽出して、その構造情報と一致する前記テンプレートを検出し、前記構造情報を前記検出されたテンプレートで置換した置換後変換規則を出力する変換規則テンプレート置換手段と、
前記構造化文書を構成する文字列情報、前記置換後構造情報および前記置換後変換規則を入力し、該置換後変換規則にしたがい、その入力した前記置換後構造情報および文字列情報を変換し、変換後構造情報と変換後文字列情報を出力する変換手段とを有することを特徴とする文書変換装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、構造化文書の変換を行う文書変換装置に関する。
【背景技術】
【０００２】
ＸＭＬ(EXtensible Markup Language)文書をはじめとする構造化文書は構造情報と文字列情報とを記述する必要があるため、一般にデータサイズ（データボリューム）が大きいという特徴がある。そのため、近年では、構造化文書を記憶させるディスクスペースの有効利用や、ネットワークリソースの有効利用を目的として、構造化文書を圧縮する技術が注目を浴びている。
【０００３】
特に、構造化文書を構造情報と文字列情報とに分離して圧縮する技術は、その構造情報に着目することによって、文字列情報をも含む場合と比較すると、出現するパターンが少なくなることから、構造化文書をただ単にＬＺ７７等の技術で圧縮するよりも圧縮率の向上を図ることができるとされている（ＬＺ７７について詳しくは、Jacob Ziv,Abraham Lempel:A Universal Algorithm for Sequential Data Compression.IEEE Transactions on Information Theory 23(3):337-343(1977)を参照）。
【０００４】
ここで、特許文献１には、予め与えられた構造指定情報を用いて構造化データの内部表現データを構造情報と文字列情報とに分離し、それぞれを独立に圧縮する方法が開示されている。この圧縮方法では、構造情報に着目して圧縮を行い、圧縮率の向上が図られている。そのほか、構造化文書は前処理として、構造情報の妥当性検証（バリデーションチェック）および構文解析（パージング）が行われるが、構造情報と文字列情報を独立に圧縮しているため、文字列情報を解凍（復元）することなく、構造情報を解凍（復元）すれば妥当性検証および構文解析が行える、とされている。
【０００５】
また、非特許文献１には、ＸＭＬ文書中に出現する部分的な構造を再利用することでＸＭＬ文書を圧縮する方法が開示されている。この圧縮方法では、構造化文書を構造情報、ノードタイプ情報、テキスト情報の３つに分離したのち、そのそれぞれをＬＺ７７等のような一般的な圧縮アルゴリズムで圧縮する。この非特許文献１によると、特許文献１に記載の技術と同様、構造情報に着目して圧縮することから、圧縮率の向上が図られる。
上述のとおり、従来技術のようにして、構造化文書を構造情報と文字列情報とに分離して圧縮すると、圧縮率の向上が図られ、妥当性検証および構文解析が文字列情報を解凍することなく行えることとなる。
【０００６】
【特許文献１】特開２００３−４４４５９号公報
【非特許文献１】Hartmut Liefke and Dan Suciu.: “XMill: An Efficient Compressor for XML Data”, In proceedings of ACM SIGMOD International Conference on Management of Data, 2000
【発明の開示】
【発明が解決しようとする課題】
【０００７】
一方、構造化文書を小さな表示装置しか持たないモバイル端末装置（例えば、携帯電話機等）で利用することを考えると、構造化文書をモバイル端末装置に合わせて変換して利用することが考えられる（例：ＸＨＴＭＬ文書をモバイル端末向けにｃ−ＨＴＭＬ(Compact Hyper Text Markup Language)化する。なお、ｃ−HTMLについて詳しくは、Compact HTML for small Information Appliance ,http://www.w3.org/TR/1998/NOTE-Compact HTML-19980209/  参照）。
しかし、構造化文書を変換するには、構造情報と文字列情報とをともに変換する必要がある。その変換に先立ち、上述した従来技術のようにして構造化文書がＬＺ７７等のアルゴリズムで圧縮されていると、その構造化文書を変換するときに、構造情報と文字列情報をすべて解凍しなければならなくなるから、変換処理に要する時間やメモリ量がともに増加してしまうという問題がある。
【０００８】
そこで、本発明は上記課題を解決するためになされたもので、構造化文書の圧縮および変換をともに行い、その変換の際には構造情報のすべてを解凍しなくてもよく、圧縮および変換を効率よく行える文書変換装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記課題を解決するため、本発明は、構造情報と文字列情報とを有する構造化文書を変換する文書変換装置であって、特定のパターンを有する構造情報をテンプレートとして蓄積するテンプレート蓄積手段と、構造化文書を構成する構造情報と、その構造情報の変換箇所を示す変換位置情報とを入力し、構造情報のうち、変換位置情報が示す変換箇所を検出対象から除外するようにして、構造情報とテンプレートとの一致箇所を検出するテンプレート一致箇所検出手段と、構造化文書を構成する構造情報と一致箇所を示す一致箇所情報とを入力し、構造情報のうち、一致箇所情報が示す一致箇所をテンプレートで置換し、置換後構造情報を出力するテンプレート置換手段と、構造化文書を構成する文字列情報と置換後構造情報と、構造化文書を構成する構造情報および文字列情報を変換するための変換規則とを入力し、その変換規則にしたがい、その入力した置換後構造情報と文字列情報とを変換し、変換後構造情報と変換後文字列情報とを出力する変換手段とを有する文書変換装置を特徴とする。
この文書変換装置は、変換位置情報が示す変換箇所を除外して、構造情報のうちの一致箇所をテンプレートで置換するため、変換手段において、構造情報を置換前に戻す処理が必要とされない。
【００１０】
また、文書変換装置は、変換規則が変換位置識別子を含み、変換規則から変換位置識別子を変換位置情報として検出し、その検出した変換位置識別子を一致箇所検出手段に入力する変換位置検出手段を更に有することが好ましい。
この構成によれば、入力された変換規則から得た変換位置情報を用いて一致箇所を検出することができる。
【００１１】
さらに、文書変換装置は、変換規則が変換位置識別子を含み、変換規則に含まれる変換位置識別子を蓄積する変換規則蓄積手段と、その変換規則蓄積手段に蓄積されている変換位置識別子の利用頻度に応じて、変換位置情報を検出する変換位置検出手段とを更に有する文書変換装置とすることもできる。
また、変換規則が変換位置識別子を含み、変換規則に含まれる変換位置識別子を蓄積する変換規則蓄積手段と、その変換規則蓄積手段に蓄積されている変換位置識別子を変換位置情報として検出する変換位置検出手段とを更に有する文書変換装置としてもよい。
いずれの文書変換装置についても、変換手段に変換規則を入力する前に変換位置情報を一致箇所検出手段に入力することができる。
【００１２】
上記いずれの文書変換装置でも、変換規則が変換後構造化文書を含み、変換規則から変換後構造化文書の構造情報を抽出し、テンプレートとしてテンプレート蓄積手段に蓄積させるテンプレート発見手段を更に有することが好ましい。
これにより、変換規則が入力されるたびに、発見手段がテンプレートを発見して蓄積手段に新たなテンプレートを自動的に加え、蓄積手段を更新することができる。
【００１３】
この文書変換装置では、テンプレート発見手段により発見されたテンプレートの蓄積要否を判断するテンプレート検証手段を更に有し、そのテンプレート検証手段の判断に応じて、テンプレート発見手段がテンプレートを蓄積することが好ましい。
この文書変換装置は、蓄積する必要のないテンプレートを蓄積対象から除外することができる。
【００１４】
また、この文書変換装置の場合、テンプレート検証手段が、テンプレート発見手段により発見されたテンプレートと同型のテンプレートのテンプレート蓄積手段における蓄積有無により、蓄積要否を判断することができる。
これにより、蓄積済みのテンプレートと同型のテンプレートを蓄積せずに除外することができる。
【００１５】
さらに、上記いずれの文書変換装置でも、テンプレート一致箇所検出手段が変換後構造情報とテンプレートとの一致箇所を検出し、テンプレート置換手段が、テンプレート一致箇所検出手段から出力される一致箇所情報が示す一致箇所をテンプレートで置換することが好ましい。
この文書変換装置は、変換後構造情報にテンプレートを再度適用することで、データ量をさらに削減し、圧縮することができる。
【００１６】
そして、本発明は、構造情報と文字列情報とを有する構造化文書を変換する文書変換装置であって、特定のパターンを有する構造情報をテンプレートとして蓄積するテンプレート蓄積手段と、変換後構造化文書を含み、構造化文書を構成する構造情報および文字列情報を変換するための変換規則を入力し、その変換規則から変換後構造化文書の構造情報を抽出して、その構造情報と一致するテンプレートを検出し、構造情報を検出されたテンプレートで置換した置換後変換規則を出力する変換規則テンプレート置換手段と、構造化文書を構成する構造情報および文字列情報と、置換後変換規則とを入力し、その置換後変換規則にしたがい、その入力した構造情報と文字列情報を変換し、変換後構造情報と変換後文字列情報とを出力する変換手段とを有する文書変換装置を提供する。
この文書変換装置は、置換後変換規則の変換後構造化文書の構造情報がすでにテンプレートで置換されているため、変換手段が置換後変換規則を用いて変換を行うと、そのテンプレートが自動的に適用され、変換とともに圧縮が行われるようになる。
【００１７】
また、変換規則テンプレート置換手段が、変換後構造化文書の構造情報との差分が最も小さい近似テンプレートを検出し、差分を示す差分情報を抽出し、置換後変換規則を差分情報と近似テンプレートとに置換する文書変換装置とすることもできる。
このような近似テンプレートを用いることにより、テンプレートを効率よく利用することが可能となる。
【００１８】
さらに、本発明は、構造情報と文字列情報とを有する構造化文書を変換する文書変換装置であって、特定のパターンを有する構造情報をテンプレートとして蓄積するテンプレート蓄積手段と、構造化文書を構成する構造情報と、その構造情報の変換箇所を示す変換位置情報とを入力し、構造情報のうち、変換位置情報が示す変換箇所を検出対象から除外するようにして、構造情報とテンプレートとの一致箇所を検出するテンプレート一致箇所検出手段と、構造化文書を構成する構造情報と一致箇所を示す一致箇所情報とを入力し、構造情報のうち、一致箇所情報が示す一致箇所をテンプレートで置換し、置換後構造情報を出力するテンプレート置換手段と、変換後構造化文書を含み、構造化文書を構成する構造情報および文字列情報を変換するための変換規則を入力し、その変換規則から変換後構造化文書の構造情報を抽出して、その構造情報と一致するテンプレートを検出し、構造情報を検出されたテンプレートで置換した置換後変換規則を出力する変換規則テンプレート置換手段と、構造化文書を構成する文字列情報、置換後構造情報および置換後変換規則を入力し、その置換後変換規則にしたがい、その入力した置換後構造情報および文字列情報を変換し、変換後構造情報と変換後文字列情報を出力する変換手段とを有する文書変換装置を提供する。
この文書変換装置では、蓄積手段に蓄積されているテンプレートは構造情報を置換するためとともに、変換規則を置換するためのテンプレートとして利用できるようになる。
【発明の効果】
【００１９】
本発明による文書変換装置によれば、ＸＭＬ文書等の構造化文書の変換と圧縮をともに行い、構造情報を解凍することなく、圧縮および変換を効率よく行い、文書変換の処理速度を向上することができる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明に係る文書変換装置の実施の形態について、添付図面を用いて詳細に説明する。
（第１の実施の形態）
図１は、本発明の第１の実施の形態にかかる文書変換装置１０１の構成を示すブロック図である。文書変換装置１０１は、テンプレート蓄積手段（以下「蓄積手段」という）１０２と、テンプレート一致箇所検出手段（以下「一致箇所検出手段」という）１０３と、テンプレート置換手段（以下「置換手段」という）１０４および変換手段１０５を有している。この文書変換装置１０１は、構造化文書１００の構造情報１０６と文字列情報１０７とを入力し、第１の出力データ１０８と第２の出力データ１０９とを出力するように構成されている。
【００２１】
ここで、入力される構造化文書１００について説明する。図２は構造化文書１００の一例となるＸＭＬ文書１０を示す図である。構造化文書１００は、ＸＭＬ文書１０のほか、ＸＭＬ文書１０と同様に構造情報と文字列情報とを有し、その両者が分離可能であれば入力の対象とすることができる。図３は、図２に記載されているＸＭＬ文書１０を既知の手法（例えばhttp://xml.apache.org/xerces2-j/ において示されるXercesなど）によって解析し、コンピュータの内部利用に適した形式に変換したデータ構造１１を示している。
【００２２】
図３において、データ構造１１はノード（頂点ともいう）３０１〜３２２を有し、各ノードが矢印で結ばれている。各矢印はノード間の参照関係を示している。図面において、ノードからみて上方向に向かう矢印は参照先が親ノードであるという意味（親参照）を示している。また、ノードからみて下方向に向かう矢印は参照先が子ノードであるという意味（子参照）を示している。さらに、ノードからみて左方向に向かう矢印は参照先が前兄弟ノードであるという意味（前兄弟参照）を示し、同じく右方向に向かう矢印は参照先が次兄弟ノードであるという意味（次兄弟参照）を示している。
【００２３】
各ノード３０１〜３２３にはノードタイプ情報及びテキスト情報が記述されている。ノードタイプ（型ともいう）情報はノードの左側に記述されていて、“Ｅ”であれば、そのノードがエレメント（要素）ノードであることを示し、“Ｔ”であれば、そのノードがテキストノードであることを示している。また、テキスト情報はノードの右側に記述されている。ノードタイプ情報が“Ｅ”であるときは、エレメント名が記述され、ノードタイプ情報が“Ｔ”であるときは、文字列が記述されている。例えば、ノード３０２は、左側のノードタイプ情報が“Ｅ”であるから、右側がエレメント名“Ｂ”となる。一方、ノード３０７は、左側のノードタイプ情報が“Ｔ”であるから、右側が文字列“ａｂｃｄ”となる。
【００２４】
また、データ構造１１は、構造情報と、ノードタイプ情報やテキスト情報を含む情報（以下「文字列情報」という）とを分離して管理するため、そのそれぞれを図４（ａ）、図４（ｂ）のように表現することも可能である。図４（ａ）はデータ構造１１から分離された構造情報１２を示し、各ノードがどのように接続しているか（各ノードの接続関係）を示している。一方、図４（ｂ）は、各ノードが有する文字列情報（ノードタイプ情報またはテキスト情報）を列記したテーブル１３を示している。
本発明の第１の実施の形態にかかる文書変換装置１０１は、構造化文書１００を入力するにあたり、構造化文書１００が図４（ａ）に示す構造情報１２といった構造情報１０６と、図４（ｂ）に示すテーブル１３に列記された文字列情報といった文字列情報１０７とに分離された状態で入力する。
【００２５】
蓄積手段１０２は構造化文書における構造情報の予め定めておいた特定のパターン、例えば、頻繁に出現することがわかっているパターンをテンプレートとして蓄積している。ここで、テンプレートの構成例を図５（ａ）に示す。図５（ａ）に示すテンプレート５００は、テンプレートＩＤ５０１と、接続情報５０２およびパターン構造情報５０３を有している。
テンプレートＩＤ５０１は、テンプレート識別子（識別ＩＤ）を示しており、蓄積手段１０２に複数のテンプレートが蓄積されている際に、各テンプレートを一意に識別するために用いられる。接続情報５０２はテンプレートの外部インタフェースを示しており、そのテンプレートが指し示すパターンが他のテンプレートや他のノードと、どのように接続可能なのかを示す情報が設定されている。パターン構造情報５０３はテンプレート５００の構造情報を示していて、複数のノードとそれらの相互参照とを有している。
【００２６】
図５（ｂ）は、テンプレート５００の具体的な一例となる第１のテンプレート５１５の構成を示すブロック図である。テンプレートＩＤ５０４には、具体的な値として“１”が設定されている。パターン構造情報５０５は、５つのノード５０６〜５１０と、それらの相互参照とを有している。各ノードの相互参照は、図５（ｂ）において、矢印で示されている。相互参照の種類は矢印に対し、親参照はｐ、子参照はｃ、次兄弟参照はｎｓ、前兄弟参照はｐｓとして記述されている。また、このパターン構造情報５０５で示された構造情報は、５つの端点を有しているが、そのうち、４つの端点が外部インタフェースとして許されている。それは「○」で記述されている。逆に、「×」で記述された端点は、外部インタフェースとして許されていない。つまり、ノード５０６の親参照、ノード５０８、ノード５０９、ノード５１０の子参照が外部インタフェースとなる。接続情報５１１は、これらの外部インタフェースをノードと相互参照の種類ごとに列挙して記述している。
【００２７】
一致箇所検出手段１０３は、構造情報１０６と、構造情報１０６における変換手段１０５により変換される箇所（変換箇所）を示す変換位置情報１１０とを入力し、その変換位置情報１１０が示す変換箇所を検出対象から除外するように（検出対象に含まないように）して、構造情報１０６と蓄積手段１０２に蓄積されたテンプレートとが一致する箇所（一致箇所）を検出する。
図１に示したように、文書変換装置１０１では、変換位置情報１１０が内部に予め備えられている。ただし、文書変換装置１０１は、変換位置情報１１０を外部から入力して、取得するようにしてもよい。また、変換位置情報１１０を蓄積する変換位置蓄積手段（図示せず）を設け、一致箇所検出手段１０３がその変換位置蓄積手段から変換位置情報を取得するようにしてもよい。
【００２８】
ここで、変換位置情報１１０として、例えば、図４（ａ）に示した構造情報１２における“ノード３１２”を入力するとする。一致箇所検出手段１０３における一致箇所検出手順は、例えば図２３に示す手順（後述する）によって行う。図２３に示すとおり、一致箇所検出手段１０３は、入力する変換位置情報１１０が示す“ノード３１２”を一致箇所の検出対象から除外し、検索対象に含めないようにして、構造情報１２について、蓄積手段１０２に蓄積されたテンプレートとの一致箇所を検出する。
【００２９】
そして、蓄積手段１０２には、図５（ｂ）に示す第１のテンプレート５１５が蓄積されているとする。すると、構造情報１２のうち、ノード３０２，３０３，３０４，３０５，３０６（３０２〜３０６）が示す構造情報が第１のテンプレート５１５と一致しているため、一致箇所検出手段１０３はノード３０２〜ノード３０６を、構造情報１２と第１のテンプレート５１５との一致箇所を示す一致箇所情報１１１として出力する。同様に、ノード３１０，３１１，３１５，３１６，３１７が示す構造情報も、第１のテンプレート５１５と一致しているため、ノード３１０，３１１，３１５，３１６，３１７も、一致箇所情報１１１として出力される。ただし、ノード３０８，３０９，３１２，３１３，３１４が示す構造情報も第１のテンプレート５１５と一致しているが、“ノード３１２”が変換位置情報１１０として入力されているため、ノード３０８，３０９，３１２，３１３，３１４は、検出対象から除外され、一致箇所情報１１１には含まれない。
【００３０】
また、変換位置情報１１０として、複数のノードが入力される場合も、一致箇所検出手段１０３は上記同様にして一致箇所を検出する。例えば、図４（ｂ）において、変換位置情報１１０としてノード３１２に加えて、“ノード３１５”が入力されるとき、一致箇所検出手段１０３は、ノード３１２，３１５を一致箇所の検出対象から除外して一致箇所を検出する。そのため、蓄積手段１０２に蓄積されているテンプレートが第１のテンプレート５１５のみであるとすると、一致箇所情報１１１として出力される情報は、ノード３０２〜３０６のみとなる。
なお、一致箇所検出手段１０３は、変換位置情報１１０として、構造情報と文字列情報とを用いて、構造情報における変換位置の対象を評価する評価式（例えば、Xpath式）を入力しても良い。その場合、一致箇所検出手段１０３は、文字列情報１０７を入力し、入力される変換位置情報１１０が示す評価式にしたがい、構造情報１２における変換位置の対象を評価することとなる。
【００３１】
置換手段１０４は構造情報１０６と一致箇所情報１１１とを入力し、その構造情報１０６のうち、一致箇所情報１１１が示す一致箇所をテンプレートで置換し、そのテンプレートによる置換後の構造情報（置換後構造情報）１１２を出力する。
ここで、テンプレートで置換する際のテンプレートの呼び出しとなるテンプレート実体６００を図６に示す。図６に示すとおり、テンプレート実体６００は、採用テンプレートＩＤ６０１、実体ＩＤ６０２、実体接続情報６０３および実体ノード情報６０４を有するオブジェクトとして呼び出される。採用テンプレートＩＤ６０１は、蓄積手段１０２に蓄積されているテンプレートのうち、置換する際に採用したテンプレートを指定するための情報が設定されている。
【００３２】
図５（ａ）に示すとおり、テンプレート５００はテンプレートＩＤ５０１によって一意に特定できるため、採用されたテンプレートは図６に示す採用テンプレートＩＤ６０１により、確実に指定することができる。同じく、図６に示す実体ＩＤ６０２はテンプレート実体６００を一意に特定するためのＩＤである。また同じく、図６に示す実体接続情報６０３は、テンプレート実体６００がどのノードと接続されるかの接続関係を指定する情報が設定されている。図５（ａ）に示すとおり、テンプレート５００では、接続情報５０２により外部インタフェースが記述されているが、実体接続情報６０３には、それぞれの外部インタフェースがどのノードと接続されるかが記述されている。外部インタフェースが他のテンプレート内のノードと接続されていることを示すときは、そのテンプレート実体を示す実体ＩＤ６０２とそのテンプレート内のノードを結び付けて記述する。実体ノード情報６０４はテンプレート内の各ノードがどの文字列情報と結び付けられているかを指定する。図５（ａ）に示すとおり、テンプレート５００にはパターン構造情報５０３が記述されており、パターン構造情報５０３内の各ノードがどの文字列情報と結び付けられているかが、実体ノード情報６０４によって記述されている。図４（ｂ）に示すテーブル１３のように、文字列情報は各ノードに付された番号（ノード番号，図４（ｂ）では３０１〜３２３）と、ノードタイプ情報およびテキスト情報とを有し、そのノード番号によって一意に特定できるので、実体ノード情報６０４にはノード番号が記述されている。
【００３３】
ここで、置換手段１０４により、置換した結果を図７に示す。図７は置換手段１０４により置換された置換後構造情報３００の構成を示すブロック図である。置換後構造情報３００は、置換手段１０４から出力される置換後構造情報１１２の具体的な一例となるもので、テンプレート実体６００ａ，６００ｂを２つ有し、両者は実体ＩＤ６０２（前者が実体ＩＤ“１”、後者は実体ＩＤ“２”）によって、相互に識別可能になっている。各テンプレート実体６００ａ，６００ｂはいずれも採用テンプレートＩＤに“１”が設定されているので、図５（ｂ）に示した第１のテンプレート５１５が採用されている。それぞれの実体接続情報６０３には、図７において示される順に、上から第１のテンプレート５１５の接続情報５１１と対応する情報が設定されている。なお、本実施の形態では、各頂点からの参照を一意に識別するため、（頂点ＩＤ，相互参照の種類）と表示し、例えば頂点５０８の子参照を（５０８，ｃ）と表示している。
そして、テンプレート実体６００ａでは、（５０６，ｐ）にノード３０１が接続され、（５０８，ｃ）にノード３０７が接続されることを示す情報が設定されている。また、（５０９，ｃ）にノード３０８が接続され、（５１０，ｃ）に２−５０６が接続されることを示す情報が設定されている。なお、（２−５０６，ｐ）はテンプレート実体６００ｂ（実体ＩＤ＝“２”）のテンプレート内におけるノード５０６の親参照ｐを示している。テンプレート実体６００ｂにおいては、第１のテンプレート５１５における（５０６，ｐ）に（１−５１０，ｃ）が接続され、（５０８，ｃ）にノード３２１が接続されることを示す情報が設定されている。また、（５０９，ｃ）にノード３２２が接続され、（５１０，ｃ）にノード３２３が接続されることを示す情報が設定されている。
【００３４】
実体ノード情報６０４には、図７において示される順に、上から第１のテンプレート５１５におけるパターン構造情報５０５内の各ノード５０６〜５１０と左上から右下に向かって対応する情報が設定されている。テンプレート実体６００ａでは、ノード５０６，５０７，５０８，５０９，５１０（５０６〜５１０）に、ノード３０２，３０３，３０４，３０５，３０６がそれぞれ対応することを示す情報が設定されている。テンプレート実体６００ｂでは、ノード５０６〜５１０に、ノード３１０，３１１，３１５，３１６，３１７がそれぞれ対応することを示す情報が設定されている。このように、図７に示した置換後構造情報３００は、図４（ａ）に示した構造情報１２と同じ意味をなしている。また、テンプレートを適用することにより構造情報の再利用が行われているため、構造情報１２よりもデータ量が少なく、圧縮されている。
【００３５】
構造情報１２におけるノード３０８以降の構造情報(３０８，３０９，３１２，３１３，３１４,３１８，３１９，３２０で形成される構造情報)は、一致箇所検出手段１０３による一致箇所の検出がノード３１２を除外するようにして行われているため、一致箇所情報１１１には反映されていない。そのため、置換手段１０４により、テンプレートで置換されてなく構造情報１２の内容がそのまま承継されている。
そして、変換手段１０５は文字列情報１０７と、置換後構造情報１１２と、文字列情報１０７および置換後構造情報１１２を変換するための変換規則１１３を入力し、その変換規則１１３にしたがい、文字列情報１０７と置換後構造情報１１２とを変換する。また、変換手段１０５は変換後の置換後構造情報（以下「変換後構造情報」という）を第１の出力データ１０８として出力し、変換後の文字列情報（以下「変換後文字列情報」という）を第２の出力データ１０９として出力する。
【００３６】
変換規則１１３は変換手段１０５の処理内容を記述したもので、変換対象の位置を示す変換対象位置と、その変換対象位置で示されたノードを含む構造情報が、変換後にどういった構造化文書になるかを示す変換後構造化文書（構造情報と文字列情報で構成される）とにより構成されている。この変換規則１１３は、文書変換装置１０１の外部から入力してもよいし、変換手段１０５に予め指定しておいてもよい。
ここで、図１２は変換規則１１３の具体的な一例となる変換規則１２０の構成を示す図である。図１２に示した変換規則１２０はＸＭＬで記述されており、“３１２”を変換対象位置とし、その変換対象位置が示すノード（ノード３１２）以降の構造情報を<transform match=“312”>と</transform>で囲まれた構造化文書１２０ａに変換せよ、という意味の規則が含まれている。
【００３７】
この変換規則１２０にしたがい、変換手段１０５により、変換された置換後構造情報、すなわち変換後構造情報３５０を図８に示し、変換された文字列情報、すなわち、変換後文字列情報を図１３にそれぞれ示す。図８は変換後構造情報３５０の構成を示すブロック図、図１３は変換後文字列情報を列記したテーブル２３を示す図である。図８に示すとおり、図４（ａ）に示した構造情報１２におけるノード３１２以降（３１２〜３１８）の構造情報が変換後構造情報３５０では、ノード８０１以降（８０１〜８０７）の構造情報に変換されている。また、図１３に示すとおり、構造情報１２におけるノード３１２，３１８の文字列情報が、変換後構造情報３５０では、ノード８０１，８０２，８０３，８０４，８０５，８０６，８０７の文字列情報にそれぞれ変換されている（ノード３１２，３１８の文字列情報の代わりにノード８０１〜８０７の文字列情報が設定されている）。そして、変換後構造情報３５０と、テーブル２３を構成する文字列情報とが、それぞれ第１の出力データ１０８と、第２の出力データ１０９として出力される。
【００３８】
ここで、変換規則１１３の別の一例となる変換規則１２１を図１６に示す。図１６は変換規則１２１を示す図である。この変換規則１２１は、ＸＳＬＴ（extensible Stylesheet language-transformation）で記述されているが、変換規則１２０と同様、変換対象位置と変換後構造化文書とにより構成されている。そして、要素１２１ａに示される“/A/B/D/F”が変換対象位置を示しており、<xsl:template match=“/A/B/D/F”>と</xsl:template>で囲まれた<J>以下の構造化文書１２１ｂが変換後構造化文書となる。この例では、“/A/B/D/F”で示される箇所を＜ｊ＞以下の構造化文書に変換せよ、という意味の規則が記述されている。変換対象位置は構造情報と文字列情報とを用いて対象を探索していく評価式の標準技術であるXPathで記述されている。この例では、上記“/A/B/D/F”が意味する変換対象位置は、ルートノード”／”の子ノードであるＡのさらに子ノードであるＢのさらに子ノードであるＤのさらに子ノードであるＦを示している。そのため、このXPath式を評価するためには自ノードの子ノードに何が存在するのか、さらにそのノードはどういう文字列情報をもっているのかを両方とも知る必要がある。したがって、この場合、変換手段１０５は構造情報１０６と文字列情報１０７を用いて変換対象位置を決定することになる。
【００３９】
ここで、仮に、変換位置情報が示す変換箇所を含めてテンプレートによる置換を行い、圧縮を行うとすると、置換後の変換箇所は、変換手段１０５により、変換前とは別の構造情報を有する構造化文書に変換されてしまうおそれがある。すると、変換後の構造情報は置換に用いたテンプレートと整合がとれなくなってしまうので、変換手段１０５において置換された変換箇所を置換前の元の構造情報に戻す処理が必要となり、圧縮および変換処理の効率が悪化する。しかし、本実施の形態における文書変換装置１０１のように、変換箇所を除外して置換を行うことにより、テンプレートで置換された構造情報を解凍することなく変換を行えるので、圧縮および変換が効率よく行われる。
【００４０】
ところで、図１に示した文書変換装置１０１は、蓄積手段１０２から変換手段１０５までが一体化された単一の装置として構成されているが、本発明による文書変換装置は、必ずしも単一の装置として実現される必要はなく、図示しない通信手段により、複数の装置を接続して実現することも可能である。ここで、図２６は、複数の装置から構成される文書変換装置の構成を示すブロック図である。図２６に示す通り、文書変換装置は蓄積手段２６０２、一致箇所検出手段２６０３、置換手段２６０４から構成される第１の文書変換装置２６０１と、変換手段２６０５から構成される第２の文書変換装置２６０６とに分離されている。第１の文書変換装置２６０１は、構造化文書１００を構成する構造情報２６０７を入力して置換後構造情報２６１３を出力し、それを第２の文書変換装置２６０６に伝達（入力）する。第２の文書変換装置２６０６は置換後構造情報２６１３と、構造化文書１００を構成する文字列情報２６０８および変換規則２６１４を入力して、変換後構造情報を第１の出力データ２６０９として出力し、変換後文字列情報を第２の出力データ２６１０として出力する。
【００４１】
一方、文書変換装置１０１では、図１における第１の出力データ１０８を蓄積手段１０２に蓄積されたテンプレートにより置換することができる。ここで、蓄積手段１０２に図９に示す第２のテンプレート９００が蓄積されているとする。図９は、第２のテンプレート９００の構成を示すブロック図である。図９に示す第２のテンプレート９００は、テンプレートＩＤ９０１と、接続情報９０７と、パターン構造情報９０２とを有している。テンプレートＩＤ９０１には“２”が設定され、接続情報９０７には、(９０３,ｐ),(９０３,ｎｓ),(９０４,ｃ),(９０５,ｃ),(９０６,ｃ)が設定されている。また、パターン構造情報９０２には、ノード９０３，９０４，９０５，９０６が接続されている構造情報が設定されている。
【００４２】
そして、文書変換装置１０１では、一致箇所検出手段１０３に変換後構造情報３５０（図８参照）を入力するようにして、その一致箇所検出手段１０３により、変換後構造情報３５０を構成するノード８０１〜８０４が第２のテンプレート９００と一致することを検出し、その検出結果を示す一致箇所情報１１１を出力する。また、置換手段１０４が、一致箇所情報１１１が示すノード８０１〜８０４を第２のテンプレート９００で置換する。図１０はその置換後における変換後構造情報３６０の構成を示すブロック図である。図１０に示すとおり、ノード８０１〜８０４に第２のテンプレート９００が採用されている。このように、変換後構造情報にテンプレートを再度適用することで、データ量をさらに削減し、圧縮することができる。
【００４３】
また、文書変換装置は、図２４に示すように、テンプレート発見手段（以下「発見手段」という）２４０１を設けた文書変換装置２４００とすることもできる。この文書変換装置２４００は、一致箇所検出手段１０３、置換手段１０４、変換手段１０５とともに、蓄積手段１０２と同様の蓄積手段２４０２と、発見手段２４０１とを有している。そして、文書変換装置２４００では、発見手段２４０１が、変換後構造化文書を含む変換規則２４０３から、その変換後構造化文書の構造情報（図１２の場合であれば、構造情報１２０ｂ）を抽出し、それをテンプレートとして、蓄積手段２４０２に蓄積する。これにより、文書変換装置２４００では、変換規則２４０３が入力されるたびに、発見手段２４０１がテンプレートを発見して蓄積手段２４０２に新たなテンプレートを加え、蓄積手段２４０２を更新することができる。
【００４４】
さらに、蓄積手段２４０２にテンプレートを蓄積する際に、蓄積しようとするテンプレートに蓄積時のタイムスタンプ（更新日時）を付加し、置換手段１０４がテンプレートを利用するたびに、そのタイムスタンプを変換時のタイムスタンプに更新するようにしてもよい。こうすると、ＬＲＵ(Least Recently Used)アルゴリズム等で蓄積手段２４０２を動的に管理することができ、蓄積手段２４０２のために必要なメモリキャッシュの容量を小さくすることができる。
【００４５】
さらにまた、文書変換装置は図２５に示す文書変換装置２５００のように、テンプレート検証手段（以下「検証手段」という）２５０１を設けてもよい。この文書変換装置２５００は文書変換装置２４００と比較して、検証手段２５０１を有する点で相違している。検証手段２５０１は、発見手段２４０１により発見されたテンプレートが蓄積手段２４０２に蓄積すべきものかどうか（テンプレートの蓄積要否）を判断する。
この文書変換装置２５００は、検証手段２５０１の判断に応じて、発見手段２４０１により発見されたテンプレートを蓄積手段２５０３に蓄積するようになっている。例えば、検証手段２５０１は、発見手段２４０１により発見されたテンプレートが、蓄積手段２５０３に蓄積されているテンプレートと同型のテンプレートであるとき（つまり、発見されたテンプレートと同型のテンプレートが蓄積手段２５０３にあるとき）に、その発見されたテンプレートは、蓄積対象のテンプレートとして妥当でないと判断し、蓄積対象から除外するように作動する。これにより、蓄積手段２５０３に、無駄なテンプレートが蓄積されなくなるので、蓄積手段２５０３の空間利用効率を向上させることができる。
【００４６】
なお、本発明は図３で例示したデータ構造１１のみを対象としているものではない。テンプレートに設定されているパターン構造情報と同一の解析方法によって、構造情報を導出可能な構造化文書であれば入力対象にすることができるので、例えばＸＭＬの構造を表す標準的なモデル（Document Object Model）で表現された例を図１９に示す。図１９はデータ構造１９００を示す図である（なお、Document Object Modelについて詳しくは、http://www.w3.org/DOM/を参照）。
【００４７】
（第２の実施形態）
図１１は第２の実施形態に係る文書変換装置１１０１の構成を示すブロック図である。図１１に示すとおり、文書変換装置１１０１は蓄積手段１１０２と、一致箇所検出手段１１０３と、置換手段１１０４と、変換手段１１０５および変換位置検出手段１１１２を有している。この文書変換装置１１０１は構造情報１１０６、文字列情報１１０７、変換規則１１１１を入力し、第１の出力データ１１０８と、第２の出力データ１１０９とを出力する。蓄積手段１１０２、一致箇所検出手段１１０３、置換手段１１０４および変換手段１１０５は、それぞれ第２の実施形態に係る文書変換装置１０１の蓄積手段１０２、一致箇所検出手段１０３、置換手段１０４および変換手段１０５と同じ構成を有している。
【００４８】
変換位置検出手段１１１２は、変換規則１１１１を入力し、その変換規則１１１１に含まれる変化対象位置を示す数字（変換位置識別子）を変換位置情報１１１０として検出する。例えば、変換位置検出手段１１１２が変換規則１１１１として、例えば図１２に示した変換規則１２０を入力するときは、<transform match=“312”>から、変換位置識別子となる“３１２”を変換位置情報１１１０として検出する。検出された変換位置情報１１１０は一致箇所検出手段１１０３に伝達（入力）され、これ以降は、第１の実施の形態における文書変換装置１０１と同様にして、構造情報１１０６および文字列情報１１０７を対象とするテンプレートでの置換と、変換とが行われる。なお、変換規則１１１１は変換位置検出手段１１１２のほか、変換手段１１０５にも入力されている。
【００４９】
なお、変換規則１１１１が、図１６に示した変換規則１２１のように、ノード番号が記載されてなく、変換対象位置を構造情報と文字列情報とを参照しながら探索する必要のある言語（例えば、ＸＳＬＴ：extensible style-sheet language-transformation等）で記述されているときがある。その場合は、図示はしないが、変換位置検出手段１１１２に、変換規則１１１１のほか、構造情報１１０６および文字列情報１１０７を入力し、変換位置検出手段１１１２により、要素１２１ａで指定される<xsl:template match=“xxx”>における“xxx”に部分に記述されたXPath式を構造情報１１０６と文字列情報１１０７において評価して、変換位置情報を検出すればよい。その変換位置情報は一致箇所検出手段１１０３で利用できるように、構造情報１１０６のノード番号で記述してもよい。また、変換位置検出手段１１１２が“xxx”の部分に記述されたXPath式を変換位置情報として出力する一方、一致箇所検出手段１１０３に文字列情報１１０７をさらに入力し、入力されるXPath式を一致箇所検出手段１１０３が評価することにより、変換対象位置を特定してもよい。
【００５０】
図１４は、図１１に示した文書変換装置１１０１に、さらに変換規則蓄積手段１４０１を設けた文書変換装置１４００の構成を示すブロック図である。文書変換装置１４００は文書変換装置１１０１と比較して、変換規則蓄積手段１４０１を有する点、変換位置検出手段１１１２と入力情報が相違する変換位置検出手段１４０３を有する点で相違し、他は共通している。
変換規則蓄積手段１４０１は変換規則１１１１を変換手段１１０５で利用するたびに、変換規則１１１１に含まれる変換位置識別子を蓄積する。図１５は、その変換位置識別子を蓄積するテーブル１５０を示す図である。テーブル１５０は、変換位置枠１５１と利用回数枠１５２とを有し、変換位置識別子が蓄積されている。
【００５１】
また、変換規則蓄積手段１４０１は変換位置識別子を蓄積するときには、変換手段１１０５で利用のあった変換規則１１１１から、変換位置識別子を抽出して変換位置枠１５０１に格納する一方、利用回数枠１５０２には、各変換位置識別子の利用回数を格納する。テーブル１５０は変換手段１１０５により、ノード３０５，３１２，３１５がそれぞれ、３回、１１回、１回づつ利用されたことを示している。
そして、変換位置検出手段１４０３は変換規則蓄積手段１４０１に蓄積されている変換位置識別子をその利用頻度に応じて、つまり、利用頻度が高く、統計的にみて利用されやすい変換位置識別子を抽出し、それを変換位置情報として一致箇所検出手段１１０３に伝達（入力）している。例えば、テーブル１５０のようにして、変換位置識別子が蓄積されているとき、利用頻度の高い変換位置識別子は、例えば、ある閾値を超える利用回数をもつ変換位置識別子とすることができる。その閾値を“１０”としたときは、利用回数枠１５０２の値からみて、変換位置識別子として“３１２”のみが抽出され、その“３１２”が変換位置情報として一致箇所検出手段１１０３に入力される。
【００５２】
後の処理は、第１の実施形態と同様にして行えばよい。すなわち、一致箇所検出手段１１０３により、構造情報１１０６から蓄積手段１１０２に蓄積されたテンプレートとの一致箇所を検出する。その一致箇所を示す一致箇所情報にしたがい、置換手段１１０４が構造情報１１０６をテンプレートで置換し、置換後構造情報を出力する。そして、変換手段１１０５が置換後構造情報と文字列情報を変換規則にしたがい変換して、変換後構造情報を第１の出力データ１１０８として出力し、変換後文字列情報を第２の出力データ１１０９として出力する。
本実施の形態における文書変換装置１１０１、１４００によれば、変換手段１１０５に変換規則を入力する前に変換位置情報を一致箇所検出手段１１０３に入力することができるため、置換後構造情報を事前に生成し、保存しておくことが可能となる。したがって、例えば、すでに変換された構造化文書と同一の構造化文書を新たに変換しようとするときは、生成済みの置換後構造情報を用いることにより、一致箇所検出手段１１０３と置換手段１１０４における一致箇所の検出とテンプレートでの置換処理をスキップ（省略）することが可能となる。そのため、文書変換装置１１０１、１４００全体の処理時間を短縮することができる。
【００５３】
（第３の実施形態）
図１７は、本発明の第３の実施の形態に係る文書変換装置１７００の構成を示すブロック図である。文書変換装置１７００はテンプレート蓄積手段（以下「蓄積手段」という）１７０１と変換規則テンプレート置換手段（以下「変換規則置換手段」という）１７０２と変換手段１７０３とを有している。文書変換装置１７００は、変換対象である構造化文書の構造情報１７０４および文字列情報１７０５と、変換後構造化文書の構造情報が記述された変換規則１７０８とを入力し、変換後構造情報を第１の出力データ１７０６として出力し、変換後文字列情報を第２の出力データ１７０７として出力する。
【００５４】
蓄積手段１７０１は第１の実施形態で説明した蓄積手段１０２（図１参照）と同様に、構造化文書における構造情報の予め定めておいた特定のパターンをテンプレートとして蓄積している。変換規則置換手段１７０２は、ＸＳＬＴスタイルシート等の変換後構造化文書を含む変換規則１７０８を入力し、その変換規則１７０８から変換後構造化文書の構造情報を抽出する。また、変換規則置換手段１７０２は、抽出した構造情報と一致するテンプレートを蓄積手段１７０１から検出する一方、その構造情報を検出されたテンプレートで置換して、置換後変換規則１７１０として変換手段１７０３に伝達（入力）する。
【００５５】
ここで、図１２に示した変換規則１２０を変換規則１７０８の一例とすると、変換後構造化文書とは、＜transform match=“312”>と、</transform>とで囲まれた部分の構造化文書１２０ａとなる。ここで、変換後構造化文書の構造情報１２０ｂと同一のパターンをもつテンプレートを蓄積手段１７０１から検索するときの検索手順の例を図２０に示す。図２０はテンプレート検索手順を示す図である。このテンプレート検索手順により検出されたテンプレートは、図９に示す第２のテンプレート９００のようになる。
テンプレート検索手順は、図２０に示すとおり、処理開始後のステップ１において、変換規則１７０８から変換後構造化文書の構造情報を抽出する。抽出された変換後構造化文書をＰｊとする。抽出された変換後構造化文書の構造情報の数分、以下を繰り返す。
ステップ２に進み、蓄積手段１７０１からＰｊとノードの数が等しいものを選択する。
選択されたテンプレートをＸ１，Ｘ２，・・・・Ｘｍとする。
選択されたテンプレートの数分、以下を繰り返す。
ステップ３に進み、ＰｊとＸｋが同型か否かを判断して、同型の場合はステップ４に進み、同型でなければステップ４を実行することなく処理を終了する。ステップ４に進むとテンプレートを同型テンプレートとして登録し、処理を終了する。
【００５６】
図２１は置換後変換規則１７１０の一例となる置換後変換規則１７１を示す図である。図２１に示す置換後変換規則１７１は、図１２に示した変換規則１２０に、図９に示した第２のテンプレート９００を適用した場合を示している。図示のとおり、置換後変換規則１７１においては、変換規則１２０に記述された<transform match=“312”>と、</transform>とで囲まれた構造化情報１２０ｂが、採用テンプレートＩＤが“２”のテンプレート（すなわち、第２のテンプレート９００）で置換されている。
【００５７】
変換手段１７０３は、構造情報１７０４、文字列情報１７０５、置換後変換規則１７１０を入力して、その置換後変換規則１７１０にしたがい、構造情報１７０４および文字列情報１７０５を変換し、変換後構造情報を第１の出力データ１７０６として出力し、変換後文字列情報を第２の出力データ１７０７として出力する。
変換手段１７０３は、その変換の際には、置換後変換規則１７１０に含まれる変換位置情報（図２１の例では“３１２”）を用いて、変換後構造化文書の構造情報を構造情報１７０４にあてはめる。図２２は、その変換結果として、第１の出力データ１７０６の一例となる変換後構造情報１７６を示す図である。また、第２の出力データ１７０７の一例となる文字列情報は図１３に示したテーブル２３に列記されている。これらは、図４（ａ）に示した構造情報１２と、図４（ｂ）に記載の文字列情報を列記したテーブル１３と、図２１に示した置換後変換規則１７１とを入力したときの第１の出力データ１７０６および第２の出力データ１７０７の一例である。図２２に示す変換後構造情報１７６のとおり、第１の出力データ１７０６は構造情報のノード３１２以降がテンプレートで置換されている。
【００５８】
置換後変換規則１７１０は変換後構造化文書の構造情報がすでにテンプレートで置換されているため、変換手段１７０３がこの置換後変換規則１７１０を用いて変換を行うと、そのテンプレートが自動的に適用され、置換が行われるようになる。すなわち、文書変換とともに圧縮が行われ、圧縮と変換が同時に行われたことになる。これにより、文書変換装置１７００では、変換および圧縮処理がより効率的に行われる。
変換規則置換手段１７０２は変換規則１７０８から抽出した構造情報と差分が最も小さいテンプレート（以下「近似テンプレート」という）を蓄積手段１７０１から検出し、上記差分を示す差分情報を抽出し、置換後変換規則１７１０を近似テンプレートと差分情報とに置換するようにしてもよい。ここで、変換規則１７０８の例を図２７（ａ）に示し、図２７（ａ）に示した変換規則１７０８から抽出した構造情報１７０９を図２７（ｂ）に示す。例えば、蓄積手段１７０１に蓄積されているテンプレートが図５（ｂ）に記載の第１のテンプレート５１５のみであったとき、変換規則置換手段１７０２は、パターン構造情報内のノード数と図２７に示した（抽出した）構造情報１７０９内のノード数とを比較し、それらが等しければ近似テンプレートとして検出する。この例では、第１のテンプレート５１５のパターン構造情報５０５において、ノード５０９がノード５１０のｎｓに接続されたパターンを想定すると（ここで想定しているパターンは図示せず）、そのパターンが図２７に示した（抽出した）構造情報１７０９と一致している。
【００５９】
図２８は図２７（ａ）に記載の変換規則１７０８をテンプレートで置換した置換後変換規則の一例を示す図である。図２８に示すとおり、テンプレートで置換された置換後変換規則２８０は近似テンプレートの識別子を示す採用テンプレートＩＤ２８０１、パターン構造情報の外部インターフェースを示す実体接続情報２８０２、パターン構造情報内のノード番号を示す実体ノード情報２８０３、テンプレート実体そのものの識別子を示す実体ＩＤ２８０４、および実際の構造情報との差分を示す差分情報としてのテンプレート差分２８０５から構成されている。採用テンプレートＩＤ２８０１、実体接続情報２８０２、実体ノード情報２８０３、実体ＩＤ２８０４はそれぞれ図６に示したテンプレート実体６００を構成する採用テンプレートＩＤ６０１、実体接続情報６０３、実体ノード情報６０４、実体ＩＤ６０２と利用形態が同じである。テンプレート差分２８０５は、例えば、テンプレート内のパターン構造情報における各ノードの接続の切替え方を示している。図２７（ｂ）に示した構造情報１７０９については、図５（ｂ）に示した第１のテンプレート５１５のパターン構造情報５０５におけるノード５０９がノード５１０のｎｓに接続される構造となるので、ノード５０８のｎｓの接続を切るための情報（テンプレート差分２８０５の１行目）、ノード５０９のｐｓをノード５１０のｎｓに接続するための情報（テンプレート差分２８０５の２行目）、ノード５１０のｎｓをノード５０９のｐｓに接続するための情報（テンプレート差分２８０５の３行目）をそれぞれ有している。
以上のとおり、このような近似テンプレートを用いることにより、蓄積手段１７０１に蓄積されたテンプレートを効率よく利用することが可能となり、蓄積手段１７０１の容量を抑制することができる。
【００６０】
（第４の実施形態）
図１８は、第４の実施の形態に係る文書変換装置１８００の構成を示すブロック図である。文書変換装置１８００は、蓄積手段１８０１、一致箇所検出手段１８０２、置換手段１８０３、変換手段１８０４、変換規則置換手段１８０５を有している。文書変換装置１８００は、変換対象である構造化文書の構造情報１８０６および文字列情報１８０７を入力し、変換後構造情報を第１の出力データ１８０８として出力し、変換後文字列情報を第２の出力データ１８０９として出力する。
蓄積手段１８０１は、第１の実施形態に係る文書変換装置１０１における蓄積手段１０２（図１参照）と同様、予め定めておいた特定のパターンをテンプレートとして蓄積している。なお、テンプレートは特定のパターンを有すれば、予め定められてなくてもよく、第１の実施形態で説明した発見手段２４０１（図２４参照）により、変換規則から抽出してもよい。
【００６１】
一致箇所検出手段１８０２は、第１の実施形態に係る文書変換装置１０１における一致箇所検出手段１０３（図１参照）と同様に、構造情報１８０６と、構造情報１８０６における変換手段１８０４による変換箇所を示す変換位置情報１８１０とを入力し、その変換位置情報１１０が示す変換箇所を検出対象から除外して、構造情報１８０６と蓄積手段１８０１に蓄積されたテンプレートとの一致箇所を検出し、一致箇所情報１８１１を出力する。一致箇所検出手段１８０２は例えば、図２３に示した一致箇所検出手順にしたがい検出を行う。変換位置情報１８１０は第２の実施形態に係る変換位置検出手段１１１２（図１８には図示せず、図１参照）によって変換規則から抽出することができる。また、図示はしないが、文書変換装置１８００に第２の実施形態に係る文書変換装置１４００における変換規則蓄積手段１４０１と変換位置検出手段１４０３とを設け、その変換規則蓄積手段１４０１に蓄積されている変換位置識別子を利用頻度に応じて抽出するようにしてもよい。
【００６２】
図２３に示した一致箇所検出手順は次のとおりである。
処理開始後のステップ１０で、蓄積手段１８０１に蓄積されたテンプレートからノードの多い順に１つづつ選択し、以下を繰り返す。
選択したテンプレートをＰｊとする。
次に、ステップ１１に進み、構造情報に含まれるノードから変換対象となるノードを除いた後に、Ｐｊのノード数と一致するノードの組み合わせをＸ１，Ｘ２，・・・Ｘｍと記述し、その中から、１つづつ選択して、以下を繰り返す。
選択したノードの組み合わせをＸｋとする。
次に、ステップ１２に進み、Ｘｋに含まれるノードはすべて置換済みのマークが無いか否かを判断し、すべて置換済みのマークが無ければステップ１３に進み、そうでなければ後続のステップ１３，１４を実行することなく処理を終了する。ステップ１３に進むと、Ｐｊ，Ｘｋが同型か否かを判断し、同型であればステップ１４に進み、そうでなければ後続のステップ１４を実行することなく処理を終了する。ステップ１４に進むと、Ｘｋをテンプレート一致箇所として登録し、Ｘｋに含まれるノードは置換済みとしてマークする。
【００６３】
置換手段１８０３は第１の実施形態に係る文書変換装置１０１における置換手段１０４（図１参照）と同様に、構造情報１８０６と一致箇所情報１８１１とを入力し、その構造情報１８０６における一致箇所情報１８１１が示す一致箇所をテンプレートで置換し、置換後構造情報１８１２を出力する。
変換規則置換手段１８０５は第３の実施形態における変換規則置換手段１７０２（図１７参照）と同様、変換後構造化文書を含む変換規則１８１３を入力する。そして、変換規則置換手段１８０５は入力した変換規則１８１３から変換後構造化文書の構造情報を抽出する一方、抽出した構造情報と一致するテンプレートを蓄積手段１８０１から検出して、その構造情報をそのテンプレートで置換し、置換後変換規則１８１４として変換手段１８０４に伝達（入力）する。
【００６４】
変換手段１８０４は、第３の実施形態における変換手段１７０３（図１７参照）と同様に、構造情報１８０６、文字列情報１８０７、置換後変換規則１８１４を入力して、置換後変換規則１８１４にしたがい、構造情報１８０６および文字列情報１８０７を変換し、変換後構造情報を第１の出力データ１８０８として出力し、変換後文字列情報を第２の出力データ１８０９として出力する。
構造情報１８０６は、上述した図４（ａ）に示す構造情報１２と同様の構成を有している。文字列情報１８０７は、上述した図４（ｂ）に示すテーブル１３のように列記されている。変換規則１８１３は、上述した図１２に示す変換規則１２０と同様の構成を有している。蓄積手段１８０１には、図５（ｂ）に示した第１のテンプレート５１５と、図９に示した第２のテンプレート９００とが蓄積されているとする。また、変換位置情報１８１０は“３１２”が予め設定されている。
【００６５】
この例では、一致箇所検出手段１８０２から出力される一致箇所情報１８１１は、ノード３０２，３１０であり、置換手段１８０３から出力される置換後構造情報１８１２は図７に示す置換後構造情報３００となる。さらに、変換規則置換手段１８０５から出力される置換後変換規則１８１４は、図２１に示した置換後変換規則１７１のようになる。変換手段１８０４から出力される第１の出力データ１８０８は、図１０に示す変換後構造情報３６０となり、第２の出力データ１８０９は図１３に示したテーブル２３に列記された変換後文字列情報となる。
【００６６】
以上のような構成により、蓄積手段１８０１に蓄積されているテンプレートは、構造情報１８０６を置換するためのテンプレートとしても、変換規則１８１３を置換するためのテンプレートとしても利用できるようになる。すると、一致箇所検出手段１８０２において、図２３に示す一致箇所検出手順を用いれば、蓄積手段１８０１に蓄積されているテンプレートがメモリ上にのるオンメモリのテンプレートになるため、変換手段１８０４において、置換後変換規則１８１４に含めたテンプレートはそのオンメモリテンプレートを用いたものとなる。そのため、変換手段１８０４はテンプレートの読み出し時間を早めることができるので、処理速度が向上することになる。
【００６７】
また、この構成により、第１の出力データ１８０８は変換手段１８０４で変換されずに残った構造情報と変換後構造情報とが双方ともテンプレートが適用された形で出力することができる。すなわち、第１の実施形態で説明した変換後構造情報を圧縮するべく、第１の出力データ１８０８に対しても再度テンプレートを適用して圧縮するという、再圧縮をする必要がなく、変換手段１８０４を通過するだけで、変換されずに残った構造情報と変換後構造情報を同時に圧縮することができることになる。
【図面の簡単な説明】
【００６８】
【図１】本発明の第１の実施形態に係る文書変換装置の構成を示すブロック図である。
【図２】ＸＭＬ文書を示す図である。
【図３】ＸＭＬ文書のデータ構造を示す図である。
【図４】（ａ）は図３のデータ構造から分離された構造情報を示す図、（ｂ）は各ノードが有する文字列情報を列記したテーブルを示す図である。
【図５】（ａ）はテンプレートの構成を示すブロック図、（ｂ）は第１のテンプレートの構成を示すブロック図である。
【図６】テンプレート実体の構成を示すブロック図である。
【図７】置換後構造情報を示す図である。
【図８】変換後構造情報を示す図である。
【図９】第２のテンプレートの構成を示すブロック図である。
【図１０】別の変換後構造情報を示す図である。
【図１１】本発明の第２の実施形態に係る文書変換装置の構成を示すブロック図である。
【図１２】変換規則の一例を示す図である。
【図１３】第２の出力データの一例となる文字列情報を列記した別のテーブルを示す図である。
【図１４】図１１に示した文書変換装置に、変換規則蓄積手段を設けた文書変換装置の構成を示すブロック図である。
【図１５】図１４の変換規則蓄積手段に蓄積されている変換位置識別子を示すテーブルの一例を示す図である。
【図１６】別の変換規則の一例を示す図である。
【図１７】本発明の第３の実施形態に係る文書変換装置の構成を示すブロック図である。
【図１８】本発明の第４の実施形態に係る文書変換装置の構成を示すブロック図である。
【図１９】ＸＭＬ文書とは異なるデータ構造の一例を示す図である。
【図２０】テンプレート検索手順を示す図である。
【図２１】別の置換後変換規則を示す図である。
【図２２】別の変換後構造情報を示す図である。
【図２３】一致箇所検出手順の一例を示す図である。
【図２４】発見手段を有する文書変換装置の構成を示すブロック図である。
【図２５】検証手段を有する文書変換装置の構成を示すブロック図である。
【図２６】複数の装置から構成される文書変換装置の構成を示すブロック図である。
【図２７】（ａ）は変換規則の他例を示す図、（ｂ）は（ａ）の変換規則から抽出した構造情報を示すブロック図である。
【図２８】別の置換後変換規則を示す図である。
【符号の説明】
【００６９】
１０…ＸＭＬ文書、１１，１９００…データ構造
１２…構造情報、１３，２３…テーブル
１００…構造化文書
１０１，１１０１，１４００…文書変換装置
１７００，１８００，２４００…文書変換装置
２５００，１８００，２４００…文書変換装置
１０２，１１０２，１７０１，１８０１…蓄積手段
２４０２，２６０２…蓄積手段
１０３，１１０３，１８０２…一致箇所検出手段
２６０３…一致箇所検出手段
１０４，１１０４，１８０３，２６０４…置換手段
１０５，１１０５，１７０３，１８０４…変換手段
２６０５…変換手段
１０６，１１０６，１７０４，１８０６…構造情報
２６０７…構造情報
１０７，１１０７，１７０５，１８０７…文字列情報
２６０８…文字列情報
１０８，１１０８，１７０６…第１の出力データ
１８０８，２６０９…第１の出力データ
１０９，１１０９，１７０７…第２の出力データ
１８０９，２６１０…第２の出力データ
１１０…変換位置情報
１１１…一致箇所情報、
１１２…置換後構造情報
１１３，１２０，１２１，１７０８…変換規則
３００…置換後構造情報
１７６，３５０，３６０…変換後構造情報
５００…テンプレート、５１５…第１のテンプレート
６００…テンプレート実体
９００…第２のテンプレート
２６０１…第１の文書変換装置
２６０６…第２の文書変換装置
【図１】
2005100057.tif 000003
【図２】
2005100057.tif 000004
【図３】
2005100057.tif 000005
【図４】
2005100057.tif 000006
【図５】
2005100057.tif 000007
【図６】
2005100057.tif 000008
【図７】
2005100057.tif 000009
【図８】
2005100057.tif 000010
【図９】
2005100057.tif 000011
【図１０】
2005100057.tif 000012
【図１１】
2005100057.tif 000013
【図１２】
2005100057.tif 000014
【図１３】
2005100057.tif 000015
【図１４】
2005100057.tif 000016
【図１５】
2005100057.tif 000017
【図１６】
2005100057.tif 000018
【図１７】
2005100057.tif 000019
【図１８】
2005100057.tif 000020
【図１９】
2005100057.tif 000021
【図２０】
2005100057.tif 000022
【図２１】
2005100057.tif 000023
【図２２】
2005100057.tif 000024
【図２３】
2005100057.tif 000025
【図２４】
2005100057.tif 000026
【図２５】
2005100057.tif 000027
【図２６】
2005100057.tif 000028
【図２７】
2005100057.tif 000029
【図２８】
2005100057.tif 000030