Moin,
(Gleich zu Beginn mal ein Wiki-Link, jeder der nicht weiß worum es geht sollte den ggf. erst durchgehen )
Einen Huffman Encoder kann vermutlich jeder basteln (ist ja nicht so schwer) wo ich aber häufig Probleme beobachtet habe ist der Part mit dem Abspeichern der Wahrscheinlichkeitstabelle. Es ist nämlich so, dass der Decoder im Regelfall den Huffman-Baum zum dekodieren benötigt.
Beispiel:
Wenn ich jetzt aber meinen Text: "Hallo Test 123" verwende gibt es ein großes Problem: Der Text besteht aus vielen verschiedenen Zeichen (es ist ja nicht "aaaaaaabbabaaaa" oder soetwas) die jeweils auch nicht allzuoft vorkommen (Leerzeichen x2 und "l" x2), egal in welcher optimierten Darstellung ich den Huffman-Baum abspeichere, er wird in jedem Fall mehr Speicher verbrauchen als mein eigentlicher Text. Wenn ich jetzt den kodierten Text + Baum benötige um wieder meinen ursprünglichen Text zu erhalten ist nichts gewonnen. Hier kommt der adaptive Teil zum tragen.
Ein adaptiver Kodierer beginnt mit irgendeiner vorgegebenen Wahrscheinlichkeitsverteilung (z.B. eine Gleichverteilung, dann hat jedes Zeichen beim erstmaligen auftreten 8 Bit, da es 256 theoretisch mögliche Asc Zeichen gibt), generiert daraus den Huffman-Baum und kodiert damit nur das allererste Zeichen des Textes. Dann wird dieses Zeichen mit einem gewissen Faktor zur Wahrscheinlichkeitstabelle hinzugefügt, ein neuer Baum generiert und damit das 2te Zeichen kodiert. usw usw. Das bedeutet, dass der Decoder KEINEN Baum benötigt, da dieser implizit durch die kodierte Nachricht selbst mitgeliefert wird. Das hat eine ganze Reihe Vor- und Nachteile.
Vorteile:
- Funktioniert auch für kurze Texte deren Huffman-Baum alleine schon größer wäre als der Text selbst
- Falls man eine Dämpfung festlegt (in meinem Skript nicht enthalten) ist es möglich dass der Kodierer lokal besser arbeitet als wenn für den vollen Text die gleiche Verteilung angenommen werden würde.
- Da die Wahrscheinlichkeitsverteilung laufend angepasst wird kann man von einem beliebigen Startpunkt aus loslaufen. Eine Gleichverteilung, oder ein Histogramm aller Zeichen in meinem UDF-Ordner, oder der Buchstabenverteilung in irgendeiner Sprache. In diesem Fall müsste man dem kodierten Text z.B. 2 bit voranstellen damit der Decoder weiß welche Verteilung er als Startwert nehmen soll. Man könnte auch die nicht adaptive Version so verwenden und statt einem Baum nur eine Baumnummer in den kodierten Text schreiben. Das wäre aber bei weitem suboptimaler, da dieser Baum dann nicht angepasst werden würde und man nicht für jeden beliebigen Text einen gut passenden Baum im Decoder hinterlegen kann. Eine Hand voll Verteilungen reichen bei der adaptiven Version aber vollkommen aus um immer ein gutes Ergebnis zu erzielen.
Nachteile:
- Da nach JEDEM ZEICHEN alles neu aufgebaut werden muss ist diese Methode unglaublich langsam (eine Version mit Min-Heap bastele ich gerade bin aber noch nicht zufrieden).
- Da die Wahrscheinlichkeitstabelle laufend angepasst wird ist sie zu keinem Zeitpunkt "wirklich" optimal. Verglichen mit einem "normalen" Huffman-Code ist die adaptive Version je nach situation unterlegen und erzeugt längeren Output als notwendig.
- Der Textanfang wird zwangsweise suboptimal kodiert, da die Startverteilung (z.B. die Gleichverteilung) nicht immer gut auf die vorliegende Zeichenfolge passt.
- Habe ich langsam schon erwähnt? (auf meinem PC aktuell ca. 20-25 Zeichen/Sekunde)
Villeicht kann ja jemand das Skript gebrauchen, daher landet es hier
Edit: 12.03.19:
Jetzt funktioniert das ganze mit Min-Heap und ist ca. 30% schneller als vorher. Es hat viel Spaß gemacht das Teil im Rahmen der Geschwindigkeit von AutoIt zu optimieren. Wenn man die Methode aber tatsächlich auch benutzen will sollte man es in einer anderen Sprache tun... 30 Zeichen/Sek ist unzureichend, alleine diesen Post hier zu kodieren würde ne Stunde dauern
; ### Adaptive Huffman Kodierung
; ### Start mit der Zeichenverteilung einiger Posts aus dem AutoIt.de Forum
Global $__AHE_aHistDefault = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100, 0, 0, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1360, 15, 85, 0, 0, 1, 0, 0, 17, 20, 3, 1, 73, 29, 74, 23, 11, 4, 12, 1, 0, 4, 1, 0, 8, 3, 17, 0, 0, 0, 0, 16, 0, 15, 44, 5, 52, 36, 12, 11, 25, 25, 3, 9, 15, 31, 24, 9, 17, 0, 9, 33, 36, 9, 27, 17, 0, 1, 21, 0, 0, 0, 3, 0, 0, 465, 145, 234, 365, 1279, 89, 202, 298, 635, 24, 110, 335, 271, 741, 225, 78, 3, 484, 426, 486, 276, 64, 97, 21, 3, 77, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 5, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 0, 0, 0, 0, 0, 33, 0, 0, 0]
For $i = 0 To UBound($__AHE_aHistDefault) - 1 Step 1
$__AHE_aHistDefault[$i] /= 100
Next
; ### Start mit einer Gleichverteilung
;~ Global $__AHE_aHistDefault[256]
Global $__AHET[512][3]
Global $__AHEE
;~ Local $sString = 'Ich bin ein etwas längeres Beispiel. Wenn man mit der Gleichverteilung gestartet ist sollte man hier den adaptiven Effekt gut beobachten können.'
Local $sString = 'Ich bin ein Beispiel.'
ConsoleWrite(@CRLF & '!----- Adaptive Huffman Entropiekodierung -----!' & @CRLF)
ConsoleWrite('Input: ' & $sString & @CRLF & 'Encode: ')
Local $t = TimerInit()
Local $sEnc = Huff_Encode($sString)
$t = TimerDiff($t)
ConsoleWrite(@CRLF & 'Output: ' & $sEnc & @CRLF & 'Bits: ' & StringFormat('%.2f', StringLen($sEnc)/StringLen($sString)) & ' per Char' & @CRLF & @CRLF)
ConsoleWrite('Input: ' & $sEnc & @CRLF & 'Decode: ')
Local $t = TimerInit()
Local $sDec = Huff_Decode($sEnc)
$t = TimerDiff($t)
ConsoleWrite(@CRLF & 'Output: ' & $sDec & @CRLF & @CRLF)
Func Huff_Encode(ByRef $sString)
Local $aLookup[256], $aSymHist[256], $sRet = ''
For $i = 0 To 255 Step 1
$aSymHist[$i] += $__AHE_aHistDefault[$i] + 0.1 ; hier könnte man eine vorgegebene Wahrscheinlichkeit/Zeichen angeben
Next
Local $aTimers[2][2], $t
For $i = 0 To StringLen($sString) - 1 Step 1
$t = TimerInit()
__AHE_BuildTreeFromSymbolHistogram($aSymHist)
$aTimers[0][0] += TimerDiff($t)
$aTimers[0][1] += 1
$t = TimerInit()
__AHE_TreeToLookupRec($aLookup)
$aTimers[1][0] += TimerDiff($t)
$aTimers[1][1] += 1
ConsoleWrite($aLookup[Asc(StringMid($sString, $i + 1, 1))] & '(' & StringMid($sString, $i + 1, 1) & ') ')
$sRet &= $aLookup[Asc(StringMid($sString, $i + 1, 1))]
$aSymHist[Asc(StringMid($sString, $i + 1, 1))] += 8
Next
ConsoleWrite(@CRLF)
ConsoleWrite('BuildTree: ' & StringFormat('%.1f', $aTimers[0][0] / $aTimers[0][1]) & ' ms' & @CRLF)
ConsoleWrite('BuildLook: ' & StringFormat('%.1f', $aTimers[1][0] / $aTimers[1][1]) & ' ms' & @CRLF)
Return $sRet
EndFunc
Func Huff_Decode($sString)
Local $aLookup[256], $aSymHist[256], $sRet = ''
For $i = 0 To 255 Step 1
$aSymHist[$i] += $__AHE_aHistDefault[$i] + 0.1 ; hier könnte man eine vorgegebene Wahrscheinlichkeit/Zeichen angeben
Next
While $sString
__AHE_BuildTreeFromSymbolHistogram($aSymHist)
__AHE_TreeToLookupRec($aLookup)
For $i = 0 To 255 Step 1 ; das ist dermaßen ineffizient, dass es fast wehtut. Das langsame Bottleneck ist aber __AHE_BuildTreeFromSymbolHistogram, weshalb
If $aLookup[$i] = StringLeft($sString, StringLen($aLookup[$i])) Then ExitLoop ; ich diesen Teil hier nicht optimiert habe da er vernachlässigbar ist.
Next
$aSymHist[$i] += 8 ; habe einige Werte ausprobiert. Die 8 hat ganz gut performed
ConsoleWrite($aLookup[$i] & '(' & Chr($i) & ') ')
$sString = StringTrimLeft($sString, StringLen($aLookup[$i]))
$sRet &= Chr($i)
WEnd
Return $sRet
EndFunc
Func __AHE_TreeToLookupRec(ByRef $aLookup, $i = 0, $sPath = '')
If $__AHET[$i][2] = '' Then
$aLookup[$__AHET[$i][0]] = $sPath
Else
__AHE_TreeToLookupRec($aLookup, $__AHET[$i][0], $sPath & '0')
__AHE_TreeToLookupRec($aLookup, $__AHET[$i][2], $sPath & '1')
EndIf
EndFunc
Func __AHE_BuildTreeFromSymbolHistogram(ByRef $aSymHist)
Local $iRi = UBound($__AHET) - 1, $t, $n, $n2
For $i = 0 To UBound($aSymHist) - 1 Step 1 ; Beginn von 0 bis 255 mit Leafs füllen
$__AHET[$i][0] = $i ; If Leaf: Char, Else LeftIndex
$__AHET[$i][1] = $aSymHist[$i] ; Propability
$__AHET[$i][2] = '' ; If Leaf: '', Else RightIndex
Next
$__AHEE = 256 ; Jemand rief "AHEEEEEE" | Func BuildMinHeap()
For $i = Int($__AHEE / 2) To 0 Step -1 ; | (wendet eigentlich nur Heapify auf das halbe Array an)
$n = $i ; | Func Heapify()
While 1 ; |
$t = 2 * $n ; |
$n2 = ($t < $__AHEE And $__AHET[$t][1] < $__AHET[$n][1]) ? $t : $n
$t += 1 ; |
If $t < $__AHEE And $__AHET[$t][1] < $__AHET[$n2][1] Then $n2 = $t
If $n2 = $n Then ExitLoop ; |
$t = $__AHET[$n][0] ; | [0] = wichtig, den kopieren wir :D
$__AHET[$n][0] = $__AHET[$n2][0];| [1] = wichtig, kann man auch kopieren
$__AHET[$n2][0] = $t ; | [2] = '' für alle Elemente, brauchen wir also hier nicht.
$t = $__AHET[$n][1] ; | Der Vorherige Arrayinhalt von [2] ist auch egal und muss nicht
$__AHET[$n][1] = $__AHET[$n2][1];| überschrieben werden, da kann also sonstiger Unfug drinstehen.
$__AHET[$n2][1] = $t ; |
$n = $n2 ; |
WEnd ; | EndFunc Heapify
Next ; | EndFunc BuildMinHeap
For $i = 0 To 254 Step 1
$__AHET[$iRi][0] = $__AHET[0][0] ; | Func HeapRemoveMin()
$__AHET[$iRi][1] = $__AHET[0][1] ; |
$__AHET[$iRi][2] = $__AHET[0][2] ; | kombiniert mit Min ans Ende schieben
$__AHEE -= 1 ; | und Heapbedingungerneuern.
$__AHET[0][0] = $__AHET[$__AHEE][0]; |
$__AHET[0][1] = $__AHET[$__AHEE][1]; |
$__AHET[0][2] = $__AHET[$__AHEE][2]; |
$n = 0 ; | Func Heapify()
While 1
$t = 2 * $n
$n2 = ($t < $__AHEE And $__AHET[$t][1] < $__AHET[$n][1]) ? $t : $n
$t += 1
If $t < $__AHEE And $__AHET[$t][1] < $__AHET[$n2][1] Then $n2 = $t
If $n2 = $n Then ExitLoop
$t = $__AHET[$n][0]
$__AHET[$n][0] = $__AHET[$n2][0]
$__AHET[$n2][0] = $t
$t = $__AHET[$n][1]
$__AHET[$n][1] = $__AHET[$n2][1]
$__AHET[$n2][1] = $t
$t = $__AHET[$n][2]
$__AHET[$n][2] = $__AHET[$n2][2]
$__AHET[$n2][2] = $t
$n = $n2 ; | EndFunc Heapify
WEnd ; ----------------------------- | EndFunc HeapRemoveMin
$__AHET[$iRi-1][0] = $__AHET[0][0] ; | Func HeapRemoveMin()
$__AHET[$iRi-1][1] = $__AHET[0][1] ; | Nochmal. wir wollen ja die 2 kleinsten Elemente.
$__AHET[$iRi-1][2] = $__AHET[0][2]
$__AHEE -= 1
$__AHET[0][0] = $__AHET[$__AHEE][0]
$__AHET[0][1] = $__AHET[$__AHEE][1]
$__AHET[0][2] = $__AHET[$__AHEE][2]
$n = 0 ; | Func Heapify()
While 1
$t = 2 * $n
$n2 = ($t < $__AHEE And $__AHET[$t][1] < $__AHET[$n][1]) ? $t : $n
$t += 1
If $t < $__AHEE And $__AHET[$t][1] < $__AHET[$n2][1] Then $n2 = $t
If $n2 = $n Then ExitLoop
$t = $__AHET[$n][0]
$__AHET[$n][0] = $__AHET[$n2][0]
$__AHET[$n2][0] = $t
$t = $__AHET[$n][1]
$__AHET[$n][1] = $__AHET[$n2][1]
$__AHET[$n2][1] = $t
$t = $__AHET[$n][2]
$__AHET[$n][2] = $__AHET[$n2][2]
$__AHET[$n2][2] = $t
$n = $n2 ; | EndFunc Heapify
WEnd ; ----------------------------- | EndFunc HeapRemoveMin
$__AHET[$__AHEE][0] = $iRi ; | Func HeapInsert(NewNode)
$__AHET[$__AHEE][1] = 1 / 0 ; | Aus den vorher gefundenen 2 kleinsten Elementen entsteht
$__AHET[$__AHEE][2] = $iRi - 1 ; | eine neue Node die man per Insert in den Heap stopft.
$n = $__AHEE ; | Func HeapDecrease()
If $__AHET[$n][1] >= $__AHET[$iRi][1] + $__AHET[$iRi - 1][1] Then
$__AHET[$n][1] = $__AHET[$iRi][1] + $__AHET[$iRi - 1][1]
While $n > 0 And $__AHET[$n][1] < $__AHET[Int($n / 2)][1]
$n2 = Int($n/2)
$t = $__AHET[$n][0]
$__AHET[$n][0] = $__AHET[$n2][0]
$__AHET[$n2][0] = $t
$t = $__AHET[$n][1]
$__AHET[$n][1] = $__AHET[$n2][1]
$__AHET[$n2][1] = $t
$t = $__AHET[$n][2]
$__AHET[$n][2] = $__AHET[$n2][2]
$__AHET[$n2][2] = $t
$n = $n2
WEnd
EndIf ; | EndFunc HeapDecrease
$__AHEE += 1 ; | EndFunc HeapInsert
$iRi -= 2 ; Reverse Index - 2
Next
EndFunc
Alles anzeigen
lg
M