Discussion:
Zufallszahlen packen
(zu alt für eine Antwort)
Helmut Wuensch
2018-06-23 15:59:15 UTC
Permalink
Ein großes Hallo und ein schönes WoEnde an Alle!

Kann man (echte) Zufallszahlen (keine Psydo-)
packen/komprimieren?

Annahme: es gibt 1.000 Zufallszahlen von 0 bis
255 als Binär-file. (Ein Byte = eine Zahl)

Meine Meinung als Laie: nein, da nicht redundant.

*Danke* für Eure Antworten und Meinungen!

cu Helmut
Andreas Leitgeb
2018-06-23 16:37:43 UTC
Permalink
Post by Helmut Wuensch
Kann man (echte) Zufallszahlen (keine Psydo-)
packen/komprimieren?
Annahme: es gibt 1.000 Zufallszahlen von 0 bis
255 als Binär-file. (Ein Byte = eine Zahl)
Meine Meinung als Laie: nein, da nicht redundant.
Das muss man etwas differenzierter betrachten:

Wenn man die Zahlen **wirklich** zufällig generiert hat,
ist es *möglich*, dass alle 1.000 bytes den Wert 42
haben, und das sogar mit derselben Wahrscheinlichkeit
wie jede andere konkrete byte-folge!

Daraus sieht man, dass es auch bei Zufallszahlen in
einer konkreten Sequenz durchaus Redundanzen geben
kann, die ein Komprimieralgorithmus erkennen kann.

Die etwas andere Frage ist dann, ob es einen Algorithmus
geben kann, der jede solche Folge komprimieren kann: Nein.

Selbst wenn man nur den Durchschnitt der Kompressionsrate
über alle möglichen Zufallsfolgen betrachtet, wird kein
Algorithmus jemals eine Verkürzung schaffen.

Als Korrolar ergibt sich, dass man aus einer erfolgreich
verkürzenden Komprimierung einer Zufallszahlenfolge *nicht*
schließen kann, dass der Zufallsgenerator schlecht sein müsse.
Helmut Wuensch
2018-06-23 17:03:02 UTC
Permalink
Hallo Andreas,

*danke* für die _tolle_, sehr differenzierte
Erklärung! ( *)Daran hatte ich allerdings nicht
gedacht. :-) )

cu Helmut
Post by Andreas Leitgeb
Post by Helmut Wuensch
Kann man (echte) Zufallszahlen (keine Psydo-)
packen/komprimieren?
Annahme: es gibt 1.000 Zufallszahlen von 0 bis
255 als Binär-file. (Ein Byte = eine Zahl)
Meine Meinung als Laie: nein, da nicht redundant.
Wenn man die Zahlen **wirklich** zufällig generiert hat,
ist es *möglich*, dass alle 1.000 bytes den Wert 42
haben, und das sogar mit derselben Wahrscheinlichkeit
wie jede andere konkrete byte-folge!
*)
Post by Andreas Leitgeb
Daraus sieht man, dass es auch bei Zufallszahlen in
einer konkreten Sequenz durchaus Redundanzen geben
kann, die ein Komprimieralgorithmus erkennen kann.
...
Jens Kallup
2018-06-23 17:57:09 UTC
Permalink
Post by Helmut Wuensch
Hallo Andreas,
*danke* für die _tolle_, sehr differenzierte
Erklärung! ( *)Daran hatte ich allerdings nicht
gedacht.   :-)   )
im Netz unter sourceforge.net gibt es ein nützliches Tool,
das aus einer exec-Datei eine kompriemierte Datei macht.
Welche Algos die machen kann ich nicht sagen.
Aber eine ratio von über 30% hatte ich schon mit einer ca.
550.000 Byte großen binär-Datei, die dann auf fast 200 kB
gekürzt wurde.
Also um ca. die Hälfte.
Natürlich ist zu sagen, das dieses Tool ( upx ) auch den
umgekehrten Weg geht; sprich, die exe Datei in den Speicher
entpackt und ausführt.
Falls Du aber eine VM Programmieren möchtest, dann kannst
Du sowas wie Lisp macht - fasl = fastload Datei erstellen.
Die haben dann ggf. den minimierten Befehlssatz, sind dafür
aber schneller in der Ausführung.
Dieses Prinzip machen zum Beispiel die RISC cpu's.
Die modernen Intel cpu's machen MIPS und man kann schon eine
Bibel dazu schreiben, was für Menomics unterstützt werden,
aber im normalen Gebrauch nicht gebraucht werden.
Da aner der Spiele-Markt dominiert, werden die Hersteller
auch nicht davon abzuhalten sind, Arbeitsplatz-Stationen mit
RISC Arch. bereit zu stellen.
Wenn man nun mit komprimierten Daten arbeitet muss man den
Wert bzw. die Zeit die zum konvertieren benötigt werden, um
wieder native Code zu Erzeugen beachten.
Gerade deswegen bin ich von Java und den ganzen Android
schizn abgekommen, und entwickle nur noch native; manchmal
auch sehr Systemnah mit C oder Assembler.
Vielmals unter der Konsole, da man ja mit den GUI krams ja
sehr schnell ermüdigt.

Gruß, Jens
Stefan Ram
2018-06-23 23:17:16 UTC
Permalink
Post by Helmut Wuensch
*danke* für die _tolle_, sehr differenzierte
Erklärung! ( *)Daran hatte ich allerdings nicht
gedacht. :-) )
Je nach dem Algorithmus kann es einige Dateien geben, die
kürzer werden - aber dafür werden andere dann umso länger.
Im allgemeinen kennt man beim Schreiben des Algorithmus die
später zu komprimierenden Zufallszahlen /nicht/. Dann ist
der /Erwartungswert/ der Komprimierung nicht größer als 1.
Anders gesagt: Gemittelt über alle möglichen zu erwartenden
Dateien und gewichtet mit ihrer jeweiligen Wahrscheinlichkeit
ist Komprimierung nicht größer als 1.

Das Thema kommt mir bekannt vor. Vielleicht wurde so etwas
Ähnliches hier kürzlich schon einmal diskutiert?

Die Komprimierung von /Zufallszahlen/ ist sozusagen so etwas
wie das Perpetuum Mobile der Kompressionsverfahren.
Jens Kallup
2018-06-24 08:39:11 UTC
Permalink
Post by Stefan Ram
Das Thema kommt mir bekannt vor. Vielleicht wurde so etwas
Ähnliches hier kürzlich schon einmal diskutiert?
das Thema Algorithmus wurde hier bestimmt schon diskutiert; in
der Form von Wahrscheinlichkeit.
Ich weiß jetzt nicht, inwiefern der OP vertieft ist mit Chiffre.
Aber der mir am einfachsten erscheinende Chiffre ist die
Cheops oder wie hieß die ägyptische Königin?
Bei der man einen Befehlssatz von 26 Buchstaben hat; sprich: die
Anzahl der lateinischen Buchstaben: A bis Z, die jeweils versetzt
um den Faktor 1 auf einer Walze sind.
Die großen Buchstaben entsprechen positive Werte, kleine Buchstaben
entsprechen negative Werte
In etwa so:

A : A
AB : B
ABC : C
ABCD : D

dann müsste noch ein Stopbit/Zeichen vorhanden sein, das angibt,
wie viel man die Walze drehen muss, um zu den nächsten Buchstaben
für das Wort zu kommen.

Nehmen wir mal an, wir wollten die schwedische Musikgruppe ABBA
chiffrieren; dann können wir:

A1 B_ b1

wobei gilt:
A1 entspricht: A, anschließend Walze um N rshift versetzen (N = +1)
_ entspricht: selbiger Buchstabe (im Beispiel oben: BB )
b1 entspricht: b, anschließend Walze um N lshift versetzen (N = -1)

Man kann also sehen, wie Stefan es schon aufgezeigt hat, das manche
algos. länger werden können, andere sich verkürzen.

Aus dem Wortgeflecht "ABBA" mit initial 4 Buchstaben (Original), ist
eine chiffrierte Antwort entstanden: "A1B_b1", also 6 Zeichen.

Manchmal kommt es vor, das sich Wörter ähnlichen Charakter besitzen,
so dass dass Chiffre weiter encodiert werden kann/muss.

Dazu wurden sogenannte Look-Up Tabellen erstellt, also einfach Tabellen,
die zu jedem zu codierenden Wort einen kürzen Alias oder neuen Algo
vorgaben.

So könnte zum Beispiel der Look-Up Tabellen-Eintrag für das Wort ABBA
mit der Chiffre "A1B_b1" aussehen:

Chiffre | Alt-Chiffre
---------+---------------
_bA | A1B_b1
---------+---------------
... | ...

hier kann man leicht erkennen, das von RL (rechts nach links) codiert
wurde, da A einmal vorkommt, brauch man nur noch die 1 davor schreiben;
und schon hat man es fast geschafft.
Dann folgt b - ebenfalls eine 1 davor (weil alleinstehend),
dann _ ...

Diese Chiffre ist natürlicherweise sehr sehr alt, und sollte nicht in
einen Produktivsystem eingesetzt werden.

Für Lehrveranstaltungen ist dies aber einer mir gängigen Vorgehensweise
in das Thema Chiffre einzusteigen, und als Hausaufgabe für die 2te
Veranstaltung zählende Zusatzpunkte, um dann auch zu überprüfen, ob sich
die Schüler/Studenten überhaupt mit den Thema vertraut machen.

Hope this helps

Jens
Udo
2018-06-24 11:14:24 UTC
Permalink
Hallo, Liebe Mitleser,
ich habe eine Frage, die zwar OT ist, die ich aber sehr beunruhigend finde:

Wenn ich "mal schnell" in diesem Forum Beiträge anschauen will, gehe ich
meist über Google
(https://groups.google.com/forum/?hl=de#!forum/de.sci.mathematik)
hierher und sehe nach.

Jetzt ist mir aufgefallen, dass ich den Beitrag von Stefan Ram bei Google gar
nicht sehe. Erst wenn ich mit Thunderbird und dem eingestellten News-Server
nachsehe, erscheint der Beitrag.

Woran liegt das? Warum unterschlägt Google einzelne Beiträge?
Und kann ich das irgendwie ab-/einstelln?
Ich finde das sehr verwirrend.

Danke für das Verständnis, wenn ich diese Frage gleich hier stelle.

Grüße
Udo
Jens Kallup
2018-06-24 12:00:00 UTC
Permalink
Hallo Udo,

das kann darin liegen, das manche NEWS-Server ihr Feed-Catch
auf (z.B.) 15 Minuten gelegt haben.
Das macht web.de meist mit ihren FreeMailer Konten.

Google ist ja inzwischen ein mächtiger Berg geworden.
Wenn bei denen bei jeden News/Mail - Eingang push gemacht wird,
sind die Server sehr schnell ausgelastet und nur noch damit
beschäftigt einzelne Mails auf Spam/Malware... zu untersuchen,
obgleich die ja riesen große MainFrame's haben.

Viele Provider gehen daher den mittleren Weg - sie sammeln erst-
mal ein paar Tausend E-Mail, Filter, Löschen...
und wenn da OK ist, werden die Mails an den nächsten Provider
versandt.

z.B.: Google => web.de => lokal

web.de hat da einen Timer, der nicht zustellbare E-Mails mit einer
Benachrichtigung and den OP sendet, das die mail nicht zugestellt
wurden konnte.

Aber auch BB macht auf einigen E-Mails ein Auge drüber...
Ansonsten ist web.de seit 20 Jahren mein Favorite in Sachen E-Mail.

Als NewsServer verwende ich "albasani".
Dies ist ein kostenloser und freier NS.
Falls Du erwägst, diesen Dienst auf die Dauer zu nutzen, sind die
Admins dort auf eine kleine Spende dankbar; wegen den Serverkosten.

Jens
Helmut Wuensch
2018-06-24 12:46:29 UTC
Permalink
Post by Jens Kallup
Hallo Udo,
...
Post by Jens Kallup
Als NewsServer verwende ich "albasani".
Dies ist ein kostenloser und freier NS.
Falls Du erwägst, diesen Dienst auf die Dauer zu nutzen, sind die
Admins dort auf eine kleine Spende dankbar; wegen den Serverkosten.
Mein NS ist News.Individual.DE der Uni Berlin; kostet 10 EUR/Jahr.

cu Helmut
Jens Kallup
2018-06-24 16:32:52 UTC
Permalink
Post by Helmut Wuensch
Mein NS ist News.Individual.DE der Uni Berlin; kostet 10 EUR/Jahr.
jup, dafür ist dieser auch sehr Spamfreier als andere.
individual.de hatte ich auch schon mal.
Aber durch unregelmäßige Zahlungen (mtl.) wurde mein
Account dort gelöscht.

Ist das jetzt so ein Flat, oder Trafficvolumen-Tarif?

Jens
Helmut Wuensch
2018-06-25 17:55:31 UTC
Permalink
Post by Jens Kallup
Post by Helmut Wuensch
Mein NS ist News.Individual.DE der Uni Berlin; kostet 10 EUR/Jahr.
jup, dafür ist dieser auch sehr Spamfreier als andere.
individual.de hatte ich auch schon mal.
Aber durch unregelmäßige Zahlungen (mtl.) wurde mein
Account dort gelöscht.
Ist das jetzt so ein Flat, oder Trafficvolumen-Tarif?
*News*.Individual.DE heißt das Ding und ist *nur* für
NG's mit dem Übertragungsprotokoll NNTP!
(Normale [Browser-] Seiten mit http gehen da nicht.
Die NG's liest und beschreibst Du da auch mit einem
READER und nicht mit dem Browser ...)

Da gibt's nur Flat dafür.

cu Helmut

PS: M.M.n. schreibst Du auch auf einem anderen
News Server (eben den bei Tante G. - siehe auch den
Beitrag von Andreas.)
Jens Kallup
2018-06-25 23:42:04 UTC
Permalink
Post by Helmut Wuensch
PS: M.M.n. schreibst Du auch auf einem anderen
News Server (eben den bei Tante G. - siehe auch den
Beitrag von Andreas.)
Hallo Helmut,

eigentlich schreibe ich maßgeblich bei reader.albasani.
Da der Dienst frei ist, kann ich nicht erwarten, dass
dort dann 24h/7d gearbeitet wird.
Eine Aussortierung der Spams erfolgt eigentlich immer
zeitgleich mit der Einsendung.
Meist ist dann am Wochenende, wo wenig Last zu vermuten
wäre, der Server für paar Minuten down, um die besagten
Spam-Mails zu löschen und die Indices neu zu screiben.
Man muss auch bedenkten, das die Hierachy des Server's
auch fast das gesamte Netz umfaßt.

Ansonsten, falls ich da mal keinen READER/SERVER zur
Verfügung habe, verwende ich gockel.

Man könnte auch hergehen und mittels Linux Boardmitteln
eine Art Fake-Mail senden, die dann keinen offiziellen
Mail-Provider-IP-Header beinhaltet, sondern (schlimsten-
falls die Eigene) oder die eines "Dummy-Rechners".

Aber das will ich erst garnicht einführen.
Nur mal ausprobiert, um zu testen ob das überhaupt auch
technisch möglich ist.
Auf die Dauer ist das nix - wie viele andere der
*Deutschen Mitnahmegesellschaft* denken mag (ja, fürchter-
lich, fürchterlich dieses Wort - Leider).

Damit meine ich nicht nur diesen einen speziellen Fall,
nein, sondern auch andere Bereiche (ich sag nur streaming)

Gruß, Jens

Andreas Leitgeb
2018-06-24 13:00:07 UTC
Permalink
Post by Udo
Jetzt ist mir aufgefallen, dass ich den Beitrag von Stefan Ram bei Google gar
nicht sehe.
Stefan hat in seinen Postings den Header "X-No-Archive: Yes" gesetzt.
und Google haelt sich wohl daran, da es sich wohl in erster Linie als
Archiv sieht. Als News-"client" ist Google ja eigentlich auch wirklich
nicht zu gebrauchen.
Helmut Wuensch
2018-06-24 12:21:13 UTC
Permalink
Hallo Jens,
hallo Stefan,

natürlich auch an Euch ein *ganz großes Danke*
für Eure Antworten!

Ihr habt mir viel mehr Fachwissen vermittelt,
als ich eigentlich wissen wollte. :-)

Andreas hat eigentlich schon den Zielpunkt
getroffen; ich wollte nur wissen (bzw. meine
Annahme bestätigt bekommen), dass man eben
binäre Daten, die im allgemeinen nicht
redundant sind, nicht vom Umfang her ver-
kleinern kann. Ich will sie auch nicht ver-
schlüsseln; trotzdem habe ich durch Eure
netten Beiträge (wieder 'mal!) dazugelernt!

An Alle: nochmals Danke!

cu Helmut
Loading...