大約編輯距離樹 - 確切編輯路徑

我一直在尋找一種算法來有效地計算兩棵樹之間的編輯路徑，這條路徑不必對應最短的編輯距離，但最好是相對較短的路徑。大約編輯距離樹 - 確切編輯路徑

這種情況是，我有兩個目錄樹，由目錄和文件組成，並且想要計算一系列刪除，插入和重命名操作，將一個目錄樹轉換爲另一個目錄樹。

我已經嘗試過同時搜索stackoverflow和wild web，但是我找到的所有算法都是計算最短編輯距離的算法，但它們都具有高縮放因子。

所以我的問題是，當我不需要最佳距離時，有沒有更有效的方法比如「張和沙沙」？

親切的問候

2013-10-31 Vskrap

你可以試探性地假設，每當有一個文件/目錄與同名稱在每棵樹的根部，它們相互對應。遞歸處理樹的其餘部分。您可以在O（nlog n）時間內通過排序然後合併來在兩個dirs之間找到匹配的文件名，因此在最壞的情況下這將是O（nlog n），其中每個樹只包含一個其中包含n個文件的根目錄。 –

但是，如果我正確理解了你的話，這將意味着一個移動（重命名）的目錄將被視爲一個刪除和一個新的插入，如果它內部有大文件，我想要考慮非常昂貴的操作。 – Vskrap

沒錯。我的建議是使用這種方法來儘可能多地獲取低懸的水果，然後回到更困難的情況下更好的算法。順便說一句，在評論中寫@j_random_hacker（或任何用戶名）來通知該人。 –

有執行比「張和薩莎」稍微好一點的Klein algorithm，但它在空間和時間上的實際目的仍然是非常高的複雜性。

有一個算法here這實際上是一種啓發式，因爲作者濫用術語approximation。它將問題簡化爲一系列最大加權派系，它存在幾個近似值和啓發式，即使是一個貪婪的方法在這裏也能很好地執行。

樹的圖真是如此，因此可以使用graph kernel convolution approach。

如果你正在尋找一個現成的實現（一unspeficied算法，我woudl猜張或克萊恩），你可以檢查here

2013-11-04 22:22:30 Julien

回答