Garsia–Wachs 算法

簡介

Garsia–Wachs 算法（Garsia–Wachs Algorithm）是計算機用來在 線性時間 內構建 最優二叉查找樹 和 字母霍夫曼碼 的有效算法。它以 Adriano Garsia 和 Michelle L. Wachs 的名字命名，他們於 1977 年發表了相關論文。

問題描述

一個整數 \(n\)，對於 \(n+1\) 個非負權值 \(w_{0},w_{1},\dots ,w_{n}\)，構造一棵有根且 \(n\) 個內部節點都有兩個子節點的二叉樹，這意味着這棵二叉樹有 \(n+1\) 個葉節點。我們將 \(n+1\) 的輸入序列與二叉樹結點順序一一映射，目標是在所有具有 \(n\) 個內部節點的可能的樹結構中找到一棵樹，使外部從根到每個葉子的路徑長度的權重和最小。

最優二叉查找樹

這個問題可以理解為 \(n\) 個有序鍵構造二叉查找樹的問題，假設樹將僅用於搜索樹中不存在的值。在這種情況下，\(n\) 個鍵將搜索值的空間劃分為 \(n+1\) 個區間，並且這些區間之一的權重可以作為搜索值落在那個區間的概率。外部路徑長度的加權和控制了查找的預期時間。

字母霍夫曼碼

這個問題也可以用作構建霍夫曼碼。這是一種通過使用二進制值的可變長度序列明確編碼 \(n+1\) 給定值的方法。在這種解釋中，值的代碼由從樹中的根到葉子的路徑上從父到子的左步和右步序列給出（例如，左為 \(0\)，右為 \(1\)）。與標準霍夫曼碼不同，以這種方式構造的霍夫曼碼是按字母順序排列的，也就是説這些二進制碼的排序順序與值的輸入順序相同。如果一個值的權重是它在編碼消息中的頻率，那麼 Garsia–Wachs 算法的輸出是將消息長度壓縮到最短的，按字母順序排列的霍夫曼代碼。

過程

Garsia–Wachs 算法一般包括三個階段：

構建一個值位於葉子的二叉樹，注意順序可能錯誤。
計算樹中根到每個葉子的距離。
構建另一個二叉樹，葉子的距離相同，但順序正確。

如上圖所示，在算法的第一階段，通過查找合併輸入序列的無序三元組構建的二叉樹（左側），和算法輸出的正確排序的二叉樹，其中葉子高度與另一棵樹一樣。

如果輸入在序列的開始和結束處增加了兩個標記值 \(\infty\)（或任何足夠大的有限值），則算法的第一階段更容易描述。所以在競賽題解中使用 Garsia–Wachs 算法時，對於一個長度為 \(n\) 的數組 \(\mathit{num}\)，我們一般定義 \(\mathit{num}[0] = \mathit{num}[n+1] = \infty\)。

第一階段維護了一個由最初為每個非標誌（non-sentinel）輸入權重創建的單節點樹組成的森林。每棵樹都與一個值相關聯，其葉子的權重之和為每個非標誌輸入權重構成一個樹節點。為了維護這些值的序列，每端會有兩個標記值。初始序列只是葉權重作為輸入的順序。然後重複執行以下步驟，每一步都減少輸入序列的長度，直到只有一棵樹包含了所有葉子：

在序列中找到前三個連續的權重值 \(x\)，\(y\)，\(z\) 使得 \(x \leq z\)。因為序列結尾的標誌值大於之前的任意兩個有限值，所以總是存在這樣的三元組。
從序列中移除 \(x\) 和 \(y\)，並創建一個新的樹節點作為 \(x\) 和 \(y\) 節點的父節點，值為 \(x+y\)。
在原來 \(x\) 的位置以前大於或等於 \(x+y\) 且距 \(x\) 最近的值的右邊重新插入新節點。因為左標誌值的存在，所以總是存在這樣的位置。

為了有效地實現這一階段，該算法可以在任何平衡二叉查找樹結構中維護當前值序列。這樣的結構允許我們在對數時間內移除 \(x\) 和 \(y\)，並重新插入它們的新父節點。在每一步中，數組中位於偶數索引上直到 \(y\) 值的權重形成了一個遞減序列，位於奇數索引位的權重形成另一個遞減序列。因此，重新插入 \(x+y\) 的位置可以通過在對數時間內對這兩個遞減序列使用平衡樹執行兩次二分查找找到。通過從前一個三元組 \(z\) 值開始的線性順序搜索，我們可以在總線性時間複雜度內執行對滿足 \(x \leq z\) 的第一個位置的搜索。

Garsia–Wachs 算法的第三階段的證明，即存在另一棵具有相同距離的樹並且這棵樹提供了問題的最優解，是很重要的。但是由於其證明方式有多種且過於複雜，此處略去。在第三階段為正確的前提下，第二和第三階段很容易在線性時間內實現。因此，在長度為 \(n\) 的輸入序列上，Garsia–Wachs 算法的總時間複雜度為 \(O(n\log n)\)。

應用

函數性編程語言 Haskell 的 garsia-wachs package 對 Garsia–Wachs 算法做了函數性實現。它主要用於構建最佳搜索表，或者以最優複雜度平衡 rope 數據結構。

註釋

rope 是 Haskell 語言中用於操作帶有可選註釋的字節串（bytestring）手指樹的工具。

例題

POJ 1738 An old Stone Game

有一個古老的石頭遊戲。在遊戲開始時，玩家將 \(n\)(\(1 \leq n \leq 50000\)) 堆石頭排成一行。目標是將石頭合併成一堆，規則如下：在遊戲的每一步，玩家可以將相鄰的兩個堆合併成一個新的堆。分數是新堆的石頭總數。請計算總分中的最小值。

解題思路

石子合併的題目很經典，一般我們可以用區間 DP 解答，但是當數據量很大，例如此題中的 \(n\)(\(1 \leq n \leq 50000\)) 時，用 Garsia–Wachs 算法求解更高效：第一步，初始化一個大小為 \(n\) 的數組 \(\mathit{num}[n]\)，其中 \(\mathit{num}[0] = \mathit{num}[n+1] = \infty\)。第二步，每次找到一個最小的 \(i\) 使 \(\mathit{num}[i-1] \leq \mathit{num}[i+1]\)，並將 \(\mathit{num}[i-1], \mathit{num}[i]\) 合併為 \(\mathit{temp}\); 找到前面一個最大的 \(j\) 使得 \(\mathit{num}[j] > \mathit{temp}\), 將 \(\mathit{temp}\) 移到 \(j\) 後面。重複這一步直到剩餘堆數為 \(1\)。關於每次只能合併相鄰石子堆的要求，因為 \(\mathit{num}[j]\geq \mathit{num}[i-1] + \mathit{num}[i]\)，我們可以將 \(\mathit{num}[j+1]\) 到 \(\mathit{num}[i-2]\) 看成一個 \(\mathit{num}[mid]\) 的整體，所以一定是先合併 \(\mathit{sum}\)。因此沒有違背題目要求。

ATCODER N-Slimes

\(N\) 個史萊姆排成一排。最初左邊第 \(i\) 個史萊姆的大小為 \(a_{i}\)。Taro 試圖將所有史萊姆組合成一個更大的史萊姆。他會反覆執行以下操作，直到只有一個史萊姆：選擇兩個相鄰的史萊姆，並將它們組合成一個新的史萊姆。新的史萊姆的大小為 \(x+y\)，其中 \(x\) 和 \(y\) 是組合之前史萊姆的大小。這一步驟有產生 \(x+y\) 的成本。合成史萊姆時史萊姆的位置關係不會改變。找出可能發生的最小總成本。

參考資料與拓展閲讀

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用