Kompressionsverfahren
von Björn Kirsch
Ü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