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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2266 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

第 1 条附言 · 2018-09-28 14:55:28 +08:00

我打算放弃了，大家要是有想法可以继续提出讨论，潜了，谢谢大家。

字符

压缩

长度

算法

26 条回复 • 2018-09-29 03:19:08 +08:00

SakuraSa

2018-09-28 13:46:11 +08:00

如果没有更强的假设，应该是做不到的。
可能的组合：(26+26+10)**15
需要的字符数：log((26+26+10)**15,256)=11.164

maemolee

2018-09-28 13:53:43 +08:00

@SakuraSa 谢谢……

xiaocsl

2018-09-28 13:59:50 +08:00

压缩后的也只能大小写英文字母和数字吗?
只是可视的压缩还是要体积压缩?

maemolee

2018-09-28 14:05:20 +08:00

@xiaocsl 因为压缩后的文本串要保证能以 64 位 2 进制码的形式储存，所以最好只能是 ASCII 表里面的东西。

JmmBite

2018-09-28 14:07:00 +08:00

改成中文字符。

stevenbipt

2018-09-28 14:22:24 +08:00 via Android

哈夫曼树重新编码？将每个 ASCII 码重新编码应该能压缩一下吧

maemolee

2018-09-28 14:41:03 +08:00

@JmmBite 怎么改用中文？

@stevenbipt 诶？你是说直接跳过转换为 8 位字符串的过程，直接用 15 位转换成 64 位二进制吗🤔难以想象啊

ThirdFlame

2018-09-28 14:41:15 +08:00

26+26+10=62 2 的 6 次方即可容纳。
15 个字符*6=90 位二进制即可。

1 楼的解释已经完美了，不可能实现的任务。

chenyu8674

2018-09-28 14:45:53 +08:00

找 124 个不重样的字符，用进制转换的思路试试

chenyu8674

2018-09-28 14:47:23 +08:00

@chenyu8674 脑抽想错，是 2^6

maemolee

2018-09-28 14:53:42 +08:00

@ThirdFlame 感谢

@chenyu8674 这样子是不是得自己定义一套编码规范😂

chenyu8674

2018-09-28 15:05:03 +08:00

@maemolee 差不多是这个意思，比如 1111->F，就相当于把 4 位压到了 1 位
不过我刚脑抽了，实际应该找不出那么多不同的字符

blackcurrant

2018-09-28 15:12:05 +08:00 via iPhone

构造一个 url, 让这个字符串成为 URL 的一部分，然后使用短网址服务进行缩短，可压缩成 5 个字符甚至更短。

sxul07

2018-09-28 15:15:38 +08:00

@blackcurrant 但还是不能保证全都压缩到 8 位以内

catcn

2018-09-28 15:16:18 +08:00

试一试这个压缩算法： http://rosettacode.org/wiki/LZW_compression#Python

catcn

2018-09-28 15:17:03 +08:00

汗，还有压缩后的位数要求。。

blackcurrant

2018-09-28 15:21:29 +08:00 via iPhone

@sxul07 楼主的标题是 **一个**长度为 15 位的字符串。

csx163

2018-09-28 15:22:38 +08:00

可以用字典么

maemolee

2018-09-28 18:28:03 +08:00

@blackcurrant 希望可以不要扣字眼，因为我有很多很多“一个”😂

maemolee

2018-09-28 18:28:40 +08:00

@csx163 当然可以……

shuax

2018-09-28 19:24:49 +08:00

可以压缩到 12 位

prolic

2018-09-28 19:46:16 +08:00 via Android

两个集合大小不一样，15 位到 8 位只能做个满射

NB40B938mff85mtq

2018-09-28 20:21:04 +08:00

不用想了。。。遍历赋值给二进制数都凑不够。。。

zealic

2018-09-28 20:48:17 +08:00

只能用已知字典代替缺失的 3.1164 位

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

2018-09-29 03:19:08 +08:00

随机的 15 位字符串不可能，如果个别字符频率比较高的话还是有可能的，参见 6 楼