構文木の編集距離

句構造などの順序付きラベル木の構造差を、最小編集費用と対応で比較する。

項目を入力・選択してから「計算する」を押してください。

選択内容に応じて、残りの入力項目を案内します。

計算する内容

括弧記法 {ラベル{子}{子}}。ラベル間の空白は保持し、各木64ノード以内。

1ノードあたり。削除後は子ノードが親へ繰り上がります。

ラベルが一致する対応は費用0です。費用は0〜100万、小数6桁以内。


計算結果

値を入力して計算してください。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

順序付き根付きラベル木で、削除・挿入・変更の費用合計を最小化。左端葉番号l(i)と後順番号を用い、森間距離F(i,j)を削除F(i−1,j)+d、挿入F(i,j−1)+a、対応F(i−1,j−1)+r(両部分木の左端葉が一致)またはF(l(i)−1,l(j)−1)+T(i,j)(それ以外)の最小値で更新。Tは部分木間の最小費用。費用は小数6桁の固定小数点で計算します。

木編集距離(費用)、操作別件数、ノード対応と編集費用の明細表。

計算例(架空の数値)

各編集費用を1とすると、{S{NP}{VP}} → {S{NP}{VP{V}}} はVの挿入1件で距離1です。

適用対象と限界

兄弟順序に意味がある根付きラベル木(各木64ノード以内)。兄弟順序がない木、一般グラフ、文字列Levenshtein距離、部分木丸ごとの削除費用、構文木の意味的同値性は対象外。。

方法と出典

方法:Zhang–Shasha 1989 / ordered labeled trees / 2026-11-14 v1。データ記録日:2026-11-14。