Forum: Offtopic Redundante Ziffernkomprimierung


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Dennis W. (adialgo)


Bewertung
0 lesenswert
nicht lesenswert
Hallo allerseits.

Ich habe bereits einiges an Feedback zu einer meiner Antworten zu einem 
ähnlichen Thema erhalten.

Nun habe ich mich eine weile mit dieser im Threadheader beschriebenen 
Thematik auseinandersetzt. Mein Vorschlag würde, mit Fallbeispiel, so 
aussehen (entschuldigt meine schwache Fremdwortartikulation, ich bin 
nicht vom Fach) :

Wir besitzen zwei in sich redundante Ziffernfolgen zusammen mit einer 
zufälligen, (die trennungen dienen der übersichtlichkeit) zb.


0123456789 295 0123456789


Mit einem simplen Komprimierungsversuch und einer zugehörigen Bibliothek 
könnte man diese Ziffernfolge nun wie folgt Komprimieren :


0-9 295 0-9


Nun Kodieren wir die einzelnen Ziffern, jede wäre einen Byte groß, somit 
haben wir mit der selben Kodierungsmethode aus 23 Ziffern, also 23 Bytes 
nun 7 Ziffern und 2 Sonderzeichen gemacht, in unserer Bibliothek also 9 
Bytes.

Ich arbeite in meinem Versuch nur mit Binärer Kodierung, durch 
Hexadezimale Darstellung lässt sich natürlich die Menge der Adressen in 
einem Byte vergrößern, da mir diese Darstellung allerdings für den 
Versuchsaufbau zu komplex erscheint, verlagerte ich meine 
Adressierbarkeit nur auf alle möglichen Zustände innerhalb eines Bytes.

Nun benötigen wir natürlich noch einen zusätzlichen Byte um damit die 
Speicheradresse der Bibliothek anzugeben, mit der wir die Ziffern 
auslesen können. Somit haben wir in der ersten Methode 24 Bytes 
Dateigröße, und im zweiten 10 Bytes Dateigröße. Die nächste Ermittlung 
wäre nun die Adresse jeder Ziffer innerhalb der Datei in der wir sie 
abspeichern möchten, da diese sich ja von der Adresse innerhalb der 
Bibliothek unterscheidet. Damit haben wir nun 48 Bytes in der ersten 
Darstellung, sowie 20 Bytes in der Komprimierten Darstellung.

So funktionieren die meisten versuche Redundante Zahlensysteme zu 
komprimieren. Nun möchte ich noch eine weitere Methode vorschlagen, zu 
der ich gerne Machbarkeitsvorschläge und Kritik lesen würde.


Mein Vorschlag beruht auf folgenden Annahmen :


das wir die Position einer Ziffer innerhalb einer Datei aus 255 Stellen 
mit einem Byte Kodieren können


Das wir die Position einer Bibliothek in einem Verzeichnis aus 255 
Stellen mit einem Byte Kodieren können.


Das wir die Position einer Kodierung in einer Bibliothek aus 255 Stellen 
mit einem Byte Kodieren können.


Nehmen wir eine jede Zweistellige Zahl und geben ihr ein Symbol. Dieses 
Speichern wir in einer separaten Bibliothek ab und weisen ihr das 
entsprechende Zahlenpaar zu. Damit hätten wir 100 Symbole und 100 
zugehörige Zweistellige Zahlen. Zudem benötigen wir noch zusätzliche 20 
Paarsymbole um jede Kombination aus [-(Ziffer)] und [(Ziffer)-], wie es 
in der Komprimierten Datei der fall ist, zu erzeugen. Damit sind 240 
Adressen innerhalb einer Bibliothek belegt.

Nun geben wir jedem Zahlenpaar aus der Komprimierten Datei ein fiktives 
Symbol das wir aus der Symbol-Bibliothek beziehen.

(0-) = Â

(92) = Ø

(95) = C

(0-) = Â

9 = 9

Da wir am Ende kein Paar mehr haben sondern nur eine einzelne Ziffer, 
wird diese als solche dargestellt. Nun haben wir folgende, Kodierte 
Ziffernfolge :

Â Ø C  9


Diese benötigen nun wieder jeweils einen Byte zur Adressierung in ihrer 
eigenen Datei, einen Byte zur Adressierung der verwendeten Bibliothek 
und einen Byte um ihre Position innerhalb dieser Bibliothek festzulegen. 
Da die 9 eine andere Bibliothek verwendet als die Symbole, benötigen wir 
für sie einen eigenen Byte um sie der entsprechenden Tabelle zuzuordnen. 
Insgesamt also 12 Bytes.

Die Methode erlaubt es mir augenscheinlich also bereits 
Redundanzreduzierte Ziffernfolgen durch Paarsymbole Rekonstruktiv weiter 
zu komprimieren.

Ich würde mich freuen wenn ihr mir helft zu ermitteln ob es sich hierbei 
um einen guten Lösungsansatz handelt oder ich mich komplett verrannt 
habe.

von Uhu U. (uhu)


Bewertung
0 lesenswert
nicht lesenswert
Das löst man üblicherweise mit einer Huffman-Codierung. Deren Grundidee 
ist es, den einzelnen Codewörtern um so kürzere Codierungen zuzuordnen, 
je häufiger sie in dem zu komprimierenden Zeichenstrom vorkommen.

Dazu muss man zuerst eine Statistik über die Zeichenhäufigkeiten im 
Allgemeinen machen. Nach dieser Statistik wird dann der Code 
konstruiert.

Huffman-Codes komprimieren nicht immer - der Code kann länger werden, 
als das Original, wenn es aus mehr seltenen Zeichen zusammengesetzt ist, 
als statistisch zu erwarten wären.

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

: Bearbeitet durch User
von Axel S. (a-za-z0-9)


Bewertung
0 lesenswert
nicht lesenswert
Dennis W. schrieb:
> Nun habe ich mich eine weile mit dieser im Threadheader beschriebenen
> Thematik auseinandersetzt.

Es wäre sicher hilfreich, wenn du dich mit der einschlägigen 
Fachliteratur auseinandersetzen würdest. Datenkompression ist ein sehr 
gut erforschtes Gebiet.

> Wir besitzen zwei in sich redundante Ziffernfolgen zusammen mit einer
> zufälligen, (die trennungen dienen der übersichtlichkeit) zb.
>
> 0123456789 295 0123456789
>
> Mit einem simplen Komprimierungsversuch und einer zugehörigen Bibliothek
> könnte man diese Ziffernfolge nun wie folgt Komprimieren :
>
> 0-9 295 0-9

Ui. Das funktioniert aber nur für sehr eingeschränkten Input. Wenn du 
diesem Kompressionsalgorithmus sowas gibst: "12398760-99", dann wird er 
ganz schön ins Schwitzen kommen.

> Nun Kodieren wir die einzelnen Ziffern, jede wäre einen Byte groß

Das wäre schon der erste Fehler. Wenn deine Eingabedaten nur die 
Ziffern "0".."9" enthalten, dann brauchst du keine 8 Bit pro Ziffer. Mit 
4 Bit kann man 16 Zustände codieren, das sind schon 6 mehr als du für 
die 10 Ziffern brauchst. Das heißt, allein durch die Verwendung einer 
geeigneten (für deine Daten) Quellencodierung kannst du schon 50% 
sparen.

> Nun benötigen wir natürlich noch einen zusätzlichen Byte um damit die
> Speicheradresse der Bibliothek anzugeben, mit der wir die Ziffern
> auslesen können.

Diesen Satz verstehe ich nicht. Die Eingabedaten sind eine Folge von 
Symbolen, die Ausgabedaten ebenso. Irgendwelche Zeiger auf den 
Kompressions-Code haben da drin doch nichts verloren.

> So funktionieren die meisten versuche Redundante Zahlensysteme zu
> komprimieren.

Eher nicht. Kompressionsalgorithmen betrachten ihre Eingabedaten als 
eine Folge von Symbolen aus einem Alphabet (Menge der erlaubten 
Symbole). Symbole können z.B. Bytes sein, dann wäre das Alphabet das 
Intervall 0x00 .. 0xFF. Ein Kompressionsalgorithmus codiert eine solche 
Folge in eine andere Folge, üblicherweise mit dem gleichen Alphabet, die 
im Idealfall kürzer ist. Der zugehörige Dekompressionsalgorithmus stellt 
die ursprüngliche Folge wieder her. Das nennt man dann verlustfreie 
Kompression.

Es gibt im wesentlichen zwei Klassen von Algorithmen:

1. häufigkeitsbasiert. Meist kommen manche Symbole häufiger vor als 
andere; manche vielleicht gar nicht. Durch die Verwendung kurzer Codes 
für häufige und längerer Code für seltene Symbole kann die 
Gesamtdatenmenge reduziert werden. Dieser Weg wurde bereits bis zu 
seinem Ende gegangen. Die Theorie lieferte schon Claude Shannon 
(Inoformationsentropie). Ein klassischer Algorithmus ist 
Huffman-Codierung. Der (beweisbar!) bestmögliche Algorithmus ist die 
arithmetische Codierung.

2. musterbasiert. Hier wird die innere Struktur der Daten ausgenutzt. 
Dein Beispiel oben mit der Ersetzung von "Läufen" durch Anfangs- und 
Endwert zählt dazu. Andere Verfahren dieser Klasse verwenden 
Wörterbücher (Lempel-Ziv-Welch = zip), sortieren die Daten blockweise 
(Burrows-Wheeler = bzip2) oder machen noch andere, verrückte Sachen. Es 
kommt dabei auf die Eingangsdaten an, welches Verfahren besser ist.

Für deine Daten würde sich auch ein simpler Delta-Coder eignen. Der 
bildet in einem ersten Lauf erstmal nur die Differenz 
aufeinanderfolgender Eingabezeichen. Wenn wir 10er 
Restklassen-Arithmetik verwenden (Überlauf bei 10, z.B. 7+8 = 5), dann 
würde deine Folge von oben so aussehen:
1
Original: 0123456789 295 0123456789
2
Delta:    0111111111 376 5111111111
3
          ^^^^...
4
Startwert_| Differenz zum Vorgänger

und das ließe sich jetzt super mit einem Entropieencoder komprimieren. 
Es sind ja nur noch 6 verschiedene Zeichen, da reichen 3 Bits pro 
Zeichen. Und eins der Zeichen, die "1" ist mit Abstand am häufigsten. 
Entropieencoder lieben solche Daten.

Den Startwert kann man entweder mitspeichern oder man fängt einfach 
immer mit einem festen Startwert von z.B. 0 an.


> Mein Vorschlag beruht auf folgenden Annahmen :
>
> das wir die Position einer Ziffer innerhalb einer Datei aus 255 Stellen
> mit einem Byte Kodieren können
>
> Das wir die Position einer Bibliothek in einem Verzeichnis aus 255
> Stellen mit einem Byte Kodieren können.
>
> Das wir die Position einer Kodierung in einer Bibliothek aus 255 Stellen
> mit einem Byte Kodieren können.

Aah. Mit "Bibliothek" meinst du ein Wörterbuch. Ja, könnte man machen. 
Aber man würde mehr als nur einzelne Ziffern in das Wörterbuch packen.

> Ich würde mich freuen wenn ihr mir helft zu ermitteln ob es sich
> hierbei um einen guten Lösungsansatz handelt oder ich mich
> komplett verrannt habe.

Komplett verrannt würde ich nicht sagen. Du erfindest halt existierende 
Verfahren in schlecht noch einmal. Mehr Bildung wäre nötig.

von Dennis W. (adialgo)


Bewertung
1 lesenswert
nicht lesenswert
Axel S. schrieb:
> Dennis W. schrieb:
>> Nun habe ich mich eine weile mit dieser im Threadheader beschriebenen
>> Thematik auseinandersetzt.
>
> Es wäre sicher hilfreich, wenn du dich mit der einschlägigen
> Fachliteratur auseinandersetzen würdest. Datenkompression ist ein sehr
> gut erforschtes Gebiet.


Ich danke dir, dadurch wird mir einiges klarer. Ich habe mich aus 
Interesse ein paar Tage mit der Thematik beschäftigt, davor hatte ich 
mal aus langeweile eine Programmiersprache gelernt, allerdings ist die 
Syntax von C++ meiner persönlichen meinung nach nicht annähernd so 
schwierig zu verstehen wie Rechenmodelle innerhalb der 
Algorithmusentwicklung. (Wie ich in den letzten Tagen einige male 
feststellen musste.


Momentan versuche ich die Vorzeichenregeln der Mengenlehre zu verstehen, 
um Rechenbeispiele zum Taubenschlagproblem auf Wikipedia lesen zu 
können. Gibt es Fachlektüre zu diesem Thema die du mir empfehlen kannst 
?


LG Dennis

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, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.