(57)【要約】【課題】複数の要素を階層的に記述する文書から作成された木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる情報処理装置、情報処理方法、及びプログラムを提供する。【解決手段】ＲＡＭ２６の木構造記憶領域１６に記憶されたＤＯＭツリーの中から、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する。検出した同一部分の中で、特定の同一部分の記憶場所を示すリンク情報を生成する。木構造記憶領域１６に記憶されたＤＯＭツリーから、特定の同一部分以外の同一部分を削除する。削除した同一部分に対応させて特定の同一部分の記憶場所を示すリンク情報を木構造記憶領域１６に記憶する。【選択図】        図８
2005011215.tif 000002
【特許請求の範囲】
【請求項１】
複数の要素が階層的に記述された文書に対応する木構造を記憶した記憶手段と、
前記記憶された木構造において、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出手段と、
前記同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する生成手段と、
前記同一部分が検出された場合に、前記記憶手段から前記特定の同一部分以外の同一部分を削除すると共に、削除した同一部分に対応させて前記特定の同一部分の記憶場所を示す情報を前記記憶手段に記憶するように処理する処理手段と、
を含む情報処理装置。
【請求項２】
複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成手段と、
前記作成された木構造において、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出手段と、
前記同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する生成手段と、
前記作成された木構造の同一部分以外の部分及び前記特定の同一部分を記憶すると共に、前記特定の同一部分以外の同一部分に対応させて前記特定の同一部分の記憶場所を示す情報を記憶する記憶手段と、
を含む情報処理装置。
【請求項３】
複数の要素が階層的に記述された文書に対応する木構造を記憶した記憶手段と、
複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成手段と、
前記記憶された木構造と前記作成された木構造とを比較し、前記作成された木構造において前記記憶された木構造と要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出手段と、
前記同一部分が検出された場合に、前記記憶された木構造の同一部分の記憶場所を示す情報を生成する生成手段と、
前記同一部分が検出された場合に、前記作成された木構造の同一部分以外の部分、及び前記作成された木構造の同一部分に対応させて前記記憶された木構造の同一部分の記憶場所を示す情報を前記記憶手段に記憶するように処理する処理手段と、
を含む情報処理装置。
【請求項４】
複数の要素が階層的に記述された文書に対応する木構造を記憶した記憶手段と、
前記記憶された木構造において、要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出手段と、
前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成手段と、
前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成手段と、
前記類似部分が検出された場合に、前記記憶手段から前記類似部分の全てを削除し、削除した類似部分に対応させて、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を前記記憶手段に記憶するように処理する処理手段と、
を含む情報処理装置。
【請求項５】
複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成手段と、
前記作成された木構造において、要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出手段と、
前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成手段と、
前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成手段と、
前記類似部分が検出された場合に、前記類似部分以外の部分については、前記作成された木構造を記憶し、前記類似部分については、前記作成された木構造に代えて前記類似部分に対応させて前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を記憶する記憶手段と、
を含む情報処理装置。
【請求項６】
複数の要素が階層的に記述された文書に対応する木構造を記憶した記憶手段と、
複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成手段と、
前記記憶された木構造と前記作成された木構造とを比較し、前記作成された木構造において前記記憶された木構造と要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出手段と、
前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成手段と、
前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成手段と、
前記類似部分が検出された場合に、前記作成された木構造の類似部分以外の部分については、前記作成された木構造を前記記憶手段に記憶すると共に、前記記憶手段から前記類似部分を削除し、前記削除した部分及び前記作成された木構造の類似部分に対応させて、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を前記記憶手段に記憶するように処理する処理手段と、
を含む情報処理装置。
【請求項７】
前記類似部分検出手段は、
前記木構造の中から、類似している可能性がある部分を抽出する第１抽出手段と、
前記第１抽出手段により抽出された部分の中から、相違部分を抽出する第２抽出手段とを備え、
前記第２抽出手段により抽出された相違部分のデータ量が所定値以下である場合、及び前記相違部分のデータ量に対する前記第１抽出手段により抽出された部分のデータ量の比率が所定値以下である場合、のいずれか一方の場合に、前記第１抽出手段により抽出された部分を類似部分として検出する請求項４乃至請求項６のいずれか１項記載の情報処理装置。
【請求項８】
前記データ作成手段は、前記第１データに前記第２データを挿入可能に作成する請求項４乃至請求項７のいずれか１項記載の情報処理装置。
【請求項９】
前記データ作成手段は、前記第１データに前記第２データを所定の規則に従って変換するための変換式が含まれるように作成する請求項４乃至請求項８のいずれか１項記載の情報処理装置。
【請求項１０】
前記第１データの記憶場所及び前記第２データの記憶場所が記憶された類似部分が参照された場合に、前記第１データと前記参照された類似部分に対応する第２データとを用いて木構造を作成して前記記憶手段に記憶する類似部分木構造作成手段を更に含む請求項４乃至請求項９のいずれか１項記載の情報処理装置。
【請求項１１】
前記記憶手段の空き容量が所定値以下になった場合、及び、前記類似部分木構造作成手段により記憶された木構造が所定時間参照されなかった場合、のいずれか一方の場合には、前記類似部分木構造作成手段により記憶された木構造を前記記憶手段から削除する削除手段を更に含む請求項１０記載の情報処理装置。
【請求項１２】
複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、
前記記憶された木構造において、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出工程と、
前記同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する生成工程と、
前記同一部分が検出された場合に、前記記憶手段から前記特定の同一部分以外の同一部分を削除すると共に、削除した同一部分に対応させて前記特定の同一部分の記憶場所を示す情報を前記記憶手段に記憶するように処理する処理工程と、
を含む情報処理方法。
【請求項１３】
複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、
前記作成された木構造において、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出工程と、
前記同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する生成工程と、
前記作成された木構造の同一部分以外の部分及び前記特定の同一部分を記憶すると共に、前記特定の同一部分以外の同一部分に対応させて前記特定の同一部分の記憶場所を示す情報を記憶する記憶工程と、
を含む情報処理方法。
【請求項１４】
複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、
複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、
前記記憶された木構造と前記作成された木構造とを比較し、前記作成された木構造において前記記憶された木構造と要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出工程と、
前記同一部分が検出された場合に、前記記憶された木構造の同一部分の記憶場所を示す情報を生成する生成工程と、
前記同一部分が検出された場合に、前記作成された木構造の同一部分以外の部分、及び前記作成された木構造の同一部分に対応させて前記記憶された木構造の同一部分の記憶場所を示す情報を記憶するように処理する処理工程と、
を含む情報処理方法。
【請求項１５】
複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、
前記記憶された木構造において、要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出工程と、
前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成工程と、
前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成工程と、
前記類似部分が検出された場合に、前記記憶手段から前記類似部分の全てを削除し、削除した類似部分に対応させて、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を前記記憶手段に記憶するように処理する処理工程と、
を含む情報処理方法。
【請求項１６】
複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、
前記作成された木構造において、要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出工程と、
前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成工程と、
前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成工程と、
前記類似部分が検出された場合に、前記類似部分以外の部分については、前記作成された木構造を記憶し、前記類似部分については、前記作成された木構造に代えて前記類似部分に対応させて前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を記憶する記憶工程と、
を含む情報処理方法。
【請求項１７】
複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、
複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、
前記記憶された木構造と前記作成された木構造とを比較し、前記作成された木構造において前記記憶された木構造と要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出工程と、
前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成工程と、
前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成工程と、
前記類似部分が検出された場合に、前記作成された木構造の類似部分以外の部分については、前記作成された木構造を前記記憶手段に記憶すると共に、前記記憶手段から前記類似部分を削除し、前記削除した部分及び前記作成された木構造の類似部分に対応させて、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を前記記憶手段に記憶するように処理する処理工程と、
を含む情報処理方法。
【請求項１８】
コンピュータに、
複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、
前記記憶された木構造において、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出工程と、
前記同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する生成工程と、
前記同一部分が検出された場合に、前記記憶手段から前記特定の同一部分以外の同一部分を削除すると共に、削除した同一部分に対応させて前記特定の同一部分の記憶場所を示す情報を前記記憶手段に記憶するように処理する処理工程と、
を実行させるためのプログラム。
【請求項１９】
コンピュータに、
複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、
前記作成された木構造において、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出工程と、
前記同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する生成工程と、
前記作成された木構造の同一部分以外の部分及び前記特定の同一部分を記憶すると共に、前記特定の同一部分以外の同一部分に対応させて前記特定の同一部分の記憶場所を示す情報を記憶する記憶工程と、
を実行させるためのプログラム。
【請求項２０】
コンピュータに、
複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、
複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、
前記記憶された木構造と前記作成された木構造とを比較し、前記作成された木構造において前記記憶された木構造と要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出工程と、
前記同一部分が検出された場合に、前記記憶された木構造の同一部分の記憶場所を示す情報を生成する生成工程と、
前記同一部分が検出された場合に、前記作成された木構造の同一部分以外の部分、及び前記作成された木構造の同一部分に対応させて前記記憶された木構造の同一部分の記憶場所を示す情報を記憶するように処理する処理工程と、
を実行させるためのプログラム。
【請求項２１】
コンピュータに、
複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、
前記記憶された木構造において、要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出工程と、
前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成工程と、
前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成工程と、
前記類似部分が検出された場合に、前記記憶手段から前記類似部分の全てを削除し、削除した類似部分に対応させて、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を前記記憶手段に記憶するように処理する処理工程と、
を実行させるためのプログラム。
【請求項２２】
コンピュータに、
複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、
前記作成された木構造において、要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出工程と、
前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成工程と、
前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成工程と、
前記類似部分が検出された場合に、前記類似部分以外の部分については、前記作成された木構造を記憶し、前記類似部分については、前記作成された木構造に代えて前記類似部分に対応させて前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を記憶する記憶工程と、
を実行させるためのプログラム。
【請求項２３】
コンピュータに、
複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、
複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、
前記記憶された木構造と前記作成された木構造とを比較し、前記作成された木構造において前記記憶された木構造と要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出工程と、
前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成工程と、
前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成工程と、
前記類似部分が検出された場合に、前記作成された木構造の類似部分以外の部分については、前記作成された木構造を前記記憶手段に記憶すると共に、前記記憶手段から前記類似部分を削除し、前記削除した部分及び前記作成された木構造の類似部分に対応させて、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を前記記憶手段に記憶するように処理する処理工程と、
を実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数の要素が階層的に記述された文書を処理する情報処理装置、情報処理方法、及びプログラムに関し、特に、該文書から作成された木構造を記憶するために必要な記憶容量を削減する情報処理装置、情報処理方法、及びプログラムに関するものである。
【０００２】
【従来の技術】
計算機あるいはアプリケーションによってばらばらであったデータ形式を、異なる計算機やアプリケーションでも使用できるようにするための統一規格として、ＸＭＬ（ｅＸｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）が知られている。ＸＭＬは、複数の要素を階層的に記述する構造化文書の代表的な規格である。
【０００３】
ＸＭＬ文書のような構造化文書をアプリケーションで操作するためのＡＰＩ（Ａｐｐｌｉｃａｔｉｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｉｎｔｅｒｆａｃｅ）として、ＤＯＭ（Ｄｏｃｕｍｅｎｔ  Ｏｂｊｅｃｔ  Ｍｏｄｅｌ）が知られている。ＤＯＭは、構造化文書を木構造のオブジェクトとして扱うためのＡＰＩである。
【０００４】
構造化文書をＤＯＭに変換することにより、アプリケーションは、構造化文書の木構造を認識でき、木をたどって必要な要素にアクセスすることができる。
【０００５】
しかし、構造化文書をＤＯＭに変換する場合、構造化文書のサイズが大きいほど、変換後の木構造が大きくなり、これを記憶するために多くの記憶容量が必要となる。また、階層が深い場合にも、階層構造を表すための記憶容量が多く必要となる。従って、木構造に変換しても容量不足により記憶装置に格納できずに、エラーとなって処理が中断する、あるいは格納できたとしてもアクセス効率が悪くなってしまう、等の問題が発生する。
【０００６】
必要な記憶容量を削減するための装置としては、構造化文書の階層を浅くすることにより動作記憶容量を削減し、データアクセス効率を改善する変換装置（例えば、特許文献１を参照。）や、相対的に同じ位置にある同じ要素名の複数の要素の内容を接合して、一つの新しい要素を生成する構造化文書変換装置（例えば、特許文献２を参照。）が知られている。
【０００７】
【特許文献１】
特開２００２−２９７５６９号公報
【特許文献２】
特開２００２−１０８８５０号公報
【０００８】
【発明が解決しようとする課題】
しかしながら、従来の変換装置及び構造化文書変換装置では、構造化文書の階層構造自体を変化させるため、構造化文書を操作するアプリケーションは階層構造の変化を認識していなくてはならない、という問題がある。また、従来の複数の要素を合成する構造化文書変換装置では、相対的に同じ階層位置に同じ要素名の要素が存在する場合でないと合成できない、という問題もある。
【０００９】
本発明は、上述した問題を解決するために提案されたものであり、複数の要素を階層的に記述する文書から作成された木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる情報処理装置、情報処理方法、及びプログラムを提供することを目的とする。
【００１０】
【課題を解決するための手段】
上記目的を達成するために、本発明の第１の情報処理装置は、複数の要素が階層的に記述された文書に対応する木構造を記憶した記憶手段と、前記記憶された木構造において、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出手段と、前記同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する生成手段と、前記同一部分が検出された場合に、前記記憶手段から前記特定の同一部分以外の同一部分を削除すると共に、削除した同一部分に対応させて前記特定の同一部分の記憶場所を示す情報を前記記憶手段に記憶するように処理する処理手段と、を含んで構成されている。
【００１１】
本発明の第１の情報処理装置の記憶手段には、複数の要素が階層的に記述された文書に対応する木構造が記憶される。記憶手段は特に限定されず、例えば、メインメモリとして一般的に用いられるＲＡＭであってもよい。木構造は、複数の要素や要素の内容をノードとする木構造とすることができる。
【００１２】
複数の要素が階層的に記述された文書は、例えば、ＸＭＬ文書等に代表される構造化文書とすることができる。
【００１３】
同一部分検出手段は、記憶された木構造において、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する。生成手段は、同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する。
【００１４】
特定の同一部分は、同一部分検出手段により検出された複数の同一部分のいずれであってもよく、特に限定されない。
【００１５】
処理手段は、同一部分が検出された場合に、記憶手段から特定の同一部分以外の同一部分を削除するように処理する。処理手段は、削除した同一部分に対応させて特定の同一部分の記憶場所を示す情報を記憶手段に記憶するように処理する。
【００１６】
すなわち、特定の同一部分以外の同一部分については、木構造が削除され、代わりに特定の同一部分の記憶場所を示す情報が記憶される。
【００１７】
記憶場所を示す情報のデータ量は小さいため、記憶場所を示す情報を記憶しても記憶手段の記憶量が大幅に増加することはない。一方、木構造のデータ量は大きいため、同一部分の木構造を削除することにより木構造を記憶するために必要な記憶容量が大幅に削減されることとなる。
【００１８】
また、削除された同一部分を参照する場合であっても、特定の同一部分の記憶場所を示す情報を用いて、削除された同一部分の代わりに特定の同一部分の木構造を参照することができるため、木構造に対する操作性が損なわれることはない。
【００１９】
このように、同一部分を共通化できるため、木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる、
本発明の第１の情報処理方法は、複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、前記記憶された木構造において、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出工程と、前記同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する生成工程と、前記同一部分が検出された場合に、前記記憶手段から前記特定の同一部分以外の同一部分を削除すると共に、削除した同一部分に対応させて前記特定の同一部分の記憶場所を示す情報を前記記憶手段に記憶するように処理する処理工程と、を含んで構成されている。
【００２０】
本発明の第１のプログラムは、コンピュータに、複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、前記記憶された木構造において、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出工程と、前記同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する生成工程と、前記同一部分が検出された場合に、前記記憶手段から前記特定の同一部分以外の同一部分を削除すると共に、削除した同一部分に対応させて前記特定の同一部分の記憶場所を示す情報を前記記憶手段に記憶するように処理する処理工程と、を実行させる。
【００２１】
本発明の第１の情報処理方法及び第１のプログラムも、本発明の第１の情報処理装置と同様に作用するため、木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる。
【００２２】
本発明の第２の情報処理装置は、複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成手段と、前記作成された木構造において、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出手段と、前記同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する生成手段と、前記作成された木構造の同一部分以外の部分及び前記特定の同一部分を記憶すると共に、前記特定の同一部分以外の同一部分に対応させて前記特定の同一部分の記憶場所を示す情報を記憶する記憶手段と、を含んで構成されている。
【００２３】
本発明の第２の情報処理装置の木構造作成手段は、複数の要素が階層的に記述された文書に対応する木構造を作成する。
【００２４】
また、第２の情報処理装置の同一部分検出手段は、作成された木構造において、同一部分を検出する。生成手段は、同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する。
【００２５】
記憶手段は、作成された木構造の同一部分以外の部分及び特定の同一部分を記憶する。更に、特定の同一部分以外の同一部分に対応させて、特定の同一部分の記憶場所を示す情報を記憶する。
【００２６】
すなわち、検出された同一部分については、特定の同一部分のみ木構造として記憶手段に記憶され、他の同一部分については、木構造の代わりに特定の同一部分の記憶場所を示す情報が記憶される。
【００２７】
このように、同一部分の木構造を記憶しないことにより、木構造を記憶するために必要な記憶容量が大幅に削減されることとなる。
【００２８】
また、記憶されなかった同一部分を参照する場合であっても、特定の同一部分の記憶場所を示す情報を用いて、記憶されなかった同一部分の代わりに特定の同一部分の木構造を参照することができるため、木構造に対する操作性が損なわれることはない。
【００２９】
このように、同一部分を共通化できるため、木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる、
本発明の第２の情報処理方法は、複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、前記作成された木構造において、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出工程と、前記同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する生成工程と、前記作成された木構造の同一部分以外の部分及び前記特定の同一部分を記憶すると共に、前記特定の同一部分以外の同一部分に対応させて前記特定の同一部分の記憶場所を示す情報を記憶する記憶工程と、を含んで構成されている。
【００３０】
本発明の第２のプログラムは、コンピュータに、複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、前記作成された木構造において、要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出工程と、前記同一部分が検出された場合に、特定の同一部分の記憶場所を示す情報を生成する生成工程と、前記作成された木構造の同一部分以外の部分及び前記特定の同一部分を記憶すると共に、前記特定の同一部分以外の同一部分に対応させて前記特定の同一部分の記憶場所を示す情報を記憶する記憶工程と、を実行させる。
【００３１】
本発明の第２の情報処理方法及び第２のプログラムも、本発明の第２の情報処理装置と同様に作用するため、木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる。
【００３２】
本発明の第３の情報処理装置は、複数の要素が階層的に記述された文書に対応する木構造を記憶した記憶手段と、複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成手段と、前記記憶された木構造と前記作成された木構造とを比較し、前記作成された木構造において前記記憶された木構造と要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出手段と、前記同一部分が検出された場合に、前記記憶された木構造の同一部分の記憶場所を示す情報を生成する生成手段と、前記同一部分が検出された場合に、前記作成された木構造の同一部分以外の部分、及び前記作成された木構造の同一部分に対応させて前記記憶された木構造の同一部分の記憶場所を示す情報を前記記憶手段に記憶するように処理する処理手段と、を含んで構成されている。
【００３３】
本発明の第３の情報処理装置の記憶手段には、複数の要素が階層的に記述された文書に対応する木構造が記憶される。
【００３４】
木構造作成手段は、複数の要素が階層的に記述された文書に対応する木構造を作成する。
【００３５】
同一部分検出手段は、記憶された木構造と作成された木構造とを比較し、作成された木構造において記憶された木構造と同一の同一部分を検出する。
【００３６】
生成手段は、同一部分が検出された場合に、記憶された木構造の同一部分の記憶場所を示す情報を生成する。
【００３７】
処理手段は、同一部分が検出された場合に、作成された木構造の同一部分以外の部分を記憶手段に記憶するように処理する。また、処理手段は、作成された木構造の同一部分に対応させて、記憶された木構造の同一部分の記憶場所を示す情報を記憶手段に記憶するように処理する。
【００３８】
すなわち、検出された同一部分については、記憶手段に既に記憶されている同一部分の記憶場所を示す情報が木構造の代わりに記憶される。
【００３９】
このように、同一部分の木構造を記憶しないことにより、木構造を記憶するために必要な記憶容量が大幅に削減されることとなる。
【００４０】
また、記憶されなかった同一部分を参照する場合であっても、記憶手段に既に記憶されていた同一部分の記憶場所を示す情報を用いて、記憶されなかった同一部分の代わりに該同一部分の木構造を参照することができるため、木構造に対する操作性が損なわれることはない。
【００４１】
このように、同一部分を共通化できるため、木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる、
本発明の第３の情報処理方法は、複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、前記記憶された木構造と前記作成された木構造とを比較し、前記作成された木構造において前記記憶された木構造と要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出工程と、前記同一部分が検出された場合に、前記記憶された木構造の同一部分の記憶場所を示す情報を生成する生成工程と、前記同一部分が検出された場合に、前記作成された木構造の同一部分以外の部分、及び前記作成された木構造の同一部分に対応させて前記記憶された木構造の同一部分の記憶場所を示す情報を記憶するように処理する処理工程と、を含んで構成されている。
【００４２】
本発明の第３のプログラムは、コンピュータに、複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、前記記憶された木構造と前記作成された木構造とを比較し、前記作成された木構造において前記記憶された木構造と要素、要素の内容、及び要素の階層構造が同一の同一部分を検出する同一部分検出工程と、前記同一部分が検出された場合に、前記記憶された木構造の同一部分の記憶場所を示す情報を生成する生成工程と、前記同一部分が検出された場合に、前記作成された木構造の同一部分以外の部分、及び前記作成された木構造の同一部分に対応させて前記記憶された木構造の同一部分の記憶場所を示す情報を記憶するように処理する処理工程と、を実行させる。
【００４３】
本発明の第３の情報処理方法及び第３のプログラムも、本発明の第３の情報処理装置と同様に作用するため、木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる。
【００４４】
本発明の第４の情報処理装置は、複数の要素が階層的に記述された文書に対応する木構造を記憶した記憶手段と、前記記憶された木構造において、要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出手段と、前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成手段と、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成手段と、前記類似部分が検出された場合に、前記記憶手段から前記類似部分の全てを削除し、削除した類似部分に対応させて、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を前記記憶手段に記憶するように処理する処理手段と、を含んで構成されている。
【００４５】
本発明の第４の情報処理装置の記憶手段には、複数の要素が階層的に記述された文書に対応する木構造が記憶される。
【００４６】
類似部分検出手段は、記憶手段に記憶された木構造において、要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する。
【００４７】
データ作成手段は、検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成する。更にデータ作成手段は、類似部分の相違部分の情報を示す第２データを類似部分毎に作成する。
【００４８】
第１データは、例えば、各類似部分に含まれる共通のデータにより構成されていてもよい。また、第２データは、例えば、各類似部分から第１データに含まれる情報を除いた情報により構成されていてもよい。
【００４９】
生成手段は、第１データの記憶場所を示す情報及び各第２データの記憶場所を示す情報を生成する。
【００５０】
処理手段は、類似部分が検出された場合に、記憶手段から類似部分の全てを削除するように処理する。更に、削除した類似部分に対応させて、第１データの記憶場所を示す情報及び各第２データの記憶場所を示す情報を記憶手段に記憶するように処理する。
【００５１】
すなわち、類似部分については、木構造が削除され、代わりに第１データの記憶場所を示す情報及び各第２データの記憶場所を示す情報が記憶される。
【００５２】
記憶場所を示す情報のデータ量は小さいため、記憶場所を示す情報を記憶しても記憶手段の記憶量が大幅に増加することはない。一方、木構造のデータ量は大きいため、類似部分の木構造を削除することにより木構造を記憶するために必要な記憶容量が大幅に削減されることとなる。
【００５３】
また、削除された類似部分を参照する場合であっても、第１データの記憶場所を示す情報及び第２データの記憶場所を示す情報を用いて、第１データ及び第２データを読み出すことができるため、削除された類似部分を参照することができる。
【００５４】
このように、類似部分の木構造を削除して、第１データの記憶場所及び第２データの記憶場所を各類似部分に対応させて記憶するため、木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる、
本発明の第４の情報処理方法は、複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、前記記憶された木構造において、要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出工程と、前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成工程と、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成工程と、前記類似部分が検出された場合に、前記記憶手段から前記類似部分の全てを削除し、削除した類似部分に対応させて、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を前記記憶手段に記憶するように処理する処理工程と、を含んで構成されている。
【００５５】
本発明の第４のプログラムは、コンピュータに、複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、前記記憶された木構造において、要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出工程と、前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成工程と、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成工程と、前記類似部分が検出された場合に、前記記憶手段から前記類似部分の全てを削除し、削除した類似部分に対応させて、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を前記記憶手段に記憶するように処理する処理工程と、を実行させる。
【００５６】
本発明の第４の情報処理方法及び第４のプログラムも、本発明の第４の情報処理装置と同様に作用するため、木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる。
【００５７】
本発明の第５の情報処理装置は、複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成手段と、前記作成された木構造において、要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出手段と、前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成手段と、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成手段と、前記類似部分が検出された場合に、前記類似部分以外の部分については、前記作成された木構造を記憶し、前記類似部分については、前記作成された木構造に代えて前記類似部分に対応させて前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を記憶する記憶手段と、を含んで構成されている。
【００５８】
本発明の第５の情報処理装置の木構造作成手段は、複数の要素が階層的に記述された文書に対応する木構造を作成する。
【００５９】
類似部分検出手段は、木構造作成手段により作成された木構造において、類似部分を検出する。
【００６０】
データ作成手段は、検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成する。更にデータ作成手段は、類似部分の相違部分の情報を示す第２データを類似部分毎に作成する。生成手段は、第１データの記憶場所を示す情報及び各第２データの記憶場所を示す情報を生成する。
【００６１】
記憶手段は、類似部分が検出された場合に、類似部分以外の部分については、作成された木構造を記憶する。また、類似部分については、作成された木構造に代えて類似部分に対応させて第１データの記憶場所を示す情報及び各第２データの記憶場所を示す情報を記憶する。
【００６２】
すなわち、類似部分については、木構造は記憶されずに、代わりに第１データの記憶場所を示す情報及び各第２データの記憶場所を示す情報が記憶される。
【００６３】
このように、類似部分の木構造を記憶しないことにより、木構造を記憶するために必要な記憶容量が大幅に削減されることとなる。
【００６４】
また、記憶されなかった類似部分を参照する場合であっても、第１データの記憶場所及び第２データの記憶場所を示す情報を用いて、第１データ及び第２データを読み出すことができるため、記憶されなかった類似部分を参照することができる。
【００６５】
このように、類似部分の木構造は記憶せず、第１データの記憶場所及び第２データの記憶場所を各類似部分に対応させて記憶するため、木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる、
本発明の第５の情報処理方法は、複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、前記作成された木構造において、要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出工程と、前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成工程と、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成工程と、前記類似部分が検出された場合に、前記類似部分以外の部分については、前記作成された木構造を記憶し、前記類似部分については、前記作成された木構造に代えて前記類似部分に対応させて前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を記憶する記憶工程と、を含んで構成されている。
【００６６】
本発明の第５のプログラムは、コンピュータに、複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、前記作成された木構造において、要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出工程と、前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成工程と、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成工程と、前記類似部分が検出された場合に、前記類似部分以外の部分については、前記作成された木構造を記憶し、前記類似部分については、前記作成された木構造に代えて前記類似部分に対応させて前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を記憶する記憶工程と、を実行させる。
【００６７】
本発明の第５の情報処理方法及び第５のプログラムも、本発明の第５の情報処理装置と同様に作用するため、木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる。
【００６８】
本発明の第６の情報処理装置は、複数の要素が階層的に記述された文書に対応する木構造を記憶した記憶手段と、複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成手段と、前記記憶された木構造と前記作成された木構造とを比較し、前記作成された木構造において前記記憶された木構造と要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出手段と、前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成手段と、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成手段と、前記類似部分が検出された場合に、前記作成された木構造の類似部分以外の部分については、前記作成された木構造を前記記憶手段に記憶すると共に、前記記憶手段から前記類似部分を削除し、前記削除した部分及び前記作成された木構造の類似部分に対応させて、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を前記記憶手段に記憶するように処理する処理手段と、を含んで構成されている。
【００６９】
本発明の第６の情報処理装置の記憶手段は、複数の要素が階層的に記述された文書に対応する木構造を記憶する。
【００７０】
木構造作成手段は、複数の要素が階層的に記述された文書に対応する木構造を作成する。
【００７１】
類似部分検出手段は、記憶された木構造と作成された木構造とを比較し、作成された木構造において記憶された木構造と類似する類似部分を検出する。
【００７２】
データ作成手段は、検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成する。更にデータ作成手段は、類似部分の相違部分の情報を示す第２データを類似部分毎に作成する。生成手段は、第１データの記憶場所を示す情報及び各第２データの記憶場所を示す情報を生成する。
【００７３】
処理手段は、類似部分が検出された場合に、作成された木構造の類似部分以外の部分については、作成された木構造を記憶手段に記憶するように処理する。また、記憶手段から類似部分を削除するように処理する。更に処理手段は、該削除した部分及び作成された木構造の類似部分に対応させて、第１データの記憶場所を示す情報及び各第２データの記憶場所を示す情報を記憶手段に記憶するように処理する。
【００７４】
すなわち、作成された木構造の類似部分については、木構造は記憶されずに、代わりに第１データの記憶場所を示す情報及び第２データの記憶場所を示す情報が記憶される。また、既に記憶されている類似部分については、木構造が削除されて、代わりに第１データの記憶場所を示す情報、及び第２データの記憶場所を示す情報が記憶される。
【００７５】
このように、作成された類似部分の木構造を記憶しないと共に、記憶されていた類似部分の木構造を削除することにより、木構造を記憶するために必要な記憶容量が大幅に削減されることとなる。
【００７６】
また、記憶されなかったあるいは削除された類似部分を参照する場合であっても、第１データの記憶場所及び第２データの記憶場所を示す情報を用いて、第１データ及び第２データを読み出すことができるため、記憶されなかったあるいは削除された類似部分を参照することができる。
【００７７】
このような構成によっても、木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる、
本発明の第６の情報処理方法は、複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、前記記憶された木構造と前記作成された木構造とを比較し、前記作成された木構造において前記記憶された木構造と要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出工程と、前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成工程と、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成工程と、前記類似部分が検出された場合に、前記作成された木構造の類似部分以外の部分については、前記作成された木構造を前記記憶手段に記憶すると共に、前記記憶手段から前記類似部分を削除し、前記削除した部分及び前記作成された木構造の類似部分に対応させて、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を前記記憶手段に記憶するように処理する処理工程と、を含んで構成されている。
【００７８】
本発明の第６のプログラムは、コンピュータに、複数の要素が階層的に記述された文書に対応する木構造を記憶手段に記憶する記憶工程と、複数の要素が階層的に記述された文書に対応する木構造を作成する木構造作成工程と、前記記憶された木構造と前記作成された木構造とを比較し、前記作成された木構造において前記記憶された木構造と要素、要素の内容、及び要素の階層構造が類似する類似部分を検出する類似部分検出工程と、前記検出された類似部分に基づいて、各類似部分に共通する情報を示す第１データを作成すると共に、前記類似部分の相違部分の情報を示す第２データを前記類似部分毎に作成するデータ作成工程と、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を生成する生成工程と、前記類似部分が検出された場合に、前記作成された木構造の類似部分以外の部分については、前記作成された木構造を前記記憶手段に記憶すると共に、前記記憶手段から前記類似部分を削除し、前記削除した部分及び前記作成された木構造の類似部分に対応させて、前記第１データの記憶場所を示す情報及び前記各第２データの記憶場所を示す情報を前記記憶手段に記憶するように処理する処理工程と、を実行させる。
【００７９】
本発明の第６の情報処理方法及び第６のプログラムも、本発明の第６の情報処理装置と同様に作用するため、木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる。
【００８０】
なお、上述したプログラムを記憶するための記憶媒体は、ＲＯＭや、ＣＤ−ＲＯＭやＤＶＤディスク、光磁気ディスクやＩＣカード、あるいはハードディスク等であってもよいし、電気通信回線上の搬送波のような伝送媒体であってもよい。
【００８１】
上述した情報処理装置において、前記類似部分検出手段は、前記木構造の中から、類似している可能性がある部分を抽出する第１抽出手段と、前記第１抽出手段により抽出された部分の中から、相違部分を抽出する第２抽出手段とを備え、前記第２抽出手段により抽出された相違部分のデータ量が所定値以下である場合、及び前記相違部分のデータ量に対する前記第１抽出手段により抽出された部分のデータ量の比率が所定値以下である場合、のいずれか一方の場合に、前記第１抽出手段により抽出された部分を類似部分として検出することができる。
【００８２】
これにより、効率的に類似部分を検出することができる。
【００８３】
なお、類似している可能性がある部分を抽出する場合には、例えば、木構造において、同名のノード（要素）が含まれる部分を類似している可能性がある部分として抽出するようにしてもよいし、階層構造がほぼ一致している部分を類似している可能性がある部分として抽出してもよい。
【００８４】
前記データ作成手段は、前記第１データに前記第２データを挿入可能に作成することができる。
【００８５】
このように第１データを作成することにより、第１データ及び第２データを用いれば、元の類似部分を示すデータを作成することができるため、これに基づいて類似部分の木構造を作成することができる。
【００８６】
前記データ作成手段は、前記第１データに前記第２データを所定の規則に従って変換するための変換式が含まれるように作成することができる。
【００８７】
このように第１データを作成することにより、第１データを用いて第２データを変換することができる。これにより容易に元の類似部分を示すデータを作成することができるため、これに基づいて類似部分の木構造を作成することができる。
【００８８】
また、上述した情報処理装置は、前記第１データの記憶場所及び前記第２データの記憶場所が記憶された類似部分が参照された場合に、前記第１データと前記参照された類似部分に対応する第２データとを用いて木構造を作成して前記記憶手段に記憶する類似部分木構造作成手段を更に含んで構成されることができる。
【００８９】
これにより、類似部分が参照された場合に、容易に参照された類似部分の木構造を作成して記憶することができる。なお、ここでいう「参照」は、類似部分の木構造を操作する場合も含む。
【００９０】
更に、上述した情報処理装置は、前記記憶手段の空き容量が所定値以下になった場合、及び、前記類似部分木構造作成手段により記憶された木構造が所定時間参照されなかった場合、のいずれか一方の場合には、前記類似部分木構造作成手段により記憶された木構造を前記記憶手段から削除する削除手段を更に含んで構成されることができる。
【００９１】
これにより、記憶手段の空き容量を無駄に使用することがなくなる。
【００９２】
【発明の実施の形態】
以下、本発明の好ましい実施の形態について図面を参照しながら詳細に説明する。
【００９３】
［第１の実施の形態］
図１（Ａ）は、本実施の形態に係る構造化文書処理システムの機能構成及び構造化文書処理システムで行われる処理を概念的に示した図である。図示されるように、テキスト形式で記述されたＸＭＬ文書３０が、本発明の情報処理装置としてのＸＭＬプロセッサ（ＸＭＬパーザ）１０に入力されると、ＸＭＬプロセッサ１０は、ＸＭＬ文書３０の各要素をノードとする木構造（ＤＯＭツリー）４０を作成する。上位ＸＭＬアプリケーション５０は、作成されたＤＯＭツリー４０を参照あるいは操作することができる。。
【００９４】
図１（Ｂ）は、図１（Ａ）で示された構造化文書処理システムの機能構成及び構造化文書処理システムで行われる処理を更に詳細に示した図である。
【００９５】
（１）では、上位ＸＭＬアプリケーション５０がＸＭＬ文書３０を参照及び操作するために、ＤＯＭインタフェース６０を介して、ＸＭＬプロセッサ１０にＤＯＭツリー４０を作成するように指示を与える。
【００９６】
（２）では、指示を受けたＸＭＬプロセッサ１０は、ＸＭＬ文書３０を入力して解析する。
【００９７】
図２は、ＸＭＬ文書３０の一例を示している。図示されるようにＸＭＬ文書３０は、テキスト形式で、要素の始まりを示す開始タグ＜○○○＞と要素の終了を示す終了タグ＜／○○○＞により、複数の要素が階層的に記述されている。
【００９８】
具体的には、ＸＭＬプロセッサ１０は、図２に示されるようなＸＭＬ文書３０を上から順に読み込み、開始タグ及び終了タグを検出していくことにより、ＸＭＬ文書３０の各要素の階層構造を解析する。
【００９９】
更にＸＭＬプロセッサ１０は、解析結果に基づいて、ＤＯＭツリー４０を作成する。
【０１００】
図３は、図２のＸＭＬ文書３０を解析して作成されたＤＯＭツリー４０の一例を示している。図示されるように、各要素（Ｅｌｅｍｅｎｔ）がＤＯＭツリー４０のノード（節点）として構成されている（例えば、図のノード７０）。また、要素の内容、すなわち、開始タグと終了タグで挟まれた文字列（Ｔｅｘｔ）もノードとして構成されている（例えば、図のノード７２）。
【０１０１】
なお、図３の▲１▼で示された部分が、図２の▲１▼のｓｃａｎ要素の記述に対応する部分木（全体の木の一部）である。また、図３の▲２▼で示された部分が、図２の▲２▼のｓｔｏｒａｇｅ要素の記述に対応する部分木である。
【０１０２】
このように、ＤＯＭツリー４０は、複数の部分木により構成されている。
【０１０３】
（３）では、上位ＸＭＬアプリケーション５０が、作成されたＤＯＭツリー４０をＤＯＭインタフェース６０を介して参照あるいは操作する。
【０１０４】
図４は、ＸＭＬプロセッサ１０の機能を実現するためのハードウェア資源としての情報処理装置１１の構成を示すブロック図である。
【０１０５】
図示されるように、情報処理装置１１は、操作部１２、入出力部１８、ＣＰＵ２０、ネットワークＩ／Ｆ２２、ＲＯＭ２４、及びＲＡＭ２６を含んで構成され、これらはバスにより相互に接続されている。
【０１０６】
操作部１２は、例えばキーボード等により構成され、ユーザは操作部１２を用いて任意のデータを入力し、所定の操作を行う。
【０１０７】
ネットワークＩ／Ｆ２２は、各種ネットワークに接続するためのインタフェースである。
【０１０８】
入出力部１８は、各種データを入出力するためのインタフェースである。入出力部１８には、各種データやプログラム等を記憶するためのＨＤＤ２８が接続されている。
【０１０９】
ＲＯＭ２４は、ＸＭＬプロセッサ１０の機能としての、ＸＭＬ文書からＤＯＭツリーを作成すると共に、ＤＯＭツリーを記憶するために必要な記憶容量を削減するための処理ルーチンのプログラムが記憶されている。更にＲＯＭ２４には、ＸＭＬ文書を扱う上位ＸＭＬアプリケーション５０とＤＯＭインタフェース６０の機能を実現するためのプログラムも記憶されている。
【０１１０】
ＣＰＵ２０は、ＲＯＭ２４等に記憶されたプログラムを実行することにより各種機能を実現する。
【０１１１】
ＲＡＭ２６は、ワーク領域１４と木構造記憶領域１６とを含んで構成されている。ワーク領域１４は、作業中のデータを記憶するための作業領域である。木構造記憶領域１６は、作成されたＤＯＭツリーを記憶するための領域である。
【０１１２】
図１に示されたＸＭＬプロセッサ１０は、図４に示される情報処理装置１１をハードウェア資源とし、ＲＯＭ２４に記憶されたプログラムをソフトウェア資源として用いて実現される機能である。なお、上位ＸＭＬアプリケーション５０及びＤＯＭインタフェース６０も、同様にして実現される機能である。
【０１１３】
以下、図５及び図６のフローチャートを参照しながら、本実施の形態のＸＭＬプロセッサ１０により実行される処理ルーチンについて説明する。
【０１１４】
図５は、本実施の形態のメインルーチンを示したフローチャートである。
【０１１５】
ステップ１００では、ＸＭＬプロセッサ１０は上位ＸＭＬアプリケーション５０からのＤＯＭツリー作成指示を受け、構造化文書（ここではＸＭＬ文書）を取得する。例えば、ＸＭＬ文書が記憶された記憶装置がＨＤＤ２８である場合には、ＨＤＤ２８から入出力部１８を介して取得され、ネットワーク上の他のコンピュータシステムに記憶されている場合には、ネットワークＩ／Ｆ２２を介して取得される。
【０１１６】
ステップ１０２では、取得したＸＭＬ文書を解析する。前述したように、開始タグ及び終了タグを順に検出することにより、これらタグで記述された要素毎にその構造と内容を解析する。
【０１１７】
ステップ１０４では、ステップ１０２の解析結果に基づいて、解析された要素をノードとする木構造（部分木）を作成する。作成した部分木は、ＲＡＭ２６のワーク領域１４に保持しておく。なお、以下では、ＲＡＭ２６の木構造記憶領域１６に記憶された木構造をＤＯＭツリーと呼称し、作成してワーク領域１４に保持する木構造を部分木と呼称して区別する。
【０１１８】
ステップ１０６では、木構造記憶領域１６の空き容量が不足しているか否かを判断する。ここで、空き容量が不足していない、すなわち、ステップ１０４で作成された部分木を格納するために十分な空き容量があると判断した場合には、ステップ１１２に移行し、ワーク領域１４の部分木を木構造記憶領域１６に格納する。
【０１１９】
なお、空き容量が不足しているか否かを判断するために、例えば、閾値を設けておき、木構造記憶領域１６の空き容量が閾値以下となった場合に、空き容量が不足していると判断してもよいし、ＤＯＭツリーの記憶量が閾値に到達した場合に、空き容量が不足していると判断してもよい。
【０１２０】
続いて、ステップ１１４で、ＸＭＬ文書全体の解析が終了したか否かを判断し、ＸＭＬ文書全体の解析が終了していないと判断した場合には、ステップ１０２に戻り、更にＸＭＬ文書を読み込んで、次の開始タグ及び終了タグを検出することにより、ＸＭＬ文書の解析を続ける。
【０１２１】
一方、ステップ１０６で、空き容量が不足していると判断した場合には、ステップ１０８に移行し、ＤＯＭツリーを記憶するために必要な記憶容量を削減するための記憶容量削減処理を実行する。
【０１２２】
図６は、本実施の形態における記憶容量削減処理の流れを示すフローチャートである。
【０１２３】
ステップ２００では、ＸＭＬプロセッサ１０は、木構造記憶領域１６に記憶されているＤＯＭツリーから同一部分を探索する。木構造記憶領域１６に記憶されているＤＯＭツリーは、前述のステップ１０２、１０４、１１２の処理により作成されて記憶された部分木により構成されたＤＯＭツリーである。また、同一部分とは、要素、要素の内容、及び階層構造が同一の部分をいう。
【０１２４】
図７は、同一部分を含むＸＭＬ文書の一例を示した図である。図示されるように、ＸＭＬ文書中に、Ｘで示される部分と、Ｘの要素、要素の内容、及び階層構造が同一のＹで示される部分が含まれている。
【０１２５】
図８（Ａ）は、要素、要素の内容、階層構造が同一の部分を含むＸＭＬ文書から作成したＤＯＭツリーの一例を示した図である。図示されるように、同一部分８０ａ、８０ｂが含まれている。ステップ２００では、このような同一部分を探索する。
【０１２６】
ステップ２０２では、探索の結果、記憶されているＤＯＭツリーの中に、同一部分があるか否かを判断する。
【０１２７】
ここで、同一部分があると判断した場合には、ステップ２０４で、該同一部分のうち、特定の同一部分を除いた全ての同一部分の木構造を木構造記憶領域１６から削除する。ここでは、同一部分の中から特定の同一部分１つを選択し、他のものについては削除する。
【０１２８】
例えば、図８（Ａ）に示される例では、同一部分８０ａを特定の同一部分として選択し、該選択した同一部分８０ａは削除せず、他の同一部分、ここでは、同一部分８０ｂを削除することができる。なお、同一部分が３つ以上ある場合であっても、同様に、特定の同一部分を選択して、選択したものは削除せずに他を削除するようにすればよい。
【０１２９】
図８（Ｂ）は、図８（Ａ）のＤＯＭツリーから同一部分の木構造を削除した状態を示した図である。図示されるように、同一部分８０ｂが削除されている。
【０１３０】
ステップ２０６では、リンク情報を作成する。ここで、リンク情報とは、前述の特定の同一部分の記憶場所を示す情報である。図８（Ｂ）に示される例では、特定の同一部分８０ａの記憶場所を示す情報がリンク情報として作成される。
【０１３１】
ステップ２０８では、作成したリンク情報を、削除した同一部分８０ｂに対応させて木構造記憶領域１６に格納する。図８（Ｂ）に示される例では、ノードＣから、ノードＢ直下のノードＥに対してリンクを張ることに相当する。
【０１３２】
ステップ２１０では、木構造記憶領域１６に記憶されているＤＯＭツリーの探索が終了したか否かを判断する。ここで、探索が終了していないと判断した場合には、ステップ２００に戻り、記憶容量削減処理を続行する。探索が終了したと判断した場合には、本記憶容量削減処理ルーチンを終了する。本処理ルーチンにより、ＤＯＭツリーを記憶するために必要な記憶容量を削減することができる。
【０１３３】
図５のステップ１０８の記憶容量削減処理が終了すると、ＸＭＬプロセッサ１０は、ステップ１１０で、木構造記憶領域１６の空き容量不足が解消されたか否かを判断する。空き容量不足が解消されなかったと判断した場合には、ステップ１１６で空き容量不足を示すメッセージを図示されない表示部等に表示し、ＤＯＭツリーを作成するための処理を終了する。
【０１３４】
ステップ１１０で、空き容量不足が解消されたと判断した場合、例えば、木構造記憶領域１６の空き容量が前述した閾値を超えた場合等には、ステップ１１２に移行し、ステップ１０４で作成した部分木を木構造記憶領域１６に格納する。
【０１３５】
ステップ１１４では、取得したＸＭＬ文書全体の解析が終了しているか否かを判断し、終了していないと判断した場合には、ステップ１０２に戻り、更にＸＭＬ文書を読み込んで、次の開始タグ及び終了タグを検出することにより、ＸＭＬ文書の解析を続ける。終了したと判断した場合には、ＤＯＭツリーを作成するための処理を終了する。
【０１３６】
なお、ＤＯＭツリー作成後、ＸＭＬプロセッサ１０は、作成したＤＯＭツリーを上位ＸＭＬアプリケーション５０に渡す。なお、ここでは、上位ＸＭＬアプリケーション５０及びＤＯＭインタフェース６０はＸＭＬプロセッサ１０と同じハードウェア資源を用いて実現されているため、ＸＭＬプロセッサ１０は、上位ＸＭＬアプリケーション５０に、作成したＤＯＭツリーの格納場所をＤＯＭインタフェース６０を介して通知する形でＤＯＭツリーを渡す。
【０１３７】
以上説明したように、本実施の形態では、特定の同一部分を除く同一部分を削除し、特定の同一部分の記憶場所を示す情報を、削除した同一部分に対応させて記憶するようにしたため、木構造を記憶するために必要な記憶容量を大幅に削減することができる。
【０１３８】
なお、本実施の形態では、木構造記憶領域１６が容量不足となった場合に、同一部分を探索して削除する記憶容量削減処理を実行する例について説明したが、木構造記憶領域１６の容量不足に拘らず、部分木作成毎、あるいは所定の間隔で、記憶容量削減処理を実行するようにしてもよい。
【０１３９】
また、本実施の形態では、木構造記憶領域１６に記憶されているＤＯＭツリーを対象として記憶容量削減処理を実行する例について説明したが、木構造記憶領域１６に記憶する前段階の、ワーク領域１４に保持された部分木を対象として記憶容量削減処理を実行するようにしてもよい。
【０１４０】
また、部分木を作成する毎に、作成した部分木と、木構造記憶領域１６に記憶されているＤＯＭツリーとを比較し、同一部分があれば、作成した部分木の中で同一部分以外の部分については、木構造の状態で木構造記憶領域１６に記憶し、同一部分については、木構造を記憶する代わりに、既に木構造記憶領域１６に記憶されている同一部分の記憶場所を示す情報を記憶するようにしてもよい。
【０１４１】
このような構成によっても、木構造を記憶するために必要な記憶容量を大幅に削減することができる。
【０１４２】
［第２の実施の形態］
第１の実施の形態では、同一部分を対象として処理する例について説明したが、本実施の形態では、類似する部分を対象として処理する例について説明する。
【０１４３】
なお、本実施の形態におけるハードウェア構成、ソフトウェア構成、及びＸＭＬプロセッサ１０により実行されるメインルーチンは第１の実施の形態と同様であるため、説明を省略する。本実施の形態では、第１の実施の形態で図６のフローチャートを用いて説明した記憶容量削減処理に代えて、以下に説明する記憶容量削減処理を実行する。
【０１４４】
まず、図９（Ａ）、（Ｂ）を参照しながら、本実施の形態の記憶容量削減処理について簡単に説明する。
【０１４５】
まず、木構造記憶領域１６に記憶されているＤＯＭツリーから類似部分を検出する。図９（Ａ）に示されるように、類似部分（部分木）８２、８４は、ノードＧとノードＩとが異なっているが、他のノードや階層構造は同じであり、類似しているといえる。
【０１４６】
図９（Ｂ）に示されるように、検出した類似部分８２，８４から、共通化できる部分については、ＸＭＬ形式の共通のデータ（以下、共通データと呼称）８６を作成し、相違部分については、類似部分それぞれに対応したＸＭＬ形式の相違部分のデータ（以下、ＸＭＬデータと呼称）８８、９０を作成する。類似部分の木構造は削除して、代わりに作成したデータの記憶場所を示す情報を記憶する。
【０１４７】
なお、本実施の形態では、共通データ８６には、類似部分に共通のテキストデータの他、Ｘｉｎｃｌｕｄｅ要素やＸＳＬＴ（ＸＳＬ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎｓ：ＸＭＬのデータ変換言語）による記述を含め作成する例について説明する。この記述については後述する。
【０１４８】
図１０は、本実施の形態で実行される記憶容量削減処理ルーチンの流れを詳細に示したフローチャートである。本図を用いて、記憶容量削減処理について更に詳細に説明する。
【０１４９】
ステップ３００では、ＸＭＬプロセッサ１０は、木構造記憶領域１６に記憶されているＤＯＭツリーから同一タグ名を探索する。すなわち、ここで同一タグ名を探索することにより、類似している可能性のある部分を抽出する。具体的には、ＸＭＬプロセッサ１０は、記憶されているＤＯＭツリーを、ルートノードから下位方向に順に探索していき、同一のタグ名を検出する。
【０１５０】
ステップ３０２で、探索の結果、記憶されているＤＯＭツリーの中に、同一タグ名のノードが検出できたか否かを判断する。同一タグ名のノードが検出できなかったと判断した場合には、ＤＯＭツリーには類似部分が無いと判断することができ、本記憶容量削減処理ルーチンを終了する。
【０１５１】
また、ステップ３０２で、同一タグ名のノードが検出できたと判断した場合には、ステップ３０４で検出された同一タグ名のノードの下位に位置するノード（下位ノード）の量を算出する。例えば、図９（Ａ）に示される例において、同一タグ名のノード「Ｃ」の下位ノードは、部分木８２では、ノードＦ、Ｈ、及びＧであり、部分木８４では、ノードＦ、Ｈ、及びＩである。ここでは、全ての下位ノードの量を算出する。
【０１５２】
ステップ３０６では、算出された下位ノードの量が予め指定された量以上であるか否かを判断する。ここで、下位ノードの量が予め指定された量未満である場合には、下位ノードの量は少ないため、これ以降の処理を行ったとしても、木構造記憶領域１６の容量不足を解消することはできないと判断し、ステップ３２２に移行する。
【０１５３】
ステップ３２２では、木構造記憶領域１６に記憶されているＤＯＭツリーの探索が終了したか否かを判断する。ここで、探索が終了していないと判断した場合には、ステップ３００に戻り、記憶容量削減処理を続行する。探索が終了したと判断した場合には、本記憶容量削減処理ルーチンを終了する。
【０１５４】
一方、ステップ３０６で、下位ノードの量が予め指定された量以上である場合には、ステップ３０８で、下位ノードの量に基づいて、閾値を算出する。この閾値は、類似している可能性のある部分として検出された部分木において、相違部分がどの程度存在するかを判断するための指標であり、これにより、検出された類似している可能性のある部分を、類似部分として扱うか否かを定めることができる。なお、ここでは、下位ノード量が多いほど、閾値が高くなるように算出する。
【０１５５】
ステップ３１０では、相違量を算出する。具体的には、下位ノードの各ノードのタグ名、及びタグの配列（配列状態や内容）を比較し、相違部分を抽出してカウントすることにより、相違量を算出する。例えば、図９（Ａ）では、ノードＧ及びノードＩが異なるため、この部分がカウント対象となる。
【０１５６】
相違量を算出する場合に、相違部分の種類によってカウント数を異ならせるようにしてもよい。例えば、内容（数字等）が異なる場合にはカウント数を低くし、タグ名が異なる場合にはカウント数を高くするようにすることもできる。これは、内容（数字等）が異なる場合には、Ｘｉｎｃｌｕｄｅ要素やＸＳＬＴによる記述が容易であり、タグ名が異なる場合には、これらによる記述が困難であることに起因する。Ｘｉｎｃｌｕｄｅ要素及びＸＳＬＴは、本記憶容量削減処理において各類似部分に共通のデータを作成する際に用いられるが、この点については後述する。
【０１５７】
なお、相違量をカウントするためのカウント数の設定は、予め設定されていてもよいし、ユーザが任意に設定するようにしてもよい。
【０１５８】
ステップ３１２では、算出した相違量と算出した閾値とを比較する。相違量が閾値より大きい場合には、類似している可能性があるとして検出した部分は、類似部分ではないと判断し、ステップ３２２に移行し、探索が終了していなければ探索処理を繰り返す。
【０１５９】
ステップ３１２で、相違量が閾値以下である場合には、類似している可能性があるとして検出した部分は、類似部分であると判断し、ステップ３１４に移行し、該類似部分から抽出された相違部分の種類を分析する。相違部分の種類により、Ｘｉｎｃｌｕｄｅ要素を用いてデータを作成するインサートデータ作成処理、及びＸＳＬＴを用いてデータを作成する変換データ作成処理、のいずれの処理を行うかを決定する。
【０１６０】
ステップ３１６で、相違部分の種類がインサートデータ作成処理に適合していると判断した場合には、ステップ３１８のインサートデータ作成処理を実行する。また相違部分の種類が変換データ作成処理に適合していると判断した場合には、ステップ３２０の変換データ作成処理を実行する。
【０１６１】
ここで、インサートデータ作成処理及び変換データ作成処理について詳細に説明する。
【０１６２】
例えば、相違部分に同じタグ名で内容が異なるノードが多く含まれている場合には、共通部分に各類似部分の相違部分を挿入することで各類似部分を表現できる。従って、この場合には、Ｘｉｎｃｌｕｄｅ要素を用いるインサートデータ作成処理に適合していると判断することができる。
【０１６３】
図１１（Ａ）及び（Ｂ）は、インサートデータ作成処理に適合するＸＭＬ文書の一例である。図示されるように、図１１（Ａ）の元データ１で示されたＸＭＬ文書と図１１（Ｂ）の元データ２で示されたＸＭＬ文書は、共通部分の他に相違部分Ａ１またはＡ２を含んで構成されている。相違部分Ａ１及びＡ２は、同じタグ名ｋｉｎｄｓであるが、内容が異なっている。従って、インサートデータ作成処理に適合していると判断できる。
【０１６４】
図１２は、インサートデータ作成処理のサブルーチンを示したフローチャートである。
【０１６５】
ステップ４００では、ＸＭＬプロセッサ１０は、Ｘｉｎｃｌｕｄｅ要素を用いて、共通データを作成すると共に、相違部分のＸＭＬデータを類似部分毎に作成する。
【０１６６】
ステップ４０２では、作成した共通データ及びＸＭＬデータを記憶する。
【０１６７】
作成した共通データ及びＸＭＬデータはテキストデータであるため、データ量が小さく、木構造を記憶する場合に比して記憶するために必要な記憶容量は少なくて済む。また、共通データを作成することにより、共通化できる部分は共通化されているため、記憶するために必要な記憶容量は少なくて済む。
【０１６８】
なお、共通データ及びＸＭＬデータの記憶場所は、特に限定されず、例えば、ＨＤＤ２８とすることもできる。また、ネットワークに接続された他のコンピュータシステムの記憶装置とすることもできる。
【０１６９】
ステップ４０４では、リンク情報を作成する。ここで、リンク情報とは、ステップ４０２で記憶した共通データ及びＸＭＬデータの記憶場所を示す情報である。
【０１７０】
ステップ４０６では、木構造記憶領域１６から類似部分の木構造を削除し、各類似部分に対応させて各リンク情報を木構造記憶領域１６に格納する。また、本実施の形態では、図１４に示されるような管理テーブルを例えばＲＡＭ２６のワーク領域あるいはＨＤＤ２８上に設け、各リンク情報を格納して一元管理する。これにより各類似部分に対応させて各リンク情報を記憶する際に、各リンク情報に代えて管理テーブルの管理番号を記憶することもできる。
【０１７１】
図１３（Ａ）、（Ｂ）、及び（Ｃ）は、図１１の元データ１及び元データ２に基づいて作成された、共通データとＸＭＬデータを示した図である。
【０１７２】
図１３（Ｂ）に示されるように、ＸＭＬデータ１は、図１１（Ａ）の元データ１に対応するデータであり、元データ１の相違部分Ａ１が記述されている。図１３（Ｃ）のＸＭＬデータ２は、図１１（Ｂ）の元データ２に対応するデータであり、元データ２の相違部分Ａ２が記述されている。
【０１７３】
また、図１３（Ａ）の共通データは、元データ１及び元データ２に共通する共通部分の他に、ＸＭＬデータ１及びＸＭＬデータ２に記述されたデータが挿入されるようにＸｉｎｃｌｕｄｅ要素Ａ３を含んで構成されている。Ｘｉｎｃｌｕｄｅ要素Ａ３で指定されるアドレスは、ＸＭＬデータ１及びＸＭＬデータ２の記憶場所を示すものであり、本実施の形態では、例えば、前述の管理テーブルの記憶場所としてもよい。
【０１７４】
このように、共通データは、類似部分の中の共通部分を含むように作成されると共に、類似部分の中の相違部分を挿入可能に作成される。
【０１７５】
一方、例えば、相違部分が、一部分の数字やテキストが異なるが、内容はほぼ同じような場合には、各々の類似部分の相違部分を所定の規則により変換することで各類似部分を表現できる。従って、この場合には、ＸＳＬＴを用いる変換データ作成処理に適合していると判断することができる。
【０１７６】
図１５（Ａ）及び（Ｂ）は、変換データ作成処理に適合したＸＭＬ文書の一例である。図示されるように、図１５（Ａ）の元データ１で示されたＸＭＬ文書と図１５（Ｂ）の元データ２で示されたＸＭＬ文書は、共通部分の他に、相違部分Ｂ１またはＢ２を含んで構成されている。相違部分Ｂ１及びＢ２は、数字やテキストが異なっているが、内容はほぼ同じである。従って、変換データ作成処理に適合していると判断できる。
【０１７７】
図１６は、変換データ作成処理のサブルーチンを示したフローチャートである。
【０１７８】
ステップ５００では、ＸＭＬプロセッサ１０は、ＸＳＬＴを用いて、共通データを作成すると共に、相違部分のＸＭＬデータを類似部分毎に作成する。
【０１７９】
ステップ５０２乃至ステップ５０６の処理は、上述したインサートデータ作成処理のサブルーチンのステップ４０２乃至４０６の処理と同様であるため説明を省略する。
【０１８０】
図１７（Ａ）、（Ｂ）、及び（Ｃ）は、図１５の元データ１及び元データ２に基づいて作成された、共通データとＸＭＬデータを示した図である。
【０１８１】
図１７（Ａ）に示されるように、共通データは、元データ１及び元データ２に共通する共通部分の他に、ＸＳＬＴの変換式Ｂ３を含んで構成されている。
【０１８２】
また、図１７（Ｂ）のＸＭＬデータ１は、元データ１に対応するデータであり、元データ１の相違部分Ｂ１に相当する記述が含まれている。図１７（Ｃ）のＸＭＬデータ２は、元データ２に対応するデータであり、元データ２の相違部分Ｂ２に相当する記述が含まれている。図から明らかなように、ＸＭＬデータの記述は、図１５の元データ１及び２の相違部分そのままが記述されたものにはなっていない。相違部分において、ＸＳＬＴを用いて変換可能な内容（本例では数字）については、共通データにＸＳＬＴの変換式Ｂ３を記述することで対応しているためである。
【０１８３】
図に示される例では、変換式Ｂ３において、ノードをそのままコピーするｃｏｐｙ−ｏｆ要素のｓｅｌｅｃｔ属性で、コピーしたノードの位置を表すｐｏｓｉｔｉｏｎ（）関数を用いて指定することにより、元データの相違部分に記述された数字が構成され、各ノードの値をそのまま文字列として出力するためのｖａｌｕｅ  ｏｆ  要素のｓｅｌｅｃｔ属性で、カレントノード（図では”．”で示されている）を指定することにより、相違部分に記述された文字列の内容が構成される。
【０１８４】
このように、ＸＳＬＴの変換式を用いることにより、類似部分を効率的に共通化することができる。
【０１８５】
このように、図１０のステップ３１８またはステップ３２０を実行した後は、ステップ３２２では、木構造記憶領域１６に記憶されているＤＯＭツリーの探索が終了したか否かを判断する。ここで、探索が終了していないと判断した場合には、ステップ３００に戻り、記憶容量削減処理を続行する。探索が終了したと判断した場合には、本記憶容量削減処理ルーチンを終了する。
【０１８６】
以上説明したように、類似部分の木構造を削除し、各類似部分に共通する情報を示す共通データと、相違部分の情報を示すＸＭＬデータとを作成して、各類似部分に対応させて記憶し、作成したデータの記憶場所を示す情報を木構造の代わりに記憶するようにしたため、木構造を記憶するために必要な記憶容量を大幅に削減することができる。
【０１８７】
なお、本実施の形態でも第１の実施の形態と同様に、記憶容量削減処理の実行を、木構造記憶領域１６が容量不足となった場合に限らず、部分木作成毎、あるいは所定の間隔で実行するようにしてもよい。
【０１８８】
また、本実施の形態では、木構造記憶領域１６に記憶されているＤＯＭツリーを対象として記憶容量削減処理を実行する例について説明したが、木構造記憶領域１６に記憶する前段階の、ワーク領域１４に保持された部分木を対象として記憶容量削減処理を実行するようにしてもよい。
【０１８９】
また、部分木を作成する毎に、作成した部分木と、木構造記憶領域１６に記憶されているＤＯＭツリーとを比較して類似部分を探索するようにしてもよい。この場合には、類似部分があれば、作成した部分木の中で類似部分以外の部分については、木構造の状態で木構造記憶領域１６に記憶し、既に木構造記憶領域１６に記憶されているＤＯＭツリーの類似部分については、木構造を削除する。また、各類似部分について、共通データ及びＸＭＬデータを作成して記憶し、この記憶場所を示すリンク情報を木構造の代わりに各類似部分に対応させて記憶するように処理する。
【０１９０】
このような構成によっても、木構造を記憶するために必要な記憶容量を大幅に削減することができる。
【０１９１】
［第３の実施形態］
本実施の形態では、第２の実施の形態で説明した記憶容量削減処理において、相違量が０の場合には、同一部分と判断して処理する例について説明する。
【０１９２】
本実施の形態におけるハードウェア構成、ソフトウェア構成、及びＸＭＬプロセッサ１０により実行されるメインルーチンは第１の実施の形態と同様であるため、説明を省略する。ＸＭＬプロセッサ１０により実行される記憶容量削減処理ルーチンは、第２の実施の形態において図１０のフローチャートを用いて説明した記憶容量削減処理ルーチンのステップ３１２に代えて、図１８に示されるステップ６００乃至ステップ６０８を実行する。
【０１９３】
ステップ３１０で相違量を算出した後、ステップ６００で、ＸＭＬプロセッサ１０は、相違量が０であるか否かを判断する。相違量が０であると判断した場合には、類似している可能性があるとして検出した部分は、同一部分であると判断し、ステップ６０４に移行する。ステップ６０４からステップ６０８では、第１の実施の形態で説明したステップ２０４からステップ２０８の処理と同様に、ＤＯＭツリーから特定の同一部分以外の同一部分を削除し、特定の同一部分の記憶場所を示すリンク情報を作成して、削除した同一部分に対応させて該リンク情報を記憶する。その後は、図１０のステップ３２２に移行し、更に探索処理を続けるか、あるいは記憶容量削減処理を終了する。
【０１９４】
ステップ６００で、相違量が０ではないと判断した場合には、類似している可能性があるとして検出した部分は、同一部分ではないと判断し、ステップ６０２に移行する。ステップ６０２では、相違量が閾値以下であるか否かを判断する。相違量が閾値以下の場合には、類似している可能性があるとして検出した部分は、類似部分であると判断し、ステップ３１４に移行する。その後の処理は、第２の実施の形態と同様であるため、説明を省略する。
【０１９５】
以上説明したように、同一部分及び類似部分の双方を処理対象として記憶容量削減処理を行うようにしたため、木構造を記憶するために必要な記憶容量を効率的に削減することができる。
【０１９６】
［第４の実施形態］
本実施の形態では、第２の実施の形態及び第３の実施の形態で木構造記憶領域１６から削除した類似部分がアクセスされた場合に、類似部分を木構造に展開する例、及び木構造記憶領域１６が容量不足となった場合、または展開した類似部分に所定時間アクセスが無い場合、のいずれか一方の場合に再度削除する例について説明する。
【０１９７】
なお、展開とは、ここでは、前述した処理ルーチンで作成された共通データ及びＸＭＬデータを用いて木構造を作成し、木構造記憶領域１６に記憶する処理をいう。
【０１９８】
図１９は、本実施の形態における展開処理ルーチンを示すフローチャートである。
【０１９９】
ステップ７００では、ＸＭＬプロセッサ１０は、ＤＯＭツリーから削除され類似部分が上位ＸＭＬアプリケーション５０からアクセスされたか否かを判断する。類似部分がアクセスされたと判断された場合には、前述の管理テーブルに該類似部分に対応して記憶されている共通データ及びＸＭＬデータのリンク情報から、共通データ及びＸＭＬデータを読み出す。
【０２００】
ステップ７０４では、読み出した共通データ及びＸＭＬデータを用いて、元の木構造に展開する。具体的には、共通データ及びＸＭＬデータから元のＸＭＬ文書を作成し、該作成されたＸＭＬ文書から木構造を再作成して木構造記憶領域１６に記憶する。
【０２０１】
ステップ７０６では、前述の管理テーブルの、該類似部分に対応して記憶されているリンク情報を削除する。
【０２０２】
ステップ７０８では、展開した類似部分に対応するタイマＴｉをスタートさせる。タイマＴｉは、展開した類似部分毎に設けられ、後述する削除処理ルーチンで、展開した類似部分の木構造を削除するか否かの判断に用いられる。
【０２０３】
このように、類似部分がアクセスされた場合には、木構造に展開するようにしたため、上位ＸＭＬアプリケーション５０は、類似部分と類似部分以外の部分とを区別することなくアクセスすることができる。
【０２０４】
図２０は、本実施の形態における削除処理ルーチンを示すフローチャートである。
【０２０５】
ステップ８００では、木構造記憶領域１６が容量不足となったか否かを判断する。容量不足ではないと判断した場合には、ステップ８０２に移行する。
【０２０６】
ステップ８０２では、ＸＭＬプロセッサ１０は、タイマＴｉが閾値Ｔｔｈ以上になったか否かを判断する。タイマＴｉが閾値Ｔｔｈ未満の場合には、ステップ８０４で、対応の類似部分にアクセスがあったか否かを判断する。アクセスがあったと判断した場合には、タイマＴｉをリセットして、ステップ８００に戻る。また、ステップ８０４でアクセスがないと判断した場合には、タイマＴｉをリセットせずにステップ８００に戻る。
【０２０７】
ステップ８００で、木構造記憶領域１６が容量不足であると判断した場合、または、ステップ８０２で、タイマＴｉが閾値Ｔｔｈ以上になったと判断した場合には、ステップ８０８で、タイマＴｉに対応する展開した類似部分を木構造記憶領域１６から削除する。
【０２０８】
ステップ８１０では、削除した類似部分に対応するリンク情報を作成して再度管理テーブルに格納する。ステップ８１２で、タイマＴｉをリセットして終了する。
【０２０９】
このように、木構造記憶領域１６が容量不足となった場合、または展開した類似部分に所定時間アクセスが無い場合、のいずれか一方の場合に、展開した木構造を木構造記憶領域１６から削除するようにしたため、木構造記憶領域１６が容量不足となってエラーが発生する、あるいはアクセス効率が低下する、といった事態が発生することを防止することができる。
【０２１０】
【発明の効果】
以上説明したように、本発明によれば、複数の要素を階層的に記述する文書から作成された木構造の階層構造を変化させることなく、木構造を記憶するために必要な記憶容量を削減することができる、という効果を奏する。
【図面の簡単な説明】
【図１】図１（Ａ）は、本実施の形態に係る構造化文書処理システムの機能構成と、構造化文書処理システムで行われる処理を概念的に示した図であり、図１（Ｂ）は、図１（Ａ）で示された構造化文書処理システムの機能構成と、構造化文書処理システムで行われる処理とを更に詳細に示した図である。
【図２】ＸＭＬ文書の一例を示した図である。
【図３】図２のＸＭＬ文書を解析して作成されたＤＯＭツリーの一例を示した図である。
【図４】ＸＭＬプロセッサの機能を実現するためのハードウェア資源としての情報処理装置の構成を示すブロック図である。
【図５】ＸＭＬプロセッサにより実行される処理ルーチンのメインルーチンを示したフローチャートである。
【図６】第１の実施の形態に係る記憶容量削減処理ルーチンを示すフローチャートである。
【図７】同一部分を含むＸＭＬ文書の一例を示した図である。。
【図８】図８（Ａ）は、要素、要素の内容、階層構造が同一の部分を含むＸＭＬ文書から作成したＤＯＭツリーの一例を示した図であり、図８（Ａ）は、図８（Ｂ）のＤＯＭツリーから同一部分の木構造を削除した状態を示した図である。。
【図９】図９（Ａ）は、類似部分を含むＤＯＭツリーの一例であり、図９（Ｂ）は、類似部分の木構造を削除して、代わりに作成した共通データ及びＸＭＬデータの記憶場所を示す情報を記憶した状態を示した図である。
【図１０】第２の実施の形態に係る記憶容量削減処理ルーチンを示すフローチャートである。
【図１１】インサートデータ作成処理に適合するＸＭＬ文書の一例である。
【図１２】インサートデータ作成処理のサブルーチンを示したフローチャートである。
【図１３】図１３（Ａ）は、図１１の元データ１及び元データ２に基づいて作成された共通データを示した図であり、図１３（Ｂ）及び図１３（Ｃ）は、図１１の元データ１及び元データ２に基づいて作成されたＸＭＬデータを示した図である。
【図１４】共通データ及びＸＭＬデータの記憶場所を示す情報を記憶した管理テーブルの一例である。
【図１５】変換データ作成処理に適合したＸＭＬ文書の一例である。
【図１６】変換データ作成処理のサブルーチンを示したフローチャートである。
【図１７】図１７（Ａ）は、図１５の元データ１及び元データ２に基づいて作成された共通データを示した図であり、図１７（Ｂ）及び図１７（Ｃ）は、図１５の元データ１及び元データ２に基づいて作成されたＸＭＬデータを示した図である。
【図１８】第３の実施の形態に係る記憶容量削減処理ルーチンのフローチャートの一部である。
【図１９】第４の実施の形態に係る展開処理ルーチンを示すフローチャートである。
【図２０】第４の実施の形態に係る削除処理ルーチンを示すフローチャートである。
【符号の説明】
１０  ＸＭＬプロセッサ
１１  情報処理装置
１６  ワーク領域
１８  木構造記憶領域
２０  ＣＰＵ
２４  ＲＯＭ
２６  ＲＡＭ
５０  上位ＸＭＬアプリケーション
【図１】
2005011215.tif 000003
【図２】
2005011215.tif 000004
【図３】
2005011215.tif 000005
【図４】
2005011215.tif 000006
【図５】
2005011215.tif 000007
【図６】
2005011215.tif 000008
【図７】
2005011215.tif 000009
【図８】
2005011215.tif 000010
【図９】
2005011215.tif 000011
【図１０】
2005011215.tif 000012
【図１１】
2005011215.tif 000013
【図１２】
2005011215.tif 000014
【図１３】
2005011215.tif 000015
【図１４】
2005011215.tif 000016
【図１５】
2005011215.tif 000017
【図１６】
2005011215.tif 000018
【図１７】
2005011215.tif 000019
【図１８】
2005011215.tif 000020
【図１９】
2005011215.tif 000021
【図２０】
2005011215.tif 000022