Algorithms, Part II - Week 5 - BurrowsWheeler
巨长的 specification，没有图片解释，超多的OJ检测点，最后的一次作业甚至涉及到第一次的内容
分析
CircularSuffixArray.java
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
读入一行字符串”ABRACADABRA!”构造一个后缀数组，再按照第一列进行字母排序，index数组记录排序后的第i行是原数组的第index[i]行
可以不生成排序后的数组，而只排序原序号
public int compare(Integer first, Integer second) {
// get start indexes of chars to compare
int firstIndex = first;
int secondIndex = second;
// for all characters
for (int i = 0; i < s.length(); i++) {
// if out of the last char then start from beginning
if (firstIndex > s.length() - 1)
firstIndex = 0;
if (secondIndex > s.length() - 1)
secondIndex = 0;
// if first string > second
if (s.charAt(firstIndex) < s.charAt(secondIndex))
return -1;
else if (s.charAt(firstIndex) > s.charAt(secondIndex))
return 1;
// watch next chars
firstIndex++;
secondIndex++;
}
// equal strings
return 0;
}BurrowsWheeler.java
transform
目的是输出排序后数组的最后一列，以及原数组第一行在排序后数组的行号
i Original Suffixes Sorted Suffixes t index[i] 输出 -- ----------------------- ----------------------- -------- 3 0 A B R A C A D A B R A ! ! A B R A C A D A B R A 11 ARD!RCAAAABB 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
OJ不允许有CircularSuffixArray.java的 API 中之外的 public 方法，所以不能在CircularSuffixArray.java记录排序后的数组然后在这里引用，因此唯一入手点就是之前的index()
inverse transform
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
最难的一部分，checklist 中说代码不超过10行，实际上就是 LSD
public static void inverseTransform() {
int first = BinaryStdIn.readInt();
String s = BinaryStdIn.readString();
int n = s.length();
int[] next = new int[n];
/* use LSD algorithm for char */
// compute frequency counts
int[] count = new int[R + 1];
for (int i = 0; i < n; i++)
count[s.charAt(i) + 1]++;
// compute cumulates
for (int r = 0; r < R; r++)
count[r+1] += count[r];
// move data
for (int i = 0; i < n; i++)
next[count[s.charAt(i)]++] = i;
// print out
for (int j = 0, k = next[first]; j < n; j++, k = next[k])
BinaryStdOut.write(s.charAt(k));
BinaryStdOut.close();
}MoveToFront.java
本次作业里最简单的一部分，简单的字符串处理；但实际编程中被 Java 内置的方法搞得有点晕，一开始不确定要用字符串还是字符数组；最后用 StringBuilder 解决