Hallöchen :)
Angenommen es stehen N Bit zur Verfügung, so können 2^N Zustände
dargestellt werden, die im Dualsystem z.B. als eine eindeutige Zahl
(keine Wiederholungen) mit dem Wertebereich [0,...,2^N-1] interpretiert
werden kann.
Gibt es Möglichkeiten, die Anzahl der eindeutigen Zahlen durch
Kompression zu erhöhen, beispielsweise indem man für bestimmte Abfolgen
von Bits (zb Zweiergruppen 00,01,10,11) neue Symbole auf Bitebene
einführt?
Vermutlich nicht, oder? Zumindest der Ansatz oben benötigt ja auch schon
wieder 4 Symbole oder halt 2 Bit. Ist damit eine Zahl im Dualsystem
sozusagen ideal was die Anzahl der Möglichkeiten angeht?
Wie lauten die Stichworte für solche Überlegungen? Unter Kompression,
Kodierung etc. habe ich nicht genau das oben genannte gefunden.
Danke!
Jan K. schrieb:> Ist damit eine Zahl im Dualsystem> sozusagen ideal was die Anzahl der Möglichkeiten angeht?
Jede Zahl in jedem Zahlensystem auf beliebige Basis ist so gesehen
ideal, weil alle Stellen mit allen verfügbaren Symbolen frei besetzt
werden können.
Es gibt keine verbotenen Ziffern/Plätze etc...
Eine sinnvolle Komprimierung erreicht man nur bei nicht zufällig
verteilten Zahlenfolgen, wenn wiederkehrende Muster auftauchen.
So kann man die Zeichenfolge AAAAABBBBCCCCDDDDDD auch als 5A4B4C6D
schreiben und entsprechend passender Konvention verlustfrei wieder
reproduzieren.
Jan K. schrieb:> Wie lauten die Stichworte für solche Überlegungen?
Huffman-Codierung - aber da gehen auch die Wahrscheinlichkeiten der
einzelnen Symbole ein und für weniger häufige verlängert sich die
Codierung sogar.
Jan K. schrieb:> Gibt es Möglichkeiten, die Anzahl der eindeutigen Zahlen durch> Kompression zu erhöhen
Nein.
Eine einzelne Zahl kann man nicht komprimieren. Treten die einzelnen
Werte unterschiedlich häufig auf, kann man sie mit unterschiedlicher
Bitanzahl darstellen entsprechend der Häufigkeit, braucht aber im
schlechtesten Fall dann mehr Bits, spart also nur im Glücksfall.
Und wenn es eine FOLGE von Zahlen ist, kann man durch die statistische
Wahrscheinlichkeit mit der Zahlen aufeinanderfolgen eine Komprimierung
erreichen, zufällige Zahlenfolgen sind nicht komprimierbar.
Jan K. schrieb:> Wie lauten die Stichworte für solche Überlegungen? Unter Kompression,> Kodierung etc. habe ich nicht genau das oben genannte gefunden.
Das Stichwort heißt Informationstheorie oder "information theory". Das
ganze Gebiet wurde 1948 mit einem Paukenschlag durch einen ursprünglich
zweiteiligen Aufsatz von Shannon gegründet. Der Aufsatz hieß "A
Mathematical Theory of Communication" (später als " The Mathematical
Theory of Communication" nochmal veröffentlicht) und ist heute noch
lesenswert.
So konstruiert er auf den ersten Seiten als eine mögliche Einheit zur
Messung von Information eine Einheit namens Bit, präsentiert ein
generisches Kommunikationsmodell und legt dann richtig los. Am Ende sind
es rund 20 Theoreme für das Kommunikationsmodell. Darunter solche Dinge
wie Quellenkodierung und die Entropie einer Nachricht.
bei genügend großer anzahl von quellbits/bytes funktioniert kompression,
aber aus einem bit kannst du kein halbes machen ;)
RLE wurde bereits genannt.
was du selbst vorgeschlagen hast gibts auch schon lange: LZW
man hat einen bytestream, und speichert im komprimierten stream nicht
die bytes des quellstreams, sondern listenindices von bytefolgen, mit
der besonderheit das dieses "dictionary" zur laufzeit der kompression
angelegt und erweitert wird.
das war zu DOS/pascal zeiten mal ein projekt von mir mit inline
assembler - hach die gute alte zeit… ^^
Michael B. schrieb:> Jan K. schrieb:>> Gibt es Möglichkeiten, die Anzahl der eindeutigen Zahlen durch>> Kompression zu erhöhen>> Nein.>> Eine einzelne Zahl kann man nicht komprimieren.
Diese Aussage ergibt keinen Sinn (genauso wie die Frage übrigens). Es
ist erstmal nur eine Folge von Bits. Daß das eine Zahl darstellt, ist
reine Interpretation.
> wenn es eine FOLGE von Zahlen ist
Genau das ist es ja. Wenn der TE eine z.B. 32-Bit Integerzahl im Auge
hatte, dann kann man sie wahlweise als Folge von 32 Bits oder 8 Nibbles
oder 4 Bytes ansehen. Und schon haben wir eine Folge von Symbolen und
können einen Kompressionsalgorithmus drauf ansetzen.
Was allerdings richtig ist: je weniger Daten man hat, desto weniger
Redundanz wird man typischerweise entfernen können. Und: Kompression
erzeugt immer auch Overhead, meist von fester Größe. Je geringer die
Datenmenge, desto größer der Overhead in Relation.
Meiner Erkenntnis nach ist es sehr wohl möglich eine nicht-Redundante
Ziffernfolge Reproduktiv um mindestens den Faktor 8 zu Komprimieren.
Mein System geht davon aus, das jedes Individuell darzustellende Symbol
genau einem Zustand innerhalb eines Bits entsprechen muss.
So wäre diese Ziffernfolge : 12345678901234567890 wie folgt zu Kodieren
: 1=1b, 2=1b, 3=2b, 4=2b, 5=3b, 6=3b, 7=3b, 8=3b, 9=4b, 0=4b, insgesamt
also 52 bits. Wenn wir die Ziffern als ganze Zahl ansehen wären es nur
40 bits.
Nun haben wir eine Redundanz innerhalb dieser Ziffernfolge, aber das
ändert prinzipiell nichts am folgenden verfahren.
Für die Komprimierung benötigen wir folgende Dinge :
Eine Bibliothek mit 176.220 Unterscheidbaren Symbolen, die jeweils einen
Bit zur Darstellung Benötigen. (Überlagerung von Kodierungsschablonen
und Prüfziffern zb)
Das sind 89 Grundsymbole, alle Kombinationen daraus sowie alle
Kombinationen aus wiederum diesen Symbolen. (3 Komprimierungsstufen)
In meinem beispiel habe ich Sonderzeichen des Alphabets genommen.
Nun nehmen wir das erste Ziffernpaar : 12. In diesem Verfahren ist
12=1+1, wir arbeiten von der linken Ziffer aus und addieren/subtrahieren
wie viel nötig ist um zur zweiten Ziffer zu gelangen (Es existieren
demnach 36 Positive, 8 Neutrale und 45 Negative Paarbeschreibungen).
1+1 ist in meinem System zb mit  kodiert. Das machen wir jetzt mit
allen nachfolgenden Zahlenpaaren, 34=3+1=Ê, 56=5+1=Ū, ect
Die Abstandsmessung zur rechten Ziffer mache ich nur zur
Zugehörigkeitsfestlegung, dadurch lässt sich einfach und schnell eine
Tabelle erstellen.
Am Ende sieht das ganze zb so aus :
Â Ê Ū Œ Ń Â Ê Ū Œ Ń
Nun haben wir 10 Symbole, von denen jedes einzelne ein Zahlenpaar
darstellt. Das sind die ersten 89 Grundsymbole in meinem System. Jedes
Symbol kann nun wie folgt Kodiert werden : Â=1b, Ê=1b, Ū=2b, Œ=2b, Ń=3b
Das sind insgesamt 18 bits. Wir haben also durch das Kodierungsverfahren
aus 52/40 bits 18 bits gemacht.
Das ganze ist noch nicht beendet. Ich kann das theoretisch unbegrenzt
oft wiederholen, damit wächst aber die Bibliothek die die Symbole
enthält jedes mal um den Faktor 44, da das die Anzahl der
rekombinatorischen Möglichkeiten aus 89 zu 3916, also der ersten
Komprimierungsstufe ist.
Mit drei Komprimierungsstufen besitzen wir am ende nur noch 3 Symbole
mit denen sich durch Stufenweise Dekodierung 20 Ziffern beschreiben
lassen. Dh wir benötigen für die Beschreibung von 20 theoretisch
nicht-redundanten Zifferfolgen 4 bits. (Sie sind redundant, allerdings
funktioniert die Paarbildung der Symbole auch ohne ein
Ordnungsparadigma)
Das dekodieren erfolgt natürlich nur, wenn wir die Bibliothek zusammen
mit der Datei verschicken. Das Programm hätte eine Größe von mehreren
hundert KB und wäre damit für sehr kleine Zifferfolgen ungeeignet.
Jenseits der Megabyte allerdings wird die Anwendbarkeit sichtbar. 100
Megabyte Ziffernfolgen werden somit auf 12 Megabyte Symbolpaare
reduziert. (Ohne Redundanz)
Ich habe einen Rechenfehler in meiner Kalkulation entdeckt, ich bitte
dies zu dieser späten/frühen Stunde zu entschuldigen.
Eine Einteilung in Verzeichnisse würde erfordern das ich jedes Symbol
mit 1-3 Bytes kodiere, um es einer der 692 Tabellen zuordnen zu können.
Zudem bräuchte ich dann einen weiteren Byte pro Symbol um es innerhalb
einer Tabelle einer Speicheradresse zuzuordnen.
Mit zusätzlichen 2-4 Bytes pro Ziffernpaar würde meine Rechnung obsolet,
es wäre nur eine sehr komplizierte und unnötig Dateivolumen
verschwendende Methode der Chiffrierung.
Dennis W. schrieb:> Mit zusätzlichen 2-4 Bytes pro Ziffernpaar würde meine Rechnung obsolet,> es wäre nur eine sehr komplizierte und unnötig Dateivolumen> verschwendende Methode der Chiffrierung.
Es ist gut, sich mit solchen Fragen zu beschäftigen, und sie ausführlich
zu durchdenken.
Mir ist jetzt Dein Ergebnis nicht klar:
Kompression irgendwie möglich, und seien es nur wenige Bits pro
Megabyte?
Oder Kompression nicht möglich?
aha, also zufällige ZIFFERN-Folgen (0-9) um den Faktor 8 komprimieren,
(BCD ist schon ziemlich gut, und dass macht nur Faktor 2)
schreib mal CODE anstelle von 2 Seiten Text in einem Uralt-Thread
Dennis W. schrieb:> Meiner Erkenntnis nach ist es sehr wohl möglich eine nicht-Redundante> Ziffernfolge Reproduktiv um mindestens den Faktor 8 zu Komprimieren.
Ich denke, du bist einfach nur dumm, wie man schon daran merkt, eine
Antwort an einen 2 Jahre alten thread zu pappen, und dein Beitrag im
wesentlichen unverständlich formuliert ist.
> So wäre diese Ziffernfolge : 12345678901234567890 wie folgt zu Kodieren> : 1=1b, 2=1b, 3=2b, 4=2b, 5=3b, 6=3b, 7=3b, 8=3b, 9=4b, 0=4b,
Das b soll wohl bit bedeuten, also codierst du
1=0, 2=1, 3=00, 4=11, 5=001, 6=011, 7=100, 8=110, 9=1001, 0=0110,
oder so.
Selbst wenn du nicht alle Codepunkte der Bitfolgen nutzt (mit 2 bit
hätte man 4 Möglichkeiten du nutzt nur 2, mit 3 schon 8, du nutzt nur
4), hast du vergessen, daß du beim decodieren die Bitfolgegrenzen nicht
mehr kennst (spätestens die codierung von 1 und 2 mit je nur 1 bit macht
es dir kaputt), du weisst also nicht, ob als nächstes ein 1 bit, 2 bit
oder 4 bit Wert folgt. Damit ist deine codierung Blödsinn.
Dennis W. schrieb:> Für die Komprimierung benötigen wir folgende Dinge :> Eine Bibliothek mit 176.220 Unterscheidbaren Symbolen, die jeweils einen> Bit zur Darstellung Benötigen.
...geht ja auch nicht, wenn man nur 1 bit hat, kann man nur 2 Symbole
unterscheiden.
Michael B. schrieb:> Dennis W. schrieb:>> Meiner Erkenntnis nach ist es sehr wohl möglich eine nicht-Redundante>> Ziffernfolge Reproduktiv um mindestens den Faktor 8 zu Komprimieren.>> Ich denke, du bist einfach nur dumm, wie man schon daran merkt, eine> Antwort an einen 2 Jahre alten thread zu pappen, und dein Beitrag im> wesentlichen unverständlich formuliert ist.>>> So wäre diese Ziffernfolge : 12345678901234567890 wie folgt zu Kodieren>> : 1=1b, 2=1b, 3=2b, 4=2b, 5=3b, 6=3b, 7=3b, 8=3b, 9=4b, 0=4b,>> Das b soll wohl bit bedeuten, also codierst du> 1=0, 2=1, 3=00, 4=11, 5=001, 6=011, 7=100, 8=110, 9=1001, 0=0110,> oder so.>> Selbst wenn du nicht alle Codepunkte der Bitfolgen nutzt (mit 2 bit> hätte man 4 Möglichkeiten du nutzt nur 2, mit 3 schon 8, du nutzt nur> 4), hast du vergessen, daß du beim decodieren die Bitfolgegrenzen nicht> mehr kennst (spätestens die codierung von 1 und 2 mit je nur 1 bit macht> es dir kaputt), du weisst also nicht, ob als nächstes ein 1 bit, 2 bit> oder 4 bit Wert folgt. Damit ist deine codierung Blödsinn.
Ich danke dir für das nette Kompliment. Ich bin absoluter Anfänger was
das Coden angeht und habe lediglich eine Idee zum Ausdruck gebracht. In
meinem zweiten Kommentar, etwas weiter unten, habe ich bereits
beschrieben dass ich den Fehler erkannt habe und die Idee der
Komprimierung selber wertlos ist.
Ich benötige 692 Verzeichnisse mit jeweils 255 Einträgen, dh. ich müsste
jedes Symbol aus den ersten 255 Verzeichnissen mit zwei Byte zur
Verzeichnisszuordnung kodieren (Position des Heap [1,2 oder 3] und
Position des Verzeichnisses aus 255 | 255 | 182) + einem weiteren Byte
für die Zuordnung innerhalb eines Verzeichnisses.
Des weiteren brauche ich dann einen weiteren Byte für Symbole aus
255-510 und wieder einen für alle Symbole aus 510-692. Dh im schnitt
brauche ich bei einer Homogenen Redundanz der Symbolmenge (SyM) für
jeweils ein Drittel mind. SyM/3*2 = Byte, SyM/3*3 = Byte und SyM/3*4 =
Byte.
In einem Beispiel mit 1 TB Volumen sind bei einer erneut Homogen
Verteilten Redundanz ca. 330 Milliarden Ziffern abgespeichert. Dh. dass
nach einer Komprimierung mit meinem System ca 55 Milliarden Ziffernpaare
jeweils 4 Byte zur Adressierung benötigen, die nächsten 55 brauchen
jeweils 5 Byte und die letzten 55 brauchen jeweils 6 Byte.
Somit ergibt sich dass die komplette Adressierung aller Ziffernpaare 768
GB an Speicher benötigen, halbiert und addiert um jeweils die Hälfte auf
den bestehenden Block pro Komprimierungsvorgang. Nach drei
Kodierungsschritten ist also der Adressierungsblock ca. 1,34 TB groß,
die Kodierte Datei jedoch nur noch 115 GB. Ohne diesen Individuellen
Adressierungsblock ist die Datei selbst jedoch nutzlos, was eine
praktische Nutzung ausschließt.
> Dennis W. schrieb:>> Für die Komprimierung benötigen wir folgende Dinge :>> Eine Bibliothek mit 176.220 Unterscheidbaren Symbolen, die jeweils einen>> Bit zur Darstellung Benötigen.>> ...geht ja auch nicht, wenn man nur 1 bit hat, kann man nur 2 Symbole> unterscheiden.
Ich sagte nie das ich nur einen Bit zur Speicheradressierung verwende,
ich unterteile diese 176.220 Symbole in 692 Verzeichnisse, die wiederum
jeweils 255 Symbole beinhalten. Somit kann ich Verzeichnis 1-255 mit 4
Bytes wiedergeben, 255-510 mit 5 Bytes und 510-692 mit 6 Bytes.
Ich weiß dass Informatik ein schwieriges Fach ist und die Nachfrage für
Kompetentes Personal umso größer, allerdings war mir nicht klar das ein
Assozialer Autismus benötigt wird um in diesen kreisen anerkannt zu
werden, ihre Persönlichkeit und die Menschen die diese ertragen müssen
tun mir sehr leid. In diesem Sinne noch einen schönen Tag !
Dennis W. schrieb:> Ich bin absoluter Anfänger was das Coden angeht und habe lediglich eine> Idee zum Ausdruck gebracht.
Wenn deine Idee funktionieren würde, hättest du dich mit diesem Thread
in der Informatik unsterblich gemacht ;-)
Dennis W. schrieb:> Meiner Erkenntnis nach ist es sehr wohl möglich eine nicht-Redundante> Ziffernfolge Reproduktiv um mindestens den Faktor 8 zu Komprimieren.
Verlustfreie Komprimierung geht, wenn Redundanz drin ist, beispielsweise
bei ASCII-Codierung, oder wenn die Häufigkeitsverteilung der Werte etwas
wie eine Huffman-Codierung zulässt.
Andernfalls würde ich empfehlen, diese Komprimierung so oft zu
wiederholen, bis nur noch 1 Bit rauskommt. ;-)
A. S. schrieb:> Dennis W. schrieb:>> Mit zusätzlichen 2-4 Bytes pro Ziffernpaar würde meine Rechnung obsolet,>> es wäre nur eine sehr komplizierte und unnötig Dateivolumen>> verschwendende Methode der Chiffrierung.>> Es ist gut, sich mit solchen Fragen zu beschäftigen, und sie ausführlich> zu durchdenken.>> Mir ist jetzt Dein Ergebnis nicht klar:>> Kompression irgendwie möglich, und seien es nur wenige Bits pro> Megabyte?>> Oder Kompression nicht möglich?
Ich danke dir, es war eine Idee die mir kam als ich mich vor ein paar
tagen das erste mal näher mit Bitcodierung auseinander gesetzt habe.
Kompression ist theoretisch unbegrenzt möglich, die letzte
Konpressionsstufe würde eine Datei mit 2 Bits Dateigröße zulassen.
Jedoch steigt die Dateigröße des Adressierungsblocks, der extern
sämtliche Positionsinformationen meiner Symbole beinhält, um den Faktor
44 an, und das pro Komprimierung.
Das heisst konkret das schon nach der ersten Komprimierung mehr Dateien
im Adressatblock enthalten sind als in der ursprünglich zu
Komprimierenden Datei, auch wenn diese sich dadurch halbiert.
Auslesen kann man sie dann jedoch nur noch mit diesem größer werdenden
Adressatblock, der individuell wäre und somit nicht zur portablen
Datenkompression zu gebrauchen ist.
Ich hoffe ich habe es verständlich ausgedrückt, mein Know-How beziehe
ich lediglich aus Selbstversuchen und Mathematischen
Formelbeschreibungen die ich in diversen Foren und im Wiki gefunden
habe.
LG Dennis
Dennis W. schrieb:> So wäre diese Ziffernfolge : 12345678901234567890 wie folgt zu Kodieren> : 1=1b, 2=1b, 3=2b, 4=2b, 5=3b, 6=3b, 7=3b, 8=3b, 9=4b, 0=4b, insgesamt> also 52 bits. Wenn wir die Ziffern als ganze Zahl ansehen wären es nur> 40 bits.
genau hier machst du deinen Fehler:
du musst einen Baum aufbauen, der an jeder Verzweigung nur maximal so
viele Äste hat, wie dein Alphabet Symbole.
Diese Regel verletzt du. Dadurch ist dein Code nicht mehr präfixfrei und
dadurch kannst du deinen komprimierten Datenstrom nicht mehr dekodieren,
da du die Symbolgrenzen nicht kennst.
Angenommen, du hast das als Codewort: 0000
Das könnte mit deinem Code eintweder 4 mal ein 1bit-Zeichen sein (1 oder
2), oder 1 1-bit und 3-bit Zeichen, .... sein
Um das Problem zu lösen, könntest du einen Baum bauen, und immer, wenn
du an einem Blatt angekommen bist, ist dein dekodiertes Symbol fertig.
Der Trick ist hier, wie man den Baum aufbaut.
Jeder Zweig sollte am ende das gleiche Gewicht habe - ein balancierter
Binärbaum
Gewicht sind in dem Fall die Häufigkeiten der Symbole an seinen Zweigen.
Dein Eingabedatenstrom ist gleichverteilt, das heißt du kannst das nicht
besser komprimieren, als log_2(10) bit/Symbol
deswegen benutze ich mal folgende Folge:
256575390519054563256552
24 Zeichen mit folgenden Häufigkeiten:
'5' '6' '2' '9' '3' '0' '7' '4' '1'
9 3 3 2 2 2 1 1 1
um da einen baum drauß zu erzeugen, teilen wir die jeweils so, dass
jeweils 2 Seiten ca gleich "schwer" sind
1
'5' '6' '2' '9' '3' '0' '7' '4' '1'
2
9 3 3 2 2 2 1 1 1
3
\__ __/ \_______________ _______________/
4
v v
5
0 (12) 1 (12)
6
/ \ \_____ _____/ \________ _______/
7
0 1 v v
8
'5' '6' 0 (7) 1(5)
9
/ \__ __/ \__ __/ \__ __/
10
0 v v v
11
'2' 1 (4) 0 (3) 1 (2)
12
/ \ / \ / \
13
0 1 0 1 0 1
14
'9' '3' '0' '7' '4' '1'
Der Baum sieht dann also so aus:
1
r
2
/ \
3
0 1
4
/ \ / \
5
0 1 / \
6
'5' '6' 0 1
7
/ \ / \
8
0 1 0 1
9
'2' / \ / \ / \
10
0 1 0 1 0 1
11
'9' '3' '0' '7' '4' '1'
bzw als wörterbuch
0 1100
1 1111
2 100
3 1011
4 1110
5 00
6 01
7 1101
9 1010
der Datestrom oben sieht also so aus:
100000100110100101110101100001111101011000011100001101110000010000100
Bei der Dekodierung geht man jetzt immer durch den baum, und wenn man an
einem Blatt angekommen ist, schreibt man das Symbol hin und springt
wieder zur wurzel
Bei der Aufteilung oben sieht man, dass es teilweise von vorteil sein
könnte, symbole umzugruppieren, um reste zu minimieren und einen
Besseren baum zu bekommen.
Das ganze ist die Hoffman-Kodierung.
Natürlich braucht die Gegenseite am Ende genug Information, dass sie den
Baum wiederherstellen kann.
Alternativ könnten beide Seiten auch mit einer Gleichverteilung beginnen
und mit jedem übertragenen Symbol wird der Baum angepasst.
Vlad T. schrieb:> Dennis W. schrieb:>> So wäre diese Ziffernfolge : 12345678901234567890 wie folgt zu Kodieren>> : 1=1b, 2=1b, 3=2b, 4=2b, 5=3b, 6=3b, 7=3b, 8=3b, 9=4b, 0=4b, insgesamt>> also 52 bits. Wenn wir die Ziffern als ganze Zahl ansehen wären es nur>> 40 bits.>> genau hier machst du deinen Fehler:>> du musst einen Baum aufbauen, der an jeder Verzweigung nur maximal so> viele Äste hat, wie dein Alphabet Symbole.>> Diese Regel verletzt du. Dadurch ist dein Code nicht mehr präfixfrei und> dadurch kannst du deinen komprimierten Datenstrom nicht mehr dekodieren,> da du die Symbolgrenzen nicht kennst.>> Angenommen, du hast das als Codewort: 0000
Vielen vielen Dank für deine Schilderung. Es hat mir enorm
weitergeholfen in meinem Verständnis über diese Thematik, so
anschauliche Erklärungen findet man nur selten im Netz !
Eine eigene Frage?
Dieser Thread ist über 9 Jahre alt.
Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.
