Einzigartiger Komprimierungsalgorithmus

Vielen herzlichen Dank!

DesertMemphis hat meine Idee im Prinzip verstanden.

Zu deinen fragen:

Die länge der einzelnen blöcke ist vordefiniert. z.B. nimmt man 1024 bytes. also weiß man, dass der unkomprimierte Block 8192 Bit lang ist.
Wenn man jetzt drüber läuft, hat er evtl nur noch 6000 Bit + die Regel. Die Regel MUSS in dem Fall begrenzt sein.
d.h. es gibt z.B. nur 10 einträge in der Regel, also (2)0(5)1(3)0 ... diese Regel muss sich durch den ganzen 1024 Byte block ziehen, also immer wieder von vorne greifen. Dann kann ich genau sagen, wie lange die Regel ist. Ich nehm also aus dem Block die Regel raus und wende die so lange an, bis der Block wieder 8192 Bits hat, dann beende ich den block und schreib den an die entpackte datei wieder ran.
Nur wegen der kleinigkeit, dass sich die Regel durch so einen ganzen Block ziehen muss, schaff ichs ned, nen Algo zu schreiben :-(

ps: Ich hab auch keinen Dr. Titel bzw Niveau, aber ein sehr gutes Vorstellungsvermögen und teilweise sehr kranke gedankengänge. Ich glaub, sowas reicht um hier mitreden zu können :-)
(zumindest hoff ich das)

Hmmm... ganz verstanden hab ich deine Methode noch nicht, aber das was ich verstanden habe:
Auf einen bestimmten Block, zb: 1024 Byte wird 10 mal die Regel angewendet... Das bedeutet dennoch, dass zwar die Länge der Regel im komprimierten Block bekannt ist, die Länge des unkomprimierten "Rests" des Blocks jedoch immer noch variabel... ausser du hast vorgesehen, dass dieser auch nur einer gewissen länge entsprechen darf, wodurch die ganze Logik extrem kompliziert erscheint. Sry :/

Ich hab heute noch einen etwas genaueren Versuch mit der von mir abgeleiteten Methode gemacht und einige Berechnungen gefunden:

---
Block: ein Teil der zu komprimierenden Datei, wobei die Datei in gleich große Blöcke zerteilt wird
Abfolge: Wenn der selbe Wert an jeder Xten Stelle im Block enthalten ist
Wert: Gibt an ob die bei jedem Schritt aus dem Block entfernte Abfolge einer 0 oder einer 1 entspricht
Index: gibt an, an jeder wievielten Stelle der Wert gefunden wurde
nIndex: Anzahl der Wiederholungen in einer Abfolge
Output: die Daten des Blocks in komprimierter Form
---

Mein Muster-Algo untersucht zuerst jede 1te Stelle des Blocks. Wird eine Abfolge gefunden, wird sie in den Output geschrieben und aus dem Block entfernt.
Wird keine Abfolge gefunden, unersucht er jede 2te, dann 3te Stelle.... usw.
Daraus ergibt sich, dass LIndex, die Bitlänge des Index, abhängig von der Bitlänge des Blocks ist, bzw umgekehrt

LBlock = 2^LIndex * 2 - 1

bzw.

LBlock = 2^(LIndex + 1) - 1

Die WorstCase verlangt, dass der Index mindestens die Stelle angeben kann, die der Hälfte der LBlock plus 1 entspricht, denn wurde bis zur Hälfte keine Abfolge gefunden, dann kann ab der nächsten Stelle nur noch eine Abfolge mit nIndex = 1 Wiederholungen gefunden werden.


Der Algo wiederholt den Vorgang so oft, bis nur noch ein Wert im Block enthalten ist. Das ist der einzige Fall, in dem der Index 1 ist. So können die Blöcke dann beim entpacken seperiert werden, ohne zusätzliche "Unterteilungs-Bits" zu benötigen.

Das Problem ist nur, dass diese Logik kaum zu einer Kompression führen wird:
Das Verhältnis von...

LBlock : (LIndex + LWert) * nAbfolgen

...müsste kleiner als 1 sein!

Noch deutlicher wird das, wenn man überlegt, dass im Schnitt mit jeder gefunden Abfolge mindesten so viele Bit aus dem Block entfernt werden müssten, wie zum abspeichern der Abfolge im Output benötigt werden:

nIndex * LWert : LIndex + LWert

Da LWert in diesem Versuch immer 1 ist:

nIndex : LIndex + 1


Kleines Beispiel:

Ein Block mit 31 Bit ergibt eine Index Bitlänge von 4 (...0-15... bzw ...jede 1te - jede 16te Stelle...)
Jede Abfolge im Output würde also 5 Bit benötigen (4 für den Index plus 1 für den Wert "0" oder "1")
Um eine Kompression zu erhalten müsste der Block also nach maximal 6 Abfolgen "aufgelöst" worden sein (6 Abfolgen zu je 5 Bit = 30 Bit Outputlänge von original 31)
Im Schnitt müssten mit jeder Abfolge 5,166° Bit aus dem Block aufgelöst werden (31 Bit Originallänge in 6 Abfolgen aufgelöst)
Und das... sind zu viele...
Erhöt man die Blocklänge, verbessert sich zwar die Anzahl der Abfolgen, jedoch erhöht sich auch die Anzahl der Bit, die pro Abfolge entfernt werden müssten:

63Bit LBlock -> ~10 Abfolgen -> im Schnitt 6,3 Bit pro Abfolge

Nicht dass bei mir im Moment Langeweile herrscht, aber sollte sich die Zeit finden, dan werde ich diesen Algo mal coden und mit extrem hohen Blocklängen austesten... sollte sich was tolles ergeben lass ich es euch wissen ;)



*EDIT

Habe nocheinmal genauere Überlegungen angestellt:


LBlock = 2^(LIndex + 1) - 1
---
maxLOutput = LBlock - 1
maxLOutput = 2^(LIndex + 1) - 2
---
maxAbfolgen = maxLOutput / LIndex + 1
maxAbfolgen = (2^(LIndex + 1) - 2) / LIndex + 1
---
BitsProAbfolge = LBlock / maxAbfolgen
BitsProAbfolge = (2^(LIndex + 1) - 1) / ((2^(LIndex + 1) - 2) / LIndex + 1)
---
Wahrscheinlichkeit = 100 / 2^(BitsProAbfolge - 1)
Wahrscheinlichkeit = 100 / 2^(2^(LIndex + 1) - 1) / ((2^(LIndex + 1) - 2) / LIndex + 1)
---

Wenn diese Überlegungen korrekt sind, was ich stark hoffe :D, dann würde das bedeuten, dass die größte Wahrscheinlichkeit einer erfolgreichen Komprimierung bei einer Blocklänge von 3 Bit liegt; Tendenz stark fallend :/

IndexLänge(Bit) / BlockLänge(Bit) / Wahrscheinlichkeit(%)
1/ 3 / 25
2 / 7 / 17,67
3 / 15 / 10,25
...
13 / 16383 / 0,01

Der Gegenbeweis:
Bei einer Blocklänge von 3 Bit darf der Output maximal 2 Bit lang sein.
3 Bit Blocklänge -> 1 Bit für den Index + 1 Bit für den Wert -> 2 Bit im Output Pro Abfolge
Der Block Müsste also mit einer Abfolge aufgelöst werden können, was bei 3 Bit nur im Falle "000" bzw. "111" der Fall wäre.
Das sind 2 Situationen von 8 möglichen = 25% Wahrscheinlichkeit.

Wenn ich das richtig in Erinnerung habe, dann erhält man das gleiche Ergebnis, wenn man den Huffman code auf eine beliebige Datei anwendet... ein Versuch könnte sich also doch lohnen... oder seh ich da was falsch?