Hallo Leute,

Die letzten Jahre habe ich mich mit der Kompression von verlustfreien Daten beschäftigt und bin dort auf eine interessante Sache gestoßen. Das Problem ist, dass ich bisher keine Datei oder zufällig generierte Datei gefunden habe, die 100% zufällig oder wenigstens annähernd zufällig war, um meine Entwicklungen zu testen.

Ich habe bisher Zufallsgeneratoren von random.org ausprobiert. Die sollen nach eigenen Angaben angeblich die besten sein. Das kann ich nicht bestätigen, da sich jede, aber auch jede generierte Datei extrem vom mathematisch definitorischen Zufall abwich. Ich hab mich bereits mit Doktoren der Informatik in Verbindung gesetzt, um möglicherweise bessere Zufallsgeneratoren zu finden. Bisher ohne Erfolg.

Den Zufallsgenerator von Delphi hab ich auch schon gestestet, aber der liefert noch schlechtere Ergebnisse wie random.org. Ich hab bisher über 300 Dateien > 1 MB getestet, darunter bereits komprimierte. Alle wichen extrem ab. Weiß jemand von euch vielleicht, wo ich mir einen Zufallsgenerator oder zur Not auch generierte Streams runterladen kann, die etwa der maximal möglichen Zufälligkeit entsprechen? Ich brauche wirklich gute Algorithmen, um zufällige Datenmengen zu erstellen.

Bin für jede Hilfe dankbar.

Gruß

Backslash

PS: Ich hab im Internet so ein Stichwort wie Kolmogorov Komplexität von Datenströmen entdeckt. Ich glaub, es wäre gar nicht schlecht wenn ich eineni Zufallsgenerator finden würde, der das berücksichtigt.

Ist Zufall nicht Zufall und was rauskommt ist Zufall?

nicht ganz *g*

-> zurück zum Problem.

Hallo und

Der PC kann leider nur pseudozufällige Zahlen generieren. Das ist klar, denn der Computer kann nur addieren, subtrahieren, und einige andere Operationen. Vielleicht probierst du mal dein Glück mit den Nachkommastellen von sqrt(2). Natürlich sind die Zahlen nicht zufällig, sondern können mit einem Algorithmus berechnet werden.
Wenn du wirklich zufällige Zahlen brauchst, musst du dir irgendwelche Tabellen suchen!

danke für die schnelle Antwort. Tabellen? Gibt es Tabellen, mit denen man zufällige Zahlen generieren kann? Das Problem ist, dass ich nicht genau weiß, wie sich "echte Zufallszahlen" von "Pseudo-Zufallszahlen" unterscheiden.

Was ich suche ist ein Programm oder einen Algorithmus, den ich in mein Delphiprogramm (ist kein Muss) mit einbinden kann, um "echte" zufallsfolgen (Bytefolgen) erzeugen zu können. Ich möcht zum Beispiel angeben können: Die Datei soll 1 MB groß sein und zufällig

Gibt es dafür gute Programme? Ich hab lang gegoogelt aber leider teilweise nur Programme gefunden, die nix taugen.

Kannst auch evt ein paar Primzahlen nehmen. Sind stellenweise weit größer als 1 MB (die 42. Mersenneprimzahl z.b. ist 2^25,964,951-1, dummerweise allerdings Hexadezimal FFFFFFF..... musst dir also was einfallen lassen )

Sind Primzahlen zufällig? Ich glaub, sie werden weit schlechtere Ergebnisse als die Zufallsgeneratoren von Random.org liefern. Ich hab schonmal überlegt, ob ich die Zahl "Pi" analysieren und komprimieren soll Fragt sich nur, wieviele Stellen!? Nunja, in der Zahl ansich sind teilweise ziemlich viele Rendundanzen. Bring glaub ich nicht viel.

Zurück zur eigentlichen Frage weiter oben: ->

Hmm...du könntest versuchen Texte einzulesen und damit eine Datenbank auf dem Markov-Modell anlegen. Dann nimmst du immer den unwahrscheinlichsten Folgebuchstaben, wobei du dann wieder häufig bei y und q landest...Vergiss die Idee

Markov Modelling... Das sagt mir was. Vielleicht google ich mal schnell. Aber ich schätze ich werd nix besseres als random.org finden. Das Problem ist, dass diese Seite gleichsam ne Blackbox ist. Die generieren zwar zufällige Daten aber ich hab nicht gefunden, welche mathematischen Verfahren dafür verwendet werden. Ist sowieso ziemlich strange: intelligente Verfahren für zufällige Datenfolgen

Schließt das eine nicht das andere aus?

Wie gesagt, ein Computer kann aus Prinzip keine echte Zufallszahlen generieren. Da brauchst du Zahlentabellen mit Zahlen, die aus Messungen von radioaktiven Quellen (o.ä.) stammen. (Es gibt auch Geräte, die du an den PC anschliessen kannst)

Achso. Hm... Das ist interessant. Frag mich nur wo ich sowas finden kann? Ich komm nicht so leicht an radioaktive Stoffe. Es sei denn, ich nehm einen Geigerzähler und messe die relative Zerfallsrate pro Sekunde. Den müsste ich nurnoch an den PC anschließen und dann warten, bis ich über ne million Bytes zusammen hab Ich schätze, das wird ziemlich aufwändig. Son Mist

Backslash hat folgendes geschrieben:

Die letzten Jahre habe ich mich mit der Kompression von verlustfreien Daten beschäftigt. ... Ich habe bisher Zufallsgeneratoren von random.org ausprobiert. Die sollen nach eigenen Angaben angeblich die besten sein. ... zur Not auch generierte Streams runterladen kann, die etwa der maximal möglichen Zufälligkeit entsprechen? Ich brauche wirklich gute Algorithmen, um zufällige Datenmengen zu erstellen. PS: Ich hab im Internet so ein Stichwort wie Kolgomorov Komplexität von Datenströmen entdeckt. Ich glaub, es wäre gar nicht schlecht wenn ich eineni Zufallsgenerator finden würde, der das berücksichtigt.

Hallo Backslash,

auch im Zusammenhang mit Zufallszahlen ist etwas Präzision sinnvoll. Du beschäftigst dich offenbar mit der verlustfreien Kompression von redundanzfreien Daten. Richtig?

Was ist die Qualität von Pseudo-Zufallszahlengeneratoren? In der (Extremwert-)Statistik werden hier andere Kriterien angesetzt als in der Kryptographie. Für statistische Aussagen spielt die Verteilungsfunktion der erzeugten Zufallszahlen die Hauptrolle, die Berechenbarkeit interessiert da nur am Rande. Also kommen alle Werte gleich häufig vor (Gleichverteilt), oder sind sie etwa Normalverteilt (Gaußkurve).

In der Kryptologie ist das eigentlich egal. Hier ist die Berechenbarkeit bzw. die Möglichkeit aus kompromitierten Teiltexten auf die Folge der Zufallszahlen rückschließen zu können, der interessierende Punkt. Wenn man. z.B. weiß, das der verschlüsselte Text ein Word-Dokument der Version X ist, und weiß, das solche Dokumente einen langen Vorspann haben, der immer gleich ist, dann könnte man einen Teil der Zufallsszahlen ermitteln, die für die Verschlüsselung verwendet wurden. Gelingt es nun, aus dieser Teilfolge auf die weiteren Zufallszahlen zu schließen, ist der Code geknackt.

Deshalb muss man immer wissen, wofür die Zufallszahlen verwendet werden sollen, bevor man Aussagen über die Qualität der Generators machen kann.

Umgekehrt ist das Ziel einer perfekten Verschlüsselung, alle Redundanz aus den unerschlüsselten Daten zu entfernen, damit kein Angriff auf der Basis von statistischen Analysen möglich ist. Um also zu "zufälligen" Datenströmen zu kommen, solltest du mal verschlüsselte Texte verwenden. Im Gegensatz zur Komprimierung, die Redundanz nutzen will, sollte Verschlüsselung die beseitigen.

Die Qualität verschiedener Verschlüsselungsverfahren kannst du dann ja mit Verfahren wie dem von Kolmogorv testen, bevor du ein Verfahren für deine Zwecken auswählst.

Sorry für meine unpräzise Antwort. Du hast völlig recht

Ich sprech nicht zufällige Zahlenfolgen an, die für Kryptographie genutzt werden können. Ich meine gleichverteilte Folgen mit gleichen Wahrscheinlichkeiten pro Element.

random.org soll das glaub ich bieten. Jedoch ist die Abweichung vom definitorischen Zufall zu hoch.

Beispiel für das was ich mir unter Zufällig vorstelle:

1. Die Wahrscheinlichkeit für eine binäre 1 im Stream soll genauso hoch sein wie die Wahrscheinlichkeit, eine binäre 0 vorzufinden.

2. Die Wahrscheinlichkeit von zwei gleichen aufeinanderfolgenden Bits soll genauso hoch sein wie die Wahrscheinlichkeit von zwei nicht gleichen aufeinanderfolgenden Bits

3. Die Anzahl der 1-Bits im Stream sollte gleich groß sein wie die Anzahl der 0 Bits (für Gleichverteilung wichtig)

....

Es gibt noch weitere Kriterien. Doch um diese hier geht es im Wesentlichen.


EDIT: Sollten zufällige Bytefolgen nicht auch redundanzfrei sein???

Ich denke Pseudozufallszahlen sind nicht schlecht. Deine 3 Punkte werden von den üblichen Randomgeneratoren sicher erfüllt!
Um die Abweichung feststellen zu können, müsstest du wohl Tausende von Milliarden von Zahlen berechnen lassen, da deine Statistik nur mit 1/sqrt(t) konvergiert.

Edit: Ich denke das Hauptproblem ist, dass die Dateien, die du untersucht hast, nicht ausreichend gross für eine aussagekräftige Statistik waren!

Nun die gleiche Anzahl von 0- und 1-Bits lässt sich sehr einfach erreichen:

Du erzeugst eine Datei mit einer deterministischen Struktur, immer abwechselnd eine 1 und eine 0.
Da wir immer in 8-Bit-Zeichen denken, geht das immer auf. Nun kommt das eigentliche Problem. Du musst zufällige Vertauschungen vornehmen, die die Wahrscheinlichkeit von 00, 11, 01 und 10 ins Gleichgewicht bringt. Aber die Gleichverteilung der 0- und 1-Bits bleibt immer erhalten, sie also von Anfang an perfekt. Um hier eine praktikable Lösung zu finden, muss man alle Kriterien betrachten, also auch die im Kleingedruckten!

Zum Edit: Zufällig in welcher Hinsicht, das ist die Frage. Nicht vorhersagbar, nicht berechenbar, statistisch gleichverteilt?

// Edit: Wenn du mal die Übergänge von 00 11 01 10, 00 11 01 10, ... betrachtest, erfüllen sie rein statistisch dein Übergangskriterium, aber von Zufall kann da keine Rede sein!

Nunja, prinzipiell bin ich auch für andere Zufallsgeneratoren offen, die nach anderen Prinzipien funktionieren. Mir geht es nur um die Analyse des Counting-Arguments, das im wesentlichen gegen die Kompression von zufälligen Datenmengen spricht.

Leider hab ich jetzt schon allerhand Dateien getestet und bin nicht glücklich geworden. Gibt es noch was anderes wie www.random.org? Mir geht es um möglichts zufällige Folgen. Vielleicht sollte ich nicht die einschränkung machen, ob gleichverteilt oder als gauß-wahrscheinlichkeit.

Ich hätte nicht gedacht, dass das Erzeugen von zufälligen Zahlen eine so hohe Komplexität besitzt. Vielleicht sollte ich das ganze so einschränken, um euch die Hilfe bei meinem Problem zu erleichtern.

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. Ich sag nur soviel: Den 5000$ Compression-Contest hätte ich bereits spielend gewonnen, zumal die Macher dieses Contests Dateien generiert von random.org benutzen

Also ich muss mich etwas mehr einschränken. Gibt es Datenfolgen > 1MB die unkomprimierbar sind? Wenn ja, wie kann ich diese erstellen? (mathematisch) Also damit man mich nicht missversteht: Ich meine Datenfolgen, die bisher als unkomprimierbar galten

Backslash hat folgendes geschrieben:

Ich sag nur soviel: Den 5000$ Compression-Contest hätte ich bereits spielend gewonnen

Nicht so überheblich bitte. Dann poste doch mal n bisschen Code!
Komprimier mal irgendwas mit deinem super Komprimierer und versuch dann das Komprimierte nochmals zu komprimieren. Es wird nicht gehn! Sonst wärst du am Schluss auf einem Bit, und könntest daraus alles rekonstruieren!
Komprimierung funktioniert indem man in einer Byte oder Bitfolge Strukturen erkennt und diese ausnutzt, d.h. die Redundanzen entfernt.

Die Randomgeneratoren von Random.org sind wahrscheinlich so gut wie man Pseudorandomgeneratoren überhaupt konstruieren kann.

Was wäre denn, wenn es die nicht gäbe (1 minus Logik):

Wir nehmen eine lange Datenreihe und komprimieren die. Wenn sie noch länger ist als 1 MB + 1 dann komprimieren wir sei halt nochmal. Das ganze solange, bis wir <= 1MB sind.

Wenn die Annahme richtg wäre, ginge das.

@defiphan: Ok, du warst schneller!

am besten machst dann folgendes:

man nehme eine große datei (JPG) (10mb) packe sie mit zip dann ace dann rar

wenn du dann schaffst die rar datei nochmal um mehr als 1/10 zu packen haste meinen respekt

benutz WinUha, da kannste vielleicht die 10% noch rausholen