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