Huffman-Kodierung

Übersicht BlitzBasic Codearchiv

Neue Antwort erstellen

Eingeproggt

Betreff: Huffman-Kodierung

BeitragFr, Jun 06, 2008 22:25
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo!

Da verbringt man nen Nachmittag mal mit der Huffman-Kompression für die Schule und am Abend setzt man sich an BB und codet das Ganze mal in dieser Sprache Smile

Leider komm ich erst jetzt drauf, dass Vertex schon sehr fleißig war, das Verfahren bekannt zu machen. Glücklicherweise sind seine Codes für Bmax, weshalb ich hier ein Unikat geschaffen habe Smile (Jedenfalls ist es eigenständig geschrieben)
Auch find ich die Funktionsbibliotheken zur Bitmanipulation erst jetzt.. Hab extra bevor ich begonnen hab noch danach gesucht aber nix gefunden Confused

Naja.. So präsentiere ich euch halt eine etwas umständliche und langsame Version der huffman-Kompression. Die Kompression an sich ist ja perfekt und so wie es sein soll. Da ich aber den Binärbaum auf meine eigene Art auch mit in die Datei hineinschreib (zum Dekodieren) werden die Dateien wiederum ziemlich aufgebläht Sad

Bei einigen Dateien (vor allem kleineren und bereits komprimierten) entsteht so als Ergebnis eine größere Datei... aber bei anderen klappt es dafür wunderbar Smile

Lange Rede, kurzer Sinn:

BlitzBasic: [AUSKLAPPEN]
;Huffman-Kompression
; von Christoph Mach ("Eingeproggt"), Jun 2008


;Funktionen ------------------

;Huffman(in$,out$)
; in$: Nachricht oder Dateipfad zu einer auszulesenden Datei
; out$: Pfad zur zu schreibenden Datei

;DecompressFile(in$,out$)
; in$: Datei, die decodiert werden soll
; out$: Datei, in die das Ergebnis geschrieben werden soll

;------------------

;Bekannte Bugs:
; Daten, die nur aus einem Zeichen bestehen, werden nicht richtig dekodiert (Programmabsturz)

;Dieses Programm ist idR nur für etwas größere Dateien geeignet (>2kb)
;Außerdem ist die Anwendung bei bereits komprimierten Daten (png, zib,...) meist nicht ratsam.


;Benötigte Variablen/Types/Arrays
Type knoten
Field char$ ;Zeichen
Field child1.knoten ;Erster Knoten (nur, wenn kein Zeichen definiert ist)
Field child2.knoten ;Zweiter Knoten (nur, wenn kein Zeichen definiert ist)
Field entropie ;Absolute Wahrscheinlichkeit
Field code$ ;Bitcode als String aus "0" und "1"
Field aktiv ;Gibt an, ob bei Knotenauswahl berücksichtigt werden soll
Field id ;Handle() funktioniert hier ausdrücklich NICHT!
End Type
Global knoten.knoten
Global knotencount

Dim huffcode$(255)
Dim zweierpotenz(7)
For i=0 To 7
zweierpotenz(i)=2^i
Next

Const ID_NOCHAR=256
Const ID_ENDOFTREE=257


Function Huffman(in$,out$)
knotencount=1
Local reader=ReadFile(in$)
If reader<>0 Then
in$=""
While Not Eof(reader)
in$=in$+Chr(ReadByte(reader))
Wend
CloseFile reader
EndIf

zeichen_erkennen(in$)

huffman_main()

CreateCode(Last knoten)

WriteCodeFile(in$,out$)
End Function

Function zeichen_erkennen(msg$)
Local akt_zeichen$ ;Aktuell bearbeitetes Zeichen
Local ok,i

For i=1 To Len(msg$)
akt_zeichen=Mid(msg$,i,1)

;Kontrollieren, ob Zeichen bereits erschien oder nicht
ok=True
For knoten=Each knoten
If knoten\char$=akt_zeichen Then
;Zeichen wurde bereits erkannt
knoten\entropie=knoten\entropie+1
ok=False
Exit
End If
Next

If ok=True Then
;Ein neues Zeichen gefunden
knoten=New knoten
knoten\id=knotencount
knotencount=knotencount+1
knoten\char$=akt_zeichen$
knoten\entropie=1
knoten\aktiv=True
End If
Next
End Function

Function huffman_main()
Local tmp.knoten
;Knoten mit den niedrigsten Entropien -> Zusammenfassen
Local min1.knoten=First knoten
While Not min1\aktiv
min1=After min1
If min1=Null Then Return
Wend

Local min2.knoten=min1
Repeat
min2=After min2
If min2=Null Then Return
Until min2\aktiv

If min2\entropie<min1\entropie Then
tmp=min1
min1=min2
min2=tmp
EndIf

For knoten=Each knoten
If knoten\aktiv Then
;Die 2 Knoten mit den kleinsten Entropien finden
If knoten\entropie<min1\entropie And knoten\entropie<min2\entropie Then
If min1\entropie<min2\entropie Then
tmp=min1
min1=min2
min2=tmp
EndIf
min1=knoten
EndIf
If knoten\entropie>=min1\entropie And knoten\entropie<min2\entropie Then
If knoten<>min1 Then
min2=knoten
If min2\entropie<min1\entropie Then
tmp=min1
min1=min2
min2=tmp
EndIf
EndIf
EndIf
EndIf
Next

;Diese 2 Knoten zusammen fassen
knoten=New knoten
knoten\id=knotencount
knotencount=knotencount+1
knoten\aktiv=True
knoten\child1=min1
knoten\child2=min2
knoten\entropie=min1\entropie+min2\entropie
min1\aktiv=False
min2\aktiv=False

huffman_main()
End Function

Function CreateCode(knoten.knoten)
If knoten\child1<>Null Then
knoten\child1\code$=knoten\code$+"0"
CreateCode(knoten\child1)
EndIf
If knoten\child2<>Null Then
knoten\child2\code$=knoten\code$+"1"
CreateCode(knoten\child2)
EndIf
End Function

Function WriteCodeFile(msg$,name$)
Local file=WriteFile(name$)
If file=0 Then Return
Local i,txt$

;Original-Dateigröße zur Kontrolle
WriteInt(file,Len(msg$))
;Code in Array bzw Datei schreiben, da in Types unpraktisch aufgehoben
For knoten=Each knoten
If knoten\char$<>"" Then
;DebugLog knoten\char$+": "+knoten\code$+" ("+knoten\entropie+")"
WriteShort(file,Asc(knoten\char$)) ;Zeichen
huffcode$(Asc(knoten\char$))=knoten\code$
Else
WriteShort(file,ID_NOCHAR) ;Kein Zeichen sondern Knoten
WriteShort(file,knoten\child1\id)
WriteShort(file,knoten\child2\id)
EndIf
Next
Delete Each knoten
WriteShort(file,ID_ENDOFTREE) ;Baum abgeschlossen

;Eigentliche Codierung
For i=1 To Len(msg$)
txt$=txt$+huffcode$(Asc(Mid(msg$,i,1)))
If Len(txt$)>=8 Then
WriteByte(file,BitsToByte(Left(txt$,8)))
txt$=Right(txt$,Len(txt$)-8)
EndIf
Next
WriteByte(file,BitsToByte(txt$))

CloseFile file
End Function

Function BitsToByte(bits$)
Local i,byte
For i=1 To Len(bits$)
byte=byte+Int(Mid(bits$,i,1))*zweierpotenz(8-i)
Next
Return byte
End Function

Function DecompressFile(in$,out$)
Local file=ReadFile(in$)
If file=0 Then Return

Local tmp.knoten,id,num1,num2
Local txt$,size,newsize,temp$
knotencount=1

;Dateigröße zur Fehlererkennung
size=ReadInt(file)
If size=0 Then
RuntimeError("Originaldateigröße von 0byte wird nicht unterstützt")
EndIf
;Baumstruktur einlesen und daraus Binärbaum erstellen
Repeat
id=ReadShort(file)
If id=ID_ENDOFTREE Then Exit
knoten=New knoten
knoten\id=knotencount
knotencount=knotencount+1
If id<ID_NOCHAR Then
knoten\char$=Chr(id)
ElseIf id=ID_NOCHAR Then
num1=ReadShort(file)
num2=ReadShort(file)
For tmp=Each knoten
If tmp\id=num1 Then
knoten\child1=tmp
EndIf
If tmp\id=num2 Then
knoten\child2=tmp
EndIf
Next
Else
RuntimeError("Datei ist beschädigt, ungültig, unvollständig, was-weiß-ich...")
EndIf
Forever

Local writer=WriteFile(out$)
If writer=0 Then
CloseFile file
Return
EndIf
;Dateiinhalt dekodieren
While Not Eof(file)
txt$=txt$+Right(Bin$(ReadByte(file)),8)
Repeat
temp$=Decode(txt$,writer)
If temp$=txt$ Then Exit
newsize=newsize+1
If newsize=size Then Exit
txt$=temp$
Forever
Wend

CloseFile file
CloseFile writer
Delete Each knoten
End Function

Function Decode$(txt$,file)
Local i
knoten=Last knoten
For i=1 To Len(txt$)
If Mid(txt$,i,1)="0" Then
knoten=knoten\child1
Else
knoten=knoten\child2
EndIf

If knoten\char$<>"" Then
WriteByte(file,Asc(knoten\char$))
txt$=Right(txt$,Len(txt$)-i)
Exit
EndIf
Next
Return txt$
End Function


Vielleicht freut sich ja jemand darüber *hoff* Smile

mfG, Christoph.

EDIT 9.1.2010: Code Tags in BB-Code-Tags geändert.
  • Zuletzt bearbeitet von Eingeproggt am Sa, Jan 09, 2010 16:05, insgesamt einmal bearbeitet

ozzi789

BeitragMo, Jun 08, 2009 19:26
Antworten mit Zitat
Benutzer-Profile anzeigen
Interessanter code!

aber was bringt mir das, die datei scheint nach dem umwandeln unbrauchbar zu sein, kann ich sie auch dekomprimieren?
0x2B || ! 0x2B
C# | C++13 | Java 7 | PHP 5
 

Coffee

BeitragDi, Jun 09, 2009 18:14
Antworten mit Zitat
Benutzer-Profile anzeigen
schreib einen decoder, der nach dem binärbaum die daten rekodiert Smile huffman ist cool Wink wird soweit ich weiß auch in so einigen bekannteren kompressionsalgorithmen eingesetzt
*Mjam*

Eingeproggt

BeitragDi, Jun 09, 2009 18:42
Antworten mit Zitat
Benutzer-Profile anzeigen
Habs mit ozzi schon per PN geklärt, aber da es hier scheinbar mehr als eine Person gibt die die Dekompressions-Funktion am Ende des Codes nicht findet sag ich es nochmal:

Die Funktion und die benötigte Hilfsfunktion sind am Ende des Codes zu finden.

@coffee: In der Tat wird Huffman beim "Deflate-Verfahren" und in weiterer Folge im *.zip-Format verwendet.

mfG, Christoph.

PS. Cool, dass es nach einem Jahr doch noch Feedback gibt. Und das vermutlich nur weil ich den Thread hier iwo empfohlen hab Wink
Gewinner des BCC 18, 33 und 65 sowie MiniBCC 9

Silver_Knee

BeitragDo, Jun 18, 2009 15:20
Antworten mit Zitat
Benutzer-Profile anzeigen
https://www.blitzforum.de/foru...hp?t=26812

vllt schaffst du die PNG mit deinem Huffman ding

hazumu-kun

BeitragSo, Jul 05, 2009 20:23
Antworten mit Zitat
Benutzer-Profile anzeigen
Coffee hat Folgendes geschrieben:
schreib einen decoder, der nach dem binärbaum die daten rekodiert Smile huffman ist cool Wink wird soweit ich weiß auch in so einigen bekannteren kompressionsalgorithmen eingesetzt


IdR wird Huffmann als abschließende Kompression für den "nicht-Header"(kA wie des heißt) verwendet.
Warum kann es keine omnipotente Macht geben?
Weil diese omnipotente Macht in der Lage sein müsste, einen so schweren Stein zu schaffen, dass sie ihn nicht heben kann
-> nicht omnipotent

Silver_Knee

BeitragMo, Jul 06, 2009 16:08
Antworten mit Zitat
Benutzer-Profile anzeigen
du meinst den body Wink

hazumu-kun

BeitragMo, Jul 06, 2009 17:19
Antworten mit Zitat
Benutzer-Profile anzeigen
JAAA! Danke!
Mir ists einfach entfallen.
Laughing
Warum kann es keine omnipotente Macht geben?
Weil diese omnipotente Macht in der Lage sein müsste, einen so schweren Stein zu schaffen, dass sie ihn nicht heben kann
-> nicht omnipotent

Neue Antwort erstellen


Übersicht BlitzBasic Codearchiv

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group