BWT算法将原来的文本转换为一个相似的文本，转换后使得相同的字符位置连续或者相邻，之后可以使用其他技术如：Move-to-fronttransform 和 游程编码 进行文本压缩。

BWT原理：

1. BWT编码

①对需要转换的字符串后加“$”符号（$作为标识符，保证n个循环移位后的字符串均布相同），进行循环右移，每次循环一位，记录下每次右移后的结果。

②对循环移位后得到的n个字符串按照字典序排序。

③记录下排序后得到的每个字符串的最后一个字符（得到L字符串）和第一个字符（得到F列）。

例如：apple

序号	移位记录M	排序后NM	F	L
1	apple$	$apple	$	e
2	$apple	apple$	a	$
3	e$appl	e$appl	e	l
4	le$app	le$app	l	p
5	ple$ap	ple$ap	p	p
6	pple$a	pple$a	p	a

 

2. BWT解码

因为进行的是循环移位，有如下性质：

①  L的第一个元素是输入字符串中的最后一个元素

②  同一行中F是L的下一个元素，L是F的前一个元素。

所以我们就可以得到：

①  F字符串可由L字符串推理得到

②  由于F序列中的字符与其相对位置和L序列中的字符与其相对位置是相对应的。因此，在每个字符串中，我们需要记录每个字符的相对位置（相对位置即指在本序列中该字符出现的第几次），例如：

 

F序列	$	a	e	l	p	p
相对位置	1	1	1	1	1	2
L序列	e	$	l	p	p	a
相对位置	1	1	1	1	2	1

 

根据上表，我们可得出原来的字符串：

如上例：字符串最后一位是e，根据L序列的e字符及其相对位置1，找到F序列中对应的（字符e及其相对位置1）, 与F序列的e字符及其相对位置1的同一行L序列字符为l其相对位置为1，所以原字符串e的前一位为l。以此类推，可得到原字符串。

参考：http://blog.csdn.net/blackjack_/article/details/73801003

          https://www.cnblogs.com/xudong-bupt/p/3763814.html

Java语言实现：

package bwt;import java.util.Arrays;
import java.util.Scanner;public class bwt2 {public static void main(String[] args) {System.out.print("请输入字符串：");Scanner sc = new Scanner(System.in);String str = sc.nextLine();String enCodeStr = enCode(str);System.out.println("编码后的字符串是："+enCodeStr.split(":")[0]);System.out.println("解码后的字符串是："+deCode(enCodeStr.split(":")[0],enCodeStr.split(":")[1]));}// bwt编码public static String enCode(String line) {String str = line+"$";int len = str.length();char[] charArray = str.toCharArray();char[][] ch = new char[len][len];char[] c_tmp = charArray.clone();for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {ch[i][j] = c_tmp[j];}char zj = c_tmp[len-1];for(int k = len-1;k>0;k--){c_tmp[k]=c_tmp[k-1];}c_tmp[0]=zj;}String[] strings = new String[len];for (int i = 0; i < len; i++) {StringBuffer chline = new StringBuffer();for (char c : ch[i]) {chline.append(c);}strings[i] = chline.toString();}Arrays.sort(strings);StringBuffer sBuffer = new StringBuffer();StringBuffer sBuffer2 = new StringBuffer();for (String s : strings) {sBuffer.append(s.substring(len - 1, len));}for (String s2 : strings) {sBuffer2.append(s2.substring(0, 1));}return sBuffer.toString()+":"+sBuffer2.toString();}// bwt解码public static String deCode(String str1,String str2) {int len=str1.length();char[] L = str1.toCharArray();char[] F = str2.toCharArray();int [] L1=new int[len];int [] F1=new int[len];for(int i=0;i<len;i++){L1[i]=1;F1[i]=1;}for(int i=0;i<len-1;i++){int num = 1;int num1 = 1;for(int j=i+1;j<len;j++){if(L[i]==L[j] && L1[j]==1){num++;L1[j]=num;}if(F[i]==F[j] && F1[j]==1){num1++;F1[j]=num1;}}}char result[]=new char[len];result[len-1]='$';result[len-2]=L[0];int newlen=len-2;int n1=0;while(newlen>0){for (int i=0;i<len;i++){if(F[i]==L[n1] && L1[n1]==F1[i]){newlen--;result[newlen]=L[i];n1=i;break;}}}String resultline = "";for(int i=0;i<len-1;i++){resultline=resultline+result[i];}return resultline;}
}