Forum: Offtopic Dualzahl komprimieren?


von Jan K. (jan_k)


Lesenswert?

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!

von Wolfgang R. (Firma: www.wolfgangrobel.de) (mikemcbike)


Lesenswert?

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.

von Uhu U. (uhu)


Lesenswert?

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.

von Michael B. (laberkopp)


Lesenswert?

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.

von Pandur S. (jetztnicht)


Lesenswert?

Komprimieren bedeutet Redundanz entfernen.

von Hannes J. (Firma: _⌨_) (pnuebergang)


Lesenswert?

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.

von Wilhelm M. (wimalopaan)


Lesenswert?

Wenn die N Zustände gleichwahrscheinlich sind, dann brauchst Du für 
jedes Zeichen, das einen Zustand repräsentieren soll, ld(N) Bits. Den 
Shannon-Ansatz findest Du in diesem Artikel ganz gut erklärt:

https://de.wikipedia.org/wiki/Entropie_(Informationstheorie)#Datenkompression_und_Entropie

Die Huffmann Codierung versucht sich dem Optimum bei 
ungleichwahrscheinlichen Symbolen anzunähern:

https://de.wikipedia.org/wiki/Huffman-Kodierung

von c. m. (Gast)


Lesenswert?

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… ^^

von Axel S. (a-za-z0-9)


Lesenswert?

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.

von Dennis W. (adialgo)


Lesenswert?

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)

: Bearbeitet durch User
von Dennis W. (adialgo)


Lesenswert?

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.

von A. S. (Gast)


Lesenswert?

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?

von Robert L. (lrlr)


Lesenswert?

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

von Michael B. (laberkopp)


Lesenswert?

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.

von Dennis W. (adialgo)


Lesenswert?

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 !

: Bearbeitet durch User
von Uhu U. (uhu)


Lesenswert?

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 ;-)

von (prx) A. K. (prx)


Lesenswert?

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. ;-)

: Bearbeitet durch User
von Dennis W. (adialgo)


Lesenswert?

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

: Bearbeitet durch User
von Vlad T. (vlad_tepesch)


Lesenswert?

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
1
100 00 01 00 1101 00 1011 1010 1100 00 1111 1010 1100 00 1110 00 01 1011 100 00 01 00 00 100
2
2   5  6  5  7    5  3    9    0    5  1    9    0    5  4    5  6  3    2   5  6  5  5  2


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.

von Dennis W. (adialgo)


Lesenswert?

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 !

von Gustl B. (-gb-)


Lesenswert?

Wo ist eigentlich Josef wenn man ihn braucht?

Hier ist noch so ein Fall:
Beitrag "Redundante Ziffernkomprimierung"

Melde dich mal in diesem großartigen Thread.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.