Anzeige

Ein theoretischer Kompressionsalgorithmus

Ein theoretischer Kompressionsalgorithmus | PSD-Tutorials.de

Erstellt von blackout, 13.01.2007.

  1. blackout

    blackout Schaf im Wolfspelz

    Dabei seit:
    12.09.2005
    Beiträge:
    3.359
    Geschlecht:
    männlich
    Ort:
    Würzburg
    Kameratyp:
    Rollei 35 S
    Ein theoretischer Kompressionsalgorithmus
    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.
     
    #1      
  2. Guest

    Guest Guest

    Ein theoretischer Kompressionsalgorithmus
    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
     
    #2      
  3. blackout

    blackout Schaf im Wolfspelz

    Dabei seit:
    12.09.2005
    Beiträge:
    3.359
    Geschlecht:
    männlich
    Ort:
    Würzburg
    Kameratyp:
    Rollei 35 S
    Ein theoretischer Kompressionsalgorithmus
    Manche Leute sind noch nicht mal fouriertransformiert komplex...
    Eimer Wasser, dein David
     
    #3      
  4. TUD

    TUD Lehrmeister

    Dabei seit:
    12.06.2006
    Beiträge:
    56
    Geschlecht:
    männlich
    Ein theoretischer Kompressionsalgorithmus
    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
     
    #4      
  5. blackout

    blackout Schaf im Wolfspelz

    Dabei seit:
    12.09.2005
    Beiträge:
    3.359
    Geschlecht:
    männlich
    Ort:
    Würzburg
    Kameratyp:
    Rollei 35 S
    Ein theoretischer Kompressionsalgorithmus
    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...
     
    #5      
Seobility SEO Tool
x
×
×