V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
maemolee
V2EX  ›  问与答

[请教]一个长度为 15 位的字符串,怎么压缩它的长度?

  •  
  •   maemolee · 2018-09-28 13:39:51 +08:00 · 8492 次点击
    这是一个创建于 2249 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一个长度为 15 位的字符串,可能包含大写、小写英文字母和数字(不包含特殊符号),想要通过一个算法压缩成一个 8 位的字符串,并能通过算法将压缩后的字符串正确还原。

    第 1 条附言  ·  2018-09-28 14:55:28 +08:00
    我打算放弃了,大家要是有想法可以继续提出讨论,潜了,谢谢大家。
    26 条回复    2018-09-29 03:19:08 +08:00
    SakuraSa
        1
    SakuraSa  
       2018-09-28 13:46:11 +08:00
    如果没有更强的假设,应该是做不到的。
    可能的组合:(26+26+10)**15
    需要的字符数:log((26+26+10)**15,256)=11.164
    maemolee
        2
    maemolee  
    OP
       2018-09-28 13:53:43 +08:00
    @SakuraSa 谢谢……
    xiaocsl
        3
    xiaocsl  
       2018-09-28 13:59:50 +08:00
    压缩后的也只能大小写英文字母和数字吗?
    只是可视的压缩还是要体积压缩?
    maemolee
        4
    maemolee  
    OP
       2018-09-28 14:05:20 +08:00
    @xiaocsl 因为压缩后的文本串要保证能以 64 位 2 进制码的形式储存,所以最好只能是 ASCII 表里面的东西。
    JmmBite
        5
    JmmBite  
       2018-09-28 14:07:00 +08:00
    改成 中文字符。
    stevenbipt
        6
    stevenbipt  
       2018-09-28 14:22:24 +08:00 via Android
    哈夫曼树重新编码?将每个 ASCII 码重新编码应该能压缩一下吧
    maemolee
        7
    maemolee  
    OP
       2018-09-28 14:41:03 +08:00   ❤️ 1
    @JmmBite 怎么改用中文?

    @stevenbipt 诶?你是说直接跳过转换为 8 位字符串的过程,直接用 15 位转换成 64 位二进制吗🤔难以想象啊
    ThirdFlame
        8
    ThirdFlame  
       2018-09-28 14:41:15 +08:00
    26+26+10=62 2 的 6 次方即可容纳。
    15 个字符*6=90 位二进制即可。

    1 楼的解释已经完美了,不可能实现的任务。
    chenyu8674
        9
    chenyu8674  
       2018-09-28 14:45:53 +08:00
    找 124 个不重样的字符,用进制转换的思路试试
    chenyu8674
        10
    chenyu8674  
       2018-09-28 14:47:23 +08:00
    @chenyu8674 脑抽想错,是 2^6
    maemolee
        11
    maemolee  
    OP
       2018-09-28 14:53:42 +08:00
    @ThirdFlame 感谢

    @chenyu8674 这样子是不是得自己定义一套编码规范😂
    chenyu8674
        12
    chenyu8674  
       2018-09-28 15:05:03 +08:00
    @maemolee 差不多是这个意思,比如 1111->F,就相当于把 4 位压到了 1 位
    不过我刚脑抽了,实际应该找不出那么多不同的字符
    blackcurrant
        13
    blackcurrant  
       2018-09-28 15:12:05 +08:00 via iPhone
    构造一个 url, 让这个字符串成为 URL 的一部分,然后使用短网址服务进行缩短,可压缩成 5 个字符甚至更短。
    sxul07
        14
    sxul07  
       2018-09-28 15:15:38 +08:00
    @blackcurrant 但还是不能保证全都压缩到 8 位以内
    catcn
        15
    catcn  
       2018-09-28 15:16:18 +08:00
    catcn
        16
    catcn  
       2018-09-28 15:17:03 +08:00
    汗,还有压缩后的位数要求。。
    blackcurrant
        17
    blackcurrant  
       2018-09-28 15:21:29 +08:00 via iPhone
    @sxul07 楼主的标题是 **一个**长度为 15 位的字符串。
    csx163
        18
    csx163  
       2018-09-28 15:22:38 +08:00
    可以用字典么
    maemolee
        19
    maemolee  
    OP
       2018-09-28 18:28:03 +08:00
    @blackcurrant 希望可以不要扣字眼,因为我有很多很多“一个”😂
    maemolee
        20
    maemolee  
    OP
       2018-09-28 18:28:40 +08:00
    @csx163 当然可以……
    shuax
        21
    shuax  
       2018-09-28 19:24:49 +08:00
    可以压缩到 12 位
    prolic
        22
    prolic  
       2018-09-28 19:46:16 +08:00 via Android
    两个集合大小不一样,15 位到 8 位只能做个满射
    NB40B938mff85mtq
        23
    NB40B938mff85mtq  
       2018-09-28 20:21:04 +08:00
    不用想了。。。遍历赋值给二进制数都凑不够。。。
    zealic
        24
    zealic  
       2018-09-28 20:48:17 +08:00
    只能用已知字典代替缺失的 3.1164 位
    mangoDB
        25
    mangoDB  
       2018-09-28 20:56:01 +08:00
    ```py
    import math

    s = (26 + 26 + 10) ** 15
    n = math.log(s, 2 ** 8)

    print n
    ```
    xychang
        26
    xychang  
       2018-09-29 03:19:08 +08:00
    随机的 15 位字符串不可能,如果个别字符频率比较高的话还是有可能的,参见 6 楼
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1137 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 18:18 · PVG 02:18 · LAX 10:18 · JFK 13:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.