構文木の編集距離
バグ・不具合を報告
句構造などの順序付きラベル木の構造差を、最小編集費用と対応で比較する。
項目を入力・選択してから「計算する」を押してください。
選択内容に応じて、残りの入力項目を案内します。
計算結果
—費用
- ラベル変更
- —件
- 削除
- —件
- 挿入
- —件
- 一致
- —件
値を入力して計算してください。
この計算機は使いやすかったですか?
回答はサイト改善のために保存します。入力値・計算結果は送りません。
ありがとうございます。よかったら、上の共有ボタンからこの計算機を紹介しませんか?
計算方法・適用範囲・出典
計算方法
順序付き根付きラベル木で、削除・挿入・変更の費用合計を最小化。左端葉番号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。