“
「 Rust 与 LLM」 是本合集的主题系列之一，本文为番外第二篇。阅读本系列文章不需要有数学基础。
本合集将优先完成该主题系列文章，所以其他主题的文章优先级将降低。
「 Rust 与 LLM」主题系列将专注于自然语言处理、 Transfomer 架构和大模型相关内容，依托 Rust 开源生态和 HuggingFace 的相关 Rust 库，探秘从模型训练到模型部署、模型量化与 WebAssembly 轻量化部署的技术原理。
经过对 BPE 分词模型和 Transformer 架构的学习，现在越来越感觉 Transformer 架构其实也可以理解为一种数据压缩和解压的过程。
正好在微信读书里也看到一本**《数据压缩入门》**的书，该书作者是两名来自 Google 的工程师。所以就快速地学习一下数据压缩相关的概念和算法。本文是这本书的一个学习笔记。
“
说明：原书对算法相关的计算过程有很多图片和示例展示，本文就不多余展示细节了。本文目的只是过一遍概念，对细节感兴趣的朋友读原书就行。微信读书里可以读本书。本文是对 《LLM 入门之旅》的下一篇正文 「BPE 分词模型 Rust 实现」的基础铺垫。
数据洪流随着信息技术的发展而逐步增长，且增长的速度比网络带宽增加、压缩算法的性能提升以及存储容量的增长速度更快。所以探索更好更快的数据压缩算法一直是刚需。
《数据压缩入门》这本书就是作为一个起点，汇总了数据压缩算法及其发展变化，帮助更多的人去探索新的数据压缩算法。
数据压缩算法的基础是数学，这个毋庸置疑。但是现代程序员不怎么需要了解数学了，因为他们只需要把数据扔给一个压缩库就能得到压缩后的数据。但是如果向前看几十年，数据会变得越来越多，整个人类社会会有更多数据。一个解决办法就是创建更好更快的新的压缩算法。
“
题外话：想起美剧《硅谷》第一季中主角创业团队就是因为发明了压缩算法才得以捞到第一桶金。另外，现在的大语言模型，实际上也是对人类知识数据的一种压缩。
所以这本书的最初目标群体是那些愿意去了解压缩原理、有一定数据基础、想要探索新的压缩算法的人。然而，对压缩算法感兴趣的读者，也非常适合阅读这本书。我就是后者，阅读这本书的时候，我跳过了数学细节。
我看这本书的目的，只是为了更好地去理解 LLM 中的相关算法。这对我来说，属于一种无用之用。如果你对此没兴趣，那可以忽略本文。
另外，还需知道一个客观事实：当今计算世界，已经完全建立在一个数据压缩算法之上了。
宏观层面上，数据压缩算法当前被分为五类：
变长编码（variable-length codes, VLC）
统计压缩（statistical compression）
字典编码（dictionary encodings）
上下文模型（context modeling）
多上下文模型（multicontext modeling）
这五类算法还有很多变种，但基本可以分为这五类。每类算法变种在输入数据、算法性能、内存要求和输出大小方面存在细微差别。
数据压缩最早其实是信息论之父香农研究工作的一项实际应用案例。简言之，数据压缩就是「在能保证信息恢复的前提下，我们可以把信息变得多么紧凑」。计算机科学家所写的每个数据压缩算法，都是对香农提出的信息熵的挑战，使数据的压缩程度超过香农发明的公式计算出来的信息熵。
“
信息熵（information entropy）是香农用来度量消息所携带内容的方法。信息熵的核心概念基于以下思想：信息的价值来自于其能够消除不确定性的能力。一个完全随机的系统有高熵，因为你很难预测它的下一个状态；而一个有序的、可预测的系统有低熵。
在数据压缩领域，信息熵定义了在没有丢失信息的情况下所能达到的最大压缩率。如果一个数据压缩算法可以将数据压缩到接近其信息熵的大小，那么这个算法是非常有效的。然而，超过信息熵的压缩通常意味着信息的丢失。
信息熵也解释了为什么一些数据不能被有效压缩。例如，一个完全随机的数据集其信息熵非常高，因此几乎不可能有效压缩，因为它包含的信息量太大。相反，如果数据集包含大量重复或可预测的模式，则其熵较低，可以被更有效地压缩。
数据压缩通常离不开两个基本思路：
减少数据中不同符号的数量（让「字母表」尽可能小）
用更少的位数对更常见的符号进行编码（最常见的「字母」所用的位数最少）
60 多年来的所有数据压缩算法都可以归结到这两个基本思路上。但是实际进行数据压缩时，还需要考虑下面一些因素：
不同数据的处理方法不同，比如 文字和浮点数就不同
有些数据必须经过转换才能更容易压缩
数据可能是偏态的。例如，夏天的温度整体偏高，即，高气温出现频率比 0 度频率更高
至少作为程序员的我们，需要了解如何找出最好的方法来压缩用户的数据。
数据压缩本质是尽可能地减少表示特定数据集时所需的二进制位数量。
在信息论的背景下，一个数值所包含的信息内容等价于：为了在一个集合中唯一地确定这个数值，需要做出二选一（是 or 否）决定的次数。
“
我来增补一个示例，我感觉比书中的好理解。
假设现在有一个 100 平米的房间，房间的地板由 100 块一平米大小的地板砖组成。这100块地板砖的颜色只有两种，黑或白。一共有50块黑色，50块白色。
现在，为这 100 块地板砖进行标注，黑色为 1， 白色为 0 。
那么，我们可以通过
0101010101000101010101010......这样的编号来表示 100 块地板砖组成的图案，比如“小鸡吃米图”。这些数字编码隐藏了的图案信息，比你直接呈现那 100 平米的图案要省很大空间。这就是数据压缩。
表示一个数或字符所需最小的二进制位数，可以称为该数的熵。对于整个数据集来说，表示整个数据集最小二进制位数就是该数据集的熵。
数据压缩领域的最前沿都是如何改变熵的，事实上，整个数据压缩科学界人士都是认为熵是互联网上一大“谎言”。理论上，通过真实数据的两个性质，我们完全可能把数据压缩得比熵定义的更小。
这是因为，香农定义的熵只考虑了符号出现的概率，没有考虑符号的排序。对真实数据集而言，排序是其基本的一项属性，符号之间的关系也是如此。
案例：
增量编码：将有序集合 [0,1,2,3,4,5] 按前一位与后一位的差值进行编码 [0,1,1,1,1,1]。
符号分组：字符串 TOBEORNOTTOBEORTOBEORNOT包含了不同字符 [O,T,B,E,R,N]的集合，如果把单词当成符号则是[TO,BE,OR,NOT]
排列：从熵的角度看，一个排列是不可能被压缩的，因为排列一般是无确定顺序的。但实际上有一种索引方法是可以对排列进行压缩的，只不过压缩空间有限。
从这些案例来看，数据压缩的艺术，就是如何突破熵的艺术。
“
题外话：感觉数据压缩和信息加密也有共通之处。
摩尔斯码为英语字母表的每个字符都分配了或长或短的脉冲。一个字母用的越频繁，其编码越短越简单。因此，字母 E 就是最短的脉冲，因为字母 E 用的最多，它用一个点表示（.）。而字母 X/Y/Z 则使用更长的脉冲，比如用-..- 表示 X。
摩尔斯码就是典型的一种变长编码（VLC）压缩。香农在摩尔斯码的启发下，创造了数据压缩的第一代技术。
VLC 原则：将最短的编码分配给最常出现的字符。
数据集中一个字符出现的概率越大，整个数据集的熵就越小，整个数据集就越容易压缩。一般进行 VLC 的步骤如下：
遍历数据集中所有符号并计算每个符号的出现概率
根据概率为每个字符分配码位（二进制位），一个符号的出现概率越大，分配的码位越短
再次遍历数据集，对每个字符编码，将对应的码位输出到压缩后的数据流中
拿字符串 TOBEORNOTTOBEORTOBEORNOT来说，出现次数最多的是字符 O，出现 8 次，次数最少的是字符 N，出现 2 次。
符号
频数
码位
O
8
11
T
5
00
B
3
011
E
3
101
R
3
0100
N
2
0101
对分组字符表[TO,BE,OR,NOT]编码后是 001101110111010001011100，共 24 个二进制位。原字符串每个字符如果以3位二进制编码来对应，则需要 72 个二进制位（24个字符 * 3）。这就实现了数据压缩。
解码过程就是编码的逆向。解码的时候拿码位去匹配字符表即可。如下图：
VLC 编码能正常工作还需要满足一个被称为「前缀性质」的条件。它的意思是：在某个码位被分配给一个符号后，其他码位就不能把它当作该码字的前缀。
如上图。不满足前缀性质，VLC 解码将无法继续。
需要知道的是，VLC 编码只能用于表示压缩数据流，没有其他用处。因为它们有不按字节/字/整型对齐、解码速度很慢等缺点。
统计编码无需将特定整数转换为特定的码位，而是通过数据集中符号的出现概率来确定新的、唯一的变长码位。给定任何输入数据，都能为其构造一套自定义的码位集，而无须匹配现有的 VLC 方法。
统计编码也被称为「熵编码」。
给定一组符号及其出现概率，该方法能生成一组符号平均长度最短的 VLC 。它的工作原理是将数据排序后建立决策树，然后从“树干”一直向下到“树叶”，并记录下所做的「是或否」选择。
“
据说哈夫曼在发明哈夫曼编码之前，苦心研究了好几个月，就在他失望至极要将研究笔记扔垃圾桶的时候，突然顿悟了。
哈夫曼编码应用范围比较窄，因为该编码方法只有在各个符号出现概率等于 2 的负整数次幂（1/2、1/4、1/8 这样）时才能生成理想的 VLC 。
所以一种新的统计编码方式算术编码被发明了出来。
“
早年间，由于 IBM 激进的专利保护，算术编码几乎被”雪藏“。因为算术编码非常好用，专利保护又没法突破，只能发明了另外一种称为「区间编码」的方法。后来专利到期，算术编码才重见天日。现代主流文件、音频和视频的压缩格式都会用到算术编码。
算术编码的工作原理是将字符串转换为一个数。与字符串相比，表示数的二进制位更少。
比如字符串 "TOBEORNOT"可以用 236712来表示。但是这个数并非随机设置，而是经过一系列算法来计算出那个数。
这套算法实际是对二分算法的改进。算术编码首先会创建一个概率空间[0,1)，然后通过数据流中出现的符号概率对这一区间进行细分。
比如计算 "RGB" 对应字符的数字，通过递归拿到最终字符对应的概率空间。
比如 B 最终取值空间是 [0.825, 0.85)，这个范围内任意数字都可以表示这个字符，但是为了压缩，需要取二进制占位最少的那个数字，这里就是 0.83（有一个数学公式可以计算数字占用二进制位大小）。进一步转换为整数 83 来表示这个字符。
解码过程就是逆向操作了，将 83 转为 0.83，再计算该概率落在 "RGB" 对应的哪个区间，就拿到了对应字符。
我这里只是简单描述这个编码解码过程，实际计算细节可以去看书了解。
但是算术编码的性能不如哈夫曼编码。
2007 年， Jarek Duda 引入了一种新的与数据压缩相关的信息论概念：非对称数字系统（Asymmetric numeral systems, ANS）。这种方法压缩率与算术编码相当，性能与哈夫曼编码相当。
ANS 编码步骤概要：
根据符号出现的频率对数值区间进行细分
创建一张表，将子区间和离散整数值相关联
每个符号都是通过读取和响应表中数值来处理
向输出流中写入可变的二进制位位数
这个算法神奇之处就在第二步创建的一张备查表。这张表先根据符号出现的概率大小排列，每个字符作为表的一列，从左到右概率依次递减。
同样，该编码方法细节可以去看书，这里不表。
实际上，在 2013 年又出现了被称为有限状态熵（FSE）的更加注重性能的版本，以至于 2015 年又推出名为 LZFSE 的 GZIP 变种，作为 iOS 版本的新一代核心 API。
所以未来，统计编码领域的算法霸主是 ANS 和 FSE 。
前面讲的统计编码算法，在编码之前必须要计算各个符号出现的概率，而且在计算之后还需要继续处理这些数值。如果数据集很大的话，这样做性能很慢。因为需要遍历整个数据集。
一般来说有三个步骤：
遍历数据流并技术各个符号出现的概率
根据概率为符号生成 VLC
再次遍历数据流并输出对应的码位
这里需要遍历两次数据流。
在自适应算法中，这三个步骤将简化为遍历一次数据流。其本质是可以动态更新 VLC 表。这是一套方法论，可以应用于上面的统计编码算法中，比如自适应算术编码，自适应哈夫曼编码等。
所以现代数据压缩算法，在数据量小的时候，选择静态统计编码算法，而数据量大的时候，则选择动态统计编码算法，即，自适应统计编码算法。
相比于 VLC “家族”，字典转换算法完全改变了人们对数据压缩的认知。它的应用更加广泛。
统计编码算法那种计算字符概率的方式，其实忽略了上下文和词语的组合。比如短语。对于字符串TO BE OR NOT TO BE，其实用不着拆开每个字符都去编码。
如果考虑的对象不再是单个字符，而是一组相邻的符号（比如，单词短语），我们就走出了统计编码的世界，进入了字典转换的世界。
字典转换的方式，是先将给定数据集，构建为单词字典，再在单词的基础上进行概率统计，这样可以直接将统计算法应用于单词上面。
为了找到“理想的单词”，这样就涉及了 「分词器」技术。
该算法的命名是来自于共同发明它的两位作者 Abraham Lempel 和 Jacob Ziv 。该算法自 1977 年被发明以来，后来的 30 多年都没有新的算法取代它。
LZ 算法尝试通过在读取字符串中寻找当前单词的匹配来分词。即，向前查找最长前向匹配单词。LZ 算法将数据流分成如下两部分：
数据流左半部分称为搜索缓冲区，包含的是已经读过并处理过的符号，包含 32kb 长的滑动窗口
数据流的右半部分被称为先行缓冲区，包含将要编码的符号
一般来说，搜索缓冲区包含几万个字节，而先行缓冲区包含几十个字节。
当最终匹配被找到以后，就会以偏移量和长度值的形式被记录下来。经过 LZ 算法编码后的数据流要比原数据流更小。
LZ 算法更吸引人的地方是它可以和统计编码算法共同使用。可以将记号中的偏移量和长度值以及字面值分开，再按类型进行合并，组成单独的偏移量集、长度值集等，再对这些数据集进行统计压缩。
这 30 多年来，也出现了很多 LZ 算法变体，本文不表。
字典转换算法，只有在分词找到最适合最理想的符号，压缩编码的效率才最高。除了字典转换算法之外，还有类似的上下文数据转换编码。
RLE 算法主要针对连续出现的相同符号聚类的现象，它会用包含符号值及其重复出现次数的元组，来替换某个符号一段连续的“行程（run）”。
比如 AAAABBBBBBBBCCCCCCCC，可以编码为 [A,4][B,8][C,8] 。
增量编码之前提过，即将一组数据转换为相邻数据之间相对差值（即增量）的过程。这种算法不依赖统计信息。但是它依赖相邻性，所以它最适合处理时间序列数据，或者音频图像数据等多媒体数据（存在时间上的关联）。
增量编码细分还有 异或增量编码 和 参照系增量编码等，细节此处不表。
上下文数据转换背后的思想是，数据的排列次序中包含着一些有助于编码未来符号的信息。前移编码（Move to front coding, MTF） 利用的也是这样的信息。MTF 考虑更多是在较短的窗口内某个特定符号出现的次数。
MTF 的预期是：如果一个符号在输入流出现了，那么它很有可能出现多次，或者在短时间内成为常见的符号。它在局部是自适应的，实际上，MTF 是最简单的动态统计转换形式之一。
伯罗斯-惠勒变换 （Burrow-Wheeler transform, BWT）编码算法和前面介绍过的都不太相同。BWT 是通过打乱数据流次序来让重复的子串聚集在一起。这种操作本身不是为了压缩数据，而是为后期压缩数据做更好的准备。属于预处理手段。
BWT 打乱数据流次序，然后让相同的符号簇彼此靠近，通常是按字典序进行排列。这个过程也较为复杂，并且它也是可以逆向解码的。细节可参阅原书。
BWT 自发明以来在数据压缩界一直没有什么用武之地，直到人类开始对 DNA基因 进行测序。BWT 的排序算法对 DNA 是一种理想变换，可以使其更容易压缩、查询和检索。
这类编码器可以看作是对统计编码算法的增强版。神奇的是，这种算法在 18 世纪就被提出了（WIKI 帕斯卡）。
马尔可夫链（Markov chain）是一种离散的随机过程，其未来状态只取决于现在，而与过去的历史无关。
“
题外话：这不就是我们的人生吗？活在当下，现在即未来。
假定有一个学生已经完成了中学三年级的课程。而我们想知道他在中学四年级数学课得 A 的概率。一般来说，这取决于他过去三年的数学成绩。然而，如果只有当前（三年级）的成绩会对结果产生影响，而前两年的成绩都可以忽略不计，那么就可以认为这是一个马尔可夫过程。
“
1913 年，马尔可夫通过将数学与诗歌（他钻研普希金的诗歌，研究元音和辅音出现的规律）结合起来创立了概率论的一个新分支。
马尔可夫提出事件选择概率可以帮助我们解决关联概率问题。比如，“如果今天多云，那么明后两天下雨的概率是多少？”。
现在马尔可夫链在预测天气，以及互联网上都有应用，比如 Google 的 pagerank 算法、亚马逊商品推荐、游戏推广等。
在数据压缩领域，马尔可夫链也可以很好地应用于现有的统计编码算法中。因为前面讲的统计编码算法属于一阶马尔可夫链。
通过为前面出现的符号增加一张符号码位对应表，就可以创建二阶马尔可夫链，简称二阶表。
但实际没有人用马尔可夫链压缩数据，因为存在内存消耗与计算性能问题。因此，后来有人提出 部分匹配预测（PPM） 算法，算是马尔可夫链的具体高性能实现。
PPM 算法使用单词查找树，来实现上下文的快速定位。在此基础上就可以实现统计编码来压缩数据。随后，又发展出上下文混合算法（比如 PAQ），给未来数据压缩的发展指明了方向。
总的来说，如果所需内存与运行的时间不加限制，同时还有足够的数据建模知识，那么最优压缩就是一个可解决问题。
“
题外话：我想到大模型那个尺度定律了。只要在更多的数据上训练更大的模型，那么准确度就会不断的上升，无需去改进其内部底层算法。
为了 《LLM 入门之旅》后面的 BPE 算法探索，这里先从整体上了解一下 BPE 的概念。
遗憾的是，《数据压缩入门》这本书中并未直接介绍 BPE 压缩算法。但对于我们理解 BPE 算法打下了很好的基础。因为 BPE 算法也是一种数据压缩算法。
BPE（byte pair encoder）字节对编码，也可以叫做双字母组合编码，主要目的是为了数据压缩。该算法为字符串里频率最常见的一对字符，被一个没有在这个字符中出现的字符代替的层层迭代过程。该算法首先是被 Philip Gage 于 1994年2月在文章“A New Algorithm for Data Compression”中提出。
原理简单示例：
比如想编码 ABABABBAABCCABAABDDD，你会发现 AB出现的词数最高，那么这里用从未出现过的字符 Z替代AB，即 ZZZBAZCCZAZDDD。然后再迭代这个过程，使用 X 替代出现频率最高的AZ，得到 ZZZBXCCZXDDD。到此为止，两个邻近字符对出现的频率没有超过 1 的了，编码完成。解码按这个过程逆向就行。
看得出来，BPE 算法有统计编码和字典转换的影子。
后面 《LLM 入门之旅》的文章也会详细介绍这个 BPE 模型算法如何应用于自然语言处理的分词器。
《数据压缩入门》后面还有多媒体压缩、压缩性能、压缩图像数据的一些章节，留待以后再看。当前，我只专注了解数据压缩基本概念和常用算法原理。本文的目的已经达到。感兴趣的朋友可以自行阅读这本书。
感谢阅读。
