问题用于为字符串生成唯一（常量）代码的算法，该代码应该是可逆的

要求：

我们在DB中有值

Chennai
Baroda
Bangalore
New Delhi
São Paulo, Lisboa
San Jose

等等...

所以我想将这些字符串转换为唯一的短字符串。例如

Chennai –> xy67kr

San Jose –> iuj73d

基本上类似于URL shortner。

并且转换它的算法应该是可逆的。即当我将“xy67kr”传递给解码函数时它应该给我“Chennai”。

期待着寻求帮助。

9706

2018-03-30 08:20

起源

字符串是否需要固定长度？ - Chetter Hummin

如果你有一个数据库，那么逆转的处理应该很容易...... - Oliver Charlesworth

@taher：没有任何函数能够以可逆转的方式缩短任意字符串（由于鸽子原则）。除非您可以对输入字符串的值进行重度约束，否则您将不得不使用某种查找机制。 - Oliver Charlesworth

我不明白......你拥有它在数据库，但你不想使用数据库？ - Karoly Horvath

@taher：但这个算法不存在...... - Oliver Charlesworth

答案:

正如其他海报所述，你不可能有一个缩短任意字符串的功能，这在数学上是不可能的。但是您可以创建一个适合您特定字符串集的自定义函数。

一个示例方法是计算集合中的字符频率，然后用a编码字符前缀代码这样，最常用的字母用短前缀编码（即霍夫曼编码。）

上面的方法没有利用这样的事实：在自然语言中，下一个字符可以从之前的字符中进行相当准确的预测，因此您可以扩展上述算法，以便不是单独编码字符，而是编码n中的下一个字符。 -公克。这当然需要比简单方法更大的压缩表，因为根据前缀，您实际上有一个单独的代码。例如，如果'e'在'th'之后非常频繁，那么'th'之后的'e'用非常短的前缀编码。如果'e'在'ee'之后非常罕见，那么在这种情况下它可以使用非常长的前缀进行编码。解码算法显然需要查看当前解压缩的前缀以检查如何解码下一个字符。

这种一般方法假设频率不会改变，或至少变化缓慢。如果您的数据集发生了更改，则可能需要重新计算统计信息并重新编码字符串。

2018-03-30 13:13

我怀疑这对短输入数据是否有效。 OP似乎也想要一个固定长度的编码，这显然是不可能的。 - Oliver Charlesworth

@OliCharlesworth相反，这种统计编码即使对于单个字符串也能很好地工作，除了这样的事实，即使得到的代码是6位，那么你仍然必须发送（或保存）至少一个字节。我同意固定长度编码是不可能的。 - Rafał Dowgird

好吧，在我原来的问题中，我问我的输入字符串可以是可变长度的。所以，假设我通过应用填充来制作固定长度，即 - >纽约[成为] - >纽约！@ !! @！或类似的东西。是否有可能在编码后缩短它们？ - Taher

@taher Oli指的是字符串的长度后编码。鸽笼原理指出，保证最终字符串是固定的唯一方法是限制输入字符串集（使其大小不大于固定长度字符串的数量。）唯一可行的方法（对于任意集合）就是使用数据库，就像URL缩短程序一样。没有数据库，您可以做的最好的事情就是使用针对您的数据调整的压缩算法。这可以实现非常好的压缩 - 但是没有固定大小的输出。 - Rafał Dowgird

谢谢你们，我得到了答案。 - Taher

看到我的答案类似的问题，只需将其重写为PHP：

编码方式：

$encoded = base64_encode(gzdeflate("São Paulo, Lisboa"))

解码：

$decoded = gzinflate(base64_decode($encoded))

注意 gzdeflate 表现要好于 gzcompress 在短串。

但无论如何，问题在于，对于短字符串，它会使字符串更长。这在较长的文本上表现更好。 当然最好使用一些具有先验信息的压缩算法，如ppm或带有初始后缀树的后缀方法......那么它也可以在短字符串上完美地工作。

2018-03-30 08:39

是的，我认为重点是这对OP没有帮助。 - Oliver Charlesworth

使用一些当然会更好具有先验信息的压缩算法，如ppm或带有初始后缀树的后缀方法......那么它也可以在短字符串上完美地工作。但问题是这些方法是否可以在PHP中访问。 - TMS

我正在使用C＃，而不是PHP :) - Taher

您不能将任意长度的字符串缩短为固定长度的字符串。

你可以做的是创建那些短字符串 唯一身份 数据库中该特定字符串的行。以下是一些提示：如何设计顺序类似哈希的函数。

2018-03-30 08:47

这不一定是确定性的，但显然你可以使用查找表。该服务类似于goo.gl或imgur

2018-03-12 23:38

问题 用于为字符串生成唯一（常量）代码的算法，该代码应该是可逆的

答案:

热门问题

问题用于为字符串生成唯一（常量）代码的算法，该代码应该是可逆的