V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
8520ccc
V2EX  ›  分享发现

[奇思妙想] 网络传输中的乱序压缩实现?

  •  
  •   8520ccc · 2020-11-27 12:04:56 +08:00 · 3116 次点击
    这是一个创建于 1436 天前的主题,其中的信息可能已经有所发展或是发生改变。

    以下仅为个人猜想,部分设计的知识点本人并没有掌握,仅仅只是发表一个理论上可能实现的东西

    本贴想要讨论的是极限压缩后再实现压缩(即本身已经无法通过现有的任何压缩算法减小体积)

    与其说是奇思妙想不若说是异想天开!欢迎各位指正~

    先说说压缩吧,压缩的原理是将重复的 N 个字节 X 缩短为 NX 来达到缩短信息长度却不损失信息的效果!

    但是这个很明显在一个极限后就无法压缩了,那就是当信息基本无重复的字节的时候,压缩算法就会失效!

    那么有没有可能实现无序信息的压缩呢,即在不损失信息的情况下缩短信息长度

    在下提出这么一个想法!

    首先创建 256 个字典,每个字典长度为 256 !每个字典的元素为 0-255 的两两组合! 0-255 的全部组合刚好是 65536 个!

    256 个 256 长度的字典刚好包含他的全部组合!

    以下是网络 TCP 传输时的实现(仅为假设,本人对 TCP 这个并不熟悉,仅为举例,我想表达的是这个理论压缩实现,而非 TCP 这个):

    第一步:同时打开 256 个 TCP 链接!并且它们各自都有一个标识符号!代表 0-255,分别代表他们所指向的字典

    第二步:准备发送数据!先将原始数据分割为两个字节为一个元素的数组!然后去找到他们所在的字典序号与所在字典内的索引!

    第三步:发送数据,按先后顺序把字节通过元素所在字典序号的 TCP 链接发送其所在的字典索引!

    第四步:接受数据,接收者收到数据后根据收到的索引与接受数据的 TCP 链接代表的字典序号将其重新转化为两个字节的元素!

    如此可以达到用一个字节来传输两个字节的效果!

    这样的话 1G/s 的宽带就传输 2G/s 的内容了!

    同理,只要增加同时的链接数,就可以无限提高效率,例如直接 65536 个链接! 1 个字节直接代表 4 个字节~

    但是会有问题存在!

    那就是但是接收数据很难高效的判断先后顺序,特别是大流量,高延迟时,达到的先后顺序很有可能出错~

    理论上来说这个方案是可以实现的。但是实用性与可靠性就需要实际测试了~

    以下是文件压缩的实现:

    一,首先创建 256 个文件,每个文件代表其所属的字典! 二,将两个字节转化为字典与索引的形式! 三,将索引写入字典

    这里还原时会有一个难点,那就是怎样判断写入顺序?

    所以文件压缩的实现可能很难实现吧

    33 条回复    2020-11-28 09:42:40 +08:00
    Lax
        1
    Lax  
       2020-11-27 12:29:25 +08:00
    即使不是大流量高延时,到达顺序也保证不了。而且你这里的传输开销很大,每两个字节就要一个 TCP 报头,流量会高于现在 TCP 实现
    shyrock
        2
    shyrock  
       2020-11-27 12:52:23 +08:00
    兄弟,你的索引数据长度也是 2 个字节。。。哪里压缩了。。。
    既然要压缩数据,建议先了解一下香农的《通信的数学原理》中信息熵的定义。
    TransAM
        3
    TransAM  
       2020-11-27 13:00:37 +08:00 via Android
    你那个是文本的压缩原理。图像的压缩主要是函数变换。
    rekulas
        4
    rekulas  
       2020-11-27 13:06:14 +08:00
    tcp 概念是多余的, 延迟流量顺序等概念都可以去掉干扰信息, 你这个设想基本原理就是索引查找内容,用在固定内容上面没有问题,但用在不限定内容内容上就无法实现了,如同二楼所说,你无法让索引的总数小于内容的总变化数(如果可以的话,信息就可以无限压缩很明显这是错的)

    我觉得更现实的方法是, 你用一台超算找到 2 个数让他们的除小数部分 0 开始的值刚好包含你的数据,这样你只需要发送 2 个数加长度就可以发送几百 G 的数据了,可能更靠谱 - -
    nanometer
        5
    nanometer  
       2020-11-27 13:11:11 +08:00
    且不说别的,TCP 包头就 8 个字节,也就说,以你的方式,每发送 2 个字节的信息,就需要发送 10 个 byte 。好样的!
    no1xsyzy
        6
    no1xsyzy  
       2020-11-27 13:18:19 +08:00
    这也能民科?
    no1xsyzy
        7
    no1xsyzy  
       2020-11-27 13:20:52 +08:00
    开 256 个 SRC-IP 和 DST-IP 相同的链接,就意味着你需要 256 个不同的端口号,同时你还需要每次发送这个端口号。
    est
        8
    est  
       2020-11-27 13:51:47 +08:00
    楼主这想法怕不是受了 Pi 的小数后面包含了所有信息的启发。你只需要记住是从第几位开始多少长度就行了。说不定 Pi 从第 m 位到 第 n 位包含了一部 GBK 编码的《金瓶梅.txt 》呢。
    kop1989
        9
    kop1989  
       2020-11-27 14:02:43 +08:00
    这不就是我先给你买本书,然后把我想说的压缩成:第五页第二段+第十页第一段。
    这个完全没有现实意义啊。
    1 、你这本书(字典)要提前传递。
    2 、要包括所有可能的排列组合。
    这就像是,我为了把一封信压缩到短信里( 70 个字),先给你物流了一座图书馆。
    TtTtTtT
        10
    TtTtTtT  
       2020-11-27 14:08:42 +08:00
    楼主说的挺好的呀,只不过现在越来越不倾向于这么做了。
    过去一根线一个用途,现在一根线上跑所有数据。
    这样能够有效降低你所说的研发成本和运维成本,而实际上压缩率没有你想象的那么重要。
    8520ccc
        11
    8520ccc  
    OP
       2020-11-27 14:09:48 +08:00
    @kop1989 有所不同 一个字节代表两个字节时其实根本不需要字典,因为每个字节本身就是 256 个可能直接通过序号代表第一个字节就行了,发送的代表第二个字节。。。。当
    8520ccc
        12
    8520ccc  
    OP
       2020-11-27 14:11:23 +08:00
    @TtTtTtT 确实没那么重要吧 我就是灵光一现想看看能否实现罢了 脑袋中总会徘徊这个问题~纯粹是想看看这个问题是否可能有解而已~
    8520ccc
        13
    8520ccc  
    OP
       2020-11-27 14:11:47 +08:00
    @est 完全不同 但是我想过你说的这种
    8520ccc
        14
    8520ccc  
    OP
       2020-11-27 14:13:53 +08:00
    @no1xsyzy 这不算名科啥的吧 有想法畅所欲言有何不可?我只是有一个想法,分享出来大家一起讨论而已,我也没说自己是对的,我开头也说了仅仅是我的理论上可行的可能而已,你没必要来这里来显示你多有文化吧?
    8520ccc
        15
    8520ccc  
    OP
       2020-11-27 14:15:24 +08:00
    @shyrock 索引长度是一个字节啊,索引最长就是 255 最小为 0 一个字节刚好能表示他的所有可能,或者换一种说法用链接序号做第一个字节,用发送的字节做第二个字节!
    8520ccc
        16
    8520ccc  
    OP
       2020-11-27 14:16:38 +08:00
    @rekulas 其实不必引入索引这个说法,直接用链接序号做第一个字节用发送的哪个字节做第二个字节就行了
    8520ccc
        17
    8520ccc  
    OP
       2020-11-27 14:17:19 +08:00
    @Lax 嗯纯粹一个想法 想发出来大家讨论而已
    8520ccc
        18
    8520ccc  
    OP
       2020-11-27 14:18:40 +08:00
    @rekulas 你的这个想法不错的~
    kop1989
        19
    kop1989  
       2020-11-27 14:25:27 +08:00
    @8520ccc #11 我理解你的意思,你的意思是说,可以用一些传输过程中的、或者收发者理应同时持有的客观信息来当作传递数据的一部分。在你的例子中你利用了“通道数量”和“顺序”这两个额外属性来传递信息。

    但你要反过来思考,提供额外的连接和保证顺序,这不也是一种“字典”么,只不过你忽略了创建,或者说传递这个“字典”的成本而已。

    换句话说,你为了压缩狭义的数据量,增加了广义的数据量(而且总体上而言还是信息量增加的)。
    XiaoxiaoPu
        20
    XiaoxiaoPu  
       2020-11-27 14:29:58 +08:00   ❤️ 1
    如果不同端口是共用相同的物理信道(例如在 TCP 构建在 IP 之上,IP 构建在以太网之上),那么为了区分不同端口,传输层必然引入额外的信令来标识端口,你所谓的只传输一个字节,在物理信道上仍然要占用两个字节。
    如果不同端口是独立的物理信道,那相当于用 256 倍物理信道,实现 2 倍物理信道的带宽,效率只有原本的 1/128,低到令人发指。
    kop1989
        21
    kop1989  
       2020-11-27 14:35:38 +08:00
    @XiaoxiaoPu #20 lz 的这个例子简单点就是,东西抱着沉,但背着就不沉了(因为看不见😂)。
    no1xsyzy
        22
    no1xsyzy  
       2020-11-27 14:37:15 +08:00   ❤️ 1
    @8520ccc 你除了没说自己是对的,其他部分确实就是民科呢亲
    不挑信息内容的 1:2 压缩率,你觉得轮得到你发现?
    这狗屁不通的理论还能理论上可行?你没必要来这里显示你多没文化吧?
    si
        23
    si  
       2020-11-27 14:47:55 +08:00
    我刚刚查了一下,“每发一个包,不论大小协议头会占用一定的空间 TCP 头 20 字节,IP 头 20 字节,MAC 头 14 字节,共 54 字节”。相当于用几十个字节表示一个字节了。好像要 256*54=13824 个连接才能抵得过,而且还没考虑其他问题。
    shuax
        24
    shuax  
       2020-11-27 14:48:33 +08:00   ❤️ 1
    支持楼主,香农算什么,他根本不懂什么叫信息。(狗头)
    yolee599
        25
    yolee599  
       2020-11-27 16:35:40 +08:00
    字典快递过去吗?
    CrazyRundong
        26
    CrazyRundong  
       2020-11-27 17:58:47 +08:00
    指出一下主要的 flaw 吧:

    “用一个字节来传输两个字节的效果” 是错误的。按照你的算法,虽然虚构的 “TCP 链接” 里只传输了 1 字节,但是为了让远端知道用来解码的字典序号,还需要在协议中规定按照 “接受数据的 TCP 链接代表的字典序号” 来确定字典——也就是说,256 个信道,每一时间槽只有 1 个信道有效,这不就是把第 1 字节的信息用时分复用传输嘛——到头来 2 个源字节的信息你都得发出去。

    你自己提到的 “接收数据很难高效的判断先后顺序”,就是时分复用模式的问题。LZ 愿意想这些问题是值得鼓励的,但毕竟思而不学则殆。建议 LZ 去搜一些严肃的课程材料,譬如通信原理和信息论,稍微了解下信息熵、时分 /频分复用这些基本概念。

    不要低估聪明人(我是指,历史上 *真正的* 那部分聪明人)在闲得无聊时候做的思维体操,更不要低估 *理论上* 这三个字的重量 :)

    祝 LZ 学习愉快
    garipan
        27
    garipan  
       2020-11-27 18:29:07 +08:00
    Pied Piper 准备上线
    zckevin
        28
    zckevin  
       2020-11-27 18:33:18 +08:00
    少想多读书
    GeruzoniAnsasu
        29
    GeruzoniAnsasu  
       2020-11-27 18:54:57 +08:00
    香农就是个种花的农民,懂个屁的信息论(
    zxlzy
        30
    zxlzy  
       2020-11-27 19:13:54 +08:00
    @rekulas 这种做法也是不可行的。数字的长度很可能长于原始数据
    vindurriel
        31
    vindurriel  
       2020-11-27 19:45:43 +08:00 via iPhone
    楼主这个问题本身挺好的 不连续的数据当然也可以压缩 可以查下 柯氏复杂性 和 霍夫曼编码 但是纯随机数据的压缩极限 shannon 在数学上已经证明了 目前还没有传输算法达到这个极限 甚至没有接近 因为还要容错
    liukangxu
        32
    liukangxu  
       2020-11-27 20:51:00 +08:00
    香农的棺材板压不住了( doge
    rekulas
        33
    rekulas  
       2020-11-28 09:42:40 +08:00
    @zxlzy 看好我设置的前提,0 开始的位置,所以数据长度一定远小于数字的,差了 N 个数量级
    理论上一定可行的,前提是有足够“强大的超算和足够的时间”
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1068 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 19:41 · PVG 03:41 · LAX 12:41 · JFK 15:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.