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