| Autor |
Beitrag |
wdbee
      
Beiträge: 628
Erhaltene Danke: 1
|
Verfasst: Di 22.03.05 18:31
Das Argument ist für sich genommen richtig. Jedenfalls wenn man alle Randbedingungen als Kleingedrucktes mit hineinpackt. Aber das hilft ihm hier nicht wirklich weiter, weil wir damit nicht aussagen können, wie groß der Anteil der komprimierbaren Folgen ist, denn wir wissen nicht, welchen Anteil der Folgen wir mit dem Generator überhaupt erzeugen können.
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: Di 22.03.05 18:44
ok ich geh mal ein bischen weiter in meiner theorie:
um von einer datenmenge die beste komprimierung bzw eine sehr gute zu erhalten muss man einen art algorithmus entwickeln von dem man auf diese datenmenge schließen kann
jetzt nehmen wir irgend einen zufallsgenerator, wir wissen von einer datei die damit erstellt worden ist das es einen algorithmus gibt der mit initalisierten mengen auf diese datei zurückführen kann
jetzt sagen wir mal wir opetimieren den algorithmus (also den code dafür) auf 0 bytes d.h. wir lassen ihn ausser acht dann hängt die datei nur von den initialisierten werten ab, um nun eine "zufällige", kaum zu komprimierbarte datei zu erstellen müssen die initialisierten dateienso groß sein wie die datei selber, denn wenn man schon bit wegnimmt kann man auch nur weniger dateien erstellen um genau zu sein -1 bit
das ist aus dem grund so da man einen algorithmus hat der aus jedem anfangswert IMMER die gleiche datei erstellt
daraus ergibt sich das jeder zufallsgenerator komprimiert werden kann wenn er aus dem ausgansgwert eine größere datei erstellt
daraus folgt dann das ein PC wie wir ihn heutzutage haben KEINE zufällige datei erstellen kann es sei denn er bekommt in seinem algorithmus als ausgansgwert genau so viele anfangswerte wie die datei groß sein soll und das KANN man nicht machen, es sei denn man ließt gerade z.b. die spannung aus (obwohl die auch dann immer im gleichen bereich sein wird 2.0001 - 2.0005 volt oder was weiß ich) oder man nimmt die zeit (wie random) die auch nur ne bestimmte größe haben kann und die von der länge auch net beliebig klein wird also z.b. 14:07:02 und 23.498430294823094329845456985984593485 msk (halt s groß wie die datei sein muss)
hat jemand gegen diese theorie etwas einzuwenden? ^^
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
|
|
wdbee
      
Beiträge: 628
Erhaltene Danke: 1
|
Verfasst: Di 22.03.05 18:51
Nein, das ist schon richtig. Aber wir müssen hier wohl unterscheiden zwischen allen möglichen Folgen der Länge 1MB und allen berechenbaren Folgen dieser Länge. Da wir nicht angeben können, wie hoch der Anteil der berechenbaren Folgen ist, sind wir noch nicht weiter.
Aber wenn wir uns vom Zufall lösen und sagen wir erzeugen alle möglichen Folgen mit einem stupiden Alg. und schreiben die alle in eine Tabelle, dann können wir nach deinem Ansatz sagen, die Länge der Tabelle legt das Minimum fest. Wenn der Alg. im Prozessor fest eingabut wäre und sich mit einen Ein-Byt-Befehl auslösen ließe, dann wäre das 1 Byte plus die Anzahl der Bytes für den Index. Richtig?
|
|
F34r0fTh3D4rk
      
Beiträge: 5285
Erhaltene Danke: 29
Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
|
Verfasst: Di 22.03.05 18:59
hab jezz net alles gelesen, aber heißt das, das eine auf eine andere folgende zahl bzw zahlenfolge immer eine geringste, also eine größtmögliche (un)wahrscheinlichkeit hat ?
weil 47283947023 ist auch zufall ^^
wie würde dann eine 4 stellen lange zeichenfolge mit der größten (un)wahrscheinlichkeit lauten ?
unwahrscheinlich wäre zb: 0000 1234, oder ? und was währe wahrscheinlich ? bei 4 stellen folgt es doch immer der gleichen wahrscheinlichkeit, bzw einem system !?

|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Di 22.03.05 19:10
Laut Mathematica sind das etwa so viele Möglichkeiten:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30:
| N[2^(8*1048576-1)-1, 10000000]
2.132243711779763936216364463042807877377710039747856107862308520376201008\ 967488041286249709124417901905269927336314057322948430952018056162653397612721\ 968866564174196907364660195472312332201536322678209376234570435480655927647279\ 987141656437437882821789716369559442339510295291380061080226267244085033368052\ 670803354365371399252282653933231555704531949352158676039185847074527162766961\ 050551237118797136829821256818352798222274144906740354568934985122187696567230\ 123294927022732462869571704926490939703061098600117096632696129832055266393977\ 333379630441235010691712652765799558675387064377261186692570370400340298611257\ 891914330977060832282578971158586283612131197656208234829341462539371466181351\ 979108421552091633169316888316798247208176923666885885464135196067394307402588\ 851165605231688960910434973051329444994922428250930344595394818075040697301650\ 004257668924793139291561713504635365184394266730923714048567255839140531653145\ 153620430093376724052391826958406745139555304572075391067667027440250609739159\ 851283066388734523398794186934875832351149761346188585867288910016071280598571\ 162869509737818606353701341598783359580069260755729706360504953966386187465502\ 957965231037029018318808479923034600571599673828871069690605959719971945834149\ ... Wer die komplette Zahl haben will, bei mir melden ... 455508874455234168926393007651776315916836884468446320847781773509057945802824\ 329219676718824211426502888422771250893718623765524280666024118410454802534068\ 770823008230262780288756992429840040979205068781341503590720243148509812856850\ 357133045189873192762695497497529074425298349082147498980669715939484668585201\ 235156518754695217898858572106907841646301994666946184886695136970782962641688\ 891999768930972284238164987738206499606473494227677344043959036319155280916650\ 676818220147768337426670484066903404480816462241374924211522493248830782902721\ 836170545346703766824930004687266467853159594213786835996691484346570955591201\ 928022198645026997725964546211381645159155655553477190768679121179338698478422\ 087535338984812600469531832840501126509682037743068020639287870339996378241771\ 28611265440089917044379173385238709742775687205909168127*10^2525222 |
Kurzfassung: 2.14*10^2525222
Naja, gut, ich kann mich ja mal daran machen für Backslash ne File zu generieren  Hab schon ne Idee wie ich seinen Algo austricksen kann  Simples XOR von Daten müsste reichen (mit paar anderen Dingen kombiniert)...
Bekannt + Zufall = Zufall 
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
wdbee
      
Beiträge: 628
Erhaltene Danke: 1
|
Verfasst: Di 22.03.05 19:39
Also der Alg. von oben wäre nichts anderes als ein Increment-Befehl in einem 1MB-Prozessor. Aber daran sieht man auch schon, dass wir so nichts gewonmnen haben.
Zwei-Bit-Prozessor: Vier mögliche Folgen, Index 0 bis 3, also 2 Bit für Index,
Drei-Bit-Prozessor: 8 mögliche Folgen, Index 0 bis 7, also 3 Bit für Index, usw.
Zusammen mit dem Befehl für das Starten unseres Zählers lägen wir immer über dem ursprüngliche Text. Also so gehts nicht.
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Di 22.03.05 19:57
Backslash hat folgendes geschrieben: | | glaube, eine gewisse Komplexität in Zufallszahlen gefunden zu haben. Leider konnte ich das bisher nur mit Pseudozufallszahlen probieren. |
Die Entropie gibt an, wie gross der Erwartungswert der Länge (in Bits) eines komprimierten Symbols allermindestens ist; gegeben die Zufallsverteilung der Symbole. Nach Shannon: Entropie = - Summe(P(X)*Log2(P(X)))
Wenn wir also 256 Ascii-Symbole haben, und diese in einem String mit Wahrscheinlichkeit je 1/256 vorkommen, braucht es im Schnitt mindestens 256*1/256*Log2(1/256) = 8 Bits (= Keine Kompression möglich). Das ist ein Theorem mit math. Beweis, da kannst du nichts dran rütteln.
Du suchst eine perfekt zufällige Quelle um deinen Algorithmus zu testen? Das musst du gar nicht tun, denn es ist unmöglich... Wenn du irgendwelche Charakteristiken gefunden hast, kannst du sie auf jeden Fall nicht nutzen, um die Daten zu komprimieren.
... Und dass man beliebig viele Pseudozufallszahlen auf nur einige Bytes reduzieren kann, ist klar und das wurde oben auch schon erklärt.
|
|
wdbee
      
Beiträge: 628
Erhaltene Danke: 1
|
Verfasst: Di 22.03.05 20:13
@delfiphan: Da komm ich gerade ins Schleudern
Der Erwartungswert liegt analog zum Gedankenexperiment oben bei 8 Bit. Aber wir wissen, dass es Folgen gibt, die komprimiert werden können ( Nur 0 oder nur 1 usw.). Andererseits gibt es keine Folgen die länger sind, als die Ursprungsfolge, denn sonst wäre das die Kompression selbst.
Was stimmt denn da nicht?
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Di 22.03.05 20:26
Ich sagte im Schnitt mindestens  . Der Erwartungswert der Länge des codierten Symbols ist 8 Bit.
Ich schätze ich brachte mit meinen Ausführungen keine neuen Erkenntnisse ins Forum. Ich weiss langsam nicht mehr was Backslash genau wollte. Zuerst wollte er zufällige Zahlen, um seinen Algorithmus (an dem er 5 Jahren programmiert hat) zu testen, weil er viele Pseudozufallsgeneratoren schon probiert hat. Jetzt sieht er aber ein, dass es unmöglich ist, einen Kompressor zu bauen, der alle mögliche Symbolfolgen um 1 Bit reduziert.
Zusammengefasst:
1.) Absolut zufällige Zahlenfolgen kann man i.A. nicht komprimieren.
2.) Durch Berechnung lässt sich keine Information erhöhen. Du kannst Milliarden von Pseudozufallszahlen immer reduzieren auf "Algorithmus + Startwerte".
@Backslash: Was willst du nun eigentlich von uns?
|
|
Backslash 
      
Beiträge: 202
WIN XP
Delphi 5 Ent, Delphi 2005 Prof
|
Verfasst: Mi 23.03.05 08:55
@delphiphan:
Ich haben in diesem Thread nie behauptet alle möglichen Bitkombinationen von 1 MB-Daten immer um 1 Bit komprimieren zu können. Langsam zweifel ich echt dran, ob du meine Postings überhaupt gelesen hast.
@others:
wieso soll ich Pseudozufallzahlen, die mit 8Byte generiert werden auch nur im Durchschnitt um 8Byte komprimieren können? Die Charakteristik die ich entdeckt habe, lässt bei weitem mehr als nur 8 Byte zu.
Eigentlich wollte ich nur einen Zufallsgenerator finden. Das wars was ich wollte und was auch aus meinen ersten Postings hervorging.
MfG
Backslash
|
|
wdbee
      
Beiträge: 628
Erhaltene Danke: 1
|
Verfasst: Mi 23.03.05 09:33
@Backslash: Das von delfiphan habe ich anders verstanden:
Um zufällige Folgen von Signalen kürzestmöglich darzustellen, benötigt man im Schitt (Erwartungswert heißt da 50% Wahrscheinlichkeit) 8 Bit, wenn es 256 verschiedene Signale gibt und alle gleichwahrscheinlich in der Folge vorkommen.
Das wird so auch stimmen, denn es lässt sich offenbar beweisen. Aber was da nicht auf unsere Annahmen passt, ist die Tatsache, der Uniformität bzw. der Gleichwahrscheinlichkeit.
Wenn wir sagen alle möglichen Folgen, dann sind da alle Kombinationen vertreten, die sich konstruieren lassen. Aber viele davon sind nicht zufällig im o.g. Sinn.
Deshalb passt das nicht zusammen.
Der tatsächliche Anteil der komprimierbaren Folgen ist größer Null, weil es viele Folgen mit Mustern (Redundanz) gibt, die bei der Kompression ausgenutzt werden können.
Das ist halt das Kleingedruckte, was ich immer meine. Offensichtlich läuft das doch auf die mathematische Methode den Löwen in der Wüste zufangen hinaus: Alle Folgen, die komprimierbar sind, sind nicht zufällig, weshalb alle zufälligen Folgen nicht komprimierbar sind.
Wir sprachen oben davon, dass du genaugenommen redundanzfreie Folgen brauchst. Die sind aber nicht gleichzusetzen mit zufälligen Folgen, denn es ist schon eine Einschränkung zu verlangen, dass alle Zeichen in der Folge mit gleicher Wahrscheinlichkeit vorkommen.
Das ist kein Zufall mehr.
@all: Habe ich das richtig zusammengefasst?
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Mi 23.03.05 09:35
@Backslash: Dann können wir wohl oder übel nicht helfen, es hat hier bisher niemand (ausser dir) einen anderen Randomgenerator vorgeschlagen. Wir sprechen bloss immer nur um den heissen Brei...
Backslash hat folgendes geschrieben: | | wieso soll ich Pseudozufallzahlen, die mit 8Byte generiert werden auch nur im Durchschnitt um 8Byte komprimieren können? |
Wurde nicht behauptet, dass diese Pseudozufallszahlen AUF 8 Byte runterkomprimiert werden?
Wenn du zukünftig über deine Algorithmen sprichst, wär es mir sympathisch, wenn du etwas konkreter wärst. Was ist genau diese "Charakteristik", die du in Zufallszahlen gefunden hast? Bitte poste doch mal einer deiner vielen Kompressoren (meinetwegen ohne Source). Wir alle würden deinen Algorithmus sicher mit allen möglichen Dokumenten ausgiebig testen. Das ist doch viel sinnvoller, als wenn wir dir irgendwelche Zahlen schicke, richtig?
Welches Ziel strebst du eigentlich an? Echte Zufallszahlen kann man iA nicht komprimieren und Pseudozufallszahlen kann man auf ihre Startwerte+Algorithmus reduzieren (d.h. auf einige Bytes).
Edit: @wdbee: Ja, würd ich ungefähr auch sagen. (Mit 50% Wahrscheinlichkeit 8 Bit ist nicht dasselbe wie im Schnitt 8 Bit, aber das ist jetzt unwichtig).
Was man vermutlich nicht kann ist es, alle 1MB Zahlenfolgen zu berechnen, die als "Selfdecompressing File" weniger als 1MB benötigen. Ich vermute das geht nicht, und zwar wegen der Kolmogorov-Komplexität(1) (die sich mit einer Turingmaschine(2) nicht berechnen lässt) und des Haltingproblems (es gibt Programme, bei denen man nicht entscheiden kann, ob sie terminieren, weswegen man nicht einfach alle möglichen Programme durchprobieren kann)
Man möge mir widersprechen, ich glaube, das irgendwo, irgendwann mal gelesen zu haben :\
((1) Terminierendes Programm bestimmter Länge, mit welchem man maximal viele Einsen auf den Speicher schreiben kann. (2) Äquivalent zu jedem Computer)
P.S. Sorry, hab das ganze einige Male editiert
|
|
Backslash 
      
Beiträge: 202
WIN XP
Delphi 5 Ent, Delphi 2005 Prof
|
Verfasst: Mi 23.03.05 10:18
@Delphiphan
Ich habe nichts gegen konstruktive Kritik. Das Script von dir ist im übrigen sehr interessant, nur leider ist es mehr oder weniger nur eien Ansammlung von mathematischen Funktionen, die nicht näher beschrieben werden. Steht ja auch oben vom Prof drinnen.
Ich möchte mich nochmal deutlicher ausdrücken. Theoretisch müsste man jede beliebige Zahlenkombination von 2^(1024*1024*8 ) Bits erstellen und auf Kompressionsrate testen, um einen endgültigen Beweis zu liefern. Es geht aber auch einfacher. Was die Charakteristik von Zufallszahlen angeht, so bin ich auf Anfragen bereits deutlicher geworden
Man kann sich an den mathematischen Zufall oder an einige spezielle Vorraussetzungen dafür herantasten. Es müssen nicht alle Zahlenkombinationen von 2^(1024*1024*8 ) geprüft werden.
An dieser Stelle möchte ich die Diskussion abbrechen, da einige Leute meine Postings entweder nicht richtig lesen oder nicht lesen wollen.
Um nochmal zum Ausgangspunkt zurückzukommen: Es wurde ja weiter oben behauptet, dass sich Zufallszahlen durchschnittlich nur um 8 Byte verkleinern lassen, da sie mit 8 Byte initialisiert werden (bei ISAAC). Ich verstehe die Logik nicht ganz. Es ist relativ einfach die generierten Zufallsfolgen der Länge N von ISAAC durchschnittlich auf 8 Byte zu komprimieren. Man muss nur den Algorithmus kennen, der hinter ISAAC steht. Um eine solche Verkleinerung zu erreichen wendet man einfach das Prinzip "Bruteforce" an. Man nimmt eine Kopie des Zufallsgenerators und initialisiert ihn in einer Schleife mit 8 Byte-Werten. Man lässt lediglich die ersten Bytes der Ausgangsfolge generieren und vergleicht sie mit dem vorhandenen Stream solange, bis man eine Folge gefunden hat, bei der alle Bytes übereinstimmen. Dann kennt man den Schlüssel, mit der die Zufallsfolge generiert wurde und diese ist 8 Byte lang. Wenn ich also behaupte alle Folgen = 1 MB von ISAAC um mindestens 4kb komprimieren zu können, dann ist das gar nicht unmöglich.
Ich setze sogar noch eines oben drauf!  Hier ein vereinfachter Algorithmus mit dem sich durch ISAAC generierte Folgen auf 8 Byte komprimieren lassen sollten:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41:
| procedure compressisaacfileto8byte(var SourceFile : String); var i : int64; comparefile : File; compressedfile : File; comparebuf : Buf; correctbytecount : Integer; begin try AssignFile(comparefile, SourceFile); Reset(comparefile, 1); except closefile(comparefile); exit; end; getmem(comparebuf, SizeOf(comparefile); blockread(comparefile, comparebuf^, SizeOf(comparefile)); correctbytecount := 0; for i := 0 to 18446744073709551616 - 1 do begin initISAAC(i); while true do begin if byte(Pointer(DWORD(comparebuf) + (DWORD i))^) = ISAACGetByte then inc(correctbytecount, 1) else begin correctbytecount := 0; break; end; end; if correctbytecount = FileSize(comparefile) then begin AssignFile(compressedfile, SourceFile + '.c8'); Rewrite(compressedfile, 1); BlockWrite(compressedfile, i, sizeof(int64)); closefile(compressedfile); break; end; end; closefile(comparefile); end; |
Mit dieser einfachen Prozedur sollte sich jede durch ISAAC generierte Datei auf die Größe von 8 Bytes komprimieren lassen. Ich hab den Code an der FH geschrieben ohne Delphi-Compiler und bitte daher mögliche Syntaxfehler zu entschuldigen. Ich werd ihn nachher zu Hause mal testen und euch über Erfolg oder Niederlage dieses 8 Byte - Compressors bescheid sagen
Kurze Funktionserklärung:
InitISAAC ist eine Methode zum Initialisieren des ISAAC Zufallsgenerators
ISAACGetByte ist eine Methode um ein zufälliges Byte zu erstellen und zurückzugeben
Wer mir jetzt bitteschön beweisen möchte, dass man mit ISAAC generierte Binärfolgen nur um 8 Byte durchschnittlich komprimieren kann darf freiwillig vortreten.
EDIT: Wie ich in deinem Script gelesen habe @delphiphan, ist die Kolmogorov-Komplexität die Länge des Programms auf einer Turingmaschine, um die Datei maximal komprimieren zu können, richtig? Wenn das so ist, ist die Kolmogorov-Komplexität von ISAAC Pseudozufallszahlen ziemlich gering.
| Zitat: | | Das ist halt das Kleingedruckte, was ich immer meine. Offensichtlich läuft das doch auf die mathematische Methode den Löwen in der Wüste zufangen hinaus: Alle Folgen, die komprimierbar sind, sind nicht zufällig, weshalb alle zufälligen Folgen nicht komprimierbar sind. |
EDIT: Noch einen wichtigen Punkt. Ich behaupte, es ist definitiv total falsch zu sagen, man könnte alle Folgen, die echt zufällig sind, nicht komprimieren. Da wir uns auf dem binären System befinden, existiert ein Zufallsdualismus. Sollte also eine zufällige Folge existieren, existiert eine inverse mit den gleichen Eigenschaften, wenn man alle Bits einfach invertiert. Vertauscht man die Bits der Reihe nach, also das letzte Bit mit dem ersten, das vorletzte mit dem zweiten, usw. bei Bitfolgen mit gerader Länge, existieren sogar 4 mögliche Folgen einer zufälligen Zahl. Demnach muss sich mindestens eine der zufälligen Folgen um mindestens 1 Bit komprimieren lassen, wenn man im mathematischen Sinne beim Countingargument bleibt.
PS: Ich bin auf die Lösung gespannt, wie sich mein Algorithmus austricksen lässt. Selbst wenn das der Fall ist, wovon ich ausgehe, dann hab ich vielleicht endlich eine Möglichkeit, die Obergrenze zu berechnen  Haushoch besser als WinRar ist er alle mal.
Zuletzt bearbeitet von Backslash am Do 24.03.05 08:52, insgesamt 1-mal bearbeitet
|
|
Backslash 
      
Beiträge: 202
WIN XP
Delphi 5 Ent, Delphi 2005 Prof
|
Verfasst: Mi 23.03.05 10:41
Nachtrag: Wer es jetzt für nichts besonderes mehr hält, dass man von ISAAC erstellte Zufallsfolgen um 0,4 % komprimieren kann, der soll es ohne Bruteforce ausprobieren und ohne den ISAAC Algorithmus versuchen 
|
|
wdbee
      
Beiträge: 628
Erhaltene Danke: 1
|
Verfasst: Mi 23.03.05 12:26
Also noch mal ein Versuch, das zusammenzufassen:
Wie oben gezeigt, können berechenbare Folgen immer komprimiert werden, wenn die Folge lang genug ist, also der Alg. plus seine Initialisierungsdaten kürzer sind als die Folge.
Die Umkehrung der Berechnung der Folge (die Kompression) kann immer durch Ausprobieren erfolgen, wenn der Alg. bekannt ist.
Was noch ungeklärt ist: Welchen Anteil haben die berechenbaren Folgen an den möglichen Folgen? Welcher Anteil der Folgen kann als zufällig angesehen werden? Bedeutet zufällig, dass alle Symbole gleich oft enthalten sind (Uniformität) oder wäre das gerade ein Zeichen, dass es sich nicht um Zufall handelt?
@Backslash: Ist es richtig zu behaupten, dass eine deiner vier Folgen (original, invers, originalrückwärts, inversrückwärts) komprimierbar sein MUSS? Gilt die Aussage tatsächlich für beliebige Untermengen? Und wären nicht alle Folgen, die durch Bit-Rotation aus den vieren entstehen, gleichermaßen betroffen?
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Mi 23.03.05 13:39
@Backslash: Es ist nicht mein Skript, sondern das Skript meiner Schule. Ich hab damit eigentlich nichts zu tun, ausser dass ich es eben durchgelesen hab.
Ich will mich nich unbeliebt machen, aber hier ist mein Kommentar zu deiner Prozedur:
Eine doppelte Schleife mit 2^64*2^20 = 2*10^25 Durchläufen.. Ist dir bewusst was das bedeutet? Wenn du für einen Durchgang eine Millionstelsekunde - oder, ich bin heute grosszügig - eine Milliardstelsekunde einberechnest - dann hast du 6.3*10^8 Jahre bis dein Algorithmus terminiert (<- Edit). Aber ich sehe ein, der Algorithmus hatte wohl eher einen "theoretischen" Hintergrund (?). ((Wieso du ihn ausformuliert hast, weiss ich nicht. Vermutlich, weil du es "nachher zu Hause testen wolltest"  (sorry, leicher Sarkasmus verträgst du hoffentlich  ))).
Ausserdem: Wenn meine Zufallsdaten mit ISAAC mit Offset 1 Byte generiert wurden, scheitert dein Algorithmus. Wie dem auch sei, dass man (von einem hinreichend kleinen Programm) alle "berechenbaren" Folgen reduzieren kann auf Algorithmus+Startwert, das wurde schon weit oben mal behauptet, dafür brauchen wir keinen Beweis in Form eines Programmes mehr.
Backslash hat folgendes geschrieben: | | Ich behaupte, es ist definitiv total falsch zu sagen, man könnte alle Folgen, die echt zufällig sind, nicht komprimieren. |
Das ist den meisten hier (wie ich aus ihren Posts entnehme) schon klar. Bei einer zufälligen Zahlenfolge ist jede mögliche Zahlenfolge gleich wahrscheinlich, darunter hat es eine, die so geht: "111111111...". Eine solche Folge zu bekommen ist tatsächlich gleich wahrscheinlich wie jede andere Folge. Und dass man die komprimieren kann, bestreitet hier wohl keiner. (=> 13 Einsen kannst du auf einer Turingmaschine mit nur 4 Zuständen codieren; Mit 5 Zuständen kannst du schon über 4000 Einsen hinzaubern..)
Anstatt deinen Kompressor/Dekompressor in alle Ewigkeit zu loben, wie wär's wenn du uns mal ein exe posten würdest, damit wir den für dich ausgiebig testen könnten? Detaillierte Testergebnisse garantiert!
|
|
Backslash 
      
Beiträge: 202
WIN XP
Delphi 5 Ent, Delphi 2005 Prof
|
Verfasst: Mi 23.03.05 17:31
So, ich hab leider nicht die Zeit, die letzten Postings komplett zu lesen, da ich gerade wieder ne Vorlesung hab. Ich kann jedoch sagen, ich hab den Quelltext mal korrigiert für den 8Byte-Kompressor. Er funktioniert übrigens, braucht allerdings bei 2^64 ziemlich lange.
Hier die korrigierte Version des Quellcodes:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114:
| unit main;
interface
uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, idwisaacasm;
type TFmMain = class(TForm) Button1: TButton; Button2: TButton; Label1: TLabel; LBStatus: TLabel; OpenDialog1: TOpenDialog; procedure Button1Click(Sender: TObject); procedure Button2Click(Sender: TObject); procedure FormCreate(Sender: TObject); procedure FormDestroy(Sender: TObject); private IsaacGen : TIsaac; procedure CompressFile(SourceFile : string); public end;
var FmMain: TFmMain;
implementation
{$R *.DFM}
procedure TFmMain.Button1Click(Sender: TObject); begin Close; end;
procedure TFmMain.Button2Click(Sender: TObject); begin if OpenDialog1.Execute then if Trim(OpenDialog1.FileName) <> '' then CompressFile(OpenDialog1.FileName); end;
procedure TFmMain.CompressFile(SourceFile : string); var i, j : DWORD; comparefile : file; compressedfile : file; CSourceBuffer : PChar; EqualCount : Integer; FilePtr : Integer; CFileSize : Integer; Test : DWORD; begin try assignfile(comparefile, SourceFile); reset(comparefile, 1); except closefile(comparefile); exit; end; CFileSize := FileSize(CompareFile); GetMem(CSourceBuffer, CFileSize); BlockRead(comparefile, CSourceBuffer^, CFileSize); i := 0; j := 0; while i < 4294967295 do begin while j < 4294967295 do begin FilePtr := 0; IsaacGen.Seed([i,j], true); while FilePtr < CFileSize div 4 do begin Test := IsaacGen.Val; if DWORD(Pointer(DWORD(CSourceBuffer) + DWORD(FilePtr * 4))^) = Test then begin inc(FilePtr, 1); inc(EqualCount, 1); end else begin FilePtr := 0; EqualCount := 0; break; end; end; if EqualCount = FileSize(CompareFile) div 4 then begin AssignFile(CompressedFile, SourceFile + '.c8'); Rewrite(CompressedFile, 1); BlockWrite(CompressedFile, i, SizeOf(DWORD)); BlockWrite(CompressedFile, j, SizeOf(DWORD)); exit; end; inc(j, 1); end; inc(i, 1); end; closefile(comparefile); end;
procedure TFmMain.FormCreate(Sender: TObject); begin IsaacGen := TIsaac.Create; end;
procedure TFmMain.FormDestroy(Sender: TObject); begin IsaacGen.Free; end;
end. |
Ihr braucht dazu allerdings den ISAAC-Quellcode. Könnt ihr euch auf der entsprechenden Homepage als Delphi-Variante herunterladen. Ich hab damit mehrere Folgen von Zufallscodes komprimiert, die von ISAAC stammen, verlustfrei auf 8 Bytes. Demnach ist der Informationsgehalt der Folgen 8 Bytes + den ISAAC - Algorithmus, richtig? Ist ja auch logisch
Interessant ist aber, dass komprimierte Dateien (z.B. mit Winrar oder Winzip komprimiert) die gleiche Charakteristik aufweisen.
Soviel dazu. Ich werd mir heut abend mal die letzten Postings durchlesen und vielleicht darauf antworten, sofern ich nicht wieder zahlreiche Beleidigungen vorfinde  Ich hab ja nix gegen eine kritische Stellungnahme, aber so langsam reichts mir hier etwas.
Gruß
Backslash
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: Mi 23.03.05 18:05
Backslash ich glaube die liest hier nicht richtig
1) habe ich schon 2 mal erwähnt das man JEDEN algorithmus auf den code und den startwert komprimieren kann
2) hat das delfiphan auch schon 3 mal gesagt
wir haben NIE behauptet das man den nur um 8 byte verkleinern kann
so da du das 2 posts über mir selbst gesagt hast weiß ich net warum du dann nicht verstehst das du JEDEN generierten code wieder verkleinern kannst also es KEINEN solchen algorithmus gibt den du suchst
setzt dich mit ner stoppuhr an ne vielbefahrende straße, jedesmal wenn ein auto vorbeikommt drückst drauf merkst die die msek wenn die größer als 50 sind haste ne 1 wenn kleiner haste ne 0
dann stopste das 8 mal dann hast ein zufälliges byte zusammen...
also nochmal -> jeder algorithmus kann wieder komprimiert werden, (du wirst keinen finden wos nich geht es sei denn die ausgangsgröße ist größer als das was rauskommt) -> es gibt auch dateien die man nicht weiter komprimieren kann weil es kein schema gibt (im gegensatz zu einem vom algorithmus generierten code)
deine schleife funktioniert auch nur wenn den algorithmus kenns! davon kannste ja nich ausgehen und selbst wenn brauchste für die wohl perfekte komprimierung (bei ISAAC 8 byte + code) immer noch zu viel zeit
also bitte frag nicht nach einem algorithmus sondern nimm irgendwelche dateien die sind schon besser als jeder generierte algorithmus zum testen, bzw nimm nen algorithmus und versuche den code zu komprimieren ohne das du dir anschaust wie der funktioniert und das dann in einer akzepablen zeit
wenn der dolle wettbewerb nen vom algorithmus erstelle datei zum komrimieren angibt und dieser bekannt ist ist das doch total schwachsinnig, dann kann man den ja darauf zurückführen. das kann jeder da braucht man auch net 5 jahre lang an so nem teil programmiert haben -> schlimmstenfalls nimmt man einfach den von dir und geht alle möglichkeiten durch (2^16)
...
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Mi 23.03.05 20:06
Langsam wird das hier zu Off Topic, nicht wahr? Wir sind in einem Delphiforum und zusätzlich nicht im Off-Topic Bereich. Wir versuchen hier Leuten mit bestimmten Fragen zu helfen.
Es bringt niemandem viel, wenn du (Backslash) hier einfach deine neuen Erkenntnisse vorpredigst. Und wie uall schon gesagt hat (siehe oben) scheinst du unsere mehrfach wiederholten Behauptungen entweder nicht gelesen oder nicht verstanden zu haben.
Versteh mich bitte nicht falsch. Wenn du in Zukunft konkrete, kurz und bündig formulierte Fragen stellst, können wir dir bestimmt weiterhelfen.
So. Dann möcht hier noch zu zwei deiner Bemerkungen/Fragen Stellung nehmen.
| Zitat: | | Sollte also eine zufällige Folge existieren, existiert eine inverse mit den gleichen Eigenschaften, wenn man alle Bits einfach invertiert. (...) Demnach muss sich mindestens eine der zufälligen Folgen um mindestens 1 Bit komprimieren lassen, wenn man im mathematischen Sinne beim Countingargument bleibt. |
Dein Schluss ist mir leider unklar. Eine Turingmaschine ist völlig symmetrisch, die kannst du (afaik) ohne weiteres "invertiert" oder "umgekehrt" laufen lassen. Daher behaupte ich, dass deine Behauptung falsch ist.
Dann möchte ich noch zu folgendem Punkt genauer Stellung nehmen. Das scheint die eigentliche Knacknuss zu sein. | Zitat: | | Es geht mir darum, möglichst zufällige Zahlenfolgen zu finden, die bisher als unkomprimierbar galten (verlustlos unkomprimerbar). Das ist denke ich erst mal der wichtigste Punkt. |
| Zitat: | | Gibt es Datenfolgen > 1MB die unkomprimierbar sind? Wenn ja, wie kann ich diese erstellen? (mathematisch) |
Ja, die gibt es. Man kann so eine Folge aber nicht berechnen, weil: Wenn sie berechenbar wären, wären sie komprimierbar, wie uall oben schon sagte. Ein Beispiel für eine (von einer Turingmaschine) nicht komprimierbaren Code ist der Code des (Turing)Programmes, der eine bestimmte Länge hat und dabei maximal viele Einsen auf den Speicher schreibt (und terminiert) => Kolmogorov Kompexität. Dieses Turingprogramm kann man (mit einer Turingmaschine) nicht komprimieren, sonst schreibt es nicht maximal viele Einsen in den Speicher (die BB Funktion ist streng monoton steigend).
P.S. Du möchtest zufällige oder pseudozufällige Datenmengen mit einem allgemeinen Algorithmus komprimieren, welcher keine konkreten Annahmen über die eigentliche Entstehung der Daten kennt (z.B. Kenntnis über den verwendeten Randomgenerator). Im Falle von zufälligen Datenmengen ist das im Allgemeinen unmöglich. Der mathematisch optimalste Kompressor braucht hier im Schnitt mindestens 8 Bit pro Byte.
Die Chance ist aber gegeben, dass du eine komprimierbare Folge (vom Zufall) kriegst. Komprimieren heisst, du musst ein Programm+Startwerte angeben, welche dir diese Folge rekonstruiert. Willst du nun ein fixes Programm haben, kannst du nur noch die Startwerte variieren. So. Wie so ein fixes Programm aussehen muss, ist dann klar: Es muss mittels statistischer Auswertungen zufällig entstandene Muster erkennen. Ich schätze, wenn dein Programm keine Annahmen über Pseudorandomgeneratoren macht (macht es ja offensichtlich nicht, denn es funktioniert mit vielen verschiedenen Pseudorandomgeneratoren, mit rar-Files, mit verschlüsselten Files), dann wird es auch nichts anderes machen als das File eben statistisch auszuwerten. Ohne dass jetzt nachzuprüfen behaupte ich, dass es durch rein statistische Methoden nicht möglich ist, durchs Band 1% oder auch nur 0.5% aus diesen 1MB rauszuholen. Ich sehe hier einen Widerspruch. Wenn dein Algorithmus in verschlüsselten, pseudozufälligen oder bereits komprimierten Daten durchs Band so viele Strukturen erkennt, dann wäre das recht verängstigend. Entweder bist du ein Genie - oder ich sehe deine ganze Story als einen Bluff (oder mir ist ein Denkfehler passiert  ). Die Tatsache, dass du dich stillschweigend weigerst, überhaupt mal was Genaueres über deinen Algorithmus zu sagen oder ein exe zu posten, erhärtet diese Annahme. Das ist kein persönlicher Angriff sondern nur meine ehrliche Meinung. Ich hoffe du verträgst sie.
Ich fände es total interessant und würde mit grossem Engagement und Staunen dein Programm testen. Wenn es aber so weitergeht wie bisher, macht das ganze wenig Sinn...
|
|
Backslash 
      
Beiträge: 202
WIN XP
Delphi 5 Ent, Delphi 2005 Prof
|
Verfasst: Do 24.03.05 09:37
Erst mal folgendes:
| Zitat: |
Von Delfiphan:
Du suchst eine perfekt zufällige Quelle um deinen Algorithmus zu testen? Das musst du gar nicht tun, denn es ist unmöglich... Wenn du irgendwelche Charakteristiken gefunden hast, kannst du sie auf jeden Fall nicht nutzen, um die Daten zu komprimieren. |
Das ist definitiv falsch. Folgendes Gegenbeispiel: Nehmen wir eine 100 Bit-Folge, damit du es auch schneller verstehst. Es gab Leute, es wird sicher noch weiterhin Leute geben (auch wenn das schwachsinn ist), die behaupten, 100 Bit immer um 1 Bit verkleinern zu können. Das ist definitiv unmöglich, siehe Shannon, siehe Countingargument... Jetzt mal unabhängig vom Verfahren. Es gibt sicherlich Wege, viele dieser 2^100 Kombinationen komprimieren zu können. Wir nehmen zum Beispiel, eine Folge daraus, die einen Entropiewert von 99% (ich gebs mal in Prozent an) hat. Diese wird sich sicherlich nicht komprimieren lassen. Das ist schon klar. Doch warum ist das der Fall? Das Hinzufügen der Statusinformationen würden die Größe der komprimierten Datenmenge sehr wahrscheinlich um einige Bits vergrößern.
Gehen wir jetzt ein Stück weiter und nehmen eine Folge von 1 mio Bits mit 99% Entropie. Die Wahrscheinlichkeit steigt erheblich, diese komprimieren zu können. Der Punkt ist: Es gibt Algorithmen, deren Statusinformationen umgekehrt proportional zur Größenänderung der Dateigröße wachsen. Diese Algorithmen können viele, natürlich nicht alle der Zufallsfolgen komprimieren. Das heißt: Je mehr Daten desto verhältnismäßiger weniger Statusinformationen. Ich hab so einen Algorithmus gefunden, wenngleich die Optimierung gar nicht sehr einfach war.
| Zitat: |
Defiphan schrieb außerdem:
@Backslash: Es ist nicht mein Skript, sondern das Skript meiner Schule. Ich hab damit eigentlich nichts zu tun, ausser dass ich es eben durchgelesen hab.
|
Für wie dumm hälst du mich eigentlich? Es ist ja wohl klar, dass ich dein Script sage, weil das von dir kommt, oder nicht? Du sagst es ja selbst. Es ist von deiner Schule. Ich frag mich jedoch ernsthaft, ob du die Vorlesungen überhaupt besucht hast, oder das Script durchgearbeitet hast. Dann hättest du rausgefunden, dass der Entropiegehalt nicht das Maximum einer Nachricht ist, sondern die Kolmogorov-Komplexität. Stand das nicht in Kapitel 3... oder 4?
| Zitat: |
uall@ogc schrieb:
setzt dich mit ner stoppuhr an ne vielbefahrende straße, jedesmal wenn ein auto vorbeikommt drückst drauf merkst die die msek wenn die größer als 50 sind haste ne 1 wenn kleiner haste ne 0
dann stopste das 8 mal dann hast ein zufälliges byte zusammen... |
Auch das ist sowas von total falsch. Anders ausgedrückt in deinem Beispiel wird die Folge nicht zufällig, sondern pseudozufällig werden(wenn überhaupt). Jede Straße hat eine durchschnittliche Auslastung. Anhand dieser kann ich berechnen, wieviele Autos pro Sekunde oder Minute oder Stunde an mir pro Tag vorbeifahren werden. Ich kann so ziemlich genau vorhersagen, vieviele Nullen und Einsen diese "Zufallsfolge" haben wird. Nehme ich einen Feldweg, werde ich viele Einsen haben. Nehme ich die Autobahn, werde ich viele Nullen haben. Nehme ich die Landstraße, bekomm ich vielleicht ein Mittel, aber ich werde nie eine Gleichverteiltheit der Nullen und Einsen erreichen. Klingt doch logisch, oder? Nunja, um den kleinen Denkfehler in deinem Beispiel zu korrigieren, kannst du folgenden Schritt machen. Du setzt dich ein Jahr lang an die Straße und stoppt die Differenzzeiten der Autos, die durchfahren. So hast du ein genaues Verkehrsaufkommen pro Monat und kannst die Durchschnittszeiten berechnen. Wenn du jetzt die zufälligen Zahlen im März generieren willst, dann musst du die Tagesdurchschittszeiten dieses Monats nehmen (weil nachts ja weniger Autos fahren). Beispiel: Es fahren pro Minute 2 Autos durch. Das sind dann 30 Sekunden pro Auto. Also musst du deinen oben angegebenen Richtwert korrigieren. Leider hast du dann immer noch keine zufälligen Zahlen, weil du die Tageszeit noch berücksichtigen musst. Morgens so gegen 7:30 Uhr ist das Verkehrsaufkommen bei Städten höher, da viele zur Arbeit fahren.
Alles in Allem: Mit deiner Idee wirst du nie eine Zufallsfolge rausbekommen, wenn du es so machst wie du oben sagst.
| Zitat: |
So. Dann möcht hier noch zu zwei deiner Bemerkungen/Fragen Stellung nehmen.
| Zitat: | Zitat:
Sollte also eine zufällige Folge existieren, existiert eine inverse mit den gleichen Eigenschaften, wenn man alle Bits einfach invertiert. (...) Demnach muss sich mindestens eine der zufälligen Folgen um mindestens 1 Bit komprimieren lassen, wenn man im mathematischen Sinne beim Countingargument bleibt. |
Dein Schluss ist mir leider unklar. Eine Turingmaschine ist völlig symmetrisch, die kannst du (afaik) ohne weiteres "invertiert" oder "umgekehrt" laufen lassen. Daher behaupte ich, dass deine Behauptung falsch ist. |
Nehmen wir an, die Zahlenfolge 11010001 sei eine zufällige Folge, so hat die inverse Folge 00101110 die gleichen Eigenschaften. Außerdem hat die Folge 10001011 und die Folge 01110100 jeweils ebenfalls die selbe Eigenschaft, Charakteristik oder wie man das auch nennen mag. Das meinte ich mit invers und gleichen Eigenschaften. Wenn also eine Datei mit 8 Bit Länge existiert, deren Folge 11010001 zufällig ist, dann muss zwangsläufig auch 00101110, 10001011 und 01110100 zufällig sein oder nicht?
Jetzt noch zwei Zitate:
| Zitat: | Zitat:
Gibt es Datenfolgen > 1MB die unkomprimierbar sind? Wenn ja, wie kann ich diese erstellen? (mathematisch) |
| Zitat: | | Ja, die gibt es. Man kann so eine Folge aber nicht berechnen, weil: Wenn sie berechenbar wären, wären sie komprimierbar, wie uall oben schon sagte. |
Das klingt einleuchtend. Warum wird dann oben von BenBE behauptet:
| Zitat: | aja, gut, ich kann mich ja mal daran machen für Backslash ne File zu generieren Hab schon ne Idee wie ich seinen Algo austricksen kann Simples XOR von Daten müsste reichen (mit paar anderen Dingen kombiniert)... |
Wenn ihr also die Folge nicht berechnen könnt, die sich nicht komprimieren lässt, also zufällig ist, dann werdet ihr mir auch keine Folge präsentieren können, die mein Algorithmus nicht komprimieren kann. Das ist in der Tat interessant. Wenn man mal davon ausgeht dass das Wissen auf der Erde intelligent ist, dann sollte es doch eigentlich immer intelligent bleiben, auch wenn es komprimiert wurde, da der Algorithmus intelligent ist und das Wissen ebenfalls. Insofern sollte rein statistisch auf der Erde nie eine Folge von Daten auftreten, die zufällig ist. ??? Das geht zwar mehr in den Bereich philosophie, wird aber auch erklären, warum es keinen Sinn mehr macht, nach Zufallsgeneratoren zu suchen. Es sind quasi die falschen Testdateien, da ihr Informationsgehalt abhängig von Zufallsgenerator zwischen 8 und N < Dateigröße Bytes liegt.
| Zitat: |
Entweder bist du ein Genie - oder ich sehe deine ganze Story als einen Bluff (oder mir ist ein Denkfehler passiert ). Die Tatsache, dass du dich stillschweigend weigerst, überhaupt mal was Genaueres über deinen Algorithmus zu sagen oder ein exe zu posten, erhärtet diese Annahme. Das ist kein persönlicher Angriff sondern nur meine ehrliche Meinung. Ich hoffe du verträgst sie. |
Ich ein Genie? Müssen Genies heute nicht schon mit 20 einen Doktortitel haben? Mehr sag ich dazu nicht, außer dass ich keinen hab.
Warum ich nichts genaueres über meinen Algorithmus sage: Nunja, wenn ich es täte, würde es weniger als eine Woche dauern, bis ihn jemand geklaut hätte... Dann waren die vielen tausend Stunden Arbeit der letzten Jahre umsonst. Das kann ich einfach nicht riskieren, sorry. Ich bin jedoch für die kritischen Statements dankbar. Es ist nicht einfach eine Abhandlung über ein so komplexes Thema zu schreiben, wenn man gerade erst am Beginn des zweiten Semesters steht. Das geb ich zu. Ich denke, ich werde mich noch einige Wochen hinsetzen müssen, bis ich die Schwachstelle des Verfahrens gefunden habe oder anders ausgedrückt die Obergrenze. Dann sehe ich weiter.
Danke nochmal für die vielen Antworten. Abgesehen von dem Stress hoffe ich, ihr seht darüber hinweg dass ich oben versehentlich das 8-Byte-Statement von Delfiphan nicht richtig gelesen hab.
Ansonsten viele Grüße
Backslash
|
|
|