我必须为查询字符串创建一个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个值会返回...
那么如何解释呢?如果您有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] 删除。
我来说两句