string - 收缩字符串编码算法

Question

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

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

Answer 1

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