Einzigartiger Komprimierungsalgorithmus

Jetzt mal zu einem Thema aus dem EDV-Bereich. Seit ein paar Tagen beschäftige ich mich in Gedanken (z. T. rein philosophisch) mit dem Thema Datenkompression. Wer jetzt nicht weiß worum es geht, hier eine kurze Erläuterung, damit es auch jeder versteht:

Ein Komprimierungs-Algorithmus (man könnte auch Packer-Algorithmus oder Kompressions-Algorithmus sagen) ist die Methode, mit der man Daten (z. B. den Inhalt von Computerdateien) verkleinern kann, so dass das Ergebnis weniger Speicherkapazität braucht als das Originial. Es gibt da eine ganze Menge an unterschiedlichen Methoden. Musik wird z. B. häufig nach dem MP3-Verfahren (Mpeg Layer 3) komprimiert, bei Bildern kommt z. B. JPG (JPEG) zum Einsatz und bei Videos MPG (MPEG) oder AVI. Das Komprimieren mit den eben genannten Verfahren bewirkt immer (mehr oder weniger kleine) Verluste im Ergebnis. Dafür sind sie aber sehr effizient bei der Reduktion der Datenmengen. Dann gibt es noch jede Menge an Methoden, wie man Datenmengen reduzieren kann, so dass man sie anschließend wieder in Originalform zurück bringen kann, z. B. bei den Verfahren (PK-)ZIP, RAR usw.

Jetzt muss ich erwähnen, dass ich mich noch nie näher über diese Thematik informiert habe. Alles was ich hier und speziell im Folgenden schreibe, spiegelt meine ganz persönlichen Erkenntnisse und Erfahrungen wieder.

Was mich verwundert hat: Egal mit welchem Verfahren eine Datei komprimiert wird, irgendwann kommt der Punkt, wo jedes weitere Komprimieren zwecklos wird, da die Datenmenge nicht weiter reduziert werden kann. So können gut komprimierte Inhalte auch mit anderen Verfahren nicht noch weiter komprimiert werden.

Eigentlich erscheint das auch logisch, denn sonst könnte ich durch mehrmaliges Komprimieren immer noch bessere Ergebnisse erzielen. Das wäre natürlich genial. Aber das Gegenteil scheint der Fall zu sein: Das Ergebnis einer Komprimierung kann unter diesen Umständen nämlich noch mehr Speicher brauchen als das Original.

Was ebenfalls logisch erscheint: Je mehr Rechenzeit ein schlaues Komprimierungsverfahren braucht, umso besser ist in der Regel das Ergebnis im Bezug auf die Datenreduktion. Aber! Irgendwann ist einfach schluss! Dann braucht man ein vielfaches der Rechenzeit, um noch ein paar Bytes mehr an Ersparnis heraus zu quetschen und ruck zuck ist man an einem Punkt angelangt, an dem einfach nichts mehr geht.

Über einen möglicherweise neuartigen Algorithmus (Eigenentwicklung von mir) habe ich mir den Kopf zerbrochen. Dieser sollte in der Lage sein, eine Datei revolutionärer weise NUR abhängig von der Berechnungszeit (!) praktisch FAST beliebig klein zu machen, in jedem Fall jedoch SEHR klein im Verhältnis zum Original.

Meine Überlegungen waren sehr detailiert, auch im Bezug auf den Algorithmuskern, auf den ich aus Platzgründen hier aber nur prinzipiell eingehen werde.

Spezielle Zufallszahlen (die in derselben Reihenfolge jederzeit reproduzierbar sind) bilden eine Grundlage für die Kompressionsmethode und werden bei der Berechnung des Algorithmus mit einbezogen. Zudem wird die Datei immer wieder und immer wieder umgerechnet, nach einem Algorithmus, der von diesen Zufallszahlen gewählt wird (wie schon erwähnt handelt es sich um spezielle Zufallszahlen, die beim Dekomprimieren wiederholt werden können). Bei den vereinzelten Komprimierungsvorgängen könnte und wird es natürlich oft vorkommen, dass das Ergebnis keine Datenreduktion sondern eine Datenvermehrung zur Folge hätte. In diesem Falle wird dieses Ergebnis wieder verworfen und eine Berechnung auf Grundlage der nächsten Zufallszahl vorgenommen. Mit diesem Ergebnis, einer etwas kleineren Datenmenge als beim vorherigen Durchgang, wird der gesamte Komprimier-Vorgang so oft wiederholt, bis insgesamt eine brauchbare Datenreduktion erfolgt ist.

Die Wiederherstellung der ursprünglichen Daten erfolgt umgekehrt. Die Zufallszahlen werden in umgekehrter Reihenfolge für die Berechnungsgrundlage hergenommen (es wurde beim Komprimieren die Information mitgespeichert, die wievielte Zufallszahl beim allerletzten Komprimierungsdurchlauf tätig war). Es wird der gesamte Datensatz jeweils um eine Stufe zurückgerechnet und das immer wieder. Nur wird jetzt der Vorgang mit der vorausgegangenen Zufallszahl immer dann wiederholt, wenn der jeweils erzeugte Datensatz weniger Daten enthält als zuvor. Die Datei wird also mit jedem Durchgang jetzt wieder aufgebläht, bis die gleiche Anzahl an Berechnungsyklen durchlaufen wurde wie beim Komprimieren der Datei.

Wo ist jetzt der Haken? Es muss einen geben. Ich glaube, ihn gefunden zu haben.

Der Algorithmuskern macht sich ein ungleichmäßiges Vorkommen aller möglichen Informationseinheiten zu Nutze. Manche Zahlen kommen demnach sicherlich öfter vor als andere. Nur wenn ein Komprimierungszyklus aufgrund einer exakt homogenen (gleichförmigen) Verteilung sämtlicher Zahlen versagt, gibt es kein Weiterkommen mehr. Dieser Zustand wird sich nach meiner Theorie definitiv irgendwann einstellen. In diesem Fall müsste für diesen Berechnungszyklus auf eine Ausweichmethode umgestellt werden. Diese könnte sich anstatt des ungleichmäßigen Zahlenvorkommens die gleichmäßige Aufteilung (Positionierung) der vorhandenen Zahlen zu Nutze machen, solange diese bestimmte erkennbare Strukturen aufweist.

Wenn aber weder die eine, noch die andere erhoffte Datenstruktur gegeben ist, haben wir ein kleines Problem. Zudem müssten wir in diesem Fall die Informationen speichern, bei welchen Berechnungszyklen auf die Ausweich-Berechnungsmethode zurück gegriffen wurde.

Darum bin ich zu folgender Schlussfolgerung gekommen:


Eine Datei, die

a) eine exakt gleiche Anzahl aller möglichen Informationseinheiten aufweist

und

b) keine erkennbare Datenstruktur, also Anordnung der vorhandenen Informationseinheiten besitzt,

kann unter keinen Umständen weiter komprimiert werden.


Vielleicht ist meine Theorie auch falsch. Um sie zu untermauern habe ich ein Programm geschrieben, das mir eine Datei erzeugt, deren Inhalt diesen Kriterien entspricht (im Detail: Jedes erzeugte Byte wird von einem zufälligen Wert bestimmt, der keinem seiner Vorgängerwerte entspricht. Wurden alle möglichen Werte erzeugt, beginnt die Prozedur von neuem, bis die Datei eine bestimmte Größe erreicht hat).

Versuche, diese Datei mit ZIP, RAR etc. zu komprimieren hatten immer zur Folge, dass das komprimierte Endergebnis größer war als das Original. Das bestätigt meine Theorie.

Deshalb mein Aufruf: Kennt jemand einen Algorithmus oder ein Programm, das eine solche Datei zu verkleinern vermag?

Für experimentelle Zwecke stelle ich sie hier vore...

mit WinAce habe ich zumindest erzielt, dass die Zieldatei exakt die selbe Grösse hatte. hilft dir aber wahrscheinlich nicht weiter...
Ansonsten würde ich als naiver Laie sagen, dass diese Datei nicht weiter komprimiert werden kann...
ich hoffe dem ist nicht so, denn das was du da oben geschrieben hast ist wirklich beeindruckend, ja fast revolutionär :).

Ein Freund von mir sagt folgendes dazu:

.
.
.
.
.

Nehmen wir mal an, man nimmt einen Pseudozufallsgenerator mit der Seed 1.

Dann kann man, wenn man so will, mehrere Gigabyte Daten (je nach Periode des Zufallsgenerators) auf ein Bit komprimieren Problem ist dabei nur:

-Rückrechenbarkeit:
Man kann aus den komprimierten Daten (die 1) zwar leicht die unkomprimierten berechnen (die Zufallszahl), allerdings kann man die Zufallszahl nur durch roher Gewalt bekommen - was bei 1Bit = 2 Möglichkeiten ja nicht allzu lange dauern würde, aber:

-Nicht universell einsetzbar:
Mit einer 1 Bit Seed kann man maximal 2 Dateien verschlüsseln, mit einer 32 Bit maximal 4Giga... die wenigsten davon sollten ein sinnvolles Ergebnis erzielen.
Wenn man alle Daten auf diese Art und Weise komprimieren wollen würde, müsste man eine unendliche Anzahl von Komprimierungsalgorithmus (Zufallsgeneratoren) haben, welche eine unendliche Menge von Platz verbrauchen würden.

Man kann Daten nicht (nahezu) beliebig komprimieren. Man kann 256 verschiedene Zustände nicht in weniger als 8 Bit darstellen. Geht nicht.

Kompression ist nur möglich, wenn es Zustände gibt, die nicht vorkommen können.
Beispiel:
Eine Ampel hat 3 Leuchten mit jeweils 2 Zuständen: An/Aus
Dies ergäbe die Möglichkeit für 9 Zustände.
Allerdings treten diverse Zustände niemals auf, z.B. leuchten niemals alle Leuchten gleichzeitig, oder alle Leuchten sind gleichzeitig aus.
Unkomprimiert würde das Bedeuten die Ampel benötigt einen Speicherplatz von: 9
Man kann sie aber auf einen Speicherplatz einschrumpfen von: 4

Denn nur 4 Möglichkeiten würden einen Sinn ergeben.
(oder hab ich mich da jetzt "verrechnet"? egal, ist denke ich klar was gemeint ist)
Kleiner lässt es sich nicht komprimieren, wie denn auch?

Bezüglich deiner Datei:
Das sie nach dem Zippen größer wird liegt wohl hauptsächlich daran dass diverse Informationen durchs Zippen hinzugefügt werden müssen:

-Dateitabelle
-Dateinamen
-Hashwerte der Dateien
-Verwendetes Komprimierungsverfahren
etc...

Rein theoretisch könnte man die Datei (eventuell) durchaus noch komprimieren, denn Sie enthält nicht alle Bytes (Null-Byte nicht vorhanden) und die Bytes sind auch nicht alle in der Anzahl gleich.
Ich gehe mal davon aus, du hast diese Datei per Pseudozufallsgenerator erzeugt, in diesem Falle komprimiere sie indem du das Programm das diese Datei erzeugt hat kompilierst und zipst.

Noch etwas: Je mehr man eine Datei komprimiert, desto mehr nähert sie sich dem Zufall.
Darum komprimiert man Daten normalerweise auch vor dem Verschlüsseln, so kann man beispielsweise der Häufigkeitsanalyse effektiv vorbeugen.

Ich bin noch ein bisschen Groggy heute, daher sehe bitte über meine (bestimmt zahlreich vorhandenen) Tippfehler sowie der künstlerischen Freiheit bzgl Grammatik und Rechtschreibung hinweg.
Hoffe es ist dennoch angekommen was ich zum Ausdruck bringen möchte.

Schweiza schrieb in Beitrag Nr. 692-3:

Man kann Daten nicht (nahezu) beliebig komprimieren. Man kann 256 verschiedene Zustände nicht in weniger als 8 Bit darstellen. Geht nicht.

Das ist natürlich richtig. Damit hast du mich auch zum Nachdenken gebracht. Ich könnte die Zahl 11111111 (=255) zwar beispielsweise auch mit nur 5 Bits beschreiben (einer 4-Bit und einer 1-Bit-Zahl), nämlich dass 1000 (=8) mal die 1 (1) folgt. Das ginge in dieser Form aber natürlich nur mit einer sehr begrenzten Anzahl an Bit-Kombinationen und wäre deshalb sinnlos.

Es geht aber schließlich nicht darum, 8 Bits zu komprimieren, sondern wesentlich größere Datenmengen. Und da sehe ich eine Chance.

Jetzt war mein Gedanke, dass das Komprimierungsverfahren in einer solchen Situation, wenn ein weiteres Komprimieren der Daten unmöglich erscheint, wie folgt vorgeht: Er rechnet sämtliche Bytes immer wieder mit einer Formel um, bis er zufällig auf eine Datenstruktur stößt, die sich weiter komprimieren lässt. Als einfaches Beispiel könnte er auf Bitebene sämtliche Bits innerhalb eines Bytes um einen Betrag verschieben, welcher von der Position des jeweiligen Bytes innerhalb der Datenstruktur abhängt (z. B. Byte Nr. 1 = 01010011 um den Betrag 1 nach rechts verschoben ergäbe 10101001. Die rechte 1 wird einfach links wieder angehängt. Wird um 8, 16, 24, 32... Bits verschoben, verändert sich die Zahl z. B. gar nicht). So ergäbe sich eben eine komplett neue Datenstruktur, die möglicherweise neue komprimierbare Strukturen aufweist und in jedem Fall auf einfache Weise beim Dekomprimieren auch wieder zurückgerechnet werden kann. Diese neue Datenstruktur könnte dann mit etwas Glück erneut komprimiert werden, oder liege ich mit meinen Ansichten falsch?

Schweiza schrieb in Beitrag Nr. 692-3:

Kompression ist nur möglich, wenn es Zustände gibt, die nicht vorkommen können.

Das ist meines Erachtens abhängig vom Algorithmus und der Datenstruktur, die komprimiert werden soll. Ich habe mal einen Algorithmus zum Komprimieren eines bestimmten Bildes geschrieben (ach ja, das waren noch die guten 8-Bit-Zeiten :-) ). Es handelte sich um ein digitalisiertes Bild mit großen einfarbigen Bereichen. Da war es ein Leichtes, die Daten zu komprimieren, wenn 600 mal nacheinander eine "0" vorkam. Trotzdem gab es generell sämtliche Zustände in den Byte-Folgen.

Schweiza schrieb in Beitrag Nr. 692-3:

Eine Ampel hat 3 Leuchten mit jeweils 2 Zuständen: An/Aus
Dies ergäbe die Möglichkeit für 9 Zustände.

Ich sehe nur 8 Zustände. Man kann diese mit insgesamt 3 Bits beschreiben: 000, 001, 010, 011, 100, 101, 110 und 111.

Schweiza schrieb in Beitrag Nr. 692-3:

Bezüglich deiner Datei:
Das sie nach dem Zippen größer wird liegt wohl hauptsächlich daran dass diverse Informationen durchs Zippen hinzugefügt werden müssen:

-Dateitabelle
-Dateinamen
-Hashwerte der Dateien
-Verwendetes Komprimierungsverfahren
etc...

Genau. Diesen Gedanken hatte ich auch.

Schweiza schrieb in Beitrag Nr. 692-3:

Rein theoretisch könnte man die Datei (eventuell) durchaus noch komprimieren, denn Sie enthält nicht alle Bytes (Null-Byte nicht vorhanden) und die Bytes sind auch nicht alle in der Anzahl gleich.

Ja wo sind denn die Null-Bytes!? Schön, dass ihr euch die Mühe gemacht habt, euch mit meiner Datei zu beschäftigen. Mir fiel gar nicht auf, dass die Null-Bytes fehlten und die Datenstruktur nicht der entsprach, die ich erwartete. Ich hab einen kleinen Programmfehler entdeckt und jetzt die Datei mit der korrekten Version (jetzt aber 1,33 MB) ersetzt, bei der alle Bytes gleichmäßig verteilt (auch Nullbytes) exakt 5461 mal vorkommen. Beim Komprimieren mit ZIP und RAR zeigten sich wie zu erwarten die selben Effekte (nach Kompression Zuwachs).

Schweiza schrieb in Beitrag Nr. 692-3:

Ich gehe mal davon aus, du hast diese Datei per Pseudozufallsgenerator erzeugt, in diesem Falle komprimiere sie indem du das Programm das diese Datei erzeugt hat kompilierst und zipst.

Stimmt. Echt schlau :-) Aber natürlich geht's hier nur darum aufzuzeigen, dass bestimmte Datenstrukturen generell nicht komprimierbar sind. Derartige Tricks ausgeschlossen, hehe.

Schweiza schrieb in Beitrag Nr. 692-3:

Noch etwas: Je mehr man eine Datei komprimiert, desto mehr nähert sie sich dem Zufall.

Genau. Und damit bestätigt sich meine Theorie, die meine Träume in Schaum auflösen lässt...

Schweiza schrieb in Beitrag Nr. 692-3:

Hoffe es ist dennoch angekommen was ich zum Ausdruck bringen möchte.

Du hast mir wirklich sehr geholfen. Dafür ein richtig dickes Dankeschön!

Kampf-Sushi schrieb in Beitrag Nr. 692-5:

... Das bringt aber trotzdem nicht viel, statistisch gesehen sind einfach zu viele Dateien nicht komprimierbar (Größe +1) im Vergleich zu den komprimierbaren Dateien (Größe -1 bis -2)

Ich glaube, da hast du einen ganz wichtigen Punkt angesprochen. Wie in den Gesetzen der Thermodynamik erwähnt wird, gibt es weitaus mehr ungeordnete Zustände als geordnete. Und wenn meine Grundsatzaussage zur Komprimierung von Daten richtig ist, lassen sich nur Daten komprimieren, die bestimmte Regelmäßigkeiten oder ein erkennbares System aufweisen.

Kampf-Sushi schrieb in Beitrag Nr. 692-5:

Ich glaube nicht dass du dadurch eine Datenstruktur erhälst die sich leichter komprimieren lässt. Vergiss außerdem nicht, dass du jeden Rechenvorgang den du vornimmst auch speichern musst, damit das Programm weiss was es rückgängig machen kann.

Vielleicht lässt es sich damit nicht leichter komprimieren, aber der vierzigste Umrechnungsvorgang könnte möglicherweise dazu führen, dass eine weitere Datenreduktion (und seien es nur wenige Bytes) realisierbar wird. Trotzdem führt das wohl auch nicht zum "heiligen Gral". Die Frage ist, ob sich mit dieser Methode immer wieder Strukturen ergeben würden, die eine weitere Komprimierung ermöglichen. Die Information, welcher Rechenvorgang jeweils letztlich zu Erfolg geführt hat, nähme zum Glück nur wenig Platz ein, muss aber natürlich mit einkalkuliert werden, wenn es darum geht zu entscheiden, ob es sich beim jeweiligen Vorgang auch effektiv um eine Reduktion der Daten handelt.

Zitat:

Manu schrieb in Beitrag Nr. 692-4:
Aber Bilder haben die Eigenschaft etwas abzubilden.
Damit will ich sagen: Enthält das Bild nur Zufälliges Rauschen, und du komprimierst die Daten, steigt das Datenvolumen statt zu sinken.

Stimmt.

Zitat:

Mindestens um 1 Bit, (komprimiert oder nicht).
Wenn du dieses Bit nicht verwenden wuerdest wär das weitaus unökonomischer, da jeder Pixel ein Präfix benötigen würde.

Also da wüsste ich vielleicht eine andere Methode, die aber nicht in jedem Fall ökonomischer sein muss, aber kann. Du definierst eine Bitfolge, die in der gesamten zu komprimierenden Datenstruktur nicht enthalten ist (sollte mit 12 bis max. 20 Bits für fast jede beliebige Datenmenge realisierbar sein), die als Einleitung für komprimierte bzw. bei wiederholtem Vorkommen als Einleitung für unkomprimierte Daten dient.

Kampf-Sushi schrieb in Beitrag Nr. 692-5:

So, und jetzt eine Theorie die mir gerade eingefallen ist:
Angenommen du berechnest alle Bildmöglichkeiten die es geben kann.
Alle komprimieren.
Die Summe des komprimierten Datenvolumens mit der Summe des unkomprimierten Datenvolumens vergleichen.
Meiner Theorie nach müssten die komprimierten Daten mindestens zu groß sein wie die unkomprimierten.

Die komprimierten Daten nähmen mehr Platz in Anspruch, da es eben weit mehr ungeordnete Zustände gibt als geordnete. Zum Glück weisen unkomprimierte Daten aber meistens irgendwelche Strukturen auf, weil diese in der Natur eine Rolle spielen.

Kampf-Sushi schrieb in Beitrag Nr. 692-5:

Wenn du es schaffst einen Algorithmus zu schreiben der den benötigten Algorithmus findet, ist doch alles in Butter :)

Der Gedanke inspiriert zu neuen Taten :)

Kampf-Sushi schrieb in Beitrag Nr. 692-5:

Stell dir vor du findest eine kurze Formel mit der du eine 100MB große Zip mit einer Applikation die du verkaufen willst berechnen kannst.
Hätte schon was cooles: 1 MB Download, 100 MB auf der Platte ;)

Mit einer kurzen Formel wäre das nur leider nicht realisierbar. Sicher gäbe es Formeln, die dann aber sicherlich einige MB's in Anspruch nähmen. Und das ließe sich mit einem guten Komprimierungsprogramm ebenfalls realisieren. Es gibt schon geniale, wenig bekannte Programme. Ich sah einmal begeistert zu, wie ein in der DOS-Box laufendes Dekomprimierungsprogramm (auf meinem Pentium 4 mit 3,2 Ghz) 90 MB Mediendaten in knapp einer viertel Stunde in ungefähr 800 MB umwandelte.

Also, ich kenne einen wahnsinnig guten Komprimierungsalgorithmus: Der kann den Inhalt eines ganzen Buches auf eine zehnstellige Zahl komprimieren!

Der Algorithmus funktioniert folgendermaßen:

Kompression: Schau die ISBN des Buches nach und schreibe sie auf.
Dekompression: Man benützt eine Dekompressionsvorrichtung (z.B. eine gut ausgestattete Bibliothek), um anhand der ISBN das Buch zu erhalten. Daraufhin,kann man den Inhalt des Buches lesen. (In der Praxis sind die Dekompressoren jedoch eingeschränkt auf einen bestimmten Anteil aller Bücher; neben Bibliotheken sind auch Buchhandlungen als Dekompressoren geeignet, allerdings ist da die Dekompression i.a. etwas teurer).

Der Punkt bei Kompressionsalgorithmen ist, daß häufig auftretende Muster durch kurze, selten auftretende durch lange Codes ausgedrückt werden. Hierbei wird ausgenutzt, daß nicht jeder Dateiinhalt gleich wahrscheinlich ist (die wenigsten zu komprimierenden Dateien dürften zufällig sein). Ein einfaches Beispiel ist der Huffman-Code: Hier wird nur die Wahrscheinlichkeit der einzelnen Zeichen betrachtet. Wenn man z.B. einen deutschen Text nimmt, dann enthält er sehr oft den Buchstaben e, aber sehr selten den Buchstaben y. Indem man nun dem e einen kürzeren Code zuweist, dem y aber einen längeren (und entsprechend für die anderen Buchstaben/Zeichen), dann wird ein deutscher Text kürzer codiert, als wenn man alle Zeichen mit gleich langen Bitfolgen codiert (wie das z.B. bei ASCII der Fall ist: Jedes Zeichen belegt ein Byte). Ganz einfach, weil das (wesentlich häufigere) e insgesamt mehr einspart als das (wesentlich seltenere) y an zusätzlichen Bits kostet. Der Huffman-Code ist nun eine ideale Implementierung dieses Schemas. Wenn man aber z.B. mit einem an die deutsche Sprache angepaßten Huffman-Code den Text "yyyyyyyyyyyyyyyyyyyyyy" codiert, dann wird er länger. Nur, daß das normalerweise keiner machen wird.

Ein Ausweg ist, den Huffman-Code aus den tatsächlich auftretenden Häufigkeiten zu berechnen, und an den Anfang der zu komprimierenden Datei hinzuzufügen. Damit wird zunächst jede Datei, in der die Häufigkeit unterschiedlich ist, verkürzt, und die anderen bleiben gleich. Aber der hinzugefügte Code am Anfang bedeutet, daß de facto sowohl Dateien mit nahezu gleichverteilter Anzahl, als auch zu kurze Dateien verlängert werden.

Modernere Kompressionsalgorithmen verwenden auch Korrelationen zwischen den Zeichen (z.B. folgt in deutschen Texten auf ein q fast immer ein u), außerdem gibt es neben den Huffman-Codes noch andere Möglichkeiten der Codierung, aber letztlich läuft es immer auf dasselbe hinaus: Wahrscheinliche Zeichen(folgen) weden mit kurzen Codes, unwahrscheinliche mit langen Codes codiert. Darum werden die Dateien wahrscheinlich kürzer. Es ist aber prinzipiell nicht möglich, einen Kompressionsalgorithmus zu schreiben, der manche Dateien kürzer, aber keine einzige länger macht (man kann die Verlängerung natürlich mit dem von Kampf-Sushi beschriebenen "Komprimiert-Bit" auf maximal 1 Bit begrenzen).

Nachtrag:

Bei Mediendateien werden höhere Kompressionsraten durch verlustbehaftete Komprimierung erreicht. Sprich: Es werden Informationen weggeworfen, wobei aber darauf geachtet wird, daß es möglichst irrelevante Information ist (im Idealfall kannst Du den Unterschied zwischen Original und dekomprimiertem Ergebnis nicht wahrnehmen). Ein Beispiel ist z.B. MP3: Hier wird Information weggeworfen, die das Ohr nicht wahrnehmen kann (z.B. wenn gleichzeitig ein sehr lauter und ein ähnlicher, sehr leiser Ton vorhanden ist, kannst Du den leisen Ton nicht hören). Das funktioniert natürlich nur so gut, wie die Theorie zum realen Ohr paßt, und wenn Du zu stark komprimierst, dann hörst Du den Unterschied dennoch (weil einfach zu viel Information fehlt).

Unabhängig davon kann auch ein verlustfreies Kompressionsprogramm, das auf bestimmte Dateitypen spezialisiert ist, für diese Dateien ein besseres Ergebnis produzieren als ein allgemeines Kompressionsprogramm (dafür wird es auf anderen Dateitypen schlechtere Ergebnisse liefern). Ganz einfach, weil es für die Komprimierung Wissen über den prinzipiellen Aufbau solcher Dateien verwenden kann (z.B. könnte ein Komprimierungsprogram speziell für deutsche Texte bereits eingebaute Codes für die 100 häufigsten deutschen Wörter haben; diese Wörter könnten dann z.B. in 7 Bits pro Wort gespeichert werden, oder besser noch, per festem Huffman-Code mit häufigkeitsabhängiger Länge).

Zufälligerweise fand ich vor kurzem eine Dokumentation des Huffman-Algorithmus und beschäftigte mich damit. Die Möglichkeit, die Tabelle der Häufigkeitsverteilung anhand der tatsächlich auftretenden Zeichen zu berechnen und im komprimierten Ergebnis zu hinterlegen, kam mir dabei ebenfalls in den Sinn.

Da fast alle Methoden, die ich mir ausdachte scheinbar (wie zu erwarten war) bereits bekannt sind, werde ich das Thema für mich als abgeschlossen betrachten. Es wäre Zeitverschwendung zu versuchen, bessere Algorithmen als die bereits existierenden zu finden und den Aufwand zu betreiben, diese in Form eines Programmes um zu setzen. Man muss sich auch vor Augen halten, dass sich hochintelligente Köpfe seit vielen Jahren ausschließlich damit beschäftigen, möglichst Effiziente Lösungen zu finden. Die vorhandenen Verfahren in absehbarer Zeit an Effizienz zu toppen halte ich für ausgeschlossen.

Selbst als angehender Programmierer kann ich den Ausführungen Timeouts nur wenig hinzufügen. Entscheidend ist der Informationsgehalt der Daten, dieser kann nicht kleiner werden ohne Informationen wegzulassen. Deine erste Idee Manu, also Daten nach einem reversiblen Verfahren immer wieder neu zu mischen und wieder zu komprimieren scheitert also daran, daß das Abspeichern der Anzahl der Durchläufe selbst im optimalen Fall genau so viele Daten erzeugt, wie das Verfahren vorher eingespart hat. Anschaulich gesagt schaufelst du damit nur Information aus den Daten in den Durchlaufzähler. Die Aufgabe eines jeden Komprimierungsalgorithmus ist nun also, aus den Daten die Information herauszufinden und diese kompakt wieder abzuspeichern. Dabei - und das ist der Grund warum ich poste - sind wir noch lange nicht am Ende mit unserem Latein. Du hast also Unrecht, wenn du glaubst es hat keinen Sinn sich damit zu beschäftigen :-). Immer wieder werden neue geniale Methoden erdacht. Zum Beispiel verwendet bzip2 mit der Burrows-Wheeler-Transformation ein Verfahren, daß von deiner Idee gar nicht so weit entfernt ist. Nur werden die Daten dort nicht zufällig gemischt sondern ein einfacher aber genialer Algorithmus sorgt dafür, daß die Daten nach dem Durchlauf besser komprimierbar sind. ( http://de.wikipedia.org/wiki/Burrows-Wheeler-Transf... )
Also auf, weiter dran rumdenken ! ;)

Ich habe auch eine Idee zu einem starken Kompressionsverfahren...

Man nehme eine beliebige Datei, beliebigen Typs oder Größe. Allerdings ist es wichtig, dass diese Datei binär betrachtet wird. Allerdings sollte dazu nicht nur der Dateiinhalt gehören, sondern auch weitere Informationen, wie Hashtabelle und das ganze Zeug, ich weiss nicht genau, was noch alles dazugehört.
Die Datei ist nun eine Ziffernfolge aus 0en und 1en ... Man erstellt eine neue Datei in der sich (!) als Text (also z.B. eine Textdatei) folgendes befindet:
Das Ergebnis aus der ersten Datei gemäss folgendem Algorhitmus:
00 = 0
01 = 1
10 = 2
11 = 3

Dann hat man eine neue Reihenfolge aus 0en, 1en, 2en und 3en. Wenn man diese eben als Text in der zweiten Datei abspeichert, kann man das gleiche Verfahren wieder auf die Binärstruktur dieser Datei anwenden und so eine datei fast beliebig oft komprimieren...

Irgendwann ist jedoch schluss, nehme ich an, weil die Datei eine Grundbasis an Informationen enthalten muss, um genug Material zur Zurückrechnung zu besitzen.

Wenn ich mich nicht vertue und totalen Bockmist verzapfe, dann müsste sich die Datei jedesmal halbieren...
Ich habe aber leider keine Ahnung, ob das auch technisch durchzusetzen ist, da ich erst 17 Jahre alt bin und sowas nicht studiert habe oder so. Bitte seht es mir nach, falls es Mist sein sollte. Und wenn, dann rege ich Euch evtl. zum Nachdenken an und Ihr kommt auf interessante Ergebnisse. :>

Akribator

Ein Zeichen in einer Textdatei hat in der üblichen Codierung stets 8 Bits. Deine Umcodierung würde also in jedem Schritt die Dateilänge nicht etwa halbieren, sondern vervierfachen.

Beispiel: Nehmen wir an, in der Datei steht der Text

Beispiel

Dessen Binärcode lautet nun bei Standard-ASCII-Dateien:

0100001001100101011010010111001101110000011010010110010101101100

Deine Codierung macht daraus

10021211122113031300122112111230

Du siehst, während die ursprüngliche Textdatei 8 Zeichen hatte, hat die "komprimierte" Textdatei 32 Zeichen.

Nun könnte man natürlich auf die Idee kommen, daß es ja Verschwendung ist, ein volles 8-Bit-Zeichen für jede der Ziffern zu verwenden. Schließlich können ja nur 4 Ziffern vorkommen. Das heißt, man könnte eine Codierung verwenden, die pro Zeichen gerade mal so viel Bits beansprucht, wie nötig sind, um 4 verschiedene Zeichen darzustellen. Nun, für 4 verschiedene Zeichen benötigt man gerade 2 Bits. Nehmen wir als naheliegende Codierung der Ziffern die Darstellung im Dualsystem, dann ist unsere "komprimierte" Datei – man höre und staune – exakt identisch mit der Ursprungsdatei!

Nun, ich hätte da ein Vorschlag, wie man einen krassen Algorithmus programmieren könnte, wenn die Rechenzeit absolut keine Rolle spielt:

Man müsste jedem möglichen Zeichen einer Datei eine Zahl zuordnen, zB 1-26 für a-z, und fügt sie zu einer großen Zeichenkette zusammen. Das Packprogramm nimmt dann die Zahl Pi (3,14...)zur Hilfe. Diese besondere Zahl hat ganz spezielle Eigenschaften. Sie ist absolut zufällig und wiederholt sich niemals (im ganzen gesehen, klar wiederholen sich kleine Abschnitte immer mal wieder). Ausserdem kann man nie wissen welche Ziffer hinterm Komma als nächstes kommt, ohne Ziffer davor zu kennen. Und das besondere ist: sie ist unendlich lang.
Daraus folgt, dass JEDE beliebige Zeichenfolge irgendwann in Der Zahl Pi auftaucht, wenn man nur lange genug sucht.
Das Packprogramm rechnet Pi dann solange aus, bis die entsprechende Zeichenkette auftaucht und speichert an welcher Stelle nach dem Komma das geschieht, in der Form xx-millionste-Stelle bis yy-millionste-Stelle.

Zum entpacken muss das Programm dann Pi wieder bis zu der yy-millionsten-Stelle ausrechnen und die Zeichen dann wieder zurückubertragen. Somit hätte man die Möglichkeit im Prinzip beliebig große Datenmengen mit nur zwei, wenn auch sehr große Zahlen, anzugeben.

Was meint ihr dazu??

supercomputer gefällig ;)

stell dir vor die zeichenfolge besteht aus 200 ziffern. ich denke das du rentner sein wirst wenn das programm ein ergebnis auspuckt, oder tot. ausserdem gibt es keinen computer der pi einfach mal so beliebig lang ausrechnen kann

Was du mit Pi versuchst zu machen, ginge auch mit den von mir weiter oben beschriebenen, definierten "Zufallszahlen", die jederzeit wieder aufs Neue in selber Reihenfolge berechnet werden können. Dafür gibt es Algorithmen, die sehr gut funktionieren. Das Problem liegt aber woanders.

Pi grob zu berechnen ist kein Problem. Je genauer das Ergebnis aber sein soll, um so länger dauert der Rechenzyklus. Das Problem: Der Rechenaufwand nimmt mit jeder zu berechnenden Stelle exponentiell anstatt linear zu. Das zweite Problem: Tatsächlich käme jede Informationskette möglicherweise irgendwo in Pi vor, aber nur theoretisch. Die Zahl, die die Stelle markieren soll, an der sich die gesuchte Zeichenfolge befindet, müsste die exakte Stelle identifizieren. Das heißt, du kannst nicht nach dem Schema vorgehen und einfach nur sagen, das Ergebnis befände sich grob an Stelle 8,16*10²⁶. Nein, du musst die Stelle exakt beschreiben. Je mehr Informationen du mit deiner Methode aber komprimieren möchtest, umso unwahrscheinlicher ihr Vorkommen innerhalb Pi, desto größer die Zahl, die die exakte Position beschreibt. Diese Zahl kann problemlos einige Millionen Stellen aufweisen. Schon ab sehr wenig zu komprimierenden Daten wäre der mutmaßliche Speichervorteil wieder dahin. Leider.

Nun ja - dass der Rechenaufwand für jede Stelle exponentiell zunimmt wusste ich halt nicht.
Das war aber auch eher eine theoretische Überlegung unter der Voraussetzung dass der Rechenaufwand keine Rolle spielt wie am Anfang gesagt wurde.
Vielleicht ist aber deine Beispieldatei sowas ähnliches wie Pi, denn Pi selber lässt sich ja auch nicht weiter komprimieren, liegt da vielleicht eine abstrakte Ähnlichkeit vor ??

Hi,

Bin mir nicht sicher, ob es noch zur Debatte steht, aber ich habe es geschafft die Datei "komprimiermich.manu" zu komprimieren.

Mit dem Programm WinRK 2.1.6a habe ich die Datei von 1.398.016 Bytes auf 1.391.776 Bytes komprimieren können.

Bin ich der erste? :>

Akribator

Akribator schrieb in Beitrag Nr. 692-18:

Bin mir nicht sicher, ob es noch zur Debatte steht, aber ich habe es geschafft die Datei "komprimiermich.manu" zu komprimieren.

Vielleicht. Es spricht für WinRK, dass es überhaupt möglich war, die Datei zu verkleinern. Allerdings wäre es nur dann revolutionär, wenn das Ergebnis im Verhältnis deutlich kleiner ausfallen würde.

Hmm ... ist es revolutionär die Datei von den 1.398.016 Bytes auf 1.273.879 Bytes zu komprimieren?
Also von ~1,33 MB auf ~1,21 MB geschrumpft


Hat nämlich das Programm PAQ8e hinbekommen. Ist ein kleines, eher unbekanntes Packprogramm in der Command-Line. Es ist meines Wissens nach das zur Zeit stärkste Komprimierungsprogramm. Nur in ein paar weniger Bereichen, wie (ich glaube es war) Textkomprimierung, kann es nicht mithalten. Aber ansonsten parfetto.

Sollte ganz leicht bei google zu finden sein. "paq8e download".

Akribator

Ich bin da im Web über etwas gestolpert, das mich wieder an diesen Thread erinnert hat, und das ich Euch nicht vorenthalten will: http://prize.hutter1.net/

Hallo tüftler-freunde!

Ich hab mich in meiner laufenden ausbildung gerade mit dem thema cryptographie beschäftigt und bin dann durch zufall auf diesen thread gestossen.
Die ganzen Beiträge sind ganz schon inspirierend!

Seit ca. einer woche studiere ich jetzt über das theme daten-kompression herum... meine ersten überlegungen gingen in die richtung, dass es doch irgendwie möglich sein muss eine information von 8 bit auf 7 bit zu schrumpfen (oder 4 auf 3 etc).
Sagen wir mal ich will 4bit auf 3 schrumpfen... dann müsste ich anhand von exakt drei Ja/Nein Fragen auf 16 mögliche antworten kommen... unmöglich...

Mein letzter versuch:
Ich habe 4bit (16 variationen) in muster eingeteilt. Durch die 3 Ja/Nein fragen habe ich drei andere grundmuster ermittelt, aus denen ich versucht habe jede der 16 variationen eindeutig zu identifizieren... ich hab die hoffnung noch immer nicht ganz aufgegeben, aber ich denke es ist einfach unmöglich!

Eine andere möglichkeit wäre die idee des Huffman-Baums...
Er ermittelt die häufigkeit der einzelnen variationen und teilt den am häufigsten auftretenden kürze bitmuster zu als den seltener auftretenden.
Sagen wir die grundlage wären 2bit, also 4 variationen. die häufigste würde zu einem bit werden, die zweithäufigste zu 2bit und die letzten beiden zu 3bit... genau auf dieser basis arbeiten die meisten modernen algorithmen...
Aber ehrlich gesagt finde ich nicht, dass das die perfekte lösung ist, denn auf fast die gleiche lösung bin ich auch schon mal gekommmen, nur dass ich das problem hatte, das mein decodierer nicht wusste aus wievielen bits die jeweiligen codierten infos bestehen.. der Huffman Code ist bei wiki sehr gut erklärt, wenn ihn sich jemand genauer anschaun möchte.

Also mal weg von der idee, dass man eine information von "X" bit irgendwie mit maximal "Xminus1" bit darstellen könnte und zurück zu der idee, dass es eine logik geben könnte, die, nachdem man sie mit z.B. 32bit füttert, die bitfolge einer 1MB großen datei ausspuckt.

Ich habe mir zur stütze ein programm geschrieben, das mir die bytefolge einer datei als grafik zeigt... Der wert des gerade eingelesenen bytes gibt mir eine y koordinate und die position im datenstrom die x koordinate eines punktes in der grafik... die muster die dabei enstehen sind bei den meisten datein erstaunlich!!! eigentlich hätte ich mir großteils "weißes rauschen" erwartet, aber das gegenteil ist eher der fall! Es ergeben sich bei fast allen datein schon fast künstlerische muster! -ok, ihr dürft mich nach dieser aussage für verrückt halten-
Bei bereits komprimierten datein ist dann, wie erwartet fast nur mehr weißes rauschen zu sehen.
(Vielleicht kann ich das programm mal als link reinstellen.. mal sehen ob sich noch mal jemand meldet hier...)

Ich denke es dürfte vielleicht nicht eine einzige logik reichen sondern mehrere formeln. Jede einzelne kann bestimmte muster erzeugen... zum beispiel eine kurve...
...eine datei, die ich mit dem programm eingelessen hab hatte unter anderem einige muster in sich, die mich stark an sinus und tangenz- kurven erinnerten...

Ich werde, wenn ich wieder zeit habe ein neues programm schreiben, dass mir nicht nur die bytes, sondern die einzellen bit aufschlüsselt und in grafiken umwandelt, mal sehen wieviel struktur sich entdecken lässt und wie schwer es tatsächlich ist, einen algorythmus zu finden, der gewisse strukturen exakt nachbilden kann.
Dann würde in der komprimierten datei nur mehr stehen: nimm die zahl x die logik y und das ergebnis sind z bit aus dem originalstrom... schön wärs ;)

Ich hoff dass sich vielleicht noch jemand hier meldet, wäre nett nochmal andere meinungen und ideen dazu zu hören!

mfg Mike