将大数字（或字符串）压缩为小值
我的ASP.NET页面有以下查询字符串参数：
…?IDs=1000000012,1000000021,1000000013,1000000022&... 在这种情况下, IDs参数将始终具有由某个东西分隔的数字。 目前有4个数字，但通常它们在3到7之间。
现在，我正在寻找将每个大数字从上面转换为最小可能值的方法; 具体压缩IDs查询字符串参数的值。 压缩每个数字算法或压缩IDs查询字符串参数的整个值都是受欢迎的。
- 编码或解码不是问题; 只压缩值
IDs查询字符串参数。 - 为
IDs创建一些唯一的小值，然后从某些数据源检索其值超出范围。
是否有算法将这些大数字压缩为小值或者将IDs查询字符串参数的值压缩在一起？
您基本上需要这么多空间来存储您的数字，因为您使用基数10代表它们。 改进将是使用基数16（hex）。 因此，例如，您可以将255（3位数）表示为ff（2位数）。
您可以通过使用更大的数字基数来进一步采用该概念…作为有效查询字符串参数的所有字符的集合：
AZ，az，0-9，’。’，’ – ‘，’〜’，’_’，’+’
这为你提供了67个字符的基础（参见Querypedia上的维基百科 ）。
看看这篇SOpost ，了解将基数10转换为任意数字基数的方法。
编辑：
在链接的SOpost中，请看这一部分：
string xx = IntToString(42, new char[] { '0','1','2','3','4','5','6','7','8','9', 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z', 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x'});
这几乎就是你所需要的。 只需添加缺少的几个字符即可扩展它：
yz.-〜_ +
该post缺少一个回到基数10的方法。我不会写它:-)但是程序是这样的：
定义一个我称之为TOTAL的计数器。
查看最右边的字符并找到它在数组中的位置。
TOTAL =（数组中字符的位置）示例：输入为BA1。 TOTAL现在为1（因为“1”在数组中的位置1）
现在查看第一个字符左边的下一个字符，找到它在数组中的位置。 TOTAL + = 47 *（数组中字符的位置）示例：输入为BA1。 TOTAL现在是（47 * 11）+ 1 = 518
现在查看前一个字符左边的下一个字符，找到它在数组中的位置。 TOTAL + = 47 * 47 *（数组中字符的位置）示例：输入为BA1。 总计现在（47 * 47 * 10）+（47 * 11）+ 1 = 243508
等等。
我建议你编写一个unit testing，将一堆基数为10的数字转换为基数47，然后再返回以确保转换代码正常工作。
请注意您如何在基数47的3位数中表示6位数的基数10 🙂
你的号码范围是多少？ 假设它们可以适合16位整数，我会：
- 将所有数字存储为16位整数 （每个数字2个字节，范围-32,768到32,767）
- 构建一个16位整数的字节流（ XDR可能是一个很好的选择;至少，确保正确处理字节顺序 ）
- Base64使用修改后的base64编码对URL进行编码（每个数字的净值约为3个字符）
作为额外的奖励，您不再需要逗号字符，因为您知道每个数字是2个字节。
或者，如果这还不够好，我会使用zlib来压缩整数流，然后使用zlib压缩的流作为base64。 如果16位不是足够大的范围（例如，如果你真的需要1,000,000,000范围内的数字），你也可以切换到32位整数。
编辑：
也许为时已晚，但这里的实现可能会满足您的需求：
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Scratch { class Program { static void Main(string[] args) { //var ids = new[] { 1000000012, 1000000021, 1000000013, 1000000022 }; var rand = new Random(); var ids = new int[rand.Next(20)]; for(var i = 0; i < ids.Length; i++) { ids[i] = rand.Next(); } WriteIds(ids); var s = IdsToString(ids); Console.WriteLine("\nResult string is: {0}", s); var newIds = StringToIds(s); WriteIds(newIds); Console.ReadLine(); } public static void WriteIds(ICollection ids) { Console.Write("\nIDs: "); bool comma = false; foreach(var id in ids) { if(comma) { Console.Write(","); } else { comma = true; } Console.Write(id); } Console.WriteLine(); } public static string IdsToString(ICollection ids) { var allbytes = new List(); foreach(var id in ids) { var bytes = BitConverter.GetBytes(id); allbytes.AddRange(bytes); } var str = Convert.ToBase64String(allbytes.ToArray(), Base64FormattingOptions.None); return str.Replace('+', '-').Replace('/', '_').Replace('=', '.'); } public static ICollection StringToIds(string idstring) { var result = new List (); var str = idstring.Replace('-', '+').Replace('_', '/').Replace('.', '='); var bytes = Convert.FromBase64String(str); for(var i = 0; i < bytes.Length; i += 4) { var id = BitConverter.ToInt32(bytes, i); result.Add(id); } return result; } } }
这是另一个非常简单的方案，它应该为N + deltaforms的一组数字提供良好的压缩，其中N是一个大常数。
public int[] compress(int[] input) { int[] res = input.clone(); Arrays.sort(res); for (int i = 1; i < res.length; i++) { res[i] = res[i] - res[i - 1]; } return res; }
这应该将集合{1000000012,1000000021,1000000013,1000000022}减少到列表[1000000012,1,9,1] ，然后您可以通过表示base47编码中的数字进一步压缩，如另一个答案中所述。
使用简单的十进制编码，从44个字符到16个字符; 即63％。 （并且使用base47将提供更多压缩）。
如果对id进行排序是不可接受的，那么压缩效果就不会那么好。 对于此示例， {1000000012,1000000021,1000000013,1000000022}压缩到列表[1000000012,9,-8,9] 。 对于这个例子，这只是一个字符
无论哪种方式，这都比通用压缩算法或编码方案更好......对于这种输入。
如果唯一的问题是URL长度，您可以将数字转换为base64字符 ，然后将它们转换回服务器端的数字
你得到的身份证有多模糊？ 如果逐位数字，ID是随机的，那么我即将提出的方法将不会非常有效。 但是，如果您作为示例提供的ID代表您将获得的类型，那么以下可能有效吗？
我以身作则激发了这个想法。
例如，您有1000000012作为要压缩的ID。 为什么不把它存储为[{1}，{0,7}，{12}]？ 这意味着第一个数字是1后跟7个零后跟12个。因此，如果我们使用表示x的一个实例的符号{x}，而如果我们使用{x，y}表示x连续y次出现。
你可以用一点模式匹配和/或函数拟合来扩展它。
例如，模式匹配：1000100032将是[{1000,2} {32}]。
例如，函数拟合：如果您的ID是10位数，则将ID拆分为两个5位数字，并存储通过两个点的线的等式。 如果ID = 1000000012，则y1 = 10000，y2 = 12.因此，您的斜率为-9988，截距为10000（假设x1 = 0，x2 = 1）。 在这种情况下，它不是一个改进，但如果数字更随机，它可能是。 同样，您可以使用分段线性函数存储ID序列。
在任何情况下，这主要取决于您的ID的结构。
我假设您正在执行此操作作为请求URL长度限制的解决方法…
其他答案建议用hex，base47或base64编码十进制id号，但你可以（理论上）通过使用LZW（或类似）来压缩id列表做得更好。 根据ID列表中的冗余程度，即使将压缩字节重新编码为文本，也可以显着减少40％以上。
在一个坚果壳中，我建议你找到一个用Javascript实现的现成的文本压缩库，并使用它在客户端压缩ID列表。 然后使用base47 / base64对压缩的字节串进行编码，并将编码的字符串作为URL参数传递。 在服务器端执行相反的操作; 即解码然后解压缩。
编辑：作为一个实验，我创建了一个包含36个不同标识符的列表，例如您提供的标识符，并使用gzip对其进行压缩。 原始文件为396字节，压缩文件为101字节，压缩文件为+ base64文件，为138字节。 这总体上减少了65％。 对于较大的文件，压缩率实际上可以提高。 但是，当我尝试使用一个小输入集（例如只有4个原始标识符）时，我没有压缩，编码后的大小比原始大。
谷歌“lzw库javascript”
理论上，可能有更简单的解决方案。 将参数作为“发布数据”而不是在请求URL中发送，并让浏览器使用它理解的编码之一来应用压缩。 这样可以节省更多成本，因为无需将压缩数据编码为合法的URL字符。
问题是让浏览器压缩请求……并以独立于浏览器的方式执行此操作。