为应该可逆的字符串生成唯一(恒定)代码的算法

Question

要求:

我们在数据库中有值

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

等...

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

Chennai –> xy67kr

San Jose –> iuj73d

基本上类似于 URL 缩短器。

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

期待您的帮助。

Answer 1

正如其他发帖人所说，您不能拥有缩短任意字符串的函数，这在数学上是不可能的。但是您可以创建一个自定义函数来很好地处理您的特定字符串集。

一个示例方法是计算集合中的字符频率，然后只用 prefix code 编码字符这样最常见的字母用短前缀编码(即 Huffman coding 。)

上面的方法没有利用自然语言中下一个字符可以从前面的字符中非常准确地预测出来的事实，所以你可以扩展上面的算法，而不是独立地编码字符，而是编码下一个字符在 n-gram 中。这当然需要比简单方法更大的压缩表，因为您实际上根据前缀有一个单独的代码。例如，如果“e”在“th”之后非常频繁，那么“th”之后的“e”将使用非常短的前缀进行编码。如果'e'在'ee'之后很少见，那么在这种情况下可以用很长的前缀对其进行编码。解码算法显然需要查看当前解压缩的前缀以检查如何解码下一个字符。

这种通用方法假设频率不变，或者至少变化缓慢。如果您的数据集发生变化，您可能需要重新计算统计数据并重新编码字符串。