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-

Well-Known Member
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.
 

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-

Well-Known Member
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-

Well-Known Member
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
#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
#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 ^^
 
Oben