Komprimieren Sie eine kleine Menge von Daten
Ich habe ein Programm, wo ich generieren bitstreams, von etwa 80 bis 150 bits oder so, die würde ich gerne komprimieren, da ich verwandele Sie in eine Art von ASCII-Strings, so dass die Menschen übermitteln Sie herum.
Kennt jemand ein gutes, kostenloses bit-fähigen Kompressor, der vielleicht einen solchen stream? Mein Hauptproblem mit der "standard-Optionen" wird dieser stream sollte wirklich behandelt werden, als bit, nicht bytes, da sonst die Struktur verloren geht, und Ihre overhead-Sümpfe alle gewinnen.
Zusatz:
Den Gründen, die ich komprimieren will diesen streams ist, weil die Benutzer Los zu werden schneiden+einfügen, wahrscheinlich mit so etwas wie base64-Codierung, so speichern einige Daten hilfreich ist.
Hier ist ein Beispiel, für diejenigen, die es sehen möchten. Ich werde Formatierungen hinzuzufügen, um es einfacher zu Lesen ist:
110 110 - This is a 6x6 grid (the maximum is 7x7, so we only need 3 bits!)
000000
011110
010010
010010
011110
000000 - This is one layout grid
000000
000000
001000
000100
000000
000000 - This is the second layout grid
Nun Listen wir einige Stücke
010 11111111 - A piece is a 3-bit colour code, then an 8-bit list of 'on /off' bits.
001 10101010 - Another bit!
001 10101010 - Another, identical bit!
Der Grund, warum ich sagen, dies sollte berücksichtigt werden, "als bits' ist, dass es ist offensichtlich, Kompression Optionen betrachtet als bitstream (in bestimmten, in der Regel viele 0EN in der 'grid' s), die verschwinden, wenn man bedenkt es als eine byte-stream.
- Einfach nur neugierig, aber was meinst du mit "behandelt werden müssen, als bits". Ein 80-bit-string ist ein 10-byte-string, und kann als solche behandelt werden, bis Ihre Programm braucht, diese auch zu verwerten.
- Wenn Sie sagen, "damit die Menschen zu übertragen" meinst du, die Leute senden die Zeichenfolge einen Anruf, indem Sie es von hand irgendwo, etc. Du willst also eine für den Menschen lesbare version der bit-stream???
- kann diese bit-Blöcken aggregiert werden, und dann verschickt, oder Sie werden weitergeleitet/gesendet, sobald Sie verfügbar sind. Wenn Sie aggregiert werden können, werden Sie sehen, bessere Kompression denke ich, aber nicht sicher sind, was Sie zu erreichen versuchen.
- Was ist die Beziehung zwischen einem layout-raster und ein Stück? Sie zeigen eine Reihe von bits und einige Muster, aber wie funktioniert es alle zusammen binden? Erzählen Sie uns mehr über Ihre Verwendung, Ihre Bedeutung, was etwas, das der Benutzer würden, einfügen und kopieren Sie herum Aussehen würde, etc.?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Was hoffen Sie zu erreichen durch die Komprimierung von 150 bits? Es sei denn, Sie aggregieren mehrere dieser 19b Nachrichten, ich bin mir nicht sicher, was Sie hoffen, zu gewinnen. Ist es ein UI-Problem-wobei Sie möchten, dass Benutzer auf senden/empfangen "codes"?
Wie etwa base-64-Codierung? Dies wird nehmen binäre Daten und verwandeln Sie es in der codierten Zeichen für die einfache übertragung oder Eintragung.
Chris, vielen Dank für die Veröffentlichung diese Proben. Ich denke, der run-length encoding ist der Weg Sie gehen wollen. Das sollte ziemlich trivial zu implementieren.
http://en.wikipedia.org/wiki/Run-length_encoding
Wird gut funktionieren mit all diesen aufeinander folgenden 0 ' s.
Also der primäre Grund, zu komprimieren, diese Ketten, um Sie leichter zu schneiden und zu fügen? Macht Sinn; das klingt wie ein Interessantes Projekt.
Wenn Sie nur versuchen, um die Saiten mehr Menschen überschaubar, es klingt wie Sie sind alle gesetzt. Wenn Sie versuchen, komprimieren Sie, so dass Sie schneller übertragen über das Kabel, das ich denke, der Vorteil der Komprimierung von kleinen strings kann besiegt werden, indem andere TCP Themen wie MTU-Größen und alle, die. (Ich bin nicht dort erlebte, so nehmen Sie das Letzte Stück mit vielen Körnchen Salz)
Glück!
Ich würde vermuten, dass kein allgemeiner Algorithmus wird Ihnen viel Kompression für diese Art von Daten.
Ihre beste Wette ist, um analysieren Sie die Struktur Ihrer Daten und versuchen Sie zu finden, eine eigene Kompressions-Algorithmus oder möglicherweise anpassen einer vorhandenen (vielleicht mit einem pre-filled Wörterbuch oder so ähnlich).
Ich würde vorschlagen, Sie schauen in zlib. Es ist zum Download und die Lizenz erlaubt es Ihnen, verwenden Sie es für so ziemlich jedes Projekt. Ein wichtiger Punkt ist, dass es weit verbreitet ist, und daher gut ausgetestet. Wenn Ihre Daten wichtig ist, die Sie nicht wollen, um zu Debuggen ungerade Grenzfälle in ein hombrew-Algorithmus zufällig Termine in der Zukunft.
Ich habe Durcheinander herum mit ihm ein wenig, und es nicht erlaubt, eine stream-orientierte Kompression. Ich bin nicht wirklich sicher, wie gut es ist, wenn Sie nur füttern Sie eine kleine Menge von Daten zu einer Zeit aber. Verlustfreie Kompression neigt dazu, die Arbeit von der Suche und Beseitigung Muster, und es wird nicht eine Menge von mustern zu finden, wenn Sie füttern es etwas klein wie 12 Byte zu einem Zeitpunkt.
Ich bin nicht voing Juans Antwort, weil auch er empfiehlt die Verwendung von GIF die eine verlustbehaftete Kompression. Sie geben nicht viel info, aber ich vermute, Sie wollen keine Kompression-format, die tatsächlich verliert Daten. Die meisten gängigen Grafik -, audio-und video-Kompression algrithms sind verlustbehaftet; Sie verlassen sich auf die Fähigkeit der menschlichen Sinne zu nehmen, in Bild oder Ton richtig mit einige der ursprünglichen Informationen entfernt oder verändert etwas.
Da die Ströme so klein sind, können Sie nach ein paar von Ihnen hier?
Außerdem sind Sie sicher, daß genügend Redundanz in diese Ströme auch zu ermöglichen Kompression? Gibt es sich wiederholende Blöcke von Daten?
Es ist ein longshot, aber ohne konkrete Antworten, vielleicht möchten Sie sich in der ROM-Szene und prüfen Sie, wie Sie Zeichenketten, die komprimiert wurden, in der Patrone-basierte RPG-Spiele wie "Chrono Trigger" oder "Final Fantasy III." Ich weiß, dass die text-strings komprimiert wurden in diese Spiele (bytes waren so kostbar in jenen Tagen) und entwirren das Schema erwies sich als eine Herausforderung für Hacker. Das ist die nur Sache, die mir in den Sinn kam, wenn Sie erwähnt viele kleine strings, komprimiert werden.
Ihr root-problem könnte bleiben, obwohl. Ich könnte mir vorstellen, dass das Kompressionsverfahren in diesen ROMs genutzt Redundanz über viele strings (ie, wenn "Timbuktu" traten in 58 verschiedenen Saiten) und nicht so viel in einem einzigen stream.
Mein Erster Vorschlag, dass man sich in Reihe Kodierung. Statt
1: komprimieren von bit-Daten in binäre Daten und dann
2: Kodierung von binären Daten in base64-ASCII-Daten,
könnte man pack die bits direkt in den Bereich 0-
N
(woN
ist die Anzahl der druckbaren Zeichen, die Sie mit minus 1) und dann einen Toten-einfache Zuordnung.Mein zweiter Vorschlag ist, dass Sie die filter-Methoden PNG und überlegen, ob ähnliche Methoden könnten verwendet werden, um zu Rendern, Ihre Daten besser komprimierbar. Es ist schwierig zu sagen, aus nur zwei Beispiel-layout grids, aber es scheint sehr wahrscheinlich aus dem ersten grid, dass eine Methode wie "Vorhersagen jedes pixel, basierend auf seine Nachbarn oben und nach Links, und dann konvertieren jedes pixels ist 0, wenn es erfüllt seine Vorhersage und 1, wenn es trotzt mit seiner Vorhersage" könnte Ihnen viel einheitlicher Satz von Daten, und damit eine höhere Kompression.
CCITT ist Gruppe 3 und Gruppe 4 lossless-Codierung-Schemata, die verwendet komprimieren in G3-und G4-TIFF entwickelt wurden mit binären Daten, die in mind. G4 TIFF-schwarz-weiß-Bilder in der Regel verwendet für die OCR-ing und Faxgeräte. Ein anderes einfaches Schema, das in den Sinn kommt ist RLE.
JBIG geben könnte, was Sie brauchen.
http://en.wikipedia.org/wiki/JBIG
http://www.jpeg.org/jbig/index.html
http://www.cl.cam.ac.uk/~mgk25/jbigkit/
JBIG verwendet wird, um komprimiert 1 bpp fax-Bilder.
Die zlib-Kompression (vielleicht der gleiche Algorithmus als gzip) ist kostenlos. Es hat ein paar Einstellungen, aber ich bin nicht sicher, wie viel Sie sparen können, es sei denn, es gibt einige regelmäßige Muster, um Ihre bits.
Da die png-und gif-Grafikdateien sind im wesentlichen Darstellungen von bit-mustern, vielleicht finden Sie den Kompressions-Algorithmus, die Sie verwenden.
Was Sie wollen, ist verlustfreien binären Komprimierung. Ich bin sicher, es gibt Papiere oder web-Artikel, wenn nicht Tonnen von anderen Ressourcen gibt. Google diese Begriffe und ich vermute, dass Sie bekommen, was Sie brauchen.
Wie viel Daten sprechen Sie? Ist die Pfeife klein ist oder der Durchsatz so hoch, dass Sie zu komprimieren?
Im Nachhinein, Ihre Daten so klein, dass Sie wahrscheinlich nicht gehen, um lohnenswerte Gewinne, es sei denn, Sie analysieren Sie Ihren traffic und machen Sie Ihre eigene "Kompression", das ist im Grunde nur ein mapping/hash von bekannten bit-Muster.
als jemand anderes sagte, nach ein paar Beispieldaten und es ist wahrscheinlich besser beraten danach.
Habe ich den gleichen Gedanken hatte wie Tim - wie eine kleine Menge von Daten kaum Wert scheint komprimieren. Als eine Angelegenheit von der Tat, würde ich vorschlagen, dass das, was Sie wirklich wollen, ist eine Art von ascii-Codierung-Methode, wie uuencode oder mime-Codierung (aka "Base64").
Nur hinzufügen, was bereits gesagt wurde, nicht "komprimieren eine kleine Datenmenge, die von" intrinsisch ein bisschen sinnlos? Wenn Sie könnten, näher auf die Daten, die Plattform oder die verwendet, die helfen könnten.
Als für die bits-vs-ascii - ich bin mir nicht ganz sicher, was Sie bekommen, aber wie erwähnt von Michael, Base64 bietet eine Möglichkeit, beliebige binäre mehr freundlich.
Beachten Sie, dass alle Umwandlung von Binär in ascii ist das Gegenteil von Kompression.