如何将base13字符串转成base64

Question

我必须为查询字符串创建一个 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!独特的 URLs，最好只制作一个紧凑的可编码和可解码查询字符串，并在访问网站后立即对其进行解码。

//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```

Answer 1

我建议您直接将 Base13 字符串编码为 Base64。尽管这可能不会产生比您的解决方案更好的压缩效果，但它可以消除您正在执行的繁重的乘法运算。此外，如何保证通过 arrayToDecimal 转换时不会发生冲突？

Answer 2

一个有趣的问题...您需要评估的第一件事是您正在寻求的基本转换压缩是否值得。即，需要多少个 base 64 字符来表示 base 13 的 n 个字符？这涉及解决...

13 ** n = 64 ** x

求解 x，我们得到...

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

即每n位13进制，需要多少位64进制。 n returns...

的几个值的采样

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

那么如何解读呢？如果你有 13 位的 10 位数字，你将需要 64 位的 7 位数字（6.17 四舍五入）。所以最好的比率是 x 等于或小于整数。所以，8位13进制需要5位64进制，达到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%。

然后，在服务器端你需要上面的常量加上下面的函数"uncompress" 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]]"

希望这对您有所帮助...

Answer 3

最好的压缩是当你可以把东西放在外面的时候。

假设您的数据结构是 Array<Array<int>> 由一个示例给出的，我们可以忽略几乎所有对数据本身没有贡献的内容。

我不是在压缩字符串，而是数据本身需要 1 个 b64Character / 5 位来表示一个数字。至于结构，我们只存储子数组的数量和它们各自的长度；所以你的数据中每个数组或多或少有一个额外的字符。

归结为：

function encode(data) {
  const alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';
  let str = "";

  function encode(nr, hasMoreDigits) {
    if (nr > 31) {
      // I need more bits/characters to encode this number.
      //encode the more significant bits with the 0b100000 flag
      encode(nr >>> 5, 32);
    }

    // 0b011111 payload | 0b100000 flag
    const index = nr & 31 | hasMoreDigits;
    str += alphabet[index];
  }

  encode(data.length);
  data.forEach(arr => {
    encode(arr.length);
    arr.forEach(v => encode(v >>> 0 /* int32 -> uint32 */));
  });

  return str;
}

function decode(str) {
  const alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';
  let i = 0;

  function parse() {
    let nr = 0, 
      hasMoreDigits;
    do {
      const index = alphabet.indexOf(str.charAt(i++));
      nr = nr << 5 | index & 31; // 0b011111 payload
      hasMoreDigits = index & 32; // 0b100000 flag
    } while (hasMoreDigits);

    return nr; // int32 due to the bit operations above
  }

  let data = Array(parse());
  for (let j = 0; j < data.length; ++j) {
    let arr = data[j] = Array(parse());
    for (let k = 0; k < arr.length; ++k) {
      arr[k] = parse();
    }
  }
  return data;
}

let data = [
  [1, 2, 9, 3],
  [1, 0, 2],
  [39, 4]
];

let text = encode(data);
let data2 = decode(text);

console.log("input:", data);
console.log("encoded:", text, "length:", text.length);
console.log("output:", data2);
console.log("equal:", JSON.stringify(data) === JSON.stringify(data2));

.as-console-wrapper{top:0;max-height:100%!important}

数字的编码。理想情况下，您会将数字编码为具有静态大小的二进制，但这意味着 32 位/整数，即 6 个字符/数字，所以多字节。

我们将数字分成 'n' 位的块，忽略前导零并对其余部分进行编码。理想情况下，我们可以用很少的字符编码小数字，缺点：如果 n 太小并且平均数字很大，我们会丢失 1 位/块。这是一种权衡；这就是我保留此可配置项的原因。

当前格式为6位/数字。 1 位用于结构，5 位作为有效载荷。格式为 (1.....)*0.....

如何将base13字符串转成base64

How to convert base13 string to base64

javascript

arrays

base