Zahlen komprimieren und expandieren

  • Allgemein

Es gibt 14 Antworten in diesem Thema. Der letzte Beitrag () ist von o815michi.

    Zahlen komprimieren und expandieren

    Neu

    Hey an alle Mathematikgenies,

    ich hatte mir die Tage mal Gedanken über die Zusammenführung von Zahlen gedacht. So zu sagen aus 2 mach 1. Was ja eigentlich kein Problem ist. Zahl 1 + Zahl 2.
    Doch was mache ich, wenn ich aus der einen Zahl wieder die beiden nehmen will. ( Dass ganze ging so in die Richtung der Kompression. )
    Selbst dass zurückführen ist noch leicht zu realisieren. Ich stelle dass ganze mal in Bytes da.

    Reduzieren
    Spoiler anzeigen
    Byte 1 -> 25
    Byte 2 -> 45

    Byte1 * (255+1) + Byte 2 = 6445


    Expandieren

    Spoiler anzeigen
    6445 Modula (255+1) = 25 Rest 45


    Dass funktioniert eigentlich wie gewollt. Nun muss ich diese nach dem Reduzieren auf einen Wert zwischen 0 und max 255 beschränken, da ich beim Reduzieren 2er Werte die schon mal zusammen geführt worden sind bei 2 Stelligen Millionwerte lande.

    Nun habe ich bestimmte Eigenschaften/Möglichkeiten
    1. Die Zahlen dürfen keine Nachkommastellen besitzen.
    2. Diese Zahlen müssen auch wieder zu dem ursprünglichen Wert umgewandelt werden können.
    3. Die Berechnung mit Konstanten.
    4. Die Berechnung mit Schleifen bedingten Werten.
    5. Pro Reduzierung ( 8B,10B, 500B oder ...) sollte maximal 1 Byte einen Wert enthalten der zur Expandierung wieder verwendet werden kann.

    Der Maximale Betrag von 2 Bytes ist demnach 255*(255+1)+255= 65.535

    Dass ist so weit richtig, da ich diesen brauche wenn ich die 2 Bytes wieder raus finden möchte. Doch wenn ich diese so speichern würde, dann würde ich natürlich 16 Bits benötigen. Da bin ich dann wieder bei meinen 2 Bytes von jeweils 8 Bit Länge. Ich habe demnach nichts verkleinert, lediglich zusammengeführt, doch die Größe bleibt ja die Selbe.

    Hoffe ihr versteht meinen Denkansatz 8o

    Wenn ich dass alles versuchen würde in einer Frage zu verpacken dann würde die vermutlich so aussehen : Gibt es eine Mathematische Möglichkeit, mit der ich eine Zahl, die den Wert 65535 nie überschreitet auf einen Wert zwischen 0 und 255 beschränken zu können, mit dem Ziel die Ursprüngliche Zahl wieder aus dieser Grenze zu bekommen.

    Liebe Grüße

    #Edit

    Egal wie oft ich darüber nachdenke. Ohne einen Zusätzlichen Wert pro Reduzierung ist eine Grenze von 255 nicht zu realisieren. Würde ich jetzt einen Wert pro Iteration auf alle Bytes verwenden, müssten man wahrscheinlich Millionen von Werten durchgehen, um genau diesen einen zu finden, der auf alle Werte oberhalb der 255 Grenze angewendet einen Betrag zwischen 0 und 255 ergibt.Und zu jedem Byte ein extra Byte zur reduktion anwenden ist sinnfrei. Ach, kann es nicht so eine "magische Zahl" wie PI geben, die auf 65535 angwendet immer einen reelen Betrag zwischen 0 und 255 ergibt^^

    *Topic verschoben*

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Marcus Gräfe“ ()

    Neu

    @Bagplatt ICh glaube, Du denkst zu kompliziert.
    Das ganze ist keine Kompression, sondern eine andere Interpretation von Speicherinhalt.
    2 Bytes sind aneinandergehängt ein ushort und feddich.
    Sieh Dir mal die Klasse BitConverter an: msdn.microsoft.com/de-de/libra…tconverter(v=vs.110).aspx
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    VB-Fragen über PN / Konversation werden ignoriert!

    Neu

    Guten Abend

    So aus dem Kopf heraus, würde ich sagen, da gibt es immer mehrere Resulte, sofern man so was lösen möchte, was wiederum wahrschienlich schwierig wäre, um herauszufeinden um welche 2 Zahlen sich es hier jetzt wirklich handelt.

    Also ich nehme mal an.

    2 Bytes: (45,73)
    Dazu würde ich eine grössere Prime (z.B. 251) nehmen, damit das irgendwie festgehalten werden kann.

    Jetzt irgend eine Gleichung, die nachher auch wieder aufgelöst werden kann. Also so etwas wie
    (46 + 73) * 73 = z

    (x + y) y = z

    Aufgelöst auf x gibt das glaube ich
    x = (z - y^2) / y

    z ist die Zahl die ich mit der Prime multipliziere und nachher modula (byte.max + 1)

    (z * p )mod 256 = Result >> Result ist die komprimierte Zahl


    Und wieder zurück:
    Jetzt erstell ich ne Algo in dem z gesucht wird, irgendwie so

    for i = 0 to 255
    (i * 251) mod 256 = Result
    next

    die oben erwähnte Gleichung auflösen.

    wahrscheinlich wird es mehrere Resultate geben, aber wahrscheinlich nur eine, bei der alle Zahlen ganzzahlig sind .

    Jooo, vielleicht habe ich auch einen Denkfehler drin, habes also nicht getestet :D

    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „exc-jdbi“ ()

    Neu

    @exc-jdbi

    So weit funktioniert dass alles. Doch ich bekomme folgende Funktion nicht umgestellt :

    exc-jdbi schrieb:

    (z * p )mod 256 = Result


    Dass müsste doch eigentlich so gehen :
    Naja, jedenfalls bekomme ich den Ursprünglichen Wert Z nicht mehr heraus.

    Liebe Grüße
    Bilder
    • wolfram.png

      269 Byte, 74×29, 80 mal angesehen

    Neu

    Bagplatt schrieb:

    Naja, jedenfalls bekomme ich den Ursprünglichen Wert Z nicht mehr heraus.

    RodFromGermany schrieb:

    Sieh Dir mal die Klasse BitConverter an: msdn.microsoft.com/de-de/libra…tconverter(v=vs.110).aspx
    Hätte ich auch ignoriert. X(
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    VB-Fragen über PN / Konversation werden ignoriert!

    Neu

    @RodFromGermany Tut mir leid, ich wollte dich wirklich nicht ignorieren. Doch ich war so eifrig am rechnen, dass ich das vergessen habe ;( die Klasse kenne ich bereits. Ich finde ich in dieser keine Funktion, die dass Unmögliche meiner Idee auf einfache Weise realisieren kann. ( Ich gehe selbst davon aus, dass das nicht funktioniert. ) Denn wenn, dann könnte man Theoretisch eine x Anzahl von Bytes immer und immer wieder zusammen nehmen, bis am Ende nur eines Übrig bleibt. Zur Umkehrung bräuchte man dann nur noch die Anzahl der Wiederholungen und dass eine Byte.

    RodFromGermany schrieb:

    2 Bytes sind aneinandergehängt ein ushort und feddich.


    Und dass sollen sie ja nicht sein. Die Methode von @exc-jdbi verkleinert den Wert der 2 Bytes in den gewünschten Bereich zwischen 0-255 ( 8 Bit ). Nur bekomm ich den ursprünglichen Wert Z nicht mehr heraus.

    Liebe Grüße

    Neu

    Bagplatt schrieb:

    Denn wenn, dann könnte man Theoretisch eine x Anzahl von Bytes immer und immer wieder zusammen nehmen, bis am Ende nur eines Übrig bleibt. Zur Umkehrung bräuchte man dann nur noch die Anzahl der Wiederholungen und dass eine Byte.
    Wenn Du eine Methode findest, die jede beliebige Bytefolge (insbesondere von mir vorgegebene Bytefolge) um ein Byte verkleinert (im Sinne von Kompression) bekommst Du von mir 1 Million Euro :!:
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    VB-Fragen über PN / Konversation werden ignoriert!

    Neu

    Nur eine Million? Du bekommst von mir das ganze Geld dieser Welt, inklusive der aktuellen Schulden von allen Nationen dieser Welt ausgezahlt in Kupfer.

    Mal hier ein Ansatz, warum ich solch eine Wette eingehen würde:
    Also wir nehmen an wir haben die funktion compress, welche eine beliebige Bytefolge nimmt und die Anzahl der Bytes halbiert:
    c' = compress(u)
    mit |c'| = ceil(|u|/2)
    gerne auch Zusätzlich |c'|>=1 und |u| >= 2

    ich nehme einfach mal nen Randomwert und sage meine unkomprimierten Daten sind 1 Zebibyte und behaupte einfach mal, das reicht für das komplette Internet.
    Das sind 2^70 bytes

    Quellcode

    1. c[71]=u//uncompressed data
    2. for (int i=70;i>=0;i--)
    3. {
    4. c[i]=compress(c[i+1])
    5. }

    Ich komprimiere also die kompletten Daten des Internets und komprimiere diese wieder mit dem komprimierten Ergebnis, das ganze 70 mal.
    Dann haben wir das gesammelte Wissen der Menschheit in einem Byte gespeichert in einem Byte, denn die größe von jedem c lässt sich ja berechnen durch halbieren der größe des vorherigen cs
    |c[71]| = 2^70
    |c[70]| = 2^70 / 2
    |c[69]| = 2^70 / 2 / 2 = 2^70 / (2*2) = 2^70 / (2^2)
    ohh moment mal, das können wir ja einfach abkürzen, wir teilen 70 mal durch 2
    |c[0]| = 2^70/(2^70) = 1

    Eine Komprimierung ist nicht einfach nur ein einfaches verkleinern von Daten, es ist entweder das weglassen von Daten, die für uns unwichtig sind(verlustbehaftete Komprimierung z.B. jpeg), oder weglassen/umformulieren von Daten, die aus etwas anderem Hervorgehen. Dasselbe gilt auch für Sprache.

    Quellcode

    1. Ich möchte 5 Kartoffeln.

    z.B. Verlustbehaftete Kompression:

    Quellcode

    1. Ich möchte Kartoffeln

    evtl. interessiert einen ja die Anzahl nicht.

    Oder verlustfrei

    Quellcode

    1. I wett 5 Kartoffla

    Wobei der Kompressions/Dekompressionsalgorithmus hier dem Sprechen/Verstehen des Dialekts entspricht.

    Natürlich gehört zur Sprache auch ein Wörterbuch und wie der Zufall es so will gibt es Komprimierungen, welche mit "Wörterbüchern" arbeiten, diese Funktionieren natürlich nur gut, wenn der Verweis auf ein Wort in diesem Wörterbuch weniger Daten benötigt als das Wort selbst.
    So wie du es haben wolltest hättest du ein Wort mit der Länge 2^16, aber auch 2^16 Wörter, d.h. für den Zugriff brauchst du auch einen Zeiger der Größe 2^16 und somit hast du nichts gewonnen.
    Was man aber machen könnte wäre Zusatzinformationen zu speichern um für bestimmte Daten weniger Platz zu benötigen:
    Wir könnten z.B. das letzte Bit eines jeweiligen Bytes auf 1 setzen, wenn der Wert ein weiteres Byte benötigt(bzw. das letzte Bit dieses Bytes).
    Somit gilt für x <= 127 -> result = x
    für > 127 jedoch result = 128 | x
    (das ganze gilt nur für 16 Bit zahlen, ansonsten müsste man mit demselben Verfahren weiter machen).
    D.h. man braucht für alle uint16 < 127 nur 1 Byte, für alles danach jedoch die vollen 2. Wenn wir also eine total randomisierte Zahlenfolge haben, dann sparen wir im Schnitt ~ 2^7/2^15 ~ 0,4%, man darf dabei aber auch nicht außer Acht lassen, dass man Zahlen > 2^15 damit nicht mehr abspeichern kann und für diese ein byte mehr benötigen würde.
    Es kommt also hinzu, dass jede Komprimierung, wenn es schlecht läuft sogar mehr Ausgangsdaten hat als Eingangsdaten...
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---

    Neu

    @jvbsl Sehr gut. :thumbup:
    Einfach gesagt:
    Aus 1000 mach 999
    aus 999 mach 998
    aus 998 mach 997
    ...
    aus 4 mach 3
    aus 3 mach 2
    aus 2 mach 1 :thumbsup: :thumbsup: :thumbsup:
    Alle Daten der Welt zu einem Byte komprimiert.
    Wer mag das dekomprimieren?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    VB-Fragen über PN / Konversation werden ignoriert!

    Neu

    Mein Gott - ihr habt jetzt eine Woche gebraucht, um herauszuarbeiten, dass Bagplatts Ansinnen auf deutsch gesagt: "Unsinn" ist?
    Und sogar das mathematische Beweisverfahren "vollständige Induktion" (zumindest was ähnliches) hinzugezogen?

    Immerhin glaube ich schließlich überhaupt die Fragestellung verstanden zu haben: Bagplatt tut es weh, zB bei Integer immer 4 Bytes verbraten zu müssen, auch wenn in 99% der Fälle, die 3 höherwertigen Bytes alle 0 bleiben - richtig?

    Es gibt da übrigens eine theoretische Komprimier-Möglichkeit, aber wohl nicht mit vertretbarem Aufwand umsetzbar, und v.a. die Performance dürfte ganz unvertretbar in den Keller gehen:
    Man könnte ein Bit reservieren für die Info, ob zur Zahl noch weitere Bytes gehören.
    Bei string-Encodings gibts sowas, glaub utf7, utf8 wenden das an.
    Weil 99% der tatsächlich verwendeten Zeichen liegen ja im Ascii-Bereich, aber dennoch muss ein Char 2 Bytes reservieren, um die ungeheure Menge an Sonderzeichen auch unterstützen zu können, u.a. ganze Zeichensätze aus dem chinesischen, arabischen, kyrillischen,....

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ErfinderDesRades“ ()

    Neu

    ErfinderDesRades schrieb:


    Es gibt da übrigens eine theoretische Komprimier-Möglichkeit, aber wohl nicht mit vertretbarem Aufwand umsetzbar, und v.a. die Performance dürfte ganz unvertretbar in den Keller gehen


    Das ist auch keine wirkliche Komprimierung, sondern halt, wie auch deine Beispiele, ein Encoding... (Ja, es gibt auch Kodierungen, die wirklich komprimieren, zb. Huffman-Codes) Und warum sollte dadurch die Performance in den Keller gehen? Warum ist der Aufwand nicht vertretbar? UTF-8 macht es doch genauso? Oft verwendet man Encodings, die nicht mal besonders platzsparend sind, z.B. Base64, und das ist oft anzutreffen, z.B. bei HTTP.

    Neu

    @ErfinderDesRades komm mal lieber wieder schnell runter von deinem hohen Ross, schließlich hast du ja bewiesermaßen einen Tag mehr gebraucht, sonst hättest du ja wie wir alle bereits gepostet, bevor du es dir angeguckt hast.
    Der tolle Beweis ist nur zum Verständnis für den TE und Formschönheit ist mMn sowieso unnötig.

    Und dein toller Vorschlag mit deinem einen Bit steht auch schon da.

    Wobei ich es echt lobenswert finde, dass du ausnahmsweise mal an die Performance denkst, aber dann auch noch bei etwas, was kaum Performance braucht, dabei bist du doch einer derer, die gerne Performance sonst wo hin blasen :P
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---

    Neu

    Hallo,

    die Überschrift und die nächsten Zeilen hören sich für mich etwas anders an.

    Wenn ich zwei Zahlen in einer vereinigen möchte nenne ich das Tabelle.
    Da gibt es einen Index. Dieser wird einfach durchgezählt. Dann gibt es Spalten und Zeilen.
    Um aus dem Index die Spalte zu errechnen muss ich nur noch die Maximale Spalte definieren.
    Zusätzlich muss ich noch für jedes definieren ob ich mit 0 oder mit 1 anfange.
    Dann ergibt sich aus jeder Zahl -> 2 Zahlen. Jeder Index kann in Zeile und Spalte mathematisch aufgelöst werden.

    In Excel sieht das so aus. ( Weil ich ein Beispiel in Excel habe. Es dürfte nicht schwer fallen es in VB zu übersetzen.)
    Basis Jeweils 1 (Index;Spalte;Zeile)
    Maximale Spalte 3 ( Ist egal, ich rechne ja nicht vor ;) )

    Spalte/Zeile zu Index

    Quellcode

    1. =Spalte+(Zeile-1)*MaxSpalte


    Index -> Spalte

    Quellcode

    1. ​=REST((Index-1);(MaxSpalte))+1


    Index -> Zeile

    Quellcode

    1. =GANZZAHL((Index-1)/(MaxSpalte))+1


    und wenn man etwas nachdenkt, kann man das bestimmt für beliebig viele Dimensionen, also Zahlen machen.
    Der einzige Nachteil ist, diese Formeln geben keine Fehler aus. Wenn ich 0:0 als Eingabewert verwende, kommt der Index -3 raus. Das kann man aber extra rausfiltern ...

    'Nur mal so, ich habe eigentlich was anderes gesucht.'

    Grüße