If you want to get an early start on this assignment, we recommend skipping directly to the circular suffix array data type. You can complete this part using only material from Section 5.1 of the textbook and the corresponding lecture.
Implement the Burrows-Wheeler data compression algorithm. This revolutionary algorithm outcompresses gzip and PKZIP, is relatively easy to implement, and is not protected by any patents. It forms the basis of the Unix compression utility bzip2.
The Burrows-Wheeler compression algorithm consists of three algorithmic components, which are applied in succession:
Binary input and binary output. To enable your programs to work with binary data, you will use BinaryStdIn and BinaryStdOut, which are described in Algorithms, 4th edition and part of algs4.jar. To display the binary output when debugging, you can use HexDump, which takes a command-line argument N, reads bytes from standard input and writes them to standard output in hexadecimal, N per line.
Note that in ASCII, 'A' is 41 (hex) and '!' is 21 (hex).% more abra.txt ABRACADABRA! % java-algs4 edu.princeton.cs.algs4.Huffman - < abra.txt 41 42 52 41 43 41 44 41 42 52 41 21 96 bits
Huffman compression and expansion. Huffman (Program 5.10 in Algorithms, 4th edition) implements the classic Huffman compression and expansion algorithms.
% java-algs4 edu.princeton.cs.algs4.Huffman - < abra.txt | java-algs4 edu.princeton.cs.algs4.HexDump 16 50 4a 22 43 43 54 a8 40 00 00 01 8f 96 8f 94 120 bits
You will not write any code for this step.% java-algs4 edu.princeton.cs.algs4.Huffman - < abra.txt | java-algs4 edu.princeton.cs.algs4.Huffman + ABRACADABRA!
Move-to-front encoding and decoding. The main idea of move-to-front encoding is to maintain an ordered sequence of the characters in the alphabet, and repeatedly read in a character from the input message, print out the position in which that character appears, and move that character to the front of the sequence. As a simple example, if the initial ordering over a 6-character alphabet is A B C D E F, and we want to encode the input CAAABCCCACCF, then we would update the move-to-front sequences as follows:
If the same character occurs next to each other many times in the input, then many of the output values will be small integers, such as 0, 1, and 2. The extremely high frequency of certain characters makes an ideal scenario for Huffman coding.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
% java-algs4 MoveToFront - < abra.txt | java-algs4 edu.princeton.cs.algs4.HexDump 16 41 42 52 02 44 01 45 01 04 04 02 26 96 bits
% java-algs4 MoveToFront - < abra.txt | java-algs4 MoveToFront + ABRACADABRA!
Performance requirements. The running time of both move-to-front encoding and decoding should be proportional to R N (or better) in the worst case and proportional to N + R (or better) in practice on inputs that arise when compressing typical English text, where N is the number of characters in the input and R is the alphabet size. The amount of memory used by both move-to-front encoding and decoding should be proportional to N + R (or better) in the worst case.public class MoveToFront { // apply move-to-front encoding, reading from standard input and writing to standard output public static void encode() // apply move-to-front decoding, reading from standard input and writing to standard output public static void decode() // if args[0] is '-', apply move-to-front encoding // if args[0] is '+', apply move-to-front decoding public static void main(String[] args) }
Circular suffix array. To efficiently implement the key component in the Burrows-Wheeler transform, you will use a fundamental data structure known as the circular suffix array, which describes the abstraction of a sorted array of the N circular suffixes of a string of length N. As an example, consider the string "ABRACADABRA!" of length 12. The table below shows its 12 circular suffixes and the result of sorting them.
We define index[i] to be the index of the original suffix that appears ith in the sorted array. For example, index[11] = 2 means that the 2nd original suffix appears 11th in the sorted order (i.e., last alphabetically).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
Your job is to implement the following circular suffix array API, which provides the client access to the index[] values:
Corner cases. The constructor should throw a java.lang.NullPointerException if the argument is null; the method index() should throw a java.lang.IndexOutOfBoundsException if i is outside its prescribed range (between 0 and N − 1).public class CircularSuffixArray { public CircularSuffixArray(String s) // circular suffix array of s public int length() // length of s public int index(int i) // returns index of ith sorted suffix public static void main(String[] args) // unit testing (not graded) }
Performance requirements. On typical English text, your data type should use space proportional to N + R (or better); the constructor should take time proportional to N log N (or better) on typical English text; and the methods length() and index() should take constant time. Warning: beginning with Java 7, Update 6, the substring() method takes time and space proportional to the length of the substring—in other words, you cannot form the N circular suffixes explicitly because that would take both quadratic time and space.
Burrows-Wheeler transform. The goal of the Burrows-Wheeler transform is not to compress a message, but rather to transform it into a form that is more amenable to compression. The transform rearranges the characters in the input so that there are lots of clusters with repeated characters, but in such a way that it is still possible to recover the original input. It relies on the following intuition: if you see the letters hen in English text, then most of the time the letter preceding it is t or w. If you could somehow group all such preceding letters together (mostly t's and some w's), then you would have an easy opportunity for data compression.
Since the original string ABRACADABRA! ends up in row 3, we have first = 3. Thus, the Burrows-Wheeler transform isi Original Suffixes Sorted Suffixes t 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
Notice how there are 4 consecutive As and 2 consecutive Bs—these clusters make the message easier to compress.3 ARD!RCAAAABB
Also, note that the integer 3 is represented using 4 bytes (00 00 00 03). The character 'A' is represented by hex 41, the character 'R' by 52, and so forth.% java-algs4 BurrowsWheeler - < abra.txt | java-algs4 edu.princeton.cs.algs4.HexDump 16 00 00 00 03 41 52 44 21 52 43 41 41 41 41 42 42 128 bits
Now, given the next[] array and first, we can reconstruct the original input string because the first character of the ith original suffix is the ith character in the input string. In the example above, since first = 3, we know that the original input string appears in row 3; thus, the original input string starts with 'A' (and ends with '!'). Since next[first] = 7, the next original suffix appears in row 7; thus, the next character in the original input string is 'B'. Since next[next[first]] = 11, the next original suffix appears in row 11; thus, the next character in the original input string is 'R'.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
However, since 'R' appears twice, it may seem ambiguous whether next[10] = 1 and next[11] = 4, or whether next[10] = 4 and next[11] = 1. Here's the key rule that resolves the apparent ambiguity: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
If sorted row i and j both start with the same character and i < j, then next[i] < next[j].This rule implies next[10] = 1 and next[11] = 4. Why is this rule valid? The rows are sorted, so row 10 is lexicographically less than row 11. Thus, the ten unknown characters in row 10 must be less than the ten unknown characters in row 11 (since both start with 'R'). We also know that between the two rows that end with 'R', row 1 is less than row 4. But, the ten unknown characters in row 10 and 11 are precisely the first ten characters in rows 1 and 4. Thus, next[10] = 1 and next[11] = 4 or this would contradict the fact that the suffixes are sorted.
Check that the inverse transform recovers any transformed message.
% java-algs4 BurrowsWheeler - < abra.txt | java-algs4 BurrowsWheeler + ABRACADABRA!
Performance requirements. The running time of your Burrows-Wheeler transform should be proportional to N + R (or better) in the worst case, excluding the time to construct the circular suffix array. The running time of your Burrows-Wheeler inverse transform should be proportional to N + R (or better) in the worst case. The amount of memory used by both the Burrows-Wheeler transform and inverse transform should be proportional to N + R (or better) in the worst case.public class BurrowsWheeler { // apply Burrows-Wheeler transform, reading from standard input and writing to standard output public static void transform() // apply Burrows-Wheeler inverse transform, reading from standard input and writing to standard output public static void inverseTransform() // if args[0] is '-', apply Burrows-Wheeler transform // if args[0] is '+', apply Burrows-Wheeler inverse transform public static void main(String[] args) }
Analysis. Once you have MoveToFront.java and BurrowsWheeler.java working, compress some of these text files; then, test it on some binary files. Calculate the compression ratio achieved for each file and report the time to compress and expand each file. (Here, compression and expansion consists of applying BurrowsWheeler, MoveToFront, and Huffman in succession.) Finally, determine the order of growth of the running time of each of your methods, both in the worst case and on typical English text inputs.
Deliverables.
Submit MoveToFront.java, BurrowsWheeler.java, and CircularSuffixArray.java
along with any other helper files
needed to run your program (excluding those in algs4.jar).
Also submit a readme.txt
and answer all questions.