最后更新: 2025-01-21 16:17 查看: 33 次反馈刷题

编码

## 编码
－如何从信号流中识别字符
－等长度编码 vs．不等长度编码
－例子：对包含 $\left\{ a (45), b _{(13)}, c _{(12)}, d _{(16),}, e _{(9)}, f _{(5)}\right\} 6$ 个字符的 10万个字符的数据文件编码，每个字符后面的数字表示该字符出现的频率（\％）。
－编码方案一： $a (000), b (001), c (010), d (011), e (100), f(101)$ ；则文件总长度 30 万字位。
－编码方案二： $a ( 0 ), b ( 1 0 1 ) , c ( 1 0 0 ), d (111), e (1101), f (1100)$ ；则文件总长度 22.4 万字位，空间节省四分之一。

## 不等长编码的分隔
－如何从信号流中识别不等长编码表示的字符
－显式表示长度：专用位或特定结束信号
－匹配的唯一性（比如，前缀码）
－如果符号串 $\alpha$ 可以表示成符号串 $\beta_1$ 和 $\beta_2$ 的并置，则 $\beta_1$ 称为 $\alpha$ 的一个前缀。（注意：$\beta_1$ 和 $\beta_2$ 可以是空串。）
－设 $A=\left\{\beta_1, \beta_2, \ldots, \beta_m\right\}$ 是符号串的集合，且对任意 $\beta_i, \beta_j \in A$ ，若 $i \neq j , \beta_{ i }$ 与 $\beta_{ j }$ 互不为前缀，则称 A 为前缀码。
－若 $A$ 中的任意串 $\beta_{ i }$ 只含符号 0,1 ，则称 $A$ 是二元前缀码。

## 用二叉树生成二元前缀码
－生成方法
－给边标号：对内点，对其出边标上号，左为 $0$ ，右为 1 。
－给叶编号：从根到每个树叶存在唯一的通路，构成该通路的边的标号依次并置，所得作为该树叶的编号。
－给定一棵完全二叉树，可以产生唯一的二元前缀码。
 ![图片](/uploads/2025-01/a46200.jpg)
 
 ## 最优前缀码
 －问题：二进前缀码 $A=\left\{\beta_1, \beta_2, \ldots, \beta_{ m }\right\}$ 表示 m 个不同的字母，如果各字母使用频率不同，如何设计编码方案可以使总传输量最少。
－基本思想：使用频率高的字母用尽量短的符号串表示。
－问题的解：若用频率（相对值）作为树叶的权，最佳二元前缀码对应的二叉树应该是最优二叉树。

－若 $T$ 是二叉树，且每个叶 $v_1, v_2, \ldots, v_{ t }$ 带数值权 $w_1, w_2, \ldots w_{ t }$ ，则二叉树 T 的权 $W(T)$ 定义为：$\Sigma_{ i =1}^{ t } w_i l\left(v_i\right)$ ，其中：$l\left(v_i\right)$ 表示 $v_i$ 的层数。
－具有相同权序列的二叉树中权最小的一棵树称为最优二叉树。
 ![图片](/uploads/2025-01/42661b.jpg)

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：决策树

下一篇： Huffman编码（算法）

本文对您是否有用？有用 (0) 无用 (0)