BWT算法解析及Java语言实现

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;
    }
}