#import "../template.typ": *
#import "@preview/tablem:0.1.0": tablem
#import "@preview/mitex:0.2.4": *
#import "@preview/cetz:0.2.2"

#show: project.with(
  title: "5",
  authors: ("absolutex",),
)

#set par(first-line-indent: 0em) // 不换行
#show heading: it => {
  set text(font: 字体.黑体)
  if it.level == 1 {
    pagebreak(weak: true)
    align(center)[#text(size: 字号.小二, it.body)]
  } else if it.level == 2 {
    // 不标序号
    text(size: 字号.四号, it.body)
  } else if it.level == 3 {
    text(size: 字号.小四, it)
  } else {
    text(size: 字号.五号, it)
  }
}

= 第五章作业

== 5.4

赫夫曼码。考虑随机变量 $X=$

#tablem[
  |x1|x2|x3|x4|x5|x6|x7|
  |---|---|---|---|---|---|---|
  |0.49|0.26|0.12|0.04|0.04|0.03|0.02|
]


(a)求X的二元赫夫曼码。

#tablem[
  |编码|-|-|-|-|-|-|-|-|
  |---|---|---|---|---|---|---|---|---|
  | 1 | $x_1$ | 0.49 | 0.49 | 0.49 | 0.49 | 0.49 | 0.51 | 1 |
  | 00 | $x_2$ | 0.26 | 0.26 | 0.26 | 0.26 | 0.26 | 0.49 | - |
  | 011 | $x_3$ | 0.12 | 0.12 | 0.12 | 0.13 | 0.25 | - | - |
  | 01000 | $x_4$ | 0.04 | 0.05 | 0.08 | 0.12 | - | - | - |
  | 01001 | $x_5$ | 0.04 | 0.04 | 0.05 | - | - | - | - |
  | 01010 | $x_6$ | 0.03 | 0.04 | - | - | - | - | - |
  | 01011 | $x_7$ | 0.02 | - | - | - | - | - | - |
]


(b)求该编码的期望码长。

$H(X) =2.01 "bits"$

(c)求X的三元赫夫曼码。

#tablem[
  |编码|-|-|-|-|-|
  |---|---|---|---|---|---|
  | 0 | $x_1$ | 0.49 | 0.49 | 0.49 | 1 |
  | 1 | $x_2$ | 0.26 | 0.26 | 0.26 | - |
  | 20 | $x_3$ | 0.12 | 0.12 | 0.25 | - |
  | 22 | $x_4$ | 0.04 | 0.09 | - | - |
  | 210 | $x_5$ | 0.04 | 0.04 | - | - |
  | 211 | $x_6$ | 0.03 | - | - | - |
  | 212 | $x_7$ | 0.02 | - | - | - |
]

== 5.14

赫夫曼码。设随机变量X的概率为

$p=(1 / 21,2 / 21,3 / 21,4 / 21,5 / 21,6 / 21)$

试求其

(a)二元赫夫曼编码

#tablem[
  |编码|-|-|-|-|-|-|-|
  |---|---|---|---|---|---|---|---|
  | 00 | $x_1$ | 6/21 | 6/21 | 6/21 | 9/21 | 12/21 | 1 |
  | 10 | $x_2$ | 5/21 | 5/21 | 6/21 | 6/21 | 9/21 | - |
  | 11 | $x_3$ | 4/21 | 4/21 | 5/21 | 6/21 | - | - |
  | 010 | $x_4$ | 3/21 | 3/21 | 4/21 | - | - | - |
  | 0110 | $x_5$ | 2/21 | 3/21 | - | - | - | - |
  | 0111 | $x_6$ | 1/21 | - | - | - | - | - |
]

(b)三元赫夫曼编码

#tablem[
  |编码|-|-|-|-|-|
  |---|---|---|---|---|---|
  | 1 | $x_1$ | 6/21 | 6/21 | 10/21 | 1 |
  | 2 | $x_2$ | 5/21 | 5/21 | 6/21 | - |
  | 00 | $x_3$ | 4/21 | 4/21 | 5/21 | - |
  | 01 | $x_4$ | 3/21 | 3/21 | - | - |
  | 020 | $x_5$ | 2/21 | 3/21 | - | - |
  | 021 | $x_6$ | 1/21 | - | - | - |
]

(c)计算以上每种情形的$L=∑P_i l_i$。

$L_1=51 / 21=2.43, L_2 = 34 / 21=1.62$

== 5.18

码的种类。考虑码{0,01}


(a)它是即时的吗？

不是。

(b)它是惟一可译的吗？

是。

(c)它是非奇异的吗？

是。

== 5.20

带价值的赫夫曼码。单词如 Run！，Help！和Fire！很简短，不是因为它们经常被使用，而多半是因为在需要用到这些词的场合中时间宝贵的缘故。假定 $X=i$ 的概率为 $p_i$。设 $l_i$ 为 $X=i$ 对应码字的比特数，$c_i$ 表示当X=i时，码字的每字母价值。于是对 X描述的平均价值为 $C=sum_(i=1)^m p_i c_i l_i$.

(a)在满足$Sigma 2^(-l)<=1$的所有 $l_1,l_2,... l_m$ 上，对C进行最小化。忽略对$l_i$的默认整数限制，试求C达到最小值时的$l_1^*,l_2^*,... l_m^*$及相应的最小值$C^*$。

$q_i=(p_i c_i) / (Sigma p_i c_i)$

#mi[`
C =\sum p_{i}c_{i}n_{i} \\
=\Sigma p_i c_i\sum q_i\log\frac{1}{r_i} \\
=\Sigma p_i c_i\left(\sum q_i\log\frac{q_i}{r_i}-\sum q_i\log q_i\right) \\
= \Sigma p_i c_i(D(q||r)+H(q))
`]

$>=Sigma p_i c_i H(q)$

$q_i=r_i$ 时等号成立

$(p_i c_i) / (Sigma p_i c_i)=2^(-l_i^*)$

$l_i^*=log (Sigma p_i c_i) / (p_i c_i)$

$C^*=(Sigma p_i c_i)H(q)$


(b)在所有惟一可译码范围内，如何利用赫夫曼编码程序以最小化C？记 $C_"Huffman"$ 表示这个最小值。

在程序使用 q 代替 p

(c)请证明 $C^*<=C_"Huffman"<=C^*+sum_(i=1)^m p_i c_i$

$-log q_i <= ceil(-log q_i) <= -log q_i+1$

乘以 $p_i c_i$ 并求和得

$C^* <= C_"Huffman"<=C^*+sum p_i c_i$

== 5.26

合并。将资产分别为W1，W2，...，Wm的公司以如下方式合并。首先合并其中的两个资产最小的公司，于是形成$m-1$个公司。合并后的资产是被合并的两个公司资产之和。继续此过程，直至仅剩一个子公司为止。设V等于所有合并的资产的累计和。于是V表示在合并过程中所呈报的资产的总和。例如，若W=（3,3,2,2)，合并产生（3,3,2,2)→(4,3,3)→(6,4)→(10), 从而 $V=4 +6+ 10=20$。

（a）说明对于由两两合并而终结于个超大型公司的所有序列过程，V是可达的最小资产。（提示：请与赫夫曼编码比较。）

归一化后，合并的总次数等于每家公司的价值总和乘以其参与合并的次数的总和，与赫夫曼编码平均长度相同。由于赫夫曼编码最大限度地减少了平均长度，因此这种合并方案可以最大限度地减少合并总量。

（b）设 $W=Sigma W_i, tilde(W_i)=W_i/W$，证明最小合并资产累计和V满足$W H(tilde(W))≤ V≤ W H(tilde(W)) + W$

$H <= E L < H+1$

$W H(tilde(W))≤ V≤ W H(tilde(W)) + W$