Как сжать строку?

Question

Я хотел бы иметь обратимое сжатие для типа строки, чтобы я мог включить его в URL-адреса без отслеживания того, к чему он относится. Строка, которую я хотел бы сжать - это строка пути SVG, вот краткий пример: http://apike.ca/prog_svg_paths.html

По сути, строка содержит символ, за которым следует произвольное число целых чисел, затем другой символ, за которым следует произвольное число целых чисел и так далее.

Если кто-нибудь знает о хорошем ресурсе для этого, он будет очень признателен!

Jason

Answer 1

Многие алгоритмы сжатия хорошо документированы, у пары даже есть реализации js:

• GZip Обычный (разумно) хороший алгоритм сжатия, я знаю, что есть JS-импл, я просто ищу URL

• LZW Другой вопрос указывает на реализацию LZW в JS

• Арифметическое кодирование (я сделал это, но модель, которую он использует, глупа, поэтому не достигает лучших показателей сжатия, которые он мог)

Answer 2

Звучит так, будто вы могли бы выиграть от одинарного и двойного сжатия RLE.

Пример этого можно увидеть здесь:

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

Библиотека должна быть достаточно гибкой, чтобы изменить ваш шаблон сжатия на что-то более предпочтительное. В рецензии объясняется, как это работает; может быть хорошим началом для оптимизации вашего случая SVG.

Answer 3

Вы можете попробовать сжатие Хаффмана . Число различных символов составляет 20-30, и если строка длинная, сжатие должно быть эффективным.

Answer 4

Следующее решение возвращает сжатую строку в кодировке 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с здесь