logo标签列表

用于生成可逆唯一（固定）代码的算法，适用于字符串

algorithmurl-shortener
12

需求:

我们在数据库中有如下数值

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

我想把这些字符串转换成唯一的短字符串。例如：

Chennai –> xy67kr

San Jose –> iuj73d

基本上就像URL缩短器一样。

而且将其转换的算法应该是可逆的...即当我把"xy67kr"传递给解码函数时，它应该返回"Chennai"。

期待帮助。

这些字符串需要固定长度吗？ - Chetter Hummin
1
如果您有一个数据库，那么撤销处理应该非常容易... - Oliver Charlesworth
5
由于鸽笼原理（pigeonhole principle）的缘故，没有一种函数可以将任意字符串缩短并可逆转。除非你能对输入字符串的值施加严格的限制，否则你必须使用某种查找机制。 - Oliver Charlesworth
4
我不明白...你在数据库中有这个东西，但你不想使用数据库？ - Karoly Horvath
1
@taher: 但是这个算法并不存在... - Oliver Charlesworth
显示剩余5条评论
4个回答
5
正如其他帖子所述，你不能有一个能够缩短任意字符串的函数，这在数学上是不可能的。但你可以创建一个自定义函数，以适应特定字符串集合的需求。
一个例子是计算字符频率，然后使用 前缀编码 对字符进行编码，使得出现频率最高的字母使用短前缀进行编码（即 Huffman 编码）。
上述方法并没有利用到自然语言中下一个字符可以从前面的字符中准确预测出来的事实，因此你可以扩展上述算法，不是独立地编码每个字符，而是对 n-gram 中的下一个字符进行编码。当然，这需要比简单方法更大的压缩表，因为你实际上正在根据前缀使用单独的代码。例如，如果 'e' 在 'th' 后面非常频繁，则 'th' 后面的 'e' 将使用非常短的前缀进行编码。如果 'e' 在 'ee' 后面非常罕见，则在这种情况下可以使用非常长的前缀进行编码。解码算法显然需要查看当前解压缩的前缀以检查如何解码下一个字符。
这种普遍的方法假定频率不会改变，或者至少变化缓慢。如果您的数据集发生更改，则可能需要重新计算统计信息并重新编码字符串。
我怀疑这对于短输入数据的效果不佳。此外，似乎OP想要一种固定长度编码，这显然是不可能的。 - Oliver Charlesworth
相反，即使是单个字符字符串，这种统计编码也能很好地工作，除了一个事实，即使结果代码是6位，您仍然必须发送（或保存）至少一个字节。我同意固定长度编码是不可能的。 - Rafał Dowgird
好的，在我的原始问题中，我问到我的输入字符串可以是可变长度的。那么，假设我通过应用填充使它们具有固定长度，即 --> 纽约 [变成] --> 纽约!@!!@! 或类似的东西。然后编码后缩短它们是否可能？ - Taher
@taher Oli 是指编码后字符串的长度。鸽巢原理表明，保证最终字符串固定的唯一方法是限制输入字符串集合（使其大小不大于固定长度字符串的数量）。对于任意集合，唯一实用的方法是使用数据库，就像 URL 缩短服务一样。如果没有数据库，你能做的最好的事情就是使用针对你的数据调整过的压缩算法。这可以实现非常好的压缩 - 但输出没有固定的大小。 - Rafał Dowgird
谢谢大家，我有点明白了我的问题的答案。 - Taher
4

请参考我对类似问题的回答（点击此处），并将其转换为PHP：

编码：

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

解码：

$decoded = gzinflate(base64_decode($encoded))

请注意，对于短字符串，gzdeflate的性能优于gzcompress。
但是，这种方法的问题在于对于短字符串来说，它会使字符串变长。这种方法在处理较长文本时表现更好。当然，最好使用一些具有先验信息的压缩算法，例如带有初始后缀树的ppm或后缀方法...那么它也可以完美地处理短字符串。
当然最好使用一些带有先验信息的压缩算法，比如带有初始后缀树的ppm或后缀方法……这样它也可以在短字符串上完美运行。但问题是这些方法是否在PHP中可用。 - Tomas
3
1
这并不一定是确定性的，但显然您可以使用查找表。该服务类似于goo.gl或imgur。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接