JavaScript中的位压缩

Question

有没有一种方法可以将一个由250多个1和0组成的JavaScript数组压缩成更易处理的东西（比如较短的字符串），然后再解压缩回来？就像Google对图像编码的方式一样...

谢谢！

- Rio

Answer 1

我可以通过使用base32编码为您提供近1:5的压缩率。我选择包含一个简单的长度值，以使其允许可变长度。请参见演示该技术的此代码片段，其中包含两个函数，可让您往返传输该值。（或者您可以查看我早期更加天真的十六进制版本，在@slebetman提醒我javascript中存在本机数字基础转换之前，我创建了该版本。）

以下是250个1和0组成的一个集合的示例输出。字符数不包括前导的“250|”：

base 32, 50 chars: 250|qgl6alf1q2lbl1aclau3k5ana2kpals78alek59ilboeglajgu
base 16, 63 chars: 250|D42A6555E1D0AABA854CAABC3A155750A995578742AAEA1532AAF0E85553878

你可以使用base 64编码将其缩小到42个字符，但需要注意的是，在使用base 32和base 64版本时，您最终得到的单词可能会引起反感（请参见上面的范例）。十六进制版本也可能存在不良内容，但要少得多（一个坏脸给了一个爸爸，成为了一个cad？）

如果你需要再节省8个字符，请告诉我，我将为你准备额外的脚本。避免使用元音字母可能是解决不良单词问题的一种方式。如果您需要这样做，请告诉我。

如果您的位串始终为250个字符，则函数可以简化一些，但我不想做出这样的假设。

以下是比特串到base-32函数的参考。

function bitstringEncode(bitstring) {
    var i, l = bitstring.length,
        retval = l.toString() + '|';
    for (i = 0; i < l; i += 5) {
        retval += parseInt((bitstring.substr(i, 5) + '0000').substr(0, 5), 2).toString(32);
    }
    return retval;
}

这个函数会向最近的5位进行填充，可能会在你提供的长度末尾生成一个虚假的额外字符。我还包括了每个转换函数的第二个版本，它们会填充到最近的10位，可能会生成多达两个虚假的额外字符。我包含它们是因为如果速度很重要，它们可能（也可能不）更快，因为它们从输入中获取更大的块。

- ErikE

---

它可以是 - 我可以做数组.join("")，反之亦然。 - Rio

我确实需要一个往返行程。本质上，我正在保存一个长度为250个音符（开或关）的音符序列，因此我想保存该序列，压缩它，并最终解压缩它。 - Rio

@Rio 在 POST 请求的负载中使用 a.join("")。 - PointedEars

最好添加一条注释，说明你从哪里获取了更新的想法。 - PointedEars

String.prototype.substr()是专有的。请使用String.prototype.substring()。更好的选择是Array.prototype.slice()。 - PointedEars

Answer 2

其他答案中并没有很多解释，因此除了介绍我的方法外，我还想在我的答案中讨论迄今为止提出的方法。请耐心等待。

正如其他答案所示，位数组可以被视为位流，它本质上是一个用二进制表示的相当大的数字。同一个数字也可以用另一个数字基数来表示。因为在更高的数字基数中，除十进制数字以外的单个字符可以用于更高价值的数字（例如，在十六进制中，“F”或“f”表示15），所以数字基数越大，显示它所需的数字（字符）就越少。

如那些答案中所建议的，您可以使用base64编码甚至更大的基数（Unicode Base Multilingual Plane有65536个代码点，符合ECMAScript实现支持该编码，因此基数为65536是一个不同的可能性，但在ECMAScript中，这将需要用户定义的函数，或许包含它的库；至少它需要一个非本地实现的转换算法，这必然比本地实现慢。另外，对于URI，您还需要进行百分号编码。（参见链接）。

幸运的是，ECMAScript 实现内置了一些方法，允许您将数字从一个基数转换为另一个基数，包括从2到36进制。有一个 parseInt(string, radix) 方法，可以将以基数 radix 写入的数字字符串值 string 转换为 Number 类型的值，还有一个 number.toString(radix) 方法，可以将 Number 值 number 转换为以基数 radix 写入的数字字符串。

然而，由于ECMAScript的Number类型是IEEE-754双精度浮点数实现，因此存在多个整数精度限制。据我所知，其中之一是对于一个全为1的比特数组，除非您的数组不包含超过53个比特元素（或者您的字符串不包含超过53个“1”），否则您无法在不失去精度的情况下将整个比特串来回转换。（IEEE-754双精度的有效数字具有53位精度。）

但是，您可以将一个大的（二进制）数字视为较小的（二进制）数字字符串的串联，将原始位流分成足够小的块并将每个块转换为更大的基数。在任何情况下，每个块中连续高位为0的信息都会丢失。因此，在从转换结果恢复位流时，您需要在每个块的左侧填充零，以使每个解码块与原始块一样长。块大小需要权衡编码流所需的步骤数以及解码它时需要填充的零的数量。

根据我理解，如果您从左到右处理比特流，那么每个块编码的数字可能会更大，因此即使使用更大的基数，编码后的字符串也可能会更长，因为块中的高位可能被设置（例如，比较右边界的11|001|001 - 3|1|1 - 和左边界的110|010|01 - 6|2|1 -，两者都具有块大小3）。首先对数据进行编码的原因是为了生成一个短的URI。因此，在编码之前应该从右到左处理流。（这种方法还消除了在编码的字符串中包含原始位数的必要性，如果该数字是块大小的倍数。）

这些考虑导致以下一般函数（为了可读性而不是完全优化）：

/*
 * @param bitArray : Array[Number|String]
 * @param chunkSize : optional Number = 53
 * @param chunkBase: optional Number = 36
 * @param delim : optional String = ","
 *   Delimiter to use.
 * @return string
 */
function bitEncode (bitArray, chunkSize, chunkBase, delim)
{
  var chunkArray = [];
  if (!chunkSize || chunkSize < 2 || chunkSize > 53)
  {
    chunkSize = 53;
  }

  if (!chunkBase)
  {
    chunkBase = 36;
  }

  for (var i = bitArray.length; i > 0; i -= chunkSize)
  {
    var index = i - chunkSize;
    if (index < 0)
    {
      index = 0;
    }

    var slice = bitArray.slice(index, i);
    var chunk = parseInt(slice.join(""), 2).toString(chunkBase);
    chunkArray.unshift(chunk);
  }

  return chunkArray.join(delim);
}

/*
 * @param input : String
 * @param length : Number > 1
 *   Target length of input after left-padded with zeros
 * @return string
 */
function leadingZero (input, length)
{
  input = String(input);

  var inputLength = input.length;
  if (inputLength >= length)
  {
    return input;
  }

  var padding = [];
  padding.length = length + 1 - inputLength;

  return padding.join("0") + input;
}

/*
 * @param s : String
 * @param chunkSize : optional Number = 53
 * @param chunkBase : optional Number = 36
 * @param delim : optional String = ","
 * @return Array[string]
 */
function bitDecode (s, chunkSize, chunkBase, delim)
{
  var chunkArray = s.split(delim || ",");
  var bitArray = [];
  if (!chunkSize || chunkSize > 53)
  {
    chunkSize = 53;
  }

  if (!chunkBase)
  {
    chunkBase = 36;
  }

  for (var i = 0, len = chunkArray.length; i < len; ++i)
  {
    bitArray = bitArray.concat(
      leadingZero(
        parseInt(chunkArray[i], chunkBase).toString(2),
        chunkSize)
      .split(""));
  }

  return bitArray;
}

正如您所看到的，这里的默认块大小为53位，默认基数为36。因此，一个由250个随机位组成的数组——

var a = [];
for (var i = 250; i--;)
{
  a[i] = +(Math.random() < 0.5);
}

- 这可以是（以53位为一组的右向块）

/*
              "11111110110011110011000011001010101010\
11010011111010010010100110100100010011001011001010111\
00100100010000101110011010000011100010010101011100011\
11100010110110111001101110000100011101101111101111100\
10001110110100010101110010011100110110100101110010011"
*/
a.join("")

默认情况下，将被编码为。

/* "3hou1lt6,21ewvahkfvb,ck8t6olnmr,26lbvliu2rg,1dh74lghy8j" (55 characters) */
var s = bitEncode(a)

"并且可以这样解码："

var a = bitDecode(s);

这些“通用”的功能应该允许您变化块大小和基数，以便优化编码字符串以适应您的使用情况。（任何可能引起冒犯的单词都可能因为分隔符而被拆成两部分。）

但是，请注意，如果原始数组长度不是块大小的倍数，则解码后的数组将包含额外的前导零。如果存在这种可能性并且会造成问题，您可以通过传递原始长度来解决问题，就像ErikE建议的那样，然后使用该值：

var originalLength = …;

a = a.slice(a.length - originalLength);

或者（在所有主要实现中，除了JavaScript 1.6版本之前和Opera ECMAScript 9.52版本之前）。

a = a.slice(-originalLength);

- PointedEars

Answer 3

我刚刚编写了这个非常幼稚的实现。

它可以在 "111000111" 和 [['1',3],['0',3], ['1',3]] 之间进行转换（反之亦然）。

希望它能够很好地处理大型二进制字符串，这些字符串应该有很多重复的字符。在最坏的情况下（01010101...），您将使用 1+7*n 个字符（其中 n 是输入字符串的大小）。

希望有人能提供更高效的解决方案？

var compress = function (input){
    var output = [], current = null;
    for (var t = 0; t < input.length; ++t ) {
        if (current === null || current[0] !== input[t]) {
            current = [input[t], 0];
            output.push(current);
        }

        ++ current[1];
    }

    return output;
};

var decompress = function (input) {
    var output = '';

    for (var t = 0; t < input.length; ++t) {
        for (var u = 0; u < input[t][1]; ++u) {
            output += input[t][0];
        }
    }

    return output;
};

- Maël Nison

Answer 4

以下是一个将1和0转换为十六进制的实现方法。在服务器上，将它转换回1和0应该相当简单。将其转换为十六进制基本上每个字符存储4位，因此它将把您的250位序列转换为63个字符。

不过需要注意的是，这个方法以4位为单位进行数据转换，所以您需要将序列填充到252位（用于4位对齐）或256位（用于8位对齐）。下面的实现方法不处理填充，因为我不知道您想从哪一端填充数据：

function binArray2HexArray (binArray) {
    var hexArray = [];
    while (binArray.length) {
        hexArray.push(parseInt(binArray.splice(0,4),2).toString(16));
    }
    return hexArray;
}

显然，您可以将返回的数组连接起来，以将其转换为十六进制字符串。

如果您将数据填充到8位对齐，则可以通过将splice参数更改为以下内容，在每个循环中操作8位来加快函数速度：

binArray.splice(0,8)

同样地，如果你将你的数据填充到16位对齐，你可以通过一次拼接16位来再次加速它。我相信极限是32位，在JavaScript开始由于浮点表示舍入数字之前。我更喜欢16作为最大值，因为我不确定各种JavaScript引擎会如何处理32位整数的符号。

- slebetman

---

我喜欢它！让我试一试。 - Rio

我在我的十六进制中得到了一串由1和0组成的字符串？ - Rio

我也尝试了http://freebeer.smithii.com/www/_source.php?file=%2Fhome%2Fross%2Fpublic_html%2Ffreebeer%2Fwww%2Flib%2Fbin2hex.js，它将1000000000000000011111000000010000000100100110000100000000100000000000100010100100000000000000000000000001000000000000000010000000000001000000001000100000000000000000000000010000000000000100000000000000000000转换了。 - Rio

313030303030303030303030303030303031313131313030303030303031303030303030303130303130303131303030303130303030303030303130303030303030303030303130303031303130303130303030303030303030303030303030303030303030303031303030303030303030303030303030303031303030303030303030303030313030303030303030303030303030303031303030303030303030303030313030303030303030313030303130303030303030303030303030303030303030303030303031303030303030303030303030303030303030 - Rio

@Rio：那个freebeer代码不同。它试图将每个ASCII字符转换为十六进制。因此，它的输出31,30实际上是字符“1”和“0”的转换。由于定义上需要两个十六进制字符来编码一个单个的ASCII字符，所以freebeer代码将字符串的大小加倍是有道理的。 - slebetman

Answer 5

这两个函数都需要一个字符串输入：

// input size must be less then 256 characters
// first byte in returned output is length of original string
// this is used during decoding for correct padding of last 8 bits
function encodeBits(input) {
    var output = String.fromCharCode(input.length);
    while(1) {
        output += String.fromCharCode(parseInt(input.substr(0,8),2));
        input = input.substr(8);
        if(input.length == 0) {
            break;
        }
    }

    return output;
}

function decodeBits(input) {
    var output = "";    
    var bits;
    var finalLength = input.charCodeAt(0);
    input = input.substr(1);

    while(1) {
        bits = input.charCodeAt(0).toString(2);

        // string must be left padded with 0's
        while(bits.length < 8) {
            if((bits.length+output.length) == finalLength) {
                break;
            }
            bits = "0"+bits;
        }

        output += bits;

        input = input.substr(1);
        if(input.length == 0) {
            break;
        }
    }

    return output;
}

编码

var instr = "101001110010100110010000111011111010110110001001111010110110";
var encStr = encodeBits(instr);

你可以使用escape对你的输出进行编码

var escapedStr = escape(encStr); // returns '%3C%A7%29%90%EF%AD%89%EB%06'

解码

使用 unescape 进行解码

var unescapedStr = unescape("%3C%A7%29%90%EF%AD%89%EB%06");
var bitStr = decodeBits(unescaped);

// bitStr now contains original input
"101001110010100110010000111011111010110110001001111010110110"

作为转义/反转义的替代方案，您也可以使用btoa和atob，这将为您提供更短的编码。

这些函数及其用法在此工作示例中进行了演示： http://jsfiddle.net/EU4nL/。

- lostsource

---

escape()和unescape()并不总是Unicode安全的。请使用encodeURIComponent()和decodeURIComponent()代替。btoa()和atob()是非标准的，即使根据参考文档，也不适用于Unicode字符。 - PointedEars

Answer 6

为什么不使用base64？我之前写过类似的东西，但它使用了类型化数组：

https://github.com/beatgammit/base64-js/blob/master/lib/b64.js

基本上只需要将你的1和0转换成字节并进行base64编码即可。Base64可以在URL中传递，因此它适用于你的情况。

- beatgammit

---

鉴于存在POST请求和gzip传输编码，使用base64会过度杀伤力。 - PointedEars

@PointedEars - OP没有详细说明需要它用于什么。如果需要作为GET查询参数的一部分，则base64可能是有意义的选择。 - beatgammit

Answer 7

啊！我终于找到了几个月前读过的一篇文章。它描述了多种有效压缩字符串的方法，你应该试试：这就是它。

论文中提到的技术：

• base64
• latin1
• utf-16
• png

- Maël Nison