如何将base13字符串转换为base64

悉达思(Siddharth Agrawal)

我必须为查询字符串创建一个URL缩短器。花了几天时间尝试将数组数据压缩为base64字符串。认为最好的方法可能是将诸如[[1,2,9,3],[1,0,2],[39,4]]之类的东西解释为以数字0-9和[]为符号的base13 。

当前算法的工作原理:将字符串化数组转换为base13数组,其中每个元素表示1个唯一字符,将此数组转换为base10数字,将此数字转换为base 64字符串。

但是问题是当将base13数组转换为base10数字时,它使5.304781188371057e + 86之类的大数字无法保存在js中。

我当然可以选择其他解决方案,但是请不要建议创建URL数据库之类的东西,因为它最多只能支持51个!* 51!唯一的URL,最好仅制作一个紧凑的可编码和可解码查询字符串,并在访问网站后立即对其进行解码。

//convert stringified array to array of base13(each element = each digit of base13 number)
function stringToArray(string)
{
    let charSet = "[],1234567890";
    let array = [];
    for(let i = 0; i < string.length; i++)
    {
        array.push(charSet.indexOf(string[i]));
    }
    return array;
}

//convert base13 array to one large decimal number
function arrayToDecimal(array, base)
{
    var decimal = 0;
    for(let i = 0; i < array.length; i++)
    {
        decimal += array[i] * Math.pow(base, i)
    }
    return decimal;
}

//convert decimal number back to array
function decimalToArray(decimal, base)
{
    var quotient = decimal;
    var remainder = [];
    while(quotient > base)
    {
        remainder.push(quotient % base)
        quotient = Math.floor(quotient / base);
    }
    remainder.push(quotient % base)
    return remainder;
}

const alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';

// binary to string lookup table
const b2s = alphabet.split('');

// string to binary lookup table
// 123 == 'z'.charCodeAt(0) + 1
const s2b = new Array(123);
for(let i = 0; i < alphabet.length; i++)
{
    s2b[alphabet.charCodeAt(i)] = i;
}

// number to base64
const ntob = (number) =>
{
    if(number < 0) return `-${ntob(-number)}`;

    let lo = number >>> 0;
    let hi = (number / 4294967296) >>> 0;

    let right = '';
    while(hi > 0)
    {
        right = b2s[0x3f & lo] + right;
        lo >>>= 6;
        lo |= (0x3f & hi) << 26;
        hi >>>= 6;
    }

    let left = '';
    do {
        left = b2s[0x3f & lo] + left;
        lo >>>= 6;
    } while(lo > 0);

    return left + right;
};

// base64 to number
const bton = (base64) =>
{
    let number = 0;
    const sign = base64.charAt(0) === '-' ? 1 : 0;

    for(let i = sign; i < base64.length; i++)
    {
        number = number * 64 + s2b[base64.charCodeAt(i)];
    }

    return sign ? -number : number;
};



console.log(decimalToArray(bton(ntob(arrayToDecimal([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 13))), 13)) 
//encoded and decoded, works output:[1,1,1,1,1,1,1,1,1,1,1,1,1]
console.log(arrayToDecimal([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 13)) 
//encoding doesnt work, array to decimal converts to 5.304781188371057e+86```
特伦托

一个有趣的问题...您需要评估的第一件事是您要寻找的基本转换压缩是否值得。即,要表示n以13为底的字符需要多少个以64为底的字符?这涉及解决...

13 ** n = 64 ** x

求解x,我们得到...

 x = n * log(13) / log(64)

即,对于基数13的每n个数字,需要多少个基数64。采样n个值会返回...

  • n = 6,x = 3.70
  • n = 7,x = 4.31
  • n = 8,x = 4.93
  • n = 9,x = 5.55
  • n = 10,x = 6.17
  • n = 11,x = 6.78
  • n = 12,x = 7.40
  • n = 13,x = 8.01
  • n = 14,x = 8.63
  • n = 15,x = 9.25
  • n = 16,x = 9.86

那么如何解释呢?如果您有10位以13为底的数字,那么您将需要7位以64为底的数字(四舍五入为6.17)。因此,最好的比率是x等于或小于整数时。因此,基数13的8位数字需要基数64的5位数字,实现5/8或62.5%压缩率的最佳情况。

假设这足以满足您的要求,那么以下函数会将“ base13”字符串转换为base 64。

const base13Chars = "0123456789[],";
const base64Chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_';  
// see https://en.wikipedia.org/wiki/Query_string for URL parameter allowable characters.

function base13toBase64(x13) {

    base13 = x13.split("").map( c => base13Chars.indexOf(c) );

    // Make the array an even multiple of 8
    for (i = base13.length; i % 8 !==0; i++) {
        base13[i] = 0;
    }

    x64 = "";
    for (i = 0; i < base13.length; i += 8) {
        // Calculate base13 value of the next 8 characters.
        let n = 0;
        for (j = 0; j < 8; j++) {
            n = n * 13 + base13[i + j];
        }
        // Now calculate the base64 of n.
        for (j = 0; j < 5; j++) {
            x64 = x64 + base64Chars.substr(n % 64,1);
            n = Math.floor(n / 64);
        }   
    }

    return x64;
}

运行上面的...

 base13toBase64( "[[1,2,9,3],[1,0,2],[39,4]]" ) returns "ilYKerYlgEJ4PxAAjaJi"

请注意,原始值是26个字符的长度,而base64值是20个字符,因此压缩率是77%,不是最佳的62.5%。这是因为填充使原始数组达到32个字符,是8的偶数倍,但是,要编码的字符串越长,该比率就越接近62.5%。

然后,在服务器端,您将需要上面的常量以及以下函数来将base64“解压缩”为base13字符串化的URL ...

function base64toBase13(x64) {

    base64 = x64.split("").map( c => base64Chars.indexOf(c) );

    x13 = "";
    for (i = 0; i < base64.length; i += 5) {
        // Calculate base64 value of the next 5 characters.
        let n = 0;
        for (j = 5 - 1; 0 <= j; j--) {
            n = n * 64 + base64[i + j];
        }
        // Now calculate the base13 of n.
        let x = "";
        for (j = 0; j < 8; j++) {
            x = base13Chars.substr(n % 13,1) + x;
            n = Math.floor(n / 13);
        }
        x13 = x13 + x;
    }

    // Removed the trailing 0's as a result of the buffering in
    // base13toBase64 to make the array an even multiple of 8.
    while (x13.substr(-1,1) === "0") {
        x13 = x13.substr(0, x13.length - 1);
    }

    return x13;
}

运行上面的...

 base64toBase13 ( "ilYKerYlgEJ4PxAAjaJi" ) returns "[[1,2,9,3],[1,0,2],[39,4]]"

希望这可以帮助...

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章