根がなく巡回的順序のある木の距離の逐次および並列計算法
スポンサーリンク
概要
- 論文の詳細を見る
根がなく巡回的順序のある木(CO木)に対し,先祖子孫関係を保存する写像に基づく距離(TD),構造保存写像に基づく距離(SPD),強構造保存写像に基づく距離(SSPD)が定義され,それぞれの逐次計算法が提案されていた.T_a,T_bをCO木とし,その頂点数をN_a,N_b,葉の数をL_a,L_b,頂点の次数の最大値をm _a,m_bとする.本論文ではまず, T_a,T_bのTD, SPDの逐次計算法を改善する.時間計算量はそれぞれO(N_aN_bL_aL_b), O(m_aN_bN_bL _b)であり,以前に提案されているアルゴリズムより時間計算量が改善されている.次に,この計算法に基づいてTD,SPD,SSPDの並列計算法を提案する.時間計算量はすべてO(max{N_a, Nb})であり,プロセッサ数はそれぞれO(N_aL_aL_b), O(m_aN_aL_b), O(m_am_b max{Na,N_b})である.これらの計算法はすべてコストが逐次計算法の時間計算量と一致するという意味で最適である.
- 社団法人電子情報通信学会の論文
- 1996-11-25
著者
関連論文
- 根がなく巡回的順序がある木の間の距離とその計算法
- 木の距離の並列計算法
- ハッシュ法を用いた類似キー検索ファイル (メディア統合および環境統合のための高機能データベースシステム、および一般)
- 一般化LR法に基づく文脈自由言語の誤り訂正アルゴリズム
- 根がなく順序がない木の距離とその計算法
- 大型データベースのための最長共通部分列の一高速抽出法
- 大型データペースのための最長共通部分列の一高速抽出法
- 木構造図の描写アルゴリズムの効率化
- 空間に埋め込まれた木のグラフ理論的距離とその計算法
- 空間に埋め込まれた木の距離とその計算法
- 構成文字ハッシュ法に基づく綴り誤りの高速訂正法
- 根がなく巡回的順序のある木の距離の逐次および並列計算法
- 類似データ検索のためのファイル構成法
- 線図形の類似度の計算法
- B木に基づく類名表記機能ファイルシステムの構成法
- 平面に埋め込まれた木の最大類似部分を求めるアルゴリズム
- 誤ったキーでも検索できるファイル構成法