Compressione delle stringhe in JavaScript

Sto cercando una funzione JavaScript che, data una stringa restituisce una stringa compressa (più breve).

Sto sviluppando un’applicazione web di Chrome che salva stringhe lunghe (HTML) in un database locale. A scopo di test, ho provato a comprimere il file che memorizzava il database, e si è ridotto di un fattore cinque, quindi ho pensato che avrebbe aiutato a mantenere il database più piccolo se ho compresso le cose che memorizza.

Ho trovato un’implementazione di LZSS in JavaScript qui: http://code.google.com/p/u-lzss/ (“U-LZSS”).

Sembra funzionare quando l’ho provato “a mano” con brevi stringhe di esempio (decode === encode), ed è anche abbastanza veloce, in Chrome. Ma quando si danno grosse stringhe (100 ko), sembra che si mischiano / mischiano l’ultima metà della corda.

È ansible che U-LZSS si aspetti stringhe corte e non riesca a gestire stringhe più grandi? E sarebbe ansible regolare alcuni parametri per spostare quel limite superiore?

Ho appena rilasciato una piccola implementazione LZW appositamente progettata per questo scopo, in quanto nessuna delle implementazioni esistenti ha soddisfatto le mie esigenze.

  • Ecco la home page del progetto

  • Ecco un link a una demo che lo confronta con il livello 1 di LZMA

Questo è quello che sto usando andando avanti e probabilmente cercherò di migliorare la libreria ad un certo punto.

Su suggerimento di Piskvor, ho testato il codice trovato in una risposta a questa domanda: implementazione di JavaScript di Gzip (risposta votata dall’alto: implementazione LZW) e ho scoperto che:

  1. Funziona
  2. riduce la dimensione del database di un fattore due

… che è meno di 5 ma meglio di niente! Quindi l’ho usato.

(Vorrei aver accettato una risposta di Piskvor, ma era solo un commento).

Per me non sembra ragionevole comprimere una stringa usando UTF-8 come destinazione … Sembra che sia solo in cerca di guai. Penso che sarebbe meglio perdere una certa compressione e usare la semplice ASCII a 7 bit come destinazione.

In una demo JavaScript di 4 KB di un giocattolo che ho scritto per divertimento ho usato una codifica per il risultato della compressione che memorizza quattro byte binari in cinque caratteri scelti da un sottoinsieme di ASCII di 85 caratteri puliti per l’incorporamento in una stringa JavaScript (85 ^ 5 è leggermente più di 8 ^ 4, ma si adatta ancora alla precisione degli interi JavaScript). Ciò rende sicuri i dati compressi, ad esempio per JSON senza bisogno di alcuna escaping.

Qui ci sono funzioni di codifica (276 byte, funzione en) e decodifica (191 byte, funzione de) che ho modificato da LZW in una demo completamente funzionante. Non esiste una routine più piccola o più veloce disponibile su Internet rispetto a quello che ti sto dando qui.

 function en(c){var x='charCodeAt',b,e={},f=c.split(""),d=[],a=f[0],g=256;for(b=1;ba?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('
'+compressed+'

'+compressed.length+' characters versus original '+decompressed.length+' characters.


'+decompressed+'
');

Prova a sperimentare con i file di testo prima di implementare qualsiasi cosa, perché penso che ciò che segue non sia necessariamente valido:

quindi ho pensato che avrebbe aiutato a mantenere il database più piccolo se ho compresso le cose che memorizza.

Questo perché gli algoritmi di compressione senza perdita di dati sono piuttosto buoni con pattern ripetuti (ad es. Spazi bianchi).

Penso che dovresti anche cercare in lz-string , è veloce, comprime abbastanza bene e ha alcuni vantaggi che elencano nella loro pagina:

E le altre biblioteche?

  • alcune implementazioni LZW che ti restituiscono matrici di numeri (terribilmente inefficienti da archiviare quando i token prendono 64 bit) e non supportano nessun carattere sopra 255.
  • alcune altre implementazioni LZW che ti restituiscono una stringa (meno terribilmente inefficiente da archiviare ma ancora, tutti i token hanno 16 bit) e non supportano nessun carattere sopra 255.
  • un’implementazione LZMA che è asincrona e molto lenta – ma, ehi, è LZMA, non l’implementazione che è lenta.
  • un’implementazione GZip non pensata per i browser ma destinata a node.js, che pesa 70kb (con deflate.js e crc32.js da cui dipende).

I motivi per cui l’autore ha creato lz-string:

  • Lavorando su mobile avevo bisogno di qualcosa di veloce.
  • Lavorando con le stringhe raccolte al di fuori del mio sito web, avevo bisogno di qualcosa che potesse prendere qualsiasi tipo di stringa come input, inclusi tutti i caratteri UTF sopra 255.
  • La libreria che non prendeva 70kb era un vantaggio decisivo. Qualcosa che produce stringhe il più ansible compatte da archiviare in localStorage. Quindi nessuna delle librerie che ho trovato online ha funzionato bene per le mie esigenze.

Ci sono implementazioni di questa lib in altri linguaggi, al momento sto esaminando l’implementazione di Python, ma la decompressione sembra avere problemi al momento, ma se si attiene a JS solo mi sembra davvero buona.