如何压缩一个字符串？

Question

我希望可以有一种可逆的压缩方法来处理一种字符串类型，以便将其包含在URL中而无需跟踪其所指代的内容。我想要压缩的字符串是SVG路径字符串，这里有一个简短的介绍：http://apike.ca/prog_svg_paths.html

基本上，该字符串包含一个字符，后面跟着任意数量的整数，然后是另一个字符，再后面又是任意数量的整数，以此类推。

如果有人知道一个好的资源可以做到这一点，那将不胜感激！

Jason

- FurtiveFelon

Answer 1

许多压缩算法都有很好的文档，其中一些甚至有JS实现：

• GZip 一种常见（相当）好的压缩算法，我知道有JS实现，我正在寻找URL

• LZW 另一个问题指向了JS中的LZW实现

• 算术编码（我做过这个，但它使用的模型很愚蠢，因此无法达到最佳压缩率）

- olliej

---

GZip链接似乎已经损坏了 :| - Penguin

Answer 2

以下解决方案返回一个压缩的Base64编码字符串。

创建一个名为zip.js的文件，其中包含下面的代码，然后查看下面的用法。

// Apply LZW-compression to a string and return base64 compressed string.
export function zip (s) {
  try {
    var dict = {}
    var data = (s + '').split('')
    var out = []
    var currChar
    var phrase = data[0]
    var code = 256
    for (var i = 1; i < data.length; i++) {
      currChar = data[i]
      if (dict[phrase + currChar] != null) {
        phrase += currChar
      } else {
        out.push(phrase.length > 1 ? dict[phrase] : phrase.charCodeAt(0))
        dict[phrase + currChar] = code
        code++
        phrase = currChar
      }
    }
    out.push(phrase.length > 1 ? dict[phrase] : phrase.charCodeAt(0))
    for (var j = 0; j < out.length; j++) {
      out[j] = String.fromCharCode(out[j])
    }
    return utoa(out.join(''))
  } catch (e) {
    console.log('Failed to zip string return empty string', e)
    return ''
  }
}

// Decompress an LZW-encoded base64 string
export function unzip (base64ZippedString) {
  try {
    var s = atou(base64ZippedString)
    var dict = {}
    var data = (s + '').split('')
    var currChar = data[0]
    var oldPhrase = currChar
    var out = [currChar]
    var code = 256
    var phrase
    for (var i = 1; i < data.length; i++) {
      var currCode = data[i].charCodeAt(0)
      if (currCode < 256) {
        phrase = data[i]
      } else {
        phrase = dict[currCode] ? dict[currCode] : oldPhrase + currChar
      }
      out.push(phrase)
      currChar = phrase.charAt(0)
      dict[code] = oldPhrase + currChar
      code++
      oldPhrase = phrase
    }
    return out.join('')
  } catch (e) {
    console.log('Failed to unzip string return empty string', e)
    return ''
  }
}

// ucs-2 string to base64 encoded ascii
function utoa (str) {
  return window.btoa(unescape(encodeURIComponent(str)))
}
// base64 encoded ascii to ucs-2 string
function atou (str) {
  return decodeURIComponent(escape(window.atob(str)))
}

使用方法：

import { zip, unzip } from './zip'

// Zip a string
const str = 'zip it'
const base64CompressedString = zip(str)

// Zip an object
const obj = { a: 123, b: 'zipit' }
const base64CompressedString = zip(JSON.stringify(obj))

// Unzip the base64 compressed string back to an object.
const originalObject = JSON.parse(unzip(base64CompressedString))

顺便说一下，如果你担心escape / unescape被弃用，请考虑使用polyfill

从这里获取LZW算法，并从这里进行Base64编码。

- Simon Hutchison

---

另一个考虑用于此目的的库。https://github.com/rotemdan/lzutf8.js - Simon Hutchison

Answer 3

看起来你可能会从单个和双重RLE压缩中受益。

这方面的入门介绍可以在这里看到:

http://pp19dd.com/2011/10/query-string-limits-encoding-hundreds-of-checkboxes-with-rle/#demo

该库应该足够灵活，能够修改您的压缩模式以达到更好的效果。这篇文章解释了如何实现；这可能是优化SVG情况的良好起点。

- pp19dd

---

RLE 对 SVG 路径数据的压缩效果并不好。 - Phrogz

Answer 4

你可以尝试使用Huffman压缩。不同字符的数量大约在20-30个之间，如果字符串很长，压缩效果应该会很好。

- pepkin88