LZW Compression - Variable Length Symbols, Fixed Length Codes - Java

LZW Compression has variable length symbols and fixed length codes.

Source:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.LinkedList;
import java.util.Queue;


public class LZW {
    private static int R = 256;
    private static int W = 12;   //Codeword width
    private static int L = 1<<W; //Number of codewords
    private static int c;        //No of code words written out compressed
    
    public static String compress(String in){
        TST<Integer> tst = new TST<>();
        for(int i=0;i<R;++i) tst.add((char)i+"", i); 
        int code = R+1;
        
        int i=0;
        c=1;
        StringBuilder out = new StringBuilder();
        while(i<in.length()){
            String longestPrefix = tst.longestPrefixOf(in.substring(i));
//            System.out.println("Substring : "+in.substring(i, i+1));
            int key = tst.getKey(longestPrefix);
//            System.out.println(longestPrefix+" "+key);
            out.append(key).append(" ");c++;
            int t = longestPrefix.length();
            if(i+t+1<=in.length() && code<L) {
                tst.add(in.substring(i, i+t+1), code++);
            } 
            i+=t;
        } 
        return out.append(R).toString();
    }
    
    private static String[] codes;
    
    public static String decompress(String input){
        String[] d = input.split(" ");
        int[] in = new int[d.length];
        for(int i=0;i<d.length;++i)in[i] = Integer.parseInt(d[i]); 
        codes = new String[L];
        for(int i=0;i<R;++i) codes[i] = (char)i+""; 
         
        StringBuilder out = new StringBuilder();
        int i=0, r = R; 
        String prev="";
        
        //256 is a special end character. Setting codes[256] to some value is not wrong. 
        //(This code does that in first iteration)
        while(true){
            int currentCode = in[i];
//            System.out.println("\nCurrent code = "+currentCode);
            String currentString = codes[currentCode];
//            System.out.println("Current string = "+currentString);
            if(in[i]==R)break;
            
            if(currentCode==r){ currentString = prev+prev.charAt(0);}
            if(r<L){
                codes[r++] = prev+currentString.charAt(0);
//                System.out.println("Set codes["+(r-1)+"] to "+codes[r-1]);
            }
//            System.out.println("Appending string "+currentString);
            out.append(currentString);
            prev = currentString;
            i++; 
        }
        return out.toString();
    }
    
    public static void testString(String s){
        String compressed = compress(s), decompressed;
        System.out.println("\n--> Compressed : "+compressed);
        System.out.println("\n--> Decompressed " +(decompressed = decompress(compressed)));
        
        System.out.println("\nUncompressed data uses "+s.length()*8+" bits. (Assuming 8-bit chars)");
        System.out.println("Compressed data uses "+c*W+" bits");
        
    }
    
    public static void main(String[] args) throws Exception{
        //compressed size more for small strings
        testString("ABABABA"); 
        
        //compression beneficial for larger strings
        testString("ABABABAABABABBABA"); 
        testString("AAAAABBABABBBBBBAAAAAABBBBBBAABABABABABABBABAAAABB");
        
        //Random Input File
        StringBuilder sb = new StringBuilder();
        String s;
        BufferedReader br = new BufferedReader(new FileReader(new File("d:\\input.txt")));
        while((s=br.readLine())!=null){
            sb.append(s);
        }
        testString(sb.toString());
    }
}  


//Ternary Search Trie used as a Symbol Table to match character values against codes.


class TST<T> {
    class Node{
        char c;
        T v;
        Node left, mid, right;
        
        Node(){}
        Node(char c){this.c = c;}
        Node(T v){this.v = v;}
        Node(char c, T v){this.c = c;this.v = v;}
    }
    
    Node root; 
    
    public void add(String s, T value){ 
       root = add(root, s, 0, value);
    }
    
    private Node add(Node n, String s, int i, T value){  
        if(n==null){ 
            n = new Node(s.charAt(i));
            if(i==s.length()-1){n.v = value; return n;}
        }
        if(s.charAt(i)==n.c){
            if(i==s.length()-1){n.v = value; return n;}
            n.mid = add(n.mid, s, i+1, value);
        }
        else if(s.charAt(i)<n.c){
            n.left = add(n.left, s, i, value);
        }
        else{
            n.right = add(n.right, s, i, value);
        }
        return n;
    }
    
    public T getKey(String s){ 
     
        return getKey(root, s, 0); 
    }
    
    private T getKey(Node n, String s, int i){  
        if(n==null) return null;
        if(i==s.length()-1){
            if(n.c==s.charAt(i)){
                if(n.v!=null)return n.v;
                else return null;
            }
        }else if(i>s.length())return null; 
        if(s.charAt(i)==n.c){
            return getKey(n.mid, s, i+1);
        }
        else if(s.charAt(i)<n.c){
            return getKey(n.left, s, i);
        }
        else {
            return getKey(n.right, s, i);
        }        
    }
    
    public void delete(String s){
        delete(root, s, 0);
    }
    
    private boolean delete(Node n, String s, int i){
        if(n==null) return false;
        if(i==s.length()-1){
            if(n.c==s.charAt(i)){
                if(n.v!=null){n.v = null;return true;}
                else return false;
            }
        }else if(i>s.length())return false; 
        
        boolean r;
        if(s.charAt(i)==n.c){
            if((r=delete(n.mid, s, i+1))){ 
                if(n.mid.v == null && n.mid.left == null 
                   && n.mid.mid == null && n.mid.right == null)n.mid = null;
            }
        }else if(s.charAt(i)<n.c){
            if((r=delete(n.left, s, i))){ 
                if(n.left.v == null && n.left.left==null 
                   && n.left.mid == null && n.left.right == null)n.left = null;
            }
        }else{
            if((r=delete(n.right, s, i))){ 
                if(n.right.v == null && n.right.left == null 
                   && n.right.mid == null && n.right.right == null)n.right = null; 
            } 
        }
        return r;
    }
    
    public Iterable<String> keys(){
        Queue<String> al = new LinkedList<>();
        String string = "";
        findKeys(root, al, string);  
        return al;
    }
    
    private void findKeys(Node n, Queue<String> al, String s){
        if(n==null)return;
        if(n.v!=null){al.add(s+n.c);}
        findKeys(n.left, al, s);
        String s2 = s+n.c;
        findKeys(n.mid, al, s2);
        findKeys(n.right,al, s);
    }
    
    public Iterable<String> keysWithPrefix(String prefix){
        Queue<String> al = new LinkedList<>();
        String string = "";
        findKeysP(root, al, string, prefix);  
        return al;
    }
    
    private void findKeysP(Node n, Queue<String> al, String s, String p){
        if(n==null)return;
        if(s.length()<=p.length() && s.length()!=0 && s.charAt(s.length()-1)!=p.charAt(s.length()-1)) return;
        if(n.v!=null){if(s.length()<p.length()&&n.c==p.charAt(s.length()))al.add(s+n.c);
        else if(s.length()>p.length())al.add(s+n.c);}
        findKeysP(n.left, al, s, p);
        
        String s2 = s+n.c;
        findKeysP(n.mid, al, s2, p);
        
        findKeysP(n.right,al, s, p);
    }
    
    public String longestPrefixOf(String s){
        String string = "";
        int l = longestPrefixOf(root, l=0, s);  
        return s.substring(0, l+1);
    }
    
    private int longestPrefixOf(Node n, int i, String p){ 
        if(n==null)return i-1;
        if(i>=p.length()) return i-1; 
         
        int l,m=Integer.MIN_VALUE,r;
        l = longestPrefixOf(n.left, i, p);
        if(n.c==p.charAt(i)) m = longestPrefixOf(n.mid, i+1, p);
        r = longestPrefixOf(n.right, i, p);
        return Math.max(l, Math.max(m, r));
    }
}

Output:

--> Compressed : 65 66 257 259 256

--> Decompressed ABABABA

Uncompressed data uses 56 bits. (Assuming 8-bit chars)
Compressed data uses 60 bits

--> Compressed : 65 66 257 259 259 258 66 262 65 256

--> Decompressed ABABABAABABABBABA

Uncompressed data uses 136 bits. (Assuming 8-bit chars)
Compressed data uses 120 bits

--> Compressed : 65 257 257 66 66 65 261 260 264 261 258 259 265 266 263 262 272 263 271 258 260 256

--> Decompressed AAAAABBABABBBBBBAAAAAABBBBBBAABABABABABABBABAAAABB

Uncompressed data uses 400 bits. (Assuming 8-bit chars)
Compressed data uses 264 bits

--> Compressed : 59 59 32 259 70 111 114 109 ... (output trimmed)

--> Decompressed ;;   Format of the site name database:;;   Column ...

Uncompressed data uses 528400 bits. (Assuming 8-bit chars)

Compressed data uses 238548 bits

Huffman Compression - Variable Length Codes - Java Implementation

Concept - Use fewer number of bits to represent frequently occurring characters and more number of bits to represent less frequently occurring characters.

Source:

import java.util.PriorityQueue; 

public class HuffmanCompression {
    public static class Node implements Comparable<Node>{
        private final char ch;
        private final int freq;
        private final Node left, right;
                
        public Node(char ch, int freq, Node left, Node right){
            this.ch = ch;
            this.freq = freq;
            this.left = left;
            this.right = right;
        }
        
        public boolean isLeaf(){
            return left==null && right==null;
        }
        
        public int compareTo(Node that){
            return this.freq-that.freq;
        }
    }
    
    private static final int R = 256;
    private static final int lgR = 8;
    private static int[] freq;
    private static Node root;
    private static String[] codes;
    
    public static Node buildTrie(){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for(int i=0;i<freq.length;++i){
            if(freq[i]!=0)pq.add(new Node((char)i, freq[i], null, null));
        }
         
        while(pq.size()>1){
            Node left = pq.poll();
            Node right = pq.poll(); 
            System.out.println("Paired "+left.ch+" : "+left.freq+" with "+right.ch+" : "+right.freq);
            Node parent = new Node('\0', left.freq+right.freq, left, right); 
            pq.add(parent);
        }
        return pq.poll();
    }
    
    public static void writeTrie(StringBuilder out, Node node){
        if(node.isLeaf()){
            writeInt(out, 1, 1);
            writeInt(out, node.ch, lgR);
            return;
        }
        writeInt(out, 0, 1);
        writeTrie(out, node.left);
        writeTrie(out, node.right);
    }
    
    public static Node readTrie(String in){
        int t = readInt(in, 1); 
        if(t==1){
            //A leaf node
            Node node = new Node((char)readInt(in, 8), 0, null, null);
            return node;
        }
        Node x = readTrie(in);
        Node y = readTrie(in);
        
        //No need for frequencies
        return new Node('\0', 0, x, y); 
    }
     
    public static void constructCodeTable(Node n, String s){
        if(n.isLeaf()){
            System.out.println("Representation for "+n.ch+" = "+s);
            codes[n.ch] = s;
            return;
        }  
        constructCodeTable(n.left, s+"0");
        constructCodeTable(n.right, s+"1"); 
    }
    
    public static String compress(String input){
        StringBuilder out = new StringBuilder();
        for(int i=0;i<input.length();++i){
            out.append(codes[input.charAt(i)]);
        }
        return out.toString();
    }
    
    public static String decompress(String input){
        StringBuilder out = new StringBuilder();
        Node traveler = root;
        for(int i=0;i<input.length();++i){
            
            if(input.charAt(i)=='1'){
                traveler = traveler.right;
            }else traveler = traveler.left;
            
            if(traveler.isLeaf()){
                out.append(traveler.ch);
                traveler = root;
            }
        }
        return out.toString();
    }
    
    //Helper Input/Output Functions
    public static void resetReader(){
        inputIndex = 0;
    }
    
    private static int inputIndex = 0;
    private static int readInt(String in, int width){  
        String bin = in.substring(inputIndex, inputIndex+width);
        inputIndex += width;
        return Integer.parseInt(bin, 2);
    }
    
    public static void writeInt(StringBuilder out, int x, int width){
        StringBuilder sb = new StringBuilder();
        String bin = Integer.toBinaryString(x); 
        int fill = width - bin.length();
        while(fill-->0)sb.append(0);
        sb.append(bin);

        //for viewing
        if(x==0)x='0';else if(x==1)x ='1';

        System.out.println("Writing "+sb+" for "+(char)x);
        out.append(sb);
    } 
    
    //Main
    public static void main(String[] args){
        testString("ABRACADABRA!");
        testString("THIS IS A PRETTY LONG AND BORING STRING");
        testString("I GOT NOTHING TO DO");
        testString("SHE SELLS SEA SHELLS BY THE SEA THE SHELLS SHE SELLS ARE SURELY SEASHELLS");
    }
    
    public static void testString(String s){ 
        System.out.println("\n\n\n\n###Testing String \""+s+"\" ###\n\n\n\n");
        freq = new int[R];
        codes = new String[R];
        
        for(int i=0;i<s.length();++i)freq[s.charAt(i)]++; 
        //Building a trie
        root = buildTrie();
        
        System.out.println("Building trie...");
        constructCodeTable(root, "");
        System.out.println();
        
        //Test writing and reading of tries
        StringBuilder out = new StringBuilder();
        System.out.println("\nWriting the trie for input string "+s+"\n");
        writeTrie(out, root); 
        
        Node readRootNode = readTrie(out.toString());
        resetReader();
        StringBuilder out2 = new StringBuilder();
        System.out.println("\nWrote the previous trie, reading it, and writing again...");
        writeTrie(out2, readRootNode);
        
        System.out.println("\nRepresentation of trie that was written earlier\n"+out);
        System.out.println("\nRepresentation of the new trie that was just written\n"+out2);
        System.out.println("\nMatches? "+(out.toString().matches(out2.toString())));
        
        //Test Compression and Decompression
        System.out.println("\nTesting compression and decompression...");
        String compressed = compress(s);
        System.out.println("\nCompressed representation of "+s+" is :\n"+compressed);
        String decompressed = decompress(compressed);
        System.out.println("\nDecompressed -> \n"+decompressed);
        System.out.println("\nOriginal string uses : "+s.length()*8+" bits");
        System.out.println("Compressed version uses : "+compressed.length()+" bits");
    }
}

Output: 

###Testing String "ABRACADABRA!" ###




Paired ! : 1 with C : 1
Paired D : 1 with   : 2
Paired R : 2 with B : 2
Paired   : 3 with   : 4
Paired A : 5 with   : 7
Building trie...
Representation for A = 0
Representation for D = 100
Representation for ! = 1010
Representation for C = 1011
Representation for R = 110
Representation for B = 111


Writing the trie for input string ABRACADABRA!

Writing 0 for 0
Writing 1 for 1
Writing 01000001 for A
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01000100 for D
Writing 0 for 0
Writing 1 for 1
Writing 00100001 for !
Writing 1 for 1
Writing 01000011 for C
Writing 0 for 0
Writing 1 for 1
Writing 01010010 for R
Writing 1 for 1
Writing 01000010 for B

Wrote the previous trie, reading it, and writing again...
Writing 0 for 0
Writing 1 for 1
Writing 01000001 for A
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01000100 for D
Writing 0 for 0
Writing 1 for 1
Writing 00100001 for !
Writing 1 for 1
Writing 01000011 for C
Writing 0 for 0
Writing 1 for 1
Writing 01010010 for R
Writing 1 for 1
Writing 01000010 for B

Representation of trie that was written earlier
01010000010010100010001001000011010000110101010010101000010

Representation of the new trie that was just written
01010000010010100010001001000011010000110101010010101000010

Matches? true

Testing compression and decompression...

Compressed representation of ABRACADABRA! is :
0111110010110100011111001010

Decompressed -> 
ABRACADABRA!

Original string uses : 96 bits
Compressed version uses : 28 bits




###Testing String "THIS IS A PRETTY LONG AND BORING STRING" ###




Paired B : 1 with D : 1
Paired L : 1 with Y : 1
Paired E : 1 with H : 1
Paired P : 1 with   : 2
Paired O : 2 with   : 2
Paired   : 2 with A : 2
Paired G : 3 with R : 3
Paired   : 3 with S : 3
Paired   : 4 with T : 4
Paired I : 4 with N : 4
Paired   : 4 with   : 6
Paired   : 6 with   : 7
Paired   : 8 with   : 8
Paired   : 10 with   : 13
Paired   : 16 with   : 23
Building trie...
Representation for E = 00000
Representation for H = 00001
Representation for A = 0001
Representation for T = 001
Representation for I = 010
Representation for N = 011
Representation for O = 1000
Representation for L = 10010
Representation for Y = 10011
Representation for P = 10100
Representation for B = 101010
Representation for D = 101011
Representation for S = 1011
Representation for G = 1100
Representation for R = 1101
Representation for   = 111


Writing the trie for input string THIS IS A PRETTY LONG AND BORING STRING

Writing 0 for 0
Writing 0 for 0
Writing 0 for 0
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01000101 for E
Writing 1 for 1
Writing 01001000 for H
Writing 1 for 1
Writing 01000001 for A
Writing 1 for 1
Writing 01010100 for T
Writing 0 for 0
Writing 1 for 1
Writing 01001001 for I
Writing 1 for 1
Writing 01001110 for N
Writing 0 for 0
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01001111 for O
Writing 0 for 0
Writing 1 for 1
Writing 01001100 for L
Writing 1 for 1
Writing 01011001 for Y
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01010000 for P
Writing 0 for 0
Writing 1 for 1
Writing 01000010 for B
Writing 1 for 1
Writing 01000100 for D
Writing 1 for 1
Writing 01010011 for S
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01000111 for G
Writing 1 for 1
Writing 01010010 for R
Writing 1 for 1
Writing 00100000 for  

Wrote the previous trie, reading it, and writing again...
Writing 0 for 0
Writing 0 for 0
Writing 0 for 0
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01000101 for E
Writing 1 for 1
Writing 01001000 for H
Writing 1 for 1
Writing 01000001 for A
Writing 1 for 1
Writing 01010100 for T
Writing 0 for 0
Writing 1 for 1
Writing 01001001 for I
Writing 1 for 1
Writing 01001110 for N
Writing 0 for 0
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01001111 for O
Writing 0 for 0
Writing 1 for 1
Writing 01001100 for L
Writing 1 for 1
Writing 01011001 for Y
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01010000 for P
Writing 0 for 0
Writing 1 for 1
Writing 01000010 for B
Writing 1 for 1
Writing 01000100 for D
Writing 1 for 1
Writing 01010011 for S
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01000111 for G
Writing 1 for 1
Writing 01010010 for R
Writing 1 for 1
Writing 00100000 for  

Representation of trie that was written earlier
000001010001011010010001010000011010101000101001001101001110000101001111010100110010101100100101010000010100001010100010010101001100101000111101010010100100000

Representation of the new trie that was just written
000001010001011010010001010000011010101000101001001101001110000101001111010100110010101100100101010000010100001010100010010101001100101000111101010010100100000

Matches? true

Testing compression and decompression...

Compressed representation of THIS IS A PRETTY LONG AND BORING STRING is :
00100001010101111101010111110001111101001101000000010011001111110010100001111001110001011101011111101010100011010100111100111101100111010100111100

Decompressed -> 
THIS IS A PRETTY LONG AND BORING STRING

Original string uses : 312 bits
Compressed version uses : 146 bits




###Testing String "I GOT NOTHING TO DO" ###




Paired D : 1 with H : 1
Paired I : 2 with   : 2
Paired N : 2 with G : 2
Paired T : 3 with   : 4
Paired O : 4 with   : 4
Paired   : 4 with   : 7
Paired   : 8 with   : 11
Building trie...
Representation for O = 00
Representation for   = 01
Representation for I = 100
Representation for D = 1010
Representation for H = 1011
Representation for T = 110
Representation for N = 1110
Representation for G = 1111


Writing the trie for input string I GOT NOTHING TO DO

Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01001111 for O
Writing 1 for 1
Writing 00100000 for  
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01001001 for I
Writing 0 for 0
Writing 1 for 1
Writing 01000100 for D
Writing 1 for 1
Writing 01001000 for H
Writing 0 for 0
Writing 1 for 1
Writing 01010100 for T
Writing 0 for 0
Writing 1 for 1
Writing 01001110 for N
Writing 1 for 1
Writing 01000111 for G

Wrote the previous trie, reading it, and writing again...
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01001111 for O
Writing 1 for 1
Writing 00100000 for  
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01001001 for I
Writing 0 for 0
Writing 1 for 1
Writing 01000100 for D
Writing 1 for 1
Writing 01001000 for H
Writing 0 for 0
Writing 1 for 1
Writing 01010100 for T
Writing 0 for 0
Writing 1 for 1
Writing 01001110 for N
Writing 1 for 1
Writing 01000111 for G

Representation of trie that was written earlier
0010100111110010000000101001001010100010010100100001010101000101001110101000111

Representation of the new trie that was just written
0010100111110010000000101001001010100010010100100001010101000101001110101000111

Matches? true

Testing compression and decompression...

Compressed representation of I GOT NOTHING TO DO is :
1000111110011001111000110101110011101111011100001101000

Decompressed -> 
I GOT NOTHING TO DO

Original string uses : 152 bits
Compressed version uses : 55 bits




###Testing String "SHE SELLS SEA SHELLS BY THE SEA THE SHELLS SHE SELLS ARE SURELY SEASHELLS" ###




Paired B : 1 with U : 1
Paired Y : 2 with T : 2
Paired   : 2 with R : 2
Paired   : 4 with   : 4
Paired A : 4 with H : 7
Paired   : 8 with L : 11
Paired   : 11 with   : 13
Paired E : 14 with S : 16
Paired   : 19 with   : 24
Paired   : 30 with   : 43
Building trie...
Representation for E = 00
Representation for S = 01
Representation for Y = 10000
Representation for T = 10001
Representation for B = 100100
Representation for U = 100101
Representation for R = 10011
Representation for L = 101
Representation for A = 1100
Representation for H = 1101
Representation for   = 111


Writing the trie for input string SHE SELLS SEA SHELLS BY THE SEA THE SHELLS SHE SELLS ARE SURELY SEASHELLS

Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01000101 for E
Writing 1 for 1
Writing 01010011 for S
Writing 0 for 0
Writing 0 for 0
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01011001 for Y
Writing 1 for 1
Writing 01010100 for T
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01000010 for B
Writing 1 for 1
Writing 01010101 for U
Writing 1 for 1
Writing 01010010 for R
Writing 1 for 1
Writing 01001100 for L
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01000001 for A
Writing 1 for 1
Writing 01001000 for H
Writing 1 for 1
Writing 00100000 for  

Wrote the previous trie, reading it, and writing again...
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01000101 for E
Writing 1 for 1
Writing 01010011 for S
Writing 0 for 0
Writing 0 for 0
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01011001 for Y
Writing 1 for 1
Writing 01010100 for T
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01000010 for B
Writing 1 for 1
Writing 01010101 for U
Writing 1 for 1
Writing 01010010 for R
Writing 1 for 1
Writing 01001100 for L
Writing 0 for 0
Writing 0 for 0
Writing 1 for 1
Writing 01000001 for A
Writing 1 for 1
Writing 01001000 for H
Writing 1 for 1
Writing 00100000 for  

Representation of trie that was written earlier
0010100010110101001100001010110011010101000010100001010101010110101001010100110000101000001101001000100100000

Representation of the new trie that was just written
0010100010110101001100001010110011010101000010100001010101010110101001010100110000101000001101001000100100000

Matches? true

Testing compression and decompression...

Compressed representation of SHE SELLS SEA SHELLS BY THE SEA THE SHELLS SHE SELLS ARE SURELY SEASHELLS is :
01110100111010010110101111010011001110111010010110101111100100100001111000111010011101001100111100011101001110111010010110101111011101001110100101101011111100100110011101100101100110010110000111010011000111010010110101

Decompressed -> 
SHE SELLS SEA SHELLS BY THE SEA THE SHELLS SHE SELLS ARE SURELY SEASHELLS

Original string uses : 584 bits
Compressed version uses : 218 bits