DecToBin (Adaptive)

**Mars**

Moin,

bevor ich meine eigenen Skripte wieder verlege und nie wieder finde, lade ich sie lieber mal hoch, dann findet man sie im Notfall in der Suche

Anbei ist eine DecToBin UDF. Sie kann... Dezimalzahlen in Binärzahlen umwandeln und umgekehrt (vermutlich geistern davon 10 Versionen durchs Forum). Neulich habe ich die Adaptive Version davon gesucht und nicht mehr gefunden, der Aufbau ist trivial, also war es einfach dasselbe nochmal zu schreiben.

Die UDF ist von 2014 (im Prinzip sogar noch älter, aber ich habe irgendwann mal aufgeräumt, die UDF wurde eigentlich hier geboren: Link, da ist sogar schon die vielsagende Variablenbenennung ($a_, $c_, etc) vorhanden), steinigt mich nicht für den unleserlichen nicht wartbaren erroranfälligen Code. Den schreibe ich auch heute noch

AutoIt

#include-once

; #INDEX# =======================================================================================================================
; Title .........: DecToBin
; AutoIt Version : 3.3.12.0
; Date ..........: 01.05.2014
; Modified ......: 08.05.2023 (3.3.16.1)
;                  - [Added] _BinToDecA
;                  - [Added] _DecToBinA
;                  - [Added] _DecToBinPrefixTable
;                  - [Added] __AHE_BuildTreeFromSymbolHistogram & __AHE_TreeToLookupRec
;                           (falls Namenskollision auftritt, Huffman.au3 hat Vorrang, das hier ist nur eine Kopie)
; Modified ......: 12.05.2023
;                  - [Changed] _BinToDecA & _DecToBinA verwenden den Default Prefix Table, wenn der 2te Parameter 0 ist.
;                  - [Changed] _DecToBin hat jetzt einen Längenparameter als 2tes
;                  - [Rename] $D2BA, $D2BB, $D2BC umbenannt zwecks vermeidung von Namenskollisionen
; Language ......: Deutsch
; Description ...: Funktionen um zwischen Dezimal und Binärzahlen umzurechnen
; Author(s) .....: Mars
; ===============================================================================================================================

; #CURRENT# =====================================================================================================================
; _BinCap8
; _BinToDec
; _BinToDecA
; _DecToBin
; _DecToBinA
; _DecToBinPrefixTable
; __DecToBinStartup
; ===============================================================================================================================

Global $D2BA[256], $D2BB[256], $D2BC[11111112]
Global Const $D2B_DPT = _DecToBinPrefixTable() ; Default Prefix Table

__DecToBinStartup()

If @ScriptName = 'DecToBin.au3' Then __DecToBinExample()

Func __DecToBinExample()
    ; Beispiel für adaptive Version.
    Local $bOnlyResults = False

    ; Generiere Liste aus Zufallszahlen
    Local $aNumbers[10]
    For $i = 0 To UBound($aNumbers) - 1 Step 1
        $aNumbers[$i] = Round(2^Random(0, 31-1, 1) * Random(0, 1)) ; Produziere Zufallszahlen mit sehr großen Unterschieden in der Länge.
    Next

    ; Nimm die Default Wahrscheinlichkeiten
    Local $iSumBits = 0, $iCount = 0

    ConsoleWrite('Eine Runde mit default Settings' & @CRLF)
    If Not $bOnlyResults Then ConsoleWrite('            Zahl   Bitrate  Encoded                                Used Bits Decoded' & @CRLF)
    For $i = 0 To UBound($aNumbers) - 1 Step 1
        Local $iNumber = $aNumbers[$i]
        Local $iBitrate = Ceiling(Log($iNumber+1+($iNumber=0?1:0))/Log(2))
        Local $sEncoded = _DecToBinA($iNumber)
        Local $iDecoded = _BinToDecA($sEncoded)
        Local $iBinaryLen = @extended
        Local $bError = $iNumber <> $iDecoded Or $iBinaryLen <> StringLen($sEncoded)
        If Not $bOnlyResults Then
            ConsoleWrite($bError ? '!' : ' ')
            ConsoleWrite(StringRight('               ' & $iNumber, 15) & ' (bits: '& StringRight(' ' & $iBitrate, 2) &') ')
            ConsoleWrite(StringLeft($sEncoded & '                                             ', 45) & ' ' & StringRight(' ' & $iBinaryLen, 2))
            ConsoleWrite(' ' & $iDecoded & @CRLF)
        EndIf
        $iSumBits += $iBinaryLen
    Next
    ConsoleWrite('Anzahl: ' & StringLeft(UBound($aNumbers) & '     ', 6) & _
    ' Bits: ' & StringLeft($iSumBits & '      ', 7) & _
    ' Bit/Number: ' & StringFormat('% 5.2f', $iSumBits / UBound($aNumbers)) & @CRLF)

    ; Nimm angepasste Wahrscheinlichkeiten
    ; Nicht gesetzte Werte werden als 0 interpretiert (haben also "kein Gewicht" bei der Baumbildung)
    ; sie werden aber dennoch berücksichtigt. Es ist also möglich auch Zahlen zu kodieren die aus
    ; bereichen kommen die mit 0 markiert sind. Das wird dann nur beliebig ineffizient.
    Local $aPropabilities[31]
    For $i = 0 To UBound($aNumbers) - 1 Step 1
        Local $iNumber = $aNumbers[$i]
        Local $iBitrate = Ceiling(Log($iNumber+1+($iNumber=0?1:0))/Log(2))
        $aPropabilities[$iBitrate-1] += 1
    Next
;~     _ArrayDisplay($aPropabilities, 'Custom Propabilities') ; muss nicht normiert werden.
    Local $aLUT = _DecToBinPrefixTable($aPropabilities), $iSumBits = 0, $iCount = 0
;~     _ArrayDisplay($aLUT, 'Lookup')

    ConsoleWrite(@CRLF & 'Eine runde mit eigener Wahrscheinlichkeitstabelle' & @CRLF)
    If Not $bOnlyResults Then ConsoleWrite('            Zahl   Bitrate  Encoded                                Used Bits Decoded' & @CRLF)
    For $i = 0 To UBound($aNumbers) - 1 Step 1
        Local $iNumber = $aNumbers[$i]
        Local $iBitrate = Ceiling(Log($iNumber+1+($iNumber=0?1:0))/Log(2))
        Local $sEncoded = _DecToBinA($iNumber, $aLUT)
        Local $iDecoded = _BinToDecA($sEncoded, $aLUT)
        Local $iBinaryLen = @extended
        Local $bError = $iNumber <> $iDecoded Or $iBinaryLen <> StringLen($sEncoded)
        If Not $bOnlyResults Then
            ConsoleWrite($bError ? '!' : ' ')
            ConsoleWrite(StringRight('               ' & $iNumber, 15) & ' (bits: '& StringRight(' ' & $iBitrate, 2) &') ')
            ConsoleWrite(StringLeft($sEncoded & '                                             ', 45) & ' ' & StringRight(' ' & $iBinaryLen, 2))
            ConsoleWrite(' ' & $iDecoded & @CRLF)
        EndIf
        $iSumBits += $iBinaryLen
    Next
    ConsoleWrite('Anzahl: ' & StringLeft(UBound($aNumbers) & '     ', 6) & _
    ' Bits: ' & StringLeft($iSumBits & '      ', 7) & _
    ' Bit/Number: ' & StringFormat('% 5.2f', $iSumBits / UBound($aNumbers)) & @CRLF)

EndFunc


; #FUNCTION# ====================================================================================================================
; Author ........: Mars
; Description ...: Erzeugt einen Lookup Table zum enkodieren/dekodieren aus einer Wahrscheinlichkeitsliste.
;                  Aufbau:
;                  $aP[0]  = Wahrscheinlichkeit, dass eine Zahl die Länge  1 Bit hat
;                  $aP[1]  =                                               2
;                  $aP[n]  =                                               n
;                  $aP[30] =                                              31
;                  Da der Maximalwert des Enkoders/Dekoders uint31-1 ist, ist $aP grundsätzlich 31 Einträge groß (Array[31])
; ===============================================================================================================================
Func _DecToBinPrefixTable($aP = 0)
    ; $aP[31] <- mehr als 31Bit geht nicht. Enthält die Wahrscheinlichkeiten für jede Bitrate.
    If Not IsArray($aP) Then
        Local $_[31]
        For $i = 0 To UBound($_) - 1 Step 1
            $_[$i] = 1 / 1.05^$i ; Initiale Wahrscheinlichkeiten je Bitrate. Leicht exponentiell, fast gleichverteilt.
        Next
        $aP = $_
    EndIf
    ; Normalisieren, falls es im Input vergessen wurde
    Local $s = 0
    For $i = 0 To UBound($aP) - 1 Step 1
        $s += $aP[$i]
    Next
    For $i = 0 To UBound($aP) - 1 Step 1
        $aP[$i] /= $s
    Next
    Local $HT[UBound($aP) * 2][3], $L1D[UBound($aP)], $L2D[UBound($aP)][2]
    __AHE_BuildTreeFromSymbolHistogram($aP, $HT) ; geklaut von Adaptive Huffman Encoder
    __AHE_TreeToLookupRec($L1D, $HT) ; geklaut von Adaptive Huffman Encoder
    For $i = 0 To UBound($L1D) - 1 Step 1
        $L2D[$i][0] = StringLen($L1D[$i]) ; Die Länge schonmal speichern
        $L2D[$i][1] = $L1D[$i]
    Next
    Return $L2D
EndFunc

; #FUNCTION# ====================================================================================================================
; Author ........: Mars
; Description ...: Adaptives enkodieren von Integern (bis uint31 - 1) via Prefix Tabelle.
;                  In $aLUT ist ein eindeutiger Lookup Table für die Prefixes. Diesen kann man z.B. via
;                  Huffman generieren.
; ===============================================================================================================================
Func _DecToBinA($d, $aLUT = 0)
    If Not IsArray($aLUT) Then $aLUT = $D2B_DPT
    Local $iBits = Ceiling(Log($d+1+($d=0?1:0))/Log(2))
    If $iBits = 1 Then
        Return $aLUT[$iBits - 1][1] & _DecToBin($d, $iBits)
    Else
        Return $aLUT[$iBits - 1][1] & StringTrimLeft(_DecToBin($d, $iBits), 1)
        ; Wir wisseen: hier steht IMMER eine '1', also kann die 1 weg.
        ; Begründung: Da wir die Zahlen je nach Bitrate kodieren würde die
        ;             Bitrate um 1 sinken, wenn vorne eine '0' stehen würde,
        ;             also ist hier immer eine '1'. Ausnahme ist der Fall
        ;             für ein einziges Bit was '0' oder '1' sein kann und für
        ;             die Zahlen 0 oder 1 steht.
    EndIf
EndFunc

; #FUNCTION# ====================================================================================================================
; Author ........: Mars
; Description ...: Adaptives dekodieren von Links. In @extended ist die Länge der dekodierten Zahl in Bin.
;                  In $aLUT ist ein eindeutiger Lookup Table für die Prefixes. Diesen kann man z.B. via
;                  Huffman generieren.
; ===============================================================================================================================
Func _BinToDecA($b, $aLUT = 0)
        If Not IsArray($aLUT) Then $aLUT = $D2B_DPT
    For $iBits = 1 To 30 Step 1 ; Könnte man über partial match tree lösen. Hab aber keine Lust. Daher linear durchprobieren.
        If StringLeft($b, $aLUT[$iBits - 1][0]) = $aLUT[$iBits - 1][1] Then
            If $iBits = 1 Then
                Return SetExtended($iBits + $aLUT[$iBits - 1][0], _BinToDec(StringMid($b, $aLUT[$iBits - 1][0] + 1, $iBits)))
            Else
                Return SetExtended($iBits + $aLUT[$iBits - 1][0] - 1, _BinToDec(('1' & StringMid($b, $aLUT[$iBits - 1][0] + 1, $iBits - 1))))
            EndIf
        EndIf
    Next
    Return SetError(1, 0, "ERROR: Verwendeter Prefix Lookuptable passt nicht zur eingegebenen Binärzahl.")
EndFunc

; #FUNCTION# ====================================================================================================================
; Author ........: Mars
; Description ...: False: Verlängert eine Binärzahl zur Umrechnung ins B256 System | True: Entfernt die Verlängerung
; ===============================================================================================================================
Func _BinCap8($sBin, $bUnCap = False)
    Local Static $aLeft[8] = ['00000000', '0000001', '000001', '00001', '0001', '001', '01', '1']
    If Not $bUnCap Then Return $aLeft[Mod(StringLen($sBin), 8)] & $sBin
    For $i = 0 To 7 Step 1
        If StringLeft($sBin, StringLen($aLeft[$i])) = $aLeft[$i] Then Return StringTrimLeft($sBin, StringLen($aLeft[$i]))
    Next
EndFunc   ;==>_BinCap8

; --------------------------------------------------------|
; #FUNCTION# ====================================================================================================================
; Author ........: Mars
; Description ...: Wandelt eine Dualzahl(String) in eine Dezimalzahl um
; ===============================================================================================================================
Func _BinToDec($s)
    Local $l = StringLen($s)
    Return $l < 9 ? $D2BC[$s] : $l < 17 ? $D2BC[StringTrimRight($s, 8)] * 256 + $D2BC[StringRight($s, 8)] : $l < 25 ? _
    $D2BC[StringTrimRight($s, 16)] * 65536 + $D2BC[StringRight(StringTrimRight($s, 8), 8)] * 256 + $D2BC[StringRight( _
    $s, 8)] : BitShift($D2BC[StringTrimRight($s, 24)], -24) + $D2BC[StringRight(StringTrimRight($s, 16), 8)] * 65536 _
    + $D2BC[StringRight(StringTrimRight($s, 8), 8)] * 256 + $D2BC[StringRight($s, 8)]
EndFunc   ;==>_BinToDec

; #FUNCTION# ====================================================================================================================
; Author ........: Mars
; Description ...: Ermittelt eine Dualzahl(String) aus einer Dezimalzahl die kleiner als 2^31 ist
; ===============================================================================================================================
Func _DecToBin($d, $l)
    Return StringRight('00000000000000000000000000000000' & ($d < 256 ? $D2BA[$d] : $d < 65536 ? $D2BA[$d / 256] & $D2BB[BitAND($d, 255)] _
    : $d < 16777216 ? $D2BA[$d / 65536] & $D2BB[BitAND($d / 256, 255)] & $D2BB[BitAND($d, 255)] : $D2BA[BitShift($d, 24)] & $D2BB[BitAND($d / _
    65536, 255)] & $D2BB[BitAND($d / 256, 255)] & $D2BB[BitAND($d, 255)]), $l)
EndFunc   ;==>_DecToBin

; #INTERNAL# ====================================================================================================================
; Author ........: Mars
; Description ...: Initialisiert die DecToBin UDF
; ===============================================================================================================================
Func __DecToBinStartup()
    Local Static $bReady = False
    If $bReady Then Return
    Local $t = DllStructCreate('char[64]'), $p = _
            DllStructGetPtr($t), $hDll = DllOpen('msvcrt.dll')
    For $i = 0 To 255 Step 1
        DllCall($hDll, 'ptr:cdecl', '_i64toa', 'int64', _
                $i, 'ptr', $p, 'int', 2)
        $D2BA[$i] = DllStructGetData($t, 1)
        $D2BB[$i] = StringRight('0000000' & $D2BA[$i], 8)
        $D2BC[$D2BA[$i]] = $i
    Next
    DllClose($hDll)
    $bReady = True
EndFunc   ;==>_DecToBinStartup

; #INTERNAL# ====================================================================================================================
; Author ........: Mars
; Description ...: Geklaut von mir selbst. (Adaptive Huffman Encoder)
; ===============================================================================================================================
Func __AHE_TreeToLookupRec(ByRef $aLookup, ByRef $__AHET, $i = 0, $sPath = '')
    If $__AHET[$i][2] = '' Then
        $aLookup[$__AHET[$i][0]] = $sPath
    Else
        __AHE_TreeToLookupRec($aLookup, $__AHET, $__AHET[$i][0], $sPath & '0')
        __AHE_TreeToLookupRec($aLookup, $__AHET, $__AHET[$i][2], $sPath & '1')
    EndIf
EndFunc   ;==>__AHE_TreeToLookupRec

; #INTERNAL# ====================================================================================================================
; Author ........: Mars
; Description ...: Geklaut von mir selbst. (Adaptive Huffman Encoder) Vermutlich die beste Funktion die ich je geschrieben habe.
; ===============================================================================================================================
Func __AHE_BuildTreeFromSymbolHistogram(ByRef $aSymHist, ByRef $__AHET)

    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

    Local $__AHEE = UBound($aSymHist)  ;         | 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 UBound($aSymHist) - 2 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   ;==>__AHE_BuildTreeFromSymbolHistogram

Alles anzeigen

Edit 10.05.23: Vollständig adaptive Version hinzugefügt die bis uint31-1 funktioniert (und nicht wie vorher bis uint28-1)

Funktionsweise: Eine Integerzahl wird als "Prefix" + "Bitrepräsentation" abgebildet.

Beispiel:

Zahl = 244368

Theoretisch benötigte Bits = 18 (da 2^18-1 = 262143 >= Zahl), normalerweise speichert man aber 32 Bit. Und das wollen wir optimieren.

Binärdarstellung: 1 & 11011101010010000 Erstes Bit kann entfernt werden, denn es ist immer eine Eins, außer bei den Zahlen 0 und 1, wo dieses Bit tatsächlich gebraucht wird.

Prefix: 00111 (Beispielhaft, ergibt sich aus HuffmanTree)

Resultat: 00111 & 11011101010010000 -> 22 Bits um eine 18 Bit Zahl zu kodieren.

- Außerdem kann man eine eigene Wahrscheinlichkeitstabelle angeben in der man festlegen kann wie wahrscheinlich Zahlen in gewissen Bereichen sind um noch ein Paar Bits einzusparen. Diese Tabelle muss man allerdings beim Dekodieren ebenfalls mitliefern. Ansonsten benutzt man einfach die "default" Tabelle (die ich von Hand gebastelt habe, die ist ganz okay für die Meisten Fälle).

- Der Prefix wird nicht mehr (wie vorher) von Hand eingetackert, sondern vollautomatisch (Huffman) generiert.

- Beim Dekodieren wird die Bitlänge mit ausgegeben (siehe @extended), es sind also keine Trennzeichen zwischen aufeinanderfolgenden Zahlen nötig, man kann die Bits einfach hintereinanderschreiben.

Hinweis: Die Adaptive Version bringt natürlich nur etwas, wenn die Zahlen die man kodieren will nicht gleichverteilt sind. Egal wie cool die Funktion ist, die Entropie kann sie nicht überlisten.

Anwendungsfall: (hypothetisch) Ich möchte ganz viele Zahlen die maximal uint31 groß sind möglichst gut verpackt speichern. Die Zahlen sind nicht gleichverteilt (sie haben irgendein Muster, z.B. kleine Zahlen sind sehr häufig, Zahlen im bereich 2000 sind auch sehr häufig (z.B. für Jahreszahlen), große Zahlen wie 25095382 sind relativ selten), aber es sind so viele verschiedene, dass eine Entropiekodierung nicht funktioniert (da werden ja "zahlen" als einzelne Symbole interpretiert, und wenn alle Zahlen unterschiedlich sind wird die Tabelle die man speichern muss größer als wenn man die Zahlen direkt mit 31Bit/Zahl speichert). Die hier gezeigte Methode verwendet eine Entropiekodierung auf "Bereiche" anstatt auf einzelne Zahlen. Deshalb ist das ganze quasi ein "Pseudo Huffman für Zahlen die nicht mehrfach auftauchen aber in einer ähnlichen Größenordnung liegen".

Edit 12.05.23: Paar kleine Änderungen in der UDF für mehr Benutzerfreundlichkeit.

Falls Fehler auftauchen: Meldet euch, ich habe das nur kurz getestet.

lg

M

**Andy**

Hi,

Zitat von Mars

bevor ich meine eigenen Skripte wieder verlege und nie wieder finde, lade ich sie lieber mal hoch, dann findet man sie im Notfall in der Suche

so sie denn nicht wie schon viiiile andere Beiträge auch, für immer im Forennirvana verschwinden

Du hängst doch mit dem "neuen" Dec2Bin nicht etwa an dem alten Thread von 2011?!

**Mars**

Zitat von Andy

Du hängst doch mit dem "neuen" Dec2Bin nicht etwa an dem alten Thread von 2011?!

Ooooooh, ja... So findet man seinen alten Code wieder und wieder und wieder (in 10 verschiedenen threads)
Da ging es aber eher um "wie kann ich einen riesigen String aus Dezimalzahlen ins Hexadezimalsystem bringen".

**Alina**

Moin Mars

Zitat von Mars

Moin,
bevor ich meine eigenen Skripte wieder verlege und nie wieder finde, ...

Das Problem kenne ich doch. Ich habe mich aber irgendwann (letztes Jahr) entschieden, alle Include-Dateien in einen Ordner zu sammeln.

Die Dec2Bin kommt gleich dazu.

**Mars**

Ich hab ja auf meinem PC schon einen AutoIt-Ordner mit unmengen Skripten die ich üblicherweise auch korrekt benenne. Aber das klappt auch nur, wenn man alles was man mit AutoIt macht grundsätzlich in diesen Ordner verschiebt und benennt/taggt. Der "adaptive" Teil ist in irgendeinem Skript wo ich das ausprobiert hatte, habe es aber nicht in die Dec2Bin UDF eingebaut, obwohl es da eigentlich hingehört.

Ich glaube ich bastel noch eine "optimale" Version davon (der prefix wird via HuffmanTree ermittelt anstatt dass man ihn "pi mal Daumen" von Hand schätzt). Das wäre dann so:
- Input: Wahrscheinlichkeit für 1, 2, ..., n Bit Zahlen (dann kann man den Huffman mit den Symbolen 1, 2, ..., n und den Wahrscheinlichkeiten p(1), p(2), ... p(n) laufen lassen)

- Output: Prefixset das die benötigten Bits zur Darstellung dieser Zahlen minimiert.
(wir sind hier aber immernoch mit "ganzen Bits ohne Übertrag" unterwegs, also wird der Prefix auf maximal 0.5 Bit optimal, außerdem werden Sonderstellungen (z.B. die Zahl 0 taucht echt oft auf, und sollte daher nicht als "prefix + bits", sondern direkt kodiert werden) nicht berücksichtigt, was im schlimmsten fall nochmal ein Bit pro Zahl schluckt... ). Immernoch weit vom Entropielimit entfernt, aber ein erster Ansatz.

Edit: Ich bin ziemlich blöd... Habe irgendwann mal eine Base.au3 gebastelt (zur Umrechnung zwischen z.B. Base10 und Base2, vielleicht kennt man sie aus meiner Abgabe zum Kompressionswettbewerb, Februar 22 von Oscar). Dort war auch die Adaptive version... Warum hat mir die Windows Suche (die ja angeblich auch Dateiinhalte durchsucht) das nicht angezeigt? Muss ich den Ordner wirklich mit VS Code öffnen und dann suchen? Oh man...

Edit2: Adaptive Version (Huff) ist im Startpost. Die wollte ich schon seit Ewigkeiten bauen und hab es immer nicht gemacht^^

M

Mars 9. Mai 2023 um 22:54