Der Supercode

Der Supercode

Der Supercode

Berichtdoor Johan1951 » vr 15 okt 2010, 16:22

From: Cyberflair

Zufällig bin ich bei amazon auf das Buch "Der Supercode. Eine Erfindung, die den Tod brachte" gestoßen:

http://www.amazon.de/Supercode-Eine-Erf ... 3431036325

gekauft hab ich mir das Buch bisher allerdings nicht.

Über die Geschichte von Jan Sloot, in dem es in diesem Buch geht, finden sich bei Wikipedia in Deutsch und Englisch leider nur kleine Artikel.
vgl.:
http://de.wikipedia.org/wiki/Jan_Sloot

anders sieht es in der holländischen Wikipedia aus:
http://nl.wikipedia.org/wiki/Jan_Sloot

versteht das hier jemand?

Insbesondere die rechte Spalte des Artikels scheint interessant zu sein. Wird damit bewiesen, dass der "Supercode" unmöglich ist? Kann jemand vielleicht ein paar Sätze mit den mathematischen Berechnungen übersetzen?
Oder weiß jemand aus anderer Quelle etwas über den "Supercode"?



Bron: http://www.politik.de/forum/bildung/153952-der.html
Avatar gebruiker
Johan1951
 
Berichten: 3752
Geregistreerd: di 31 aug 2010, 17:04

Re: Der Supercode

Berichtdoor Johan1951 » vr 15 okt 2010, 16:28

From: Scepticus

Cyberflair schrieb:
(...) Wird damit bewiesen, dass der "Supercode" unmöglich ist? (...)

Nicht wirklich!

Die Argumentation ist, daß ein Spielfilm aus mindestens 24 x 60 x 60 = 86400 Einzelbildern besteht, die selbst dann, wenn jedes Bild nur aus einer schwarzen oder weißen Fläche bestünde (also mit 1 bit codierbar wäre) mindestens 86400 Bit zur Codierung erfordern würden.

Das beweist letztlich aber nur, daß man nicht 16 beliebige, theoretisch mögliche, Spielfilme verlustfrei in 64KB unterbekommt, sagt aber nicht wirklich etwas über die praxisrelevanten Grenzen aus. (denn wer will schon einen Spielfilm aufs Einzelbild und aufs Pixel genau sehen, der Pi auf eine Folge schwarzer und weisser Seiten abbildet :))

Es dürfte schwierig werden, die Grenzen der Möglichkeiten eines verlustbehafteten Kompressionsverfahrens (ala jpeg oder mp3) theoretisch auszuloten - daß der 'Supercode' aber gleich um einige Größenordnungen besser als alle heute bekannten Verfahren ist (die ja ihrerseits schon nicht frei von Artefakten sind), sollte aber zumindest äußerst mißtrauisch machen.
Avatar gebruiker
Johan1951
 
Berichten: 3752
Geregistreerd: di 31 aug 2010, 17:04

Re: Der Supercode

Berichtdoor Johan1951 » vr 15 okt 2010, 16:37

From: Mithrandir

Nur zur Veranschaulichung: Das wäre deutlich weniger als ein Byte pro Sekunde! Das istallein für die Audiodaten extrem unrealistisch.
Avatar gebruiker
Johan1951
 
Berichten: 3752
Geregistreerd: di 31 aug 2010, 17:04

Re: Der Supercode

Berichtdoor Johan1951 » vr 15 okt 2010, 16:37

From: Washuu

Theoretisch könnte man natürlich eine MD5 oder ähnliche Checksumme über eine Datei berechnen und speichern. Zur Wiederherstellung überprüft man alle möglichen Datensätze, bis man einen findet, der die gleiche Checksumme hat - voila.

Nö nicht wirklich. Selbst wenn man genug Zeit dafür hätte, würde man eine unglaublich grosse Menge von Datensätzen entdecken, die die gleiche Checksumme haben, aber sonst keinerlei Ähnlichkeit zu der Originaldatei. Ich denke aber dass viele Leute auf diese "idee" gekommen sind, womöglich auch der Herr Jan Sloot.
Avatar gebruiker
Johan1951
 
Berichten: 3752
Geregistreerd: di 31 aug 2010, 17:04

Re: Der Supercode

Berichtdoor Johan1951 » vr 15 okt 2010, 16:39

From: Scepticus

Washuu schrieb:
Theoretisch könnte man natürlich eine MD5 oder ähnliche Checksumme über eine Datei berechnen und speichern. Zur Wiederherstellung überprüft man alle möglichen Datensätze, bis man einen findet, der die gleiche Checksumme hat - voila. (...)

Das geht viel besser! :)

Jede beliebige Zahlenfolge taucht irgendwo in Pi auf - also muß man sich nur die Anfangsposition und die Länge merken, durch die der Abschnitt von Pi definiert wird, der die binäre Repräsentation der mpeg-Kompression des Spielfilms darstellt.

Mit etwas Glück benötigt die Zahl, die die Anfangsposition beschreibt, weniger Bits als die mpeg-Kompression selbst - dann muß man nur noch die Bytes per BBP-Algorithmus berechnen und das Ergebnis per mpeg dekomprimieren - und voilà!

:mrgreen:
Avatar gebruiker
Johan1951
 
Berichten: 3752
Geregistreerd: di 31 aug 2010, 17:04

Re: Der Supercode

Berichtdoor Johan1951 » vr 15 okt 2010, 16:41

From: Gast

Scepticus schrieb:
Das geht viel besser! :)

Jede beliebige Zahlenfolge taucht irgendwo in Pi auf - also muß man sich nur die Anfangsposition und die Länge merken, durch die der Abschnitt von Pi definiert wird, der die binäre Repräsentation der mpeg-Kompression des Spielfilms darstellt.

Mit etwas Glück benötigt die Zahl, die die Anfangsposition beschreibt, weniger Bits als die mpeg-Kompression selbst - dann muß man nur noch die Bytes per BBP-Algorithmus berechnen und das Ergebnis per mpeg dekomprimieren - und voilà!

:mrgreen:

Das halte ich für unwahrscheinlich, dass die Zahl, die die Anfangsposition beschreibt, weniger Bits braucht.
Allerdings muss es ja nicht Pi sein. Man könnte jede x-beliebig definierte transzendente (oder zumindest irrationale) Zahl hernehmen.
Mit 86400 Bit könnte man eine riesige Menge an Reihen definieren, von denen vielleicht eine einen Wert ergibt, der schon von der ersten Stelle an die richtige Codierung liefert.
Fragt sich nur, wie man diese Reihe findet.
Avatar gebruiker
Johan1951
 
Berichten: 3752
Geregistreerd: di 31 aug 2010, 17:04

Re: Der Supercode

Berichtdoor Johan1951 » vr 15 okt 2010, 16:43

From: Mithrandir

Scepticus schrieb:
Jede beliebige Zahlenfolge taucht irgendwo in Pi auf - also muß man sich nur die Anfangsposition und die Länge merken, durch die der Abschnitt von Pi definiert wird, der die binäre Repräsentation der mpeg-Kompression des Spielfilms darstellt.

Die Nummer der Anfangsposition ist so groß, dass sie im allgemeinen deutlich(!) komplexer ist, als der Film selbst. => Keine Chance :)
Avatar gebruiker
Johan1951
 
Berichten: 3752
Geregistreerd: di 31 aug 2010, 17:04

Re: Der Supercode

Berichtdoor Johan1951 » vr 15 okt 2010, 16:44

From: Amelie

Ein Ansatzpunkt wäre vielleicht die sogenannte Gödelisierung. Die Idee ist, dass man den Film als eine Zahl interpretiert und dann eine Primfaktorzerlegung macht. Die Faktoren müsste man dann möglichst effizient speichern (z.B. nochmal Gödelisierung anwenden).
In der Praxis scheitert das natürlich an der Primfaktorzerlegung (aber wer weiß, vielleicht kommen ja bald die Quantencomputer :)).

Leider kann ich kein Holländisch und deshalb auch den Wiki-Artikel nicht verstehen, aber die Idee der Gödelisierung ist weniger geheim. Ein effizienter Algorithmus zur Primfaktorzerlegung könnte dem Entdecker aber tatsächlich Schwierigkeiten bereiten :)
Avatar gebruiker
Johan1951
 
Berichten: 3752
Geregistreerd: di 31 aug 2010, 17:04

Re: Der Supercode

Berichtdoor Johan1951 » vr 15 okt 2010, 16:45

From: Sozialist

EDIT: kB steht im folgenden für 1000 Byte, nicht für 1024 Byte.

Bei verlustloser Datenkompression muss ich jedes Objekt immer noch einwandfrei identifizieren können. Die absolute Untergrenze für verlustlose Kompression einer Klasse von Objekten, die über n mögliche Konfigurationen verfügt, wäre also Schlüssel von 0 (mit einem Bit Länge) bis der Binärrepräsentation von n-1 zu haben, die Rekonstruktion der Daten aus den Schlüsseln wäre dann noch eine andere Frage. Dafür ist natürlich ein fixes Format notwendig. Nehmen wir als Beispiel die Kompression von Bitmaps mit der Dimensionierung 100x100 Pixel bei einer Farbtiefe von 8 Bit. Würde ich für diese limitierte Objektklasse das effizientmöglichste Speicherformat verwenden, würde ich die Information in 10000 Farbcodes von einem Byte speichern, der 70. Code z.B. für den Pixel (1,70), der 3030. Code für den Pixel (30,30) und so fort. Dann hätte ich 256 hoch 10000 mögliche Konfigurationen, die benötigte Länge zur Darstellung dieser Zahl entspricht genau der Größe des oben spezifizierten Formats nämlich 100 x 100 x 1 Byte = 10 kByte.
Der absolute Idealfall wäre also, dass ich jeder Zahl zwischen 0 und 256^10000 -1 genau eines der möglichen Bilder zuordnen kann. Das geht schon, wenn ich die normale oben vereinbarte Repräsentation nehme und als lange Zahl interpretiere, bei der ich alle führenden Nullen streiche, die dann bei der Interpretation so wieder vorne angefügt werden, dass die Datei wieder exakt 10 kB lang ist. Dabei muss man sich aber im Klaren sein, dass man in nur 50% aller möglichen Konfigurationen überhaupt mindestens ein Bit einspart, will man gar 2 Byte einsparen, kommen gar nur noch 0,001526% der möglichen Konfigurationen in Frage. Um einen signifikanten Teil an Einsparungen zu gewinnen (z.B. 1-2 kB von den 10 kB) müssen also alle relevanten Bilder zu einer astronomisch winzigen Teilmenge der denkbaren Bildkonfigurationen gehören.
Der interessante Aspekt ist aber, dass wir die Untergrenze der eindeutigen Identifikation jeder möglichen Konfiguration mit einem Schlüssel nicht unterschreiten können. Bei der Hälfte können wir ein Bit einsparen, bei einem Viertel ein weiteres Bit, bei einem Achtel ein weiteres Bit etc. Insgesamt kommen wir darauf, dass die mittlere Größe aller erdenklichen Bildkonfigurationen unseres 10kB-Bitmapformats auch bei der besten verlustfreien Kompression nicht 79999 Bit unterschreiten kann (sprich, ein mittlerer Gewinn von maximal einem Bit). Der Trick bei verlustfreier Kompression ist es, dass die immense Vielzahl der möglichen Konfigurationen für unsere Zwecke sinnloser Datenmüll (im Falle unseres Bitmapbeispiels Farbrauschabfall) ist und wir die für uns interessanten Konfigurationen also möglichst in Richtung der ersten Positionen der Schlüsselliste schieben müssen.

4 kB repräsentiert zwar sicherlich eine immense Zahl, namentlich etwa 9,117 x 10 hoch 9632, aber die Zahl der theoretisch denkbaren Spielfilme bis zwei Stunden Länge ist mit 100% Sicherheit um astronomische Größenordnungen größer.

Da hilft auch keine Gödelisierung oder was auch immer mehr weiter. Denn die Identifkationsuntergrenze zu unterschreiten, würde heißen eine Abbildung von N nach N (Bereich der natürlichen Zahlen) f(a) := b zu finden, wobei b,max < a,max ist, aber die Funktion immer noch eineindeutig bleibt. Dies würde in der Tat alle bisherige Mathematik und Logik in der Menschheitsgeschichte auf den Kopf stellen.

EDIT: Bei dem vorhergehenden Stück Mathematik bin ich davon ausgegangen, dass man kein größeres a oder b als Schlüssel wählt, solange noch eine kleinere Zahl im Definitions- bzw. Wertebereich frei ist, sodass a,max gleich der Anzahl der verschiedenen tatsächlichen Argumente der Funktion ist und b,max gleich der Anzahl der verschiedenen Werte im Wertebereich (im Verständnis der Zahlenmenge N ohne die 0).
Avatar gebruiker
Johan1951
 
Berichten: 3752
Geregistreerd: di 31 aug 2010, 17:04

Re: Der Supercode

Berichtdoor Johan1951 » vr 15 okt 2010, 16:46

From: Mithrandir

Amelie schrieb:
Ein Ansatzpunkt wäre vielleicht die sogenannte Gödelisierung. Die Idee ist, dass man den Film als eine Zahl interpretiert und dann eine Primfaktorzerlegung macht. Die Faktoren müsste man dann möglichst effizient speichern (z.B. nochmal Gödelisierung anwenden).

Gödelisierung hilft auch nicht weiter, die Zahl wäre so groß, dass die Idee zur Kompression ungeeignet ist. Die Vorstellung, man könnte ein Kompressionsverfahren einfach mehrmals anwenden könnte, um weiter zu komprimieren, ist auch verkehrt.

Für reine Redundanzkomprimierung gibt es eine theoretische Grenze, da geht nicht mehr. (Das geht im Prinzip auch aus den Erläuterungen von Sozialist hervor.)
Avatar gebruiker
Johan1951
 
Berichten: 3752
Geregistreerd: di 31 aug 2010, 17:04

Volgende

Keer terug naar Politik.de (1006)

cron