2

我们如何将 20 个字母的字符串压缩/编码为 6 个字母。我发现很少有算法解决数据压缩问题,如 RLE、算术编码、通用代码,但它们都不能保证 6 个字母。

原始字符串可以包含字符 AZ(大写)、0-9 和破折号。

4

1 回答 1

6

如果您的目标是将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。它列出了许多算法供您选择。祝你好运!

于 2013-12-24T20:02:45.773 回答