我有一个包含6000个元素的数据结构,对于每个元素,我需要存储7位信息。如果我天真地将其存储为包含数字的6000个元素的数组,则它将占用大约22 KB的空间。我正在尝试减小页面的大小-什么是存储6000 * 7位信息的最佳方法(应为5 KB)。我想要一个像数据结构一样的“比特流”。我考虑过将其编码为字符串甚至图像,但不确定。我之所以不能将其编码为字符串,是因为我无法从数学上保证所有字符都不是不可打印的ASCII字符之一(例如ASCII 1-25)
最佳答案
让我们考虑两个解决方案。
基数32
为了好玩,让我们考虑使用基数为32的数字。是的,您可以使用JavaScript进行操作。
首先将四个7位值打包为一个整数:
function pack(a1,a2,a3,a4){
return ((a1 << 8 | a2) << 8 | a3) << 8 | a4;
}
现在,转换为基数32。
function encode(n){
var str = "000000" + n.toString(32);
str = str.slice(0,6);
return str;
}
那应该不超过六位数。我们确保它恰好是六个。
往另一个方向走:
function decode(s){
return parseInt(s, 32);
}
function unpack(x){
var a1 = x & 0xff0000>>24, a2 = x & 0x00ff0000>>16, a3 = x & 0x0000ff00>>8, a4 = x & 0x000000ff;
return [a1, a2, a3, a4];
}
剩下的就是将逻辑包装起来以处理6000个元素。压缩:
function compress(elts){
var str = '';
for(var i = 0; i < elts.length; i+=4){
str += encode(pack(elts[i], elts[i+1], elts[i+2], elts[i+3])
}
return str;
}
并解压缩:
function uncompress(str){
var elts = [];
for(var i = 0; i < str.length; i+=6){
elts = elts.concat(unpack(decode(str.slice(i, i+6)));
}
return elts;
}
如果将所有6,000个元素的结果连接在一起,将有1,500个压缩数字,每个数字六个字符将变成大约9K。每个7位值大约1.5个字节。这绝不是信息理论上的最大压缩,但是还算不错。
要解码,只需将过程逆转即可:
统一码
首先,我们将两个7位值打包为一个整数:
function pack(a1,a2){
return (a1 << 8 | a2) << 8;
}
我们将对所有6,000个输入执行此操作,然后使用我们的 friend
String.fromCharCode
将所有3,000个值转换为3,000个字符的Unicode字符串:function compress(elts){
var packeds = [];
for (var i = 0; i < elts.length; i+=2) {
packeds.push(pack(elts[i], elts[i+1]);
}
return String.fromCharCode.apply(0, packeds);
}
反过来,这很容易:
function uncompress(str) {
var elts = [], code;
for (var i = 0; i < str.length; i++) {
code=str.charCodeAt(i);
elts.push(code>>8, code & 0xff);
}
return elts;
}
每两个7位值将占用两个字节,因此效率比base 32方法高约33%。
如果将上述字符串作为Javascript赋值写到script标签中,例如
var data="HUGE UNICODE STRING";
,则需要对字符串中的引号进行转义:javascript_assignment = 'var data = "' + compress(elts).replace(/"/g,'\\"') + '";';
上面的代码不是生产性代码,特别是不能处理输入数量不是四或二的倍数的情况。