平面に埋め込まれた木の間の距離およびその計算法
スポンサーリンク
概要
- 論文の詳細を見る
平面に埋め込まれた木は根がなく巡回的順序がある木(CO-木)と定義できる.本論文はCO-木間の三種類の距離を定義し,それぞれの計算法を提案する.三種類の距離はそれぞれTai写像に基づく距離,構造保存写像に基づく距離と強構造保存写像に基づく距離である.簡単のため,三種類の距離をそれぞれTai距離(TD),構造保存距離(SPD)と強構造保存距離(SSPD)と呼ぶ.それらの距離の定義およびそれぞれの計算法は従来の定義および計算法より簡単である.本論文で定義したTDおよびSPDは従来の定義より大きい値を取ることがあり,換言すれば,構造の相違に対して敏感である.二つのSSPDの定義は等価である.CO-木T_aとT_bの間のTD,SPDおよびSSPDの計算に要する時間計算量はそれぞれO_T(N^2_aN^2_b),O_T(m_aN_aN^2_b)およびO_T(m_am_bN_aN_b)である.ここで,N_a(N_b)とm_a(m_b)はそれぞれT_a(T_b)の頂点数とT_a(T_b)の頂点の最大次数を表す.三つの計算法の空間計算量は共にO_S(N_aN_b)である.
- 社団法人情報処理学会の論文
- 1995-11-17
著者
関連論文
- 3次元グラフ構造の最大共通部分を求めるアルゴリズム
- 点パターンマッチングアルゴリズムの効率化
- 順序がない木の間の類似度問題
- 平面に埋め込まれた木の最大共通類似部分問題
- 順序がない木の最大類似部分問題
- 外平面グラフの点部分同型判定アルゴリズム
- 順序がない木の距離を求めるアルゴリズム
- 木の最大類似部分問題とそのアルゴリズム
- 二つの外平面描写の最大共通部分の抽出について
- 木の描写アルゴリズムの効率化
- 二つの木の最大共通部分グラフを求めるアルゴリズム
- 線図形の類似度とその計算法
- 根がなく巡回的順序がある木の間の距離とその計算法
- 構造をもつものの距離と類似度
- 綴り誤りの高速訂正法
- 平面に埋め込まれた木の間の距離およびその計算法
- 拡張ハッシュ法を用いた類似キー検索ファイル
- 根がなく巡回的順序を持つ木の距離とその計算法
- 誤り訂正構文解析法 : 研究の現状と問題点(代数的コード理論および語の組合せ論)
- 大型データペースのための最長共通部分列の一高速抽出法
- 空間に埋め込まれた木のグラフ理論的距離とその計算法
- 空間に埋め込まれた木の距離とその計算法
- 節点の分離・融合操作に基づく木の距離について
- 一般化LR構文解析法に基づく文脈自由言語の誤り訂正
- 中国語高頻度単語の〓音対
- 中国語高頻度単語の品詞と近距離単語について
- 拡張可能類名表記を用いた類似キー検索ファイル
- THEORETICAL ASPECTS OF SYNTACTIC PATTERN RECOGNITION