(57)【特許請求の範囲】
【請求項１】
サーバ装置上の構造化文書格納手段に格納されている、階層的に結合された構造を持つ複数のエレメントを含み且つ各エレメントには文字情報が付随する構造化文書を対象として、エレメント間の結合関係に係る構造を変更する編集及び又はエレメントに付随する文字情報を変更する編集を複数のクライアント装置上で並行して行うための構造化文書編集システムにおいて、
前記構造化文書格納手段に格納されている構造化文書に含まれる複数のエレメントの各々について、当該エレメントに係る文字情報に対して最後に行われた編集に関する情報を含む第１の管理情報を記憶する第１の記憶手段と、
前記構造化文書格納手段に格納されている構造化文書に含まれる複数のエレメントの各々について、当該エレメントの他のエレメントとの結合関係に係る構造に対して最後に行われた編集に関する情報を含む第２の管理情報を記憶する第２の記憶手段と、
前記複数のクライアント装置のうちの１つのクライアント装置上で行われた編集全体を、文字情報に関する第１の編集と構造に関する第２の編集とに分けて得るための取得手段と、
前記第１の編集について、前記第１の記憶手段に記憶されている第１の管理情報との比較に基づいて、前記構造化文書格納手段に格納されている構造化文書の一貫性維持に関する判定を行い、この判定結果に基づいて、該第１の編集を前記構造化文書格納手段に格納されている構造化文書へ反映させるとともに、前記第１の記憶手段に記憶されている第１の管理情報のうち該第１の編集に係る部分を更新するための第１の処理手段と、
前記第２の編集について、前記第２の記憶手段に記憶されている第２の管理情報との比較に基づいて、前記構造化文書格納手段に格納されている構造化文書の一貫性維持に関する判定を行い、この判定結果に基づいて、該第２の編集を前記構造化文書格納手段に格納されている構造化文書へ反映させるとともに、前記第２の記憶手段に記憶されている第２の管理情報のうち該第２の編集に係る部分を更新するための第２の処理手段とを備えたことを特徴とする構造化文書編集システム。
【請求項２】
前記第１の処理手段は、前記第１の編集が前記一貫性維持を維持しているか否かを判定し、維持していると判定された場合には、該第１の編集を前記構造化文書に反映し、維持していないと判定された場合には、該第１の編集を破棄しまたは一貫性が崩れていることをコメントとして付加して該第１の編集を前記構造化文書に反映することを特徴とする請求項１に記載の構造化文書編集システム。
【請求項３】
前記第２の処理手段は、前記第２の編集が前記一貫性維持を維持しているか否かを判定し、維持していると判定された場合には、該第２の編集を前記構造化文書に反映し、維持していないと判定された場合には、該第２の編集を破棄することを特徴とする請求項１に記載の構造化文書編集システム。
【請求項４】
前記第１の処理手段及び前記第２の処理手段は、前記サーバ装置に組み込まれていることを特徴とする請求項１に記載の構造化文書編集システム。
【請求項５】
前記取得手段は、前記サーバ装置又は前記クライアント装置のいずれか一方に組み込まれていることを特徴とする請求項１に記載の構造化文書編集システム。
【請求項６】
前記第１の編集を、さらに、独立性及び極小性を有する単位に分割するための分割手段を更に備え、
前記第２の処理手段は、前記第１の編集が、さらに、前記独立性及び極小性を有する単位に分割された場合には、該独立性及び極小性を有する単位ごとに、前記判定並びに前記反映及び前記更新を行うことを特徴とする請求項１ないし５のいずれか１項に記載の構造化文書編集システム。
【請求項７】
前記分割手段は、前記第１の編集を、一旦、複数のアトミックな単位に分割する手段と、該複数のアトミックな単位のうち、独立性及び極小性を有しないものを、独立性及び極小性を有するものになるように取り纏めて、独立性及び極小性を有する単位を作成する手段とを含むものであることを特徴とする請求項６に記載の構造化文書編集システム。
【請求項８】
前記取得手段及び前記分割手段がいずれも前記クライアント装置に組み込まれているか、前記取得手段が前記クライアント装置に組み込まれており且つ前記分割手段が前記サーバ装置に組み込まれているか、又は前記取得手段及び前記分割手段がいずれも前記サーバ装置に組み込まれていることを特徴とする請求項６または７に記載の構造化文書編集システム。
【請求項９】
前記第１の管理情報及び又は前記第２の管理情報は、前記最後に行われた編集に関する情報として、当該編集が最後に行われたクライアント装置を示すクライアント情報を含み、
前記第１の処理手段及び又は前記第２の処理手段は、前記判定にあたって、当該編集が行われた今回のクライアント装置が、前記クライアント情報により示されるクライアント装置と同一である場合と同一でない場合とで、相異なる判定基準を用いることを特徴とする請求項１ないし７のいずれか１項に記載の構造化文書編集システム。
【請求項１０】
前記第１の処理手段及び又は前記第２の処理手段は、前記判定にあたって、前記今回のクライアント装置が、前記クライアント情報により示されるクライアント装置と同一である場合には、より遅い時刻における編集を前記構造化文書格納手段に格納されている構造化文書に反映させる判定基準を用い、同一でない場合には、より早い時刻における編集を前記構造化文書格納手段に格納されている構造化文書に反映させる判定基準を用いることを特徴とする請求項９に記載の構造化文書編集システム。
【請求項１１】
前記エレメントに付随する文字情報は、エレメントのエレメント値及びエレメントのエレメント名であり、
前記第１の編集は、エレメントのエレメント値を変更する編集と、エレメントのエレメント名を変更する編集に分けられ、
前記第１の処理手段は、前記判定並びに前記反映及び前記更新を、エレメント値に関する編集と、エレメント名に関する編集とに分けて行うことを請求項１に記載の構造化文書編集システム。
【請求項１２】
前記構造化文書に含まれる複数のエレメントの各々には固有のエレメント識別子が割り当てられており、
編集前の構造化文書のエレメントと編集後の構造化文書のエレメントとの対応は、前記エレメント識別子に基づいて特定されることを特徴とする請求項１ないし１１のいずれか１項に記載の構造化文書編集システム。
【請求項１３】
サーバ装置上の構造化文書格納手段に格納されている、階層的に結合された構造を持つ複数のエレメントを含み且つ各エレメントには文字情報が付随する構造化文書を対象として、エレメント間の結合関係に係る構造を変更する編集及び又はエレメントに付随する文字情報を変更する編集を複数のクライアント装置上で並行して行うための構造化文書編集システムであって、取得手段、第１の処理手段及び第２の処理手段、並びに前記構造化文書格納手段に格納されている構造化文書に含まれる複数のエレメントの各々について、当該エレメントに係る文字情報に対して最後に行われた編集に関する情報を含む第１の管理情報を記憶する第１の記憶手段、及び前記構造化文書格納手段に格納されている構造化文書に含まれる複数のエレメントの各々について、当該エレメントの他のエレメントとの結合関係に係る構造に対して最後に行われた編集に関する情報を含む第２の管理情報を記憶する第２の記憶手段を備えた構造化文書編集システムにおける構造化文書編集方法において、
前記取得手段により、前記複数のクライアント装置のうちの１つのクライアント装置上で行われた編集全体を、文字情報に関する第１の編集と構造に関する第２の編集とに分けて得るためのステップと、
前記第１の処理手段により、前記第１の編集について、前記第１の記憶手段に記憶されている第１の管理情報との比較に基づいて、前記構造化文書格納手段に格納されている構造化文書の一貫性維持に関する判定を行い、この判定結果に基づいて、該第１の編集を前記構造化文書格納手段に格納されている構造化文書へ反映させるとともに、前記第１の記憶手段に記憶されている第１の管理情報のうち該第１の編集に係る部分を更新するためのステップと、
前記第２の処理手段により、前記第２の編集について、前記第２の記憶手段に記憶されている第２の管理情報との比較に基づいて、前記構造化文書格納手段に格納されている構造化文書の一貫性維持に関する判定を行い、この判定結果に基づいて、該第２の編集を前記構造化文書格納手段に格納されている構造化文書へ反映させるとともに、前記第２の記憶手段に記憶されている第２の管理情報のうち該第２の編集に係る部分を更新するためのステップとを有することを特徴とする構造化文書編集方法。
【請求項１４】
サーバ装置上の構造化文書格納手段に格納されている、階層的に結合された構造を持つ複数のエレメントを含み且つ各エレメントには文字情報が付随する構造化文書を対象として、エレメント間の結合関係に係る構造を変更する編集及び又はエレメントに付随する文字情報を変更する編集を複数のクライアント装置上で並行して行うための構造化文書編集システムであって、取得手段、第１の処理手段及び第２の処理手段、並びに前記構造化文書格納手段に格納されている構造化文書に含まれる複数のエレメントの各々について、当該エレメントに係る文字情報に対して最後に行われた編集に関する情報を含む第１の管理情報を記憶する第１の記憶手段、及び前記構造化文書格納手段に格納されている構造化文書に含まれる複数のエレメントの各々について、当該エレメントの他のエレメントとの結合関係に係る構造に対して最後に行われた編集に関する情報を含む第２の管理情報を記憶する第２の記憶手段を備えた構造化文書編集システムとしてコンピュータを機能させるためのプログラムにおいて、
前記プログラムは、
前記取得手段により、前記複数のクライアント装置のうちの１つのクライアント装置上で行われた編集全体を、文字情報に関する第１の編集と構造に関する第２の編集とに分けて得るためのステップと、
前記第１の処理手段により、前記第１の編集について、前記第１の記憶手段に記憶されている第１の管理情報との比較に基づいて、前記構造化文書格納手段に格納されている構造化文書の一貫性維持に関する判定を行い、この判定結果に基づいて、該第１の編集を前記構造化文書格納手段に格納されている構造化文書へ反映させるとともに、前記第１の記憶手段に記憶されている第１の管理情報のうち該第１の編集に係る部分を更新するためのステップと、
前記第２の処理手段により、前記第２の編集について、前記第２の記憶手段に記憶されている第２の管理情報との比較に基づいて、前記構造化文書格納手段に格納されている構造化文書の一貫性維持に関する判定を行い、この判定結果に基づいて、該第２の編集を前記構造化文書格納手段に格納されている構造化文書へ反映させるとともに、前記第２の記憶手段に記憶されている第２の管理情報のうち該第２の編集に係る部分を更新するためのステップとをコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、サーバ上に格納されている構造化文書を、複数のクライアント上で並行して編集するための構造化文書編集システム及び構造化文書編集方法に関する。
【０００２】
【従来の技術】
同一の文書を複数のユーザが並行して編集する際には、現在ＣＶＳ（Ｃｏｎｃｕｒｒｅｎｔ  Ｖｅｒｓｉｏｎｓ  Ｓｙｓｔｅｍ）と呼ばれる文書のバージョン管理をシステムを用いて文書管理する方法が一般的に用いられている。ＣＶＳには、これからシステムに登録しようとしている文書と現在システムに登録されている文書を行単位で比較し、両者において一貫性が取れていない部分を行単位でユーザに通知するという機能が備わっている。そこで、この機能を使うことにより、文書の一貫性を維持することが可能である。構造化文書も文書であるから、ＣＶＳを用いて構造化文書の一貫性を維持することも可能である。
【０００３】
【発明が解決しようとする課題】
しかしながら、ＣＶＳには、以下に述べるような問題点がある。
【０００４】
サーバ上で一元管理している構造化文書を、複数のユーザが各自のクライアント上で並行して編集するシステムでは、ユーザがつじつまが合わない編集を行った場合であっても、システムがコンフリクトしないと判定してサーバに反映した結果、構造化文書の一貫性を壊すことや、逆にユーザがつじつまが合う編集を行った場合であっても、システムがコンフリクトすると判定した結果、サーバに反映することが不可能なことが多い。
【０００５】
例えば、構造化文書を用いて記述される同一の論文を複数の執筆者が並行して編集するとき、ある執筆者が他の執筆者の編集内容とつじつまが合わない編集を行った場合であっても、常に論文全体の一貫性を維持するシステムを実現することや、お互い他の執筆者の編集内容とつじつまが合う編集を行っている場合には、常にすべての執筆者の編集内容を忠実に反映するシステムを実現することは困難である。
【０００６】
同一の文書を複数のユーザが並行して編集する際は、現在ＣＶＳを用いて文書管理する方法が一般的に用いられている。しかしながら、ＣＶＳを構造化文書を管理する際に用いると、ＣＶＳは文書の行単位でコンフリクト判定を行うために、構造化文書が持っている構造情報を反映した単位でのコンフリクト判定を行わず、望ましい結果が得られない。
【０００７】
例えば、ＣＶＳを使って構造化文書を管理するシステムで、図３１（ａ）に示した構造化文書をユーザ１とユーザ２が並行して編集する場合を考える。手続き（１−１）でユーザ１が図３１（ｂ）に示すように節の順番を入れ替える編集を行い、手続き（１−２）でユーザ２が図３１（ｃ）に示すように段落の順番を入れ替える編集を行ったとする。節の順番を入れ替える編集と、段落の順番を入れ替える編集とは独立であるので、２人のユーザが行った編集内容は両方とも反映されるべきである。しかし、編集結果につき、第１に手続き（２）においてユーザ１が同期を取り、続いて手続き（３）においてユーザ２が同期を取ると、システムはコンフリクトが発生したと判断し、最終的な編集結果は図３１（ｄ）に示した文書になる。
【０００８】
そこで、すべてあるいはより多くのユーザの編集意図をより豊富に柔軟に取り込むことを可能とする一貫性維持方式が望まれる。
【０００９】
本発明は、上記事情を考慮してなされたもので、サーバ上に格納されている構造化文書を、複数のクライアント上で並行して編集する場合でも、ユーザの編集意図をより豊富に柔軟に取り込むことを可能にした構造化文書編集システム及び構造化文書編集方法を提供することを目的とする。
【００１０】
【課題を解決するための手段】
本発明は、サーバ装置上の構造化文書格納手段に格納されている、階層的に結合された構造を持つ複数のエレメントを含み且つ各エレメントには文字情報が付随する構造化文書を対象として、エレメント間の結合関係に係る構造を変更する編集及び又はエレメントに付随する文字情報を変更する編集を複数のクライアント装置上で並行して行うための構造化文書編集システムにおいて、
前記構造化文書格納手段に格納されている構造化文書に含まれる複数のエレメントの各々について、当該エレメントに係る文字情報に対して最後に行われた編集に関する情報を含む第１の管理情報を記憶する第１の記憶手段と、
前記構造化文書格納手段に格納されている構造化文書に含まれる複数のエレメントの各々について、当該エレメントの他のエレメントとの結合関係に係る構造に対して最後に行われた編集に関する情報を含む第２の管理情報を記憶する第２の記憶手段と、
前記複数のクライアント装置のうちの１つのクライアント装置上で行われた編集全体を、文字情報に関する第１の編集と構造に関する第２の編集とに分けて得るための取得手段と、
前記第１の編集について、前記第１の記憶手段に記憶されている第１の管理情報との比較に基づいて、前記構造化文書格納手段に格納されている構造化文書の一貫性維持に関する判定を行い、この判定結果に基づいて、該第１の編集を前記構造化文書格納手段に格納されている構造化文書へ反映させるとともに、前記第１の記憶手段に記憶されている第１の管理情報のうち該第１の編集に係る部分を更新するための第１の処理手段と、
前記第２の編集について、前記第２の記憶手段に記憶されている第２の管理情報との比較に基づいて、前記構造化文書格納手段に格納されている構造化文書の一貫性維持に関する判定を行い、この判定結果に基づいて、該第２の編集を前記構造化文書格納手段に格納されている構造化文書へ反映させるとともに、前記第２の記憶手段に記憶されている第２の管理情報のうち該第２の編集に係る部分を更新するための第２の処理手段とを備えたことを特徴とする。
【００１３】
なお、装置に係る本発明は方法に係る発明としても成立し、方法に係る本発明は装置に係る発明としても成立する。
また、装置または方法に係る本発明は、コンピュータに当該発明に相当する手順を実行させるための（あるいはコンピュータを当該発明に相当する手段として機能させるための、あるいはコンピュータに当該発明に相当する機能を実現させるための）プログラムとしても成立し、該プログラムを記録したコンピュータ読取り可能な記録媒体としても成立する。
【００１４】
本発明によれば、サーバ上に格納されている構造化文書を、複数のクライアント上で並行して編集する場合でも、ユーザの編集意図をより豊富に柔軟に取り込むことが可能になる。
【００１５】
【発明の実施の形態】
以下、図面を参照しながら発明の実施の形態を説明する。
【００１６】
まず、本実施形態の概要について説明する。
【００１７】
本実施形態では、ユーザがクライアントで行った編集を適切な単位に分割し、この単位ごとに、コンフリクト判定、サーバへの反映をする。ユーザが行った編集の分割は、以下に示した２段階で行うことにより、適切な単位へ分割することが可能である。
【００１８】
ここで、構造化文書の編集が適切な単位に分割されているとは、具体的には、以下の２つの性質を満たしていることを指す。
独立性：編集の単位全体のうち任意の一部を省略し、さらに編集の単位を任意の順番に入れ替えてサーバに反映した場合、得られる文書が必ず（ｗｅｌｌ−ｆｏｒｍｅｄな）構造化文書になる。
極小性：独立性を満たしながらこれ以上小さな編集の単位に分割することが困難である。
【００１９】
前述の通り、編集全体を適切な単位に分割し、この単位ごとにコンフリクト判定、サーバへの反映を行うことから、分割した編集の単位のうち一部がサーバに反映され、一部はサーバに反映されない。その場合でも、文書が構造化文書の形式を満たしているという性質が「独立性」である。
【００２０】
また、コンフリクト判定時に、個々の編集の単位がなるべく小さくなっていればいるほど、コンフリクトが起こっていると判定される確率を低く抑えることが可能である。個々の編集の単位がこれ以上小さな単位に分割することが難しいという性質が「極小性」である。
【００２１】
２段階の分割とは、具体的には、以下の２つの手続きである。
１つは、文字情報編集と構造情報編集への分割の手続きである。
図３０に示すように、構造化文書の持つ情報には、文字情報と構造情報の２種類があるが、これら２種類の情報が多くの場合において互いに独立であるととらえると、これに対応して、構造化文書の編集には、文字情報に関する編集と構造情報に関する編集との２種類があり、これら２種類の編集も互いに独立であるととらえることが可能である。例えば、論文の編集の例で言うと、ある段落の内容を変更すること（文字情報の編集）と、この段落の位置を移動すること（構造情報の編集）とは、互いに独立であるととらえる。この性質を利用して、構造化文書の編集全体を文字情報の編集と構造情報の編集とに分割し、分けられた単位ごとに、コンフリクト判定し、サーバへの反映を行う。
もう１つは、構造情報編集の分割の手続きである。
もし、構造化文書の編集全体を文字情報に関する編集と構造情報に関する編集とに分割しただけでは、適切な編集の単位に分割されていない場合には、さらに、構造情報に関する編集を適切な単位に分割し、分けられた単位ごとに、コンフリクト判定し、サーバへ反映する。
【００２２】
構造化文書の構造情報の編集を、適切な単位に分割する際には、以下の３つの手順で行う。
第１に、編集前の構造化文書の構造情報と編集後の構造化文書の構造情報とから（後述する編集前後のＸＴグラフ（ＸＭＬ  ｔｏｐｏｌｏｇｙ  グラフ  ｏｒＸＭＬ  ｔｒｅｅ  グラフ）から）、構造化文書の構造情報に関する編集全体を表現するデータ構造（後述する編集グラフ）を求める。
第２に、上記データ構造を、構造情報に関する編集のアトミックな単位を表現するデータ構造（後述するオルターネイティング・リング）に分割する。この手続きは、構造化文書に対して行われた構造情報に関する編集を小さな単位に分割することに相当する。
第３に、アトミックなデータ構造いくつかをまとめて、アトミックなデータ構造のグループを作成する。この手続きは、小さく分け過ぎてしまった編集の小さな単位をまとめ、適切な編集の単位を作成することに相当する。
【００２３】
構造化文書の編集全体を、第１に文字情報の編集と構造情報の編集とに分割し、第２に必要に応じて構造化文書の構造情報の編集を適切な単位に分割を行う、という２段階の分割を用いると、従来の一貫性維持方式と比較して、より適切な編集の単位に分割することが可能である。この結果、本実施形態の構造化文書の一貫性維持方式は、従来の一貫性維持方式と比較して、より適切な編集の単位で、コンフリクト判定、サーバへの反映を行うため、ユーザの編集意図をより豊富に柔軟に取り込むことが可能になる。
【００２４】
以下では、本実施形態をより詳しく説明する。
【００２５】
図１に、本発明の一実施形態に係る構造化文書の一貫性維持システムの構成例を示す。このように、本システムは、大きく分けて、サーバ３とクライアント１からなる。図１では、１つのクライアントのみ示しているが、複数のクライアントが存在して構わない。また、サーバ３とクライアント１とは、ネットワークを通じて結合される別々の装置でもよいし、サーバ３とクライアント１とが同一の装置に搭載されたものとして存在していてもよい。
【００２６】
図１に示されるように、本実施形態のサーバ３は、格納部３１、通信部３２、編集抽出部３３、編集分割部３４、構造情報編集表現部３５、構造情報編集分割部３６、構造情報編集併合部３７、構造情報編集一貫性判定部３８、文字情報編集一貫性判定部３９を備えている。また、図１に示されるように、本実施形態のクライアント１は、表示・編集部１１、通信部１２を備えている。
【００２７】
なお、図１の構成例では、編集抽出部３３、編集分割部３４、構造情報編集表現部３５、構造情報編集分割部３６および構造情報編集併合部３７の全てがサーバ中に配置されるシステム構成を取っているが、その代わりに、それらの全部又は一部をクライアント中に配置するシステム構成も可能である。例えば、（１）編集抽出部３３がクライアント中に配置されるシステム構成、（２）編集抽出部３３および編集分割部３４がクライアント中に配置されるシステム構成、（３）編集抽出部３３、編集分割部３４、構造情報編集表現部３５、構造情報編集分割部３６および構造情報編集併合部３７の全てがクライアント中に配置されるシステム構成なども可能である。さらに、構造情報編集併合部３７を設けないシステム構成も可能である。
【００２８】
図１のクライアントの各構成要素の機能は、以下の通りである。
【００２９】
表示・編集部１１は、表示編集を行うためのものである。
【００３０】
通信部１２は、サーバ３との間で通信を行うためのものである。
【００３１】
図１のサーバの各構成要素の機能は、以下の通りである。
【００３２】
格納部３１は、構造化文書を格納するためのものである。
【００３３】
通信部３２は、クライアント１との間で通信を行うためのものである。
【００３４】
編集抽出部３３は、編集を行う前の構造化文書と編集を行った後の構造化文書とを比較し、構造化文書のどの部分に対してどのような編集が行われたかを求める。なお、この手続きを行う際には、編集を行う前と編集を行った後の構造化文書において、どのエレメントとどのエレメントが対応するかを見付けなければならない。本実施形態では、構造化文書は、編集の前後で値が変わらない識別子を保持しているものとし、この識別子を用いて上記の対応を見付けるものとする。
【００３５】
編集分割部３４は、編集全体を文字情報に関する編集と構造情報に関する編集とに分割する。
【００３６】
構造情報編集表現部３５は、編集前の構造化文書の「構造情報を表現するグラフ」と編集後の構造化文書の「構造情報を表現するグラフ」とから、構造化文書の「構造情報に関する編集全体を表現するグラフ」を求める。なお、「構造情報を表現するグラフ」を、ＸＴグラフと呼ぶものとする。また、「構造情報に関する編集全体を表現するグラフ」を、編集グラフと呼ぶものとする。
【００３７】
構造情報編集分割部３６は、構造化文書に対して行われた構造情報に関する編集を、アトミックな単位に分割する。なお、本実施形態では、「構造情報に関する編集のアトミックな単位」として、後述するオルターネイティング・リングを用いる。以下では、構造情報に関する編集のアトミックな単位を、オルターネイティング・リングと呼んで説明する。
【００３８】
構造情報編集併合部３７は、構造情報編集分割部３６によって求められた、構造化文書に対して行われた構造情報に関する編集のアトミックな単位すなわちオルターネイティング・リングを、適切なグループにまとめる。
【００３９】
構造情報編集一貫性判定部３８は、構造化文書に対して行われた個々の構造情報に関する編集が一貫性を維持しているか、それとも一貫性を崩しているか判定する。一貫性を維持すると判定された構造情報に関する編集は、格納部３１に格納されている構造化文書に反映し、一貫性を崩していると判定された構造情報に関する編集は、格納部３１に格納されている構造化文書に反映しない。
【００４０】
文字情報編集一貫性判定部３９は、構造化文書に対して行われた個々の文字情報に関する編集が一貫性を維持しているか、それとも一貫性を崩しているか判定する。一貫性を維持すると判定された文字情報に関する編集は、格納部３１に格納されている構造化文書に反映し、一貫性を崩していると判定された構造情報に関する編集は、格納部３１に格納されている構造化文書に反映しない。
【００４１】
以下では、図１のサーバの構造情報編集表現部３５、構造情報編集分割部３６、構造情報編集併合部３７、文字情報編集一貫性判定部３９、および構造情報編集一貫性判定部３８における処理に関する詳細な説明を順番に行う。
【００４２】
まず、構造情報編集表現部３５における処理に関して説明する。
【００４３】
構造情報編集表現部３５は、前述のように、編集前の構造化文書の構造情報を表現するＸＴグラフと編集後の構造化文書の構造情報を表現するＸＴグラフとから、構造化文書の構造情報に関する編集全体を表現する編集グラフを求める。
【００４４】
ここでは、最初に、構造化文書のＸＴグラフについて説明を行い、次いで、構造化文書のＸＴグラフを用いて構造情報に関する編集全体を表現するグラフすなわち編集グラフについて説明を行う。
【００４５】
まず、構造化文書のＸＴグラフについて説明する。
【００４６】
構造化文書のエレメントのローカルな構造情報は、このエレメントの「左隣のエレメント」、「右隣のエレメント」、「親エレメント」によって決まる。よって、構造化文書の編集によって、構造化文書中のエレメントに関するローカルな構造情報が編集されたかどうかは、編集の前後においてこのエレメントの左隣のエレメント、右隣のエレメント、親エレメントが変化したかどうかによって決まる。
【００４７】
図２（ａ）に例示した構造化文書の構造情報を表現する方法は何通りか考えられるが、本実施形態では、編集の前後において構造化文書のエレメントに関するローカルな構造情報が編集されたかどうかを検出する目的に適した、図２（ｂ）に例示したようなグラフ（ＸＴグラフ）を用いる。
【００４８】
グラフの各頂点は、構造化文書の各エレメントに１対１に対応する。もしエレメントが右側に兄弟エレメントを持つ場合には、グラフはこのエレメントを開始頂点とし隣り合う右の兄弟エレメントを終了頂点とする「右向き辺」（この辺ラベルを２つの頂点の親頂点の識別子とする）を持ち、右側に兄弟エレメントを持たない場合には、このエレメントを開始頂点とし親エレメントを終了頂点とする「上向き辺」（この辺ラベルを終了頂点の識別子とする）を持つ。また、もしエレメントが子エレメントを持つ場合には、このエレメントを開始頂点とし一番左の子エレメントを終了頂点とする「下向き辺」（この辺ラベルを開始頂点の識別子とする）を持ち、エレメントが子エレメントを持たない場合には、このエレメントを開始頂点とし自分自身を終了頂点とする「下上向き辺」（この辺ラベルを開始頂点の識別子とする）を持つ。
【００４９】
このような構造化文書の構造情報を表現するＸＴグラフにおいて各頂点に接続する辺が変化したかどうかをチェックするだけで、この頂点に関するローカルな構造情報が編集されたかどうかを判定することが可能である。
【００５０】
次に、構造化文書のＸＴグラフを用いて構造情報に関する編集全体を表現する編集グラフについて説明する。
【００５１】
より具体的には、本実施形態では、構造化文書のＸＴグラフを用いて、構造化文書の構造情報の編集をシミュレートするグラフを導入する。すなわち、実際に構造化文書におけるどの部分にどのような編集がどのような順番に行われたかは、編集開始前と終了後の構造化文書を比較しただけでは分からない。そこで、編集前後の構造化文書を比較することにより、編集をシミュレートする。
【００５２】
編集前の構造化文書と編集後の構造化文書とから、以下に示す手順で編集グラフを作成する。
【００５３】
第１に、編集前の構造化文書のＸＴグラフを作成する。ただし、ここで、グラフ中のすべての辺は黒で彩色する。したがって、編集前の構造化文書のＸＴグラフ中の各辺は、以下に示す５つの情報を保持する。
（１）辺の開始頂点
（２）辺の終了頂点
（３）辺の向き
（４）辺のラベル
（５）辺の色（黒）
なお、辺の色＝黒の情報を保持するとは、実際には、例えば、辺の色を示す属性情報として、０または１のうちの予め定められた一方（例えば、０）を保持することである。なお、後に参照する各図では、「辺の色」＝黒の情報を持つ辺は、実線で表すものとする。
【００５４】
第２に、編集後の構造化文書のＸＴグラフを作成する。ただし、ここで、グラフ中のすべての辺は赤で彩色する。したがって、編集後の構造化文書のＸＴグラフ中の各辺は、以下に示す５つの情報を保持する。
（１）辺の開始頂点
（２）辺の終了頂点
（３）辺の向き
（４）辺のラベル
（５）辺の色（赤）
なお、辺の色＝赤の情報を保持するとは、実際には、例えば、辺の色を示す属性情報として、０または１のうちから上記の辺の色＝黒に割り当てたものとは異なる値（例えば、１）を保持することである。なお、後に参照する各図では、「辺の色」＝赤の情報を持つ辺は、点線で表すものとする。
【００５５】
第３に、編集前のＸＴグラフと編集後のＸＴグラフとを重ねて新しいグラフ（編集グラフ）を作成する。編集前のＸＴグラフと編集後のＸＴグラフとを重ねて編集グラフを作成するとは、より具体的には、編集前の構造化文書のＸＴグラフ中のすべての頂点と辺、および編集後の構造化文書のＸＴグラフ中のすべての頂点と辺を含むグラフを作成することである。
【００５６】
図３に、編集前のＸＴグラフＧb（図中の（ｂ））と、編集後のＸＴグラフＧa（図中の（ａ））と、編集前後のＸＴグラフＧbおよびＧaから作成される編集グラフＧc（図中の（ｃ））を示す。なお、上記のように、図３では、黒辺を実線で表し、赤辺を点線で表している。
【００５７】
ここで、構造化文書の構造情報に関する編集全体を表現する編集グラフについて、グラフの辺の色の交換という手続きを考える。この色の交換には、以下の２通りの手続きが存在する。
（１）現在辺の色が黒の場合には、赤で再彩色する（例えば、辺が保持する「辺の色」の値を、０から１に変更する）。
（２）現在辺の色が赤の場合には、黒で再彩色する（例えば、辺が保持する「辺の色」の値を、１から０に変更する）。
【００５８】
なお、以下では、「色の交換」を、スイッチと呼ぶものとする。
【００５９】
図３（ｃ）に示した構造化文書の編集グラフＧcにおいて、黒の辺（図中の実線の辺がこれに相当する）のみから構成されるグラフは、編集前の構造化文書のＸＴグラフＧbに等しい。また、編集グラフＧcにおいて、すべての辺をスイッチした結果得られる編集グラフＧ’cを考えると、編集グラフＧ’cにおいて黒の辺（図中の編集グラフＧcにおける点線の辺がこれに相当する）のみから構成されるグラフは、（辺の色の違いを除いて）編集後の構造化文書のＸＴグラフＧaに等しい。したがって、構造化文書の構造情報の編集は、構造化文書の構造情報に関する編集全体を表現する編集グラフＧcにおける辺のスイッチによってシミュレートすることが可能であり、編集全体は編集グラフＧc中すべての辺のスイッチによってシミュレートされる。
【００６０】
なお、「黒の辺のみから構成されるグラフ」を、黒サブグラフと呼ぶものとする（「赤の辺のみから構成されるグラフ」は、同様に、赤サブグラフと呼ばれる）。
【００６１】
次に、構造情報編集分割部３６における処理に関して説明する。
【００６２】
構造情報編集分割部３６は、前述のように、構造化文書に対して行われた構造情報に関する編集を、アトミックな単位（オルターネイティング・リング）に分割する。
【００６３】
前述のように、構造化文書の構造情報に関する編集は、編集前後の構造化文書から作成される編集グラフ中のすべての辺のスイッチによってシミュレートされる。そこで、構造化文書の構造情報に関する編集の分割は、構造化文書の編集グラフ中のすべての辺を（より厳密には、構造化文書の編集グラフ中のすべての辺のスイッチを）いくつかのグループに分けることに帰着される。
【００６４】
構造化文書の文字情報に関する編集全体を適切な単位に分割し、この単位ごとに、コンフリクト判定、サーバへの反映を行うことから、分割した編集の単位のうち一部がサーバに反映され、一部はサーバに反映されない。その場合でも文書が構造化文書の形式を満たす分割を求めなければならない。
【００６５】
上記の内容を構造化文書の編集グラフを用いて説明すると、構造化文書の編集グラフ中のすべての辺を（より厳密には、構造化文書の編集グラフ中のすべての辺のスイッチを）いくつかのグループに分けたもののうち、「独立性」を満たしているもの（グループ全体のうち任意の一部のグループを省略し、さらにグループを任意の順番に入れ替えスイッチを行った結果得られる編集グラフにおける黒サブグラフが、構造化文書になっているもの）を求めなければならないということである。
【００６６】
構造化文書の編集グラフを分割する方法は一般に複数あるが、構造化文書の編集グラフの辺全体の集合は自明な構造化文書の編集グラフの分割である。
【００６７】
次に、構造化文書の構造情報に関する編集の分割を用いて、構造化文書の構造情報に関する編集の「適切な」分割を定義する。
【００６８】
構造化文書の編集グラフの分割（構造化文書の編集グラフ中のすべての辺を「独立性」を満たすグループに分けたもの）のうち、「極小性」を満たしているもの（これ以上小さな辺のグループに分割することが困難であるもの）が、適切な分割である。
【００６９】
構造化文書の構造情報に関する編集の分割は、自明なものも含めて一般的に複数存在するが、個々の辺のグループが小さければ小さいほど、グループ単位で、コンフリクト判定、サーバへの反映を行う際に、他のユーザが行った編集とコンフリクトしないと判定される確率が高くなるため、ユーザの編集意図をより豊富に柔軟に取り込むことが可能である。
【００７０】
図４（ａ）に示した構造化文書の編集グラフにおいて（ただし、図４では、グラフが煩雑にならないように下上向き辺は省略している）、
辺（１，２，下向き，１，黒）
をスイッチした結果得られる図４（ｂ）に示した構造化文書の編集グラフにおける黒サブグラフは、構造化文書の構造情報を表現しない（図４（ｃ）参照）。
【００７１】
明らかに、ある構造化文書の編集グラフにてただ１つの辺のスイッチを行った結果得られる編集グラフは、常にその黒サブグラフが構造化文書を表現するわけではないことがわかる。
【００７２】
これは、
辺（１，２，下向き，１，黒）
をスイッチした結果、頂点１を開始頂点とし頂点１の子頂点を終了頂点とする黒辺がなくなったからであり、この編集グラフにおける黒サブグラフが構造化文書の構造情報を表現するように保つためには、
辺（１，２，下向き，１，黒）
をスイッチするのと同時に、
辺（１，３，下向き，１，赤）
もスイッチしなければならない。
【００７３】
すると、今度は、
辺（１，３，下向き，１，赤）
をスイッチした結果、頂点３を終了頂点とする黒辺が２本になったので、この編集グラフにおける黒サブグラフが構造化文書の構造情報を表現するように保つためには、
辺（１，３，下向き，１，赤）
をスイッチするのと同時に、
辺（２，３，右向き，１，黒）
もスイッチしなければならない。
【００７４】
このようなスイッチの連鎖は、「この構造化文書の編集グラフにおける黒サブグラフが構造化文書の構造情報を表現するように保つためには、
辺（３，２，下向き，１，赤）
をスイッチするのと同時に、
辺（１，２，下向き，１，黒）
もスイッチしなければならない」、というように、一番目にスイッチした辺に戻るまで続く。
【００７５】
上記の通り、構造化文書の構造情報に関する編集全体を表現する編集グラフにおける黒サブグラフが、構造化文書の構造情報を表現するように保つためには、常に同時にスイッチしなければならない辺のグループが存在することが分かる。この辺のグループが、「構造情報に関する編集のアトミックな単位」としての「オルターネイティング・リング」である。
【００７６】
構造化文書の編集グラフのすべての辺は、構造情報に関する編集のアトミックな単位すなわちオルターネイティング・リングに分割することができ、図４（ａ）の構造化文書の編集グラフのすべての辺は、図５に示した７つの構造情報に関する編集のアトミックな単位すなわちオルターネイティング・リングに分割される。
【００７７】
色以外が同一な２つの辺（開始頂点、終了頂点、辺向き、辺ラベルが同一な２つの辺）からなるオルターネイティング・リングは、自明なオルターネイティング・リングである。自明なオルターネイティング・リングをスイッチする前後において、構造化文書の編集グラフは不変である。図５には、５つの自明なオルターネイティング・リングが含まれている。
【００７８】
次に、構造情報編集併合部３７における処理に関して説明する。
【００７９】
構造情報編集併合部３７は、前述のように、構造情報編集分割部３６によって求められた構造情報に関する編集のアトミックな単位すなわちオルターネイティング・リングを、適切なグループにまとめる。
【００８０】
オルターネイティング・リングより小さな辺グループが「極小性」を満たさないことは、上記の内容から明らかである。ただし、オルターネイティング・リングの中には、編集の単位として小さすぎて「独立性」を満たさないものが存在する。そこで、「独立性」を満たさないオルターネイティング・リングをまとめて、構造情報に関する編集のアトミックな単位のグループすなわちオルターネイティング・リングのグループを作成する。この手続きは、小さく分け過ぎてしまった編集の小さな単位をまとめ適切な編集の単位を作成することに相当する。オルターネイティング・リングが編集の単位として小さ過ぎる場合とは、オルターネイティング・リングが「独立性」を満たさないために、スイッチを実行した結果得られる編集グラフにおける黒サブグラフが構造化文書を表現しない場合のことを意味し、具体的には、黒サブグラフが、
（１）複数の親頂点を持つ頂点を含む
（２）親頂点を持たない頂点を含む
（３）祖先・子孫頂点が自分自身になる頂点を含む
という３通りの場合が存在する。
【００８１】
以下、３通りのそれぞれについて、オルターネイティング・リングをまとめるアルゴリズムについて説明する。
【００８２】
＜複数の親頂点を持つ場合＞
まず、（１）の複数の親頂点を持つ頂点を含む場合にオルターネイティング・リングをまとめるアルゴリズム例について説明する。
【００８３】
図３に示した構造化文書の編集グラフは、
（１）｛（４，３，右向き，２，黒），（６，３，右向き，５，赤），（６，５，上向き，５，黒），（４，５，上向き，２，赤）｝と、
（２）｛（２，４，下向き，２，黒），（２，７，下向き，２，赤），（５，７，下向き，５，黒），（５，６，下向き，５，赤），（７，６，右向き，５，黒），（７，２，上向き，２，赤），（３，２，上向き，２，黒），（３，４，右向き，５，赤）｝、
の２つの自明でないオルターネイティング・リングを持つ。
【００８４】
オルターネイティング・リング（１）をスイッチした結果得られる構造化文書の編集グラフを図６（ａ）に示し、図６（ａ）の編集グラフにおける黒サブグラフを図６（ｂ）に示す。
【００８５】
図６（ｂ）の黒サブグラフの頂点４に注目すると、この頂点は、辺（４，５，上向き，５）の開始頂点であることから、頂点４は頂点５の子頂点であり、辺（２，４，下向き，２）の終了頂点であることから、頂点４は頂点２の子頂点である。頂点４は複数の親頂点を持つため、図６（ｂ）に示した黒サブグラフは、構造化文書の構造情報を表現していない。
【００８６】
図６（ｂ）の黒サブグラフ中のある頂点に注目した際に、この頂点を終了頂点とする右向きまたは下向き辺のラベルと、この頂点を開始頂点とする右向きまたは上向き辺のラベルが異なることが原因で、黒サブグラフが複数の親頂点を持つ頂点を含む（具体的には、この例の場合、頂点３を終了頂点とする右向き辺のラベル５と頂点３を開始頂点とする上向き辺のラベル２が異なり、頂点４を終了頂点とする下向き辺のラベル２と頂点４を開始頂点とする右向き辺のラベル５が異なる）。この場合には、下記の方法を用いて複数のオルターネイティング・リングを同一グループにまとめることで、適切な編集の単位を構成することができる。
【００８７】
図７（ａ）に示した通り、黒サブグラフが構造化文書を表現するような編集グラフの各頂点は、
（１）この頂点を開始頂点とし右向きまたは上向きの辺を含むオルターネイティング・リング、
（２）この頂点を終了頂点とし右向きまたは下向きの辺を含むオルターネイティング・リング、
の２つのオルターネイティング・リングを持つ。
【００８８】
例えば、図３に示した構造化文書の編集グラフの頂点４は、前述の２つのオルターネイティング・リングを持つ（図７（ｂ）参照）。
【００８９】
図７（ｂ）に示すように、オルターネイティング・リング（１）において、この頂点を開始頂点とする２つの辺の辺ラベルが異なる場合に（オルターネイティング・リング（２）において、この頂点を終了頂点とする２つの辺の辺ラベルが異なる場合に）、オルターネイティング・リング（１）とオルターネイティング・リング（２）を同一グループにまとめる。
【００９０】
オルターネイティング・リングを上記方法で同一グループにまとめることにより、複数の親頂点を持つことを防ぐことができる。
【００９１】
＜親頂点を持たない場合＞
次に、（２）の親頂点を持たない頂点を含む場合にオルターネイティング・リングをまとめるアルゴリズム例について説明する。
【００９２】
図８（ａ）に示した構造化文書の編集グラフは（ただし、図８（ａ）では、グラフが煩雑にならないように下上向き辺は省略している）、
（１）｛（４，１，上向き，１，赤），（６，１，上向き，１，黒），（６，３，右向き，１，赤），（２，３，右向き，１，黒），（２，５，右向き，１，赤），（４，５，右向き，１，黒）｝と、
（２）｛（１，４，下向き，１，黒），（１，２，下向き，１，赤），（５，２，右向き，１，黒），（５，６，右向き，１，赤），（３，６，右向き，１，黒），（３，４，右向き，１，赤）｝、
の２つの自明でないオルターネイティング・リングを持つ。
【００９３】
オルターネイティング・リング（１）をスイッチした結果得られる構造化文書の編集グラフを図８（ｂ）に示し、図８（ｂ）の編集グラフにおける黒サブグラフを図８（ｃ）に示す。
【００９４】
図８（ｃ）の黒サブグラフの頂点２に注目すると、この頂点は、親頂点を持たないため、黒サブグラフは、構造化文書の構造情報を表現していない。
【００９５】
図８（ｃ）に示した黒サブグラフ中のあるループがループを構成する辺のラベルと同一の頂点を含まないことが原因で、この黒サブグラフが親頂点を持たない頂点を含む（具体的には、この例の場合、ループ（３，６，右向き，１），（６，３，右向き，１）が頂点１を含まず、ループ（２，５，右向き，１），（５，２，右向き，１）が頂点１を含まない）。この場合には、下記の方法を用いて複数のオルターネイティング・リングを同一グループにまとめることで、適切な編集の単位を構成することができる。
【００９６】
ここで、構造化文書の編集グラフ中のループが単一の辺ラベルのみを含む場合、このループのことを、「水平ループ」と呼ぶものとする（図９（ａ）参照）。
【００９７】
第１に、編集グラフの各頂点ｎについて、
（１）頂点ｎを含み辺ラベルｎを保持する黒の辺のみから構成される水平ループ、
（２）頂点ｎを含み辺ラベルｎを保持する赤の辺のみから構成される水平ループ、
の２つの水平ループを探し出す。
【００９８】
例えば、図８（ａ）に示した構造化文書の編集グラフの頂点１は、図９（ｂ）に示した２つの水平ループを持つ。
【００９９】
第２に、２つの水平ループの各々に関して、頂点を順番に並べた頂点列を求め（ただし、頂点列の第１頂点と最終頂点は、ともに、上記頂点ｎとする）、２つの文字列の最大共通部分列を求める。
【０１００】
例えば、図９（ｂ）に示した２つの水平ループ｛１，４，５，２，３，６，１｝と｛１，２，５，６，３，４，１｝の最大共通部分列には、｛１，５，３，１｝がある。
【０１０１】
最大共通部分列の隣り合う２つの頂点ｎi-1，ｎiに注目すると、図１０（ａ）に示した通り、
（１）第１の水平ループの辺のみを使って頂点ｎi-1と頂点ｎiを結ぶパス、
（２）第２の水平ループの辺のみを使って頂点ｎi-1と頂点ｎiを結ぶパス、
の２つのパスが存在する。
【０１０２】
例えば、図９（ｂ）の最大共通部分列｛１，５，３，１｝の隣り合う２つの頂点５，６は、図１０（ｂ）に示した２つのパスを持つ。
【０１０３】
編集グラフのオルターネイティング・リングをスイッチした結果得られる構造化文書の編集グラフにおける黒サブグラフにおいて、頂点ｎi-1と頂点ｎiとを結ぶパスが、上記パス（１）またはパス（２）のいずれにもなっていない場合には、スイッチした結果得られる構造化文書の編集グラフは、必ずしもその黒サブグラフが構造化文書を表現するものになっているとは限らない。
【０１０４】
そこで、第３に、上記２つのパス上の辺を含むオルターネイティング・リングを常に同時にスイッチさせる目的で、上記２つのパス上の辺を含むオルターネイティング・リングをすべて同一グループにまとめる。
【０１０５】
オルターネイティング・リングを上記方法で同一グループにまとめることにより、親頂点を持たないことを防ぐことができる。
【０１０６】
＜祖先・子孫頂点が自分自身になる場合＞
次に、（３）の祖先・子孫頂点が自分自身になる頂点を含む場合にオルターネイティング・リングをまとめるアルゴリズム例について説明する。
【０１０７】
図１１（ａ）に示した構造化文書の編集グラフは、
（１）｛（３，５，上向き，５，赤），（５，５，下上向き，５，黒），（５，３，下向き，５，赤），（２，３，右向き，１，黒），（２，４，右向き，１，赤），（３，４，右向き，１，黒）｝と、
（２）｛（３，５，下向き，３，黒），（４，５，下向き，４，赤），（４，４，下上向き，４，黒），（５，４，上向き，４，赤），（５，３，上向き，３，黒），（３，３，下上向き，３，赤）｝、
の２つの自明でないオルターネイティング・リングを持つ。
【０１０８】
オルターネイティング・リング（１）をスイッチした結果得られる構造化文書の編集グラフを図１１（ｂ）に示し、図１１（ｂ）の編集グラフにおける黒サブグラフを図１１（ｃ）に示す。
【０１０９】
図１１（ｃ）の黒サブグラフの頂点３に注目すると、この頂点は、辺（３，５，上向き，５）の開始頂点であることから、頂点３は頂点５の子頂点であり、辺（５，３，上向き，３）の終了頂点であることから、頂点３は頂点５の親頂点である。頂点３の祖先・子孫頂点が自分自身であるため、図１１（ｃ）に示した黒サブグラフは、構造化文書の構造情報を表現していない。
【０１１０】
図１１（ｃ）に示した黒サブグラフ中のある頂点がこの頂点を開始頂点とする上向きまたは右向き辺とこの頂点を終了頂点とする上向き辺を含むループを持つことが原因で、黒サブグラフが子孫・祖先頂点が自分自身になる頂点を含む。この場合には、下記の方法を用いて複数のオルターネイティング・リングを同一グループにまとめることで、適切な編集の単位を構成することができる。
【０１１１】
ここで、構造化文書の編集グラフ中のあるループが複数の辺ラベルを含む場合、このループのことを、「垂直ループ」と呼ぶものとする（図１２（ａ）参照）。
【０１１２】
第１に、編集グラフにおいて、垂直ループをすべて探し出す。
【０１１３】
例えば、図１１（ａ）に示した構造化文書の編集グラフは、図１２（ｂ）に示す垂直ループを持つ。この編集グラフにおける黒サブグラフと赤サブグラフがともに構造化文書を表現するものであることから、この垂直ループは、黒辺と赤辺の両方を含んでいる。
【０１１４】
もし、この垂直ループ中のすべての赤辺がスイッチされてすべての色が黒になった場合は、この構造化文書の編集グラフは、黒サブグラフが構造化文書を表現するものではなくなる。
【０１１５】
そこで、第２に、オルターネイティング・リングのスイッチを行った結果、この垂直ループ中の辺がすべて黒になることを避けるために、垂直ループ上の辺を含むオルターネイティング・リングを常に同時にスイッチさせる目的で、垂直ループ上の辺を含むオルターネイティング・リングをすべて同一グループにまとめる。
【０１１６】
オルターネイティング・リングを上記方法で同一グループにまとめることにより、祖先・子孫頂点が自分自身になることを防ぐことができる。
【０１１７】
次に、文字情報編集一貫性判定部３９における処理に関して説明する。
【０１１８】
文字情報編集一貫性判定部３９は、前述のように、編集分割部３４から与えられた文字情報に関する編集をもとにして、構造化文書に対して行われた個々の文字情報に関する編集が一貫性を維持しているか、それとも一貫性を崩しているか判定する。一貫性を維持すると判定された文字情報に関する編集は、格納部３１に格納されている構造化文書に反映し、一貫性を崩していると判定された構造情報に関する編集は、格納部３１に格納されている構造化文書に反映しない。
【０１１９】
さて、以下では、個々の文字情報に関する編集が一貫性を維持しているか、それとも一貫性を崩しているか判定するための構成・動作について説明する。
【０１２０】
ここで、本実施形態で扱う構造化文書は、図３０に示すように、エレメント名とエレメント値の２種類の文字情報を保持する（図２（ａ）の例では、例えば、ｉｄ＝３のエレメントのエレメント名＝“段落”であり、エレメント値＝“システムの概要”である）。
【０１２１】
本実施形態において、サーバ３は、現在格納している構造化文書の各エレメントのエレメント名に関する情報と、各エレメントのエレメント値に関する情報とのそれぞれを、管理テーブルに格納して管理する。
【０１２２】
なお、エレメント値の管理テーブルとエレメント名の管理テーブルとは基本的には同様であるので、ここでは、エレメント値の管理テーブルに関して説明し、エレメント値の管理テーブルに関する説明は省略する。
【０１２３】
図１３に、現在サーバ３に格納されている構造化文書のエレメントのエレメント値に関する管理テーブルの構成例を示す。
【０１２４】
図１３において、「エレメント識別子」は、サーバに格納されているエレメント値ごとに一意に付与される識別子である。
「現在のバージョン」は、サーバに格納されているエレメント値の現在のバージョンである。
「前のバージョン」は、現在サーバに格納されているエレメント値の直前にサーバに格納されていたエレメント値のバージョンである。
「クライアントの識別子」は、サーバに格納されているエレメント値を現在の値に更新したクライアントの識別子である。
「最終更新時刻」は、サーバに格納されているエレメント値をクライアントが現在の値に更新した時刻である。この時刻は、クライアントが実際に編集を行った時刻のことであり、クライアントが行った編集をサーバに反映した時刻のことではない。
「エレメント値」は、現在サーバに格納されているエレメント値である。
【０１２５】
さて、上記のように、本実施形態で扱う構造化文書は、エレメント名とエレメント値の２種類の文字情報を保持するが、これに対応して、文字情報に関する編集は、エレメント名編集とエレメント値編集の２種類が存在する。
【０１２６】
本実施形態において、クライアント１は、構造化文書のエレメント名の編集に関する情報と、エレメント値の編集に関する情報とのそれぞれを、管理テーブルに格納して管理する。
【０１２７】
なお、エレメント値の管理テーブルとエレメント名の管理テーブルのフォーマットやそれらに関する処理等は基本的には同様であるので、ここでは、エレメント値の管理テーブルに関して説明し、エレメント値の管理テーブルに関する説明は省略する。
【０１２８】
図１４に、現在クライアント１に格納されている構造化文書のエレメントのエレメント値の編集に関する管理テーブルの構成例を示す。
【０１２９】
図１４において、「エレメント識別子」は、クライアントで編集を行ったエレメント値の識別子である。
「前のバージョン」は、サーバから読み出しを行った際にエレメント値にサーバで付与されていた「現在のバージョン」である。「前のバージョン」は、クライアントでエレメント値を変更した場合であっても不変である。
「クライアントの識別子」は、エレメント値の編集を行ったクライアントの識別子である。
「更新時刻」は、エレメント値の更新を行った時刻である。クライアントでエレメント値が更新されるごとに、「更新時刻」も更新される。この時刻は、クライアントが実際に編集を行った時刻のことであり、クライアントが行った編集をサーバに反映した時刻のことではない。
「エレメント値」は、エレメントの値である。
【０１３０】
なお、エレメント名の管理テーブルの場合には、上記フォーマットにおいて「エレメント値」フィールドを、エレメント名を保持する「エレメント名」フィールドにすればよい。
【０１３１】
ここで、あるエレメント値の編集が一貫性を維持しているか、崩しているかの判定の手続きについて説明する。
【０１３２】
図１５及び図１６に、この判定手続きの処理手順の一例を示す。
【０１３３】
まず、図１３に示した管理テーブルと、図１４に示した管理テーブルにおいて、一貫性判定を行おうとしているエレメント値に対応する行を見付ける（ステップＳ１１）。
【０１３４】
次に、クライアント上でエレメント値が保持する「前のバージョン」とサーバ上でエレメント値が保持する「現在のバージョン」を比較する（ステップＳ１２）。
【０１３５】
両者が等しい場合は（ステップＳ１３）、一貫性が維持されていると判定して（ステップＳ２０）、終了する。
ステップＳ１２の比較で両者が異なっている場合（ステップＳ１３）、クライアント上でエレメント値が保持する「前のバージョン」とサーバ上でエレメント値が保持する「前のバージョン」を比較する（ステップＳ１４）。
【０１３６】
そして、両者が等しいならば（ステップＳ１５）、さらに、クライアント上でエレメント値が保持する「クライアントの識別子」とサーバ上でエレメント値が保持する「クライアントの識別子」を比較する（ステップＳ１７）。
【０１３７】
そして、両者が等しいならば（ステップＳ１７）、さらに、クライアント上でエレメント値が保持する「更新時刻」とサーバ上でエレメント値が保持する「最終更新時刻」を比較する（ステップＳ１８）。
【０１３８】
「更新時刻」が「最終更新時刻」よりも遅いまたは等しい場合には（ステップＳ１９）、一貫性が維持されていると判定して（ステップＳ２０）、終了する。一方、「更新時刻」が「最終更新時刻」よりも早い場合には（ステップＳ１９）、一貫性が維持されていないと判定して（ステップＳ２１）、終了する。
なお、ステップＳ１４またはステップＳ１６の比較で両者が異なっていたならば（ステップＳ１５またはステップＳ１７）、一貫性が維持されていないと判定して（ステップＳ２１）、終了する。
【０１３９】
エレメント名の編集が一貫性を維持しているか、崩しているかの判定の手続きも基本的には同様であり、図１５及び図１６の手順例の場合には、エレメント値をエレメント名と置き換えればよい。
【０１４０】
そして、前述したように、一貫性を維持すると判定された文字情報に関する編集は、格納部３１に格納されている構造化文書に反映し、一貫性を維持しないと判定された文字情報に関する編集は、格納部３１に格納されている構造化文書に反映しないで終了する。
【０１４１】
なお、文字情報に関する編集が一貫性を維持しないと判定された場合に、サーバに反映せず、サーバ上のログに残す、あるいは通信部を通じてユーザに通知する、あるいはサーバに反映し、一貫性が崩れていることをコメントとして付加するなどの処理を行ってもよい。もちろん、これらの他にも種々のバリエーションが可能である。
【０１４２】
また、本実施形態で示した一貫性判定方式は一例であり、これ以外にも、バージョン、クライアントの識別子、更新時刻を比較する順番が異なる方式も可能である（本実施形態で一貫性が維持すると判定している場合に一貫性が維持されていないと判定する（またはその逆）方式なども可能である）。
【０１４３】
次に、構造情報編集一貫性判定部３８における処理に関して説明する。
【０１４４】
ところで、前述したように、編集分割部３４は、編集全体を文字情報に関する編集と構造情報に関する編集とに分割し、構造情報編集表現部３５は、編集前の構造化文書の構造情報を表現するＸＴグラフと編集後の構造化文書の構造情報を表現するＸＴグラフとから、構造化文書の構造情報に関する編集全体を表現する編集グラフを求め、構造情報編集分割部３６は、構造化文書に対して行われた構造情報に関する編集を、構造情報に関する編集のアトミックな単位すなわちオルターネイティング・リングに分割し、構造情報編集併合部３７は、必要に応じて、構造情報に関する編集のアトミックな単位すなわちオルターネイティング・リングを、適切なグループにまとめる。
【０１４５】
そして、この構造情報編集一貫性判定部３８は、構造情報編集併合部３７から出力されるグラフ（または、構造情報編集分割部３６から出力されるグラフ）をもとにして、構造化文書に対して行われた個々の構造情報に関する編集（すなわち、オルターネイティング・リングのグループ）が一貫性を維持しているか、それとも一貫性を崩しているか判定する。一貫性を維持すると判定された構造情報に関する編集は、格納部３１に格納されている構造化文書に反映し、一貫性を崩していると判定された構造情報に関する編集は、格納部３１に格納されている構造化文書に反映しない。
【０１４６】
さて、以下では、構造情報に関する個々の編集が一貫性を維持しているか、それとも一貫性を崩しているか判定するための構成・動作について説明する。
【０１４７】
本実施形態において、サーバ３は、現在格納している構造化文書のＸＴグラフに関する情報を、管理テーブルに格納して管理する。
【０１４８】
図１７に、現在サーバ３に格納されている構造化文書のＸＴグラフに関する管理テーブルの構成例を示す。
【０１４９】
図１７に示した管理テーブルは、構造化文書のＸＴグラフの各頂点ごとに、当該頂点を開始頂点または終了頂点とする４つの辺（左辺、右辺、左下辺、右下辺）の情報を格納する。
【０１５０】
ただし、ここで、
「左辺」とは、当該頂点を終了頂点とする右向き又は下向きの辺のことであり、
「右辺」とは、当該頂点を開始頂点とする右向き又は上向きの辺のことであり、
「左下辺」とは、当該頂点を開始頂点とする下向き又は下上向きの辺のことであり、
「右下辺」とは、当該頂点を終了頂点とする上向き又は下上向きの辺のことである。
【０１５１】
図１７では、頂点１０の情報のみ例示しているが、実際には、管理テーブルは、ＸＴグラフ中のすべての頂点に関する情報を保持する。
【０１５２】
図１７において、「頂点識別子」は、サーバに格納されているＸＴグラフの頂点ごとに一意に付与される識別子である。
「辺タイプ」は、管理テーブルの列が情報を格納する辺のタイプである。
「辺ラベル」は、管理テーブルの列が情報を格納する辺のラベルである。
「辺向き」は、管理テーブルの列が情報を格納する辺の向きである。
「現在のバージョン」は、サーバに格納されている辺の現在のバージョンである。
「前のバージョン」は、現在のサーバに格納されている辺の直前にサーバに格納されていた辺のバージョンである。
「クライアントの識別子」は、サーバに格納されている辺を現在の値に更新したクライアントの識別子である。
「最終更新時刻」は、サーバに格納されている辺をクライアントが現在の値に更新した時刻である。この時刻は、クライアントが実際に編集を行った時刻のことであり、クライアントが行った編集をサーバに反映した時刻のことではない。
【０１５３】
一方、本実施形態において、クライアント１は、編集した構造化文書のＸＴグラフに関する情報を、管理テーブルに格納して管理する。
【０１５４】
図１８に、現在サーバ３に格納されている構造化文書のＸＴグラフに関する管理テーブルの構成例を示す。
【０１５５】
図１８に示した管理テーブルは、図１７に示した管理テーブルと同様に、構造化文書のＸＴグラフの各頂点ごとに、当該頂点を開始頂点または終了頂点とする４つの辺（左辺、右辺、左下辺、右下辺）の情報を格納する。図１８では、頂点１０の情報のみ例示しているが、実際には、管理テーブルは、ＸＴグラフ中のすべての頂点に関する情報を保持する。
【０１５６】
図１７に示した管理テーブルと図１８に示した管理テーブルとはほとんど同様の構成であるが、ただし、図１７に示した管理テーブルでは「現在のバージョン情報」と「前のバージョン情報」の２通りのバージョン情報が存在するのに対して、図１８に示した管理テーブルでは「前のバージョン情報」のみが存在する点において相違するものとなっている。
【０１５７】
クライアントの管理テーブル（図１８）の「前のバージョン」は、どのバージョンの辺に対してクライアントで編集を行ったかを表している。つまり、サーバから構造化文書を読み出した際にサーバの管理テーブルに格納されている「現在のバージョン」が、クライアントの管理テーブル（図１７）の「前のバージョン」に等しい（サーバ管理テーブルの「前のバージョン」とクライアント管理テーブルの「前のバージョン」とが対応する訳ではない）。「前のバージョン」は、クライアントで構造情報の編集を行った場合であっても不変である。
【０１５８】
なお、図１７の管理テーブルと図１８の管理テーブルとを比較して分かるように、図１８の管理テーブルは、編集において頂点１０の右辺が変更された場合を例示している。
【０１５９】
さて、前述したように、構造化文書の構造情報に関する編集は、編集前の構造情報を表現するＸＴグラフと編集後の構造情報を表現するＸＴグラフとから構成される編集グラフの辺のスイッチで表現され、構造情報に関する編集の「適切な単位」は、編集グラフの辺（オルターネイティング・リング）の集合で表現される。
【０１６０】
構造情報に関する編集の「適切な単位」が、一貫性を維持しているか、崩しているかについて判定する際には、第１に、この編集の単位を構成する各辺が一貫性を維持するか、それとも崩すかを判定する。具体的には、辺の開始頂点と終了頂点の両方に注目し、下記に示した方法を用いて、この辺のスイッチが一貫性を維持するか、崩すか判定する。開始頂点と終了頂点の両方において一貫性を維持すると判定された場合に限って、この辺のスイッチは一貫性を維持すると判定される。
【０１６１】
第２に、構造情報に関する編集の適切な単位の中の全ての辺が一貫性を維持すると判定された場合に限って、構造情報に関する編集の適切な単位全体が一貫性を維持すると判定し、構造情報に関する編集の適切な単位の中に１つでも一貫性を崩すと判定された辺が存在する場合には、構造情報に関する編集の適切な単位全体が一貫性を崩すと判定する。
【０１６２】
求めた編集の単位は、ＸＴグラフの辺集合である。編集の単位を構成する全ての辺の編集が一貫性を維持していると判定された場合に限り、編集の単位が一貫性を維持していると判定し、サーバに、この編集を反映する。
【０１６３】
また、辺の編集（スイッチ）が一貫性を維持しているか、崩しているかの判定は、辺の開始頂点、終了頂点それぞれに関して、以下の手続きを用いて行う。両方とも一貫性を維持していると判定された場合に、また、辺の編集（スイッチ）が一貫性を維持していると判定される。
【０１６４】
ここで、ある辺の編集が一貫性を維持しているか、崩しているかの判定の手続きについて説明する。
【０１６５】
図１９及び図２０に、この判定手続きの処理手順の一例を示す。
【０１６６】
まず、図１７に示した管理テーブルと、図１８に示した管理テーブルにおいて、一貫性判定を行おうとしている辺に対応する行を見付ける（ステップＳ３１）。
【０１６７】
次に、クライアント上で辺が保持する「前のバージョン」とサーバ上で辺が保持する「現在のバージョン」を比較する（ステップＳ３２）。
【０１６８】
両者が等しい場合は（ステップＳ３３）、一貫性が維持されていると判定して（ステップＳ４０）、終了する。
ステップＳ３２の比較で両者が異なっている場合（ステップＳ３３）、クライアント上で辺が保持する「前のバージョン」とサーバ上で辺が保持する「前のバージョン」を比較する（ステップＳ３４）。
【０１６９】
そして、両者が等しいならば（ステップＳ３５）、さらに、クライアント上で辺が保持する「クライアントの識別子」とサーバ上で辺が保持する「クライアントの識別子」を比較する（ステップＳ３７）。
【０１７０】
そして、両者が等しいならば（ステップＳ３７）、さらに、クライアント上で辺が保持する「更新時刻」とサーバ上で辺が保持する「最終更新時刻」を比較する（ステップＳ３８）。
【０１７１】
「更新時刻」が「最終更新時刻」よりも遅いまたは等しい場合には（ステップＳ３９）、一貫性が維持されていると判定して（ステップＳ４０）、終了する。一方、「更新時刻」が「最終更新時刻」よりも早い場合には（ステップＳ３９）、一貫性が維持されていないと判定して（ステップＳ４１）、終了する。
なお、ステップＳ３４またはステップＳ３６の比較で両者が異なっていたならば（ステップＳ３５またはステップＳ３７）、一貫性が維持されていないと判定して（ステップＳ４１）、終了する。
【０１７２】
なお、構造情報に関する編集が一貫性を維持しないと判定された場合に、サーバに反映せず、サーバ上のログに残す、あるいは通信部を通じてユーザに通知するなどの処理を行ってもよい。もちろん、これらの他にも種々のバリエーションが可能である。
【０１７３】
また、本実施形態で示した一貫性判定方式は一例であり、これ以外にも、バージョン、クライアントの識別子、更新時刻を比較する順番が異なる方式も可能である（本実施形態で一貫性が維持すると判定している場合に一貫性が維持されていないと判定する（またはその逆）方式なども可能である）。
【０１７４】
以下では、本実施形態の各種手順について説明する。
【０１７５】
まず、読み出し時の手順例を示す。
【０１７６】
サーバ３に格納されている構造化文書は、以下の手順でクライアント１に呼び出される。
【０１７７】
（１）サーバの格納部３１は、構造化文書を読み出し、サーバの通信部３２に送信する。
（２）サーバの通信部３２は、格納部３１から送信される構造化文書を受信し、クライアントの通信部１２に送信する。
（３）クライアントの通信部１２は、サーバの通信部３２から送信される構造化文書を受信し、クライアントの表示・編集部１１に送信する。
（４）クライアントの表示・編集部１１は、クライアントの通信部１２から送信される構造化文書を受信し、表示を行う。
【０１７８】
次に、書き込み時の手順例を示す。
【０１７９】
クライアントの表示・編集部１１で編集を行った構造化文書は、以下の手順でサーバに書き込まれる（反映される）。
【０１８０】
（１）クライアントの表示・編集部１１は、編集が終了した構造化文書をクライアントの通信部１２に送信する。
（２）クライアントの通信部１２は、クライアントの表示・編集部１１から送信される構造化文書を受信し、サーバの通信部３２に送信する。
【０１８１】
（３）サーバの通信部３２は、クライアントの通信部１２から送信された構造化文書を受信し、サーバの編集抽出部３３に送信する。
（４）サーバの編集抽出部３３は、サーバの通信部３２から送信された構造化文書を受信し、編集前後の構造化文書を比較して、どの部分にどんな編集が行われたかを求める。求められた編集をサーバの編集分割部３４に送信する。
（５）サーバの編集分割部３４は、サーバの編集抽出部３３で求め、送信された編集全体を受信し、文字情報に関する編集と構造情報に関する編集とに分割する。その後、文字情報に関する編集は、文字情報編集一貫性判定部３９に、構造情報に関する編集は、構造情報編集表現部３５に、それぞれ送信する。
【０１８２】
以下、（６−１）と、（６−２−１）〜（６−２−４）とは、いずれを先に行ってもよいし、並行して行ってもよい。
【０１８３】
（６−１）文字情報編集一貫性判定部３９は、編集分割部３４から送信された文字情報に関する編集を受信し、構造化文書に対して行われた個々の文字情報に関する編集が一貫性を維持しているか、それとも一貫性を崩しているか判定する。文字情報に関する編集が一貫性を維持している場合、文字情報に関する編集を格納部３１に送信する。文字情報に関する編集が一貫性を維持していない場合、文字情報に関する編集を破棄する。
【０１８４】
（６−２−１）構造情報編集表現部３５は、編集分割部３４から送信された構造情報に関する編集を受信し、構造化文書の構造情報に関する編集全体を表現する編集グラフを作成する。作成した構造化文書の編集グラフを、構造情報編集分割部３６に送信する。
（６−２−２）構造情報編集分割部３６は、構造情報編集表現部３５から送信された構造化文書の編集グラフを受信し、構造化文書の編集グラフを、構造情報に関する編集のアトミックな単位すなわちオルターネイティング・リングに分割する。つまり、構造化文書の構造情報に関する編集を、アトミックな単位に分割する。この結果得られるすべてのオルターネイティング・リングを、構造情報編集併合部３７に送信する。
（６−２−３）構造情報編集併合部３７は、構造情報編集分割部３６から送信されたオルターネイティング・リングを受信し、オルターネイティング・リングを適切なグループにまとめる。つまり、構造情報編集分割部３６で小さく分け過ぎてしまった編集をまとめて、適切な編集の単位を作成する。この結果得られるすべてのオルターネイティング・リングのグループを、構造情報編集一貫性判定部３８に送信する。
（６−２−４）構造情報編集一貫性判定部３８は、構造情報編集併合部３７から送信された構造情報に関する編集を受信し、構造化文書に対して行われた個々の構造情報に関する編集（つまり、オルターネイティング・リングのグループ）が一貫性を維持しているか、それとも一貫性を崩しているか判定する。構造情報に関する編集が一貫性を維持している場合、構造情報に関する編集を格納部３１に送信する。構造情報に関する編集が一貫性を維持していない場合、構造情報に関する編集を破棄する。
【０１８５】
（７）サーバの格納部３１は、文字情報編集一貫性判定部３９、構造情報編集一貫性判定部３８から送信された編集を受信し、編集内容を格納する。
【０１８６】
さて、以下では、具体例を用いて本実施形態を説明する。
【０１８７】
ここで、サーバ３に、図２１に示した構造化文書と図２２に示したエレメント値の管理テーブルが格納されていたとする。
【０１８８】
なお、ここでは、説明を簡略化するために、エレメント名の編集は、なされなかった場合を考える。
【０１８９】
編集の具体例としては、ユーザ１がクライアントＡを使用し、ユーザ２がクライアントＢを使用し、それらユーザが互いに異なるクライアントであるクライアントＡとクライアントＢから同一文書を並行して編集する場合を考え、クライアントＡが１７：００に、クライアントＢが１７：２０に、それぞれ上記構造化文書を読み出し、
引き続き、クライアントＡが、以下のように各時刻に各編集を行い、
“１７：４０”  ：  「alternating ring とは…」を「構造情報に関する編集のアトミックな単位とは…」に編集した。
“１８：００”  ：  「並行編集システムとは…」を「一貫性維持方式とは…」に編集した。
“１８：２０”  ：  ｉｄ＝“２”を保持する節と、ｉｄ＝“４”を保持する節の入れ替え編集を行った。
【０１９０】
一方、クライアントＢが、以下のように各時刻に各編集を行ったものとする。
“１８：４０”  ：  「alternating ring とは…」を「アトムとは…」に編集した。
“１９：００”  ：  「ＸＴグラフとは…」を「構造化文書の構造情報を表現するグラフとは…」に編集した。
“１９：２０”  ：  ｉｄ＝“５”を保持する節と、ｉｄ＝“６”を保持する段落の入れ替え編集を行った。
【０１９１】
なお、図２７に、編集から得られる、構造化文書の構造情報を表現するＸＴグラフ、構造化文書の構造情報に関する編集全体を表現する編集グラフ、構造情報に関する編集のアトミックな単位すなわちオルターネイティング・リングを示す。図２７において、（ａ）は、図２１の編集前の構造化文書のＸＴグラフである。また、（ｂ）は、図２３のクライアントＡ（ユーザ１）による編集後の構造化文書のＸＴグラフであり、（ｃ）は、（ａ）と（ｃ）のＸＴグラフから得られた編集グラフであり、（ｄ）は、（ｃ）の編集グラフから得られた非自明なオルターネイティング・リングである。一方、（ｅ）は、図２４のクライアントＢ（ユーザ２）による編集後の構造化文書のＸＴグラフであり、（ｆ）は、（ａ）と（ｅ）のＸＴグラフから得られた編集グラフであり、（ｇ）は、（ｆ）の編集グラフから得られた非自明なオルターネイティング・リングである。
【０１９２】
ここで、“１９：３０”にクライアントＡの編集結果が、サーバに対して送信されたものとする。すると、構造化文書は図２３に示した通りになり、エレメント値の管理テーブルは図２４に示した通りになる（エレメント名の管理テーブルは、変化しない）。この場合、編集は、すべてサーバに反映される。
【０１９３】
次いで、“１９：４０”にクライアントＢの編集結果を、サーバに対して送信されたものとする。すると、構造化文書は図２５に示した通りにない、エレメント値の管理テーブルは図２６に示した通りになる（エレメント名の管理テーブルは、変化しない）。この場合、クライアントＢが“１８：４０”に行った編集は、クライアントＡにより“１７：４０”に行われた編集との間でコンフリクトが発生しているのでサーバには反映されないが、それ以外の編集は、すべてサーバに反映される。
【０１９４】
以下では、構造化文書の構造情報を表現するＸＴグラフの拡張した実施形態について説明する。
【０１９５】
これまで、構造化文書の構造情報に関する編集例をいくつか説明したが、それらの例においては、構造化文書のルートエレメントの構造情報は、変更されていないものであった。構造化文書のルートエレメントは親エレメントを持たないため、ルートエレメントの構造情報を変更する場合には、これまで説明してきた構造化文書の構造情報を表現するＸＴグラフを拡張し、構造化文書のルートエレメントが仮想的に親エレメントを持つとみなすことによって、これまで説明してきた構造化文書の一貫性維持方式を適用することが可能である。
【０１９６】
図２の構造化文書のＸＴグラフに仮想ルート頂点を追加する拡張を行った結果を図２８に示す。図２８において、頂点０が仮想ルートである。
【０１９７】
また、これまで説明した例においては、実際に行っている構造化文書の構造情報に関する編集は、エレメントの移動のみであった。構造化文書の構造情報に関する編集の主なものには、作成、削除、移動の３つがあるが、構造化文書のＸＴグラフの拡張を行うことで、作成、削除は、移動に帰着することが可能である。
【０１９８】
ここで、具体例を用いて説明する。
【０１９９】
図２９（ａ）に示した構造化文書のＸＴグラフにおいて、頂点４を作成し、頂点３を削除する編集を行って図２９（ｂ）に示した構造化文書のＸＴグラフが得られたとする。
【０２００】
このとき、編集前後の構造化文書のＸＴグラフに対して以下に説明する拡張を行えばよい（図２９（ｃ），（ｄ）参照）。
【０２０１】
第１に、構造化文書のすべてのエレメントに１対１に対応する仮想頂点１’，２’，３’，４’を、編集前後の構造化文書のＸＴグラフの仮想ルート頂点０の子頂点として追加する。
【０２０２】
第２に、構造化文書の編集によって作成された頂点４を、編集前の構造化文書のＸＴグラフの仮想頂点４’の子頂点として追加する。
【０２０３】
第３に、構造化文書の編集によって削除された頂点３を、編集後の構造化文書のＸＴグラフの仮想頂点３’の子頂点として追加する。
【０２０４】
構造化文書の構造情報を表現するＸＴグラフに対して以上の拡張を行うことにより、作成、削除は、移動に帰着することが可能であることは、明らかである。
【０２０５】
なお、以上の各機能は、ソフトウェアとして実現可能である。
また、本実施形態は、コンピュータに所定の手段を実行させるための（あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるための）プログラムとして実施することもでき、該プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
【０２０６】
なお、この発明の実施の形態で例示した構成は一例であって、それ以外の構成を排除する趣旨のものではなく、例示した構成の一部を他のもので置き換えたり、例示した構成の一部を省いたり、例示した構成に別の機能あるいは要素を付加したり、それらを組み合わせたりすることなどによって得られる別の構成も可能である。また、例示した構成と論理的に等価な別の構成、例示した構成と論理的に等価な部分を含む別の構成、例示した構成の要部と論理的に等価な別の構成なども可能である。また、例示した構成と同一もしくは類似の目的を達成する別の構成、例示した構成と同一もしくは類似の効果を奏する別の構成なども可能である。
また、この発明の実施の形態で例示した各種構成部分についての各種バリエーションは、適宜組み合わせて実施することが可能である。
また、この発明の実施の形態は、個別装置としての発明、関連を持つ２以上の装置についての発明、システム全体としての発明、個別装置内部の構成部分についての発明、またはそれらに対応する方法の発明等、種々の観点、段階、概念またはカテゴリに係る発明を包含・内在するものである。
従って、この発明の実施の形態に開示した内容からは、例示した構成に限定されることなく発明を抽出することができるものである。
【０２０７】
本発明は、上述した実施の形態に限定されるものではなく、その技術的範囲において種々変形して実施することができる。
【０２０８】
【発明の効果】
本発明によれば、サーバ上に格納されている構造化文書を、複数のクライアント上で並行して編集する場合に、ユーザの編集意図をより豊富に柔軟に取り込むことが可能になる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る構造化文書の一貫性維持システムの構成例を示す図
【図２】構造化文書の構造化を表現するグラフについて説明するための図
【図３】構造化文書の構造情報に関する編集全体を表現するグラフ（編集グラフ）について説明するための図
【図４】ただ１つの辺のスイッチ（辺の色の交換）について説明するための図
【図５】構造情報に関する編集のアトミックな単位（オルターネイティング・リング）について説明するための図
【図６】複数の親頂点を持つ場合について説明するための図
【図７】複数の親頂点を持つ場合の解決法について説明するための図
【図８】親頂点を持たない場合について説明するための図
【図９】親頂点を持たない場合の解決法について説明するための図
【図１０】親頂点を持たない場合の解決法について説明するための図
【図１１】祖先・子孫頂点が自分自身になる場合について説明するための図
【図１２】祖先・子孫頂点が自分自身になる場合の解決法について説明するための図
【図１３】サーバ側で管理される文字情報に関する管理テーブルの構成例を示す図
【図１４】クライアント側で管理される文字情報に関する管理テーブルの構成例を示す図
【図１５】エレメント値の編集が一貫性を維持しているか否かを判定する手順の一例を示すフローチャート
【図１６】エレメント値の編集が一貫性を維持しているか否かを判定する手順の一例を示すフローチャート
【図１７】サーバ側で管理される構造情報に関する管理テーブルの構成例を示す図
【図１８】クライアント側で管理される構造情報に関する管理テーブルの構成例を示す図
【図１９】辺の編集が一貫性を維持しているか否かを判定する手順の一例を示すフローチャート
【図２０】辺の編集が一貫性を維持しているか否かを判定する手順の一例を示すフローチャート
【図２１】構造化文書の具体例を示す図
【図２２】管理テーブルの具体例を示す図
【図２３】構造化文書の具体例を示す図
【図２４】管理テーブルの具体例を示す図
【図２５】構造化文書の具体例を示す図
【図２６】管理テーブルの具体例を示す図
【図２７】構造情報に関する編集の具体例を示す図
【図２８】構造化文書の構造情報を表現するグラフへの仮想ルート頂点の追加について説明するための図
【図２９】構造化文書の構造情報を表現するグラフへの仮想頂点の追加について説明するための図
【図３０】文字情報と構造情報への分割について説明するための図
【図３１】ＣＶＳを用いた構造化文書管理について説明するための図
【符号の説明】
１…クライアント
３…サーバ
１１…表示・編集部
１２，３２…通信部
３１…格納部
３３…編集抽出部
３４…編集分割部
３５…構造情報編集表現部
３６…構造情報編集分割部
３７…構造情報編集併合部
３８…構造情報編集一貫性判定部
３９…文字情報編集一貫性判定部
【図１】
0003725084.tif 000002
【図２】
0003725084.tif 000003
【図３】
0003725084.tif 000004
【図４】
0003725084.tif 000005
【図５】
0003725084.tif 000006
【図６】
0003725084.tif 000007
【図７】
0003725084.tif 000008
【図８】
0003725084.tif 000009
【図９】
0003725084.tif 000010
【図１０】
0003725084.tif 000011
【図１１】
0003725084.tif 000012
【図１２】
0003725084.tif 000013
【図１３】
0003725084.tif 000014
【図１４】
0003725084.tif 000015
【図１５】
0003725084.tif 000016
【図１６】
0003725084.tif 000017
【図１７】
0003725084.tif 000018
【図１８】
0003725084.tif 000019
【図１９】
0003725084.tif 000020
【図２０】
0003725084.tif 000021
【図２１】
0003725084.tif 000022
【図２２】
0003725084.tif 000023
【図２３】
0003725084.tif 000024
【図２４】
0003725084.tif 000025
【図２５】
0003725084.tif 000026
【図２６】
0003725084.tif 000027
【図２７】
0003725084.tif 000028
【図２８】
0003725084.tif 000029
【図２９】
0003725084.tif 000030
【図３０】
0003725084.tif 000031
【図３１】
0003725084.tif 000032