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


0 0 投票数
评分

Burrows–Wheeler

Princeton Algorithm Assignment Burrows–Wheeler

普林斯顿大学算法课 Burrows–Wheeler

Burrows–Wheeler 算法是一个革命性的压缩算法,可以对 gzipPKZIP 进行压缩,并且构成了 Unix 系统压缩工具 bzip2 的基础,该算法分为 3 个主要的部分:

  1. Burrows–Wheeler 变换。给定一段英文文本,将其转化为具有如下格式的文本序列:相同的字符会在相邻的位置出现多次。
  2. Move-to-Front 编码。将 Burrows–Wheeler 变换后的文本编码为特定字符出现的频率比其他字符更高的文本。
  3. 对上述编码进行 Huffman 压缩。哈夫曼压缩可将出现频率更高的字符用更短的编码值表示,从而实现高效压缩。

事实上,第 3 步的 Huffman 压缩才是唯一对信息进行压缩的步骤,但是前 2 步的变换和编码可以保证特定字符出现的频率高于其他字符,从而保证 Huffman 压缩具有较高的压缩效率。

为了展开压缩后的信息,我们可以将上述操作逆向进行:首先进行 Huffman 解码,然后进行 Move-to-Front 解码,最后逆向进行 Burrows–Wheeler 变换。

Princeton 的 Algorithm 课程作业要求实现 Burrows–Wheeler 变换和 Move-to-Front 编码,并调用课程所学 Huffman 算法完成完整的压缩程序。为了方便代码调试,课程提供了 BinaryStdInBinaryStdOut 以及 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 的字符,我们比较它们后一个字符的大小,即比较 BDDBCC,发现 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。注意这段序列中 AB 连续出现了多次,这样的结构使得文本更利于被压缩。

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 变换,怎么才能通过 firstt 来还原原始的文本呢?

当我们获得了一段文本并获得了它的环形后缀数组之后,我们需要先根据 firstt 来获得 next 数组,next 数组可以帮助我们还原原始的文本:如果第 $j$ 个原始后缀(原始字符串向左移动 $j$ 个字符)是排序中的第 $i$ 行,我们定义 next[i] 是排序中出现的第 $(j+1)$ 个原始后缀的行。

这句话有点绕口,所以我们不妨先通过一个例子来看一下 next 数组是怎么帮助我们还原原始信息的,然后再讨论怎么求出 next 数组。

我们知道了 tA 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] = 2next[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] = 1next[11] = 4,还是 next[10] = 4next[11] = 1,可能会显得模棱两可。

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

这条规则意味着正确的结果是 next[10] = 1next[11] = 4

为什么这条规则是对的?

因为行是排序的,所以第 10 行在字典序上比第 11 行小。又由于这两行的第一个字母都是 R,因此,第 10 行的后 10 个未知字符一定小于第 11 行的后 10 个未知字符。我们还知道,在以 R 结尾的两行之间,第 1 行比第 4 行小,而,第 10 行和第 11 行的 10 个未知字符正是第 1 行和第 4 行的前 10 个字符。因此,next[10] = 1next[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] == targetk 未被访问过。

// 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 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论