proggen.org

Hallo,
ich möchte aus einer Datei lesen und das ganze im RAM als Byte-Array speichern.

Nun kommt es mir aber eigentlich gar nicht auf die Bytes, sondern auf die Bits an.
Mich interessieren immer 4 bis 7 Bits, die für mich dann eine Zahl darstellen.
An und für sich, kann man mittels Bitmanipulation natürlich auch dies aus dem Bytearray auslesen.
Bei meinem Sachverhalt geht es allerdigs um Rechenzeit und Speicherkapazität, sodass es am besten wäre, ich hätte wirklich nur ein Bit-Array aus dem ich dann immer soviele Bytes auslese, wie ich gerade brauche.

Wie kann ich das Anstellen?
Gibt es soetwas wie ein Bit-Array?
Oder kann ich einfach ein Datentyp definieren, der z.B. nur 4 Bits belegt?

Hintergrund: Es geht um ein Komprimierungsprogramm. Wenn da z.B. die Zahlen 200 201 stehen, wird daraus 200 ++. Die Plus-Plus Anweisung muss also kleiner als 1 Byte sein, damit es sich überhaupt lohnt. Denn die 201 war ja selbst schon 1 Byte groß und es macht ja nur sinn diese zu ersetzen, wenn es dadurch kleiner wird.
Aber ich möchte gar nicht über das Programm reden, ob es sinnvoll ist oder nicht sondern einzig und allein über das Problem mit den Bits.

Es gibt Bitfelder die in einer Struktur definiert sind, aber die sind langsam sowei ich weiß.
Andere Möglichkeiten sind mir nicht bekannt.

Da wirst du selbst Hand anlegen müssen

Ein paar Anregungen findest du uU hier:
http://www.proggen.org/forum/viewtopic.php?f=49&t=4629

Hier geht es darum, immer nur 2 Bits zu speichern.

canlot hat geschrieben:Es gibt Bitfelder die in einer Struktur definiert sind, aber die sind langsam sowei ich weiß.
Andere Möglichkeiten sind mir nicht bekannt.

Ja an Bitfelder hatte ich zunächst auch gedacht.

Dirty Oerti hat geschrieben:Da wirst du selbst Hand anlegen müssen

Ein paar Anregungen findest du uU hier:
viewtopic.php?f=49&t=4629

Ok, ich hab mir das mal durchgelesen. Ich denke ich speichere einfach als Bytearray und lese dann mittels einer Funktion immer soviel Bits aus, wie ich brauche. So verschwende ich keinen Speicher, keine Speichergeschwindigkeit, aber ein wenig Rechenzeit durch das ständige hin- und her gespringe.

Ich habe auch im Vorfeld überlegt, ob ich wirklich soetwas brauche. Aber ich habe mir in einem Hex Editor mal ein paar Dateien angeschaut. Und mir ist aufgefallen, dass oft, vorallem bei bereits komprimierten Dateien, Zahlen hintereinander stehen, die sich nur geringfügig unterscheiden. Und ich denke das lohnt sich vorallem bei größeren Dateien, wenn ich dann statt einem Byte nur ein halbes verwende, in dem ich nur die Differenz zum Vorgänger speichere.

Dir ist aber klar, dass wenn du nur ein halbes Byte verwendest, du den Rest logischerweise "aufrücken" lassen musst, sprich das nachfolgende Byte steht zur Hälfte mit im Byte, aus dem du nur die Hälfte liest und zur anderen Hälfte im Folgenden Byte. Ansonsten nützt das ja nichts

HerrKlinke hat geschrieben:Mich interessieren immer 4 bis 7 Bits, die für mich dann eine Zahl darstellen.
An und für sich, kann man mittels Bitmanipulation natürlich auch dies aus dem Bytearray auslesen.
Bei meinem Sachverhalt geht es allerdigs um Rechenzeit und Speicherkapazität, sodass es am besten wäre, ich hätte wirklich nur ein Bit-Array aus dem ich dann immer soviele Bytes auslese, wie ich gerade brauche.

Schreib Dir eine Klasse, die den Speicherbereich entsprechend addressiert?

HerrKlinke hat geschrieben:Oder kann ich einfach ein Datentyp definieren, der z.B. nur 4 Bits belegt?

Die kleinste vom Prozessor addressierbare Einheit ist 1 Byte. Alles andere musst Du selbst beschreiben.

HerrKlinke hat geschrieben:Hintergrund: Es geht um ein Komprimierungsprogramm. Wenn da z.B. die Zahlen 200 201 stehen, wird daraus 200 ++. Die Plus-Plus Anweisung muss also kleiner als 1 Byte sein, damit es sich überhaupt lohnt.

Wie kommst Du auf 200? Zahlen größer 127 sind schon mindestens 1 Byte groß.

HerrKlinke hat geschrieben:Denn die 201 war ja selbst schon 1 Byte groß und es macht ja nur sinn diese zu ersetzen, wenn es dadurch kleiner wird.
Aber ich möchte gar nicht über das Programm reden, ob es sinnvoll ist oder nicht sondern einzig und allein über das Problem mit den Bits.

Eine Komprimierung findet nur statt, wenn Du informationserhaltend arbeitest: auf Deutsch: man muss es wieder dekomprimieren können und zur gleichen Information kommen (bzw. bei JPG zu ähnlichen Informationen).

Für den Wert 200 brauchst Du 8 Byte. Es sind 8 Bit Information, unter der Bedingung, dass Du weißt, dass eine Information genau 8 Bit groß ist. Bei 32-Bit zahlen ist der Wert 200 32 Bit groß, um ihn genau von anderen 32-Bit Werten unterscheiden zu können.

Eine Information besteht also nicht nur aus dem Wert, sondern implizit auch aus der Darstellungsform, dem Datentyp.

Wenn Du Daten verlustfrei komprimieren willst, dann werden daraus nicht weniger Daten, sondern es werden daraus Daten, die in einem anderen Datentyp transformiert wurden, der Dir aber bekannt sein muss. Deswegen musst Du Dir merken, dass die Information nun in einem anderen Datentyp vorliegt. Wenn Du also ein einzelnes Byte "komprimieren" willst, dann könntest Du Zahlen > 200, die entsprechend dann von 0 bis 55 gehen in 6 Bit speichern. Wenn Du also weißt, dass jetzt 20433 Werte >200 kommen, könntest Du die maximale Differenz der Werte (maximal 56) in 6 Bit speichern und dir davor merken, dass die nächsten 20433 6-Bitzahlen auf 200 addiert werden müssten, um eine 8 Bit-Zahl zu ergeben. Diesen beschreibenen Header muss natürlich auch gespeichert werden, könnte sich lohnen, weil Du ja 20433 * 2 Bit, also etwa 5kB so sparen könntest.
Das ganze funktioniert aber nur, wenn dazwischen keine Zahlen < 200 vorkommen, sonst brauchst Du mehr Header, bzw. musst häufiger das Datenformat wechseln, was dann dazu führt, dass Du regelmäßig Header einfügen musst, was die Datei dann wieder größer macht.

Nichts anderes ist ein char-Array: Wenn Du weißt, dass alle Werte < 256 sind, kannst Du aus dem 32-Bit-Integer-Array ein 8-Bit-Array machen und somit 75% Platz sparen, wobei Du aber keine Information "komprimiert" hast, sondern sie lediglich in ein platzsparenderes Format überführt hast.

Dirty Oerti hat geschrieben:Dir ist aber klar, dass wenn du nur ein halbes Byte verwendest, du den Rest logischerweise "aufrücken" lassen musst, sprich das nachfolgende Byte steht zur Hälfte mit im Byte, aus dem du nur die Hälfte liest und zur anderen Hälfte im Folgenden Byte. Ansonsten nützt das ja nichts

Ja so habe ich auch gedacht^^

Xin hat geschrieben:Wie kommst Du auf 200? Zahlen größer 127 sind schon mindestens 1 Byte groß.

Mein Hex-Editor zeigt alles als unsigned char an.

Xin hat geschrieben:Wenn Du Daten verlustfrei komprimieren willst, dann werden daraus nicht weniger Daten, sondern es werden daraus Daten, die in einem anderen Datentyp transformiert wurden, der Dir aber bekannt sein muss. Deswegen musst Du Dir merken, dass die Information nun in einem anderen Datentyp vorliegt. Wenn Du also ein einzelnes Byte "komprimieren" willst, dann könntest Du Zahlen > 200, die entsprechend dann von 0 bis 55 gehen in 6 Bit speichern. Wenn Du also weißt, dass jetzt 20433 Werte >200 kommen, könntest Du die maximale Differenz der Werte (maximal 56) in 6 Bit speichern und dir davor merken, dass die nächsten 20433 6-Bitzahlen auf 200 addiert werden müssten, um eine 8 Bit-Zahl zu ergeben. Diesen beschreibenen Header muss natürlich auch gespeichert werden, könnte sich lohnen, weil Du ja 20433 * 2 Bit, also etwa 5kB so sparen könntest.

Genau das habe ich mir überlegt.
Ich möchte nämlich experimentieren, wie sehr es mir gelingt eine Datei "platz sparender" zu machen. Dazu möchte ich verschiedenste Systeme kombinieren.
Zunächst werden Dopplungen gesucht und als Wörterbuch indexiert.
Dann werden längere Ketten mit eingeschränktem Zahlenbereich gesucht, wie Xin das schon beschrieben hat.
Anschließend - und jetzt wirds interessant - wird nach beschreibbaren Zahlenfolgen gesucht.

Das letzte wird sicherlich das kniffligste. Ich meine eine Zahlenfolge von 1 2 3 4 5 6 7 8 9 10 ist ja einfach zu erfassen. Aber das Programm soll weitaus komplexere Zahlenfolgen erkennen und auch mit Ausreißern umgehen können.
Dann müssen auch noch die Header so klein gehalten werden, wie möglich und die Rechenzeiten gut ausgenutzt werden.
- und das finde ich alles sehr spannend.

Xin hat geschrieben:Schreib Dir eine Klasse, die den Speicherbereich entsprechend addressiert?

Kannst du da nochmal ein wenig drauf eingehen, ich verstehe es nicht ganz.

Ich wollte nur kurz anmerken, dass std::vector<bool> eine Spezialisierung ist, die sich genau mit diesem Problem beschäftigt. Ursprünglich gut gemeint, gibts da allerdings ein paar Probleme (Richtige Iteratoren...).
Für deine Anwendung könnte es aber auch funktionieren:
http://www.cplusplus.com/reference/stl/vector/
Edit: hier die Probleme von vector<bool>: http://www.gotw.ca/publications/N1211.pdf

HerrKlinke hat geschrieben:

Xin hat geschrieben:Wie kommst Du auf 200? Zahlen größer 127 sind schon mindestens 1 Byte groß.

Mein Hex-Editor zeigt alles als unsigned char an.

Alle unsigned chars sind 8 Bit groß. Zahlen bis einschließlich 127 brauchen maximal 7 Bits, um "unkodiert" im Binärsystem dargestellt zu werden. Alles darüber braucht mindestens 8 Bit. Die Grenze ist also bei 127 zu 128, 200 ist eine vollkommen willkürliche Zahl.

HerrKlinke hat geschrieben:

Xin hat geschrieben:Wenn Du also weißt, dass jetzt 20433 Werte >200 kommen, könntest Du die maximale Differenz der Werte (maximal 56) in 6 Bit speichern und dir davor merken, dass die nächsten 20433 6-Bitzahlen auf 200 addiert werden müssten, um eine 8 Bit-Zahl zu ergeben. Diesen beschreibenen Header muss natürlich auch gespeichert werden, könnte sich lohnen, weil Du ja 20433 * 2 Bit, also etwa 5kB so sparen könntest.

Genau das habe ich mir überlegt.
Ich möchte nämlich experimentieren, wie sehr es mir gelingt eine Datei "platz sparender" zu machen. Dazu möchte ich verschiedenste Systeme kombinieren.
Zunächst werden Dopplungen gesucht und als Wörterbuch indexiert.

Das funktioniert natürlich vorrangig bei Dateien, bei denen sich viele "Wörter" wiederholen. Aufpassen muss man dabei allerdings dass man nicht so kodiert, dass die seltenen Wörter dabei so groß kodiert werden müssen, dass sie mehr Platz verwenden, als die Indizierung spart.

HerrKlinke hat geschrieben:Dann werden längere Ketten mit eingeschränktem Zahlenbereich gesucht, wie Xin das schon beschrieben hat.
Anschließend - und jetzt wirds interessant - wird nach beschreibbaren Zahlenfolgen gesucht.

Schau Dir doch mal Ziv-Lempel-77 an, nur zur Übung und Inspiration.
Ich habe mal eine Implementation davon geschrieben und eigentlich auch vor, diese hier mal vorzustellen, aber das wird noch dauern.

HerrKlinke hat geschrieben:

Xin hat geschrieben:Schreib Dir eine Klasse, die den Speicherbereich entsprechend addressiert?

Kannst du da nochmal ein wenig drauf eingehen, ich verstehe es nicht ganz.

Wenn Du Daten unterhalb der Bytegrenze bearbeiten willst, musst Du entweder sehr sauberes C programmieren oder die Probleme in C++ in Klassen abstrahieren. Ich würde Dir hier raten, zwei Klassen zu schreiben, die Bit-Array-Items ausdrücken (eine Wert von 1 bis 32 Bit, inkl seiner Breite) und ein Bit-Array, dass Du Bit-Array-Item-Weise auslesen kannst. So dass Du sagen kannst, dass Du mal eben 3 Bit aus dem Array als Stream lesen kannst und beim Schreiben eben einen Wert formulieren kannst und ihn in definierter Breite an ein Bit-Array anhängen kannst.

Bevor Du also Daten komprimierst, rate ich dazu, Dir diese beiden Klassen zu schreiben.

AHH.
Ok, danke für die Tips. Das mit den Klassen wäre meine nächste Überlegung gewesen, vor der ich mich bereits gefürchtet habe^^