Princeton Algorithms, Burrows–Wheeler

本文写于 2020年10月28日，距今已超过 1 年，距 2020年10月28日的最后一次修改也已超过 3 个月，部分内容可能已经过时，您可以按需阅读。如果图片无法显示或者下载链接失效，请给我反馈，谢谢！

0 0 投票数

评分

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]。

注意由于空间复杂度要求是 $n+R$，所以我们不能求出整个 Sorted Suffixes 数组，因为长度为 $n$ 的字符串一共可以有 $n$ 个不同的循环表示，最终会得到一个 $n^2$ 的大小，但是又因为调用 index() 是需要在常数时间内完成的，所以我们必须在构造时就完成整个 index[] 数组的计算。

给定一个原后缀，它应该排在 Sorted Suffixes 数组中的第几位呢？

如果我们发现它的首字母是所有 $n$ 个字符中第 $k$ 大的，那它必定是在 Sorted Suffixes 数组中的第 $k$ 或更大的位置上。例如，XABCYABDZ 中的 X 比 $6$ 个字符大，所以它必定排在第 $6$ 位甚至更大的位置上。

那如果是 BDZXABCYA 呢，怎么比较首字母 B 和其他相同的 B 的大小？首先我们发现，明确比 B 小的，有 $2$ 个 A，所以 BDZXABCYA 至少排在第 $2$ 位。接着，对于同样是 B 的字符，我们比较它们后一个字符的大小，即比较 BD 的 D 和 BC 的 C，发现 C 更小，所以事实上 BDZXABCYA 排在第 $3$ 位。

整个过程依然可以使用排序来实现，只不过我们需要重新定义一下小于号。

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 数组可以帮助我们还原原始的文本：如果第 $j$ 个原始后缀（原始字符串向左移动 $j$ 个字符）是排序中的第 $i$ 行，我们定义 next[i] 是排序中出现的第 $(j+1)$ 个原始后缀的行。

这句话有点绕口，所以我们不妨先通过一个例子来看一下 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 数组的定义是：如果第 $j$ 个原始后缀（原始字符串向左移动 $j$ 个字符）是排序中的第 $i$ 行，我们定义 next[i] 是排序中出现的第 $(j+1)$ 个原始后缀的行。那么，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，可能会显得模棱两可。

事实上，结果是唯一的：如果排序后的行 $i$ 和 $j$ 都以相同的字符开始，并且 $i < j$，那么 $next[i] < next[j]$。

这条规则意味着正确的结果是 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 的任务要求使用的空间复杂度只有 $n+R$，所以我们只能一步步操作。

首先要得到 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()，是求出排序后数组第 $i$ 个字符串对应原后缀字符串的第 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 算法。

之前，我们遍历 $i$，去找 next[i] 应该填多少，即 next[i] = ?。现在，让我们逆向思考，我们还是遍历 $i$，但是我们去找 next[] 的哪个位置会填上 $i$，即 next[?] = i。

对于 $i$，我们可以得到 t[i]，即 Sorted Suffixes 数组最后一列的第 $i$ 行的字符。我们只需要找到最早出现的那个 $k$，使得 Sorted Suffixes 数组第一列的第 $k$ 行是 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

这一步，我们可以通过统计每个字符出现的次数，并进行前缀和求和，即可知道这个字符会出现在第几行。例如，我们可以计算 ! 出现 $1$ 次、A 出现 $5$ 次、B 出现 $2$ 次、C 出现 $1$ 次，那么我们知道在 D 之前有 $9$ 个其他字符串。

// 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 在 $1$、$2$、$3$、$4$、$5$ 都出现了，我们要谁呢？没关系，我们本来要的就是第一次出现的，所以，刚好就是 count['A']，即 $1$。对于已经出现过一次的字符，之后 count[c]++ 即可，那么下次就是访问 $2$。

// 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 看作 $0$ ~ $255$ 的整数，作为数组的下标。

现在，我们通过一个更高效的方法获得了 next[] 数组，但是我们失去了第一列的字符，只留下了最后一列的字符，怎么办？别忘了 next[] 的含义。我们始终有 s[i] == t[next[i]] 成立，所以仍然可以依次输出。

// output
for (int i = 0; i < length; i++) {
    BinaryStdOut.write(t.charAt(next[first]));
    first = next[first];
}

完整代码如下，也可以访问 https://gitlab.jxtxzzw.com/jxtxzzw/coursera_assignments 或者 https://github.com/jxtxzzw/coursera_assignments 获取，完整代码获得 Coursera 评分 100 分。

import edu.princeton.cs.algs4.BinaryStdIn;
import edu.princeton.cs.algs4.BinaryStdOut;

import java.util.LinkedList;

public class MoveToFront {

    private static final int RELEVANT_BITS = 8;

    // An ordered sequence of the 256 extended ASCII characters.
    private static LinkedList<Character> generateInitialSequence() {
        final int EXTENDED_ASCII_INDEX_MAX = 256;
        LinkedList<Character> sequence = new LinkedList<>();
        for (int i = 0; i < EXTENDED_ASCII_INDEX_MAX; i++) {
            sequence.add((char) i);
        }
        return sequence;
    }

    // apply move-to-front encoding, reading from standard input and writing to standard output
    public static void encode() {
        LinkedList<Character> sequence = generateInitialSequence();

        while (!BinaryStdIn.isEmpty()) {
            char c = BinaryStdIn.readChar();
            int index = sequence.indexOf(c);
            BinaryStdOut.write(index, RELEVANT_BITS);
            // remove the object, not the one at the index
            sequence.remove((Object) c);
            sequence.addFirst(c);
        }

        // Remember to flush the cache
        BinaryStdOut.close();
    }

    // apply move-to-front decoding, reading from standard input and writing to standard output
    public static void decode() {
        LinkedList<Character> sequence = generateInitialSequence();

        while (!BinaryStdIn.isEmpty()) {
            int index = BinaryStdIn.readInt(RELEVANT_BITS);
            char c = sequence.get(index);
            BinaryStdOut.write(c);
            // remove the object, not the one at the index
            sequence.remove((Object) c);
            sequence.addFirst(c);
        }

        // Remember to flush the cache
        BinaryStdOut.close();
    }

    // if args[0] is "-", apply move-to-front encoding
    // if args[0] is "+", apply move-to-front decoding
    public static void main(String[] args) {
        if ("-".equals(args[0])) {
            encode();
        } else {
            decode();
        }

    }

}

import java.util.Arrays;
import java.util.Comparator;

public class CircularSuffixArray {

    private final int length;
    private final Integer[] indexes;

    // circular suffix array of s
    public CircularSuffixArray(String s) {
        if (s == null) {
            throw new IllegalArgumentException();
        }

        length = s.length();
        indexes = new Integer[length];
        for (int i = 0; i < length; i++) {
            indexes[i] = i;
        }

        Comparator<Integer> cmp = (o1, 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;
            }
        };

        Arrays.sort(indexes, cmp);
    }


    // length of s
    public int length() {
        return length;
    }

    // returns index of ith sorted suffix
    public int index(int i) {
        if (i < 0 || i >= length) {
            throw new IllegalArgumentException();
        }
        return indexes[i];
    }

    // unit testing (required)
    public static void main(String[] args) {
        String original = "ABRACADABRA!";
        CircularSuffixArray csa = new CircularSuffixArray(original);
        for (int i = 0; i < csa.length(); i++) {
            System.out.println("index[" + i + "] = " + csa.index(i));
        }
    }

}

import edu.princeton.cs.algs4.BinaryStdIn;
import edu.princeton.cs.algs4.BinaryStdOut;

public class BurrowsWheeler {

    // apply Burrows-Wheeler transform,
    // reading from standard input and writing to standard output
    public static void transform() {
        // input
        StringBuilder sb = new StringBuilder();
        while (!BinaryStdIn.isEmpty()) {
            sb.append(BinaryStdIn.readChar());
        }
        int length = sb.length();
        CircularSuffixArray csa = new CircularSuffixArray(sb.toString());

        // find "first" and output
        for (int i = 0; i < length; i++) {
            if (csa.index(i) == 0) {
                // write a 32-bit int
                BinaryStdOut.write(i);
                break;
            }
        }

        // 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"
            BinaryStdOut.write(sb.charAt(lastIndex));
        }

        BinaryStdOut.close();

    }

    // apply Burrows-Wheeler inverse transform,
    // reading from standard input and writing to standard output
    public static void inverseTransform() {

        // input
        int first = BinaryStdIn.readInt();
        StringBuilder t = new StringBuilder();
        while (!BinaryStdIn.isEmpty()) {
            t.append(BinaryStdIn.readChar());
        }
        int length = t.length();

        // 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];
        }
        // 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]++;
        }

        // output
        for (int i = 0; i < length; i++) {
            BinaryStdOut.write(t.charAt(next[first]));
            first = next[first];
        }
        BinaryStdOut.close();

    }

    // if args[0] is "-", apply Burrows-Wheeler transform
    // if args[0] is "+", apply Burrows-Wheeler inverse transform
    public static void main(String[] args) {
        if ("-".equals(args[0])) {
            transform();
        } else {
            inverseTransform();
        }
    }

}

0 0 投票数

评分

Windows Server 2008 安装 XAMPP 环境并进行基本网页环境测试

Java实践课作业

嵌入式系统原理期末样卷

求有向图的所有强连通分量

Speech Audio Denoising