一种压缩传输算法

[weijiz]

昨天在微博上看到这样的一个新闻。

蚌埠一个工人从高空坠落身体被四根钢筋穿透。

这句话虽然只有这么几个字但是包含的信息就非常多。从最开始说，蚌埠。这是什么？这是一个地名，包含了位置坐标信息，又可以延伸出整个城市的信息。工人这个词也包含了很多的信息。说明这个人是在那里工作的。由此也可以引申出很多内容。这样看似简单的一句话包含了大量的信息，显然是一种很高效的压缩算法。

然而并不是所有人都能够理解这么一句话的意思，你对一个外国人说这句话他显然就是无法理解的。所以理解的基础在于字典。什么是字典呢，就是词和实际含义之间的映射关系。由此我想到了一种很高效的压缩数据传输算法。基本过程如下。

首先发送者分析要发送的数据，从中提取出重复出现的部分，将其用简短的数据替代。最后形成一个简短字符和实际数据的映射，也就是一个字典。把数据用字典的形式表达出来。以实际数据为例

原始数据
AAAAAABBBBBBBCCCCCCCC
字典
AAAAAA -> $A
BBBBBBB -> $B
CCCCCCCC -> $C
用字典表示后的数据
$A$B$C

这样是不是短了很多
然后发送者把用字典表示后的数据发送给接受者。

接收者本地维护了一份字典。他首先尝试利用自己本地的字典进行解释，如果本地有对应的解释就把对应的数据解释出来。如果没有对应的解释就向发送者询问对应的词是什么意思，然后发送者发送对应的映射关系，接受者收到后对词进行解释，同时更新本地的字典。当下次再次收到这个词的时候就可以不用询问直接解释。以实际数据为例

接收到的原始数据
$A$B$C
接收者的本地字典
$A -> AAAAAA
$C-> CCCCCCCC
接收者无法解释$B然后从发送者处询问$B的含义
发送者发送$B -> BBBBBBB
接收者对数据进行解释，得到最终的数据
AAAAAABBBBBBBCCCCCCCC

这个算法的有效性的前提条件是数据是有一定规律的，并不是完全的随机。这个也是所有的压缩算法能够有效的条件。

具体的实现还是有一些问题，希望以后能把它实现出来吧。比如字典的提取应该是在多大的范围上，字典的范围肯定是会影响整个压缩结果的。字典的文件大小也可能会很大。个人感觉和自相关函数是有点关系。