我们如何将 20 个字母的字符串压缩/编码为 6 个字母。我发现很少有算法解决数据压缩问题,如 RLE、算术编码、通用代码,但它们都不能保证 6 个字母。
原始字符串可以包含字符 AZ(大写)、0-9 和破折号。
如果您的目标是将20 个字符的随机输入字符串(每个字符可以是 [AZ]、[0-9] 或 -)无损压缩或散列为 6 个字符的输出字符串。理论上是不可能的。
在信息论中,给定一个离散随机变量X={x|x1,...,xn}
,香农熵 H(X)
定义为:
p(xi)
的概率在哪里X = xi
。在你的情况下,X
有 37 个可能的字符中的 20 个,所以它可能是{x|x1,...,xn}
where n = 37^20
。假设这 37 个字符的存在概率相同(也就是输入字符串是随机的),那么p(xi) = 1/37^20
. 所以输入的香农熵为:
. 一char
台普通的计算机可以容纳 8 位,因此 6 个字符可以容纳 48 位。没有办法用 6 个字符来保存 104 位信息。您需要至少 15 个字符来保存它。
如果您确实允许丢失并且必须将 20 个字符散列为 6 个字符,那么您正在尝试将37^20
值散列到128^6
键。可以做到,但你会遇到很多哈希冲突。
在您的情况下,假设您以最均匀的方式对它们进行散列(否则会更糟),对于每个输入值,平均会有 5.26 个其他输入值与其共享相同的散列键。通过生日攻击,我们可以预期在大约 2 亿次试验中发现碰撞。一台普通的笔记本电脑可以在不到 10 秒的时间内完成。所以我认为这不是一个安全的散列。
但是,如果您坚持这样做,您可能需要阅读Hash function algorithms。它列出了许多算法供您选择。祝你好运!