Einfaches Preprocessing zum Komprimieren (nur eine Spielerei)

**Mars**

Moin,

habe neulich nochmal über die LZ77 Methode nachgedacht und überlegt, dass man einen ähnlichen Effekt vermutlich auch deutlich einfacher bekommen kann. Die Idee ist folgendes:

- Die Daten sind Binär '010101...' und wir wollen eine "Mustererkennung" ohne wirklich irgendwas zu rechnen.

- Baue einen Lookuptable auf, der für jede Bitfolge (von z.B. 8 Bit) angibt, wie wahrscheinlich eine "0" oder eine "1" auf diese 8 Bit folgt.

- Laufe alle Daten durch und ersetze sie durch "0" oder "1", je nachdem ob die Vorhersage gestimmt hat. Aktualisiere den LUT entsprechend nach jedem Schritt.

- Das Ganze ist trivial reversibel.

- Für einen Lookuptable mit >8Bit wird eine Map mit Stringkeys verwendet (das ist langsam). Falls man das mal in einer anderen Sprache programmiert müsste die Methode extrem schnell sein (es ist im Prinzip nur triviales Bitgeschiebe und Lookups), sollte auch ASM-freundlich sein.

- Aktuell wird nichts komprimiert, sondern nur "die Anzahl der Nullen in den Binären Daten maximiert". Vielleicht kann man die Methode aber für irgendwas als Ausgangspunkt verwenden (z.B. Lauflängenkodierung, etc). Daher "Preprocessing", es ist ein Vorverarbeitungsschritt der redundante Daten durch Nullen ersetzt.

Vermutlich hatten schon hunderte Leute dieselbe Idee, und was besonderes ist es auch nicht (daher in Off-Topic). Vielleicht kann damit ja trotzdem jemand etwas anfangen

Beispiel mit zwei Datensätzen (oben im Skript via "GetSomeData" und "GetSomeData2") abrufbar. In der Konsole kann beobachtet werden die der Algorithmus "warmläuft", zu Beginn ändert sich fast nichts am Input (da jede Vorhersage daneben liegt), später bestehen die Daten aber zum Großteil aus Nullen (im Redundanten Fall bestehen sie quasi exklusiv aus Nullen). Getestet wurde nur rudimentär.

AutoIt

; Test

Local $sOriginal = GetSomeData() ; Normaler Text ohne wiederholungen
;~ Local $sOriginal = GetSomeData2() ; Sehr redundanter Text

Local $v = StringToStruct($sOriginal) ; Um jegliche Encoding Probleme zu umgehen -> Array of Bytes (kennt nur Bytes und sonst nichts)
Local $b = StructToBin($v)

Local $LUT_Bits = 16 ; Wert zwischen 1 und 16. Bis 8 Bit gehts "schnell" ab 8 Bit wirds langsam (StringLUT = Langsam). Größerer Table = besser (Falls genug Daten vorhanden sind, ab ca. 4KB ist ein 16Bit Table am besten)

Local $c = PredictionEncode($b, $LUT_Bits)
Stats($c, $LUT_Bits, 'encoded')
Local $d = PredictionDecode($c, $LUT_Bits)
Stats($d, $LUT_Bits, 'decoded')
ConsoleWrite(($d = $b ? '+ OK' : '! FAIL') & @CRLF)
ConsoleWrite('original:               ' & $b & @CRLF)
ConsoleWrite('reduced naive entropy:  ' & $c & @CRLF)
ConsoleWrite('restored naive entropy: ' & $d & @CRLF)

Func Stats($x, $n, $info = '')
	StringReplace($x, '0', '', 0, 1)
	Local $zero = @extended
	StringReplace($x, '1', '', 0, 1)
	Local $one = @extended
	ConsoleWrite($info & ' Bits: ' & StringLen($x) & ' LUT-size: ' & StringRight(' ' & $n, 2) & ' #0: ' & $zero &StringFormat(' (%.1f%%)',(100*$zero/($zero+$one))) & ' #1: ' & $one & StringFormat(' (%.1f%%)',(100*$one/($zero+$one))) & @CRLF)
EndFunc

Func PredictionDecode($sBin, $n = 8)
	Local $intN = Int(2^$n)
	Local $_[$intN][2] ; Linearer Lookup für die letzten N bits: [i][0] = Akkumulierte Einsen, [i][1] = Anzahl Gesamt
	For $i = 0 To $intN - 1 Step 1
		$_[$i][0] = 0.5 ; 50/50 chance zu Beginn. (da > 0.5 gecheckt wird ist das per default eine Null)
		$_[$i][1] = 1 ; Initialwert hat das Gewicht von 1. Ansich kann man jede Zahl >0 verwenden, aber 1 war intuitiv
	Next
	Local $start = $n + 1, $end = StringLen($sBin)
	Local $rest = '', $roll = StringLeft($sBin, $n)
	Local $iLast = '', $pred = '', $right = '', $iLUT = 0
	If $n <= 8 Then ; Maps für einen schnellen Lookup [11111111] gehen leider nicht bis 16 Bit, also [1111111111111111]
		Local Static $Int256 = Int256() ; 8Bit Lookup ohne führende Nullen (da Integerkey)
		For $i = $start To $end Step 1
			$iLast = Int($roll)
			$iLUT = $Int256[$iLast]
			$pred = ($_[$iLUT][0] / $_[$iLUT][1]) > 0.5 ? 1 : 0
			$right = StringMid($sBin, $i, 1) = '1' ? 1 - $pred : $pred
			$_[$iLUT][0] += Int($right) ; 0 oder 1
			$_[$iLUT][1] += 1
			$rest &= $right
			$roll = StringTrimLeft($roll, 1) & $right
		Next
	Else ; Stringkeys sind wiederum in Ordnung, aber eben langsamer.
		Local Static $Int65536 = Int65536() ; 16Bit Lookup mit führenden Nullen (da Stringkey)
		For $i = $start To $end Step 1
			$sLast = StringRight('0000000000000000' & $roll, 16)
			$iLUT = $Int65536[$sLast]
			$pred = ($_[$iLUT][0] / $_[$iLUT][1]) > 0.5 ? 1 : 0
			$right = StringMid($sBin, $i, 1) = '1' ? 1 - $pred : $pred
			$_[$iLUT][0] += Int($right) ; 0 oder 1
			$_[$iLUT][1] += 1
			$rest &= $right
			$roll = StringTrimLeft($roll, 1) & $right
		Next
	EndIf
	Return StringLeft($sBin, $n) & $rest
EndFunc

Func PredictionEncode($sBin, $n = 8)
	Local $intN = Int(2^$n)
	Local $_[$intN][2] ; Linearer Lookup für die letzten N bits: [i][0] = Akkumulierte Einsen, [i][1] = Anzahl Gesamt
	For $i = 0 To $intN - 1 Step 1
		$_[$i][0] = 0.5 ; 50/50 chance zu Beginn. (da > 0.5 gecheckt wird ist das per default eine Null)
		$_[$i][1] = 1 ; Initialwert hat das Gewicht von 1. Ansich kann man jede Zahl >0 verwenden, aber 1 war intuitiv
	Next
	Local $start = $n + 1, $end = StringLen($sBin)
	Local $rest = '', $roll = StringLeft($sBin, $n)
	Local $iLast = '', $pred = '', $right = '', $iLUT = 0
	If $n <= 8 Then ; Maps für einen schnellen Lookup [11111111] gehen leider nicht bis 16 Bit, also [1111111111111111]
		Local Static $Int256 = Int256() ; 8Bit Lookup ohne führende Nullen (da Integerkey)
		For $i = $start To $end Step 1
			$iLast = Int($roll)
			$iLUT = $Int256[$iLast]
			$pred = ($_[$iLUT][0] / $_[$iLUT][1]) > 0.5 ? 1 : 0
			$right = StringMid($sBin, $i, 1)
			$_[$iLUT][0] += Int($right) ; 0 oder 1
			$_[$iLUT][1] += 1
			$rest &= ($pred = $right) ? 0 : 1
			$roll = StringTrimLeft($roll, 1) & $right
		Next
	Else ; Stringkeys sind wiederum in Ordnung, aber eben langsamer.
		Local Static $Int65536 = Int65536() ; 16Bit Lookup mit führenden Nullen (da Stringkey)
		For $i = $start To $end Step 1
			$sLast = StringRight('0000000000000000' & $roll, 16)
			$iLUT = $Int65536[$sLast]
			$pred = ($_[$iLUT][0] / $_[$iLUT][1]) > 0.5 ? 1 : 0
			$right = StringMid($sBin, $i, 1)
			$_[$iLUT][0] += Int($right) ; 0 oder 1
			$_[$iLUT][1] += 1
			$rest &= ($pred = $right) ? 0 : 1
			$roll = StringTrimLeft($roll, 1) & $right
		Next
	EndIf
	Return StringLeft($sBin, $n) & $rest
EndFunc

Func StringToStruct($sString)
	Local $vString = DllStructCreate('char s[' & StringLen($sString) & ']')
	$vString.s = $sString
	Return $vString
EndFunc

Func StructToString($vString)
	Local $v = DllStructCreate('char s[' & DllStructGetSize($vString) & ']', DllStructGetPtr($vString))
	Return $v.s
EndFunc

Func BinToStruct($sBin)
	Local Static $Int256 = Int256()
	Local $vRet = DllStructCreate('byte b[' & Int(StringLen($sBin) / 8) & ']'), $k = 1
	For $i = 1 To StringLen($sBin) Step 8
		DllStructSetData($vRet, 1, $Int256[Int(StringMid($sBin, $i, 8))], $k)
		$k += 1
	Next
	Return $vRet
EndFunc

Func StructToBin($vStruct)
	Local Static $Bin256 = Bin256()
	Local $vBytes = DllStructCreate('byte b[' & DllStructGetSize($vStruct) & ']', DllStructGetPtr($vStruct)), $sRet = ''
	For $i = 1 To DllStructGetSize($vStruct) Step 1
		$sRet &= $Bin256[$vBytes.b(($i))]
	Next
	Return $sRet
EndFunc

Func Bin256()
	Local Static $Bin16 = Bin16()
	Local $Bin256[]
	For $i = 0 To 255 Step 1
		$Bin256[$i] = $Bin16[Int($i/16)] & $Bin16[Int($i - Int($i/16) * 16)]
	Next
	Return $Bin256
EndFunc

Func Int256()
	Local Static $Bin16 = Bin16()
	Local $Int256[]
	For $i = 0 To 255 Step 1
		$Int256[Int($Bin16[Int($i/16)] & $Bin16[Int($i - Int($i/16) * 16)])] = $i
	Next
	Return $Int256
EndFunc

Func Int65536()
	Local Static $Bin256 = Bin256()
	Local $Int65536[] ; Ja, Maps sind "langsamer" als Arrays bei sehr vielen Elementen. Ich habe die Zeiten hier nicht gestoppt. Vielleicht gehts schneller, ist aber für dieses Beispiel wurst.
	For $i = 0 To 65535 Step 1
		$Int65536[$Bin256[Int($i/256)] & $Bin256[Int($i - Int($i/256) * 256)]] = $i ; StringKeys, da Array Indices hier nicht mehr gehen, da 1111111111111111 ungefähr 2^50
	Next
	Return $Int65536
EndFunc

Func Bin16()
	Local $Bin16[]
	$Bin16[0] = '0000'
	$Bin16[1] = '0001'
	$Bin16[2] = '0010'
	$Bin16[3] = '0011'
	$Bin16[4] = '0100'
	$Bin16[5] = '0101'
	$Bin16[6] = '0110'
	$Bin16[7] = '0111'
	$Bin16[8] = '1000'
	$Bin16[9] = '1001'
	$Bin16[10] = '1010'
	$Bin16[11] = '1011'
	$Bin16[12] = '1100'
	$Bin16[13] = '1101'
	$Bin16[14] = '1110'
	$Bin16[15] = '1111'
	Return $Bin16
EndFunc

Func GetSomeData()
	Return 'Ich bin ein Teststring. Hier könnte alles mögliche stehen. Irgendwie muss ich ein paar KB Text voll bekommen... Wie könnte man das anstellen?' & _
	'Func Int65536()' & _
	'	Local Static $Bin256 = Bin256()' & _
	'	Local $Int65536[] ; Ja, Maps sind "langsamer" als Arrays bei sehr vielen Elementen. Es ist aber dennoch schneller als ein Funktionsaufruf oder irgendwelche zusätzlichen Operatoren.' & _
	'	For $i = 0 To 65535 Step 1' & _
	'		$Int65536[$Bin256[Int($i/256)] & $Bin256[Int($i - Int($i/256) * 256)]] = $i ; StringKeys, da Array Indices hier nicht mehr gehen, da 1111111111111111 ungefähr 2^50' & _
	'	Next' & _
	'	Return $Int65536' & _
	'EndFunc' & _
	'Leider lässt die Methode erst bei ziemlich viel Text (ein paar KB) die Muskeln spielen. Für sehr kleine Textmengen sind niedrige LUT Größen besser geeignet, wir wollen hier aber den 16-Bit Table verwenden!' & _
	'To use this method, one proves that the history of the given process can be recorded in an efficient way, such that the state of the process at any past time can be recovered from the current state and this record, and such that the amount of additional information that is recorded at each step of the process is (on average) less than the amount of new information randomly generated at each step. The resulting growing discrepancy in total information content can never exceed the fixed amount of information in the current state, from which it follows that the process must eventually terminate. This principle can be formalized and made rigorous using Kolmogorov complexity.[3]' & _
	'Ein bisschen Wikipediatext kann nicht schaden...' & _
	'An example given by both Fortnow[3] and Tao[4] concerns the Boolean satisfiability problem for Boolean formulas in conjunctive normal form, with uniform clause size. These problems can be parameterized by two numbers (k,t) where k is the number of variables per clause and t is the maximum number of different clauses that any variable can appear in. If the variables are assigned to be true or false randomly, then the event that a clause is unsatisfied happens with probability 2−k and each event is independent of all but r = k(t − 1) other events. It follows from the Lovász local lemma that, if t is small enough to make r < 2k/e (where e is the base of the natural logarithm) then a solution always exists. The following algorithm can be shown using entropy compression to find such a solution when r is smaller by a constant factor than this bound: ' & _
	'Zeilenumbrüche ignorieren wir mal. Selbstverständlich klappt es damit auch!' & @CRLF & _
	'Das hier kann super komprimiert werden: ------------------------------------------------------------------------------------------------------- ziemlich cool. 3.141592654' & @CRLF & _
	'blablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablabla' & _
	'Sooo wir sind jetzt bei 22336 Bits angekommen.' & _
	'Es folgen ein paar Stellen von PI damit "zufällige" Daten vorliegen: 3.1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 8214808651 3282306647 0938446095 5058223172 5359408128 4811174502 8410270193 8521105559 6446229489 5493038196 4428810975 6659334461 2847564823 3786783165 2712019091 4564856692 3460348610 4543266482 1339360726 0249141273 7245870066 0631558817 4881520920 9628292540 9171536436 7892590360 0113305305 4882046652 1384146951 9415116094 3305727036 5759591953 0921861173 8193261179 3105118548 0744623799 6274956735 1885752724 8912279381 8301194912' & _
	'Ist nicht wirklich zufällig, aber man weiß was ich meine. Der Witz ist jetzt, wenn man die selben Zahlen wiederholt, werden sie fast komplett durch nullen ersetzt, weil genau diese Abfolge ja bereits bekannt ist:' & _
	'3.1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 8214808651 3282306647 0938446095 5058223172 5359408128 4811174502 8410270193 8521105559 6446229489 5493038196 4428810975 6659334461 2847564823 3786783165 2712019091 4564856692 3460348610 4543266482 1339360726 0249141273 7245870066 0631558817 4881520920 9628292540 9171536436 7892590360 0113305305 4882046652 1384146951 9415116094 3305727036 5759591953 0921861173 8193261179 3105118548 0744623799 6274956735 1885752724 8912279381 8301194912' & _
	'Das kann man jetzt im "reduced naive entropy" Stream beobachten :)' & @CRLF & _
	'Hier noch ein paar Plot-Daten:' & _
	'# 256 Symbols' & @CRLF & _
	'128	9.4' & @CRLF & _
	'256	10.1' & @CRLF & _
	'512	11.4' & @CRLF & _
	'1024	11.7' & @CRLF & _
	'2048	13.3' & @CRLF & _
	'4096	16' & @CRLF & _
	'35k Bits sollten zu Demonstrationszwecken ausreichen.' & _
	'In diesem Beispiel wird die Anzahl der Nullen von 55.9% auf 79.0% erhöht. Damit kann man doch bestimmt irgendwas anfangen (z.B. Lauflängencodierung etc...)'
EndFunc

Func GetSomeData2()
	Return 'Zu Demonstrationszwecken bei sehr redundanten daten gibts hier noch ein Beispiel:' & _
	'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?' & _
	'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?' & _
	'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?' & _
	'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?' & _
	'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?' & _
	'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?' & _
	'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?' & _
	'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?' & _
	'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?' & _
	'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?' & _
	'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?123456789ABCDEFGHIJKLMNOPQRSTUVWXYZÄÖÜ!"§$%&/()=?' & _
	'Das sind 44144 Bits und davon sind 97.9% Nullen'
EndFunc

Alles anzeigen

(Edit: Genau das Gleiche habe ich vor Urzeiten schonmal gebastelt (nur viel umständlicher) und den Code nicht mehr gefunden)

lg

M

**SOLVE-SMART** · Poweruser seit 21.01.2023

Hi Mars ,

ich habe ehrlich gesagt keine Verwendung dafür, doch das liegt auch einfach daran das ich mich noch nicht wirklich damit beschäftigt habe und mir nicht ganz klar ist in wie weit ich dies als "Ausgangspunkt" für etwas anderes nutzen kann, dennoch finde ich es spannend, was in so mancher Kopf vorgeht 😅 ... ( nett gemeint 😇 ). Außerdem lerne ich liebend gern dazu, jeden Tag ein wenig.

encoded Bits: 36816 LUT-size: 16 #0: 29074 (79.0%) #1: 7742 (21.0%)
decoded Bits: 36816 LUT-size: 16 #0: 20580 (55.9%) #1: 16236 (44.1%)

Zitat von Mars

(Edit: Genau das Gleiche habe ich vor Urzeiten schonmal gebastelt (nur viel umständlicher) und den Code nicht mehr gefunden)

Übrigens witzig mal wieder eines deiner Beispiele, die du schon so manche Male erwähnt hast, zu sehen 👍 .

Viele Grüße
Sven

**Mars**

Mit Ausgangspunkt ist gemeint, dass man das als Vorstufe für einen Kompressionsalgorithmus verwenden kann. Üblicherweise bekommt man eine bessere Kompression, wenn irgendeine Struktur in den Daten vorliegt die man ausnutzen kann. In diesem Fall: Sehr viel mehr Nullen als Einsen, dafür aber etwas unstrukturierter. (Ist also für einen Kodierer der Muster erkennt ungeeignet, die Muster wurden ja quasi in Nullen umgewandelt)

Mögliche Folgeschritte wären:
- Lauflängenkodierung (ist intuitiv das erste was mir einfällt)
- Falls Lauflängenkodierung im Binärformat -> Arithmetische Entropiekodierung als Folgeschritt (huffman geht hier nicht besonders gut, da die Symbole nicht mehr aligned sind).
- Falls Lauflängenkodierung mit Tokens -> Irgendeine Entropiekodierung (hier hat man die Symbole einzeln -> Jede Methode geht) als Folgeschritt -> Fertig.

Probleme der aktuellen Methode:
- Je größer der LUT, desto länger ist die Warmlaufphase, da der LUT erstmal gefüllt werden muss
- Je größer der LUT, desto besser das Ergebnis nach der Warmlaufphase, aber man ist auf 16 Bit beschränkt.

Lösungsansatz den ich irgendwann ausprobiere:
- Baue einen beliebig großen "pseudo" LUT aus mehreren 8Bit Blöcken zusammen.
- So siehts aus: [Block n-2][Block n-1][Block n][Bit x] -> Akuell wird nur [Block n] verwendet um x vorherzusagen. Man könnte allerdings auch alle anderen Blöcke einbeziehen. Da hier (aus Stochastik-Sicht) keine Unabhängigkeit vorliegt (es ist also ein Unterschied ob ich ausgehend von [Block n-1 (8Bit)] und [Block n (8Bit)] das x vorhersage, oder ob ich einen einzigen 16Bit Block nehme) muss man für halbwegs gute Ergebnisse vermutlich eine Art Interleaving verwenden.

Trivialbeispiel mit 4 x 8Bit Blöcken -> [aaaaaaaa][bbbbbbbb][cccccccc][dddddddd][x] -> 4 Vorhersagen mit den Blöcken ohne Änderung (habe keine Nummern drangeschrieben, die aaaaaaaa sind eigentlich a1a2a3...usw)
Zusätzlich mit Interleaving [abcdabcd][abcdabcd][abcdabcd][abcdabcd][x] -> 4 Weitere Vorhersagen für x
Eine Linearkombination (mit irgendwelchen Koeffizienten die ich nicht kenne) dieser 8 Vorhersagen dient als Approximation der Vorhersage die ein einziger 32Bit Block liefern könnte. Je mehr Vorhersagen mit verschieden Verwobenenen 8 Bit Blöcken man verwendet, desto besser die Approximation. Gleichzeitig sinkt die Warmlaufphase, da man nicht 2^32 Zustände, sondern (im Beispielfall) nur 8 * 2^8 = 2048 Zustände vollmachen muss. Ich schätze damit sind auch bei "normalem Text" 90%+ Nullen möglich (statt 79%). Wäre zumindest lustig, wenn das gehen würde

Danach kommt die "swap Methode" (aus dem Permutationen Komprimieren Thread) zum Einsatz (wobei hier die Nullen und Einsen geswappt werden um sie zu sortieren). Dann sind die Daten in folgender Form: [Bits zur Steuerung der Swaps][alle Einsen][alle Nullen]. Alle Einsen und Alle Nullen können als 2 Integer gespeichert werden, sodass die komprimierten Daten nur noch aus Swap-Positionen + 2 Int bestehen. Hehehe. Damit werde ich die Welt erobern.

M

🌍	Au3Forums
🎲	AutoIt (de) Cheat Sheet / en
💎	Code Katas: Eins, Zwei, Drei
🔮	GitHub
🥳	Poweruser seit 21.01.2023
🎭	Sammlung von GitHub Benutzern mit AutoIt Projekten
🔭	Umgang mit Powershell-Output
🔭	Umgang mit SQLite
✂	VSCode-AutoItSnippets
🎬	WebDriver Crashkurs
📑	WebDriver FAQs
👨‍💻	WebDriver Beispiel (Login, Klicks, Daten eingeben, robustes Warteverhalten)
👨‍💻	WebDriver Beispiel (Texte von Website lesen, in CSV überführen)