Komprimierung von Byte-Kombinationen

#1
Hallo.

Kurz zu mir: Ich befasse mich seit einigen Jahren nach Lust und Laune mit MQL4. Den heiligen Gral hab ich leider noch nicht gefunden. :rolleyes: Es geht jetzt aber nicht darum, sondern ich schreibe hier meine Idee auf, weil C/C++, und was es nicht alles gibt, MQL4 sehr ähnlich ist, bzw. Letzteres auf C basiert.

Hab mal aufgeschnappt, dass ein inzwischen verstorbener Wissenschaftler oder sowas einen Weg gekannt haben soll, jegliche Art von Daten auf ungefähr 1/100 zusammen zu quetschen. Aber er hat anscheinend sein Geheimnis mit ins Grab genommen...

Ich hab drüber nach gedacht und eine Idee dazu. Aber ich bin vorsichtig gesagt alles Andere als Profi-Programmierer und hab keine Ahnung, ob und wie das überhaupt funktionieren könnte. Von Mathe versteh ich auch nicht allzu viel. Ich versuch jetzt mal, es zu erklären.

Wie wir Alle wissen, besteht ein typisches "Windows-Byte" heutzutage aus 8 Bits, also aus 8 Stellen, von denen Jede 2 Werte, 0 oder 1 einnehmen kann. Das heißt, dass ein Byte eine von 256 Variationen aus Nullen und Einsen sein kann.

Theoretisch könnte man jetzt jede dieser Varianten mit 256 multiplizieren, bzw. das Ergebnis wieder durch 256 teilen, um die Anordnung der 0en und 1en in Werte umzuwandeln, bzw. später diese Werte wieder in Bytes zurück zu "verwandeln". Aber 1 einziges Byte zu komprimieren, ist natürlich nicht besonders sinnvoll.

Anders siehts natürlich bei großen Folgen von Bytes aus.

1 Byte kann ja immer nur eine von 256 möglichen Varianten sein. Bei 2 Bytes sind es dann 256 x 256 Möglichkeiten, 3 Bytes können nur eine Kombination von 256 x 256 x 256 Möglichen 1 und 0 Folgen sein, usw. und so fort. Je nach dem, mit was für Zahlen der Computer und die Software umgehn kann, könnte man theoretisch unzählige Byte-Kombinationen in Zahlen in 256er-Schritten multiplizieren und dann wieder in 1en und 0en zurück dividieren.

Aber da ich mich mit Mathe wie gesagt nicht besonders gut auskenne... :(
 

German

Well-Known Member
c-b Experte
#2
Ich weiß ehrlich gesagt nicht mal wo du hindenkst. Aber rechne doch einfach mal 256 x 256 und dann schau dir an wie viele Bytes du brauchen würdest um diese Zahl zu speichern ;) (Dazu braucht man kein Mathe-Genie zu sein.)
 

-AB-

R.I.P.
c-b Team
c-b Experte
#3
Hab mal aufgeschnappt, dass ein inzwischen verstorbener Wissenschaftler oder sowas einen Weg gekannt haben soll, jegliche Art von Daten auf ungefähr 1/100 zusammen zu quetschen. Aber er hat anscheinend sein Geheimnis mit ins Grab genommen...
Hmmm, ich rate mal, Claude Shannon? Eventuell auch erst David Huffman, aber die grundlegende Theorie ist von Shannon.

Du scheinst davon auszugehen, dass eine "Zahl" im Computer atomar abgelegt wird. (Und, dass sie beliebig groß werden kann.) Dem ist natürlich nicht so. Eine Zahl besteht ja auch nur aus Bytes, je nachdem aus einem, zwei, vier oder acht, und in jeder Zahl lassen sich dann exakt so viele Möglichkeiten speichern wie... naja, wie in den einzelnen Bytes, ganz ohne rumrechnen.

Wenn eine beliebige Zahl oder ein Bruch nur einen "Speicherplatz" belegen würde, hättest du Recht. Da gibt es ein Beispiel mit einem Alien, dass auf der Erde landet, und gerne jede Menge Wissen wieder nach Hause mitnehmen möchte - aber er kann gerade mal 1 Kilo Nutzlast mitnehmen...

Er nimmt sich also einen 1-Meter langen (kann auch ein Alienfuß sein) Stab und denkt sich: Ich codiere jetzt erstmal Wikipedia.... alle Buchstaben zu Zahlen, dann hat er etwas wie 89488575695973975....... - dann teilt er 1 durch diese Zahl, und erhält einen bruch zwischen 0 und 1. Jetzt nur noch den Stab auf die entsprechende Länge zusägen, fertig. Zuhause dann exakt nachmessen, wie lang der Stab ist, und sämtliche Information ist wieder vorhanden. Problem gelöst! Dann nimmt er noch das gesamte Internet, codierte DNA aller Lebewesen, usw usw mit....

Natürlich endet man auch hier vor dem Problem der Granularität - Der Stab ist eben nicht mathematisch exakt, sondern nur eine grobe, atomare Annäherung. Und das gleiche Problem hast du bei deinen Bytes - auch eine Fließkommazahl ist nicht durchgehend definiert, sondern hat nur eine begrenzte Anzahl möglicher Zustände.


Komprimieren kannst du nur, was sich wiederholt, also: Wo eine Art Muster ist. Ein Maß dafür, wie "Musterbehaftet" eine Menge von Zahlen ist, ist z.B. durch die Entropie gegeben. Ist die Entropie hoch, liegt eine Art Ungleichgewicht vor, also z.B. "mehr Nullen als Einsen" - diese Information kann dann verwendet werden, die Datenmenge geschickter zu codieren, so dass am Ende kein Muster mehr vorhanden ist.
 
Gefällt mir: Mat

German

Well-Known Member
c-b Experte
#4
So ist es. Der Screenshot ist der Anfang eines 32Bit Windows Explorers im Hex Editor. Sofort auffällig sind die vielen aufeinanderfolgenden Nullbytes. Das lässt sich jeweils auf den Wert des Bytes (0) in Verbindung mit der Anzahl reduzieren. Auch der markierte Bereich ist eine Folge von 3 x vier gleichen Bytes und ließe sich entsprechend behandeln.
explorer.png
 
#5
Hab mal in OpenOffice Calc nen kurzen Test mit x256 gemacht. Schon bei 3 Bytes war das Ergebnis nicht mehr lesbar. o_O

Allerdings ließen sich 1 & 2 Bytes jeweils völlig verlustfrei wieder zurück "dividieren". Vielleicht wars auch Multiplikation, wie gesagt bin ich nicht gerade Mathe-Professor... :confused:

Aber irgendeinen Weg gibts bestimmt, die Bytes in normale Zahlen umzuwandeln und mit Multiplikation oder was auch immer in Werte umzurechnen, die sich dann wieder problemlos zu Bytes zurück rechnen lassen.

Wie wär statt x256

x2 x2 x2 ...

Ein Bit kann ja nur einen von 2 Werten anzeigen...
 

-AB-

R.I.P.
c-b Team
c-b Experte
#6
Aber irgendeinen Weg gibts bestimmt, die Bytes in normale Zahlen umzuwandeln und mit Multiplikation oder was auch immer in Werte umzurechnen, die sich dann wieder problemlos zu Bytes zurück rechnen lassen.
...Dir scheint nicht klar zu sein, dass du einfach *256 rechnest, und dann wieder durch 256 teilst. Wie willst du auf die Art Daten sparen? ;)

Ach ja, außerdem *sind* Bytes nur normale Zahlen. Bloß ist ein Byte eben 8 Bit, aber trotzdem fundamental nicht unterschiedlich zu, sagen wir, einer Dezimalzahl von 2 Stellen:
00 ... 99 - nennen wir sie "Dyte" (decimal byte)

100 Kombinationen kann ich in einem Dyte ablegen (analog zu 256 in einem Byte) - von 0 bis 99. Wenn ich 100 ablegen will, brauche ich ein weiteres "Dyte": 01 00 - "100".

Klar kann ich auch hingehen und meine Dytes 08 15 mit 100 multiplizieren. Dann erhalte ich eben 08 15 00. (oder 81500) Und dann kann ich wieder durch 100 teilen, und habe meine 08 15 zurück. Aber Daten spare ich da nirgendwo.
 
#7
Wie gesagt, ich bin nicht gerade Compjudda-Experte...

Aber worum es eigentlich geht:

z.B. kann wie gesagt eine Reihe von z.B. 256 aufeinander folgenden Bytes nur eine Möglichkeit der begrenzten, möglichen Kombinationen sein. Es geht ja z.B. nur

0 000 0001
0 000 0010
0 000 0100
...

oder

0 000 0001
0 000 0011
0 000 0111
...

Diese möglichen Kombinationen, die jeweils nur eine von einer begrenzten und berechenbaren Menge an möglichen Kombinationen sein kann, die sozusagen in verkürzte Zahlen- oder Buchstaben- Codes oder Beides zu "verschlüsseln", das ist das Ziel. Nicht einfach irgendwas mit 256 multiplizieren oder dividieren...
 

-AB-

R.I.P.
c-b Team
c-b Experte
#8
Das sind Bits, keine Bytes, aber egal.

nimm mal nur 2 Bits:

0 0
0 1
1 0
1 1

Das sind die Möglichkeiten. Vier Stück. (2 Bits, je 2 Möglichkeiten - 2^2 = 4)
Jetzt kannst du natürlich hingehen und die Durchnummerieren:

0 | 0 0
1 | 0 1
2 | 1 0
3 | 1 1

Und statt der Bitfolge "1 0" quasi die Zahl 2 verwenden. Und wenn du die Zahl 2 dann speichern willst, landest du... bei der Kombination "1 0".

ann wie gesagt eine Reihe von z.B. 256 aufeinander folgenden Bytes nur eine Möglichkeit der begrenzten, möglichen Kombinationen sein.
Klar, aber diese Reihe ist schon die kürzeste Darstellung exakt dieser Information (solang wir kein weiteres Wissen haben.)

Das Aufteilen in Bytes erzeugt keine Redundanz. (*) Sprich, nur, weil etwas "in Bytes" dargestellt ist, heißt es nicht, dass man es irgendwie "kleiner" speichern kann.

Versuch doch mal, die Zahlen von 0 bis 100 (oder 99) kürzer darzustellen. :) Gibt auch nur eine begrenzte Anzahl an möglichen Zahlen.


(*) Stimmt nicht ganz, wenn z.B. nicht sämtliche Möglichkeiten verwendet werden. Sagen wir, eine Art "Telegramm"-Text kommt mit 26 Buchstaben, Leerzeichen und ",.-" aus - dann brauchen wir keine 8 Bit pro Buchstabe mehr, weil die meisten Bits nur 0 wären; stattdessen könnte man hier auf eine 5-Bit Darstellung wechseln - 2^5 = 32 mögliche Buchstaben.

Aber wenn theoretisch sämtliche Möglichkeiten ausgereizt werden können - nicht unbedingt in Text, aber in Programmcode, Bildern, zufälligen Daten - dann kann man sich nur noch Häufigkeitsverteilungen ansehen, und versuchen, weniger oder häufiger auftauchende Zahlenfolgen anders zu codieren.
 

asc

Well-Known Member
c-b Experte
#9
Ich glaube hier fehlt das generelle Verständnis, dass die Informationen (Buchstaben/Zahlen/usw.) immer als Bytes gespeichert werden. Man kann nicht einfach statt 0000 0010 eine 2 als Dezimalzahl in eine Datei schreiben, bzw. kann man schon nur steht dann halt wieder 0000 0010 drin ...

Bytes sind auch nur Zahlen, nur eben auf Basis-2 statt Basis-10
 

lord_haffi

Well-Known Member
c-b Experte
#10
(*) Stimmt nicht ganz, wenn z.B. nicht sämtliche Möglichkeiten verwendet werden. Sagen wir, eine Art "Telegramm"-Text kommt mit 26 Buchstaben, Leerzeichen und ",.-" aus - dann brauchen wir keine 8 Bit pro Buchstabe mehr, weil die meisten Bits nur 0 wären; stattdessen könnte man hier auf eine 5-Bit Darstellung wechseln - 2^5 = 32 mögliche Buchstaben.
Hat jetzt nichts mit dem Thema zu tun, aber wenn ich mich recht erinnere, benutzt man bei Datenübertragungen i.a.R. doch mehr Bits, als man eigentlich braucht (hier z.B. 8 Bits), um die Informationen im Falle eines Datenverlustes während der Übertragung teilweise zu rekonstruieren (oder um zumindest eine fehlerhafte Übertragung zu erkennen), oder? Ich meine, da wäre sowas in der Vorlesung erwähnt worden ^^
 

lano

Well-Known Member
c-b Experte
#11
benutzt man bei Datenübertragungen i.a.R. doch mehr Bits, als man eigentlich braucht (hier z.B. 8 Bits)
Bei den 8 bits für ein Byte sind keine extra bits für Fehlerkorrektur dabei.

Beim Komprimieren wirst du nur wie -AB- sagte
dann kann man sich nur noch Häufigkeitsverteilungen ansehen, und versuchen, weniger oder häufiger auftauchende Zahlenfolgen anders zu codieren.
weiter kommen.

Du könntest dir ja mal ne ganz einfache Komprimierung ansehen.
https://de.wikipedia.org/wiki/Lauflängenkodierung
 

lord_haffi

Well-Known Member
c-b Experte
#12
Bei den 8 bits für ein Byte sind keine extra bits für Fehlerkorrektur dabei.
Nein, das war auf das Telegram-Text-Beispiel von AB bezogen, d.h. 30 verschiedene Zeichen -> 5 kodierende bits.
Aber in der Realtität benutzt man bei Dateiübertragungen doch so "Fehlerkorrekturbits", das war meine Frage :) Also bei diesem Beispiel könnte man 3 extra-bits zur Fehlerkorrektur reinpacken, sodass man wieder ne 8-bit-Darstellung hätte... Wie gesagt, hatte jetzt nichts mit Komprimierung zu tun, war nur so ne Frage aus Interesse am Rande ^^
 
#13
Hallo.

Mit dem "Umrechnen" war ich wohl auf dem Holzweg.

Man muss sich wohl die Arbeit machen und für jede möglich Bytes-Kombination eine feste int-Zahl festlegen. Glaub nicht, dass man mehr als 32000 Kombis braucht.

also nur mal z.B.

0 000 0000 = (Kombination Nr.) 1
0 000 0001 = (Kombination Nr.) 2
0 000 0010 = (Kombination Nr.) 3

0 000 0000 0 000 0000 = (Kombination Nr.) 65
0 000 0000 0 000 0001 = (Kombination Nr.) 66
0 000 0000 0 000 0010 = (Kombination Nr.) 67

und immer so weiter bis man alle Kombinationen aus 1 und 0, die in 256 Bytes möglich sind, in int Zahlen codiert hat. Wird zwar nen ganz schöner Aufwand, aber dann könnte man wie gesagt 256 Bytes zu einer 4- o. 5-stelligen int Zahl "komprimieren", bzw. codieren.

Bin aber wie gesagt Alles Andere als nen Experte. :rolleyes:
 

beepsoft

Well-Known Member
c-b Team
c-b Experte
#14
Hallo,
leider muss ich dir sagen, dass du einen Denkfehler in deiner Idee hast.

Folgendes:
Die kleinste Einheit im Computer ist ein Bit. Ein Bit kann entweder den Zustand 1 oder 0 haben.
8 Bit kann man zu einem Byte zusammenfassen. Kann ich jetzt nun 8 mal aus den Zuständen 1 oder 0 wählen erhalte ich diese 256 Kombinationen.
Entweder ausprobieren.
00000000
00000001
00000010
00000011
u.s.w.
oder rechnen.
2^8 (2 hoch 8)=256
Denk daran, auf Bitebene gibt es keine anderen Ziffern ausser 0 bzw. 1
also aus 00000001 kann man keine 0006 machen. (im binären Zahlensystem)

Wenn wir jetzt deine 256 Byte nehmen dann sind das 256*8 bit=2048 bit.
Das gibt 2^2048 (2hoch2048) Möglichkeiten.
Das sind rund 3 * 10 ^ 616 Möglichkeiten.
Diese Darstellung die der Windowsrechner ausspuckt nennt sich wissenschaftliche Notation.
Damit du eine Idee kriegst gibt mal eine Milliarde mal eine Milliarde mal eine Milliarde mal eine Milliarde ein.

Will sagen es sind wesentlich mehr als 32.000 Möglichkeiten.


Komprimierung funktioniert ehr etwas anderes. Die Daten die man komprimieren will enthalten ja üblicherweise irgendeinen Inhalt. Und der ist selten komplett unterschiedlich.
Nehmen wir ein Bild mit schwarzem Hintergrund.
Schwarz taucht häufig auf. Also codiere ich schwarz mit 0 (Ich meine hier das Binäre 0. Also ein Bit)
die Farbe Gelb taucht nur in einem Pixel auf. Die kann ich ruhig mit binär 111111111111111111111111 codieren. Das sind zwar 3 Byte also mehr als das eine Bit von schwarz. Aber das macht nichts. Ich spare Speicher im Vergleich zu einer Codierung bei der jeder Farbwert einfach 1 Byte groß ist.
Nennt sich Lauflängencodierung.


Oder aber ich verwandele mein Datenmaterial in günstige Werte die ich besser verpacken kann.

Annahme: Ich habe Musik.
Das menschliche Gehör hört am besten zwischen 3500 und 4000 Hz. (Quelle:https://de.wikipedia.org/wiki/Hörschwelle)
Ein Mikro kann Frequenzen von 20 Herz bis 20.000 Herz aufzeichnen. (Quelle:https://de.wikipedia.org/wiki/Mikrofon#Prinzip)
Wenn ich jetzt die Frequenz herzgenau speichern will bräuchte ich 20.000-20 Möglichkeiten=19.980.
Bräuchte ich 15 Bit um das zu speichern. Wenn ich jetzt pro Sekunde 1.000 Frequenzwerte aufzeichnen will dann sind das 1.875 Byte.

Nur bringen mir die Werte größere 4.000 Herz nicht so viel weil die der Mensch nicht gut hören kann.
Also speichern wir nur Werte von 3000 Herz bis 5000 Herz.
Um das zu speichern brauche ich nur 11 bit. Das wären für eine Sekunde nur noch 1.375 Byte

und das lässt sich jetzt via Lauflängencodierung noch besser komprimieren da es nun wahrscheinlicher geworden ist, dass Werte mehrfach vorgekommen sind.




Ich hoffe dir etwas weitergeholfen zu haben.


Wenn du noch weitere Fragen hast melde dich sehr gerne.

LG

Beepsoft
 
Oben