Logisch grübeln: Information Codieren

[Monty]

Hallo.
Ich habe schon Kopfschmerzen, denn ich sitze schon seit vielen Stunden grübelnd an einem Problem:

Aufgabe ist es im Zahlenbereich von 1 bis 1200 bis zu 600 Zahlen in einem Code bestehend aus Buchstaben(A-Z) und Zahlen (0-9) zu Speichern, und wieder rückrechnen zu können.
Dieser Code sollte möglichst kurz sein, was das eigentliche Problem ausmacht.

Das Ergebnis sollte in etwa so aussehen:
                   3S3O6AU8T4... => 1;25;36;45;89;96;111;123;589;...
und
1;25;36;45;89;96;111;123;589;... => 3S3O6AU8T4...

Uns stehen also insgesamt 36 verschiedene Zeichen zur Verfügung(Umlaute uÄ. lassen wir aus).

Ich bin nur auf ein System gekommen, mit dem ich in 120 Stellen beliebig viele Zahlen bis 600 Speichern kann.

Habt ihr eine Idee?
Gibt es schon ein solches System?

Im Internet habe ich auch nichts gefunden.
Man stößt nur immer wieder auf das Hexadezimalsystem mit 16 verschiedenen Zeichen

Hoffentlich ist verständlich was ich meine.
Danke schon im Vorraus.
Monty

[Ludger]

Hi,

Du hast 36 Zeichen und 600 Zahlen mit 1200 moeglichen Werten.

Ich bin nur auf ein System gekommen, mit dem ich in 120 Stellen beliebig viele Zahlen bis 600 Speichern kann.

Da 36*36 ">=" 1200 ist, muesstest Du mindestens ca. 1200 Zeichen (2 Zeichen pro Zahl) benoetigen um die o.g. Zahlen zu speichern.

Oder?

Gruss,
Ludger

[Monty]

Du hast 36 Zeichen und 600 Zahlen mit 1200 moeglichen Werten.

Ich bin mir nicht sicher, ob richtig rübergekommen ist, was ich meine. Es ist auch etwas verzwickt.

Bildlich:
Ich habe 1200 durchnummerierte Eimer, welche entweder voll oder leer sind.
Ich muss nun für bis zu 600 Eimer angeben welche voll sind.
Und das eben mit diesem Code.
Aber es gibt nur Zwei Zustände: Voll/Leer, oder 0/1 oder true/false oder wie auch immer man es nennen will.(boolean eben)

Ich bin nur auf ein System gekommen, mit dem ich in 120 Stellen beliebig viele Zahlen bis 600 Speichern kann.

Ich meine damit, dass ich einen 120 stelligen Code hinschreiben kann, und darin für 600 Eimer der Füllzustand (voll/leer) steht.
Aber das ist noch zu viel Code.

Da 36*36 ">=" 1200 ist, muesstest Du mindestens ca. 1200 Zeichen (2 Zeichen pro Zahl) benoetigen um die o.g. Zahlen zu speichern.

Eben nicht, das macht es ja so spannend (und schwierig).
Mann muss sich eben ein System überlegen.
Ich bin bis zu 5 Eimer pro eine Stelle gekommen. - Zu wenig noch.

Hast du noch eine Idee?

[Der Martin]

Hi monty,

Bildlich:
Ich habe 1200 durchnummerierte Eimer, welche entweder voll oder leer sind.
Ich muss nun für bis zu 600 Eimer angeben welche voll sind.
Und das eben mit diesem Code.
Aber es gibt nur Zwei Zustände: Voll/Leer, oder 0/1 oder true/false oder wie auch immer man es nennen will.(boolean eben)

okay, das macht mir die Sache schon viel klarer!
Also bräuchtest du z.B. eine Sequenz von 1200 Bits, und jedem Eimer ist ein Bit zugeordnet. Da ein Symbol in deiner Codierung (0..9,A..Z) einen Informationsgehalt von rund 5 Bit hat, brauchst du demnach etwas weniger als 1200/5 = 240 Symbole.
Um der einfacheren Codierung willen würde ich übrigens nicht 36 Zustände pro Symbol codieren, sondern nur 32, also (0..9, A..V). Dann hast du exakt 5 Bit pro Symbol, das lässt sich auch leicht programmieren. Und du brauchst für die 1200 Bits insgesamt nur 8 Symbole mehr.

Ich bin nur auf ein System gekommen, mit dem ich in 120 Stellen beliebig viele Zahlen bis 600 Speichern kann.

Ja, aber du brauchst nicht 600, sondern 1200, weil du die Zuordnung noch speichern musst, oder?

Ich meine damit, dass ich einen 120 stelligen Code hinschreiben kann, und darin für 600 Eimer der Füllzustand (voll/leer) steht.

Ja, für 600 Eimer - aber welche 600 von den insgesamt 1200 sind das?

Aber das ist noch zu viel Code.

Die 1200 Bits sind die kompakteste mögliche Darstellung - weniger geht nicht, wenn du bei binär arbeitenden Systemen bleibst. Sonst gehen dir irgendwelche Informationen flöten (wobei du ja auch schon vereinfacht hast, denn zwischen "voll" und "leer" gibt es ja beliebig viele Zwischenstufen).
Du könntest höchstens eine andere Bit/symbol-Codierung wählen. Mit base64 hast du z.B. schon 6 Bits pro Symbol, also 200 statt 240 Symbole.

So long,

Martin

[Henryk Plötz]

Moin,

Ich habe 1200 durchnummerierte Eimer, welche entweder voll oder leer sind.
Ich muss nun für bis zu 600 Eimer angeben welche voll sind.

Also bräuchtest du z.B. eine Sequenz von 1200 Bits, und jedem Eimer ist ein Bit zugeordnet. Da ein Symbol in deiner Codierung (0..9,A..Z) einen Informationsgehalt von rund 5 Bit hat, brauchst du demnach etwas weniger als 1200/5 = 240 Symbole.

Besser noch: Es gibt 'nur' [latex]\sum_{i=0}^{600} {1200 \choose i}[/latex] Zustände, das sind 8410984905079824302015330840595014877024158274870949135297680963877643637315402177123632909067057352671363781743379068645296084024653763822326614966956330778491291690332393014455755965337061172503583702981934979115270951639741950474200318188987117095650680656930343919926849486984939050087235740840919769479112505230663690566284840943309844134177012045163982888, entsprechend 1198.96... Bits. Hmm, dass das so wenig spart erstaunt mich jetzt, wo ich's ausgerechnet habe aber doch ein bisschen.

[Der Martin]

Hallo Henryk,

Besser noch: Es gibt 'nur' [latex]\sum_{i=0}^{600} {1200 \choose i}[/latex] Zustände, das sind 8410984905079824302015330840595014877024158274870949135297680963877643637315402177123632909067057352671363781743379068645296084024653763822326614966956330778491291690332393014455755965337061172503583702981934979115270951639741950474200318188987117095650680656930343919926849486984939050087235740840919769479112505230663690566284840943309844134177012045163982888, entsprechend 1198.96... Bits.

wenn ich deinen Ansatz richtig deute, nutzt er die Voraussetzung, dass _exakt_ 600 Eimer gefüllt sind - raffiniert, aber selbst dann enthält er einen Fehler: Du darfst nicht über (0..600) summieren, sondern nur (0..599) oder (1..600), sonst hast du insgesamt doch 601 volle Eimer vorausgesetzt.

Hmm, dass das so wenig spart erstaunt mich jetzt, wo ich's ausgerechnet habe aber doch ein bisschen.

Mich auch, ehrlich gesagt. Okay, mit einem Iterationsschritt weniger wird der Unterschied deutlicher, dürfte aber nicht gar so viel ausmachen.

So long,

Martin

[Henryk Plötz]

Moin,

wenn ich deinen Ansatz richtig deute, nutzt er die Voraussetzung, dass _exakt_ 600 Eimer gefüllt sind - raffiniert, aber selbst dann enthält er einen Fehler: Du darfst nicht über (0..600) summieren, sondern nur (0..599) oder (1..600), sonst hast du insgesamt doch 601 volle Eimer vorausgesetzt.

Nein. n über k ist die Anzahl der Kombinationen wie ich k Elemente aus n Elementen auswählen kann. 1200 über i ist also wieviele Möglichkeiten es gibt, dass i (fest) Eimer gefüllt sind. Das muss man jetzt aber von i=0 bis 600 aufsummieren, da wir nur wissen, dass maximal 600 Eimer gefüllt sind, aber nicht wieviele Eimer tatsächlich gefüllt sind. (Die Rechnung kann man leicht überprüfen indem man i von 0 bis 1200 laufen lässt, da muss [latex]2^{1200}[/latex] rauskommen.[1])

[1] Huch, jetzt wo ich das gemacht habe fällt mir auf, dass in meiner Schleife ein Durchlauf fehlte und dann sind es 1199.03... Bits.

[Der Martin]

Hallo,

Nein. n über k ist die Anzahl der Kombinationen wie ich k Elemente aus n Elementen auswählen kann. 1200 über i ist also wieviele Möglichkeiten es gibt, dass i (fest) Eimer gefüllt sind. Das muss man jetzt aber von i=0 bis 600 aufsummieren, da wir nur wissen, dass maximal 600 Eimer gefüllt sind, aber nicht wieviele Eimer tatsächlich gefüllt sind.

Stimmt, 0 bis einschließlich 600 sind ja _wirklich_ 601 mögliche Zustände. Okay, dann war ich auf dem Holzweg - aber das ±1-Problem verfolgt uns Informatiker ja auf Schritt und Tritt.

[1] Huch, jetzt wo ich das gemacht habe fällt mir auf, dass in meiner Schleife ein Durchlauf fehlte und dann sind es 1199.03... Bits.

hab ich's nicht gerade gesagt...  ;-)

Ciao,

Martin

[Gunnar Bittersmann]

Besser noch: Es gibt 'nur' [latex]\sum_{i=0}^{600} {1200 \choose i}[/latex] Zustände, das sind […] 1198.96... Bits.

Henryk,
Was hast du da gerechnet?

[latex]\sum_{i=0}^{1200} {1200 \choose i} = \sum_{i=0}^{600} {1200 \choose i} + \sum_{i=601}^{1200} {1200 \choose i} = \sum_{i=0}^{600} {1200 \choose i} + \sum_{i=600}^{1200} {1200 \choose i} - {1200 \choose 600} = 2 \sum_{i=0}^{600} {1200 \choose i} - {1200 \choose 600}[/latex]

folglich

[latex]\sum_{i=0}^{600} {1200 \choose i} = \frac{1}{2} \Biggl(\sum_{i=0}^{1200} {1200 \choose i} + {1200 \choose 600}\Biggr) = \frac{1}{2} \Biggl(2^{1200} + {1200 \choose 600}\Biggr) = 2^{1199} + \frac{1}{2} {1200 \choose 600}[/latex]

Also mehr als 1199 Bits (wenn ich mich nicht vertan habe).

Hmm, dass das so wenig spart erstaunt mich jetzt, wo ich's ausgerechnet habe aber doch ein bisschen.

Allerdings. Haben wir da noch einen Denkfehler?

Live long and prosper,
Gunnar

[Henryk Plötz]

Moin,

Was hast du da gerechnet?

Mich ver. Ich sollte immer dran denken, dass for i in range(0,600) in Python das gleiche wie for(i=0;i<600;i++) in C ist. Wenn man das richtig rechnet kommt man tatsächlich auf knapp über 1199 Bits.

[Gunnar Bittersmann]

Was hast du da gerechnet?
Mich ver.

:-)

… Python … C …

Jaja, die junge Generation, die immer gleich zum Taschenrechner greift, statt sich mit einer Überschlagsrechnung zufrieden zu geben. ;-)

Live long and prosper,
Gunnar

[Gunnar Bittersmann]

Bildlich:
Ich habe 1200 durchnummerierte Eimer, welche entweder voll oder leer sind.
Ich muss nun für bis zu 600 Eimer angeben welche voll sind.

Monty,
Was denn nun, 600 Eimer oder 1200?

OK, wohl 600. Um die Zustände (voll/leer) aller Eimer anzugeben, brauchst du also 600 Bit. Das ist dein Informationsgehalt.

Die 600 Bit kannst du hintereinandergeschrieben als Zahl n interpretieren – aus dem Bereich 0 ≤ n < 2^600 ≈ 4.15E180.

Diese Zahl n kannst du mit den 36 Ziffern 0, 1, …, 9, A, B, …, Z im Zahlensystem mit der Basis 36 darstellen. Dazu brauchst du 117 Stellen, denn 36^116 ≈ 3.4E180 < 4.15E180 < 36^117 ≈ 1.2E182.

Ich meine damit, dass ich einen 120 stelligen Code hinschreiben kann, und darin für 600 Eimer der Füllzustand (voll/leer) steht.
Aber das ist noch zu viel Code.

Ja, genau 3 Zeichen zu viel.

Live long and prosper,
Gunnar

[Der Martin]

Hallo Gunnar,

da haben wir wohl beinahe zeitgleich beinahe dieselbe Situationsanalyse erstellt.

OK, wohl 600.

Ich habe ihn so verstanden, dass es 1200 insgesamt sind, von denen bis zu 600 (oder genau 600?) voll sind.

Diese Zahl n kannst du mit den 36 Ziffern 0, 1, …, 9, A, B, …, Z im Zahlensystem mit der Basis 36 darstellen. Dazu brauchst du 117 Stellen, denn 36^116 ≈ 3.4E180 < 4.15E180 < 36^117 ≈ 1.2E182.

Genau, und mit meiner Annahme von 1200 Bit bin ich auf 233 Stellen gekommen, wobei die letzte nicht mehr vollständig ausgenutzt wird.

Ja, genau 3 Zeichen zu viel.

*g* So ähnlich wollte ich es ihm auch klarmachen.

Schönen Abend noch,

Martin

[Gunnar Bittersmann]

Ich habe ihn so verstanden, dass es 1200 insgesamt sind, von denen bis zu 600 (oder genau 600?) voll sind.

Ja, mir ist auch nicht ganz kla, was er will.

Genau, und mit meiner Annahme von 1200 Bit bin ich auf 233 Stellen gekommen, wobei die letzte nicht mehr vollständig ausgenutzt wird.

Wenn von denn 1200 Eimern aber maximal 600 voll sind, ist der Informationsgehalt um etliches kleiner als 1200 Bit.

Wenn du z.B. die ersten 600 Eimer gefüllt hast (600 Bit auf "1", brauchst du für die restlichen nicht mehr 600 Bit "0", sondern nur noch eine kurze Sequenz, die besagt: alle weiteren leer.

Das heißt, es sind deutlich weniger als 233 Ziffern aus dem 36er System notwendig.

Live long and prosper,
Gunnar

[wahsaga]

hi,

Wenn von denn 1200 Eimern aber maximal 600 voll sind, ist der Informationsgehalt um etliches kleiner als 1200 Bit.
Wenn du z.B. die ersten 600 Eimer gefüllt hast (600 Bit auf "1", brauchst du für die restlichen nicht mehr 600 Bit "0", sondern nur noch eine kurze Sequenz, die besagt: alle weiteren leer.

dafür erhöht sich der verwaltungsaufwand.

Das heißt, es sind deutlich weniger als 233 Ziffern aus dem 36er System notwendig.

dein vorschlag geht ja schon mehr in richtung komprimierung.

btw: wenn die ersten 600 "am stück" gefüllt sind, bietet sich da natürlich ebenfalls "abkürzungspotential".

gruß,
wahsaga

[Der Martin]

Hi,

Wenn du z.B. die ersten 600 Eimer gefüllt hast (600 Bit auf "1"), brauchst du für die restlichen nicht mehr 600 Bit "0", sondern nur noch eine kurze Sequenz, die besagt: alle weiteren leer.

Ah, das ist ein guter Hinweis. Aber das geht dann schon in Richtung Kompressionsalgorithmen, in diesem Fall eine Art RLE. Auch das Abschneiden eines Strings mit der Vorschrift "Alle fehlenden Elemente sind 0" würde ich im weitesten Sinne als RLE-Verfahren einstufen.

Das heißt, es sind deutlich weniger als 233 Ziffern aus dem 36er System notwendig.

Nur unter guten Voraussetzungen. Ein verlustfreies Kompressionsverfahren (wie z.B. RLE oder LZW) kann nur dann wirklich eine Datenreduktion erreichen, wenn es innerhalb der Nutzdaten gewisse Regelmäßigkeiten erkennt. Sind die Daten aber statistisch zufällig verteilt, sind derartige Algorithmen kaum nützlich (schon mal versucht, eine JPG-Datei zu zippen? Es bringt normalerweise nichts). Man muss deshalb im ungünstigsten Fall doch von der maximalen unkomprimierten Datenmenge ausgehen.

So long,

Martin

[wahsaga]

hi,

Sind die Daten aber statistisch zufällig verteilt, sind derartige Algorithmen kaum nützlich (schon mal versucht, eine JPG-Datei zu zippen? Es bringt normalerweise nichts).

ja, weil jpeg selbst bereits einen sehr starken kompressionsalgorithmus verwendet - und dann ist weitere kompression idR. wenig erfolgreich.

gruß,
wahsaga

[Der Martin]

Hallo,

Sind die Daten aber statistisch zufällig verteilt, sind derartige Algorithmen kaum nützlich (schon mal versucht, eine JPG-Datei zu zippen? Es bringt normalerweise nichts).

ja, weil jpeg selbst bereits einen sehr starken kompressionsalgorithmus verwendet - und dann ist weitere kompression idR. wenig erfolgreich.

Eben - die Aussagen sind zwar nicht äquivalent, laufen aber auf dasselbe Ergebnis hinaus: Solange eine gegebene Datenmenge gewisse Regelmäßigkeiten aufweist (Periodizität, mehrfache Wiederholung bestimmter Muster, etc.), kann man sie ohne Informationsverlust weiter komprimieren.
Eine ideale Kompression erzeugt daher eine Datenmenge, in der alle Zustände (z.B. alle Bytewerte) gleich häufig und in ihrem Kontext gleich wahrscheinlich sind. Die JPEG-Kompression kommt diesem Ideal sehr nahe.

Schönen Abend noch,

Martin

[Gunnar Bittersmann]

Das heißt, es sind deutlich weniger als 233 Ziffern aus dem 36er System notwendig.

Ich nehme das „deutlich“ zurück.

2^1199 ≈ 8.61E360; 36^232 ≈ 1.15E361

Verdammt, reicht nicht.
Ich nehme das „weniger als 233 Ziffern“ zurück.

Wenn man mit Codierungen variabler Länge arbeitet, kommt man aber im Mittel unter 233. ;-)

Live long and prosper,
Gunnar

[Gunnar Bittersmann]

2^1199 ≈ 8.61E360; 36^232 ≈ 1.15E361
Verdammt, reicht nicht.

So’n Quatsch. Reicht ja doch.

Ich nehme das „weniger als 233 Ziffern“ NICHT zurück. 232 tun’s auch.

Mit variabler Codelänge im Mittel sogar noch weniger. Da überleg ich mir’s glatt mit dem „deutlich“ nochmal. ;-)

Live long and prosper,
Gunnar

[Henryk Plötz]

Moin,

Ich nehme das „deutlich“ zurück.

2^1199 ≈ 8.61E360; 36^232 ≈ 1.15E361

Verdammt, reicht nicht.

Das reicht (auf die Potenz schauen). Tatsächlich sind es 231.92... Zeichen zur Basis 36.

Wenn man mit Codierungen variabler Länge arbeitet, kommt man aber im Mittel unter 233. ;-)

"Kommt drauf an." Das da oben ist der Informationsgehalt bei angenommener Gleichverteilung. Eine Kodierung die (bei Gleichverteilung) im Erwartungswert auf unter die angegebene Grenze kommt, ist keine, sondern ein Fehler[1]. Wenn die Ereignisse nicht gleichverteilt sind könnte man aber was reissen, ja.

[1] In comp.compression immer wieder gerne gesehen wenn einer eine tolle neue Kompressionsmethode 'erfunden' hat und behauptet n Bits mit n-1 Bits ausdrücken zu können. ;-)

[Daniel Thoma]

Hallo Monty,

Das ist natürlich ein ganz anderes Problem als das beschriebene.
Erst mal muss man überlegen, wie viel mögliche Zustände Du speichern können musst.
Du musst für 0 bis 600 volle Eimer die Anzahl der Möglichkeiten wie die unter 1200 Eimern verteilt sind, speichern können.
Also summe von 0 bis 100 (1200 über 0).
Davon der Logarithmus zur Basis 36 ist ca. 231.92
Für 1200 Eimer käme man auf 232.11
Ich denke, es lohnt sich nicht, wegen einer Stelle, die Du evtl. einspaaren könntest, nach einem besseren Algortihmus zu suchen.

Grüße

Daniel

[Detlef G.]

Hallo Monty

Ich habe 1200 durchnummerierte Eimer, welche entweder voll oder leer sind.
Ich muss nun für bis zu 600 Eimer angeben welche voll sind.
Und das eben mit diesem Code.
Aber es gibt nur Zwei Zustände: Voll/Leer, oder 0/1 oder true/false oder wie auch immer man es nennen will.(boolean eben)

Es gibt maximal 600 volle Eimer.
Ich würde die Nummern der vollen Eimer sortieren, die größte Nummer zuerst.

(Ich hoffe, ich habe mich nicht vertan)
Nun gehen wir die gefüllten Eimer der Reihe nach durch.
  1. voller Eimer 0 oder einer von 1200 ->   Eimernummer * 1200
  2. voller Eimer 0 oder einer von 1199 -> + Eimernummer * 1199
  3. voller Eimer 0 oder einer von 1198 -> + Eimernummer * 1198
  ...
600. voller Eimer 0 oder einer von 601  -> + Eimernummer * 1198

ergibt maximal 504540100 oder 8ce1ms

Auf Wiederlesen
Detlef

[Detlef G.]

Hallo alle

(Ich hoffe, ich habe mich nicht vertan)

Ja, ich habe mich vertan.

Vergesst, was ich geschrieben habe.

Auf Wiederlesen
Detlef

[Sven Rautenberg]

Moin!

Bildlich:
Ich habe 1200 durchnummerierte Eimer, welche entweder voll oder leer sind.
Ich muss nun für bis zu 600 Eimer angeben welche voll sind.
Und das eben mit diesem Code.

Ist dabei die Information, für welche Eimer du den leer/voll-Zustand angibst, wichtig? Soll heißen: Wäre es ok, wenn du immer für alle 1200 Eimer deren Füllzustand angibst, oder ist es wichtig, dass du nur für die Eimer 2, 5, 19, 20, 21, 29,... den Füllzustand angibst.

Darüber hinaus ist noch interessant, wieviele Eimer durchschnittlich denn tatsächlich angegeben werden, denn logischerweise kann es sich bei nur wenigen aus 1200 Eimern lohnen, einfach nur die wenigen gefüllten oder nicht gefüllten aufzuzählen und den Rest als das Gegenteil zu betrachten. Die Info "Eimer 2 ist voll (und der Rest ist leer)" läßt sich eben wesentlich kürzer darstellen, als wenn man sämtliche Eimerinhalte aufzählen würde.

Aber es gibt nur Zwei Zustände: Voll/Leer, oder 0/1 oder true/false oder wie auch immer man es nennen will.(boolean eben)

Wenn es wichtig ist, ob der Eimer existiert oder nicht, und nur bei existierenden Eimern der Füllzustand wichtig ist, dann haben wir keinen binären Wert je Eimer mehr, sondern es werden mehr als 1 Bit erforderlich (wobei es nicht 2 Bit sind, weil der Füllzustand eines nicht existierenden Eimers ja nicht dargestellt wird, sondern nur 3 Zustände - keine Ahnung, ob sich das zu 1,5 Bit berechnet, das mögen die Informationstheoretiker ausrechnen).

Und wo wir gerade bei Informationstheorie sind: man kann natürlich auch noch zusätzliche Redundanz in den zu erstellenden Code einbauen, um zumindest Fehler erkennen oder gar korrigieren zu können.

Ich bin nur auf ein System gekommen, mit dem ich in 120 Stellen beliebig viele Zahlen bis 600 Speichern kann.

Eine weitere Frage ist, welche Darstellungsart der gefundenen Daten du dir vorstellst. Was spricht beispielsweise gegen eine vollständig binäre Darstellung mit Bytes von 0 bis 255 - das würde die Anzahl der Zeichen sehr verkürzen können. Aber auch eine Konvertierung einer derartigen Byte-Kombo mittels base64 würde zu einer zwar längeren, aber als Textstring darstellbaren Zeichenkombination führen, die vermutlich immer noch kürzer ist, als deine Basis-36-Zahl, weil einfach mehr mögliche Zeichen genutzt werden.

- Sven Rautenberg

[Henryk Plötz]

Moin,

(wobei es nicht 2 Bit sind, weil der Füllzustand eines nicht existierenden Eimers ja nicht dargestellt wird, sondern nur 3 Zustände - keine Ahnung, ob sich das zu 1,5 Bit berechnet, das mögen die Informationstheoretiker ausrechnen).

Aber bitte doch: [latex]\log_2 3 = 1.584\ldots[/latex]

Eine weitere Frage ist, welche Darstellungsart der gefundenen Daten du dir vorstellst. Was spricht beispielsweise gegen eine vollständig binäre Darstellung mit Bytes von 0 bis 255 - das würde die Anzahl der Zeichen sehr verkürzen können.

Naja, das kann man dann immer noch klären. Erstmal geht es darum die Aufgabe in Bit zu lösen und eine passende Abbildung auf einen Bitstring zu finden. Den dann in ein beliebiges Format zu einer beliebigen Basis zu bringen ist anschließend direkt trivial. Die untere Schranke hatten wir nebenan zu 1199 (komma ein bisschen was) Bits bestimmt und kürzer geht es ohne weitere Informationen (sowas wie "In 90% aller Fälle sind es nicht mehr als 10 Eimer" wäre zum Beispiel toll und müsste den Erwartungswert der optimalen Codierung auf 1195.7... Bits senken wennichmichnichtwiederverrechnethabe) nicht.

[Henryk Plötz]

Moin,

sowas wie "In 90% aller Fälle sind es nicht mehr als 10 Eimer" wäre zum Beispiel toll und müsste den Erwartungswert der optimalen Codierung auf 1195.7... Bits senken wennichmichnichtwiederverrechnethabe

Denkfehler. Natürlich ist das korrekte Ergebnis 192.782... Bits:
[latex]e1 := \sum_{i=0}^{10}{1200 \choose i}[/latex], [latex]e2 := \sum_{i=11}^{600}{1200 \choose i}[/latex]
[latex]H = 0.9 \log_2 \frac{e1}{0.9} + 0.1 \log_2 \frac{e2}{0.1} = 192.782\ldots[/latex]

(Herleitung: Die Wahrscheinlichkeiten für das Auftreten sind [latex]p_i = \frac{0.9}{e1}[/latex] für [latex]1 \leq i \leq e1[/latex] (Wahrscheinlichkeit 90% dafür, dass eine Kombination mit 10 oder weniger Eimern auftritt, und davon gibt es [latex]e1[/latex] Stück) und [latex]p_i = \frac{0.1}{e2}[/latex] sonst.

Entropie = [latex]-\sum_{i=1}^{e1+e2} p_i \log_2 p_i[/latex] = [latex]-\sum_{i=1}^{e1} p_i \log_2 p_i -\sum_{i=1}^{e2} p_{e1+i} \log_2 p_{e1+i}[/latex] = [latex]-\sum_{i=1}^{e1} \frac{0.9}{e1} \log_2 \frac{0.9}{e1} -\sum_{i=1}^{e2} \frac{0.1}{e2} \log_2 \frac{0.1}{e2}[/latex], was sich zu obiger Formel vereinfacht.)

[wahsaga]

hi,

Man stößt nur immer wieder auf das Hexadezimalsystem mit 16 verschiedenen Zeichen

das besteht aus 0-9 plus a-f = sechzehn "ziffern". bei umrechnungen von/ins dezimalsystem werden deshalb 16er-potenzen benutzt.

also warum nicht analog vorgehen?
0-9 plus a-z sind 36 "ziffern", bei umrechnungen also analog mit 36er-potenzen arbeiten.

gruß,
wahsaga

[Christian Kruse]

你好 Monty,

Aufgabe ist es im Zahlenbereich von 1 bis 1200 bis zu 600 Zahlen in einem
Code bestehend aus Buchstaben(A-Z) und Zahlen (0-9) zu Speichern, und
wieder rückrechnen zu können.

Du möchtest also Dezimal-Ziffern ins 36er-System und wieder zurückwandeln
können. Dann mach das doch. Beispiel-Code für eine Von-Hand-Lösung in Perl:

  
sub to_dec36 {  
  my $num   = shift;  
  my @chars  = (0..9,'A'..'Z');  
  my $a      = 1;  
  my $result = '';  
  
  $a *= 36 while $num >= $a;  
  
  while($a != 1) {  
    $a    /= 36;  
  
    $b     = $num / $a;  
    $num %= $a;  
  
    $result .= $chars[$b];  
  }  
  
  return $result;  
}  
  
sub from_dec36 {  
  my $num    = shift;  
  my @nums   = split // => $num;  
  my @chars  = (0..9,'A'..'Z');  
  
  my $i3     = length($num) - 1;  
  my $i2;  
  my $base;  
  my $result = 0;  
  
  for(my $i=0;$i<length($num);$i++) {  
    $base = 36 ** ($i3 - $i);  
  
    for($i2=0;$i2<@chars;$i2++) {  
      last if $chars[$i2] eq $nums[$i];  
    }  
  
    $base = $base * $i2;  
    $result = $result + $base;  
  }  
  
  return $result;  
}  
  
my $num   = 20;  
my $num36 = to_dec36($num);  
my $num10 = from_dec36($num36);  
  
print "num: $num, num36: $num36, num10: $num10\n";  

Ich habe absichtlich auf Perl-Rafinessen verzichtet, damit du es 1:1 in
PHP, C oder sonsteine Sprache übertragen kannst.

再见,
 克里斯蒂安

[Gunnar Bittersmann]

Du möchtest also Dezimal-Ziffern ins 36er-System und wieder zurückwandeln
können. Dann mach das doch. Beispiel-Code für eine Von-Hand-Lösung in Perl:

sub to_dec36 {

[snip]

Ich habe absichtlich auf Perl-Rafinessen verzichtet, damit du es 1:1 in
PHP, C oder sonsteine Sprache übertragen kannst.

Hi,
Die Übertragung in JavaScript ist übrigens denkbar einfach:

function to_dec36(n) {  
  return n.toString(36)  
}

;-)

Live long and prosper,
Gunnar

[Gunnar Bittersmann]

function to_dec36(n) {

return n.toString(36)
}

  
Wenn bei Riesenzahlen toString() nicht mehr bis zur letzten Stelle genau rechnet, muss man die Funktion allerdings neu implementieren. Argl.  
  
Live long and prosper,  
Gunnar

-- 
„Weisheit ist nicht das Ergebnis der Schulbildung, sondern des lebenslangen Versuchs, sie zu erwerben.“ (Albert Einstein)

[Monty]

Du möchtest also Dezimal-Ziffern ins 36er-System und wieder zurückwandeln
können. Dann mach das doch. Beispiel-Code für eine Von-Hand-Lösung in Perl:

sub to_dec36 {
  my $num   = shift;
  my @chars  = (0..9,'A'..'Z');
  my $a      = 1;
  my $result = '';

$a *= 36 while $num >= $a;

while($a != 1) {
    $a    /= 36;

$b     = $num / $a;
    $num %= $a;

$result .= $chars[$b];
  }

return $result;
}

sub from_dec36 {
  my $num    = shift;
  my @nums   = split // => $num;
  my @chars  = (0..9,'A'..'Z');

my $i3     = length($num) - 1;
  my $i2;
  my $base;
  my $result = 0;

for(my $i=0;$i<length($num);$i++) {
    $base = 36 ** ($i3 - $i);

for($i2=0;$i2<@chars;$i2++) {
      last if $chars[$i2] eq $nums[$i];
    }

$base = $base * $i2;
    $result = $result + $base;
  }

return $result;
}

my $num   = 20;
my $num36 = to_dec36($num);
my $num10 = from_dec36($num36);

print "num: $num, num36: $num36, num10: $num10\n";

>   
> Ich habe absichtlich auf Perl-Rafinessen verzichtet, damit du es 1:1 in  
> PHP, C oder sonsteine Sprache übertragen kannst.  
  
Vielen Dank für die Mühe die du dir gemacht hast!  
  
Wenn ich dich richtig verstanden habe, dann werden jetzt Dezimal-Ziffern ins 36er-System (und umgekehrt) umgewandelt.  
Das heißt, dass ich anstelle von "1295" "ZZ" schreibe oder an Stelle von "36" "10" usw. damit würde ich ab den dreistelligen Zahlen nur zwei Stellen schreiben müssen.  
  
Wenn ich jetzt aber 3,5,14,15 darstellen möchte, dann muss ich trotzdem 3,5,E,F schreiben.  
Ich möchte aber so wenig wie möglich schreiben und so viele Zahlen wie möglich damit darstellen.  
  
 1,3,4,5,8,11,14,15,17,20 wären nach meinem System dann 4DGO nur vier anstelle von zehn Zeichen.  
So kann ich 600 Zahlen mit 120Zeichen darstellen, das ist mir aber noch zu viel.  
Die Zahlen müssen quasi verschlüsselt werden.  
Hast du noch eine Idee wie ich viele Zahlen mit wenig Zeichen darstellen kann?  
  
Danke nochmal,  
Monty

[Bio]

Sup!

Wenn die zu kodierenden Zeichen sehr ungleich verteilt sind (z.B. keine 800, viele 3), dann könntest Du ggf. eine Komprimierung nutzen.

Gruesse,

Bio

[Frank (no reg)]

Hi,

mal angenommen, du schreibst mit deinem System die Zahlen

3, 5, 14, 15    um in    3, 5, E, F   und hängst diese Ausgabe dann zusammen zu      35EF    ?

Woran willst du erkennen, dass nicht beim Zurückkodieren 35, 35E oder 5EF zurück in eine Dezimal-Zahl übersetzt werden?

Dann hättest du genau gar nichts gewonnen?!?

Ansonsten könntest du jeder Position eine 2er Potenz zuordnen ...

3 wird zu 4, 5 zu 16, 14 zu 8192, 15 zu 16384  ... diese dann zusammenaddieren zu 24596 und das in das 36-er System hin und herrechnen. Die Elemente von Pos 1 (2^0) bis Pos 14 (2^13) würden zusammen nie 16384 sondern nur 16383 ergeben, wenn ich mich jetzt nicht verrechnet habe. Ist 2^600 größer als 36^117?  Aber da wären wir wieder bei 117 Stellen?

Gruß, Frank

[Daniel Thoma]

Hallo Monty,

Den Tip mit dem 36er-Zahlensystem hast Du ja schon bekommen.
Der kürzest mögliche Code ist das aber noch nicht, da 1200 keine 36-Potenz ist. Die nächstgrößere wäre 1296, Du verschenkst also etwas Platz.

Optimalerweise geht man folgendermaßen vor:
Benötigte Stellen: s = aufrunden(#zahlen * log_36(1200));
Alle Zahlen z_i um eins erniedrigen (da Du keine 0 speichern willst)
Zahlen z_i so aufsummieren: S = summe von 0 bis i (z_i * 1200^i)
S ins 36er-System umrechnen und den Code vorn mit Nullen auf s Stellen auffüllen.

Decodieren:
Aus der Länge des Codes die größte, beim Speichern verwendete 36 Potenz bestimmen: #zahlen = abrunden(s / log_36(1200));
Berechnent der z_i:
for i from #zahlen - 1 to 0 do
  z_i = abrunden(s / 1200^i);
  s = s % 1200^i;
od;
Anschließend noch alle Zahlen wieder um eins erhöhen.
Für 600 Zahlen brauchst Du so nur 1188 statt 1200 Stellen.
Fragt sich natürlich, ob es das Wert ist ;-)

Grüße

Daniel

[Hans]

Hallo Monty,

mach's doch so:

1 = "AA"
2 = "AB"
3 = "AC"
..
26 = "AZ"
27 = "A0"
28 = "A1"
..
36 = "A9"
37 = "BA"
..
1296 = "99"

etc.

Gruß

Hans