Was bedeutet Kompression

Letztendlich ist Kompression (Komprimieren = verdichten, zusammendrücken) auf verschiedene Bereiche des täglichen Lebens anwendbar. Speicherkapazität ist auch im Zeitalter von Gigabyte-Festplatte noch immer beschränkt und der Datentransfer im Internet fordert den Versand von Daten nicht in der Originalform, sondern im komprimierten Zustand (aus Zeit- und somit Kostengründen).

Weiterhin ist Kompression für Backups sinnvoll, da ein Realtime-Zugriff nicht notwendig ist. Kompression sollte natürlich nur begrenzt in Bereichen eingesetzt werden, in denen ein besonders schneller Zugriff auf Daten (z. B. in Realtime) notwendig ist, denn die Dekomprimierung fordert immer Rechenkapazität (mittlerweile sind die Rechner aber so schnell, daß in einigen Segmenten bereits in nahezu Realtime komprimiert und dekomprimiert wird; man denke an DoubleDisk von Microsoft).

Mit freundlichen Grüßen
Björn Kirsch

Inhalt

	Das grundsätzliche Prinzip
	Übersicht der gängigen Verfahren
	Übersicht der gängigen Datenformate
	Beispielprojekt an Hand des LZWs

Die grundsätzliche Funktionsweise der Kompression kann in wenigen Worten zusammengefaßt werden. Es gibt zwei fundamentale Methoden:

• Redundanzen (Wiederholungen) von Daten(-Strängen) werden erkannt und zusammengefaßt (verkürzte Datenmodellierung)
• Unnötige und teilweise unwichtige Daten werden gelöscht.

Die Löschung von Daten kann natürlich nur vorgenommen werden, wenn diese nicht mehr benötigt werden und auch später zur Verarbeitung unrelevant sind. Diese Art der Kompression wird z. B. für Video- oder Audiodaten verwendet.

Achtung: natürlich können beide Prinzipien kombiniert werden.

LZW-Codierung (Lempel, Ziv, Welch)

Es wird ein Wörterbuch aufgebaut (ein Wort wird durch ein Byte definiert) und im Endeffekt wird für ein Folgewort nur noch ein Zeiger auf das erste Wort/das Wort im Wörterbuch gesetzt. Diese Kompression eignet sich natürlich sehr gut für Textdokumente, allerdings auch für Binarys, die viele gleiche Zeichenstränge beinhalten. LZW existiert mittlerweile in vielen Abwandelungen und in einigen sehr stark optimierten Formen. Die Kompression erfolgt verlustfrei, der Ursprungszustand des Dokumentes kann also wiederhergestellt werden.

RLE - Run Length Encoding

Einzelne gleiche Bytefolgen (z. B. 3, 3, 3, 3) werden zahlenmäßig zusammengefaßt (z. B. 43, also 4 x 3) und nacheinander gespeichert. Diese Methode eignet sich hervorragend für Schwarz/Weiß-Bilder, sofern es sich nicht um ein gleichmäßiges Störbild handelt (also 1,0,1,0), da dann eine Verfielfältigung der Dateigröße vorgenommen wird. Die Kompression ist auch verlustfrei.

Huffman-Codierung

Alle Zeichen werden in einem Table gespeichert. Der Table wird so sortiert, daß häufig vorkommende Zeichen einen kürzeren Identifiaktionscode bekommen (z. B. ein oder zwei Bit), als ein nicht so häufig vorkommendes Zeichen (z. B. vier Bit). In Abwandelung kann auch ein Zeichenfolgentable gebildet werden. Letztendlich wird die Datei dann so gespeichert, daß ein Abbild der Originaldatei gebildet wird, in der dann nur die über den Table definierten Zeichen gespeichert werden (also anstelle eines E, dann ein Bit mit 0). Der Table muß bei dieser Komprimierungsmethode mit in die Datei eingefügt werden, da sonst eine Dekomprimierung unmöglich ist. Dieses Vorgehen kann den Nachteil bergen, daß eine kurze Datei somit länger werden kann. Auch diese Komprimierungsform ist verlustfrei.

Wavelet-Kompression

Das Objekte/die Datei wird komplett betrachtet und mittels mathematischer Berechnung (Koeffizienten, Hoch- und Tiefpaßfilterung, etc.) gesplittet (non-blocking Strategie). Letztendlich ist dieses Verfahren allerdings für dieses Tutorial zu komplex. Insgesamt ist die Methode nicht verlustfrei (also nicht für Backups geeignet) und in der Folge der Berechnung wird meistens noch einmal per RLE oder Huffman zusätzlich komprimiert. Diese Methode ist bestens für Bilder geeignet.

Fraktale-Kompression

Ein Bild wird in verschiedene Fragmente (geometrische Strukturen) geteilt und diese Fragmente werden dann durch pushing / turning / zooming / sizing verglichen. Es werden sogenannte Domain- und Rangeblocks erzeugt (dynamisch). Zueinander ähnliche Blöcke werden gesucht; der Faktor der Ähnlichkeit kann eingestellt werden und hierüber bestimmt sich dann der Datenverlust. Jeder Domainblock wird mit mit jedem Rangeblock verglichen und außerdem wird die jeweilige Distanz zwischen den Domain- und dem transformierten Rangeblock ermittelt. Das Bild wird letztendlich durch eine Viezahl mathematischer Gleichungen präsentiert. Eine Dekodierung erfolgt durch Abarbeitung der Gleichungen und den Aufbau der Fragmente. Diese Komprimierung ist eigentlich nur für Bilder geeignet und auch nicht verlustfrei.

JPEG

Erkennt und entfernt Farbunterschiede / Helligkeitsunterschiede (für das menschliche Auge unrelevante Daten). Hierdurch ist eine gute Kompression erreichbar (einstellbar; die Qualität nimmt mit höhere Komprimierung ab). Das Verfahren ist nicht verlustfrei.

GIF

Im Standardformat hat GIF eine 8-Bit-Schlüsselung und verwendet den LZW-Algorithmus. Die Komprimierung ist verlustfrei und es gibt verschiedene Arten der Speicherung und der späteren Darstellung (z. B. Rasterung während des Aufbaus).

PNG

Dienst als Nachfolgeformat der GIF-Definition. Die Farbtiefe ist bis 64-Bit (Photorealismus) möglich und es werden weitere Filter eingesetzt.

ZIP

Das ZIP-Format kombiniert diverse Komprimierungsverfahren (Huffman, LZW, RLE und andere). Das ZIP-Format und der Einsatz der Kompressionsalgorithmen ist standardmäßig definiert.

Option Explicit

Private Type BIdx
  pLinks As Long
  pRechts As Long
  Woerterbuchindex As Long
End Type

Dim Woerterbuch(4096) As String
Dim NaechsterWoerterbuchindex As Long
Dim Heap(4096) As BIdx
Dim NaechsterHeapIndex As Long
Dim pStr As Long

Sub InitWoerterbuch()
'In dieser Sub wird das Woerterbuch
'initialisiert und mit Standardwerten belegt

  Dim i As Integer

    For i = 0 To 255
        Woerterbuch(i) = Chr(i)
    Next i

    NaechsterWoerterbuchindex = 256
    NaechsterHeapIndex = 0
End Sub

Function AddToWoerterbuch(s As String) As Long
'In dieser Sub wird dem Woerterbuch ein
'Begriff hinzugefügt

  If Len(s) = 1 Then
    AddToWoerterbuch = Asc(s)
  Else
    AddToWoerterbuch = AddToBTree(0, s)
  End If
End Function

Function AddToBTree(ByRef Node As Long, ByRef s As String) As Long
  Dim i As Integer

    If Node = -1 Or NaechsterHeapIndex = 0 Then
      Woerterbuch(NaechsterWoerterbuchindex) = s
      Heap(NaechsterHeapIndex).Woerterbuchindex = _
    NaechsterWoerterbuchindex
      NaechsterWoerterbuchindex = NaechsterWoerterbuchindex + 1
      Heap(NaechsterHeapIndex).pLinks = -1
      Heap(NaechsterHeapIndex).pRechts = -1
      Node = NaechsterHeapIndex
      NaechsterHeapIndex = NaechsterHeapIndex + 1
      AddToBTree = -1
    Else
      i = StrComp(s, Woerterbuch(Heap(Node).Woerterbuchindex))
      If i < 0 Then
          AddToBTree = AddToBTree(Heap(Node).pLinks, s)
      ElseIf i > 0 Then
          AddToBTree = AddToBTree(Heap(Node).pRechts, s)
      Else
          AddToBTree = Heap(Node).Woerterbuchindex
      End If
    End If
End Function

Private Sub SchreibeStringBuffer(s As String, s2 As String)
  Do While pStr + Len(s2) - 1 > Len(s)
    s = s & Space(100000)
  Loop
  Mid$(s, pStr) = s2
  pStr = pStr + Len(s2)
End Sub

Function Komprimieren(IPStr As String) As String
  Dim TmpStr As String
  Dim Ch As String
  Dim Woerterbuchindex As Integer
  Dim LetzterWoerterbuchindex As Integer
  Dim ErsterBegriffinFolge As Boolean
  Dim HalfCh As Integer
  Dim i As Long
  Dim ostr As String

    Call InitWoerterbuch
    ErsterBegriffinFolge = True
    pStr = 1

    For i = 1 To Len(IPStr)
      Ch = Mid$(IPStr, i, 1)
      Woerterbuchindex = AddToWoerterbuch(TmpStr & Ch)

      If Woerterbuchindex = -1 Then
        If ErsterBegriffinFolge Then
          HalfCh = (LetzterWoerterbuchindex And 15) * 16
        Else
          SchreibeStringBuffer ostr, _
    Chr(HalfCh Or (LetzterWoerterbuchindex And 15))
        End If
        SchreibeStringBuffer ostr, Chr(LetzterWoerterbuchindex \ 16)

        ErsterBegriffinFolge = Not ErsterBegriffinFolge
        TmpStr = Ch
        LetzterWoerterbuchindex = Asc(Ch)
      Else
        TmpStr = TmpStr & Ch
        LetzterWoerterbuchindex = Woerterbuchindex
      End If
    Next i

    SchreibeStringBuffer ostr, _
    IIf(ErsterBegriffinFolge, Chr(LetzterWoerterbuchindex _
        \ 16) & Chr((LetzterWoerterbuchindex And 15) * 16), _
       Chr(HalfCh Or (LetzterWoerterbuchindex And 15)) & _
    Chr(LetzterWoerterbuchindex \ 16))
    Komprimieren = Left(ostr, pStr - 1)
End Function

Function GC(str As String, position As Long) As Integer
  GC = Asc(Mid$(str, position, 1))
End Function

Function DeKomprimieren(IPStr As String) As String
  Dim Woerterbuchindex As Integer
  Dim ErsterBegriffinFolge As Boolean
  Dim i As Long
  Dim s As String
  Dim s2 As String

    Call InitWoerterbuch
    pStr = 1
    i = 1
    ErsterBegriffinFolge = True

    Do While i < Len(IPStr)
      If ErsterBegriffinFolge Then
        Woerterbuchindex = (GC(IPStr, i) * 16) Or _
    (GC(IPStr, i + 1) \ 16)
        i = i + 1
      Else
        Woerterbuchindex = (GC(IPStr, i + 1) * 16) Or _
    (GC(IPStr, i) And 15)
        i = i + 2
      End If
      ErsterBegriffinFolge = Not ErsterBegriffinFolge

      If i > 2 Then
        If Woerterbuchindex = NaechsterWoerterbuchindex Or _
    (Woerterbuchindex = 256 _
                      And NaechsterWoerterbuchindex = 4096) Then
    AddToWoerterbuch s2 & Left$(s2, 1)
        Else
    AddToWoerterbuch s2 & Left$(Woerterbuch(Woerterbuchindex), 1)
        End If
      End If

      s2 = Woerterbuch(Woerterbuchindex)
      SchreibeStringBuffer s, s2
    Loop

    DeKomprimieren = Left(s, pStr - 1)
End Function

Sub Start()
  Dim KomprS As String
    Screen.MousePointer = vbHourglass

    'Kompression aufrufen
    KomprS = Komprimieren(Form1.Text1)

    'Übergabe des komprimierten Textes
    Form1.Text6 = KomprS

    'DeKompression des komprimierten Textes
    Form1.Text2 = DeKomprimieren(KomprS)

    'Länge des Originaltextes ermitteln
    Form1.Text3 = Len(Form1.Text1)

    'Länge des komprimierten Textes ermitteln
    Form1.Text4 = Len(KomprS)

    'Status einfügen
    If Form1.Text1 <> Form1.Text2 Then
      Form1.Text5 = "Fehler"
    Else
      Form1.Text5 = "fertig"
    End If

    Screen.MousePointer = vbNormal
End Sub

Projekt als Download