Week 5 - Regular Expressions & Data Compression #

public class NFA {

    private char[] re; // match transitions
    private Digraph G; // epsilon transition digraph 
    private int M; // number of states
    
    public NFA(String regexp) {
        M = regexp.length();
        re = regexp.toCharArray();
        G = buildEpsilonTransitionDigraph(); 
    }
    
    public boolean recognizes(String txt) {
        Bag<Integer> pc = new Bag<Integer>(); 
        DirectedDFS dfs = new DirectedDFS(G, 0); // states reachable from start by ε-transitions
        for (int v = 0; v < G.V(); v++) 
            if (dfs.marked(v)) pc.add(v);

        for (int i = 0; i < txt.length(); i++) {
            // states reachable after scanning past txt.charAt(i)
            Bag<Integer> match = new Bag<Integer>(); 
            for (int v : pc) {
                if (v == M) continue;
                if ((re[v] == txt.charAt(i)) || re[v] == '.')
                    match.add(v+1); 
            }

            // follow ε-transitions
            dfs = new DirectedDFS(G, match); 
            pc = new Bag<Integer>(); 
            for (int v = 0; v < G.V(); v++) 
                if (dfs.marked(v)) pc.add(v);
        }

        for (int v : pc) 
            if (v == M) return true; // accept if can end in state M
        return false;
    }
    
    private Digraph buildEpsilonTransitionDigraph() { 
        
        Digraph G = new Digraph(M+1); 
        Stack<Integer> ops = new Stack<Integer>(); 
        for (int i = 0; i < M; i++) { 
            int lp = i;
            if (re[i] == '(' || re[i] == '|') ops.push(i); // left parentheses and |
            else if (re[i] == ')') {
                int or = ops.pop(); 
                if (re[or] == '|') { // 2-way or
                    lp = ops.pop();
                    G.addEdge(lp, or+1);
                    G.addEdge(or, i); 
                } else lp = or;
            }
    
            // closure (needs 1-character lookahead)
            if (i < M-1 && re[i+1] == '*') { 
                G.addEdge(lp, i+1); 
                G.addEdge(i+1, lp); 
            }
            
            if (re[i] == '(' || re[i] == '*' || re[i] == ')') // metasymbols
                G.addEdge(i, i+1);
        } 
        return G;
    }
}

public class LZW {
    private static final int R = 256;        // number of input chars
    private static final int L = 4096;       // number of codewords = 2^W
    private static final int W = 12;         // codeword width

    // Do not instantiate.
    private LZW() { }

    /**
     * Reads a sequence of 8-bit bytes from standard input; compresses
     * them using LZW compression with 12-bit codewords; and writes the results
     * to standard output.
     */
    public static void compress() { 
        String input = BinaryStdIn.readString();
        TST<Integer> st = new TST<Integer>();

        // since TST is not balanced, it would be better to insert in a different order
        for (int i = 0; i < R; i++)
            st.put("" + (char) i, i);

        int code = R+1;  // R is codeword for EOF

        while (input.length() > 0) {
            String s = st.longestPrefixOf(input);  // Find max prefix match s.
            BinaryStdOut.write(st.get(s), W);      // Print s's encoding.
            int t = s.length();
            if (t < input.length() && code < L)    // Add s to symbol table.
                st.put(input.substring(0, t + 1), code++);
            input = input.substring(t);            // Scan past s in input.
        }
        BinaryStdOut.write(R, W);
        BinaryStdOut.close();
    } 

    /**
     * Reads a sequence of bit encoded using LZW compression with
     * 12-bit codewords from standard input; expands them; and writes
     * the results to standard output.
     */
    public static void expand() {
        String[] st = new String[L];
        int i; // next available codeword value

        // initialize symbol table with all 1-character strings
        for (i = 0; i < R; i++)
            st[i] = "" + (char) i;
        st[i++] = "";                        // (unused) lookahead for EOF

        int codeword = BinaryStdIn.readInt(W);
        if (codeword == R) return;           // expanded message is empty string
        String val = st[codeword];

        while (true) {
            BinaryStdOut.write(val);
            codeword = BinaryStdIn.readInt(W);
            if (codeword == R) break;
            String s = st[codeword];
            if (i == codeword) s = val + val.charAt(0);   // special case hack
            if (i < L) st[i++] = val + s.charAt(0);
            val = s;
        }
        BinaryStdOut.close();
    }

    /**
     * Sample client that calls {@code compress()} if the command-line
     * argument is "-" an {@code expand()} if it is "+".
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        if      (args[0].equals("-")) compress();
        else if (args[0].equals("+")) expand();
        else throw new IllegalArgumentException("Illegal command line argument");
    }

}