Die Community zu .NET und Classic VB.
Menü

Kompressionsverfahren

 von 

Übersicht 

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

Das grundsätzliche Prinzip  

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.

Übersicht der gängigen Verfahren  

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.

Übersicht der gängigen Datenformate  

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.

Beispielprojekt an Hand des LZWs  

Anmerkung der Redaktion: Die Funktion AddToWoerterbuch wurde am 30.12.2011 gemäss dem Kommentar von Götz K. um die Indexprüfung erweitert um Bereichsüberschreitungen im Arrayzugriff vorzubeugen.

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 NaechsterWoerterbuchindex > 4095 Then
          NaechsterWoerterbuchindex = 256
          NaechsterHeapIndex = 0
    End If
    
  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 [2950 Bytes]

Ihre Meinung  

Falls Sie Fragen zu diesem Tutorial haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.

Archivierte Nutzerkommentare 

Klicken Sie diesen Text an, wenn Sie die 6 archivierten Kommentare ansehen möchten.
Diese stammen noch von der Zeit, als es noch keine direkte Forenunterstützung für Fragen und Kommentare zu einzelnen Artikeln gab.
Aus Gründen der Vollständigkeit können Sie sich die ausgeblendeten Kommentare zu diesem Artikel aber gerne weiterhin ansehen.

Kommentar von Götz am 12.07.2007 um 23:55

Bei der Funktion AddToWoerterbuch hat der Fehlerteufel zugeschlagen, deshalb der "Index außerhalb des Bereichs".

So funktioniert es korrekt:

Private Function AddToWoerterbuch(s As String) As Long

'fehlt im Originalcode
If NaechsterWoerterbuchindex > 4095 Then
NaechsterWoerterbuchindex = 256
NaechsterHeapIndex = 0
End If
'/fehlt

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

End Function


schönen Gruß, Götz K.

Kommentar von Tox am 19.01.2007 um 12:27

Also dass der Wavelet-Algorithmus verlustbehaftet ist, ist nicht grundsätzlich richtig. Die Standardimplementierung kann verlustfrei geschehen. Verluste treten erst dann auf, wenn die gefilterten Werte quantisiert werden, was aber nicht grundsätzlich so vorgesehen ist!

Kommentar von peter am 29.12.2006 um 02:51

habe eine kurze frage:

wenn ich einen längeren text komprimiere, wird er meinst nicht ganz übermittelt...

woran kann das liegen?

Kommentar von Balduin am 31.07.2005 um 22:47

Bei mir wird ein Fehler "Index außerhalb des Bereichs" angezeigt, und zwar weil das Wörterbuch zu klein ist.
Hat es einen bestimmten Grund, warum das Wörterbuch 4097 Einträge hat, oder kann man diese Anzahl beliebig variieren?

Kommentar von Pitcheraider am 23.05.2005 um 00:15

ByRef Node As Long
= Parameterübergabe "by reference"

Space(100000)
gibt einen String mit 100000 Leerzeichen zurück

Mid$(s, pStr)
gibt den Rest des Strings s ab der Position pStr zurück

mfg benjamin

Kommentar von andreas am 21.03.2005 um 15:20

hallo!
gibt es genau dieses programm für c/c++ ?
ich habe leider kein vb und kann nur einige grundlagen.
folgendes in diesem vb-code verstehe ich nicht:

ByRef Node As Long
Space(100000)
Mid$(s, pStr)

würde mich auf eine antwort freuen.
mfg andreas