Burrows Wheeler transform

Burrows Wheeler transform helps rearranges a character string into runs of similar characters and useful for string comparison. Write a program to implement Burrows Wheeler transform.

Algorithm Explanation

	Initialize the string and generate all rotations, Sort the next sort those strings.
	Take the last character of each sorted string to get the Burrows-Wheeler transform.
	Compress the Burrows-Wheeler transform and get a much-compressed string even with no runs of repeated letters in the original.
	Run length encoding on a string and return the string. Print the compressed string.

Source Code

package com.dsacode.DataStructre.array;
 
public class CompressBurrowsWheeler {
 
     public static String Encode(String source){
         String result = "";
         int count = 1;
         char current = source.charAt(0);
          
         for(int i = 1; i < source.length(); i++) {
            if (source.charAt(i)==current)
               count = count + 1;
            else{
                result = result + count + current;
                count = 1;
                current = source.charAt(i);
            }
         }
         result = result + count + current;
         return result;
     }
 
 
     public static void generateRotations(String source, String[] s) {
         s[0] = source;
          
         for(int i = 1; i < source.length(); i++) {
            s[i] = s[i-1].substring(1) + s[i-1].charAt(0);
         }
     }
 
     public static String lastChars(String[] s, int SIZE){
         String result = "";
          
         for(int i = 0; i < SIZE; i++) {
            result = result + s[i].charAt(SIZE-1);
         }
          
         return result;
     }
 
 
     public static void printStringArray(String[] a, int SIZE) {
         for(int i = 0; i < SIZE; i++) {
            System.out.println(a[i]);
         }
         System.out.println();
 
     }
 
     public static void sortStrings(String[] a, int SIZE){
         for(int pass = 0; pass <= SIZE-2; pass++) {
           for(int i = 0; i <= SIZE-pass-2; i++)  {
               if (a[i].compareTo(a[i+1])>0)
                   swap(a, i, i+1);
           }
         }
     }
 
      
      public static void swap(String[] a, int i, int j){
        String t = a[i];
        a[i] = a[i+1];
        a[i+1] = t;
     }
 
      public static void main (String[] param)    {
        String text = "Hello world.";
 
        final int SIZE = text.length();
 
        String[] rotations = new String[SIZE];
        String result = "";
        String compressed = "";
         
        System.out.println(SIZE + " rotations" );
        System.out.println();
         
        generateRotations(text, rotations);
        printStringArray(rotations, SIZE);
        sortStrings(rotations, SIZE);
        printStringArray(rotations, SIZE);
 
        result = lastChars(rotations, SIZE);
        System.out.println(result);
         System.out.println();
 
        compressed = Encode(result);
        System.out.println(compressed);
        System.out.println("Compressed length: " + compressed.length());
        System.out.println();
        System.exit(0);
    }
  
}

Output

12 rotations
 
Hello world.
ello world.H
llo world.He
lo world.Hel
o world.Hell
 world.Hello
world.Hello
orld.Hello w
rld.Hello wo
ld.Hello wor
d.Hello worl
.Hello world
 
 world.Hello
.Hello world
Hello world.
d.Hello worl
ello world.H
ld.Hello wor
llo world.He
lo world.Hel
o world.Hell
orld.Hello w
rld.Hello wo
world.Hello
 
od.lHrellwo
 
1o1d1.1l1H1r1e2l1w1o1
Compressed length: 22