南通网站制作计划/合肥seo推广培训班
- 问题描述
证明：如果我们将字母表中字符按频率单调递减排序，那么存在一个最优编码，其码字长度是单调递增的。 - 问题分析
任务是证明存在一个码字长度单调递增的最优编码，那么如果可以从它的反例推出码字长度单调递增的编码是最优编码，则问题可以求证。 - 问题求解
①假设字母表为：{c1,c2,...cn}，字母出现的频率用f表示，字母对应的码字长度用d 表示。则用数学的语言描述待证明的问题是：如果f(c1)≥f(c2)≥...≥f(cn)，那么存在最优编码使得d(c1)≤d(c2)≤...≤d(cn)。
②假设在字母集的一个最优编码T中，存在i<j ,f(ci)≥f(cj)，d(ci)>d(cj)。通过交换T中ci 和cj的编码，可以得到编码T′。T′中字母的频率和字码长度分别用f′和d′表示，则f′(ci)≥f′(cj)，d′(ci)<d′(cj)。则
B(T)−B(T′)=∑k=1nf(ck)(d(ck)−d′(ck))=f(ci)[d(ci)−d′(ci)]+f(cj)[d(cj)−d′(cj)]=f(ci)[d(ci)−d(cj)]+f(cj)[d(cj)−d(ci)]=[f(ci)−f(cj)][d(ci)−d(cj)]≥0
因此B(T)≥B(T′)。由于T是字母集的一个最优编码，所以T′ 也是字母集的一个最优编码。