压缩Base62(0-9a-zA-Z)编码字符串

Question

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

谢谢!

Answer 1

看Pigeonhole principle -如果你试着把100只鸽子放进10个洞里，有些洞里会有多只鸽子。同样，对于您的问题，必须出现两个字符串压缩为同一个字符串的情况。在这些情况下，您将不知道将压缩的字符串解压缩为哪个字符串。

因此，对于所有可能的输入，您不能以相同的编码将20个字符losslessly压缩为16个字符(甚至20到19个字符)。

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

如果您有这样的特征(或者如果您想转换为具有足够空间的不同编码)，您可以很容易地将任何编码的字符串转换为唯一的数字，然后将该数字转换为不同编码的字符串。要做到这一点，方法是：

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

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

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

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

• 将合计设置为合计除以当前位置的允许值的数量(向下舍入)的结果。
• 将当前位置设置为与上述除法的剩余部分相对应的字符。

在上述任何一种情况下，从左到右或从右到左都无关紧要，只要选择一种方式并坚持下去即可。

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

请注意，以上仅用于某些位置具有固定值的情况，虽然您可以在某种程度上将其扩展为适用于其他编码(例如字符串中最多有1个数字)，但这会变得有点复杂。

示例：

输入格式：1大写字母(A-Z)，然后是2位数字(0-9)

输出格式：1个小写字母( a-z)，然后2个大写/小写字母(A-Z或a-z)

输入： "Z35“

编号： 10*(10*(26*0 + 25) + 3) +5= 2535

Explanation:我们从"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，因此第3个字符= "B“

输出： "ntB“

输入格式最大取值： 10*(10*(26*0 + 25) + 9) +9= 2599

输出格式的最大可能值： 52*(52*(26*0 + 25) + 51) + 51 = 70303

可以转换吗？可以，因为70303 >= 2599.