Antworten auf deine Fragen:
Neues Thema erstellen

Antworten zum Thema „Ein theoretischer Kompressionsalgorithmus“

blackout

Schaf im Wolfspelz

Die Hashfunktionen finde ich schon seit recht langer Zeit ziemlich interessant, vor Allem das Auffinden von Kollisionen. Vorhin ist mir dann ein (De-)Kompressionsalgorithmus eingefallen - ich weiß allerdings nicht, ob er Sinn macht.
Die Idee: Jeder String ergibt einen eindeutigen MD5-Wert. Das Script prüft alle Strings von 0 an, ob ihr Wert mit dem gegebenen MD5 übereinstimmt. Sollte das der Fall sein, hat man einen String gefunden, der zumindest die selbe Checksumme besitzt - es könnte aber auch irgend ein anderer sein. Dafür gibt es die Kollisionsvariable: wird eine Kollision gefunden, wird sie dekrementiert; ist sie 0 ist die gewünschte Kollision erreicht und die Datei dekomprimiert. (Über die Kompression machen wir uns jetzt mal noch keine Gedanken)

Vorraussetzung für die Dekompression ist also den MD5 der gewünschten Daten zu wissen und die Anzahl der Kollisionen von "kleineren" Daten (binär gesehen).

Die Funktion würde dann in etwa so aussehen:[php:1:5b59db895c]// Das <?php wird von der dämlichen Seite hier gesetzt und ich werde es sicher nicht weghacken
function decompress($md5, $collision = 1) {
for($expression = '';; $expression++) { /* $expression ist ein Wert im 256er-System und steht
dabei für ein ISO-8859-1-Zeichen. Die Implementierung davon spare ich mir
hier mal der Übersicht halber. */
if(md5($expression) == $md5) { // Kucken ob's passt
if(!--$collision) break; // Falls die gewünschte Kollision erreicht wurde Schleife verlassen
}
}
return $expression;
}[/php:1:5b59db895c]Das Hauptproblem wird sein, dass Kollisionen statistisch alle 2^128 Wörter auftreten; wenn man Pech hat, ist $collision also eine riesige Zahl - womöglich größer als die Datei selbst. Hier kann auch abhilfe geschaffen werden: diese riesige Zahl wird, neben der MD5-Summe, erneut mit dem selben Algorithmus komprimiert, wodurch sich bei häufiger Annahme die Datenmenge reduzieren könnte.

Blöderweise kann man all das nicht nachprüfen, weil Quantencomputer noch in der Entwicklung sind - es bleibt also Theorie. Außerdem klingt es ziemlich seltsam, beliebig große Daten in 128Bit chiffrieren zu können.

Ein weiterer Gedanke: Wenn tatsächlich irgendwann mal eine Grenze erreicht sein sollte, ab der $collision immer größer wird, könnte man auch an die dechiffrierten Strings eine Anforderung stellen ("ein F an 4. Stelle"), aber das führt jetzt zu weit.

Wie auch immer, wer Lust hat kann sich ja mal ein paar Gedanken drüber machen... und wer Lust hat den Sinn der Fragestellung in Frage zu stellen möge das bitte an meine persönliche eMail-Adresse (blackout@example.com) senden - ich werde mich darum kümmern, sobald ich sie erhalten habe.
 
G

Guest

Guest

blackout schrieb:
Wie auch immer, wer Lust hat kann sich ja mal ein paar Gedanken drüber machen... und wer Lust hat den Sinn der Fragestellung in Frage zu stellen möge das bitte an meine persönliche eMail-Adresse (blackout@example.com) senden - ich werde mich darum kümmern, sobald ich sie erhalten habe.

was schreibst du da? ist das der text aus deiner letzten heirats-annonce?
hast du freunde? fühlst du dich manchmal missverstanden ? :***
küsschen deine doris
 

TUD

Lehrmeister

Interessanter Ansatz, erinnert mich sehr an eine von mir angestrenge Überlegung.

Dieser Ansatz ist und wird leider in absehbarer Zeit Zukunftsmusik bleiben.
Stell dir einfach vor du zerlegst jede Information in ihre kleinste Einheit, nun suchst du nach eindeutigen Mustern die mehfach und mit hoher Wahrscheinlichkeit auftauchen.
Diese werden erfasst und als logische Binärwerte wieder neu organisiert. Die Kompressionsleitung wäre dabei enorm, würde sich aber erst bei großen Datenmengen lohnen. Dies haette aber zur Folge das zum einen der Such und Logikalgorithmus enorm effizent arbeiten muesste und sich die Rechenleistung allein beim Musterprüfen bei größeren Informationem ins schier undendliche Steigern würde.

Dieselben Probleme sind bei deinem Algorithmus zu erwarten, da schon geringe Änderungen zu grundverschiedenen Hashwerten führen, wird es nicht möglich sein eine Dekompressionslogik zu entwickeln die effektiv genug ist die Bruteforcelast zu senken, die vom Computer zu tragen ist.


Aber warten wir ab was die Zukunft bringt...
Ich versuche weiterhin meinen Prozessor stabil bei ~0 K zu halten.
Best regards
 

blackout

Schaf im Wolfspelz

Daher bleibt er ja theoretisch :)
Wobei es mit Quantencomputern durchaus realisierbar sein wird, selbst wenn's noch ein paar hundert Jahre dauert.
(Nein, ich weiß nicht was ein Quant ist, ich weiß auch nicht was ein Elektron ist weil ich es dieses Jahr verlernt bekommen habe. Aber der Ansatz dieser Rechentechnik fasziniert mich, obwohl ich nicht die geringste Ahnung davon habe.)
Heute war ich in einer Vorlesung (als Gast) über Codierungstechnik, einige Ansätze von da kämen bestimmt in Verbindung mit obigen Algorithmus. Würde man z.B. eine bestimmte Zeichenkette vor den MD5 setzen könnte man bei der Dechiffrierung sehr viele Kollisionen ausschließen (statistisch 2^8 pro Zeichen).
Das Problem von meinem Modell ist eigentlich, dass es darauf baut, dass die Anzahl der Kollisionen von kleineren Datensätzen nicht mit steigernder Komprimierung divergiert - und langsam bezweifle ich, dass das falsch ist. In dem Fall könnte man nur bestimmte Daten, die zufällig günstig sind, sehr gut komprimieren... das führt dann auf das Problem zurück, dass man vorhandene Daten auf solche Idealdaten zurückrechnen müsste. Ach je...
 
Bilder bitte hier hochladen und danach über das Bild-Icon (Direktlink vorher kopieren) platzieren.
Antworten auf deine Fragen:
Neues Thema erstellen

Willkommen auf PSD-Tutorials.de

In unseren Foren vernetzt du dich mit anderen Personen, um dich rund um die Themen Fotografie, Grafik, Gestaltung, Bildbearbeitung und 3D auszutauschen. Außerdem schalten wir für dich regelmäßig kostenlose Inhalte frei. Liebe Grüße senden dir die PSD-Gründer Stefan und Matthias Petri aus Waren an der Müritz. Hier erfährst du mehr über uns.

Stefan und Matthias Petri von PSD-Tutorials.de

Nächster neuer Gratisinhalt

03
Stunden
:
:
25
Minuten
:
:
19
Sekunden

Flatrate für Tutorials, Assets, Vorlagen

Statistik des Forums

Themen
175.155
Beiträge
2.581.856
Mitglieder
67.222
Neuestes Mitglied
Gregor
Oben