Kompressionsformat



  • Hallo alle

    Bei einem perfekten (keine Redundanz) Kompressions-Dateiformat dürfte es theoretisch keine fehlerhaften Dateien geben, sehe ich das richtig? Die Vermutung kommt daher, weil Fehler ja im Dateiformat selbst durch z.B. logische Widersprüche entstehen. Bei einem redundanzlosen Verfahren werden aber alle mehrfachen Informationen (auch Implikationen) gestrichen.



  • Ist das ein Huff-Frau Verfahren, das so funktioiniert?



  • Ich hoffe mal schwer das auch bei nicht perfekten Formaten nicht automatisch Fehler entstehen...



  • Angenommen, man möchte 3 Symbole mit gleichem Informationsgehalt darstellen und wählt dazu die Codewörter 00, 01 und 10. Dann ist das Codewort 11 ein Fehler, obwohl die Darstellung perfekt ist. Das ist aber kein echtes Problem, man kann ja einfach dem Codewort 11 willkürlich eins der Symbole zuweisen und so den Fehler wegdefinieren.

    Dasselbe kann man aber auch bei unperfekten Darstellungen machen. Woran liegt das? IMHO ist dieser intuitive Fehlerbegriff nicht vernünftig formalisierbar bzw. er ist nicht mehr interessant, wenn man ihn einmal als Definitionslücke in der Interpretationsabbildung erkannt hat.



  • Bashar schrieb:

    Angenommen, man möchte 3 Symbole mit gleichem Informationsgehalt darstellen und wählt dazu die Codewörter 00, 01 und 10. Dann ist das Codewort 11 ein Fehler, obwohl die Darstellung perfekt ist. Das ist aber kein echtes Problem, man kann ja einfach dem Codewort 11 willkürlich eins der Symbole zuweisen und so den Fehler wegdefinieren.

    Dann enthält das Kompressionsformat aber Redundanz.

    Meine Ansicht:

    keine Redundanz <=> keine Definitionslücke bis auf 1 Bit <= keine Definitionslücke



  • perfetto schrieb:

    Dann enthält das Kompressionsformat aber Redundanz.

    Wieso? Bzw. nach welcher Definition von Redundanz?



  • Hufffrau schrieb:

    Hallo alle

    Bei einem perfekten (keine Redundanz) Kompressions-Dateiformat dürfte es theoretisch keine fehlerhaften Dateien geben, sehe ich das richtig? (...)

    Nein.
    Weil es unmöglich ist "keine Redundanz" genau zu definieren.

    Oder überleg' dir mal folgendes: Du hast Datei-Format X, wo an Offset 123 ein Byte steht, das nur die Werte 1, 2, oder 3 haben darf. Wenn du an der Stelle also eine 4 stehen hast, dann ist das ein Fehler.
    Dein "optimales" Format darf also keine Möglichkeit haben ein File darzustellen das eine 4 an der Stelle stehen hat - sonst wäre es ja nach deiner Definition nicht "optimal". Weil es ja immer noch Platz verschwenden würde, für die möglichkeit dieses defekte File darzustellen.

    So und nu definiert der Erfinder des Formats eine neue Verison des Formats, wo eine 4 an der Stelle auf einmal erlaubt ist, und eine bestimmte Bedeutung hat. Dein "optimales" Format kann das File aber nicht abbilden. Dein "optimales" Format ist also auf einmal nicht mehr optimal, sondern einfach kaputt.



  • perfetto schrieb:

    Bashar schrieb:

    Angenommen, man möchte 3 Symbole mit gleichem Informationsgehalt darstellen und wählt dazu die Codewörter 00, 01 und 10. Dann ist das Codewort 11 ein Fehler, obwohl die Darstellung perfekt ist. Das ist aber kein echtes Problem, man kann ja einfach dem Codewort 11 willkürlich eins der Symbole zuweisen und so den Fehler wegdefinieren.

    Dann enthält das Kompressionsformat aber Redundanz.

    Meine Ansicht:

    keine Redundanz <=> keine Definitionslücke bis auf 1 Bit <= keine Definitionslücke

    Wie willst du 3 Symbole mit weniger als 2 Bit darstellen?



  • hustbaer schrieb:

    Wie willst du 3 Symbole mit weniger als 2 Bit darstellen?

    z.b. mit arithmetic coding, im simpelsten fall, bei einer gleichmaessigen verteilung waere das einfach nur

    ArthNumber Encode(const ArthNumber& rN,size_t Code)
    {
      return rN*3+Code;
    }
    size_t Decode(ArthNumber& rN,)
    {
      size_t Code=rN%3;
      rN/=3;
      return Code;
    }
    

    @topic
    ja, bei einem format das komplet ohne redundanz auskommt, hast du per definition keine konstelation bei der etwas schiefgehen kann, denn 'ohne redundanz' impliziert 'alles macht validen sinn'. du musst nichtmal die dateigroesse oder sowas ablegen, da der stream wohl definiert endet, denn wuerde er das in irgend einem fall nicht, dann haette man eine konstelation die nicht ausgenutzt wurde -> redundant.



  • hustbaer schrieb:

    Hufffrau schrieb:

    Hallo alle

    Bei einem perfekten (keine Redundanz) Kompressions-Dateiformat dürfte es theoretisch keine fehlerhaften Dateien geben, sehe ich das richtig? (...)

    Nein.
    Weil es unmöglich ist "keine Redundanz" genau zu definieren.

    das ist sogar sehr wohl definiert, ich kann dir sogar beispielcode geben der garantiert redundanzfrei dekodiert

    typedef std::map<ArbitaryDataStream,DecodeValue> tdDecodeMap;
    DecodedValue Decode(ArbitaryDataStream& rData)
    {
      tdDecodeMap::iterator it=m_AllCodesOfZeUniverse.find(rData);
      return it->second.
    }
    

    Oder überleg' dir mal folgendes: Du hast Datei-Format X, wo an Offset 123 ein Byte steht, das nur die Werte 1, 2, oder 3 haben darf. Wenn du an der Stelle also eine 4 stehen hast, dann ist das ein Fehler.

    aber damit wiederlegst du doch die grundbedingung, dass es keine redundanz gibt.

    Dein "optimales" Format darf also keine Möglichkeit haben ein File darzustellen das eine 4 an der Stelle stehen hat - sonst wäre es ja nach deiner Definition nicht "optimal". Weil es ja immer noch Platz verschwenden würde, für die möglichkeit dieses defekte File darzustellen.

    es geht nicht so sehr ein dateiformat mit metadaten darzustellen, sondern ein format das jedes bisschen daten nutzt. sagen wir z.b. die hast ein LZW implementiert, beim LZW waechst die tabelle staetig mit. die allermeisten implementierungen machen es so, dass sie schauen wieviel bit fuer zum encoden der tabelle noetig sind, wenn du also 256 eintraege hast am anfang -> 8bit, hast du nach dem ersten schritt 257 eitnraege -> 9bit. du hast effektiv 255invalide werte und somit kann das file kaputt sein.
    etwas schlauer ist es bei 257 eintraegen weiterhin 8bit abzulegen, triffst du auf den code '255', liest du ein bit extra, was dir sagt ob du an 255 oder 256 den code auslesen sollst.
    wenn du das so weiter treibst, hast du keine moeglichkeit den stream in irgendeiner weise defekt zu bekommen (wenn man noch weiter annimmt, dass die rest 0 bits vom stream nicht abgespeichert werden, da sie ebenfalls redundant sind, denn dann kannst du den stream auch irgendwo abschneiden und der parser muss beim lesen des letzten codes die fehlenden nuller bits ergaenzen).

    So und nu definiert der Erfinder des Formats eine neue Verison des Formats, wo eine 4 an der Stelle auf einmal erlaubt ist, und eine bestimmte Bedeutung hat. Dein "optimales" Format kann das File aber nicht abbilden. Dein "optimales" Format ist also auf einmal nicht mehr optimal, sondern einfach kaputt.

    bin gespannt wie du mein optimales lzw format weiter oben kaputt machen wirst 🙂



  • hustbaer schrieb:

    Wie willst du 3 Symbole mit weniger als 2 Bit darstellen?

    Arithmetische Codierung oder range coder. Mit asymptotisch 1.58 Bits. Klar, klappt nicht bei nur einem einzelnen übertragenen Zeichen.

    Darum gehts dem Fragesteller aber auch nicht, füchte ich. Und mit dem range coder wird schon fast sicher1 ein umgefallenes Bit unentdeckt bleiben und nur dazu führen, daß hinten Quark rauskommt.

    Insofern ist "Bei einem perfekten (keine Redundanz) Kompressions-Dateiformat dürfte es theoretisch keine fehlerhaften Dateien geben" richtig.

    Falls der Fragesteller den "optimalen Code" mit seinem Namen "Hufffrau" auf nur Huffman-Codes einschränkt, ja, da isses klar. Der Huffman-Code löst die Aufgabe optimal, wenn der Codierer kein Gedächtnis haben darf und mindestens ein Bit pro Symbol verwendet. Insofern ist er optimal UND es können Fehler wegen umgekippter Bits beim Entpacken entstehen.

    Der optimale arithmetische Codierer hat das Problemchen schonmal nicht mehr (außer vielleicht am letzen Zeichen, bin nicht sicher).

    Trotzdem ist "optimaler Code" unglaublich unbestimmt. Mein Bruder kann mir die foo.exe so geil komprimieren, wie er will, wenn sie nicht ausgepackt mit MZ (oder ZM, danke, Bashar!) beginnt, habe ich einen Fehler.

    "Optimaler Code" ist mir so schwammig wie für einen Zimmermann ein "optimales Werkzeug" zu finden. Was sind die (derzeit) optimalen Codierungen für "Man kann jede ebene Landkarte mit 4 Farben einfärben" bzw "Es gibt unendlich viele Primzahlenzwillinge"? Wohl "true" bzw "Es gibt unendlich viele Primzahlenzwillinge"? Aber sollte eine optimale Codierung nicht zeitlos sein? Ich füchte, daraus könnte man basteln, daß es keine optimale Codierung geben kann.

    Andersrum isses leicht, man kann leicht eine Codierung finden, die beim Auspacken keine Fehler erkennt.

    1 Damit war nicht http://de.wikipedia.org/wiki/Fast_sichere_Eigenschaften gemeint, aber fast, die Maschinengenauigkeit tut noch was weg und so…



  • volkard schrieb:

    Was sind die (derzeit) optimalen Codierungen für "Man kann jede ebene Landkarte mit 4 Farben einfärben" bzw "Es gibt unendlich viele Primzahlenzwillinge"? Wohl "true" bzw "Es gibt unendlich viele Primzahlenzwillinge"? Aber sollte eine optimale Codierung nicht zeitlos sein? Ich füchte, daraus könnte man basteln, daß es keine optimale Codierung geben kann.

    Das sehe ich nicht. Bloß weil man eine optimale Kodierung definiert heißt es ja nicht, dass man die dann auch kennen muss.

    Am ehesten passt vielleicht sowas wie Kolmogorov Complexity? https://en.wikipedia.org/wiki/Kolmogorov_complexity



  • Oh je oh je, bitte auch den restlichen Thread lesen.
    Ja, ich kenne range coding.

    Aber wenn du ein File mit einem einzigen Symbol aus einem Alphabet von 3 kodieren sollst, dann geht das nicht in weniger als 2 Bit!



  • hustbaer schrieb:

    ... wenn du ein File mit einem einzigen Symbol aus einem Alphabet von 3 kodieren sollst, dann geht das nicht in weniger als 2 Bit!

    bitcode - zeichen
    0 - 0
    1 - 1
    11 - 2
    

    decoder liest das erste bit, ist es 0, ist es zweifelsfrei zeichen 0. ist es 1, liest der decoder ein weiteres bit, gemaess der regel das overflow beim lesen mit 0 aufgefuellt wird, dekodiert der decoder durch 10 zeichen 1, falls der decoder 11 liest, ist es zeichen 2.

    speicheranforderung ist 1 1/3 bit/zeichen bei nur einem zeichen, ansonsten 1 2/3bit auf unendlich zeichen.

    manipulation der datei aendert nichts am funktionalem dekodieren da es keine redundanz gibt.

    0 - 0
    1 - 1
    00 - 0, 0
    01 - 0, 1
    10 - 1
    11 - 2
    000 - 0, 0 ,0
    001 - 0, 0, 1
    010 - 0, 1
    011 - 0, 2
    100 - 1, 0
    101 - 1, 1
    110 - 2, 0
    111 - 2, 1
    ...
    


  • rapso schrieb:

    hustbaer schrieb:

    ... wenn du ein File mit einem einzigen Symbol aus einem Alphabet von 3 kodieren sollst, dann geht das nicht in weniger als 2 Bit!

    bitcode - zeichen
    0 - 0
    1 - 1
    11 - 2
    

    decoder liest das erste bit, ist es 0, ist es zweifelsfrei zeichen 0. ist es 1, liest der decoder ein weiteres bit, gemaess der regel das overflow beim lesen mit 0 aufgefuellt wird, dekodiert der decoder durch 10 zeichen 1, falls der decoder 11 liest, ist es zeichen 2.

    Ganz verstanden habe ich es nicht.
    zeichenstrom - bitcodestrom
    0 - 0
    1 - 1
    11 - 2
    soweit ok
    11 - 11 ??
    2 - 11 ??

    Willste nicht vielleicht ein wenig mehr ausgeben?
    bitcode - zeichen
    0 - 0
    10 - 1
    11 - 2
    Bei gleichverteilen Zeichen 1.66Bit/Zeichen, unter 1.58 wirste nicht kommen, fürchte ich, das Fallenlassen der Fano-Bedingung war schon hübsch problematisch.


Log in to reply