Garsia-Wachs 算法

简介

Garsia-Wachs 算法（Garsia-Wachs Algorithm）是计算机用来在 线性时间 内构建 最优二叉查找树 和 字母霍夫曼码 的有效算法。它以 Adriano Garsia 和 Michelle L. Wachs 的名字命，他们于 1977 年发表了相关论文。

问题描述

一个整数 ，对于 个非负权值 ，构造一棵有根且 个内部节点都有两个子节点的二叉树，这意味着这棵二叉树有 个叶节点。我们将 的输入序列与二叉树结点顺序一一映射，目标是在所有具有 个内部节点的可能的树结构中找到一棵树，使外部从根到每个叶子的路径长度的权重和最小。

最优二叉查找树

这个问题可以理解为 个有序键构造二叉查找树的问题，假设树将仅用于搜索树中不存在的值。在这种情况下， 个键将搜索值的空间划分为 个区间，并且这些区间之一的权重可以作为搜索值落在那个区间的概率。外部路径长度的加权和控制了查找的预期时间。

字母霍夫曼码

这个问题也可以用作构建霍夫曼码。这是一种通过使用二进制值的可变长度序列明确编码 给定值的方法。在这种解释中，值的代码由从树中的根到叶子的路径上从父到子的左步和右步序列给出（例如，左为 ，右为 ）。与标准霍夫曼码不同，以这种方式构造的霍夫曼码是按字母顺序排列的，也就是说这些二进制码的排序顺序与值的输入顺序相同。如果一个值的权重是它在编码消息中的频率，那么 Garsia-Wachs 算法的输出是将消息长度压缩到最短的，按字母顺序排列的霍夫曼代码。

过程

Garsia-Wachs 算法一般包括三个阶段：

1. 构建一个值位于叶子的二叉树，注意顺序可能错误。
2. 计算树中根到每个叶子的距离。
3. 构建另一个二叉树，叶子的距离相同，但顺序正确。

如上图所示，在算法的第一阶段，通过查找合并输入序列的无序三元组构建的二叉树（左侧），和算法输出的正确排序的二叉树，其中叶子高度与另一棵树一样。

如果输入在序列的开始和结束处增加了两个标记值 （或任何足够大的有限值），则算法的第一阶段更容易描述。所以在竞赛题解中使用 Garsia-Wachs 算法时，对于一个长度为 的数组 ，我们一般定义 。

第一阶段维护了一个由最初为每个非标志（non-sentinel）输入权重创建的单节点树组成的森林。每棵树都与一个值相关联，其叶子的权重之和为每个非标志输入权重构成一个树节点。为了维护这些值的序列，每端会有两个标记值。初始序列只是叶权重作为输入的顺序。然后重复执行以下步骤，每一步都减少输入序列的长度，直到只有一棵树包含了所有叶子：

• 在序列中找到前三个连续的权重值 ，， 使得 。因为序列结尾的标志值大于之前的任意两个有限值，所以总是存在这样的三元组。
• 从序列中移除 和 ，并创建一个新的树节点作为 和 节点的父节点，值为 。
• 在原来 的位置以前大于或等于 且距 最近的值的右边重新插入新节点。因为左标志值的存在，所以总是存在这样的位置。

为了有效地实现这一阶段，该算法可以在任何平衡二叉查找树结构中维护当前值序列。这样的结构允许我们在对数时间内移除 和 ，并重新插入它们的新父节点。在每一步中，数组中位于偶数索引上直到 值的权重形成了一个递减序列，位于奇数索引位的权重形成另一个递减序列。因此，重新插入 的位置可以通过在对数时间内对这两个递减序列使用平衡树执行两次二分查找找到。通过从前一个三元组 值开始的线性顺序搜索，我们可以在总线性时间复杂度内执行对满足 的第一个位置的搜索。

Garsia-Wachs 算法的第三阶段的证明，即存在另一棵具有相同距离的树并且这棵树提供了问题的最优解，是很重要的。但是由于其证明方式有多种且过于复杂，此处略去。在第三阶段为正确的前提下，第二和第三阶段很容易在线性时间内实现。因此，在长度为 的输入序列上，Garsia-Wachs 算法的总时间复杂度为 。

应用

函数性编程语言 Haskell 的 garsia-wachs package 对 Garsia-Wachs 算法做了函数性实现。它主要用于构建最佳搜索表，或者以最优复杂度平衡 rope 数据结构。

例题

参考资料与拓展阅读

• [1]Garsia–Wachs algorithm - Wikipedia
• [2]Data.Algorithm.GarsiaWachs - Hackage Haskell
• [3]garsia-wachs: A Functional Implementation of the Garsia-Wachs Algorithm - Wikipedia
• [4]Sentinel value - Wikipedia
• [5]A new proof of the Garsia-Wachs algorithm