算法挑战:无损字符串压缩的任意就地基本转换

Question

从真实世界的例子开始可能会有所帮助.假设我正在编写一个由MongoDB支持的Web应用程序,因此我的记录有一个长的十六进制主键,使我的url可以查看记录/widget/55c460d8e2d6e59da89d08d0.这似乎过长了.网址可以使用更多字符.虽然24位十六进制数字中只有under 8 x 10^28(16^24)可能的值,但仅限于由[a-zA-Z0-9]正则表达式类匹配的字符(YouTube视频ID使用更多),62个字符,您8 x 10^28只能以17个字符过去.

我想要一种算法,它将任何限制为特定字符字符串的字符串转换为具有另一个字符字符串的任何其他字符串,其中每个字符的值c可以被认为是alphabet.indexOf(c).

形式的东西:

convert(value, sourceAlphabet, destinationAlphabet)

假设

• 所有参数都是字符串
• 每个角色都value存在于sourceAlphabet
• 在每一个字符sourceAlphabet,并destinationAlphabet是唯一

最简单的例子

var hex = "0123456789abcdef";
var base10 = "0123456789";
var result = convert("12245589", base10, hex); // result is "bada55";

但我也希望它能够将War&Peace从俄语字母加上一些标点符号转换为整个unicode charset并再次无损地返回.

这可能吗？

我曾经被教过在Comp Sci 101中进行基本转换的唯一方法是首先通过求和转换为十进制整数digit * base^position,然后反向转换为目标基数.这种方法不足以转换很长的字符串,因为整数变得太大.

这当然感觉直观,一个基本转换可能要做到位,当你通过串(可能向后,保持标准显著位顺序)步骤,跟踪余莫名其妙,但我没有足够的智慧来解决如何.

这就是你进来的地方,StackOverflow.你够聪明吗？

也许这是一个已解决的问题,由一些18世纪的数学家在纸上完成,1970年在LISP中实施了打卡,以及Cryptography 101中的第一个家庭作业,但我的搜索没有结果.

我更喜欢具有功能风格的javascript解决方案,但任何语言或风格都可以,只要你没有欺骗一些大整数库.当然,奖励点可以提高效率.

请不要批评原来的例子.解决问题的一般书呆子信誉比解决方案的任何应用更重要.

Answer 1

我认为任何解决方案都不能正常工作，因为如果 n ^{e != m 对于某些整数 e 和某些 MAX_INT ，因为如果 n p} > MAX_INT ，则无法计算某个位置 p 的目标基数的值。

^{对于某些 e 的 n e} == m的情况，您可以摆脱这种情况，因为该问题是递归可行的（n 的前 e 数字可以求和并转换为 M 的第一个数字，然后截断并重复。

如果你没有这个有用的属性，那么最终你将不得不尝试获取原始基数的一部分并尝试在 n ^p中执行模数，并且 n ^p将大于 MAX_INT，这意味着它是不可能的。