6 - Kompression

Ansätze

• Verlustfreie Kompression

  • Originaldaten können aus komprimierten Daten exakt zurückgewonnen werden

• Verlustbehaftete Kompression

  • Originaldaten können aus komprimierten nicht Daten exakt zurückgewonnen werden -> Teil der Informationen geht verloren

Verfahren

• Wörterbuchkodierung

  • LZW-Kodierung

• Entropiekodierung

  • Huffman-Kodierung

  • Lauflängenkodierung

• Bei Wörterbuchkodierung werden wiederkehrende Symbolfolgen durch Code ersetzt, der entsprechenden Eintrag in Wrterbuch zugeordnet ist

• bei naiver Methode: Wörterbuch müsste zur Dekodierung bekannt sein

• LZW (Lempel-Ziv-Welch-Algorithmus) komprimiert wiederkehrende Symbolfogen mittels dynamischem Wörterbuch

  • Wörterbuch muss nicht gespeochert/übertragen werden, sondern wird aus komprimierten Daten rekonstruiert

• für jede Datenform geeignet, häufig bei Grafikformaten

• Einträge im Wörterbuch über 12 Bit Code angesprochen

  • maximal 4096 Einträge

  • erste 256 entsprechen sich selbst

• Verfahren zur Kodierung:

  • 1) Muster = leeres Muster

  • 2) Solange noch Zeichen verfügbar

    • 1) Lies nächstes Zeichen ein

    • 2) Wenn Muster + Zeichen in Mustertabelle

      • dann setze Muster = Muster + Zeichen

      • sonst

        • füge Muster + Zeichen der Mustertabelle hinzu

        • Ausgabe Muster

        • Muster = Zeichen

    • 3) Wenn Muster nicht leer, Ausgabe Muster

1) LetzterCode = Lies ersten Code

2) Ausgabe Muster (LetzterCode)

3) Solange noch Codes verfügbar

• 1) NächsterCode = Lies nächsten Code

• 2) Wenn NächsterCode in Mustertabelle

  • dann füge Muster(LetzterCode)+ErstesZeichen(Muster(NächsterCode)) zur Mustertabelle hinzu

  • sonst füge Muster(LetzterCode)+ErstesZeichen(Muster(LetzterCode)) zur Mustertabelle hinzu

• 3) Ausgabe Muster (NächsterCode)

• 4) LetzterCode = NächsterCode

Mehrwertige Symbole (Zeichen)

• Bei Zeichenfolgen werden Zeichensequenzen durch Anzahl und Zeichen ersetzt

• Bei Texten mit wenigen Wiederholungen: Aufblähen der Daten - Idee:

  • Einzelzeichen nicht zählen

  • Escape-Zeichen verwenden (seltenes Symbol)

  • erst ab 4 Wiederholungen kodieren

• Bei Kodierung von Bitfolgen existieren nur zwei mögliche Zeichen 0 und 1

• Festlegung auf Startzeichen und abwechselnde Speicherung der Anzahl

• besonders gut geeignet für Schwarz-Weiß Rastergrafiken (Lange Folgen von 0 und 1)