BWT(Burrows-Wheeler Transformation)の説明とjava実装

BWT(Burrows-Wheeler Transformation)
1.BWTとは
圧縮技術の主な仕事の方式は繰り返しのモードを見つけて、緊密な符号化を行うことです.
BWT(Burrows–Wheeler_transform)は、元のテキストを類似のテキストに変換し、変換後、同じ文字位置が連続的または隣接するようにし、その後、Move-to-front transformおよびコースコードなどの他の技術を使用してテキスト圧縮を行うことができる.
2.BWTの原理
2.1 BWT符号化
(1)まず,BWTはまず変換が必要なテキストブロックを右回りにループし,1ビットずつループする.長さnのテキストブロックがわかり,n回ループして繰り返すことで,n個の長さnを見る文字列が得られる.下の図の「Rotate Right」列のようです.(「#」は識別子としてテキストブロックの文字セットになく、nサイクルシフト後の文字列が同じであることを保証し、'#'が文字セットの任意の文字より小さいことを定義する).
(2)ループシフト後のn文字列をディクショナリ順に並べ替える.下図の「Sorted(M)」列のようです.
(3)「Sorted(M)」列の各文字列の最後の文字を記録し、「L」列を構成する.(ここで「F」列は「Sorted(M)」列の各文字列の接頭辞である)
すると、元の文字列「banana#」が「annb#aa」に変換されます.場合によっては、L列を使用して圧縮するとより効果的です.「L」列は符号化の結果である.
2.2 BWT復号
循環シフトが行われているので、循環左シフトは以下の性質に注意してください.
    　　1、
Lの最初の要素はTextの最後の要素です
    　　2、
Mの各行(最初の行を除く)について、最初の要素は最後の要素の次の要素です.
すなわち、テキストブロックの場合、同じ行のFはLの次の要素であり、LはFの前の要素である.
 
このようにして
(1)「F」列の要素を通じて、彼の前の文字を見つけて、対応する同じ行の「L」列です.
(2)「L」列の要素を通して、「F」列の対応する文字の位置を見つけます.しかし、「L」には3文字aがありますが、Fの3文字aにどう対応するのでしょうか.LはFの前の要素であるため、同じ接頭辞を持つ複数の文字列が並べ替えられ、共通接頭辞を除いた相対順序は変化しない.複数の同じ文字に遭遇した場合、相対的な位置は変わりません.
(3)終了するまで(1)に移動します.
ソート後の文字列BWT変換後の文字列
まずBWT変換後の文字列にドル記号「$」を見つけ、同じ行のアルファベットがBであることを書きます.$BがBを見つけた後、右の欄でBを探します.それに対応するのはAです.
そして$BAをメモして、
今Aのは左で3回目の出現で、だから右の1欄の中でAを探して、同じく3回目の出現で、それに対応するのはNで、それから$BANをメモして、左のN
2回目の出現なので、右の欄でNを探すのは同じように2回目の出現で、それに対応するのはAで、
それから$BANAをメモして、今Aの左側は2回目の出現で、だから右側で、1欄の中でAを探して同様に2回目の出現で、それに対応するのはNで、それから$BANANをメモします
左のNは初めてなので、右の欄でNを探すのも初めてですが、
これに対応するのはAで、それから$BANANAをメモして、今のAは左側で初めて現れたので、右の欄でAを探すのは同じように初めて現れたので、それに対応するのは「$」で、終わります.

package cn.genekang.io.test;



import java.util.Arrays;



public class BWTtest {



    public static void main(String[] args) {

        String str = "banana";

        System.out.println(" ："+str);

        String enCodeStr = enCode(str);

        System.out.println(" ："+enCodeStr);

        System.out.println(" ："+deCode(enCodeStr));

    }



    // bwt 

    public static String enCode(String line) {

        String str = line + "&";

        int len = str.length();

        // 1. 

        char[] charArray = str.toCharArray();

        char[][] ch = new char[len][len];

        for (int i = 0; i < len; i++) {

            char[] c_tmp = charArray.clone();

            for (int j = 0; j < len; j++) {

                ch[i][j] = c_tmp[j];

                if (j <= len - 2)

                    charArray[j + 1] = c_tmp[j];



            }

            charArray[0] = c_tmp[len - 1];



        }

        // 2. ， 

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

        // 3. 

        StringBuffer sBuffer = new StringBuffer();

        for (String s : strings) {

            sBuffer.append(s.substring(len - 1, len));

        }

        return sBuffer.toString();

    }



    // bwt 

    public static String deCode(String str) {

        int len = str.length();

        String[] strArr = new String[len];

        for (int i = 0; i < len; i++) {

            strArr[i] = str.substring(i, i + 1) + ":" + i;

        }

        Arrays.sort(strArr);

        // for(String string : strArr)

        // System.out.println(string);

        StringBuffer sb = new StringBuffer();

        int num = 0;

        int corr = Integer.parseInt(strArr[0].split(":")[1]);

        while (num < len-1) {            

            sb.append(strArr[corr].split(":")[0]);

            corr =Integer.parseInt( strArr[corr].split(":")[1]);

            num++;

        }

        return sb.toString();



    }



}