Ich möchte einen binären Datenstrom komprimieren. Ich weiß, dass nach jeder "1" eine höhere Wahrscheinlichkeit besteht, eine "0" zu finden, und nach jeder "0" gibt es eine höhere Wahrscheinlichkeit, eine "1" zu finden. Wie soll ich es kodieren? Ich habe über Rice-Codes nachgedacht, aber ich bin nicht so weit gekommen ... Vielen Dank im Voraus für jede Antwort.Entropie-Codierung eines binären Datenstroms
Haben Sie eine einfache Huffman-Codierung ausprobiert? Vielleicht wird es nicht so viel sparen, aber wenn einer der Codes '10' und '01' viel höhere Wahrscheinlichkeiten hat als '00' oder '11', können Sie ihn auf '0' und die anderen auf '10' , 110 'und, 111'.
Natürlich wird dies nicht die beste Wahl sein, da es Ihren Stream in 2 Bit Chunks aufteilt und nur einen Fall optimiert. Sie kann jedoch verfeinert werden, indem Wahrscheinlichkeiten für einen größeren Eingabesatz wie 4 oder 8 Bits berechnet/gemessen werden, z. in den 8 Bits werden 10101010 und 01010101 häufiger als 00000000 und 11111111 verwendet.
Sie könnten sogar bessere Ergebnisse mit arithmetischer Codierung oder einer Komprimierung erhalten, die wirklich ein Modell verwendet, das auf den Bitproblemen basiert.
Ein anderer einfacher Ansatz wäre, jedes zweite Bit zu invertieren. Da die von Ihnen genannte Wahrscheinlichkeit zu vielen alternierenden Streamteilen wie 0101010 tendiert, erhalten Sie viele Streams wie 111111, die normalerweise mit den üblichen Komprimierungsalgorithmen besser komprimiert werden können. Aber der Erfolg dieser Methode hängt davon ab, wie groß die "Wahrscheinlichkeits-Lücke" wirklich ist.
Hallo! Ich habe Huffmann ausprobiert, aber, wie Sie bemerken, wird es keine optimalen Ergebnisse geben ... Aber danke für die arithmetische Codierung des Vorschlags. Scheint wie die richtige Wahl, ich werde es versuchen. Vielen Dank! – zakk
Arithmetische Codierung ist patentiert, verwenden Sie Bereichscodierung. –