Garsia–Wachs Algorithm

Introduction

Garsia–Wachs algorithm is an efficient algorithm used in computer science to construct optimal binary search trees and alphabetic Huffman codes in linear time. It is named after Adriano Garsia and Michelle L. Wachs, who published the related paper in 1977.

Problem Description

Given an integer \(n\) and \(n+1\) non-negative weights \(w_{0},w_{1},\dots ,w_{n}\), construct a rooted binary tree with \(n\) internal nodes, each having two children, meaning the binary tree has \(n+1\) leaf nodes. We map the input sequence of length \(n+1\) one-to-one with the tree's leaf nodes in order. The goal is to find, among all possible tree structures with \(n\) internal nodes, a tree that minimizes the weighted sum of the external path lengths from the root to each leaf.

Optimal Binary Search Tree

This problem can be understood as constructing a binary search tree from \(n\) ordered keys, assuming the tree will only be used to search for values not present in the tree. In this case, the \(n\) keys partition the search value space into \(n+1\) intervals, and the weight of one of these intervals can be interpreted as the probability that the search value falls within that interval. The weighted sum of external path lengths controls the expected search time.

Alphabetic Huffman Code

This problem can also be used to construct Huffman codes. This is a method for explicitly encoding \(n+1\) given values using variable-length sequences of binary digits. In this interpretation, the code for a value is given by the sequence of left and right steps from parent to child along the path from the root to the leaf in the tree (e.g., left as \(0\), right as \(1\)). Unlike standard Huffman codes, Huffman codes constructed this way are alphabetic, meaning the binary codes are sorted in the same order as the input values. If a value's weight is its frequency in the encoded message, then the output of the Garsia–Wachs algorithm is the alphabetic Huffman code that compresses the message length to the shortest.

Process

The Garsia–Wachs algorithm generally consists of three stages:

Construct a binary tree with values at the leaves, noting that the order may be incorrect.
Compute the distance from the root to each leaf in the tree.
Construct another binary tree with the same leaf distances but in the correct order.

As shown in the figure above, the first stage of the algorithm builds a binary tree (left) by merging unordered triples from the input sequence, and the algorithm outputs a correctly ordered binary tree (right) where the leaf heights match those of the other tree.

The first stage of the algorithm is easier to describe if two sentinel values \(\infty\) (or any sufficiently large finite value) are added to the beginning and end of the input sequence. Therefore, when using the Garsia–Wachs algorithm in competitive programming solutions, for an array \(\mathit{num}\) of length \(n\), we typically define \(\mathit{num}[0] = \mathit{num}[n+1] = \infty\).

The first stage maintains a forest consisting initially of single-node trees created for each non-sentinel input weight. Each tree is associated with a value, which is the sum of the weights of its leaves, forming a tree node for each non-sentinel input weight. To maintain the sequence of these values, two sentinel values are placed at each end. The initial sequence is simply the leaf weights in input order. Then the following steps are repeated, each step reducing the length of the input sequence until only one tree contains all leaves:

Find the first three consecutive weight values \(x\), \(y\), \(z\) in the sequence such that \(x \leq z\). Because the sentinel values at the end of the sequence are larger than any two finite values before them, such a triple always exists.
Remove \(x\) and \(y\) from the sequence and create a new tree node as the parent of the nodes for \(x\) and \(y\), with value \(x+y\).
Reinsert the new node to the right of the nearest value before \(x\) that is greater than or equal to \(x+y\). Due to the left sentinel value, such a position always exists.

To implement this stage efficiently, the algorithm can maintain the current value sequence in any balanced binary search tree structure. Such a structure allows us to remove \(x\) and \(y\) and reinsert their new parent node in logarithmic time. In each step, the weights at even indices up to the value \(y\) form a decreasing sequence, and the weights at odd indices form another decreasing sequence. Therefore, the position to reinsert \(x+y\) can be found by performing two binary searches on these two decreasing sequences using a balanced tree in logarithmic time. By performing a linear sequential search starting from the previous triple's \(z\) value, we can search for the first position satisfying \(x \leq z\) in overall linear time complexity.

The proof for the third stage of the Garsia–Wachs algorithm, that there exists another tree with the same distances and that this tree provides the optimal solution to the problem, is important. However, due to the variety and complexity of the proof methods, it is omitted here. Assuming the correctness of the third stage, the second and third stages can be easily implemented in linear time. Therefore, for an input sequence of length \(n\), the total time complexity of the Garsia–Wachs algorithm is \(O(n\log n)\).

Applications

The functional programming language Haskell has a functional implementation of the Garsia–Wachs algorithm in the garsia-wachs package. It is primarily used to build optimal search tables or to balance the rope data structure with optimal complexity.

Note

rope is a tool in Haskell for manipulating annotated bytestrings using finger trees.

Example Problems

POJ 1738 An old Stone Game

There is an old stone game. At the beginning of the game, the player lines up \(n\)(\(1 \leq n \leq 50000\)) piles of stones in a row. The goal is to merge the stones into one pile, with the following rules: at each step of the game, the player can merge two adjacent piles into a new pile. The score is the total number of stones in the new pile. Calculate the minimum total score.

Solution Idea

The stone merging problem is classic. Generally, it can be solved with interval DP, but when the data size is large, such as \(n\)(\(1 \leq n \leq 50000\)) in this problem, using the Garsia–Wachs algorithm is more efficient: First, initialize an array \(\mathit{num}[n]\) of size \(n\), where \(\mathit{num}[0] = \mathit{num}[n+1] = \infty\). Second, each time find the smallest \(i\) such that \(\mathit{num}[i-1] \leq \mathit{num}[i+1]\), and merge \(\mathit{num}[i-1], \mathit{num}[i]\) into \(\mathit{temp}\); find the largest \(j\) before \(i\) such that \(\mathit{num}[j] > \mathit{temp}\), and move \(\mathit{temp}\) after \(j\). Repeat this step until the number of remaining piles is \(1\). Regarding the requirement that only adjacent stone piles can be merged, since \(\mathit{num}[j]\geq \mathit{num}[i-1] + \mathit{num}[i]\), we can treat \(\mathit{num}[j+1]\) to \(\mathit{num}[i-2]\) as a whole \(\mathit{num}[mid]\), so \(\mathit{sum}\) must be merged first. Therefore, it does not violate the problem requirements.

ATCODER N-Slimes

There are \(N\) slimes lining up. Initially, the \(i\)-th slime from the left has size \(a_{i}\). Taro tries to combine all slimes into one larger slime. He will repeatedly perform the following operation until there is only one slime: Choose two adjacent slimes and combine them into a new slime. The new slime has size \(x+y\), where \(x\) and \(y\) are the sizes of the slimes before combining. This step incurs a cost of \(x+y\). The positional relationships of the slimes do not change when combining slimes. Find the minimum possible total cost.

References and Further Reading

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