压缩算法原理

背景

会员管理后台需要记录接口的调用日志，由于接口的出参可能过大而超过数据库字段所能容忍的大小时插入日志数据就会报错，为了解决这个问题所以需要将出入参进行压缩后再进行保存。

一、BWT算法（Burrows-Wheeler Transform）

‌BWT算法（Burrows-Wheeler Transform）是一种数据变换算法，通过BWT变换可以将相同的字符聚集到一块，以简化索引，提升压缩效果‌。BWT算法可以分为正向数据变换运算和逆向数据恢复运算。‌BWT算法可以分为编码和解码两部分。编码后，原始字符串中的相似字符会处在比较相邻的位置；解码就是将编码后的字符串重新恢复成原始字符串的过程。BWT的一个特点就是经过编码后的字符串可以完全恢复成原始字符串。

1、编码步骤

BWT编码分为以下几步：

1、输入一个字符串s，假设其中所有字符都介于a-z之间。

2、在s的末尾加上一个标记字符，该字符要比s 中的所有字符都要小。比如$字符。这样将末尾加上标记的新字符串记为ss 。

3、重复地将ss 中的最后一个字符转移到开头，每转移一次就得到一个新的字符串。

4、将上一步得到的所有新字符串从小到大排序，排序后的字符串数组记为M。

5、M中每个字符串的第一个字符构成F 列，M 中每个字符串的最后一个字符构成L 列

6、将M列按照大小排序(可根据ASCII码排序，但请保证$永远是最小的，排在F列的第一行)

7、输出L 列。

2、解码步骤

通过上述编码后我们可以得到两列数据，F列和L列。我们使用F列于L列两列整合就能得到原始字符串。

1、找到L列的 $ 符号为起始点，查看他对应的F列然后进行拼接。

2、然后找到上一步的F列在L列对应的字母，然后查看找到的L列对应的F列，然后继续拼接。重复1、2步骤即可，其中注意F列中的相同字母的位置于L列字母的位置相对是不变的，例如F列第一个字母 a 在L列 中也对应了 第一个字母a （对应BWT性质2）。

3、BWT性质

1、L列是M列的前一个数据。

解释：L列的数据都是上个字符向迁移后得到的结果，所以L列的前一位字符一定是M列同行数的字符。

2、M列于L列相同字母的相对位置是固定不变的。

解释：在上述图片中的例子可以看出来，M列出现的第一个 a 与L列出现的第一个 a 是同一个字符(因为是字符迁移的结果)。所以M列第二个出现的 a 与L列第二个出现的 a 也是同一个。那么将M列进行排序后，他们的对应关系是不变的，因为不管排序与否第一条性质始终是成立的(同一列相同字符相对位置不变的情况)，所以始终可以通过L列与M列去还原原始的字符串。

字符串经过上述BWT处理后就以及可以进行简单的压缩了。例如上图例子，只需存储M列和L列数据即可。相同字符可以用字符+数字表示。例如M列 aabbc 可以表示为 a2b2c ,L列亦是如此。字符串中包含大量重复的数据压缩率会更高。

二、‌MTF算法（Move To Front）

‌MTF算法（Move To Front）是一种简单的无损数据压缩算法，它利用数据中存在的重复性来减少所需的存储空间‌。MTF算法的基本原理是将输入数据序列中的每个符号（例如字符）映射到一个变长的编码序列，编码的长度取决于该符号在序列中出现的频率和最近的出现位置。出现频率越高或距离最近，编码长度越短。‌

1、编码步骤

1、初始化：创建一个包含所有可能符号的列表（例如ASCII字符集），并初始化一个空的输出编码列表。

2、遍历输入数据：逐个读取输入数据序列中的符号。

3、移动到前（Move To Front）：对于每个读取的符号，将其在列表中移动到最前面。

4、编码符号：输出符号在列表中的索引作为编码。

5、重复：重复步骤3和4，直到所有输入数据都被读取和编码。

2、示例

假设我们有以下输入序列：`AAAABBBCCDAA`

1、编码

初始化：符号列表 = `[A, B, C, D]`

初始索引为：A-0; B-1;C-3;D-4；

遍历输入： - 第一个A：移动到前，列表 = `[A, B, C, D]`，编码 = `0` A在初始列表中的索引为0 - 第二个A：移动到前，列表 = `[A, B, C, D]`，编码 = `0` A在更新列表中的索引为0 - 第三个A：移动到前，列表 = `[A, B, C, D]`，编码 = `0` A在更新列表中的索引为0 - 第四个A：移动到前，列表 = `[A, B, C, D]`，编码 = `0` A在更新列表中的索引为0 - 第一个B：移动到前，列表 = `[B, A, C, D]`，编码 = `1` B在[A, B, C, D]中的索引为1 - 第二个B：移动到前，列表 = `[B, A, C, D]`，编码 = `0` B在[B, A, C, D]中的索引为0 - 第三个B：移动到前，列表 = `[B, A, C, D]`，编码 = `0` B在[B, A, C, D]中的索引为0 - 第一个C：移动到前，列表 = `[C, B, A, D]`，编码 = `2` C在[B, A, C, D]中的索引为2 - 第二个C：移动到前，列表 = `[C, B, A, D]`，编码 = `0` C在[C, B, A, D]中的索引为0 - 第一个D：移动到前，列表 = `[D, C, B, A]`，编码 = `3` D在[C, B, A, D]中的索引为3

- 第一个A：移动到前，列表 = `[A, D, C, B]`，编码 = `3` A在[D, C, B, A]中的索引为3 - 第二个A：移动到前，列表 = `[A, D, C, B]`，编码 = `0` A在[A, D, C, B]中的索引为0

输出编码序列：`000010020330`

4、还原

初始化：符号列表 = `[A, B, C, D]`

初始索引为：A-0; B-1;C-3;D-4；

编码序列：`000010020330`

- 第一个0：移动到前，列表 = `[A, B, C, D]`，输出= `A` A在初始列表中的索引为0 - 第二个0：移动到前，列表 = `[A, B, C, D]`，输出= `A` A在更新列表中的索引为0 - 第三个0：移动到前，列表 = `[A, B, C, D]`，输出= `A` A在更新列表中的索引为0 - 第四个0：移动到前，列表 = `[A, B, C, D]`，输出= `A` A在更新列表中的索引为0 - 第一个1：移动到前，列表 = `[B, A, C, D]`，输出= `B` B在[A, B, C, D]中的索引为1 - 第二个0：移动到前，列表 = `[B, A, C, D]`，输出= `B` B在[B, A, C, D]中的索引为0 - 第三个0：移动到前，列表 = `[B, A, C, D]`，输出= `B` B在[B, A, C, D]中的索引为0 - 第一个2：移动到前，列表 = `[C, B, A, D]`，输出= `C` C在[B, A, C, D]中的索引为2 - 第二个0：移动到前，列表 = `[C, B, A, D]`，输出= `C` C在[C, B, A, D]中的索引为0 - 第一个3：移动到前，列表 = `[D, C, B, A]`，输出= `D` D在[C, B, A, D]中的索引为3

- 第一个3：移动到前，列表 = `[A, D, C, B]`，输出= `A` A在[D, C, B, A]中的索引为3 - 第二个0：移动到前，列表 = `[A, D, C, B]`，输出= `A` A在[A, D, C, B]中的索引为0

输出原文：AAAABBBCCDAA

3、压缩思想

通过上述例子就完成了对字符的压缩，我们可以将 AA 作为一个整体放入符号列表中就可以实现压缩

三、哈夫曼编码

‌哈夫曼编码（Huffman Coding）是一种用于无损数据压缩的熵编码算法，由大卫·哈夫曼（David A. Huffman）在1952年发明‌。其基本思想是根据字符在数据中出现的频率来分配不同长度的编码，频率高的字符分配较短的编码，频率低的字符分配较长的编码，从而达到数据压缩的目的。‌

1、哈夫曼树

给定 n 个权值分别为 w 的结点

1）将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。

2）构造一个新结点，从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。

3）从 F 中删除刚才选出的两棵树，同时将新得到的树加入F中。

4）重复步骤2）和 3）, 直至F中只剩下一棵树为止。

哈夫曼树特点

1）每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。

2）构造过程中共新建了n-1个结点 （双分支结点），因此哈夫曼树的结点总数为2n- 1 。

3）每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为1 的结点。

2、哈夫曼树构建图示

假设有 8个节点，这8个节点的权值为{5，29，7，8，14，23，3，11}, 那么哈夫曼树构造过程如下图所示。

其中每次都会删除两个最小节点，生成一个新的节点。至于途中的节点放在左边还是右边或者是与其他节点的上、下位置是否放在同一条线上面都没有关系。因为每次都会找到最小两个节点去生成新节点，所以最终都只会有一个根节点，所以哈夫曼树相同的权值构造出来的哈夫曼树形态不唯一。

3、哈夫曼编码

我们将第二点的 8 个节点按顺序用字母代替 {A (5)，B(29)，C(7)，D(8)，E(14)，F(23)，G(3)，H(11) } , 我们定义 0 为树的左子树， 1 为树的右子树。

1、编码

根据上图最后一张图我们可以进行如下编码(从根节点开始)：

A：0001 (左-左-左-右)

B：10 (右-左)

C: 1110 (右-右-右-左)

D - H 依次类推

我们输入一下序列：ABBC

根据上述编码可以将序列 转换成 000110101110 。到这就完成了哈夫曼编码。

2、解码

编码序列：000110101110

根据上图最后一张图我们可以从根节点开始找，找到叶子节点结束。0001→A ，10 → B , 10 → B , 1110 → C 。最终还原序列：ABBC。这个解码例子为了方便直接使用了上图中的哈夫曼树，但是实际上每个字符串都有自己对应的哈夫曼树(我们可以将字符出现的频率作为权重)，ABBC的哈夫曼树可以与上图肯定是不同的。

这样我们就将字符传转换成了二进制编码，注意 ：二进制编码的单位是位(bit)， 而字符根据不同的格式单位是不同的，已UFT-8为例，它使用1到4个字节（即8到32位）来表示一个字符。所以到此已经对字符完成了压缩。并且也可以像WTF一样 将重复的字符看作一个整体进行进一步压缩。

那么我们可以使用 BWT处理字符串，然后使用 WTF 压缩字符串， 然后再用哈夫曼编码进行进一步压缩，那么你就得到了一个简略的压缩方法。

四、案例

我们使用第一步bwt的序列化做演示

第一步：bwt

F列：$aabbc

L列：c$baab

第二步: mtf

初始化：符号列表 = [$,a,b,c]

初始索引为：$-0; a-1; b-2;c-3;

首先我们将L列拼接F列得到新的序列：c$baab$aabbc

然后通过mtf得到编码： 313301220203

第三步：哈夫曼编码

首先我们将字符出现的频率作为权重构建哈夫曼树(括号数字表示出现频率)

0(3) 1(2) 2(3) 3(4)

构建得到如下哈夫曼树

其中叶子节点从左到右分别为 2(1) 3(0) 3(2) 4(3) , 其中括号中表示上述mtf编码后包含的数字。可以看到有两个值为3的节点，他们分别代表mtf编码里面的0 和 2，这个位置无所谓，从左到右也可以为 2(1) 3(2) 3(0) 4(3) 位置无关紧要。

我们以 2(1) 3(0) 3(2) 4(3) 的叶子节点顺序对mtf编码进行进一步的压缩编码。

我们计算出每个数字的编码如下

0： 01

1: 00

2: 10

3：11

然后通过哈夫曼编码得到压缩编码： 110011110100101001100111

解码

1、110011110100101001100111通过哈夫曼树可解码为：313301220203

2、313301220203通过mtf的符号列表（[$,a,b,c]）解码为：c$baab$aabbc

3、c$baab$aabbc通过截取第二个$得到两串字符：c$baab、$aabbc。其中第一串为L列，第二串为F列

4、将F列和L列通过BWT的特性还原最终得到原文: ababc

五、示例代码

ZipUtil

import java.util.*;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

public class ZipUtil {

public static void main(String[] args) {

String seq = "ababc";

// String seq = "{\n" +

// " \"sex\": \"男\",\n" +

// " \"name\": \"测试人员： d\"\n" +

// "}";

System.out.println("=================================================================");

System.out.println("原始字符串："+seq);

System.out.println("=================================================================");

System.out.println();

Bwt bwt = new Bwt();

String bwtCode = bwt.enCode(seq);

System.out.println("=================================================================");

System.out.println("BWT编码："+bwtCode);

System.out.println("=================================================================");

System.out.println();

Mtf mtf = new Mtf();

String mtfCode = mtf.enCode(bwtCode);

System.out.println("=================================================================");

System.out.println("MTF编码："+mtfCode);

System.out.println("=================================================================");

System.out.println();

Haffuman haffuman = new Haffuman();

byte[] haffumanEnCode = haffuman.enCode(mtfCode);

System.out.println("Haffuman编码："+ Arrays.toString(haffumanEnCode));

System.out.println("=================================================================");

System.out.println();

String haffumanDecode = haffuman.deCode(haffumanEnCode);

System.out.println("Haffuman解码："+haffumanDecode);

System.out.println("=================================================================");

System.out.println();

String mtfDecode = mtf.deCode(haffumanDecode);

System.out.println("MTF解码："+mtfDecode);

System.out.println("=================================================================");

System.out.println();

String bwtDeCode = bwt.deCode(mtfDecode);

System.out.println("BWT解码："+ bwtDeCode);

System.out.println("=================================================================");

System.out.println();

}

}

BWT

public class Bwt{

// bwt编码

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

}

//排序里面注意将$视为最小

sortByBwt(strings);

// 3.取最后一行

StringBuffer sBuffer = new StringBuffer();

for (String s : strings) {

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

}

return sBuffer.toString();

}

public String deCode(String seq){

StringBuilder orginSeq = new StringBuilder();

//传递进来L列即可

String lCloumn= seq;

char[] chars = seq.toCharArray();

//L列排序后就是F列 注意将$符号移动至最前端(因为我们定义$符号最小)

Arrays.sort(chars);

for (int i = 0; i < chars.length; i++) {

if(chars[i] == '$'){

for (int j = i; j > 0; j--) {

chars[j] = chars[j-1];

}

chars[0] = '$';

break;

}

}

String fCloumn = new String(chars);

//从L列查找$符号位置，从这里为起点进行还原

int index = lCloumn.indexOf("$");

char charAt = fCloumn.charAt(index);

orginSeq.append(charAt);

//F列的$为结束位置

while (fCloumn.charAt(index) != '$'){

//因为F列是有序的，那么我们找到一个字符后只需要往上对比是否一致。直到找到不一致的字符那么就可以知道该字符在F列相同字符的第几个

int currentCharIndex = getCurrentCharIndex(fCloumn,charAt,index);

//这里根据正则查找这个相同字符在L列的下标

index = getNthCharPosition(lCloumn,charAt,currentCharIndex);

//取F列对应index下标的字符拼接

charAt = fCloumn.charAt(index);

//结束符不需要拼接

if(fCloumn.charAt(index) != '$'){

orginSeq.append(charAt);

}

}

return orginSeq.toString();

}

private int getCurrentCharIndex(String fCloumn,char achar,int begin){

Integer index = 0;

while (begin>0 && fCloumn.charAt(begin) == achar){

index++;

begin--;

}

return index;

}

private int getNthCharPosition(String str, char c, int n) {

String regex = "(.*?" + Pattern.quote(String.valueOf(c)) + ")";

Pattern pattern = Pattern.compile(regex);

Matcher matcher = pattern.matcher(str);

int pos = -1;

while (n > 0 && matcher.find()) {

pos = matcher.end(1) - 1;

n--;

}

return pos;

}

private void sortByBwt(String[] strings){

int n = strings.length;

for (int i = 1; i < n; i++) {

String string = strings[i];

int j = i - 1;

while (j >= 0 && !comparaString(strings[j],string)) {

strings[j + 1] = strings[j];

j--;

}

strings[j + 1] = string;

}

}

private boolean comparaString(String string, String string1) {

for (int i = 0; i < string.length(); i++) {

char c = string.charAt(i);

char c1 = string1.charAt(i);

if(c == '$'){

return true;

}else if(c == c1){

continue;

} else{

return c - c1 < 0;

}

}

return false;

}

}

MTF

public class Mtf{

//字典表信息

private List dict = new ArrayList<>();

public String enCode(String seq){

dict.clear();

StringBuilder mtfStr = new StringBuilder();

char[] chars = seq.toCharArray();

for (char aChar : chars) {

if(dict.contains(aChar)){

continue;

}

dict.add(aChar);

}

List dictTemp = new ArrayList(dict);

for (char aChar : chars) {

//获取字典表中的符号所在位置，并且更新字典表将当前字符移动至字典表的第0个。

//加上 ; 标识下标结束位置，因为如果字典表超过10个 那么10的下标不加分隔符的话会被认为是1 和 0

mtfStr.append(getPos(aChar,dictTemp)+";");

}

return mtfStr.toString();

}

public String deCode(String seq){

StringBuilder orginSeq = new StringBuilder();

if(dict.isEmpty()){

return null;

}

List dictTemp = new ArrayList(dict);

//按分隔符分割取下标

String[] split = seq.split(";");

for (int i = 0; i < split.length; i++) {

//获取字典表中的对应位置的字符，并且更新字典表将当前字符移动至字典表的第0个。

orginSeq.append(pos2Char(Integer.valueOf(split[i]),dictTemp));

}

return orginSeq.toString();

}

private char pos2Char(int target, List dictTemp){

Character remove = dictTemp.remove(target);

dictTemp.add(0,remove);

return remove;

}

private int getPos(char target, List dictTemp){

for (int i = 0; i < dictTemp.size(); i++) {

Character character = dictTemp.get(i);

if(character.equals(target)){

Character remove = dictTemp.remove(i);

dictTemp.add(0,remove);

return i;

}

}

return 0;

}

}

Haffuman

public class Haffuman{

private HaffumanNode root;

private Map haffumanCode = new HashMap<>();

private class HaffumanNode implements Comparable{

private Integer weight;

private Character value;

private HaffumanNode parent;

private HaffumanNode left;

private HaffumanNode right;

private byte[] code = new byte[0];

@Override

public int compareTo(HaffumanNode node) {

return this.weight - node.weight;

}

}

public byte[] enCode(String seq){

byte[] result = new byte[0];

//创建哈夫曼树

root = createHuffmanTree(seq);

//创建哈夫曼编码映射

getHaffumanCodeMap();

char[] chars = seq.toCharArray();

for (char aChar : chars) {

//获取哈夫曼编码

byte[] bytes = haffumanCode.get(aChar);

//生成新的编码

for (byte aByte : bytes) {

result = getNewByteArray(result,aByte);

}

}

return result;

}

public String deCode(byte[] haffumanEnCode) {

StringBuilder result = new StringBuilder();

HaffumanNode queryNode = root;

//根据编码从根节点遍历树

for (byte b : haffumanEnCode) {

if(b == 1){

queryNode = queryNode.right;

}else{

queryNode = queryNode.left;

}

//找到叶子节点，解码。重新从根节点开始查找

if (isLeafNode(queryNode)){

result.append(queryNode.value);

queryNode = root;

}

}

return result.toString();

}

private void getHaffumanCodeMap(){

haffumanCode.clear();

preTraverse() ;

//前序遍历.将叶节点的属性保存到map中

List stack = new LinkedList<>() ;

HaffumanNode p = this.root ;

while(p != null || !stack.isEmpty()) {

while(p != null) {

stack.add(p) ;

p = p.left ;

}

//如果栈不空,去栈顶元素,然后向右

if(!stack.isEmpty()) {

p = ((LinkedList) stack).pop() ;

if(isLeafNode(p)) {

haffumanCode.put(p.value, p.code) ;

}

p = p.right ;

}

}

}

private void preTraverse() {

preTraverse(this.root) ;

}

private void preTraverse(HaffumanNode root) {

if(root != null) {

if(root != this.root) { //如果不是根节点

if(root == root.parent.left) { //左孩子

root.code = getNewByteArray(root.parent.code,(byte) 0);

} else {

root.code = getNewByteArray(root.parent.code,(byte)1);

}

}

//System.out.println(root) ;

preTraverse(root.left) ;

preTraverse(root.right) ;

}

}

private byte[] getNewByteArray(byte[] code,byte value){

byte[] bytes;

if(code.length > 0){

bytes = Arrays.copyOf(code, code.length+1);

}else{

bytes = new byte[1];

}

bytes[bytes.length - 1] = value;

return bytes;

}

private boolean isLeafNode(HaffumanNode node) {

return node.left == null && node.right == null ;

}

private HaffumanNode createHuffmanTree(String seq){

Queue queue = new PriorityQueue<>();

char[] chars = seq.toCharArray();

Map weightMap = new HashMap<>(8);

for (char aChar : chars) {

if(!weightMap.containsKey(aChar)){

weightMap.put(aChar,0);

}

Integer count = weightMap.get(aChar);

weightMap.put(aChar,count+1);

}

Set keys = weightMap.keySet() ;

for(Character key : keys) {

HaffumanNode newNode = new HaffumanNode() ;

newNode.value = key ;

newNode.weight = weightMap.get(key) ;

//入堆 -- 覆写CompareTo

queue.add(newNode) ;

}

while(queue.size() > 1) {

HaffumanNode n1 = queue.poll() ;

HaffumanNode n2 = queue.poll() ;

HaffumanNode sumNode = new HaffumanNode() ;

sumNode.weight = n1.weight + n2.weight;

sumNode.left = n1;

sumNode.right = n2;

n1.parent = sumNode ;

n2.parent = sumNode ;

queue.add(sumNode) ;

}

return queue.poll();

}

}