sirve - Compresión de cadena en JavaScript

substring javascript

Question

Estoy buscando una función de JavaScript que, dada una cadena, devuelva una cadena comprimida (más corta).

Estoy desarrollando una aplicación web de Chrome que guarda cadenas largas (HTML) en una base de datos local. Para fines de prueba intenté comprimir el archivo que almacenaba la base de datos, y se redujo en un factor de cinco, así que pensé que ayudaría a mantener la base de datos más pequeña si comprimiera las cosas que almacena.

Encontré una implementación de LZSS en JavaScript aquí: http://code.google.com/p/u-lzss/ ("U-LZSS").

Pareció funcionar cuando lo probé "a mano" con cadenas cortas de ejemplo (decodificación === codificación), y también es razonablemente rápido en Chrome. Pero cuando se le dan grandes cadenas (100 ko), parece distorsionar / mezclar la última mitad de la cuerda.

¿Es posible que U-LZSS espere cadenas cortas y no pueda manejar cadenas más grandes? ¿Y sería posible ajustar algunos parámetros para mover ese límite superior?

Answer 1

A sugerencia de Piskvor, probé el código que se encuentra en una respuesta a esta pregunta: la implementación de JavaScript de Gzip (respuesta mejor votado: implementación de LZW) y encontré que:

1. funciona
2. reduce el tamaño de la base de datos por un factor de dos

... que es menos de 5 pero mejor que nada! Entonces usé eso.

(Ojalá pudiera haber aceptado una respuesta de Piskvor, pero fue solo un comentario).

Answer 2

Acabo de lanzar una pequeña implementación de LZW especialmente diseñada para este propósito, ya que ninguna de las implementaciones existentes satisfacía mis necesidades.

• Aquí está la página de inicio del proyecto

• Aquí hay un enlace a una demostración que lo compara con el nivel 1 de LZMA

Eso es lo que estoy usando en el futuro, y probablemente intentaré mejorar la biblioteca en algún momento.

Answer 3

Aquí están las funciones de codificación (276 bytes, función en) y decodificación (191 bytes, función de) modificadas desde LZW en una demostración completamente operativa. No hay una rutina más pequeña o más rápida disponible en Internet que la que te doy aquí.

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>'');

Answer 4

Creo que también deberías mirar dentro de lz-string, que es rápido, comprime bastante bien y tiene algunas ventajas que listan en su página:

¿Qué hay de otras bibliotecas?

• algunas implementaciones de LZW que te devuelven matrices de números (terriblemente ineficaces para almacenar como tokens toman 64bits) y no admiten ningún personaje por encima de 255.
• algunas otras implementaciones LZW que le devuelven una cadena (menos terriblemente ineficaces para almacenar pero, aún así, todas las fichas toman 16 bits) y no admiten ningún carácter por encima de 255.
• una implementación LZMA que es asíncrona y muy lenta, pero bueno, es LZMA, no la implementación lenta.
• una implementación de GZip no es realmente para navegadores, sino para node.js, que pesa 70kb (con deflate.js y crc32.js de los que depende).

Las razones por las cuales el autor creó lz-string:

• Trabajando en el móvil necesitaba algo rápido.
• Al trabajar con Strings recopilados desde fuera de mi sitio web, necesitaba algo que pueda incluir cualquier tipo de cadena como entrada, incluidos los caracteres UTF superiores a 255.
• La biblioteca que no tomó 70kb fue una ventaja definitiva. Algo que produce cadenas tan compactas como sea posible para almacenar en localStorage. Así que ninguna de las bibliotecas que pude encontrar en línea funcionó bien para mis necesidades.

Hay implementaciones de esta lib en otros idiomas, actualmente estoy investigando la implementación de python, pero la descompresión parece tener problemas en este momento, pero si te apegas a JS solo se ve muy bien para mí.

Answer 5

Intente experimentar con archivos de texto antes de implementar cualquier cosa porque creo que lo siguiente no necesariamente se cumple:

así que pensé que ayudaría a mantener la base de datos más pequeña si comprimiera las cosas que almacena.

Esto se debe a que los algoritmos de compresión sin pérdida son bastante buenos con la repetición de patrones (por ejemplo, espacios en blanco).

Answer 6

Para mí, no parece razonable comprimir una cadena usando UTF-8 como destino ... Parece que está buscando problemas. Creo que sería mejor perder algo de compresión y usar ASCII de 7 bits como destino.

En una demostración de JavaScript de 4 KB de juguete, escribí por diversión. Utilicé una codificación para el resultado de compresión que almacena cuatro bytes binarios en cinco caracteres elegidos de un subconjunto de ASCII de 85 caracteres que está limpio para incrustación en una cadena de JavaScript (85 ^ 5 es un poco más de 8 ^ 4, pero todavía se ajusta a la precisión de los enteros de JavaScript). Esto hace que los datos comprimidos sean seguros, por ejemplo, para JSON sin necesidad de ningún escape.