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
:
Bearbeitet durch User
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
Thread beobachten
Seitenaufteilung abschaltenBitte 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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.