使用Javascript中的utf-32编码缩短utf-8字符串？

Question

我正在尝试找到一种在Javascript中压缩/解压缩字符串的方法.通过压缩我的意思是使字符串看起来更短(更少char).那是我的目标.

以下是事情应该如何运作的一个例子:

// The string that I want to make shorter
// It will only contain [a-zA-Z0-9] chars and some ponctuations like ()[]{}.,;'"!
var string = "I like bananas !";

// The compressed string, maybe something like "????",
// which is shorter than the original
var shortString = compress(string);  

// The original string, "I like banana !"
var originalString = decompress(shortString);

这是我的第一个想法(也许有更好的方法来达到我的目标,如果是这样,我对它感兴趣).

我知道我的原始字符串将是utf-8.所以我正在考虑使用utf-32进行编码,它应该将字符串的长度除以4.

但我不知道如何使用不同的编码来构造这两个函数来构造新的字符串.这是我到目前为止的代码不起作用......

function compress(string) {
    string = unescape(encodeURIComponent(string));
    var newString = '';

    for (var i = 0; i < string.length; i++) {
        var char = string.charCodeAt(i);
        newString += parseInt(char, 8).toString(32);
    }

    return newString;
}

Answer 1

由于您使用的是一组少于100个字符且javascript字符串以UTF-16编码(这意味着您有65536个可能的字符),您可以做的是连接字符代码以便拥有一个"压缩"字符每两个基本字符.这允许您将字符串压缩到一半的长度.

像这样例如:

document.getElementById('compressBtn').addEventListener('click', function() {
  var stringToCompress = document.getElementById('tocompress').value;
  var compressedString = compress(stringToCompress);
  var decompressedString = decompress(compressedString);

  if (stringToCompress === decompressedString) {
    document.getElementById('display').innerHTML = stringToCompress + ", length of " + stringToCompress.length  + " characters compressed to " + compressedString + ", length of " + compressedString.length + " characters back to " + decompressedString;
  } else {
    document.getElementById('display').innerHTML = "This string cannot be compressed"
  }

})


function compress(string) {
  string = unescape(encodeURIComponent(string));
  var newString = '',
    char, nextChar, combinedCharCode;

  for (var i = 0; i < string.length; i += 2) {
    char = string.charCodeAt(i);

    if ((i + 1) < string.length) {

      // You need to make sure that you don't have 3 digits second character else you  might go over 65536. 
      // But in UTF-16 the 32 characters aren't in your basic character set. But it's a limitation, anything
      // under charCode 32 will cause an error
      nextChar = string.charCodeAt(i + 1) - 31;

      // this is to pad the result, because you could have a code that is single digit, which would make 
      // decompression a bit harder
      combinedCharCode = char + "" + nextChar.toLocaleString('en', {
        minimumIntegerDigits: 2
      });

      // You take the concanated code string and convert it back to a number, then a character
      newString += String.fromCharCode(parseInt(combinedCharCode, 10));

    } else {

      // Here because you won't always have pair number length
      newString += string.charAt(i);
    }
  }
  return newString;
}

function decompress(string) {

  var newString = '',
    char, codeStr, firstCharCode, lastCharCode;

  for (var i = 0; i < string.length; i++) {
    char = string.charCodeAt(i);
    if (char > 132) {
      codeStr = char.toString(10);

      // You take the first part of the compressed char code, it's your first letter
      firstCharCode = parseInt(codeStr.substring(0, codeStr.length - 2), 10);

      // For the second one you need to add 31 back.
      lastCharCode = parseInt(codeStr.substring(codeStr.length - 2, codeStr.length), 10) + 31;

      // You put back the 2 characters you had originally
      newString += String.fromCharCode(firstCharCode) + String.fromCharCode(lastCharCode);
    } else {
      newString += string.charAt(i);
    }
  }
  return newString;
}

var stringToCompress = 'I like bananas!';
var compressedString = compress(stringToCompress);
var decompressedString = decompress(compressedString);

document.getElementById('display').innerHTML = stringToCompress + ", length of " + stringToCompress.length  + " characters compressed to " + compressedString + ", length of " + compressedString.length + " characters back to " + decompressedString;

body {
  padding: 10px;
}

#tocompress {
  width: 200px;
}

<input id="tocompress" placeholder="enter string to compress" />
<button id="compressBtn">
  Compress input
</button>
<div id="display">

</div>

关于可能使用UTF-32进一步压缩,我不确定是否可能,我可能错了,但从我的理解来看,这是不可行的.原因如下:

上面的方法基本上是在一个2字节值中连接两个1字节值.这是可能的,因为javascript字符串以2个字节(或16位)编码(请注意,根据我的理解,引擎可以决定以不同的方式存储,从纯粹的内存空间的角度来看这种压缩是不必要的 - 最后说,最后,一个字符被认为是16位).实现上述压缩的一种更简洁的方法实际上是使用二进制数而不是十进制数,这将更有意义.像这样例如:

document.getElementById('compressBtn').addEventListener('click', function() {
  var stringToCompress = document.getElementById('tocompress').value;
  var compressedString = compress(stringToCompress);
  var decompressedString = decompress(compressedString);

  if (stringToCompress === decompressedString) {
    document.getElementById('display').innerHTML = stringToCompress + ", length of " + stringToCompress.length  + " characters compressed to " + compressedString + ", length of " + compressedString.length + " characters back to " + decompressedString;
  } else {
    document.getElementById('display').innerHTML = "This string cannot be compressed"
  }

})


function compress(string) {
  string = unescape(encodeURIComponent(string));
  var newString = '',
    char, nextChar, combinedCharCode;

  for (var i = 0; i < string.length; i += 2) {
  
  // convert to binary instead of keeping the decimal
    char = string.charCodeAt(i).toString(2);

    if ((i + 1) < string.length) {

     
      nextChar = string.charCodeAt(i + 1).toString(2) ;
     

      // you still need padding, see this answer https://stackoverflow.com/questions/27641812/way-to-add-leading-zeroes-to-binary-string-in-javascript
      combinedCharCode = "0000000".substr(char.length) + char + "" + "0000000".substr(nextChar.length) + nextChar;

      // You take the concanated code string and convert it back to a binary number, then a character
      newString += String.fromCharCode(parseInt(combinedCharCode, 2));

    } else {

      // Here because you won't always have pair number length
      newString += string.charAt(i);
    }
  }
  return newString;
}

function decompress(string) {

  var newString = '',
    char, codeStr, firstCharCode, lastCharCode;

  for (var i = 0; i < string.length; i++) {
    char = string.charCodeAt(i);
    if (char > 132) {
      codeStr = char.toString(2);

      // You take the first part (the first byte) of the compressed char code, it's your first letter
      firstCharCode = parseInt(codeStr.substring(0, codeStr.length - 7), 2);

      // then the second byte
      lastCharCode = parseInt(codeStr.substring(codeStr.length - 7, codeStr.length), 2);

      // You put back the 2 characters you had originally
      newString += String.fromCharCode(firstCharCode) + String.fromCharCode(lastCharCode);
    } else {
      newString += string.charAt(i);
    }
  }
  return newString;
}

var stringToCompress = 'I like bananas!';
var compressedString = compress(stringToCompress);
var decompressedString = decompress(compressedString);

document.getElementById('display').innerHTML = stringToCompress + ", length of " + stringToCompress.length  + " characters compressed to " + compressedString + ", length of " + compressedString.length + " characters back to " + decompressedString;

<input id="tocompress" placeholder="enter string to compress" />
<button id="compressBtn">
  Compress input
</button>
<div id="display">

</div>

那么为什么不推动逻辑并使用utf-32,它应该是4个字节,意味着4个1字节字符.一个问题是javascript有2个字节的字符串.确实,您可以使用16位字符对来表示utf-32字符.像这样:

document.getElementById('test').innerHTML = "\uD834\uDD1E";

<div id="test"></div>

但是如果你测试结果字符串的长度,你会发现它是2,即使只有一个"字符".所以从javascript的角度来看,你并没有减少实际的字符串长度.

另一件事是UTF-32实际上有2 ^21个字符.请参见:https://en.wikipedia.org/wiki/UTF-32

它是一种编码Unicode代码点的协议,每个Unicode代码点使用正好32位(但由于Unicode代码点少于221个,所以前导位必须为零)

所以你实际上没有4个字节,实际上你甚至没有3个,这需要编码3.所以UTF-32似乎不是一种压缩方式.由于javascript具有原生的2字节字符串,因此在我看来它是最有效的 - 至少使用这种方法.

Answer 2

如果您的字符串仅包含 ASCII 字符 [0, 127]，您可以使用自定义 6 位或 7 位代码页“压缩”该字符串。

您可以通过多种方式执行此操作，但我认为更简单的方法之一是定义一个包含所有允许字符的数组 - LUT、查找表（如果您愿意），然后使用其索引值作为编码值。当然，您必须手动屏蔽编码值并将其转移到类型化数组中。

如果你的 LUT 看起来像这样：

var lut = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.,:;!(){}";

在这种情况下，您将处理长度为 71 的 LUT，这意味着我们需要使用 7 位范围或 [0, 127]（如果长度为 64，我们可以将其减少到6 位[0, 63] ]值）。

然后，您将获取字符串中的每个字符并转换为索引值（您通常会在单个操作中执行以下所有步骤，但为了简单起见，我将它们分开）：

var lut = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.,:;!(){}";

您始终可以调整 LUT，以便最常用的字符位于开头，然后支持可变编码位范围，找到最大值并使用它来确定要编码的范围。您可以添加初始位作为标志编码使用哪个范围（例如，如果 6 位适合，则设置位 0，否则使用 7 位范围）。

现在您知道了索引，我们可以开始使用 7 位方法对二进制输出本身进行编码。由于 JavaScript 仅支持字节值，即 8 位宽度，因此我们必须手动执行所有拆分、移位和合并操作。

这意味着我们需要在位级别上跟踪余数和位置。

假设第一个索引值是以下 7 位值（完整的 7 位范围以提高可读性 - 全部采用伪格式）：

var lut = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.,:;!(){}";
var str = "I like bananas !";
var page = [];

Array.prototype.forEach.call(str, function(ch) {
  var i = lut.indexOf(ch);
  if (i < 0) throw "Invalid character - can't encode";
  page.push(i);
});

console.log("Intermediate page:", page);

第一步是将其移至位位置 0 并跟踪余数：

&b01111111

导致：

&b01111111 << 1

然后是下一个索引值，例如：

&b11111110
         ^
new bit position: 7
new remainder   : 1

将像这样编码 - 首先转换为其自己的字节表示形式的 7 位值：

&b01010101

然后先获取提醒部分。要获得此结果，将使用 8 位减去当前余数（在 8 的模内）将所有内容向右移动：

&b01010101 << 1 => &b10101010

给我们留下以下表示：

remainderValue = &b10101010 >>> (8 - remainder)

（请注意，我们使用三倍>>>右移以避免符号问题。）

现在的下一步是将此值与我们之前已编码并存储到目标字节数组中的值合并 - 为此，我们将使用 OR 运算：

&b00000001

然后转到目标数组中的下一个索引并存储当前值的其余部分，然后更新余数和位置。

字节的“剩余”是使用原始（移位后）7 位字节值来计算的：

Index 0      New value     Result in index 0 (index of dst. array)
&b11111110 | &b00000001 => &b11111111

我们现在将其放入下一个位置：

leftover = &b10101010 << remainder => &b01010100

其余索引值依此类推。有关如何在 JavaScript 中执行此操作的实际代码，请参阅此答案- 此答案中的代码本身不处理字符串编码，但它显示了如何按位移动字节缓冲区，这与您需要的本质上相同为了这个任务。

要计算余数步长，请使用 8 位减去您的自定义位范围：

Index 0    Index 1   (destination array index, not page index)
&b11111111 01010100
                 ^

new bit position: 14
new remainder   : 2

这也将是开始余数。对于每个字符，您将在处理后将步骤添加到余数，但请记住在使用它进行移位时使用模 8（字节宽度）：

step = 8 - newRange (here 7) => 1

位位置当然使用位范围，在本例中为 7：

remainder += step;
numOfBitsToShift = remainder % 8;

然后，要找到要处理的索引，请将 bitPosition 除以 8，如果有小数，则必须处理两个索引（旧的和新的），如果没有小数，则当前位置仅代表新索引（当前位置只需要移位）指数值）。

您还可以使用模，当余数 = 步骤的模时，您知道您正在处理目标中的单个索引。

要计算最终长度，您可以使用位长度和字符串长度，然后将结果取整，以便所有字符都适合 8 字节的字节数组，这是我们在 JavaScript 中可以获得的唯一数组：

dstLength = Math.ceil(7 * str.length / 8);

要解码，只需颠倒所有步骤即可。

如果您使用长字符串或必须快速前进，另一种方法是使用已建立的压缩器，例如zlib，它具有非常紧凑的标头，并且在链接解决方案的情况下在 JavaScript 中具有良好的性能。这还将处理字符串中的“模式”以进一步优化结果大小。

免责声明：由于这主要是理论上的答案，因此可能存在一些错误。如果发现的话请随意评论。有关实际代码示例，请参阅链接的答案。