48

我正在寻找一个给定字符串返回压缩（较短）字符串的 JavaScript 函数。

我正在开发一个将长字符串 (HTML) 保存到本地数据库的 Chrome Web 应用程序。出于测试目的，我尝试压缩存储数据库的文件，但它缩小了五倍，所以我认为如果我压缩它存储的内容，它将有助于使数据库更小。

我在 JavaScript 中找到了 LZSS 的实现：http ://code.google.com/p/u-lzss/ （“U-LZSS”）。

当我用简短的示例字符串（decode === encode）“手动”测试它时，它似乎工作了，而且在 Chrome 中它也相当快。但是当给定大字符串（100 ko）时，它似乎会混淆/混淆字符串的后半部分。

U-LZSS 是否有可能需要短字符串而不能处理更大的字符串？是否可以调整一些参数以移动该上限？

4

8 回答 8

41

我刚刚发布了一个专门为此目的量身定制的小型LZW实现，因为现有的实现都不能满足我的需求。

这就是我正在使用的东西，我可能会在某个时候尝试改进这个库。

于 2013-05-09T10:29:24.837 回答
19

这是我在一个完整的演示中从 LZW 修改的编码（276 字节，函数 en）和解码（191 字节，函数 de）函数。互联网上没有比我在这里给你的更小或更快的例程了。

function en(c){var x='charCodeAt',b,e={},f=c.split(""),d=[],a=f[0],g=256;for(b=1;b<f.length;b++)c=f[b],null!=e[a+c]?a+=c:(d.push(1<a.length?e[a]:a[x](0)),e[a+c]=g,g++,a=c);d.push(1<a.length?e[a]:a[x](0));for(b=0;b<d.length;b++)d[b]=String.fromCharCode(d[b]);return d.join("")}

function de(b){var a,e={},d=b.split(""),c=f=d[0],g=[c],h=o=256;for(b=1;b<d.length;b++)a=d[b].charCodeAt(0),a=h>a?d[b]:e[a]?e[a]:f+c,g.push(a),c=a.charAt(0),e[o]=f+c,o++,f=a;return g.join("")}

var compressed=en("http://www.ScriptCompress.com - Simple Packer/Minify/Compress JavaScript Minify, Fixify & Prettify 75 JS Obfuscators In 1 App 25 JS Compressors (Gzip, Bzip, LZMA, etc) PHP, HTML & JS Packers In 1 App PHP Source Code Packers Text Packer HTML Packer or v2 or v3 or LZW Twitter Compress or More Words DNA & Base64 Packer (freq tool) or v2 JS JavaScript Code Golfer Encode Between Quotes Decode Almost Anything Password Protect Scripts HTML Minifier v2 or Encoder or Escaper CSS Minifier or Compressor v2 SVG Image Shrinker HTML To: SVG or SVGZ (Gzipped) HTML To: PNG or v2 2015 JS Packer v2 v3 Embedded File Generator Extreme Packer or version 2 Our Blog DemoScene JS Packer Basic JS Packer or New Version Asciify JavaScript Escape JavaScript Characters UnPacker Packed JS JavaScript Minify/Uglify Text Splitter/Chunker Twitter, Use More Characters Base64 Drag 'n Drop Redirect URL DataURI Get Words Repeated LZMA Archiver ZIP Read/Extract/Make BEAUTIFIER & CODE FIXER WHAK-A-SCRIPT JAVASCRIPT MANGLER 30 STRING ENCODERS CONVERTERS, ENCRYPTION & ENCODERS 43 Byte 1px GIF Generator Steganography PNG Generator WEB APPS VIA DATAURL OLD VERSION OF WHAK PAKr Fun Text Encrypt Our Google");
var decompressed=de(compressed);

document.writeln('<hr>'+compressed+'<hr><h1>'+compressed.length+' characters versus original '+decompressed.length+' characters.</h1><hr>'+decompressed+'<hr>');

于 2016-01-09T22:55:53.990 回答
12

看来，有一个压缩/解压缩 API 的提议：https ://github.com/wicg/compression/blob/master/explainer.md 。

根据https://blog.chromium.org/2019/12/chrome-80-content-indexing-es-modules.html上的博客文章，它在 Chrome 80（现在处于 Beta 版）中实现。

我不确定我是否在流和字符串之间进行了良好的转换，但这是我使用新 API 的尝试：

function compress(string, encoding) {
  const byteArray = new TextEncoder().encode(string);
  const cs = new CompressionStream(encoding);
  const writer = cs.writable.getWriter();
  writer.write(byteArray);
  writer.close();
  return new Response(cs.readable).arrayBuffer();
}

function decompress(byteArray, encoding) {
  const cs = new DecompressionStream(encoding);
  const writer = cs.writable.getWriter();
  writer.write(byteArray);
  writer.close();
  return new Response(cs.readable).arrayBuffer().then(function (arrayBuffer) {
    return new TextDecoder().decode(arrayBuffer);
  });
}

const test = "http://www.ScriptCompress.com - Simple Packer/Minify/Compress JavaScript Minify, Fixify & Prettify 75 JS Obfuscators In 1 App 25 JS Compressors (Gzip, Bzip, LZMA, etc) PHP, HTML & JS Packers In 1 App PHP Source Code Packers Text Packer HTML Packer or v2 or v3 or LZW Twitter Compress or More Words DNA & Base64 Packer (freq tool) or v2 JS JavaScript Code Golfer Encode Between Quotes Decode Almost Anything Password Protect Scripts HTML Minifier v2 or Encoder or Escaper CSS Minifier or Compressor v2 SVG Image Shrinker HTML To: SVG or SVGZ (Gzipped) HTML To: PNG or v2 2015 JS Packer v2 v3 Embedded File Generator Extreme Packer or version 2 Our Blog DemoScene JS Packer Basic JS Packer or New Version Asciify JavaScript Escape JavaScript Characters UnPacker Packed JS JavaScript Minify/Uglify Text Splitter/Chunker Twitter, Use More Characters Base64 Drag 'n Drop Redirect URL DataURI Get Words Repeated LZMA Archiver ZIP Read/Extract/Make BEAUTIFIER & CODE FIXER WHAK-A-SCRIPT JAVASCRIPT MANGLER 30 STRING ENCODERS CONVERTERS, ENCRYPTION & ENCODERS 43 Byte 1px GIF Generator Steganography PNG Generator WEB APPS VIA DATAURL OLD VERSION OF WHAK PAKr Fun Text Encrypt Our Google";

async function testCompression(text, encoding = 'deflate') {
  console.log(encoding + ':');
  console.time('compress');
  const compressedData = await compress(text, encoding);
  console.timeEnd('compress');
  console.log('compressed length:', compressedData.byteLength, 'bytes');
  console.time('decompress');
  const decompressedText = await decompress(compressedData, encoding);
  console.timeEnd('decompress');
  console.log('decompressed length:', decompressedText.length, 'characters');
  console.assert(text === decompressedText);
}

(async function () {
  await testCompression(test, 'deflate');
  await testCompression(test, 'gzip');
}());

于 2019-12-24T12:57:21.573 回答
7

对我来说，使用 UTF-8 作为目标来压缩字符串似乎并不合理……看起来只是在找麻烦。我认为如果线外大小很重要，最好放弃一些压缩并使用纯 7 位 ASCII 作为目标。

如果存储限制基于 UTF-16 字符，那么如果您关心转义或 UTF-16 合规性，则可以寻找一个大的安全子集，或者如果涉及其他所有内容（例如数据库）没有问题。大多数软件层在（ab）使用方面应该没有问题，但请注意，在 UTF-16 范围内，0xD800-0xDFFF 保留用于特殊用途（代理对），因此某些组合在形式上是“编码错误”，理论上可以停止或扭曲。

在我为好玩而编写的一个玩具4 KB JavaScript 演示中，我使用了一种编码作为压缩结果，将四个二进制字节存储到五个字符中，这些字符是从 85 个字符的 ASCII 子集中选择的，这些字符可以嵌入 JavaScript 字符串 (85^5略大于 8^4，但仍符合 JavaScript 整数的精度）。这使得压缩数据例如对于JSON是安全的，无需任何转义。

在代码中，以下构建了 85 个“安全”字符的列表：

let cset = "";
for (let i=35; i<35+85+1; i++) {
    if (i !== 92) cset += String.fromCharCode(i);
}

然后将 4 个字节（b0, b1,b2以及b3从 0...255 的每个字节）编码为 5 个字符，代码为：

// First convert to 0...4294967295
let x = ((b0*256 + b1)*256 + b2)*256 + b3;

// Then convert to base 85
let result = "";
for (let i=0; i<5; i++) {
    let x2 = Math.floor(x / 85);
    result += cset[x - x2*85];
    x = x2;
}

要解码，请执行相反的操作，即从 base-85 数字计算 x，然后提取 4 个 base-256 数字（即字节）。

注意：在环面代码中，我使用了稍微不同的字符集，而不是跳过 92\我用 126 替换它~。谁有兴趣，完整的解压代码是

// There are two Huffman-encoded code streams
//    T - single chars (0..127) and sequence lengths (128...255)
//    A - high bits of relative addresses of sequence (0..255)
//
// Expansion algorithm is:
//    1) Read a code X from T
//    2) If it's a char (X < 128) then add to output
//    3) otherwise (X>=128) read sequence address ADDR from stream A (high bits)
//       and from input (low bits) and copy X-128 bytes from ADDR bytes "ago"
//

let Z = 5831; // expanded size
let i = 0, // source ptr
    a = 0, // current bits accumulator
    n = 0; // number of available bits in a

// Read a single bit
let b = function(){
    if (!n) {
        // There are no more bits available in the accumulator, read a new chunk:
        // 5 ASCII escape-safe chars will be transformed in 4 8-bit binary bytes
        // (like BASE64, just a bit more dense)
        a = 0;
        let w = 5;
        while (w--) {
            let y = s.charCodeAt(i+w);          // get next char
            a = a*85 + (y > 125 ? 92 : y) - 35; // extract base-85 "digit" (note, uses ~ instead of \ that requires quoting)
        }
        n = 32; // we got 32 bits in a
        i += 5; // we consumed 5 characters from source
    }
    return (a >> --n) & 1;  // extract a single bit
};

// Read a code of z bits by concatenating bits coming from b()
let v = function(z){
    return (--z ? v(z) : 0)*2+b();
};

// Read an Huffman (sub-)tree: a bit will tell if we need to
// read a two sub-trees or a leaf
let h = function(){
    return b() ? [h(), h()] : v(8);
};

// Read A and T Huffman trees
let A = h(), T = h();

// Extract a code given a node:
//   if the node is an array (intermediate node) then we need to read a bit
//   from the input binary stream to decide which way to go down the tree,
//   if it's a number then we just return the value.
//   `n.map` is truthy for arrays and falsy for numbers.
let d = function(n){
    return n.map ? d(n[b()]) : n;
};

let S="";  // Output

// While we're not done
while(S.length<Z){
    // Extract a code from T
    x = d(T);
    if (x < 128) {
        // This is a single character, copy to output
        S += String.fromCharCode(x);
    } else {
        // This is a sequence of x-128 bytes, get address and copy it
        // Note: high 8 bits are from the Huffman tree A and 8 low bits
        // are instead directly form the bit stream as they're basically
        // noise and there's nothing to gain by trying to compress them.
        S += S.substr(S.length-(d(A)<<8)-v(8), x-128)
    };
}

（请注意，我没有测试这个重新格式化/注释的版本，可能存在拼写错误）

于 2010-12-31T13:36:18.143 回答
6

在 Piskvor 的建议下，我测试了在这个问题的答案中找到的代码：JavaScript implementation of Gzip (top-voted answer: LZW implementation) 并发现：

  1. 有用
  2. 它将数据库的大小减少了两倍

... 小于 5 但总比没有好！所以我用了那个。

（我希望我能接受 Piskvor 的回答，但这只是一个评论）。

于 2011-01-03T12:16:52.610 回答
1

在实现任何东西之前尝试使用文本文件，因为我认为以下内容不一定成立：

所以我认为如果我压缩它存储的东西，它会有助于保持数据库更小。

这是因为无损压缩算法非常适合重复模式（例如空格）。

于 2010-12-31T13:22:11.367 回答
1

我认为您还应该研究lz-string它的速度很快，压缩得很好，并且在他们的页面上列出了一些优点：

其他图书馆呢？

  • 一些 LZW 实现可以返回数字数组（存储非常低效，因为令牌占用 64 位）并且不支持 255 以上的任何字符。
  • 其他一些 LZW 实现可以返回一个字符串（存储效率不那么低，但所有标记仍然占用 16 位）并且不支持任何高于 255 的字符。
  • 一个异步且非常慢的 LZMA 实现——但是，嘿，它是 LZMA，而不是慢的实现。
  • GZip 实现并不真正适用于浏览器，而是适用于 node.js，它的重量为 70kb（它依赖于 deflate.js 和 crc32.js）。

作者创建lz-string的原因：

  • 在移动设备上工作我需要一些快速的东西。
  • 使用从我的网站外部收集的字符串，我需要可以将任何类型的字符串作为输入的东西，包括 255 以上的任何 UTF 字符。
  • 图书馆不占用 70kb 是一个明确的优势。产生尽可能紧凑的字符串以存储在 localStorage 中的东西。因此，我在网上找到的所有图书馆都不能很好地满足我的需求。

这个库有其他语言的实现，我目前正在研究 python 实现，但目前解压似乎有问题，但如果你只坚持 JS，它对我来说真的很好。

于 2016-01-29T18:27:05.967 回答
1

BWTC32Key 使用 BZip 系列改进和 Base32768 以获得极高的效率，其可选加密为 AES256-CTR 以避免填充。您想要的任何东西（包括字符串）都可以输入其中，结果将是一个非常有效的 UTF16 字符串，其中包含重压缩后的输入（以及压缩后但在 Base32768 之前的可选加密。）我运行了我的 829KiB 自制 Minecraft 纲要来自 eons 之前通过 BWTC32Key 的命令块命令，我得到了一个 13078 字符的输出字符串。我的世界命令块最多可以包含 32767 个字符，但一些旧版本的游戏只允许在游戏中使用一半大小的字符串，尽管使用 MCEdit 你可以达到 32767 大小，尽管这个问题很快得到修复。

无论如何，829KiB 的纯文本远远大于 32767 的限制，但 BWTC32Key 使它适合少于 16K 的字符。举个更极端的例子，Titin 蛋白的化学全名是 18.9 万个字母。我可以使用 BWTC32Key 将其降低到 640 左右。即使使用高于每个字符 1 个字节的 ASCII 表示（如 UTF16）作为输入仍然可以节省成本。

于 2021-10-25T22:24:16.097 回答