Das Deutsche Casio-Taschenrechner Forum wurde zum 31.12.2013 geschlossen und kann weiterhin als Nachschlagewerk verwendet werden.
Wer mehr erfahren möchte: Ein sehr guter Beitrag von Elias

HowTo: Komprimierung und Zeichenketten

Hilfe beim Programmieren in Casio Basic.

HowTo: Komprimierung und Zeichenketten

Beitragvon cfxm » So 6. Sep 2009, 02:06

Vor einiger Zeit habe ich mit jemandem per PM über Komprimierung und deren Anwendbarkeit bei Zeichenketten diskutiert. Damit diese doch recht nützliche Unterhaltung nicht verloren geht, will ich sie mal ins Forum stellen - allerdings wird es hier nur eine etwas gekürzte Fassung der Antworten von mir geben.

Angefangen hat alles damit, dass sich mein Gesprächspartner an einem Programm zur Verarbeitung von Strings probiert hat (für OS 2.00-Nutzer natürlich uninteressant) - da wollte ich selbstverständlich ein paar Tipps geben. ;-) Die Behauptung, dass man bei 26 Buchstaben (Werte von 0 bis 25), unter Hinzunahme von Imaginärzahlen als zusätzlichen Speicherplatz, 20 Zeichen in einer Variablen unterbringen kann, sollte sich allerdings als zu optimistisch herausstellen.

Hier nun meine Antwort auf die Frage, wie das denn gehen soll:
[...] und 20 Zeichen in eine Variable quetschen, ist auch nicht so ratsam. Der Rechner rundet nämlich gelegentlich die letzten 5 von 15 Stellen und dadurch ist die Dekomprimierung natürlich fehlerhaft. [...] Wenn man allerdings 10 Stellen nicht überschreitet, dürften keine weiteren Fehler auftreten. Das reduziert natürlich die Anzahl von 20 Zeichen auf 14 (für Werte von 0-25).
Nun zum Algorithmus: Für wenige Werte sollte man weiterhin z. B. die Komma-Methode verwenden, d. h. zwei Werte werden mittels Komma getrennt (xx.yy) und können später über Int() und Frac() wieder extrahiert werden. Auch kann man das Komma einfach verschieben (xxxyyyzzz/1000^2 => Int Ans => xxx; etc.). Basierend auf letzterem kann man natürlich statt der Basis 1000 auch eine andere verwenden - wie z. B. 8 für oktal oder 16 für hexadezimal und viele weitere. Dabei ist nur zu beachten, dass alle Werte nicht größer-gleich der Basis sein dürfen, bzw. dass der Gesamtwert (z. B. xxxyyyzzz) kleiner als 1e+10 ist (Wegen der Rechengenauigkeit).
Kommen wir zum Code: Wobei X für die/den Basis/Grenzwert steht, Y die Anzahl der Werte angibt, die in den Gesamtwert Z (Kleiner als 1e+10) gespeichert werden (Imaginärzahlen speichern stets die doppelte Anzahl (2Y)), List 1 die Werte zum Komprimieren und List 2 die Werte nach der Dekomprimierung enthält.

Code: Alles auswählen
Komprimieren:
X+1->X // Damit man den Grenzwert selbst verwenden kann
Sigma(List 1[I+1]X^I,I,0,Y-1)+Sigma(List 1[I+Y+1]X^I,I,0,Y-1)i->Z
/* Einer+Zehner+...+(Einer+Zehner+...)*Imaginärzahl */

Beispiel:
X=25, Y=7, Dim List 1=14 und List 1=Fill(25,List 1) liefert 8031810175+8031810175i

Code: Alles auswählen
Dekomprimieren:
For 1->I To Y
ReP Z-XInt (ReP Z/X)->List 2[I] // Modulo=Letzte Stelle (ReP)
ImP Z-XInt (ImP Z/X)->List 2[I+Y] // Modulo=Letzte Stelle (ImP)
Int (ReP Z/X)+Int (ImP Z/X)i->Z // Letzte Stellen streichen
Next
/* ReP=Realteil; ImP=Imaginärteil */

Wenn man jetzt nicht mit Imaginärzahlen arbeiten möchte, dann entfernt man beim Komprimieren einfach den Teil ...+Sigma()i und beim Dekomprimieren die komplette Zeile (ImP), ändert ReP Z zu Z und verkürzt die vorletzte Zeile zu Int (Z/X)->Z. [...]

OS 2.00-Nutzern würde ich übrigens empfehlen die neuen Operatoren zur Bestimmung des Restes und des Ganzzahlquotienten zu verwenden:
Code: Alles auswählen
For 1->I To Y
ReP Z Rmdr X->List 2[I]
ImP Z Rmdr X->List 2[I+Y]
ReP Z Int/ X+(ImP Z Int/ X)i->Z
Next

Leider war das alles wohl gleich ein bisschen kompliziert und es kamen ein paar Fragen zurück:
Ich habe außerdem noch nie was von Sigma gehört

Sigma() ist einfach das Summenzeichen und findet sich normalerweise unter [OPTN]/[F4]/[F6]/[F3].
[...] aber ein Zeichen belegt doch 2 Stellen, oder?

Das stimmt so... wenn man im Dezimalsystem denkt.
Ich erkläre dir das mal am Hexadezimalsystem. Dieses System nutzt 16 Ziffern von 0 bis F, dabei entspricht A dem dezimalen Wert 10, B 11, C 12, D 13, E 14 und F 15. Daraus folgt, dass zweistellige dezimale Zahlen nicht zwangsläufig auch zwei Stellen zur Darstellung in einem anderen Stellenwertsystem brauchen.
Außerdem können wir dezimale Zahlen auch als ...+Tausender*10^3+Hunderter*10^2+Zehner*10^1+Einer*10^0 schreiben und wenn wir z. B. die hexadezimale Zahl 89AB nehmen, dann können wir diese damit ganz leicht in eine Dezimalzahl umwandeln, nämlich 8*16^3+9*16^2+10*16^1+11*16^0=35243. Wir nutzen bei der "Komprimierung" also einfach ein anderes Stellenwertsystem [...]

Beispiel:
Wir wollen Werte von 0 bis 19, die jeweils zur Speicherung nur eine Ziffer brauchen? Dann nehmen wir doch das Zwanzigersystem mit Ziffern von 0 bis J. Nun verwenden wir einfach mal die fünf Werte {3,7,10(A),13(D),17(H)} und speichern diese dezimal in Liste 1. Die daraus resultierende Zahl 37ADH wird zur "Komprimierung" nun in eine einzige Dezimalzahl umgewandelt: 3*20^4+7*20^3+10*20^2+13*20^1+17*20^0=540277. Wichtig ist, dass der generierte Wert kleiner als 1e+10 ist.

Die "Dekomprimierung" wandelt nun den Wert 540277 wieder in die Zahl 37ADH um, also {3,7,10,13,17}. Dazu muss man wissen, dass wenn man z. B. die Dezimalzahl 1234 durch 10 teilt, man immer die letzte Stelle als Rest erhält. Wir teilen nun einfach 540277 durch 20 und erhalten als Rest 17(H), kürzen den Nachkommateil und teilen diese Zahl wieder durch 20 und erhalten als Rest 13(D). Das geht so lange bis man wieder fünf Werte hat. [...]

Als nächstes probiert man das Ganze natürlich auch mal mit eigenem Code:
[...] in deinem bsp kam ich nicht auf 17 sondern auf 0.85 hinter dem komma raus.

Wenn man 540277 durch 20 teilt, ist nicht 85 der Rest.
Den Rest kann man nämlich nur auf zwei Arten berechnen: 20*Frac (540277/20) oder 540277-20*Int (540277/20).
Nach ein bisschen experimentieren bin ich dann auf folgendes gekommen [...]

Der Algorithmus sah bei mir mal ähnlich aus, aber ich finde den jetzigen besser.
Sofern man sicherstellt, dass die höchstwertige Ziffer (die, die ganz links steht) nicht 0 ist oder es egal ist, wie viele Werte im Gesamtwert gespeichert sind (feste Listengröße), kann man auch einfach eine While()-Schleife verwenden.

Code: Alles auswählen
1->I
While Z
Z%X->List 2[I] // Den Rest-Operator gibt's so leider nicht...
Int (Z/X)->Z
I+1->I
WhileEnd

[...]
Um eine höhere geschwindigkeit zu erreichen verzichte ich beim schreiben darauf, die getkeys umzuwandeln.

Warum? Geht doch ganz einfach (von Caspro):
If you want to convert Getkey codes for keys 1-9 into the actual number use:
0.1Getkey
2-Ans+31Frac Ans->G

Or to also detect the number 0 then use:
0.1Getkey
2-Ans+31Frac Ans+2(Ans=7.1)->G

Also in reverse to convert numbers 1-9 into Getkey codes use:
?->N
(N-1)/3 ;don't use reciprocal or get rounding errors
72+Ans-31Frac Ans->G

If you want to take into account the number 0 as well then use:
?->N
(N-1)/3 ;don't use reciprocal or get rounding errors
72+Ans-31Frac Ans-11(Not N)->G

To convert Getkey codes for letters A~Z into numbers 1~26 use:
0.1Getkey
6-10Frac Ans->R
8-Int Ans+5R+R(R<3)->G


Hierauf folgte nichts Wesentliches mehr.

Nun werden sich sicher noch einige fragen, wie man Strings auf älteren Rechnern denn überhaupt eingeben soll. Hier folgender Vorschlag: Ich würde einfach eine kleine Anzeige programmieren und dann alle Tasten für die Buchstaben abfragen und abspeichern (vorher eventuell, wie von Caspro erklärt, noch konvertieren). Wenn man nun die Eingabe mit einem bestimmten String vergleichen will, nutzt man hierzu entweder eine oder mehrere Variablen (auf maximal 14 Zeichen begrenzt) oder vergleicht die gesamte Eingabeliste (als unkomprimierter String) einfach mit einer anderen Liste.

Das lässt sich z. B. durch folgende Anweisungen realisieren:
Code: Alles auswählen
{5,24,9,20,0} // String "EXIT"
Dim List Ans->J
Seq(List Ans[I-(I>J)(I-J)],I,1,Dim List 1,1)
If Dim List 1=Sum (List 1=List Ans)
Then Stop
IfEnd

In diesem Zusammenhang auch recht lesenswert: viewtopic.php?f=59&t=3685

Ich hoffe, dass ich das einigermaßen gut erklären konnte. Seit OS 2.00 sind Strings zwar kein Thema mehr, aber zum sparsameren Umgang mit Speicherplatz oder zur Umrechnung in andere Stellenwertsysteme kann man dieses HowTo sicher noch gebrauchen. ;-)
cfxm
 
Beiträge: 739
Registriert: Mi 1. Apr 2009, 19:39

Re: HowTo: Komprimierung und Zeichenketten

Beitragvon cfxm » Di 19. Okt 2010, 20:16

Hier ein einfaches Testprogramm ohne Imaginärzahlen und für GTR mit OS 2.00:
Code: Alles auswählen
ClrText
ClrList 2
"List="?->List 1
Dim List 1->Y
Int Abs List 1->List 1
1+Max(List 1)->X
Sigma(List 1[I+1]X^I,I,0,Y-1)->Z
For 1->I To Y
Z Rmdr X->List 2[I]
Z Int/ X->Z
Next
List 2
cfxm
 
Beiträge: 739
Registriert: Mi 1. Apr 2009, 19:39


Zurück zu Casio Basic (Alle Modelle, die dies unterstützen)

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste