哈夫曼编码直观讲解

1. 图示
   观察依据

   一个蓝色圆角矩形，标注为“数据”，出现在屏幕的左侧和右侧。

2. 声音
   观察依据

   讲述者提到“一段数据”和“原始文件”。

Data

正在被压缩或解压缩的输入或输出数据。

文件或文本数据

1. 图示
   观察依据

   一个红色圆圈，标注为“C”，显示在初始数据块与压缩后数据块之间。

2. 声音
   观察依据

   讲述者说：“将其传入一个压缩算法。”

C

压缩算法。

将原始数据映射为压缩数据的函数

1. 图示
   观察依据

   一个红色圆圈，标注为“$C^{-1}$”，显示在压缩后数据块与恢复后数据块之间。

2. 声音
   观察依据

   讲述者说：“将其传入该算法的逆过程。”

$C^{-1}$

逆过程（解压缩）算法。

将压缩数据映射回原始数据的函数

1. 图示
   观察依据

   文本‘100 MB’和‘70 MB’分别显示在对应的数据块下方。

MB

兆字节，一种数字信息大小的单位。

正实数

1. 图示
   观察依据

   文本‘112 bits’、‘42 bits’和‘55 bits’显示在各计算结果下方。

bits

二进制位，计算机中信息的基本单位。

非负整数

1. 图示
   观察依据

   屏幕顶部显示文本‘BANANA BANDANA’。

2. 声音
   观察依据

   讲解员说道：‘我们以一个文本例子开始——banana bandana，全部大写。’

BANANA BANDANA

用作压缩示例的特定字符字符串。

字符组成的字符串

1. 声音
   观察依据

   讲解员指出：‘每个字符在ASCII中使用8位表示。’

ASCII

美国信息交换标准代码，一种字符编码标准。

字符集

1. 图示
   观察依据

   标题文字“BANANA BANDANA”始终显示在画面顶部，用作频次统计与编码的示例字符串。

BANANA BANDANA

用于统计字符频次并进行编码的示例输入字符串。

一个由字母A、B、N、D及一个空格字符（用“-”表示）组成的14字符字符串。

1. 图示
   观察依据

   垂直列表依次显示：A : 6，B : 2，N : 4，D : 1，- : 1。

A : 6, B : 2, N : 4, D : 1, - : 1

该示例字符串的频次表；每个符号均与其出现次数配对。

出现在“BANANA BANDANA”中的字符；其频次均为正整数。

1. 图示
   观察依据

   屏幕先后显示“42 bits”、“55 bits”，随后替换为“97 bits”。

2. 声音
   观察依据

   讲述者指出，总大小变为97比特，远小于原始的112比特。

42 bits, 55 bits, 97 bits, 112 bits

用于比较该示例消息不同编码方式的比特长度量。

非负整数形式的比特数。

1. 图示
   观察依据

   叶节点标注有字符及权重1、1、2、4、6；内部节点则按合并生成，权重分别为2、4、8、14。

2. 声音
   观察依据

   讲述者说明：新节点的频次等于刚刚合并的两个节点的频次之和。

node frequency / weight

附加在霍夫曼树节点上的数值标签，等于该节点下方所有叶节点频率之和。

本例中的正整数。

1. 图示
   观察依据

   二进制标签1和0在树构建完成后标注在树的边上。

2. 声音
   观察依据

   讲解者指出，所有左向边均被赋予1，所有右向边均被赋予0；且对调这两者的赋值方式不会影响最终结果。

edge value 0 or 1

分配给树边的二进制数字；叶节点的编码即为从根节点到该叶节点路径上各边所赋数字组成的序列。

每条边恰好被分配一个二进制数字。

1. 声音
   观察依据

   讲述者将无损压缩定义为在不丢失任何信息的前提下恢复原始文件。

2. 图示
   观察依据

   标题变为“无损压缩”，同时展示$C^{-1}$过程。

无损压缩是一种技术：压缩后的文件可通过压缩算法的逆算法进行处理，从而精确还原原始文件，整个过程中不丢失任何数据。

1. 逆算法$C^{-1}$必须存在且被正确应用。

1. 声音
   观察依据

   讲解员解释分配3位编码给5个唯一字符。

2. 图示
   观察依据

   一张表格将字符 A、B、N、D 和空格（-）分别映射为3位二进制字符串（000、001、010、100、101）。

一种朴素的压缩方法：文本中每个不同字符都被分配一个长度固定的二进制编码；该固定长度由表示全部不同字符所需的最少比特数决定。

1. 每个字符所占的比特数必须足以对源文本中所有不同字符进行唯一编码。

1. 二进制表示容量

1. 声音
   观察依据

   讲述者解释1位、2位和3位各自能够表示多少个值。

2. 图示
   观察依据

   列表显示：1位可表示0、1；2位可表示00、01、10、11；3位可表示从000到111。

由$n$位组成的序列所能表示的不同数值的个数为$2^n$。例如，1位可表示2个数值，2位可表示4个数值，3位可表示8个数值。

1. $n$是位数。

1. 声音
   观察依据

   讲解员指出，解码时需要存储编码表，这会额外占用若干比特。

2. 图示
   观察依据

   计算表明，编码表共需$5 * (8 + 3) = 55$比特。

在定长编码中，原始字符与其新编码之间的映射关系必须被存储。这一‘编码表’会增加压缩后文件的总大小。

1. 解码器必须能够访问该编码表，才能还原出原始文本。

1. 定长编码

1. 图示
   观察依据

   显示了一个固定映射：A : 000，B : 001，N : 010，D : 100，- : 101。

2. 图示
   观察依据

   比特总数42比特和55比特被替换为97比特。

3. 声音
   观察依据

   讲解员称，这使得总大小变为97比特，已远小于原始的112比特。

该片段首先回顾了一种等长编码，其中每个不同符号都被分配一个3比特的码字。使用该编码，示例消息从112比特压缩至97比特，从而引出进一步优化的必要性。

1. 每个符号使用相同的码长，此处为3比特。

2. 示例字母表为{A, B, N, D, -}。

1. 声音
   观察依据

   讲解员提示观众记下示例中每个字母的出现频率。

2. 图示
   观察依据

   出现如下列表：A : 6, B : 2, N : 4, D : 1, - : 1。

3. 动画
   观察依据

   五个圆形节点出现，并按其数值频率从小到大排列。

霍夫曼编码始于统计源消息中每个符号的出现频次。所统计出的频次成为初始叶节点的权重，且这些叶节点在合并开始前按权重从小到大排序。

1. 必须已知源消息，才能统计各符号频次。

2. 每个不同符号成为一个初始叶节点。

1. 示例消息的定长3比特编码

1. 声音
   观察依据

   讲解者指出，应选取频率最小的两个节点，并将它们合并为一个新节点，该新节点的频率等于这两个被合并节点的频率之和。

2. 动画
   观察依据

   权重为1和1的节点合并为2；接着2和2合并为4；然后4和4合并为8；最后8和6合并为14。

每一步中，从当前所有可用节点中选出权重最小的两个节点，在它们上方创建一个父节点，并将该父节点的权重设为这两个节点权重之和。重复此过程，直至仅剩一个根节点。

1. 当剩余节点多于一个时，持续重复该操作。

2. 已合并的节点本身不再参与后续选择，除非通过其父节点间接参与。

1. 构建霍夫曼树前，先统计各符号的出现频率

1. 声音
   观察依据

   讲述者指出，所有左分支边均赋值为1，所有右分支边均赋值为0；若反过来赋值，最终结果不受影响。

2. 图示
   观察依据

   完成的树被重新标记：左分支上标1，右分支上标0。

霍夫曼树构建完成后，每条边都被赋予一个二进制数字。本视频采用的约定是：左 = 1，右 = 0；但采用相反约定所得的编码结构同样等价。

1. 该树必须已是完整的。

2. 所有边必须统一且一致地采用同一约定。

1. 霍夫曼编码核心合并规则

1. 声音
   观察依据

   讲解者说明：要得到符号 A 的编码，需从根节点出发，沿树向下遍历至 A；该路径上仅有一个取值0，因此 $A = 0$。对于 B，该路径给出110。

2. 图示
   观察依据

   最终表格列出：A : 6 0，B : 2 110，N : 4 10，D : 1 1110，- : 1 1111。

对每个叶节点符号，记录从根节点向下移动至该叶节点过程中所经过的各条边的标签序列；该序列即为该符号的哈夫曼编码。

1. 使用已完整标注的树。

2. 每个叶节点恰好对应一个信源符号。

1. 为树的各条边分配二进制数字

1. 声音
   观察依据

   讲解者指出：高频字母被分配较短的编码，低频字母被分配较长的编码，并称这是哈夫曼编码背后的关键思想。

2. 图示
   观察依据

   最终表格在视觉上将较大频数与较短码字配对：A（6）→ 0，N（4）→ 10，B（2）→ 110，D（1）→ 1110，-（1）→ 1111。

此处演示的核心压缩原理是：更常见的符号被置于离根更近的位置，因而用更少的比特编码；而较罕见的符号位于更深的位置，因而需要更多比特。

1. 适用于视频片段中展示的哈夫曼构造过程。

2. 本片段中的陈述属于定性描述；未给出最优性证明。

1. 从每个符号对应的根节点到叶节点的路径读取其编码

1. 声音
   观察依据

   讲解指出：更常出现的字符被分配较短的编码，而较少出现的字符则被分配较长的编码。

2. 图示
   观察依据

   所显示的表格符合该规则：A 的频次为6、编码为0，N 的频次为4、编码为10，B 的频次为2、编码为110，而 D 和空格的频次均为1、编码分别为1110和1111。

本片段介绍了霍夫曼编码的核心设计思想：符号出现频率决定其码字长度。高频符号分配较短的二进制码，低频符号则分配较长的二进制码。示例表格通过将频率与码长1、2、3和4一一配对，明确呈现了这种对应关系。

1. 适用于一组已知各符号频率的固定信源符号集。

2. 该片段以示例文本“BANANA BANDANA”为例演示这一原理。

1. 图示
   观察依据

   表格列出了：A：$6 \to 0$，B：$2 \to 110$，N：$4 \to 10$，D：$1 \to 1110$，以及空格：$1 \to 1111$。

视频为示例文本中的每个字符给出了具体的二进制码字映射。该表格随后既用于消息编码，也用于计算该映射信息本身所占用的存储开销。

1. 仅针对示例字符串“BANANA BANDANA”。

2. 假设所展示的频率即为编码所依据的符号统计信息。

1. 霍夫曼编码中与频率相关的码长

1. 声音
   观察依据

   讲解员得出结论：由于共有5个不同字符，因此至少需要3位。

若要用定长二进制码唯一地编码$k$个不同字符，则至少需要$n$位，使得$2^n \ge k$。

1. 共有$k$个不同的字符需要编码。

2. 编码是长度为$n$的定长二进制字符串。

对所有正整数$k$和$n$。

1. 声音
   观察依据

   讲解员指出，97比特已远小于原始的112比特。

2. 图示
   观察依据

   屏幕上显示97比特，同时回溯到先前的112比特基准值。

对于该示例消息，屏幕上展示的定长编码使用97比特，小于原始的112比特。

1. 原始消息大小为112比特。

2. 该示例采用屏幕上展示的每符号3比特编码方案进行编码。

针对视频中展示的具体示例字符串。

1. 声音
   观察依据

   讲解员提问我们能否做得更好，并回答：可以，借助霍夫曼编码。

视频指出，霍夫曼编码对此示例能产生比先前所展示编码更优的结果。

1. 定长编码已被展示过。

2. 当前讨论的是同一信源消息。

本片段中的例子未证明任何一般性定理。

1. 声音
   观察依据

   讲解者指出，你也可以反过来操作，这不会影响最终结果。

将0分配给左分支、1分配给右分支（而非视频中展示的约定）不会影响最终结果。

1. 底层的树结构保持不变。

2. 仅交换了边上二进制标签。

针对本片段中展示的基于树的编码构造方法。

1. 声音
   观察依据

   讲解者指出，频率较高的字母被分配较短的码字，频率较低的字母被分配较长的码字。

2. 图示
   观察依据

   最终的码表明确体现了这一顺序。

对于本例中的树，频率较大的符号所获得的码字比频率较小的符号更短。

1. 请使用本片段中已完成的哈夫曼树及最终码表。

在具体示例中观察得出；视频将其呈现为关键思想，而非一般性证明。

1. 声音
   观察依据

   旁白指出，为高频字符分配较短编码、为低频字符分配较长编码，正是霍夫曼编码高效的原因。

霍夫曼编码之所以高效，是因为它为高频符号分配较短的码字，为低频符号分配较长的码字。

1. 源符号上存在已知的频率分布。

2. 编码依据示例中所展示的霍夫曼原则进行分配。

针对演示示例中的符号。

1. 声音
   观察依据

   旁白指出，文本占28比特，码表占54比特，总计为82比特。

2. 图示
   观察依据

   屏幕上显示28比特、54比特，以及一个框出的82比特。

对于字符串“BANANA BANDANA”及所展示的霍夫曼编码表，总存储量为82比特，其中编码文本占28比特，编码表占54比特。

1. 使用所展示的编码表。

2. 总计时需同时包含编码后的消息与映射表。

针对此特定示例字符串及该编码表。

1. 声音
   观察依据

   讲解员指出，82比特明显小于使用朴素压缩算法所得的97比特。

1. 本片段中并未重新推导朴素算法本身。

霍夫曼编码结果82比特明显小于此前讨论的朴素压缩算法所得的97比特结果。

1. 此前提到的97比特数值，指的是同一示例文本在朴素方法下的结果。

2. 总大小是在相同基准下进行比较的。

以“BANANA BANDANA”为例。

1. 声音
   观察依据

   讲述者指出，在更大的数据集上，该算法效果更佳，压缩效果的差异也更加明显。

1. 这是一个定性论断，片段中未提供证明或数值演示。

当霍夫曼编码应用于更大的数据集时，其压缩优势变得更加突出。

1. 同一通用编码方案被应用于更大的输入。

2. 对比中包含了编码表的开销。

针对比所展示的小例子更大的数据集。

1. 图示
   观察依据

   逐步计算各部分大小：原始文本占112位，编码后文本占42位，编码表占55位。

2. 声音
   观察依据

   讲解者逐步演示字符计数、每个字符的比特数以及编码表大小的计算过程。

1. 公式

   $$14 \times 8 = 112$$
   解释

   计算文本‘BANANA BANDANA’（含空格共14个字符）的原始大小，使用8位ASCII编码。

   步骤依据

   ASCII编码的定义及基础乘法运算。

   视频直接表达
2. 公式

   $$\lceil \log_2(5) \rceil = 3$$
   解释

   确定对5个不同字符（A、B、N、D、空格）进行编码所需的最少比特数。

   步骤依据

   二进制表示的容量（$2^2 < 5 \le 2^3$）。

   依据视频推导
3. 公式

   $$14 \times 3 = 42$$
   解释

   使用新的3位定长编码计算编码后文本的大小。

   步骤依据

   定长编码公式。

   视频直接表达
4. 公式

   $$5 \times (8 + 3) = 55$$
   解释

   计算解码所需的码表大小，存储5个条目（每个条目包含8位原始码和3位编码）。

   步骤依据

   码表开销公式。

   视频直接表达
5. 公式

   $$42 + 55 = 97$$
   解释

   计算包含码表在内的压缩文件总大小。

   步骤依据

   编码后文本大小与码表大小之和。

   依据视频推导

朴素压缩后的文件总大小为97比特，小于原始的112比特，但码表开销（55比特）显著。

1. 动画
   观察依据

   视频从五个带权叶节点出发，逐步构建该树。

2. 声音
   观察依据

   讲解者说明了合并规则，并指出需重复执行，直至所有节点合并成一棵完整的哈夫曼树。

1. 公式

   $$\{-:1,\ D:1,\ B:2,\ N:4,\ A:6\}$$
   解释

   初始时，每个不同符号对应一个叶节点，权重为其出现频次，并按权重升序排列。

   步骤依据

   讲解者指出需记录各字符频次，为每个字符创建节点，再按频次升序排列。

   视频直接表达
2. 公式

   $$1+1=2$$
   解释

   将两个最小权重的叶节点——空格符号与 D——合并，生成一个权重为2的新内部节点。

   步骤依据

   所陈述的规则是：选取两个频次最小的节点，将其频次之和作为新节点的频次。

   视频直接表达
3. 公式

   $$2+2=4$$
   解释

   在其余可用节点中，将权重为2的新节点与权重为2的节点 B 合并，形成一个权重为4的节点。

   步骤依据

   讲解者指出，需持续检查剩余节点中频次最小的两个，已合并的元素应被排除。

   视频直接表达
4. 公式

   $$4+4=8$$
   解释

   将权重为4的节点与权重为4的节点 N 合并，生成一个权重为8的节点。

   步骤依据

   这遵循相同的“反复选取最小两个进行合并”的流程。

   视频直接表达
5. 公式

   $$8+6=14$$
   解释

   将权值为8的节点与权值为6的节点A合并，得到权值为14的根节点。

   步骤依据

   该过程持续进行，直至所有节点都被合并成一棵完整的哈夫曼树。

   视频直接表达

完成的哈夫曼树根节点权值为14，其叶节点对应于A、B、N、D以及空格符号。

1. 声音
   观察依据

   讲解者说明了路径追踪法，并明确推导出$A = 0$和$B = 110$。

2. 图示
   观察依据

   最终表格列出了全部五个码字。

1. 关于N、D及空格符号的中间路径说明未被完整口述；它们的码字仅在最终表格中显示。

1. 公式

   $$\text{left edge}=1,\ \text{right edge}=0$$
   解释

   为完成树的每一条边标注一个二进制数字。

   步骤依据

   讲解者将1赋给左向边，将0赋给右向边。

   视频直接表达
2. 公式

   $$A:0$$
   解释

   从根节点到A仅经过一条右向边，因此路径标签为0。

   步骤依据

   讲解者明确追踪了从根节点到A的路径，并读出了唯一的数值0。

   视频直接表达
3. 公式

   $$B:110$$
   解释

   从根节点到B的路径依次经过左向边、左向边、右向边，结果为110。

   步骤依据

   讲解者明确追踪到节点 B 的路径，并读出110。

   视频直接表达
4. 公式

   $$N:10$$
   解释

   从根节点到节点 N 的路径先经过一条左分支，再经过一条右分支，得到10。

   步骤依据

   这遵循相同的根节点到叶节点的路径读取规则；该值显示在最终表格中。

   视频直接表达
5. 公式

   $$D:1110$$
   解释

   从根节点到节点 D 的路径连续经过三条左分支，然后是一条右分支，得到1110。

   步骤依据

   这遵循相同的根节点到叶节点的路径读取规则；该值显示在最终表格中。

   视频直接表达
6. 公式

   $$-:1111$$
   解释

   从根节点到空格符号的路径经过四条左分支，得到1111。

   步骤依据

   这遵循相同的根节点到叶节点的路径读取规则；该值显示在最终表格中。

   视频直接表达

最终生成的编码表为：$A = 0$，$B = 110$，$N = 10$，$D = 1110$，- = 1111。

1. 图示
   观察依据

   编码后的比特串显示在标题下方，并用“28比特”括起。

2. 图示
   观察依据

   表格列出了符号频次6、2、4、1、1以及对应码长1、3、2、4、4。

1. 公式

   $$A:6\to 0,\ N:4\to 10,\ B:2\to 110,\ D:1\to 1110,\ \text{space}:1\to 1111$$
   解释

   从所显示的表格中读取符号频次和码长。

   步骤依据

   直接从屏幕上的码表中观察得出。

   视频直接表达
2. 公式

   $$6\cdot 1 + 4\cdot 2 + 2\cdot 3 + 1\cdot 4 + 1\cdot 4$$
   解释

   将每个符号的频率乘以其码长，再对所有符号求和。

   步骤依据

   根据符号到码字的映射计算总编码长度的标准方法。

   依据视频推导
3. 公式

   $$6+8+6+4+4=28$$
   解释

   计算该和式以得到有效载荷大小。

   步骤依据

   算术化简。

   依据视频推导

字符串“BANANA BANDANA”的编码结果占用28比特，与屏幕上的标签一致。

1. 图示
   观察依据

   屏幕上将消息标注为28比特，将码表标注为54比特。

2. 声音
   观察依据

   讲解员称这使得总比特数达到82比特。

1. 54比特的码表开销内部构成并未在屏幕上推导。

1. 公式

   $$\text{payload}=28\ \text{bits}$$
   解释

   取示例中显示的编码消息大小。

   步骤依据

   从图示与讲解中观察得出。

   视频直接表达
2. 公式

   $$\text{table}=54\ \text{bits}$$
   解释

   采用示例中所示的码表存储方式。

   步骤依据

   从图示和讲解中观察得出。

   视频直接表达
3. 公式

   $$28+54=82$$
   解释

   将这两部分开销相加，得到总存储量。

   步骤依据

   视频明确地将这两个量合并为一个总量。

   视频直接表达

当同时存储编码后的文本和映射表时，整个压缩表示共需 82 比特。

1. 图示
   观察依据

   整个片段使用“BANANA BANDANA”来演示压缩步骤。

2. 声音
   观察依据

   讲解员明确将此作为文本示例引入。

使用定长编码方案压缩文本“BANANA BANDANA”，并计算包含码表在内的总压缩大小。

1. 文本：“BANANA BANDANA”（共14个字符）。

2. 原始编码：8位ASCII码。

3. 不重复字符：A、B、N、D、空格（共5个字符）。

计算朴素压缩后的总比特数。

1. 公式

   $$\text{Original Size} = 14 \times 8 = 112 \text{ bits}$$
   解释

   计算未压缩时的大小。

   步骤依据

   14个字符 × 8比特/字符。

   视频直接表达
2. 公式

   $$\text{Encoded Text Size} = 14 \times 3 = 42 \text{ bits}$$
   解释

   计算将字符替换为3比特编码后的文本大小。

   步骤依据

   5个不同字符需要3比特（$2^3=8 \ge 5$）。14个字符 × 3比特/字符。

   视频直接表达
3. 公式

   $$\text{Code Table Size} = 5 \times (8 + 3) = 55 \text{ bits}$$
   解释

   计算解码所需的查找表大小。

   步骤依据

   5个条目 × （8比特用于原始字符 + 3比特用于新编码）。

   视频直接表达
4. 公式

   $$\text{Total Compressed Size} = 42 + 55 = 97 \text{ bits}$$
   解释

   将编码后文本的大小与编码表的大小相加。

   步骤依据

   加法。

   依据视频推导

97比特

结果97比特小于原始的112比特，证实了压缩发生，但相对于这段短文本而言，开销较大。

1. 图示
   观察依据

   整段视频围绕单一示例字符串“BANANA BANDANA”展开。

2. 声音
   观察依据

   讲解者以该例引入霍夫曼编码，并逐步演示频率统计、树的构建及编码提取过程。

给定消息“BANANA BANDANA”，构造霍夫曼编码，并确定每个符号对应的码字。

1. 消息：BANANA BANDANA。

2. 不同符号：A、B、N、D 和空格（-）。

3. 所示频次：$A = 6$，$B = 2$，$N = 4$，$D = 1$，- = 1。

4. 所示边约定：左侧 = 1，右侧 = 0。

构造哈夫曼树，并列出每个符号对应的二进制编码。

1. 公式

   $$A:6,\ B:2,\ N:4,\ D:1,\ -:1$$
   解释

   统计消息中每个符号出现的次数。

   步骤依据

   讲解者提示先记下各符号的频次。

   视频直接表达
2. 公式

   $$\{-:1,\ D:1,\ B:2,\ N:4,\ A:6\}$$
   解释

   为每个符号创建一个叶节点，并按频次升序排列。

   步骤依据

   视频中明确将节点按频次升序排列。

   视频直接表达
3. 公式

   $$1+1=2,\ 2+2=4,\ 4+4=8,\ 8+6=14$$
   解释

   重复合并当前最小的两个节点，直至只剩一个根节点。

   步骤依据

   这是所陈述的哈夫曼合并规则。

   视频直接表达
4. 公式

   $$\text{left}=1,\ \text{right}=0$$
   解释

   为完成后的树的所有边分配二进制数字。

   步骤依据

   讲述者明确了这一约定，并指出反向约定也是可行的。

   视频直接表达
5. 公式

   $$A=0,\ B=110,\ N=10,\ D=1110,\ -=1111$$
   解释

   通过从根节点到对应叶节点的路径，读出每个符号的编码。

   步骤依据

   讲述者先以 A 和 B 为例进行演示，再将相同方法应用于其余符号。

   视频直接表达

A 对应 0，B 对应 110，N 对应 10，D 对应 1110，减号对应 1111。

最终呈现在屏幕上的表格与已完成树中的路径标签一致，片段同时强调：出现频率越高的符号，其编码越短。

1. 图示
   观察依据

   完整演算示例已给出：标题文字、码表、编码比特串、28 比特、54 比特 和 82 比特。

2. 声音
   观察依据

   讲解过程逐步演示了原文本的编码，以及消息长度与码表长度之和的计算。

1. 用于存储 54 比特码表的具体比特级格式未予展示。

使用图中显示的霍夫曼编码对文本“BANANA BANDANA”进行编码，并计算包含码表在内的总存储量。

1. 文本：BANANA BANDANA

2. 频次与编码：A：$6\to 0$，B：$2\to 110$，N：$4\to 10$，D：$1\to 1110$，空格：$1\to 1111$

3. 编码后消息的大小显示为28比特

4. 编码表的大小显示为54比特

求出编码后的比特串，以及存储压缩结果加编码表所需的总比特数。

1. 公式

   $$110\ 0\ 10\ 0\ 10\ 0\ 1111\ 110\ 0\ 10\ 1110\ 0\ 10\ 0$$
   解释

   用表中的哈夫曼编码替换字符串“BANANA BANDANA”中的每个字符。

   步骤依据

   直接应用所展示的映射关系。

   视频直接表达
2. 公式

   $$28\ \text{Bits}$$
   解释

   统计拼接后所有码字的总长度。

   步骤依据

   由编码串下方的大括号标出，并由旁白确认。

   视频直接表达
3. 公式

   $$54\ \text{Bits}$$
   解释

   计入编码表所需的存储空间。

   步骤依据

   旁白中已说明，并由围绕编码表的大括号标出。

   视频直接表达
4. 公式

   $$28+54=82\ \text{Bits}$$
   解释

   将有效载荷与编码表开销相加，得到压缩后的总大小。

   步骤依据

   视频中明确指出并直观展示。

   视频直接表达

编码后的比特串：110 0 10 0 10 0 1111 110 0 10 1110 0 10 0；包含编码表在内的总存储量：82比特。

算术式 $6*1 + 4*2 + 2*3 + 1*4 + 1*4 = 28$ 与显示的有效载荷大小一致，且 $28 + 54 = 82$ 与显示的总数一致。

1. 动画
   观察依据

   方块先从左向右穿过‘C’，再从右向左穿过‘$C^{-1}$’。

1. 蓝色“数据”方块

2. 红色“C”圆圈

3. 红色“$C^{-1}$”圆圈

4. 箭头

1. 数据方块经过 C 后，从 100 MB 缩小为 70 MB。

2. 数据块通过100MB，恢复为原始大小$C^{-1}$。

1. 方块上始终保留“数据”标签。

2. 标题“数据压缩”变为“无损压缩”。

直观呈现无损压缩算法的可逆性。

1. 动画
   观察依据

   字符 A、B、N、D、- 垂直排列于主文本下方。

1. 文本“BANANA BANDANA”

2. 字符的垂直列表

3. 括号与数字“5”

1. 逐个提取并列出各个字符。

2. 在列表旁显示5的计数。

1. 原始文本保留在顶部。

演示定长编码的第一步：找出唯一符号构成的字母表。

1. 动画
   观察依据

   依次出现1位、2位和3位的行，及其可能的组合。

1. 文本行：“1位 : ……”，“2位 : ……”，“3位 : ……”

1. 二进制组合列表呈指数增长（分别含2、4、8项）。

1. 格式“n位 : [列表]”保持一致。

说明为何至少需要3位来表示5个不同字符。

1. 动画
   观察依据

   为字符列表中的每个不同字符分配3位编码，然后用这些编码替换原文。

1. 字符列表

2. 编码分配（000、001等）

3. 编码后的二进制字符串

1. 字符旁的空位用3位编码填充。

2. 原始文本“BANANA BANDANA”被直观映射为一长串二进制字符串。

1. 该映射对各个不同字符是一一对应的。

展示源文本向压缩比特流的转换过程。

1. 动画
   观察依据

   初始的定长映射及总比特数逐渐淡出，仅保留标题，随后出现频率列表。

1. 标题：“BANANA BANDANA”

2. 定长映射：A : 000, B : 001, N : 010, D : 100, - : 101。

3. 总比特数：42 比特，55 比特，97 比特。

1. 3比特的映射及总比特数消失。

2. 屏幕清空，为频率统计做准备。

1. 示例字符串保持不变。

视觉重置标志着从比较先前的编码方式，转向引入霍夫曼编码这一更优方法。

1. 动画
   观察依据

   五个圆圈出现并排列成一行，每个圆圈标注符号及其出现频率。

1. 频率列表：A : 6, B : 2, N : 4, D : 1, - : 1。

2. 五个圆形叶节点，分别标注为 -、D、B、N、A，对应权重为 1、1、2、4、6。

1. 数值型频率被转换为独立的节点对象。

2. 这些节点按权重从小到大排列。

1. 每个不同符号恰好对应一个初始叶节点。

动画表明，霍夫曼编码从加权叶节点出发，而这些叶节点仅由符号频率决定。

1. 动画
   观察依据

   在每对较小节点上方添加父节点，红色箭头指向新生成的权重和。

1. 叶节点：-、D、B、N、A。

2. 带权重的内部节点：2、4、8、14。

3. 红色箭头表示新生成的父节点。

1. 两个权重最小的节点被反复合并到一个新父节点之下。

2. 可用的顶层节点数量不断减少，直至只剩一个根节点。

1. 每个父节点的权重等于其两个子节点权重之和。

2. 原始的叶节点符号保留在树的底部。

不断生长的树直观地编码了定义霍夫曼构造的贪心合并过程。

1. 动画
   观察依据

   在调整树的布局后，二进制数字出现在各条边上。

1. 完成的霍夫曼树。

2. 边上的标签：0和1。

1. 左分支边标记为1。

2. 右分支边标记为0。

1. 在标记过程中，树的拓扑结构保持不变。

此步骤将抽象的合并树转化为具体的二进制码生成器。

1. 动画
   观察依据

   根节点及通往A的路径以红色高亮显示，且代码0写在表格中A的旁边。

1. 根节点14。

2. 叶节点A。

3. 边的标记0。

4. A在码表中的条目。

1. 从根节点到A的路径被强调。

2. 码字0被添加至A所在表格行。

1. 此刻仅读取通往A的路径。

动画演示：一个符号的编码，恰好是其从根节点到叶节点路径上各条边的标签序列。

1. 动画
   观察依据

   通往B的路径被高亮显示，且在B旁写出110；随后展示完整的最终表格。

1. 对于N、D和-的中间高亮步骤，不如A和B那样明确，但最终表格清晰明了。

1. 从根节点到B的路径。

2. 最终表格：A : 6 0，B : 2 110，N : 4 10，D : 1 1110，- : 1 1111。

1. 将B的码字110加入。

2. 全部码字集合随之显现。

3. 树结构逐渐淡出，仅留下最终汇总表格。

1. 每个码字对应一条唯一的根节点到叶节点路径。

最终呈现将整个构造过程整合为一张查找表，并使频次与码长之间的规律清晰可见。

1. 图示
   观察依据

   静态画面显示标题“BANANA BANDANA”以及一个五行表格，内容为字符、频次与编码。

1. 标题文字“BANANA BANDANA”

2. 各行分别为：A：6 0，B：2 110，N：4 10，D：1 1110，空格：1 1111

1. 尚无动画；该表格以固定参考形式呈现。

1. 在此时间段内，字符-频次-编码的映射关系保持不变。

本片段先确立符号统计结果及由此生成的变长编码，再演示编码过程。

1. 动画
   观察依据

   二进制组依次出现在标题下方，构成示例文本的编码字符串。

1. 编码后的分组：110、0、10、0、10、0、1111、110、0、10、1110、0、10、0

1. 标题下方的空白区域从左至右依次填入各字符对应的码字。

1. 右侧的码表始终保持可见且不变。

这可视化了每个源字符被其霍夫曼编码字替换，并连接成一个比特流的过程。

1. 声音
   观察依据

   讲解员强调需要存储编码表，额外增加55位到42位有效载荷中。

假设减少每个字符的比特数总能显著减小文件大小，而未考虑解码所需的元数据。

对于短文本或大字母表，存储编码表的固定开销可能超过使用更短字符编码所带来的节省，导致朴素的定长压缩效率低下。

1. 声音
   观察依据

   讲述者表示，你也可以反过来操作，这不会影响最终结果。

有人可能认为，为了使霍夫曼编码正常工作，左侧必须始终为1，右侧必须始终为0。

视频指出，交换边的约定不会影响最终结果；关键在于所选树内部的一致性。

1. 声音
   观察依据

   讲述者强调，高频字母获得较短的编码，低频字母获得较长的编码。

固定长度的思维模式会让人觉得每个符号都应当使用相同数量的比特。

本片段将先前的固定长度编码方法与霍夫曼编码进行对比，后者中编码长度随频率而变化。

1. 声音
   观察依据

   讲解者明确地将54位的编码表加到28位的消息上，得到82位。

2. 图示
   观察依据

   画面区分了用于编码文本的28位和用于编码表的54位，再将二者合并。

人们可能误以为压缩后的大小就只是编码后消息的长度。

视频强调映射表也必须被存储，因此本例中真正的总大小为28＋54＝82位。

1. 图示
   观察依据

   该表格展示了不同长度的码字：0、10、110、1110、1111。

2. 声音
   观察依据

   讲解通过对比指出：高频字符使用较短的编码，低频字符使用较长的编码。

1. 这一误解并未被口头点明；而是从与定长编码直觉的对比中推断得出。

定长编码的心理模型会为每个符号分配相同的比特宽度。

本例采用变长编码，其长度与字符出现频率相关，这正是本片段所强调的核心效率机制。

1. 声音
   观察依据

   讲述者利用二进制容量规则来确定定长编码的3位长度。

理解$n$位所能表示的数值个数，是选择定长编码中编码长度的必要前提。

1. 声音
   观察依据

   讲述者解释，解码定长编码后的文本需要编码表。

编码表开销这一概念直接适用于定长编码方案的实现。

1. 声音
   观察依据

   在展示先前方法得到的97比特后，讲述者提问我们能否做得更好，并以霍夫曼编码作答。

固定长度编码被作为基准呈现，霍夫曼编码旨在对此加以改进。

1. 声音
   观察依据

   讲述者首先指出需记录频率并创建节点，接着强调关键步骤是合并这些节点。

频率统计提供了合并操作开始前所需的初始加权叶节点。

1. 声音
   观察依据

   树构建完成后，讲解者接着为各条边分配二进制值。

必须先存在一棵完整的树，边上的标签才能定义码字。

1. 声音
   观察依据

   完成边的标注后，讲解者指出该树现在可用于计算每个字母对应的编码。

边上的标签即为从根节点到叶节点路径上所读取的原始符号，由此生成码字。

1. 图示
   观察依据

   最终的表格直观展示了高频符号对应短编码、低频符号对应长编码。

2. 声音
   观察依据

   讲解者称这一模式为霍夫曼编码背后的关键思想。

提取出的编码表体现了霍夫曼编码的一般原则：符号出现频率决定其编码长度。

1. 声音
   观察依据

   讲解明确指出了基于频率的编码分配规则。

2. 图示
   观察依据

   该表格用具体的编码实例化了这一规则。

将通用的基于频率的原理应用于生成“BANANA BANDANA”的特定编码表。

1. 图示
   观察依据

   通过按所展示的表格替换每个字符，形成编码后的比特串。

直接使用示例表格计算28比特的编码有效载荷。

1. 图示
   观察依据

   视频先展示28比特和54比特，再将它们合并为82比特。

总尺寸结论依赖于先确定有效载荷尺寸，再加入编码表开销。

1. 图示
   观察依据

   54比特的编码表标签与28比特的有效载荷标签合并，得到总尺寸。

总尺寸公式还依赖于单独测得的编码表开销。

1. 声音
   观察依据

   在计算出包含编码表开销的82比特后，讲解者指出：数据集越大，其优势越明显。

1. 片段中的缩放论证是定性的。

观察到编码表开销是一项独立的加性成本，这支持了“输入规模越大，其相对影响越小”的论断。

1. 声音
   观察依据

   叙述中给出的定义。

1. 无损压缩

1. 图示
   观察依据

   二进制容量的可视化列表。

1. 二进制表示容量
2. 唯一编码所需的最少位数

1. 公式
   观察依据

   计算$5 * (8 + 3) = 55$位。

1. 编码表开销

1. 图示
   观察依据

   屏幕上显示97比特替换了42比特和55比特。

2. 声音
   观察依据

   讲解者将97比特与原始的112比特进行比较。

1. 示例消息的定长3比特编码

1. 声音
   观察依据

   讲解者指出，应首先记录各符号的频率，然后按频率递增顺序创建并排列节点。

1. 构建霍夫曼树前，先统计各符号的出现频率

1. 声音
   观察依据

   讲述者陈述了规则：选取两个最小的频率，将它们相加形成一个新节点。

1. 霍夫曼编码核心合并规则

1. 声音
   观察依据

   讲述者将1分配给左分支，将0分配给右分支，并指出反过来也同样可行。

1. 为树的各条边分配二进制数字
2. 认为左右分配0–1是强制性的

1. 声音
   观察依据

   讲述者通过从根节点追踪路径，明确推导出 $A = 0$。

1. 从每个符号对应的根节点到叶节点的路径读取其编码

1. 声音
   观察依据

   讲述者总结道：高频字母获得较短的编码，低频字母获得较长的编码。

1. 高频符号获得较短的码字

1. 声音
   观察依据

   解说说明了为何出现频率更高的字符会分配更短的编码。

1. 霍夫曼编码中与频率相关的码长

1. 图示
   观察依据

   编码表可见，其中列出了各字符的出现频率及其对应的二进制编码。

1. “BANANA BANDANA”的霍夫曼编码示例表

1. 图示
   观察依据

   编码后的字符串长度标注为28比特。

1. 示例的编码后消息大小
2. 根据所显示的表格计算28比特的有效载荷