以 URL 安全方式压缩十六进制 GUID 的算法？

Question

我有一个数据库，其中的行由 32 个字符的十六进制 GUID（存储为二进制）标识。我想知道如何将这些字符串动态压缩成更短但仍对用户友好的表示形式……非常适合在共享 URL 中使用。由于它们是 32 个十六进制字符（目前不区分大小写）...我尝试使用 base64 编码来表示二进制表示。这使它们从 32 个字符变成了 22 个字符，但我不确定是否有更好的东西既常见又简单。

我也在考虑发挥创意，因为现在即使是表情符号在技术上也是 URL 安全的。不过不确定这是否是个好主意。

有没有人考虑过这个问题的跨平台解决方案？仅使用较小的子集完全生成新 ID 是否更好？

Answer 1

查看此 Javascript 实现：

function toDigits(n, b){
    var digits = []
    while(n.isPositive()){
        digits.push(n.remainder(b).valueOf())
        n  = n.quotient(b);
    }
    return digits
}
function fromDigits(digits, b){
    n = BigInteger(0);
    for(var i=0;i<digits.length;i++){
        var d=parseInt(digits[i],b);
        n = n.multiply(b).add(d);
    }
    return n;
}
function changebase(n,from_base,to_base){
    var temp=fromDigits(n,from_base);
    return toDigits(temp,to_base);
}
var unreserved_characters="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~";
var number_of_unreserved_characters=unreserved_characters.length;

var guid="9ec54806c242982ca059661b6db74ab9";
var newbase=changebase(guid,16,number_of_unreserved_characters);
var newurl="";
for(var i=0;i<newbase.length;i++){
    newurl+=unreserved_characters[newbase[i]];
}

我使用了 BigInteger 库 http://silentmatt.com/biginteger/。

此实现将十六进制转换为新的基数，即 URI 中允许的未保留字符数。这可能比 base64 好一点，因为它有 2 个额外的字符，总共 66 个字符，而 base64 中有 64 个字符。但这可能没有太大区别。因此，根据您是否不介意浏览器兼容性，您可以将其他 ascii 字符添加到列表中。

例如使用：

var unreserved_characters="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~ÇüéâäàåçêëèïîìÄÅÉæÆôöòûùÿÖÜø£Ø×ƒáíóúñÑªº¿®¬½¼¡«»░▒▓│┤ÁÂÀ©╣║╗╝¢¥┐└┴┬├─┼ãÃ╚╔╩╦╠═╬¤ðÐÊËÈıÍÎÏ┘┌█▄¦Ì▀ÓßÔÒõÕµþÞÚÛÙýÝ¯´≡±‗¾¶§÷¸°¨·¹³²■";

有更多的字符并且更小的大小，并且可能适用于您的目标浏览器。

Answer 2

您可以在 URI 中使用 0-9、a-z、A-Z 和 !$'()*+,-._~（不包括具有特殊语法解释的字符）。那是74个字符。这比 64 好一点。您可以使用一个简单的方案从您的位流中提取 6 位或 7 位，并将其用于 select 允许的 URI 字符之一。

要编码，请从流中提取六位。如果小于 54，则发出 74 组中对应的字符。如果大于等于 54，则在其底部再拉一位。您现在有一个 108..127 范围内的七位数字。减去 108 并加 54 得到范围 54..73。从集合中发出那个字符。

您现在每个字符的平均位数为 6*54/74 + 7*20/74 = 6.27。或每字节 1.276 个字符。然后，您的 16 字节 ID 将平均编码为 20.4 个字符。实际上要多一点，因为您必须在末尾填充几个零位才能取出最后一个字符。现实世界的平均水平是21.1303，最低19，最高22。

这比尝试使用大整数进行基本转换更快、更简单，并且提供基本相同的性能，21 个字符。

您的 16 字节 ID 是否倾向于具有前导或尾随零，或其他可压缩的模式？如果是这样，那么您可以安排编码方案在这些情况下使用更少的字符。

以 URL 安全方式压缩十六进制 GUID 的算法？

Algorithm for compacting hexadecimal GUID in URL-safe way?

compression

algorithm

hash

hex

guid