2

我需要将长度为 20 个字符的 base62 (0-9a-zA-Z) 编码字符串压缩为 15-16 个字符的字符串，以便将一些其他信息挤进去。棘手的部分是压缩输出也应该是 base62编码。这可以做到吗？非常感谢任何建议。

谢谢！

4

1 回答 1

3

参见鸽洞原理——如果你尝试将 100 只鸽子放入 10 个洞中，有些洞会有多只鸽子。同样，对于您的问题，必须出现两个字符串压缩为同一个字符串。在这些情况下，您将不知道将压缩字符串解压缩到哪个字符串。

所以不，对于所有可能的输入，您不能以相同的编码将 20 个字符无损压缩为 16 个字符（甚至 20 到 19 个字符）。

如果输入具有一些定义特征，例如唯一的大写字符将是第一个字符，最后 3 个字符是数字出现的位置等，那么它会更加可压缩并且可能是可能的。

如果您有这样的特征（或者如果您想转换为具有足够空间的不同编码），您可以轻松地将任何编码的字符串转换为唯一数字，然后将该数字转换为不同编码的字符串。这样做的方法是：

  • 对于每个字符位置，从 0 开始为该位置允许的每个可能字符分配一个数字。

    因此，如果在第一个位置允许“A”到“Z”和“a”到“z”，您可以将 0-25 分配给“A”到“Z”，将 26-51 分配给“a”到“z” . 因此，例如，“B”将为 1。

  • 遍历字符串，将总数乘以当前位置的允许值数，然后将分配给该位置字符的数字加到总数中。

要获得不同的编码，只需重复：

  • 将总计设置为将总计除以当前位置的允许值数的结果（向下舍入）。
  • 将当前位置设置为上述除法余数对应的字符。

以上任何一种情况，从左到右或从右到左都没有关系，只要选择一种方式并坚持下去。

您还可以通过计算每种编码的最大可能值（通过为每个字符取最大值）轻松确定这种转换是否可行 - 如果目标具有较小的最大可能值，则无法进行转换。

请注意，上述内容仅适用于某些位置具有固定值的情况，尽管您可以在某种程度上将其扩展为适用于其他编码（例如字符串中最多有 1 个数字），但这会变得更复杂一些。

例子：

输入格式： 1 个大写字母 (AZ)，然后是 2 个数字 (0-9)
输出格式： 1 个小写字母 (az)，然后是 2 个大写/小写字母（AZ 或 az）
输入： “Z35”
数字： 10*( 10*(26*0 + 25) + 3) + 5 = 2535
解释：我们以“Z”开头，总为0开始，乘以大写字母的个数（26）再加上“Z” (25)。然后我们继续“3”，我们将这个总数乘以位数（10）并添加“3”的值（3），依此类推。
输出计算：
2535 / 26 = 97
2535 % 26 = 13，所以第一个字符 = “n”（13+1 = 字母表的第 14 个字母）
97 / 52 = 1
97 % 52 = 45，所以第二个字符 = “t”（45-26+1 = 字母表的第 20 个字母）
1 % 52 = 1，所以第三个字符 = “B”
输出： “ntB”

输入格式的最大可能值： 10*(10*(26*0 + 25) + 9) + 9 = 2599
输出格式的最大可能值： 52*(52*(26*0 + 25) + 51) + 51 = 70303
可以转换吗？是的，因为 70303 >= 2599。

于 2013-07-16T13:27:53.037 回答