部分木の移動を考慮した文書併合アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
1つの文書データを複数のクライアントで共有し並行編集を行う場合,文書データの併合が必要となる.本橋では,構造化文書の併合について考える.ここで,併合は2個の文書データを同じ構造に変換することにより行う.併合では,2個の文書データを順序木みなし,それらにadd(頂点の追加),del(頂点の削除),upd(ラベルの変更),および,move(部分本の移動)という操作を適用することにより,元の文書データを同じ構造に変換する.本橋では,まず,2個の文書データおよび整数Kに対して,それら文書データがコストK以下で併合可能か否かを決定する問題がNP完全であることを示す.次に,コスト最小の併合を行う操作系列を多項式時間で求めるための十分条件を示す.
- 2003-12-15
著者
関連論文
- A-4-27 大規模ディジタルシステムのSTPNによるモデル化(A-4. ディジタル信号処理)
- D-10-14 メタステーブル動作を考慮したリングアービタのペトリネット表現
- 半構造データにおけるスキーマ抽出問題の計算複雑さ
- D-6-6 高速マルチウィンドウシステムのハードウエアアーキテクチャ
- オブジェクト指向データベースにおける逆行を含む属性集合とその閉包を用いた経路式を経由するクラスの一探索法
- グラフデータベースにおける正規表現及び文脈自由文法を満たす最短経路の一探索法
- 妥当でないXPath式に対するK最適修正候補発見アルゴリズム
- オブジェクト指向データベースにおける逆行を含む経路式の航行可能性に関する考察
- オブジェクト指向データモデルにおける逆行を含む経路式の航行可能性について (時空間データベースおよび一般)
- 1P-3 限定されたXPath構文に関する充足可能性問題について(XMLと応用,学生セッション,データベースとメディア)
- 正規木文法の差分抽出問題に関する研究
- 正規木文法の差分抽出問題に関する研究
- D-001 XPath式の部分クラスに対する充足可能性判定アルゴリズム(データベース,一般論文)
- XML文書と正規木文法との間の最適編集操作列の発見(DE: データ工学理論, データ工学とメディア理解との融合)
- XML文書と正規木文法との間の最適編集操作列の発見(DE: データ工学理論, データ工学とメディア理解との融合)
- 妥当でないXMLデータに関する最適な構造変換を求めるための一手法(インターネット環境のコンテンツ技術及び一般)
- 複合オブジェクトモデルにおける逆行を含む経路式に関する考察
- 部分木の移動を考慮した文書併合アルゴリズム
- 正規木文法間の差分抽出アルゴリズムの提案
- 正規木文法間の差分抽出アルゴリズムの提案
- オンライン目録検索システム構築演習の4年間とこれから
- 部分木の移動を考慮した文書併合アルゴリズム
- 構造化文書のための併合アルゴリズム
- オブジェクト指向データベースにおける逆行を含む属性集合及びその閉包を用いた経路式について (高度データベース論文特集)
- オブジェクト指向データモデルにおける逆行を含む経路式に関する考察
- 選択的継承の可能な複合オブジェクトモデルに関する考察