[Codewar练习-java]Burrows-Wheeler-Transformation(BWT压缩算法)

问题：

段位：4

说明：

BWT压缩算法，是先枚举所有字符串移位后，再对移位后的字符串集合排序得出后缀以及原始数组索引的压缩算法，题目要求实现一次压缩算法以及压缩解压算法。

题目连接：

Burrows-Wheeler-Transformation：https://www.codewars.com/kata/54ce4c6804fcc440a1000ecb/train/java

输入案例：

Input: "bananabar"

所有的移位字符串集合：
b a n a n a b a r
r b a n a n a b a
a r b a n a n a b
b a r b a n a n a
a b a r b a n a n
n a b a r b a n a
a n a b a r b a n
n a n a b a r b a
a n a n a b a r b
Then we sort that matrix by its rows. The output of the transformation then is the last column and the row index in which the original string is in:

对字符串进行排序后：
               .-.
a b a r b a n a n
a n a b a r b a n
a n a n a b a r b
a r b a n a n a b
b a n a n a b a r <- 4
b a r b a n a n a
n a b a r b a n a
n a n a b a r b a
r b a n a n a b a
               '-'

Output: ("nnbbraaaa", 4)

---

我的代码：

首先是编码：

因为文本越长，如果全部字符串列举出来是不可能的，所以

1、先获得所有移位的头字符，以及头字符对应的字符串索引，形成一个头字符集合

2、根据头字符集合进行排序，字符串排序就是根据 ASCII 码表，将每一个字符比较并排序

3、头字符集合排序好之后，按顺序拿集合中头字符对应的字符串索引，然后获取属于移位后最后一个的字符，并记录原始数组的索引。

import java.util.*;
public class BurrowsWheeler {
    private static StringBuilder builder = new StringBuilder();
    public static BWT encode(String s) {
        builder.setLength(0);
        int len = s.length(), index = 0;
        char[] chs = s.toCharArray();
        boolean[] map = new boolean[256];
        Map<Character, List<Integer>> indexMap = new HashMap<Character, List<Integer>>();
        for(int i = 0;i < len;map[chs[i]] = true,i ++) { // 先 hash 排序一次, 并记录索引
            List<Integer> list = indexMap.getOrDefault(chs[i], new ArrayList<Integer>());
            list.add(i);
            indexMap.put(chs[i], list);
        }
        for(int i = 0;i < 256;i ++) {
            if(!map[i]) continue;
            List<Integer> list = indexMap.get((char)i);
            Collections.sort(list, new Comparator<Integer>() { // 每个字符开头排序一次
                @Override
                public int compare(Integer o1, Integer o2) {
                    int i = 1;
                    for(;i < len && chs[(o1 + i) % len] == chs[(o2 + i) % len];i ++);
                    return chs[(o1 + i) % len] > chs[(o2 + i) % len] ? 1 : -1;
                }
            });
            for(int l : list)
                if(l == 0) { // 拼最后一个, 并记录原始位置
                    index = builder.length();
                    builder.append(chs[len - 1]);
                }
                else builder.append(chs[l - 1]); // 拼前一个
        }
        return new BWT(builder.toString(), len == 0 ? -1 : index);
    }

    public static void main(String[] args) {
        System.out.println(new BWT("nnbbraaaa", 4).equals(BurrowsWheeler.encode("bananabar")));
        System.out.println(new BWT("e emnllbduuHB", 2).equals(BurrowsWheeler.encode("Humble Bundle")));
        System.out.println(new BWT("ww MYeelllloo", 1).equals(BurrowsWheeler.encode("Mellow Yellow")));
    }

    static class BWT {
        String res; int index;
        BWT(String res, int index){ this.res = res; this.index = index; }
        public boolean equals(BWT b) {
            System.out.println(b); return this.res.equals(b.res) && this.index == b.index;
        }
        public String toString() { return "obj :" + res + ":" + index; }
    }
}

然后解码：

1、先把输入的字符串进行排序，就获得第一排字符串，第一排字符串，都认为排在最后一排后面的字符。

2、根据最后一排，第一排字符串，进行分类排名。

3、因为根据编码时候，所有字符串都是排序过的，那么 从 原始索引开始，找到第一排的排名，根据排名(同一个字符，最后一排和第一排顺序上排名是一致的)在最后一排找到一样的排名然后获取索引。

4、最后从头到末尾把字符串排好。

最终代码：

import java.util.*;

public class BurrowsWheeler {

    public static void main(String[] args) {
        System.out.println(new BWT("nnbbraaaa", 4).equals(BurrowsWheeler.encode("bananabar")));
        
        System.out.println("bananabrbanrrabarr".equals(BurrowsWheeler.decode("rnnbbbrraaaaarrbna", 6)));
        System.out.println("bananabar".equals(BurrowsWheeler.decode("nnbbraaaa", 4)));
        System.out.println("Humble Bundle".equals(BurrowsWheeler.decode("e emnllbduuHB", 2)));
        System.out.println("Mellow Yellow".equals(BurrowsWheeler.decode("ww MYeelllloo", 1)));
    }

    private static StringBuilder builder = new StringBuilder();
    public static BWT encode(String s) {
        builder.setLength(0);
        int len = s.length(), index = 0;
        char[] chs = s.toCharArray();
        boolean[] map = new boolean[256];
        Map<Character, List<Integer>> indexMap = new HashMap<Character, List<Integer>>();
        for(int i = 0;i < len;map[chs[i]] = true,i ++) { // 先 hash 排序一次, 并记录索引
            List<Integer> list = indexMap.getOrDefault(chs[i], new ArrayList<Integer>());
            list.add(i);
            indexMap.put(chs[i], list);
        }
        for(int i = 0;i < 256;i ++) {
            if(!map[i]) continue;
            List<Integer> list = indexMap.get((char)i);
            Collections.sort(list, new Comparator<Integer>() { // 每个字符开头排序一次
                @Override
                public int compare(Integer o1, Integer o2) {
                    int i = 1;
                    for(;i < len && chs[(o1 + i) % len] == chs[(o2 + i) % len];i ++);
                    return chs[(o1 + i) % len] > chs[(o2 + i) % len] ? 1 : -1;
                }
            });
            for(int l : list) System.out.print(l);
            for(int l : list)
                if(l == 0) { // 拼最后一个, 并记录原始位置
                    index = builder.length();
                    builder.append(chs[len - 1]);
                }
                else builder.append(chs[l - 1]); // 拼前一个
        }
        return new BWT(builder.toString(), len == 0 ? -1 : index);
    }

    public static String decode(String s, int n) {
        if(n < 0) return "";
        builder.setLength(0);
        int len = s.length();
        char[] preArr = s.toCharArray(), nxtArr = s.toCharArray();
        Arrays.sort(nxtArr);
        Map<Character, List<Integer>> preMap = new HashMap<>(), nxtMap = new HashMap<>();
        for(int i = 0;i < len;i ++) { // 按字符, 将前缀和后继索引存放
            List<Integer> prelist = preMap.getOrDefault(preArr[i], new ArrayList<>()), nxtlist = nxtMap.getOrDefault(nxtArr[i], new ArrayList<>());
            prelist.add(i); nxtlist.add(i);
            preMap.put(preArr[i], prelist); nxtMap.put(nxtArr[i], nxtlist);
        }
        while(len -- > 0) {
            char temp = nxtArr[n];
            builder.append(temp); // 元素
            n = nxtMap.get(temp).indexOf(n); // 排名
            n = preMap.get(temp).get(n); // 索引位置
        }
        return builder.toString();
    }

    static class BWT {
        String res;
        int index;
        BWT(String res, int index){
            this.res = res;
            this.index = index;
        }
        public boolean equals(BWT b) {
            System.out.println(b);
            return this.res.equals(b.res) && this.index == b.index;
        }
        public String toString() {
            return "obj :" + res + ":" + index;
        }
    }
}

c++的代码居然出现乱码我也是醉了，没办法贴c++