我有一个包含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,'\\"') + '";';

上面的代码不是生产性代码,特别是不能处理输入数量不是四或二的倍数的情况。

10-07 16:14