编码、压缩算法

csuzhucong

已于 2024-11-15 11:40:34 修改

阅读量2.7k

点赞数

文章标签： c++

于 2022-03-14 01:40:05 首次发布

本文链接：https://blog.csdn.net/nameofcsdn/article/details/123469934

版权

1，游程编码（Run-Length Encoding）

2，BWT转换算法（Burrows-Wheeler Transform）

一，格雷码

1，力扣 89. 格雷编码

n 位格雷码序列是一个由 2n 个整数组成的序列，其中：
每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
第一个整数是 0
一个整数在序列中出现不超过一次
每对相邻整数的二进制表示恰好一位不同，且
第一个和最后一个整数的二进制表示恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列。

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同
示例 2：

输入：n = 1
输出：[0,1]

提示：

1 <= n <= 16

思路：

利用分治算法，由n位格雷码可以直接得到n+1位格雷码。

代码：

//翻转vector
template<typename T>
vector<T> frev(const vector<T>& v)
{
	vector<T> ans;
	ans.resize(v.size());
	for (int i = 0; i < v.size(); i++)ans[i] = v[v.size() - 1 - i];
	return ans;
}
//vector加一个数
template<typename T1, typename T2>
void fjia(vector<T1>& v, T2 n)
{
	for (int i = v.size() - 1; i >= 0; i--)v[i] += n;
}

class Solution {
public:
	vector<int> grayCode(int n) {
		if (n <= 0) {
			return vector<int>(1);
		}
		vector<int> v = grayCode(n - 1);
		vector<int> v2 = frev(v);
		fjia(v2, 1 << n - 1);
		return FvecJoin(v, v2);
	}
};

2，格雷码简介

上面的题目已经把格雷码的要求说的很清楚了，输出解释里面也提到了格雷码不是唯一的。

我上面代码得到的是最典型的格雷码（和上面图片内相同），一般格雷码默认指的就是这种。

对于典型格雷码，可以直接算出每个数的格雷码：

对于n位二进制数a1 a2 ... an，表示成n位格雷码g1 g2 ... gn，

则 $g_i = a_i+a_{i-1},a_0=0$ ，这里的＋表示异或

例如11的四位二进制是1011，则格雷码是1110，即14

用数学归纳法很容易证明这个规律是对的。

（1）二进制转格雷码

void gray(int n, int k)
{
	vector<int>v;
	for (int i = 0; i < k; i++) {
		v.push_back(n % 2);
		n /= 2;
	}
	v.push_back(0);
	for (int i = k; i; i--)cout << (v[i] ^ v[i - 1]);
}

int main()
{
	int n, k;
	cin >> n >> k;
	gray(n, k);
	return 0;
}

输入：9 4

输出：1101 即9的四位格雷码

（2）格雷码转二进制

void grayToInt(int n, int k)
{
	vector<int>v;
	for (int i = 0; i < k; i++) {
		v.push_back(n % 2);
		n /= 2;
	}
	int tmp;
	cout << (tmp = v[k - 1]);
	for (int i = k - 2; i >= 0; i--)cout << (tmp = (v[i] ^ tmp));
}

int main()
{
	int n, k;
	cin >> n >> k;
	grayToInt(n, k);
	return 0;
}

输入：14 4

输出：1011 即四位格雷码14表示的是11

3，格雷码和九连环

九连环按照每个环在上面就是1在下面就是0编号，可以得到一个九位二进制数。

每次只能修改一位（一个环），最终的目标是变成000000000

神奇的是，九连环的最快解法（即没有无效操作，不考虑最后2个环一起操作）就是在从2^9-1到0的一个遍历。

grayToInt(511,9)的结果是101010101，即341，所以九连环需要341步。

也可以根据gray函数直接把九连环的步骤打出来：

void gray(int n, int k)
{
	vector<int>v;
	for (int i = 0; i < k; i++) {
		v.push_back(n % 2);
		n /= 2;
	}
	v.push_back(0);
	for (int i = k; i; i--)cout << (v[i] ^ v[i - 1]);
	cout << "  ";
}

int main()
{
	for (int n = 341; n >= 0; n--) {
		gray(n, 9);
		if (n % 5 == 0)cout << endl;
	}
	return 0;
}

输出：

111111111 111111110
111111010 111111011 111111001 111111000 111101000
111101001 111101011 111101010 111101110 111101111
111101101 111101100 111100100 111100101 111100111
111100110 111100010 111100011 111100001 111100000
110100000 110100001 110100011 110100010 110100110
110100111 110100101 110100100 110101100 110101101
110101111 110101110 110101010 110101011 110101001
110101000 110111000 110111001 110111011 110111010
110111110 110111111 110111101 110111100 110110100
110110101 110110111 110110110 110110010 110110011
110110001 110110000 110010000 110010001 110010011
110010010 110010110 110010111 110010101 110010100
110011100 110011101 110011111 110011110 110011010
110011011 110011001 110011000 110001000 110001001
110001011 110001010 110001110 110001111 110001101
110001100 110000100 110000101 110000111 110000110
110000010 110000011 110000001 110000000 010000000
010000001 010000011 010000010 010000110 010000111
010000101 010000100 010001100 010001101 010001111
010001110 010001010 010001011 010001001 010001000
010011000 010011001 010011011 010011010 010011110
010011111 010011101 010011100 010010100 010010101
010010111 010010110 010010010 010010011 010010001
010010000 010110000 010110001 010110011 010110010
010110110 010110111 010110101 010110100 010111100
010111101 010111111 010111110 010111010 010111011
010111001 010111000 010101000 010101001 010101011
010101010 010101110 010101111 010101101 010101100
010100100 010100101 010100111 010100110 010100010
010100011 010100001 010100000 011100000 011100001
011100011 011100010 011100110 011100111 011100101
011100100 011101100 011101101 011101111 011101110
011101010 011101011 011101001 011101000 011111000
011111001 011111011 011111010 011111110 011111111
011111101 011111100 011110100 011110101 011110111
011110110 011110010 011110011 011110001 011110000
011010000 011010001 011010011 011010010 011010110
011010111 011010101 011010100 011011100 011011101
011011111 011011110 011011010 011011011 011011001
011011000 011001000 011001001 011001011 011001010
011001110 011001111 011001101 011001100 011000100
011000101 011000111 011000110 011000010 011000011
011000001 011000000 001000000 001000001 001000011
001000010 001000110 001000111 001000101 001000100
001001100 001001101 001001111 001001110 001001010
001001011 001001001 001001000 001011000 001011001
001011011 001011010 001011110 001011111 001011101
001011100 001010100 001010101 001010111 001010110
001010010 001010011 001010001 001010000 001110000
001110001 001110011 001110010 001110110 001110111
001110101 001110100 001111100 001111101 001111111
001111110 001111010 001111011 001111001 001111000
001101000 001101001 001101011 001101010 001101110
001101111 001101101 001101100 001100100 001100101
001100111 001100110 001100010 001100011 001100001
001100000 000100000 000100001 000100011 000100010
000100110 000100111 000100101 000100100 000101100
000101101 000101111 000101110 000101010 000101011
000101001 000101000 000111000 000111001 000111011
000111010 000111110 000111111 000111101 000111100
000110100 000110101 000110111 000110110 000110010
000110011 000110001 000110000 000010000 000010001
000010011 000010010 000010110 000010111 000010101
000010100 000011100 000011101 000011111 000011110
000011010 000011011 000011001 000011000 000001000
000001001 000001011 000001010 000001110 000001111
000001101 000001100 000000100 000000101 000000111
000000110 000000010 000000011 000000001 000000000

二，字符串编码

1，字符编码、字符串编码

ASCII编码：用来表示英文，它使用1个字节表示，其中第一位规定为0，其他7位存储数据，一共可以表示128个字符。

拓展ASCII编码：用于表示更多的欧洲文字，用8个位存储数据，一共可以表示256个字符

GBK/GB2312/GB18030：表示汉字。GBK/GB2312表示简体中文，GB18030表示繁体中文。

Unicode编码：包含世界上所有的字符，是一个字符集。

UTF-8：是Unicode字符的实现方式之一，它使用1-4个字节表示一个字符，根据不同的字符而变化字节长度。

2，映射关系

本章节以ASCII编码字符+UTF-8编码字符串为例，有些地方不是这套编码，那么结论会有所差异。

（1）所有语言通用关系

第1列：字节就是u8，u8序列需要解码时，会自动分割成若干段，每一段1-4个u8，所谓的自动分割就是基于字符串编码方案。

第2列：字符包括单字节字符，也包括2-4字节的字符，字符串就是字符组成的串。

第3列：比较灵活，我们先把左边6个概念梳理清楚。

第1行：u8要么是单字节字符，要么只是某个整数但不是字符，即单字节字符到u8的映射是单射非满射。

第2行：u8段要么是字符，要么只是若干u8整数但不是字符，即字符到u8段的映射是单射非满射。

第3行：u8序列可以分割成若干u8段，如果分割失败或者某个u8段不是字符，那这个u8序列就不是字符串，反之就是字符串，即字符串到u8序列的映射是单射非满射。

（2）C++方案

C++中，char和u8是双射的，char占1个字节，string和u8序列是双射的。

非单字节字符的char、非字符串的string打印出来都是空白。

char支持加一个任意整数，2个char相减，string支持在随机访问。

（3）Rust方案

rust中，char和字符是双射的，char占4个字节，string和字符串是双射的。

由于rust的字符并不是ASCII编码而是Unicode编码，所以rust中的u8和单字节字符是双射的。

char和string都是有实际含义的字符和字符串，所以不存在打印问题。

char不支持加一个任意整数，也不支持2个char相减，string不支持随机访问。

三，无损压缩算法

无损压缩可以分为三大类：直接编码、转换、上下文编码。

四，直接编码

1，熵编码（哈夫曼编码）

哈夫曼编码就是把各个字符转换成不同长度的01串，按照固定的替换规则全文替换即可。

当然，哈夫曼编码的依据，可以是硬编码的，也可以是根据文本内容统计计算出来的。

2，算术编码、区间编码

这2个编码方式在我理解差不多，根据不同字符的概率不一样，把一个字符串编码成一个实数。

五，转换编码

1，游程编码（Run-Length Encoding）

输入: AAABBCCCCDEEEEEEAAAAAAAAA
输出: 3A2B4C1D6E9A

这种转换，是字符到字符的转换，转换之后，仍然可以用哈夫曼编码等从字符转换成二进制。

2，BWT转换算法（Burrows-Wheeler Transform）

BWT算法，就是压缩之前把字符串A转换成字符串B，压缩B即可，解压的时候得到B之后，再把B转换成A。

例如字符串“banana#”转换为了“annb#aa，其中#是算法添加的特殊标识符。

如果字符串比较长，转换后的字符串可以出现很长的一段相同字符，所以BWT转换之后再用别的压缩算法，比如LZW，可以提高LZW的压缩率。

4，滑动窗口+字典转换（LZ系列算法）

（1）LZ77

1977年诞生LZ77算法，也叫LZSS算法

（2）LZ78

1978年诞生LZ78算法（3）

六，上下文编码

上下文编码，如PPMD、PAQ 利用的是上下文预测，消除二进制串的重复，达到压缩的目的。

七，复合压缩算法（转换+编码）

1，LZW

LZ78 + 哈夫曼编码

初始化字典为255个字符，随着压缩的过程，字典一步步扩充，最终把全文本转换成字典的id序列，再用变长编码的方法，把id序列编码成二进制。

2，deflate

LZ77 + 哈夫曼编码

3，LZMA

LZ77 + 区间编码

八，我对压缩算法的理解

1，压缩算法能接力吗？

不能，无论是先用A压缩再用A压缩，还是先用A压缩再用B压缩，都没有效果。

2，有没有一种无损压缩算法，保证压缩之后一定比原数据要小？

不存在，无损压缩是一种从二进制流到二进制流的一一映射，任何一种无损压缩算法，都能找到某个二进制流，使得用这个算法压缩之后长度不变或变长。

也就是说，当数据有重复信息的时候，通过去除重复信息可以压缩数据量，但是如果数据没有任何重复信息，压缩率可能就是接近1或者超过1

3，压缩算法为什么不能接力？

简单理解，数据可以分为文本信息、二进制流、图片等。

这里的二进制流指的是随机二进制流，比如一个常见的exe，它的二进制流就几乎是随机的，压缩算法很难压缩。

理论上来讲，所有数据都是二进制流，都是0和1组成的序列，但是数据的属性决定了我们如何理解数据。

比如一个通用英文文本，虽然也是二进制串，但是26个英文字母的ASCII码对应的8个比特，肯定是大量出现的。

所有的算法，经过压缩之后，都会变成二进制流，剩下的重复信息就很少了。

所有的算法，都是几乎无法压缩二进制流的。

4，BWT转换算法，只涉及把字符重排，是否可以用在所有压缩算法上？比如先用BWT转换再用PPMD？

不行。通用英文文本，先用BWT转换再用PPMD，压缩率比单纯的PPMD还小。

BWT转换可以提高某些算法的压缩率，比如LZW，但是并不能提高所有算法的压缩率。

因为，同样的二进制流，不同的压缩算法有不同的理解角度，并不是每个角度看来，字符串重排都变得更加规整。

例如，我的算法依据是，当一个单词是字母e开头的时候，下一个字母大概率是n，（随便举的例子）

也就是说空格符合字母e连续出现的话，下一个字母大概率是n，那么这就是我消除重复的一个依据，如果重排就没有这个依据了。

这里说的对数据的理解角度，还有算法依据，其实都是数据本身的特点。

5，数据有哪些特点可以用来压缩？这些特点是怎么来的？

如果把01串看成数列，那么所有我们能想到的数列规律，都能以某种形式展现在某个01串的，但是并不是所有的都能用来压缩。

反过来，对于一个01串，可以用任意角度去理解它，如果某个角度看来，它具有一种重复性的规律，那么就可以用来压缩。

这么说还是太主观了，或许还是用熵来表述更为精确。

数据的特点，自然是来自产生数据的源，比如文本，来自人类交流的语料库，有语法限制，字母按照一定的规则组合成词，汉字按照一定的规则组合成词，比如图片，来自大自然，由于地球（宇宙）上的原子排列是有规律的，原子都是扎堆出现的，而光学原理是简洁而和谐的，所以拍出来的照片总是以色块的形式展现出来。

再比如，假设我在手算圆周率Pi，需要记录一串实数：

3, 3.1, 3.14, 3.141, 3.1415 ......

显然，这串数据把它当做通用文本压缩，也会有不错的压缩率，应该比一般的通用文本压缩率更高。

但是，如果我确定所有的数据都是Pi的前若干位，而Pi的前10000万都是确定的，那么以此规律为基础，就可以自创一个压缩算法，针对此类数据压缩率很高。

上面的串其实就可以转换成0 1 2 3 4 ......

如果规律变得复杂一点，每个数都是Pi的前若干位向上或者向下取整，比如：

3, 4, 3.1, 3.2, 3.14, 3.15 ......

那么，压缩算法肯定要复杂一点。

如果再允许一点误差，比如3.16也是有可能出现的，但是统计规律显示3.16出现的概率远小于3.14和3.15，那么我们仍然可以定制压缩算法，使得压缩率远高于通用压缩算法。

总之，数据的特点，无论是数学公式的强规律，还是基于统计的弱规律，都可以用来压缩。

6，什么是信息？什么是熵？

信息是由数据来承载的。

个人理解：数据的信息，是一个主观的属性，而信息的信息熵，是一个客观的属性。

就像文本，它所传达的信息到底是01串还是字符串，这是一个主观的，甚至我们可以把某个01串先按照计算公式转换成3, 3.1, 3.14, 3.141, 3.1415 ...... ，再按照Pi的数值作为对照表，把序列转换成0 1 2 3 4 ......，然后说这才是这个01串表达的信息。

也就是说，信息是由数据+理解数据的角度决定的。

而在每一个角度之下，这个数据的信息熵都是一个确定的量，同一个数据在不同的角度下信息熵不一样。

再举个例子，如果一个文本全都是数字和空格组成的，那么我们可以说，这个文本熵比较低。

如果我们又知道，这个文本其实是一串正整数的最简表示，那么它的熵更低了，因为我们排除了形如01 02 03这样的文本，因为01不是任何正整数的最简表示，当然，形如额外约定用第一个数字表示正负的规则除外，这又是一种新的理解这个文本的角度。

所以，这个文本可以是这样的：1 3 124 56 2 38 ......

如果我们又知道，每个整数都是素数，比如2 13 5 7 11 5 97 ...... 这样的串，那么熵就更低了。

所以，熵表示的是不确定性，规律越严格，熵越低。

热力学里面的熵，和信息学里面的熵，本质上是一样的。

PS：2 13 5 7 11 5 97 ...... 这样的素数串，如果看做通用文本，先用BWT转换，再用任何压缩算法压缩都不好用了。

这也是一个例子，可以用来帮助理解为什么BWT转换针对文本并不具有普适性。