type
status
date
slug
summary
tags
category
icon
password
📝 实验一 算术编码
题目
算术编码（最短二进制编码）编码时，输入字典为[’A’,’B’,’C’,’D’]，[0.1,0.4,0.2,0.3]待编码字符串为’CADACDB’，编码结果应该得到一个最短的二进制数，并能根据编码结果进行解码，得到原字符串。
题目简介——算术编码
算数编码的本质是——在保留原始字符排列顺序的同时，对于出现频率更高的字符，也就是概率更大的字符，赋予更大的小数区间。
编码
例如有这样一段字符：AABABC。
P(A) = 0.5P(B) = 0.4P(C) = 0.1那么算术编码会对 0 -1 进行区间划分。
A [0,0.5) B [0.5,0.9) C [0.9,1)
AABABC的第 1 个字符为：A，那么我们选中了 A 的区间 [0, 0.5) 作为新的目标区间。
我们对新目标区间，再按照 ABC 的概率占比进行划分。
A [0, 0.25), B [0.25, 0.45), C [0.45, 0.5)
AABABC的第 2 个字符仍然为：A，那么我们再选中了 A 的区间 [0, 0.25) 作为新的目标区间。
我们对新目标区间，再按照 ABC 的概率占比进行划分。
A [0, 0.125), B [0.125, 0.225), C [0.225, 0.25)
不断重复上述操作，直到最后一个字符。
当前字符 | 当前目标区间 |
A | [0,0.5) |
A | [0,0.25) |
B | [0.125,0.225) |
A | [0.125,0.175) |
B | [0.15,0.17) |
C | [0.168,0.17) |
完成上述操作后，最终目标区间为[0.168,0.17),在这个区间内选一个小数，要求这个小数可以被转换成这个区间内的一串最短的二进制编码，即完成压缩。
解码
解码操作需先由二进制串转化为十进制编码小数，再依次由第一个区间开始进行判定每一个字符。
假设这个小数为：0.168763。我们先从第一个区间开始确定第一个字符。
A [0, 0.5), B [0.5, 0.9）, C [0.9, 1)
0.168763位于A区间，所以第一个字符为A。
接着对A [0,0.5)进行划分。
A [0, 0.25), B [0.25, 0.45）, C [0.45, 0.5)
0.168763仍位于A区间，所以第二个字符仍然为A。
接着对A [0,0.25)进行划分。
A [0, 0.125), B [0.125, 0.225）, C [0.225, 0.25)
0.168763位于B区间，所以第三个字符为B。
重复下去直到最后一个区间，就会得到解码字符AABABC。
为什么要这样划分区间呢？因为算术编码的目的，是要在最终的目标区间内，找一个二进制最短的小数作为最终编码。
那么怎么去找到这样一个目标区间呢？最终目标区间的范围更大，可容纳的小数精度就越低，意味者我们最终的二进制编码更短。比如在低精度的 [0.1, 0.2) 和 高精度的 [0.1111111111, 0.1111111112) 之间各找一个最短编码的二进制进行比较，肯定是 [0.1, 0.2) 中找到的的最短二进制编码更短。
所以算术编码的实现途径就是：尽量使最终目标区间的范围更大。
由于高频字符出现次数多，区间较大，而低频字符出现次数少，区间小。所以在遍历完所有字符之后，我们最终得到目标区间就更大，也就是小数精度更低。
CODE
🤗 总结归纳
通过本次实验学习到了算术编码的原理，同时解决了一些编程中的问题，如：键值对的使用，python底层的问题，深拷贝等。提升了编程能力。
📎参考文章
- Author:XZY
- URL:https://xzy-blog.top/article/%E5%A4%9A%E5%AA%92%E4%BD%93%E6%95%B0%E6%8D%AE%E5%A4%84%E7%90%861
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts