Wir suchen einen Algorithmus zum Komprimieren sehr kurzer Texte (Es handelt sich um SMS). Die Texte sind
in der Regel in deutscher Sprache verfasst und ca. 80 Zeichen lang.
Diese sollen nach der Komprimierung über ein Netzwerk übertragen werden
und danach wieder dekomprimiert werden. Der Speicherbedarf der Software
ist für den Wettbewerb unerheblich, d.h. es können Wörterbücher und co
beliebiger Größe verwendet werden. Der Algorithmus soll verlustfrei
arbeiten bis auf folgende Ausnahmen:
– nach dem Dekomprimieren dürfen alle Buchstaben Großbuchstaben sein.
– Umlaute und das „ß“ dürfen nach dem Dekomprimieren ausgeschrieben sein.
– Alle nicht-Buchstaben – also auch Zahlen – ausser “ !.-:)“ dürfen nach
dem Dekomprimieren ein „.“ sein
Gewinner ist der Algorithmus, der auf eine Textsammlung angewandt das
beste Durchschnittsergebnis erzielt. Der Algorithmus muss unter GPL oder
BSD Lizenz stehen und wird von uns veröffentlicht. Als Preis winken
neben ewigen Ruhm eine Nennung im Quellcode, auf unserer Website und auf
dem LNDW-Poster!
Der Wettbewerb läuft bis Ende Februar. Einsendungen bitte per Mail an
mich. Der Algorithmus sollte am besten in c oder Java abgefasst sein.
Die
Am 27. Januar 2011 um 13:44 Uhr
Hi,
Hätte ein paar fragen :
1. welche zeichen sind in der eingabe erlaubt?
2. alle sms in deutscher sprache?
grüße
Am 27. Januar 2011 um 13:45 Uhr
Warum 80 Zeichen? SMS sind doch 160 Zeichen lang…
Am 27. Januar 2011 um 14:09 Uhr
Ja, aber 160 zeichen über eine Kugelbahn sind je nach Komprimierung über 1000 Kugeln…
Am 27. Januar 2011 um 14:10 Uhr
Hallo,
in der Eingabe sind alle Zeichen erlaubt – das ist aber irrelevant, da ich ja die Zeichen der Ausgabe vorgegeben habe. D.h. alle nicht Buchstaben und die 6 erlaubten Sonderzeichen können schon vor dem Komprimieren durch den „.“ ersetzt werden.
Am 27. Januar 2011 um 14:13 Uhr
Die Texte sind in deutscher Sprache, es müssen aber auch alle anderen Wörter/Texte übertragen werden können. Da 99% in deutscher Sprache sein werden, spielt der Komprimierungsgrad der nicht deutschen in der Summe aber keine Rolle.
Am 27. Januar 2011 um 14:20 Uhr
Super wäre es, ein Beispielwörterbuch mit SMS-Sprache zu haben. Will nicht mal jemand eine einschlägige Internetseite parsen und hier als TXT zur Verfügung stellen?…
Am 27. Januar 2011 um 15:19 Uhr
Hier gibt es diverse Wortlisten, nach Häufigkeit sortiert:
https://wortschatz.uni-leipzig.de/html/wliste.html
Am 27. Januar 2011 um 17:09 Uhr
Ist das Versenden über ein Netzwerk ein echtes Versenden, so dass man beim Dekrompieren „Fehler erkennen“ und/oder „Fehler korrigieren“ soll oder ist das irrelevant?
Am 27. Januar 2011 um 17:16 Uhr
Es ist ein echtes Versenden (auf dieser Website erklärt). Allerdings findet auf den unteren Layer eine Fehlererkennung statt, so dass Euer Algorithmus von einer fehlerfreien Übertragung ausgehen kann.
Am 27. Januar 2011 um 17:17 Uhr
In welcher Zeichencodierung ist die Eingabe? Bei UTF-8 würden die Umlaute und das ß 2 Bytes brauchen. Bei ISO-8859-1 wäre es nur ein Byte. Das wäre zum Einlesen wichtig.
Am 27. Januar 2011 um 17:22 Uhr
Das Ursprungsformat ist ISO 8859-1 (ASCII). Arbeitet für die Eingabe einfach mit normalen String (egal ob UTF8 oder ASCII), komprimiert das ganze dan wie Ihr wollt und entkomprimiert das ganze wieder als String, der dann eben nur noch die erlaubten 32 Zeichen enthält.
Am 27. Januar 2011 um 18:16 Uhr
Ich korrigiere nur ungerne, aber ISO 8859-1 ist nicht das gleiche wie ASCII.
Am 27. Januar 2011 um 19:04 Uhr
Wird dem Algorithmus die vollständige Sammlung von SMS gegeben, oder nur eine SMS nach der anderen?
Am 27. Januar 2011 um 19:15 Uhr
BItte auch den Rest der Seite lesen. Es geht hier um echte Datenübertragung. Wir empfangen eine SMS aus dem Publikum und übertragen diese mittels einer Kugelbahn. Da wir so wenig Kugeln wie nötig nutzen wollen, muss die SMS komprimiert werden. Eurer Fantasie sind dabei keine Grenzen gesetzt.
Eine Wortdatei können wir nicht stellen, da wir ja nicht wissen was für SMS die Leute schreiben werden. Erfahrungsgemäß kommen aber Sachen wie „Hallo [NAME]“ oder ähnliches recht häufig vor.
Am 31. Januar 2011 um 14:21 Uhr
Wie soll denn der kodierte Byte-Stream repräsentiert werden? Einfach als String von ‚0‘en und ‚1‘en, oder kodiert in 32bit Integers, oder …?
Am 1. Februar 2011 um 13:34 Uhr
Am besten als char array oder wie auch immer, aber nicht als String.
Am 3. Februar 2011 um 19:50 Uhr
Gibt’s bekommt man am Ende mitgeteilt auf welchen Platz man mit seinem Algo gekommen ist – oder wird es gar ein Ranking geben?
Am 7. Februar 2011 um 13:20 Uhr
Hier mein Vorschlag für einen Algorithmus:
Die Bedinungen stehen ja schon oben:
-das Alphabet hat 32 Zeichen
-ca. 80 Zeichen Text werden versandt
-Speicherbedarf unerheblich
Meine Idee ist ganz simpel, braucht für eine SMS mit 160 Zeichen – NACH Konvertierung in das 32-Zeichen Alphabet – maximal 235Kugeln. Bei maximal 80 Zeichen sind es 203 Kugeln.
Eine Lookup-Tabelle…
alle 160^32 Möglichkeiten generieren und in einer Tabelle ablegen und durchnummerieren.
zum Komprimieren den Text in der Tabelle suchen und die Zahl übertragen, beim Dekomprimieren die Zahl nachschlagen und den Text ausgeben.
Vermutlich sprengt die Tabelle doch ein wenig den Rahmen…
LG LB
Am 8. Februar 2011 um 08:35 Uhr
@Marco: Ein Ranking sollte kein Problem sein. Ich würde eines mit den Ergebnissen unseres Testtextes erstellen – worauf der Sieger basiert. Und zusätzlich noch Eines das aus den echten auf der LNDW verschickten SMS generiert ist – also das Praxisranking.
@LB: Dem ganzen liegt ein Rechenfehler zugrunde. Da Deine Betrachtung die Entropie des Textes überhaupt nicht betrachtet, könnte ich Deinen Ansatz rekursiv anwenden und Text würde jede Runde kleiner.
Eine SMS aus 80 Zeichen mit einem Alphabet aus 32 Zeichen hat 80*5 Bit – das sind 400 Bit. 400 Bit sind 2^400 Kombinationen und 2^400 Kombinationen kannst Du bijektiv nur in Log2(2^400)=80 Bit repräsentieren. Du brauchst also keinerlei Speicher, da Deine Representation bei entsprechender Abbildungsvorschrift die Nachricht selber ist. Probier das mal bei einem Byte. Das hat 8 Bit und 256 Kombinationen. Diese 256 Kombinationen kannst Du jetzt in eine Lookup Tabelle eintragen und jeder einen key geben und nur den Übertragen. Trotzdem ist die Keylänge 8 Bit.
Am 8. Februar 2011 um 10:57 Uhr
@Heiko: 1) char array heißt, wir können nur Vielfache von 8 Bit als Code ausgeben? 2) Darf der Codec beim Benchmark auch Dateien erstellen, die zwischen den Aufrufen erhalten bleiben?
Am 8. Februar 2011 um 12:59 Uhr
@Stefan: Du kannst auch zusätzlich zum array die Menge der relevanten Bits zurückgeben, dann kannst Du evtl. 7 Bit sparen ;-). Dateien erstellen wäre mir nicht so lieb, aber behalte alles was Du brauchst im Speicher und besorg Dir den mit malloc, so das der überlebt. Wenn es nicht anders geht, kannst Du auch Dateien nutzen.