Verfahren zum Komprimieren einer SMS

S

softrunner

0
Ich beschäftige mich zur Zeit damit, wie man möglichst effektiv eine SMS Nachricht komprimieren kann. Mir ist dazu folgendes eingefallen: Ich nutze einfach die Sonderzeichen um häufig vorkommende Zeichenfolgen damit zu codieren. So .. ersetze ich z.b. jedes "er" durch ein "@". Ich hab mal eine kleine Liste bestehend aus 31 2-stelligen Zeichenfolgen erstellt und das ganze am PC simuliert. Damit lassen sich schon relativ gute Ergebnisse erzielen. In einem zweiten Durchgang könnte man natürlich das "er" nutzen, um damit andere,längere Zeichenfolgen zu codieren. Ich weiss jedoch noch nicht ,ob das in der Praxis Sinn macht. Diese Methode hat allerdings 2 Nachteile: 1. Sie ist an die Eigenarten der deutschen Sprache gebunden. 2. Sonderzeichen können nicht mehr genutzt werden.

Den 2. Punkt könnte man vielleicht lösen, indem man das "er" nutzt, um damit das Sonderzeichen zu codieren. Geht natürlich nur wenn man zu Grunde legt, dass Sonderzeichen viel seltener in der SMS vorkommen als Buchstaben. Die Zeichen .?,! sind übrigens komplett von dem Verfahren ausgeschlossen und somit verwendbar. Für weitere Anregungen und Ideen wäre ich dankbar. Ich erwarte hier keine fertigen Quellcodes, sondern nur Beschreibungen von Verfahren oder Gedankenanstösse.

mfg softrunner
 
hm, es sind vor allem die längeren worte, die eine sms schnell zuenden gehen lassen. daher würde ich bei längeren wiorten einfach die letzte(n) silbe(n) wegschneiden, aufgrund der länge des wortes sollte die bedeutung unmissverstädnlich bleiben...
 
Es geht schon darum einen Algorithmus zu entwickeln, der die SMS ohne Verlust komprimiert. Beim Empfänger wird die SMS dann wieder dekomprimiert. D.h. die SMS muss im komprimierten Zustand nicht lesbar sein. Ich codiere "en" mit einem einstelligen Symbol, wobei das Wort "letzte" bei mir jetzt eher so "letz*n" codiert werden würde. Liegt einfach daran, dass der Algorithmus zuerst "te" sieht.
Aber vielleicht gibt es ja auch einen komplett anderen Ansatz...


mfg, sofrunner
 
könnte man bei sms nicht auch eine direkte komprimierung einsetzen ?
oder "sondersonderzeichen" benutzen (unicode) und damit auch wieder dekomprimiert wird müssten beide handys das prog haben, auf symbian os handys könnte man das afaik noch recht einfach realisieren (wenn die unicode haben) aber auf anderen ?
 
Willst du codieren oder komprimieren?
Also ich rate dir z.b. X-OR zu codieren.

Dazu ein c-beispiel:

...
char sms[100];
int sms_len;
sms = get_sms(&sms_len); // irgendwas...
for(i = 0; i < sms_len; i++)
sms = sms ^ geheimzahl;
send_sms(sms, sms_len);
...

Zum Komprimieren kann sagen, dass deine Methode ziemlich schlecht ist, weil wenn ich z.b. folgende sms schreibe:
hallo mail an aaa@bbb.com
kommt nachher raus:
hallo mail an aaaerbbb.com

==> Komprimieren ist wesentlich schwiriger. Du musst die sms nach regelmäßigkeiten durchsuchen und eine header proggen, in dem du diese speicherst. Da eine sms meistens ziemlich klein ist, macht das nicht wirklich sinn und ist außerden ziemlich kompliziert. -> bz2 verfahren.
 
ach noch was: decodieren geht natürlich genauso.
^ steht für logisches X-OR (aber das weist du wahrscheinlich).
Es gilt:
b = a ^ geheimzahl
a = b ^ geheimzahl

Also ist nochmal X-OR-EN die dekokodierungsmethode.
 
wenn man den header für die meisten verkommenden silben im programm selber speichert dann kann man sich sicher was sparen. ich versuche morgen mal in pseudo code ein beispiel zu bauen ^^
 
Es geht darum ein SMS-Programm zu schreiben, welches das Versenden von längeren SMS ermöglicht. Also gilt es diese zu komprimieren. Ich habe eine Liste mit zweistelligen Zeichenfolgen erstellt.
"au","eu","ei","ie","ch","es","er","en","an", "zu","ge","be","st","ab","in","da","du","ir","sp","ha","wo","wa","ss","tt","de","sa","ta","te","gr","un","mm"

Diese Zeichenfolgen werden mit einstelligen Symbolen codiert. Damit erziele ich schon recht gute Ergebnisse.
@HellKnight

Die Idee Sonderzeichen mit längeren Symbolen zu codieren war ja nur angedacht und setzt die Annahme voraus, dass die meisten SMS-Nachrichten viel weniger Sonderzeichen enthalten.
Mit meiner Liste würde deine Nachricht so aussehen:*lo mail *aaaerbbb.com. Die Sternchen stehen für die kürzeren Symbole. Schon an dieser Nachricht sieht man, dass durch das Ungleichgewicht ein komprimierender Effekt erhalten bleibt. Ich bin mit dieser Idee aber auch nicht glücklich,zumale es auch leicht zu uneindeutigen Situation kommen kann. D

Die Zeichenfolge "cha" wäre mit meiner Liste nicht mehr dekomprimierbar, weil der Algorithmus nicht wissen kann ob nun "ch" oder "ha" als kürzeres Symbol eingesetzt wurde. Insofern muss ich auch die Idee, längere Zeichenfolgen in einem zweiten Durchgang damit zu codieren neu überdenken.

Eigentlich müsste man eine grosse Anzahl von Sms-Nachrichten mal nach bestimmten Kriterien scannen um eine möglichst ideale Liste von Zeichenfolgen zu erstellen.

@treo

Diesen Gedanken hatte ich auch schon. Ich muss mich da nochmal genauer kundig machen. Dann wäre auch das Problem mit den Sonderzeichen gelöst.



mfg softrunner
 
Du könntest dein Problem mit einem Header lösen:

Byte1: HEADERLEN
Headerbytes: positionen der echten sonderzeichen in der sms
SMS:
komprimierte sms

Also ein Beispiel:

Ursprünglich:
hallo mail an aaa@bbb.com

Dann wird daraus:
BYTE1: 1
Headerbytes: 15 (positiopn 15 im string => 17 im wirklichen)
SMS:
@llo !il = aaa@bbb.com

Also im header speichern, welche sonerzeichen echt gemeint sind!
 
heute in der schule brachte mich einer auf die idee das es ja auch open source kompressions programme gibt, wie z.b. bz2 (http://sources.redhat.com/bzip2/) du könntest dir also mal den source code anschauen und sehen wie die es denn gemacht haben ^^


sonnst hätte ich da noch eine idee:
es kommt sicher auch mal vor das so sachen wie h.d.g.g.g.g.g.g.g.g.d.l. gemacht werden
wenn man also jetzt nur darauf eine solche code tabelle anwenden würde:
h. = ?
d. = ?
g. = ?
l. = ?

(ich hoffe ihr könnt alle zeichen auch anzeigen lassen ^^)
dann würde das ja vorerst so aussehen:
????????????
wenn mann sich wiederhohlende zeichen einfach auch noch zählt, dann hätte man nochmehr kompression:
???8?

das wäre jetzt schon eine ersparniss von 19(!) zeichen.

EDIT: leider werden die zeichen so nicht gespeichert ... ich arbeite an einer lösung
EDIT2: lösung gefunden
 
Bz2 ist wesentlich schwiriger, da man dort nach regelmäßigkeiten sucht!
(Schon oben gesagt)
Und lohnt sich bei einer kleinen SMS(130 zeichen oder?)nicht!!

Hab noch n bissn über dein Problem nachgedacht und bin zu folgendem ergebnis gekommen:

Die idee von mir oben war keine gute Idee, da man unter umständen dadurch eine SMS sogar dekomprimieren könnte!!!
z.B.: @@!"$%

Und nochwas: Warum willst du eigentlich eine SMS komprimieren? Damit du mehr Zeichen schreiben kannst? Auch wenn es gehen würde, würdest du höchstens 10 zeichen rausholen! Lohnt sich das?
 
@treo

Ich denke das die bekannten Algorithmen wie RLE, Huffman und Co bei einer Sms nicht greifen können. Die Besonderheit der Sms besteht eben darin, dass sie selbst bereits sehr klein ist. Dadurch ist der Platz für Vereinbarungen sehr begrenzt Deutlich wird dies wenn man mal versucht eine 160 Byte grosse Datei mir WinRar zu komprimieren. Die resultierende Datei wird in vielen Fällen grösser sein als die Quelldatei. Mag sein, dass ich dich falsch verstanden aber was würde bei deiner Methode passieren wenn die Zeichenfolge "h.d.8g.7g.g.g.g.g.g.g.g." komprimiert werden sollte?


@Hellknight
Und nochwas: Warum willst du eigentlich eine SMS komprimieren? Damit du mehr Zeichen schreiben kannst? Auch wenn es gehen würde, würdest du höchstens 10 zeichen rausholen! Lohnt sich das?
Zum Vergrößern anklicken....
Mir ist beim Schreiben von Sms-Nachrichten aufgefallen, dass ich häufig gerade etwas mehr als 160 Zeichen benötige. In einem solchen Fall wird die Sms dann in 2 Nachrichten gesplittet und das ist natürlich teurer.Blöd ist soetwas wenn ich z.b. nur 165 Zeichen brauche und dafür dann die zweite Sms "anbrechen" muss.
Dadurch kam ich auf die Idee, aber abgesehen davon finde ich es einfach interessant mir mal Gedanken zu dem Problem zu machen.

Da das Verfahren auf den Eigenarten der deutschen Sprache basiert hängt es natürlich immer von dem individuellen Text ab, wie stark die Sms komprimiert werden kann, aber ich habe bei meinen Tests meistens 20 Zeichen oder mehr gespart. In einigen Fällen konnte die Nachricht bis auf die Hälfte reduziert werden. Ich finde das durchaus sinnvoll. Ich habe das natürlich immer mit 160 Zeichen langen Sms getestet, denn nur ab dieser Länge machte das Komprimieren überhaupt Sinn. Ich berücksichtige allerdings nicht die Gross-und Kleinschreibung d.h. der User kann entweder keine grossen Zeichen eingeben oder die grossen Zeichen werden in kleine umgewandelt. Hier der Code , mit dem ich getestet habe:

Code: 
#include <iostream>
#include <stdlib.h>
#include <string.h>

#define MAX_SMSLENGTH 160
#define MAX_TABELLENGTH 31


char aszSrcTable [MAX_TABELLENGTH][3] = {"au","eu","ei","ie","ch","es","er","en",
                                         "an","zu","ge","be","st","ab","in","da",
                                         "du","ir","sp","ha","wo","wa","ss","tt",
                                         "de","sa","ta","te","gr","un","mm"};

char aszDestTable [MAX_TABELLENGTH][2] = {"'","!","(",")","@","/",":","_",
                                          ";","+","&","%","*","=","<",">",
                                          "ß","?","$","-","[","]","{","\\",
                                          "~","^","°","`","§","|","}"};                      
                        


char *GetCompressedSms (const char *szSource)
{

    char i,j,*pszDest,*pszSource; 
   
    pszDest =    (char*)malloc(MAX_SMSLENGTH); 
    pszSource =  (char*)malloc(MAX_SMSLENGTH);
    
    strcpy (pszSource,szSource);
   
    
    for (i = 0;i <= (MAX_TABELLENGTH-1);i++)
    {
       
       
       j  = 0;
       strcpy (pszDest,"");
       
       while (j <= strlen (pszSource))
        {
        
          if (!memcmp(&pszSource[j],&aszSrcTable[i],strlen(aszSrcTable[i])))
           {
              strncat(pszDest,aszDestTable[i],strlen(aszDestTable[i]));
              j += strlen(aszSrcTable[i]);
              
           }
          else
           {
              strncat(pszDest,(const char*)&pszSource[j],1);
              j++;  
              
           };
         
        };
        
       strcpy (pszSource,pszDest);     
       
                    
    } 
  
    free (pszDest);
    return (pszSource);

}


int main(int argc, char *argv[])
{
  
  char szSmsMessage [MAX_SMSLENGTH];
  char *pszCompressedSms;
  
  strcpy (szSmsMessage,"hier sollte eine sms stehen die möglichst 160 zeichen haben sollte und keine Grossschreibung enthält.");
  printf("%s\n",szSmsMessage);
  printf("%i\n",strlen(szSmsMessage));
   
  
  pszCompressedSms = GetCompressedSms(szSmsMessage);
  printf ("%s\n",pszCompressedSms);
  printf("%i\n",strlen(pszCompressedSms));
  
  
  system("PAUSE");	
  return 0;
}

Wobei das jedoch nur eine Vorabliste ist, die noch optimiert werden muss.


mfg, softrunner
 
Original von softrunner
@treo

Ich denke das die bekannten Algorithmen wie RLE, Huffman und Co bei einer Sms nicht greifen können. Die Besonderheit der Sms besteht eben darin, dass sie selbst bereits sehr klein ist. Dadurch ist der Platz für Vereinbarungen sehr begrenzt Deutlich wird dies wenn man mal versucht eine 160 Byte grosse Datei mir WinRar zu komprimieren. Die resultierende Datei wird in vielen Fällen grösser sein als die Quelldatei. Mag sein, dass ich dich falsch verstanden aber was würde bei deiner Methode passieren wenn die Zeichenfolge "h.d.8g.7g.g.g.g.g.g.g.g." komprimiert werden sollte?
Zum Vergrößern anklicken....

ja, das ist eben eins dieser probleme, dabei könnte man schauen ob direkt nach einem der speziellen zeichen eine zahl kommt, und beim komprimieren muss man dann zwischen Komprimierten zeichen und zahl ein leerzeichen gemacht werden
 
hmm is eigentlich nich meine idee (eigentlich von treo) aber ich sags mal hier:
Mach dir doch dein eigenes Protokoll!
mit socket() connect() usw...
Dann:
1.zahlst du weniger und
2.kannst du belibig viele zeichen senden
 
die idee war eigentlich so:
man schickt per datenruf (direkt) dem anderen eine msg, die wird von dem handy empfangen und dein prog kann dann decodieren
 
@Hellknight

Hab ich vorher nicht drüber nachgedacht. Scheint tatsächlich keine schlechte Idee zu sein. Ich kenne die Preise momentan überhaupt nicht. Aber im Augenblick warte ich noch auf die Entwicklungssoftware für Symbian, sodass ich nur gedanklich experimentieren kann.

mfg ,softrunner
 
wer eine gprs flat hat der zahl dann nix für so eine nachricht
sonnst kosten 10 kb glaube ich so 3 ct oder sowas :)
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben