IT-Academy Logo
Sign Up Login Help
Home - Programmieren - Visual Basic - LZW-Kompression mit Visual Basic



LZW-Kompression mit Visual Basic

Einführung in das LZW-Kompressionsverfahren.


Autor: arno strehle (paulvanderburg)
Datum: 06-04-2003, 17:03:28
Referenzen: http://www.activevb.de
Schwierigkeit: Fortgeschrittene
Ansichten: 6349x
Rating: 5.25 (4x bewertet)

Hinweis:

Für den hier dargestellte Inhalt ist nicht der Betreiber der Plattform, sondern der jeweilige Autor verantwortlich.
Falls Sie Missbrauch vermuten, bitten wir Sie, uns unter missbrauch@it-academy.cc zu kontaktieren.

[Druckansicht] [Als E-Mail senden] [Kommentar verfassen]



LZW-Komprimierung

Inhalt:
  1. Entstehung
  2. Prinzip
  3. Realisierung
Entstehung

Das Kompressionsverfahren wurde 1984 von Terry Welch entwickelt und ist patentiert. Der Ursprung dieses Verfahrens ist das LZ78-Verfahren welches wiederum ein Nachfahre des LZ77-Verfahrens ist. LZ77 wurde 1977 von Lempel und Ziv als ein Verfahren zur Datenkompression vorgeschlagen.

Prinzip
LZ77

Das Verfahren verwendet den Anfang eines Textes als Wörterbuch bzw. die von der aktuellen Stelle k zurückliegenden Zeichen. Statt des Textes wird die relative Distanz zu einer Folge von Zeichen angegeben, sowie die Anzahl der von dort zu kopierenden Zeichen. Zusätzlich wird noch das erste nicht passende Zeichen ausgegeben.

Beispiel

Position 1 2 3 4 5 6 7 8 9
Zeichen A A B C B B A B C


Kompression

Nr. Pos Treffer Zeichen Ausgabe
1. 1 - A (0,0) A
2. 2 A B (1,1) B
3. 4 - C (0,0) C
4. 5 B B (2,1) B
5. 7 A B C (5,2) C


LZW

Vor der Codierung werden alle möglichen Zeichen (bzw. Zeichenketten mit der Länge 1) im Wörterbuch untergebracht. Bei der Kompression wird zur eingegebenen Zeichenkette eine lange Zeichenkette im Wörterbuch gesucht und dann als Index ausgegeben. Vor dem Start werden alle möglichen Zeichen (d.h. Zeichenketten der Länge 1) Die Zeichenkette zusammen mit dem ersten nicht passenden Zeichen wird als neue Zeichenkette in das Wörterbuch übernommen.

Bei der Kompression erfolgt der Aufbau des Wörterbuches immer einen Schritt später, da für das aktuelle Wort immer das erste Zeichen des nächst ausgegeben Wortes benötigt wird. Dieses führt zu Problemen, wenn das bei der Kompression zuletzt in das Wörterbuch übernommene Wort als nächstes kodiert wird.

Beispiel

(1) Es liege die Zeichenfolge (A x)(A x A) vor, wobei A ein beliebiges Zeichen und x eine beliebige Zeichenfolge ist (im Beispiel ist x=B und die Zeichenfolge beginnt an Position 4).

(2) Bei der Kompression wird Ax im Wörterbuch gefunden und nach der Regel AxA in das Wörterbuch abgelegt (weil (A x A x A) im Text vorkommt), bei der Dekompression wurde AxA aber noch nicht ins Wörterbuch übernommen.

(3) Allerdings bedeutet dieses, dass die neue Folge gleich der vorherigen Folge plus dem ersten Zeichen der vorherigen Folge (A x + A) ist, da der nächste Eintrag ins Wörterbuch stets gleich dem vorhergehenden Eintrag plus dem ersten Zeichen des neuen Worts ist. Daher kann im Falle eines nicht vorhandenen Eintrags im Wörterbuch (7:) die Dekompression den Wert des Wörterbucheintrags leicht rekonstruieren und sowohl das neue Wort in das Wörterbuch übernehmen als auch in die Ausgabe schreiben.

Realisierung

!Bitte beachten das es sich bei dem Code um Visual-Basic-Code handelt!
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

2003 X-TAS-Y & paulvanderburg


[back to top]



Userdaten
User nicht eingeloggt

Gesamtranking
Werbung
Datenbankstand
Autoren:04510
Artikel:00815
Glossar:04116
News:13565
Userbeiträge:16552
Queueeinträge:06247
News Umfrage
Ihre Anforderungen an ein Online-Zeiterfassungs-Produkt?
Mobile Nutzung möglich (Ipone, Android)
Externe API Schnittstelle/Plugins dritter
Zeiterfassung meiner Mitarbeiter
Exportieren in CSV/XLS
Siehe Kommentar



[Results] | [Archiv] Votes: 1158
Comments: 0