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.
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
