ROS交流群
ROS Group
产品服务
Product Service
开源代码库
Github
官网
Official website
技术交流
Technological exchanges
激光雷达
LIDAR
ROS教程
ROS Tourials
深度学习
Deep Learning
机器视觉
Computer Vision

一种压缩传输算法



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

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

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

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

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

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

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

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

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

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

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


Log in to reply