ツリー編集距離
1. 序章
このチュートリアルでは、ツリー編集距離(TED)とその計算方法について説明します。 TEDは文字列編集距離に似ていますが、ツリーで機能します。
2. ツリー編集距離(TED)とは何ですか?
TEDは、あるツリー()を別のツリー()に変換するために必要な選択操作の最小数です。通常、これらの操作は、 relabel 、 delete 、および[ X177X]ノードを挿入します。 ただし、2つのノード間のエッジの削除や作成など、エッジベースの操作を定義することもできます。 いずれの場合も、それらはにのみ作用します。
これらの操作にさまざまなコストを関連付けることもできます。次に、TEDは、に変換される最も安価な一連のアクションのコストになります。ここで、シーケンスのコストは個々のアクションの合計です。 ‘コスト。
2.1. 例
これらの2つのツリーを見てみましょう。
変換コストは次のように定義できます。
最も安価なシーケンスは次のとおりです。
そのコストはです。 そう、 。
2.2. TEDの解釈
変換操作とそのコストに依存するため、TEDはそれらの設定に関してのみ解釈できます。 さまざまな操作とコストを使用すると、さまざまな距離が得られる可能性があります。 したがって、アプリケーションで意味のある方法でそれらを選択する必要があります。
とにかく、TEDが距離公理を満たす場合、それは木の距離空間を誘発します。 これにより、それらを厳密に分析できます。
それでは、一般的なTEDとその計算方法を定義しましょう。
3. 一般的な再帰計算
ツリーで実行できる一連の操作を表し、操作のコストとします。 コストはマイナスになる可能性がありますが、すべてがプラスの場合にのみ焦点を当てます。
TEDの一般的な再帰的定義は次のとおりです。
(1)
とに応じて、指数関数的である可能性があることを除いて、その複雑さについてこれ以上言うことはできません。
3.1. メモ化
ただし、ハッシュツリーの効率的な方法を見つければ、複雑さを軽減できる可能性があります。 初めて計算するときは、ペアをハッシュしてハッシュマップに挿入します。 そうすれば、再帰に再び現れる場合、それを再度計算する必要はありません。
この特定の手法はメモ化として知られています。 一部の著者は、それを動的計画法のツールであると考えています。
4. ノードベースのTED
再帰( 1 )は、TEDの一般的なケースをカバーします。 ここでは、より具体的な運用とコストに焦点を当てます。 特に、ノードベースの再ラベル付けでは、挿入、および削除します。
4.1. オペレーション
操作について詳しく説明しましょう。 ノードを削除している間、その子を宙に浮かせたままにしないでください。 代わりに、ノードの親の新しい子としてそれらを追加します。
ノードのラベルを変更するとは、そのラベルを変更することを意味します。 例えば:
削除や再ラベル付けとは異なり、挿入には複数の引数があります。 挿入するノードとその親になるノードを指定します。
4.2. 仮定と備考
最初に重要な仮定を述べましょう:ノードがあり、左から右への順序があります。 したがって、ツリー内の任意の2つのノードについて、どちらがもう一方の左側にあるかを判断できます。
もう1つの前提は、変換中にノードを最大1回挿入、削除、または再ラベル付けできることです。 たとえば、ノードを挿入した後でノードを削除することはできません。 そうしないと、考慮すべき変換シーケンスのスペースが無限になります。
操作のコストは一定です。したがって、削除するノード()と削除するツリーの状態()に関係なく、同じコストがかかります。 挿入と再ラベル付けについても同じことが言えます。 彼らの費用にしましょう。
にノードを挿入することは、からノードを削除することと同じであるため、実装でに挿入を適用する必要はありません。 代わりに、ノードをから削除して、に挿入されたと見なすことができます。 同様に、一致するようにラベルを付け直す場合、実際にラベルを変更する必要はありません。 ツリーから両方のノードを削除し、に再ラベル付けすることを検討できます。 表記を簡単にするために、削除を。の代わりにマイナス記号で示します。
最後に、アルゴリズムのコスト関数は、距離メトリックに制限されています。 これにより、TEDは距離メトリックも計算します。 選択した非負の一定コスト関数は、この条件を満たす。
4.3. フォレストを使用したTEDの計算
その中間ステップでは、アルゴリズムはフォレストで動作します。 これは、ノードの順序付け後の番号付けを考慮することによって行われます。 ポストオーダートラバーサルの-番目のノードとします。 次に、のポストオーダートラバーサルで番号が付けられたノードで構成されるフォレストです。 例えば:
より一般的な構造を扱うことは物事を複雑にするように見えるかもしれませんが、そうではありません。 代わりに、問題が簡単になります。 ツリーをサブフォレストに分割することで、動的計画法を使用して問題を解決できます。
4.4. 再発
のポストオーダーサブフォレストとし、その右端のルートを示します。 また、(をルートとする)の右端のツリーとします。 同じ表記が。にも当てはまります。 次に、TEDを次のように計算します。
(2)
メモ化手法を使用して再発を計算できます。 たとえば、各フォレスト(ツリー)をペアとしてハッシュできます。ここで、とは元のツリーのノードのポストオーダー境界です。
森林と樹木構造には、、、および()を評価するための効率的な方法を提供する必要があります。
4.5. ツリー操作
まず、フォレストの右端のツリーのルートがノード番号であることに注目しましょう。したがって、。 そこから、になります。 との違いは、にあるが含まれていないすべてのノードで構成されるフォレストです。 同じことが他の木にも当てはまります。
ただし、()を見つけるには、より慎重に検討する必要があります。 の右の境界は、そのルートのポストオーダーインデックス、つまり、です。 ポストオーダートラバーサルルーチンを実行することで、その場で左側の境界を計算できますが、このアプローチではアルゴリズムの速度が低下します。 代わりに、ツリーを前処理し、各サブツリーの順序付け後の左境界を計算して、TEDの計算中に時間内に使用できるようにする方が効率的です。 ポストオーダートラバーサルアルゴリズムを使用して、線形時間でそれを行うことができます。
したがって、は、ルートがであるツリーの左側のポストオーダー境界が、両方のツリーのノードで使用可能であると想定します。 次に、、、およびです。 (フォレストにツリーが1つだけ含まれていない場合)、はです。 さもないと、 。
4.6. メモ化アルゴリズム
メモ化アルゴリズムを使用して計算する方法は次のとおりです。
このアルゴリズムは、ZhangおよびShashaの反復TEDアルゴリズムのメモ化バージョンです。 したがって、その複雑さは同じです。
4.7. 複雑
およびの関連する(サブ)フォレストを考慮して、これを導き出します。
フォレストは、の再帰計算に表示される場合に関連します。
()のキールートの深さを、ルートからツリー内の他のノードへのパス上のキールートノードの最大数とします。 次に、ZhangとShashaのアルゴリズムの複雑さ(したがって私たちのアルゴリズムも)はです。
結果をさらに改善することができます。 で葉の高さと数を示し、。についても同じことを行います。 張とシャシャはそれとそれを証明します。 したがって、全体的な複雑さは次のとおりです。
ツリーがバランスの場合、および、したがって、全体的な複雑さは次のようになります。
またはの場合。 ただし、ツリーが縮退していてリンクリストを表す場合、複雑さはです。 したがって、最悪の場合の複雑さは、キールートのないバージョンと同じままです。 実際には、改善されたアルゴリズムのパフォーマンスが向上することが期待されます。
4.8. シーケンスのトレース
検索アルゴリズムでパスをトレースするのと同じ方法で変換される操作の最小シーケンスをトレースできます。
、、、およびの最小値を決定すると、どの操作がその結果につながるかを覚えています。 完全なTEDを計算すると、逆の順序で操作を実行できます。
5. 結論
この記事では、ツリーの編集距離について説明しました。 多項式時間で定義する方法と計算する方法を示しました。