Burrows–Wheeler
Princeton Algorithm Assignment Burrows–Wheeler
普林斯顿大学算法课 Burrows–Wheeler
Burrows–Wheeler 算法是一个革命性的压缩算法，可以对 gzip 和 PKZIP 进行压缩，并且构成了 Unix 系统压缩工具 bzip2 的基础，该算法分为 3 个主要的部分：
- Burrows–Wheeler 变换。给定一段英文文本，将其转化为具有如下格式的文本序列：相同的字符会在相邻的位置出现多次。
- Move-to-Front 编码。将 Burrows–Wheeler 变换后的文本编码为特定字符出现的频率比其他字符更高的文本。
- 对上述编码进行 Huffman 压缩。哈夫曼压缩可将出现频率更高的字符用更短的编码值表示，从而实现高效压缩。
事实上，第 3 步的 Huffman 压缩才是唯一对信息进行压缩的步骤，但是前 2 步的变换和编码可以保证特定字符出现的频率高于其他字符，从而保证 Huffman 压缩具有较高的压缩效率。
为了展开压缩后的信息，我们可以将上述操作逆向进行：首先进行 Huffman 解码，然后进行 Move-to-Front 解码，最后逆向进行 Burrows–Wheeler 变换。
Princeton 的 Algorithm 课程作业要求实现 Burrows–Wheeler 变换和 Move-to-Front 编码，并调用课程所学 Huffman 算法完成完整的压缩程序。为了方便代码调试，课程提供了 BinaryStdIn、BinaryStdOut 以及 HexDump 工具。
Move-to-Front 编码和解码的主要思想是通过反复从输入信息中读取一个字符，打印该字符在序列中出现的位置，并将该字符移动到序列的前面，从而保持字母表中字符的有序序列。例如对于 6 个字符的初始序列 A B C D E F，我们对 CAAABCCCACCF 进行加密，我们可以得到：
move-to-front in out
------------- --- ---
A B C D E F C 2
C A B D E F A 1
A C B D E F A 0
A C B D E F A 0
A C B D E F B 2
B A C D E F C 2
C B A D E F C 0
C B A D E F C 0
C B A D E F A 2
A C B D E F C 1
C A B D E F C 0
C A B D E F F 5
F C A B D E
-
对
C进行加密，发现C的位置是 2（A位于 0、B位于 1、C位于 2），所以输出结果为 2，接着将C移动到序列的最前端，此时序列变为C A B D E F。 -
对
A进行加密时，A出现在序列的位置是 1，所以输出结果为 1，并将A移动到序列最前端，此时序列变为A C B D E F。 -
继续对
A进行加密，此时A出现的位置是 0，所以输出 0，以此类推……
如果在输入中多次出现彼此接近的字符，那么许多输出值将是较小的整数（如 0、1 和 2 等），由此产生的这些字符（较多的 0、1 和 2 等）的频率会很高，提供了 Huffman 编码所能达到的、有利压缩比的输入。例如 CAAABCCCACCF 的编码中出现了 5 次 0、2 次 1 和 4 次 2。
Move-to-Front 编码的任务是依次读入每一个字节（8 个二进制位，看作字符 char），输出其在序列中的位置，并将其移动到最前面。Move-to-Front 解码的任务是依次读入每一个字节（8 个二进制位，看作 0 - 255 之间的无符号整数），输出这个整数所代表的位置上的字符，并将改字符移动到序列最前面。
这一部分的代码比较简单，只需要使用 BinaryIn 和 BinaryOut 即可，注意运行到最后要 flush() 刷新输入输出缓冲区，并注意输入输出整型时，需要指定只输出或读入 8 位。
LinkedList<Character> sequence = generateInitialSequence();
while (!in.isEmpty()) {
char c = in.readChar();
int index = sequence.indexOf(c);
out.write(index, RELEVANT_BITS);
sequence.remove((Object)c);
sequence.addFirst(c);
}
out.flush(); // out.close();
由于没有 remove(char c) 的函数签名，所以 char c 会被当做 int index，并执行 remove(int index)，在 LinkedList 中，这是代表移除第 index 个位置上的元素。我们希望的是移除那个内容为 c 的元素，所以这里强制转换成了 Object，这样就会调用 remove(Object o) 去移除那个内容为 o 的元素。
为了高效地进行 Burrows–Wheeler 变换，我们需要环形后缀数组。
例如对于一个长度为 12 的字符串 ABRACADABRA!，我们通过每次将其循环移动 1 位，可以得到 12 个不同的字符串（记为 Original Suffixes）。然后将这 12 个字符串按照字典序排序（记为 Sorted Suffixes）。
我们定义 index[i] 为排序后数组（Sorted Suffixes）中出现第 i 个原后缀（Original Suffixes）的索引。例如，index[11] = 2 意味着第 2 个原后缀（R A C A D A B R A ! A B）出现在排序顺序中的第 11 位。
i Original Suffixes Sorted Suffixes index[i]
-- ----------------------- ----------------------- --------
0 A B R A C A D A B R A ! ! A B R A C A D A B R A 11
1 B R A C A D A B R A ! A A ! A B R A C A D A B R 10
2 R A C A D A B R A ! A B A B R A ! A B R A C A D 7
3 A C A D A B R A ! A B R A B R A C A D A B R A ! 0
4 C A D A B R A ! A B R A A C A D A B R A ! A B R 3
5 A D A B R A ! A B R A C A D A B R A ! A B R A C 5
6 D A B R A ! A B R A C A B R A ! A B R A C A D A 8
7 A B R A ! A B R A C A D B R A C A D A B R A ! A 1
8 B R A ! A B R A C A D A C A D A B R A ! A B R A 4
9 R A ! A B R A C A D A B D A B R A ! A B R A C A 6
10 A ! A B R A C A D A B R R A ! A B R A C A D A B 9
11 ! A B R A C A D A B R A R A C A D A B R A ! A B 2
CircularSuffixArray 的任务是完成一个函数，方便获得 index[i]。
注意由于空间复杂度要求是 ，所以我们不能求出整个 Sorted Suffixes 数组，因为长度为
的字符串一共可以有
个不同的循环表示，最终会得到一个
的大小，但是又因为调用
index() 是需要在常数时间内完成的，所以我们必须在构造时就完成整个 index[] 数组的计算。
给定一个原后缀，它应该排在 Sorted Suffixes 数组中的第几位呢？
如果我们发现它的首字母是所有 个字符中第
大的，那它必定是在 Sorted Suffixes 数组中的第
或更大的位置上。例如，
XABCYABDZ 中的 X 比 个字符大，所以它必定排在第
位甚至更大的位置上。
那如果是 BDZXABCYA 呢，怎么比较首字母 B 和其他相同的 B 的大小？首先我们发现，明确比 B 小的，有 个
A，所以 BDZXABCYA 至少排在第 位。接着，对于同样是
B 的字符，我们比较它们后一个字符的大小，即比较 BD 的 D 和 BC 的 C，发现 C 更小，所以事实上 BDZXABCYA 排在第 位。
整个过程依然可以使用排序来实现，只不过我们需要重新定义一下小于号。
Arrays.sort(indexes, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
int entry = o1;
// skip equal characters
while (s.charAt(o1) == s.charAt(o2)) {
// compare next character, loop back when it goes over the last character
o1 = (o1 + 1) % length;
o2 = (o2 + 1) % length;
// corner case: "AAA" and "AAA"
// if come back to the entry, every character is the same
if (o1 == entry) {
return 0;
}
}
// sort according to the characters
if (s.charAt(o1) < s.charAt(o2)) {
return -1;
} else {
return 1;
}
}
});
最后，我们就可以进行 Burrows–Wheeler 变换了。
Burrows–Wheeler 变换本身并不对信息进行压缩，而是为了将信息变成更有利于压缩的形式。Burrows-Wheeler 变换对输入中的字符进行重新排列，使输入中出现了很多重复字符的簇，但这种方式仍然可以恢复原始输入。它依赖于以下的直觉：如果你在英文文本中看到字母 hen，那么，大多数情况下，它前面的字母不是 t 就是 w。
我们先来看一个例子，然后解释一下 Burrows–Wheeler 变换是如何进行的。
仍以 ABRACADABRA! 为例，对这个文本进行 Burrows–Wheeler 变换，我们得到了
3
ARD!RCAAAABB
变换后的结果的第一行是 3，表示 ABRACADABRA! 出现在排序后的数组中的第 3 行，我们记 first = 3。
接着，第二行的字符串是用排序后数组的最后一列的字符构成的。定义 t[] 表示排序后的数组中最后一列字符所组成的字符数组，即 A R D ! R C A A A A B B。注意这段序列中 A 和 B 连续出现了多次，这样的结构使得文本更利于被压缩。
Sorted Suffixes t[]
-------------------------
! A B R A C A D A B R [A]
A ! A B R A C A D A B [R]
A B R A ! A B R A C A [D]
A B R A C A D A B R A [!]
A C A D A B R A ! A B [R]
A D A B R A ! A B R A [C]
B R A ! A B R A C A D [A]
B R A C A D A B R A ! [A]
C A D A B R A ! A B R [A]
D A B R A ! A B R A C [A]
R A ! A B R A C A D A [B]
R A C A D A B R A ! A [B]
如果我们将上述 Burrows–Wheeler 变换后的结果用 16 进制输出，我们会得到 00 00 00 03 41 52 44 21 52 43 41 41 41 41 42 42，注意整数 3 是使用 4 个字节（00 00 00 03）来表示的，其余字符是使用 ASCII 的编码值来表示的。
Burrows–Wheeler 变换就是这么简单。
可是，看着挺容易的 Burrows–Wheeler 变换，怎么才能通过 first 和 t 来还原原始的文本呢？
当我们获得了一段文本并获得了它的环形后缀数组之后，我们需要先根据 first 和 t 来获得 next 数组，next 数组可以帮助我们还原原始的文本：如果第 个原始后缀（原始字符串向左移动
个字符）是排序中的第
行，我们定义
next[i] 是排序中出现的第 个原始后缀的行。
这句话有点绕口，所以我们不妨先通过一个例子来看一下 next 数组是怎么帮助我们还原原始信息的，然后再讨论怎么求出 next 数组。
我们知道了 t 是 A R D ! R C A A A A B B，即 Sorted Suffixes 的最后一列是 A R D ! R C A A A A B B。Sorted Suffixes 是根据字典序排序的，因此其第 0 列一定是字典序有序的，根据 t 字符串的字符，我们可以得到 Sorted Suffixes 的第 0 列为 ! A A A A A B B C D R R。
那么，我们就可以得到下表（表中的 next 数组已给出，我们将在后面解释如何构建 next 数组）。
i Sorted Suffixes t next[i]
-- ----------------------- -------
0 ! ? ? ? ? ? ? ? ? ? ? A 3
1 A ? ? ? ? ? ? ? ? ? ? R 0
2 A ? ? ? ? ? ? ? ? ? ? D 6
*3 A ? ? ? ? ? ? ? ? ? ? ! 7
4 A ? ? ? ? ? ? ? ? ? ? R 8
5 A ? ? ? ? ? ? ? ? ? ? C 9
6 B ? ? ? ? ? ? ? ? ? ? A 10
7 B ? ? ? ? ? ? ? ? ? ? A 11
8 C ? ? ? ? ? ? ? ? ? ? A 5
9 D ? ? ? ? ? ? ? ? ? ? A 2
10 R ? ? ? ? ? ? ? ? ? ? B 1
11 R ? ? ? ? ? ? ? ? ? ? B 4
通过 next 数组和 first，我们可以重建原始输入字符串。
-
由于
first = 3，我们知道原始输入字符串出现在第 3 行；因此，我们知道原始输入字符串以A开头并以!结束。 -
由于
next[first] = 7，下一个原始后缀出现在第 7 行；因此，原始输入字符串中的下一个字符是B。 -
由于
next[next[first]] = 11，下一个原后缀出现在第 11 行；因此，原输入字符串中的下一个字符是R。 -
以此类推，我们可以得到原始字符串。
等等，为什么由于 next[first] = 7，下一个原始后缀出现在第 7 行？注意 next 数组的定义是：如果第 个原始后缀（原始字符串向左移动
个字符）是排序中的第
行，我们定义
next[i] 是排序中出现的第 个原始后缀的行。那么，
next[first] 就是排序顺序中第 1 个原始后缀（原始字符串左移 1）出现的行、next[next[first]] 是排序顺序中第 2 个原始后缀出现的行、next[next[next[first]] 是第 3 个原始后缀出现的行……
那么，next 数组是如何求得的呢？
对于一个在输入字符串中只出现过一次的字符，很容易推导出 next[]。
例如，考虑以 C 开头的后缀：
-
通过检查第一列，它在排序顺序中出现了第 8 位。
-
在这之后的下一个原始后缀将以
C作为最后一个字符（因为每次是对原始字符串循环左移 1 位，所以C必定被移动到了最后一位），通过检查最后一列，下一个原始后缀在排序顺序中出现第 5 个字符。 -
因此，
next[8] = 5
同样，D 和 ! 各只出现一次，所以我们可以推断出 next[9] = 2、next[0] = 3。
i Sorted Suffixes t next[i]
-- ----------------------- -------
0 ! ? ? ? ? ? ? ? ? ? ? A 3
1 A ? ? ? ? ? ? ? ? ? ? R
2 A ? ? ? ? ? ? ? ? ? ? D
*3 A ? ? ? ? ? ? ? ? ? ? !
4 A ? ? ? ? ? ? ? ? ? ? R
5 A ? ? ? ? ? ? ? ? ? ? C
6 B ? ? ? ? ? ? ? ? ? ? A
7 B ? ? ? ? ? ? ? ? ? ? A
8 C ? ? ? ? ? ? ? ? ? ? A 5
9 D ? ? ? ? ? ? ? ? ? ? A 2
10 R ? ? ? ? ? ? ? ? ? ? B
11 R ? ? ? ? ? ? ? ? ? ? B
然而，由于 R 出现了两次，因此，究竟是 next[10] = 1 和 next[11] = 4，还是 next[10] = 4 和 next[11] = 1，可能会显得模棱两可。
事实上，结果是唯一的：如果排序后的行 和
都以相同的字符开始，并且
，那么
。
这条规则意味着正确的结果是 next[10] = 1 和 next[11] = 4。
为什么这条规则是对的？
因为行是排序的，所以第 10 行在字典序上比第 11 行小。又由于这两行的第一个字母都是 R，因此，第 10 行的后 10 个未知字符一定小于第 11 行的后 10 个未知字符。我们还知道，在以 R 结尾的两行之间，第 1 行比第 4 行小，而，第 10 行和第 11 行的 10 个未知字符正是第 1 行和第 4 行的前 10 个字符。因此，next[10] = 1、next[11] = 4，否则，这将与后缀排序的事实相矛盾。
如果我们能够像上面一样写出完整的 Sorted Suffixes，那么整个过程会变得非常简单，但是由于 Burrows-Wheeler 的任务要求使用的空间复杂度只有 ，所以我们只能一步步操作。
首先要得到 first，即求出满足 index[first] == 0 的那个 first，我们可以直接用一个循环来搞定它。
// find "first" and output
for (int i = 0; i < length; i++) {
if (csa.index(i) == 0) {
// write a 32-bit int
out.write(i);
break;
}
}
然后就是构造字符串 t。我们现在手上有的函数其实只有 index()，是求出排序后数组第 个字符串对应原后缀字符串的第
index[i] 个，而原后缀字符串的第 index[i] 个字符串，就是原始字符串循环左移 index[i] 个字符后得到的，那我们就可以得到这个对应字符串的最后一个元素。依次处理，即可得到 t 字符串。
// find the string "t"
for (int i = 0; i < length; i++) {
// the i-th original suffix string
int index = csa.index(i);
// get the index of its last character
int lastIndex = (length - 1 + index) % length;
// append these characters, and then we get "t"
out.write(sb.charAt(lastIndex));
}
逆向的过程需要先求出 next[] 数组，然后直接遍历输出。
// output
for (int i = 0; i < length; i++) {
out.write(s[first]);
first = next[first];
}
out.flush(); // out.close();
我们首先需要读入 t，并根据 t 中的每一个字符排出 Sorted Suffixes 数组的第一列。
// input
int first = in.readInt();
StringBuilder t = new StringBuilder();
while (!in.isEmpty()) {
t.append(in.readChar());
}
int length = t.length();
// generate the first column
char[] s = t.toString().toCharArray();
Arrays.sort(s);
找 next[] 数组的过程，就是遍历 t，寻找到一个 k 满足 t[k] == target 且 k 未被访问过。
// generate next array
int[] next = new int[length];
boolean[] used = new boolean[length];
for (int i = 0; i < length; i++) {
char target = s[i];
// find the first k, s.t. t[k] == target, and k is not used
for (int k = 0; k < length; k++) {
if (t.charAt(k) == target && !used[k]) {
next[i] = k;
used[k] = true;
break;
}
}
}
但是这样的代码运行效率非常低下，我们需要用更高效的方法来完成 next[] 数组的构建。这是整个作业中最具有技巧性的部分，我们要用到字符串中的常用算法——Key-Indexed Counting 算法。
之前，我们遍历 ，去找
next[i] 应该填多少，即 next[i] = ?。现在，让我们逆向思考，我们还是遍历 ，但是我们去找
next[] 的哪个位置会填上 ，即
next[?] = i。
对于 ，我们可以得到
t[i]，即 Sorted Suffixes 数组最后一列的第 行的字符。我们只需要找到最早出现的那个
，使得 Sorted Suffixes 数组第一列的第
行是
t[i]，那么 next[k] = i。例如，当 i = 2 时，t[2] = 'D'，我们找到第 9 行开头字母是 D，所以 next[9] = 2。
i Sorted Suffixes t next[i]
-- ----------------------- -------
0 ! ? ? ? ? ? ? ? ? ? ? A 3
1 A ? ? ? ? ? ? ? ? ? ? R 0
2 A ? ? ? ? ? ? ? ? ? ? D 6
*3 A ? ? ? ? ? ? ? ? ? ? ! 7
4 A ? ? ? ? ? ? ? ? ? ? R 8
5 A ? ? ? ? ? ? ? ? ? ? C 9
6 B ? ? ? ? ? ? ? ? ? ? A 10
7 B ? ? ? ? ? ? ? ? ? ? A 11
8 C ? ? ? ? ? ? ? ? ? ? A 5
9 D ? ? ? ? ? ? ? ? ? ? A 2
10 R ? ? ? ? ? ? ? ? ? ? B 1
11 R ? ? ? ? ? ? ? ? ? ? B 4
这一步，我们可以通过统计每个字符出现的次数，并进行前缀和求和，即可知道这个字符会出现在第几行。例如，我们可以计算 ! 出现 次、
A 出现 次、
B 出现 次、
C 出现 次，那么我们知道在
D 之前有 个其他字符串。
// compute frequency counts
final int EXTENDED_ASCII_INDEX_MAX = 256;
int[] count = new int[EXTENDED_ASCII_INDEX_MAX + 1];
for (int i = 0; i < length; i++) {
count[t.charAt(i) + 1]++;
}
// transform counts to indices
for (int i = 0; i < EXTENDED_ASCII_INDEX_MAX; i++) {
count[i + 1] += count[i];
}
那……出现重复字符怎么办？比如 A 在 、
、
、
、
都出现了，我们要谁呢？没关系，我们本来要的就是第一次出现的，所以，刚好就是
count['A']，即 。对于已经出现过一次的字符，之后
count[c]++ 即可，那么下次就是访问 。
// generate next array
int[] next = new int[length];
for (int i = 0; i < length; i++) {
char c = t.charAt(i);
next[count[c]] = i;
count[c]++;
}
这个过程中，我们把 char 看作 ~
的整数，作为数组的下标。
现在，我们通过一个更高效的方法获得了 next[] 数组，但是我们失去了第一列的字符，只留下了最后一列的字符，怎么办？别忘了 next[] 的含义。我们始终有 s[i] == t[next[i]] 成立，所以仍然可以依次输出。
// output
for (int i = 0; i < length; i++) {
BinaryStdOut.write(t.charAt(next[first]));
first = next[first];
}
完整代码可以访问 凝神长老的 GitLab、凝神长老的 GitHub 或者 凝神长老的博客 获取，完整代码获得 Coursera 评分 100 分。
网友评论