Komprimieralgorithmus in JavaScript?

[Marc Reichelt]

Hallo an alle,

für eine Offline-Suche würde ich gerne Dokumente komprimiert abspeichern können. Natürlich könnte ein Server eine gzip-komprimierte JavaScript-Datei an den Browser senden. Dies fällt allerdings flach, da die JS-Dateien offline eingebunden werden müssen.

Nun frage ich mich, ob es möglich ist, einen String der Form
var myString = "Dies ist ein sehr langer String, mit UTF-8-Zeichen wie €, ß, ö, ô etc...";
zu komprimieren. Konkret stelle ich mir dabei zwei Funktionen compress(str) und uncompress(str) vor, die jeweils einen String zurückgeben können.

Dann könnte man mit
var compressed = compress(myString);
den String komprimieren und mittels
var uncompressed = uncompress(compressed);
wieder dekomprimieren.

Weiß jemand, ob es diesbezüglich bereits etwas im Web gibt?
Nett wäre eine LGPL-konforme Lizenz, also beispielsweise LGPL oder eine BSD-Lizenz.

Wenn nein: Wie könnte man dies realisieren, und welcher Komprimieralgorithmus würde sich anbieten?
Der Nachteil in JavaScript ist ja dass man im normalen Zeichen-Modus operieren muss.

Falls eine derartige Kompression nicht oder nur schwer zu realisieren ist, werde ich die Daten auf eine eigene Weise zu komprimieren versuchen. Da das Format der Daten ungefähr bekannt ist (Folge von Wörtern, die alle kleingeschrieben sind) könnte man den Wörtern Indizes verpassen. Je häufiger das Wort vorkommt desto kleiner die Zahl, und dann wird der String als Array von Zahlen abspeichert.
Dennoch wäre ein effektiver allgemeingültiger Komprimieralgorithmus vorzuziehen.

Grüße

Marc Reichelt || http://www.marcreichelt.de/

[Bio]

Sup!

Tja... das Problem scheint zu sein, dass man ja normalerweise sowohl den Server als auch den Client dazu bringen kann, die Daten mit gzip komprimiert zu übertragen; darum scheinen Kompressions-Libraries für JavaScript sehr selten zu sein ;-)

Was relativ einfach gehen sollte wäre, per JavaScript auf ein Java-Applet zuzugreifen, dass dann mit der vollen Power einer hunderte Megabyte großen JVM im Rücken das Kompressions-Problem relativ leicht bewältigen dürfte.
Lokal ein Java-Applet rumliegen zu haben sollte ja möglich sein?

Gruesse,

Bio

[Marc Reichelt]

Hallo Bio,

Was relativ einfach gehen sollte wäre, per JavaScript auf ein Java-Applet zuzugreifen, dass dann mit der vollen Power einer hunderte Megabyte großen JVM im Rücken das Kompressions-Problem relativ leicht bewältigen dürfte.
Lokal ein Java-Applet rumliegen zu haben sollte ja möglich sein?

Ja, das ist in der Tat möglich. Allerdings soll die Suche komplett mit JS funktionieren (Java keine Voraussetzung sein), und ein Applet braucht IMHO zu lange um zu laden.
Natürlich wäre Java für die Suche auch schöner, aber man kann nicht alles haben.

Die von Anfängern oftmals getroffene Annahme Java == JavaScript gilt in der Realität leider nicht. ;-)

Grüße

Marc Reichelt || http://www.marcreichelt.de/

[plan_B]

Hallo,

beim googlen ist mir dieser Link aufgefallen, eine reine js-Lösung: Huffman JavaScript Compression

Gruß plan_B

[LanX²]

Hallo

beim googlen ist mir dieser Link aufgefallen, eine reine js-Lösung: Huffman JavaScript Compression

Cool, mit selbstentpackendem Coe, allerdings ne Kompression von 15% find ich eher mau... :(

Gruß
  LanX

[Alexander (HH)]

Moin Moin!

Gegenfragen:

1. Kennst Du die Javascript-basierende offline-Suche in SelfHTML 8.x? Wäre die vielleicht hilfreich?

2. Warum willst Du die Dokumente komprimieren? Geht der Platz auf Deiner Festplatte zur Neige oder bist Du durch irgendein kleineres Medium (Floppy, ZIP-Drive, USB-Stick, CDROM) im Platz oder im Datendurchsatz beschränkt?

3. Dir ist klar, dass Du mit der Kompression Platz gegen Rechenzeit tauschst? Insbesondere Bit-Operationen, die Du zur Kompression brauchst, sind in Javascript umständlich und alles andere als schnell. Das könnte auf einem schwachen Rechner mit großen Datenmengen schonmal zu komatösem Verhalten führen.

Alexander

[Marc Reichelt]

Hallo Alexander,

1. Kennst Du die Javascript-basierende offline-Suche in SelfHTML 8.x? Wäre die vielleicht hilfreich?

Kenne ich. Ich programmiere am Nachfolger. ;-)
Daher kann ich den Code aus dem Vorgänger auch nicht verwenden (proprietär).

2. Warum willst Du die Dokumente komprimieren? Geht der Platz auf Deiner Festplatte zur Neige oder bist Du durch irgendein kleineres Medium (Floppy, ZIP-Drive, USB-Stick, CDROM) im Platz oder im Datendurchsatz beschränkt?

Es geht um größere Datenmengen (Volltext-Index) der neuen Suche.
Die Index-Dateien werden sowieso standardmäßig in der SELFHTML-Zip-Datei übertragen und damit vermutlich schon besser komprimiert als jeder JS-Algorithmus es könnte.
Die Suche wird als SourceForge-Projekt realisiert und soll damit auch bei anderen Projekten laufen (beispielsweise Offline-Dokumentationen, Webseiten auf CDROM oder Mini-CDROM, Diskette wohl eher weniger), wo teilweise der Speicherplatz recht begrenzt ist.

3. Dir ist klar, dass Du mit der Kompression Platz gegen Rechenzeit tauschst? Insbesondere Bit-Operationen, die Du zur Kompression brauchst, sind in Javascript umständlich und alles andere als schnell. Das könnte auf einem schwachen Rechner mit großen Datenmengen schonmal zu komatösem Verhalten führen.

Ja, dessen bin ich mir bewusst.
Genau deshalb gibt es zwei Indizes: Einen für die schnelle Suche (Präfix-basiert) und einen für den Volltextindex. Beide Indizes werden jeweils schön auf mehrere Dateien verteilt und dann erst nach Bedarf nachgeladen.

Der JS-Kompressionsalgorithmus soll dafür sorgen, dass die JS-Dateien des Volltextindexes auch im dekomprimierten Zustand nicht allzugroß werden.

Da der Volltextindex nur für die Volltextsuche (beispielsweise die feste Wortfolge "dies ist ein" in "Dies ist ein toller Film") gedacht ist, und er den Gesamtindex auf das 10fache des ursprünglich für die normale Suche benötigten Indexes vergrößert, bin ich dafür dieses Feature fallen zu lassen und stattdessen auf die Online-Suche zu verweisen.

Grüße

Marc Reichelt || http://www.marcreichelt.de/

[LanX²]

Hallo Marc,

erst mal grundsätzlich, hast du alle Möglichkeiten abgegrast das entzippen zu deligieren? document.open() oder xmlhttprequest oder was auch immer einen MimeType als Argument mitnimmt, mit sowas wie "x-zip-encodig" (?) oder ähnlichem aufzurufen?

Ansonsten ein plugin nutzen? Java-apletts oder flash könnten sowas eingebaut haben, und erlauben Kommunikation mit JS

Da das Format der Daten ungefähr bekannt ist (Folge von Wörtern, die alle kleingeschrieben sind) könnte man den Wörtern Indizes verpassen. Je häufiger das Wort vorkommt desto kleiner die Zahl, und dann wird der String als Array von Zahlen abspeichert.

Was du da beschreibst hört sich sehr nach einer Huffmann-Codierung an, blos dass die Wörter das Alphabet sind.

Beispiel: Nur 3 Wörter, zu 50% "Eins" (0) zu je 25% "Zwei" (10) und "Drei" (11), dann könntest du die geklammerten Bitfolgen nehmen

0110010 wäre also Eins Drei Eins Eins Zwei

Also 1,5 Bit statt 4 Byte pro Wort.

wie du siehst wären das aber nur 7 Bit und du müsstest shiften! Um dieses zeitintensive shiften eventuell ganz zu vermeiden könntest du mit geshiftetetn Tabellen a 256 Einträge auskommen.

Erster Schritt:
Tab[0][01100101]=> Decode+="Eins Drei Eins Eins Zwei" Carry=1
Tab[0][01100100]=> Decode+="Eins Drei Eins Eins Zwei" Carry=0
...

Zwoter Schritt;
Tab[Carry][Byte2] => Decode+="..." Carry=...

usw.

Die Tabelle könnte in Extremfällen auch noch größer werden, abhängig von der größe des Wortschatzes.

Statt sei vorzukalkulieren könnstest du sie auch erst von JS dynamisch generieren lassen. Eventuell wären sogar Hashes besser, wenn die Tabellen dünn besetzt werden.

der Zeitbedarf deines Decoders läge also bei der Zeit die Tabelle anzulegen + Bytezahl der Nachricht * Tabellenzugriffe!

Weiter oben hat dir PlanB auch einen Huffmandecoder gegooglet, aber der arbeitet wahrscheinlich auf Characterebene. Da die Zahl der Buchtsaben größenmäßig bei 30-40 liegen bräuchtest du dann auch nur kleinere Tabellen.  Wenn der Wortschatz nicht begrenzbar ist, hättest du auf Silbenebene die beste Kompression! Es gibt für sowas Häufigkeitstabellen.

Soweit die Theorie, ob sichs lohnt hängt natürlich von der genauen Natur deiner Daten ab...

Tschau
  LanX

[LanX²]

Eventuell wären sogar Hashes besser, wenn die Tabellen dünn besetzt werden.

obwohl bei JS könnte das Jacke wie Hose sein, wenn die Compiler nicht optimiert ist, dann sind alle Arrays intern sowieso als Hashes realisiert.

[molily]

Hallo,

obwohl bei JS könnte das Jacke wie Hose sein, wenn die Compiler nicht optimiert ist, dann sind alle Arrays intern sowieso als Hashes realisiert.

Sind sie ohnehin, das hatten wir doch letztens.

Mathias

[KurtZ]

Kurtz gegrüßt

Sind sie ohnehin, das hatten wir doch letztens.

Naja, ein  Compiler könnte ja *theoretisch* zwecks Tuning numerische Keys in einem echtes Array ablegen, sodass sich diese Optimierung lohnen *könnte* ...

Allerdings wohl nicht im Mozilla

  
x=[];  
rep=10000;  
x[0]="1";  
x.t0="2";  
start1=Date.now();  
  
for (y="",i=0;i<rep;i++) {  
  y=x[0];  
}  
  
start2=Date.now();  
  
for (z="",i=0;i<rep;i++) {  
  z=x["t0"];  
}  
  
end=Date.now();  
  
alert((start2-start1)+" "+(end-start2));  

t0 war sogar schneller als 0

Grüße
 Kurt

[molily]

Hallo,

Naja, ein  Compiler könnte ja *theoretisch* zwecks Tuning numerische Keys in einem echtes Array ablegen, sodass sich diese Optimierung lohnen *könnte* ...

Achso, stimmt.

Mathias

[KurtZ]

Kurtz gegrüßt

wie du siehst wären das aber nur 7 Bit und du müsstest shiften! Um dieses zeitintensive shiften eventuell ganz zu vermeiden könntest du mit geshiftetetn Tabellen a 256 Einträge auskommen.

man könnte ja auch 7 gerade sein lassen, in dem man auf den Übertrag verzichtet so wie man bei Farbcodierungen auf mit 16 Bit ein Bit auslässt, udn immer rund anfängt.

Gut, ie Kompressionsrate wäre zwar schlechter aber man bräuchte weniger Tabellen und Operationen.

aber ich glaube nicht das lookups in JS viel schneller als shiften ist, in meinem Benchmark auf Mozilla shiftet es sich 25% schneller als das Ergebnis nachzuschlagen.

  
  
x=[];  
rep=10000;  
u=255;  
x[u]=1;  
  
start1=Date.now();  
  
for (y="",i=0;i<rep;i++) {  
  y=u>>7  
}  
  
start2=Date.now();  
  
for (z="",i=0;i<rep;i++) {  
  z=x[u];  
}  
  
end=Date.now();  
  
alert((start2-start1)/(end-start2));  
alert(y);  
alert(z);  

Also lieber den Übertrag in den nächsten key reinshiften und gleich eine 16bit statt 8bit Tabelle anlegen, das vereinfacht und beschleunigt die Dekodierung doch deutlich. :)

Die Tabelle könnte in Extremfällen auch noch größer werden, abhängig von der größe des Wortschatzes.

Hmm da müsste uns Marc schon mehr Infos geben...

Grüße
 Kurt

[Marc Reichelt]

Hallo LanX²,

erst mal grundsätzlich, hast du alle Möglichkeiten abgegrast das entzippen zu deligieren? document.open() oder xmlhttprequest oder was auch immer einen MimeType als Argument mitnimmt, mit sowas wie "x-zip-encodig" (?) oder ähnlichem aufzurufen?

Nein. Ich bin mir aber fast sicher, dass dies nicht in allen neueren Browsern funktioniert.

Ansonsten ein plugin nutzen? Java-apletts oder flash könnten sowas eingebaut haben, und erlauben Kommunikation mit JS

Plugin fällt auch aus - das Ganze soll rein JS-basiert laufen.

Was du da beschreibst hört sich sehr nach einer Huffmann-Codierung an, blos dass die Wörter das Alphabet sind.

Ganz genau. :-)
Ich habe aber durch deinen und plan_Bs Vorschlag erkennen müssen dass eine Kompression in JavaScript kein gutes Geschwindigkeit/Kompressionsrate-Verhältnis hat, und das Laden einer unkomprimierten JS-Datei mehr Sinn macht (wenn diese nicht zu groß ist - aber das kann man durch Splitten ändern).

Mir ging es in diesem Thread einfach interessehalber darum, ob es effiziente Komprimieralgorithmen in JavaScript gibt und wie diese aussehen.
Huffman kenne ich und hätte ich auch selbst implementieren können, weiß aber aus Erfahrung dass die Kompressionsrate hier i.d.R. nicht sehr hoch ist.

Vielen Dank an alle für die Beiträge!

Grüße

Marc Reichelt || http://www.marcreichelt.de/

[LanX]

Hi

Geschwindigkeit/Kompressionsrate-Verhältnis hat, und das Laden einer unkomprimierten JS-Datei mehr Sinn macht (wenn diese nicht zu groß ist - aber das kann man durch Splitten ändern).

So macht es die alte Suche AFAIK auch.

Gibt es denn technische Gründe die alte Self-JS-Suche abzulösen?

Selfhtml sollte doch wohl kein schnelleres Wachstum haben, als die Rechnergeschwindigkeiten (Verdopplung alle 18 Monate?).

Mir ging es in diesem Thread einfach interessehalber darum, ob es effiziente Komprimieralgorithmen in JavaScript gibt und wie diese aussehen.
Huffman kenne ich und hätte ich auch selbst implementieren können, weiß aber aus Erfahrung dass die Kompressionsrate hier i.d.R. nicht sehr hoch ist.

naja ... also Huffmann komprimiert ein gewähltes Alphabet eigentlich nahe am theoretischen Optimum. Und auch nur "nahe" weil man Bits nicht noch weiter  unterteilen kann. (sowas meine ich an deiner Uni noch in INF1 bewiesen bekommen zu haben)

Die Kunst von Zip,Gzip, usw besteht IMHO darin das geeigneste Alphabet auszuwählen (Silben), und sowas könnte hier ja serverseitig geschehen.

So long!
 LanX

[KurtZ]

Kurtz gegrüßt

für eine Offline-Suche würde ich gerne Dokumente komprimiert abspeichern können. Natürlich könnte ein Server eine gzip-komprimierte JavaScript-Datei an den Browser senden. Dies fällt allerdings flach, da die JS-Dateien offline eingebunden werden müssen.

hast du denn ein Platzproblem auf der Platte oder willst du soviele Daten wie möglich für deine Suche im RAM halten? Falls ersteres gilt will ich nicht wissen wie lange JS braucht um all diese Daten dann zu dekoden.

Bei letzterem würde sich anbieten die Sachen in Pakete aufzusplitten, du suchst zuerst in eienr Masterdatei, die dich auf die richtigen Unterdateien verweist wo du mehr Infos findest.

ich könnte mir vorstellen das lokale Plattenzugriffe  billiger sind als ein Dekompressing in JS!

Grüße
 Kurt