spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hey,
du merkst dir zu jedem Buchstaben einfach wie oft er hintereinander steht. Sowas wie abbbccdeeefba wird (a, 1), (b, 3), (c, 2), (d, 1), (e, 3), (f, 1), (b, 1), (a, 1).
In deinem Fall ist es jetzt leicht abgewandelt. Anstatt dir die Zahl der aufeinanderfolgenden gleichen Buchstaben zu merken, merkst du dir einen weniger. Das hat den Vorteil dass "abc" einfach "abc" bleibt und nicht "a1b1c1" wird. Mal ein paar Beispiele.
Hallo -> Hal1o
Brunnen -> Brun1en
Schifffahrtsgesellschaft -> Schif2ahrtsgesel1schaft

@Schorsch: Man kann das nicht einfach weglassen:

"213" -> "213"
"223" -> "213"

Wohl also eher:

"213" -> "201030"
"223" -> "2130"

Zitat von »MaxB96«

kann man auch für Hallo ->H2lo für Brunnen->Bru2nen ,Schif3ahrtsgesel2schaft oder muss das so sein wie oben?

Ob du die Zahl vor oder hinter den Text schreibst ist egal.

Zitat von »Jonathan«

@Schorsch: Man kann das nicht einfach weglassen:

Das führt zu Problemen, klar, wird aber so in dem vorgegebenen Text beschrieben. Es gibt übrigens noch mehr Probleme.
a123 bedeutet das 123 mal a oder a222? Dafür gibt es Lösungen, die werden hier in der Erklärung aber auch nicht aufgegriffen.

Hä? Das ist doch nur ganz normales Run-Length-Encoding. Wieso macht ihr daraus jetzt so eine Diskussion?

Zeichen, Anzahl Wiederholungen, nächstes Zeichen, ...

Problematisch wird es nur, wenn es sich 256-mal wiederholt und nur 1 Byte genutzt wird, dann müsste man da abbrechen und a 255 a 0 speichern.

Zitat von »MaxB96«

1)wähle das erste Zeichen aus der Zeichenfolge
2)zähle die Anzahl der nachfolgenden Vorkommen des ausgewählten Zeichens.
3)ersetze die Anzahl des Vorkommen des ausgewählten Zeichens durch Zahlen.
4)Falls das ausgewählte Zeichen keine nachfolgenden Vorkommen hat, dann schreibe 1 auf.
5)wähle dann das nächste Zeichen und wiederhole die Schritte 1-5 bis zum ende der Zeichenfolge.


Kann ich das so schreiben? Ich soll den Algorithmus aufschreiben.

Naja es geht in die richtige Richtung, aber man kann das auch leicht falsch interpretieren.

Zu 2: Was bedeutet ersetzen? Die Anzahl der Vorkommen ist ja eine eigenständige Variable, soll die dann ihren Typ ändern? Oder änderst du den Eingabestring?
Zu 4: Wieso 1 und nicht 0? Wenn das Zeichen noch 1 mal vorkommt, steht dann da nicht auch 1?
Und was passiert, wenn das Zeichen mehr als 10 mal hintereinander auftaucht?

Programmier den Algorithmus einfach mal, such dir ein paar gute Teststrings raus und teste ob du die komprimieren und wieder dekomprimieren kannst.

Vor etwas längerem, brauchte ich auch mal eine Komprimierungsfunktion für ein Mobil-Game. Speicher und CPU durften nicht stark belastet werden. Daher hatte ich letztlich dann auch eine simple Lauflängenkodierung programmiert. Dabei zeigte sich jedoch mit der Zeit, das es doch sehr viele Situationen gibt, in denen die Daten zweideutig sind.... hier im Thema wurden das ja auch schon angesprochen ;-)

Nach sehr vielen Tests mit Realdaten, entwickelte sich der Algorithmus deswegen letztlich hin zu einer Lauflängenkodierung mit Flag als Signal für komprimierte Bytes/Zeichen.


Dabei habe ich dann in einem einzigen Byte, sowohl dieses Flag, als auch die Anzahl der Wiederholungen gespeichert.
Flag ist: Binär 1110 0000
Damit stehen also die rechten 5 Bits noch zur Verfügung für die 'Anzahl Wiederholungen'.
Mit 5 Bits lassen sich nur die Dezimalzahlen bis 31 speichern. Entsprechend werden also bei mehr als 31 Wiederholungen, für je 31 Zeichen dann 'Zwischenschritte' sozusagen komprimiert.

Ich hatte auch mit Flag '1100 0000' und '0100 0000' experimentiert. Was 63 Wiederholungen erlaubt hätte ohne 'Zwischen-Komprimierung'. Jedoch zeigte sich, dass es mit Realdaten viel seltener zu mehr als 31 Wiederholungen kommt, als das in den unkomprimierten Originaldaten ein Byte '1100 0000' enthalten ist was dann extra Maskiert werden müsste.
Auch mit einem '2-Byte Flag / Wiederholungsanzahl' habe ich experimentiert. Doch auch hier zeigte sich, dass bei Realdaten viel zu selten so viele Wiederholungen vorkommen, um den Mehrbedarf des 2. Bytes auszugleichen.

Wenn also eine Wiederholung entdeckt wird, dann wird dies mit 2 Bytes gespeichert. Zuerst das original Zeichen/Byte, dann das Flag inkl. Anzahl. Komprimierungsmäßig wäre es kein Unterschied welches der beiden Bytes zuerst kommt, aber in dieser Reihenfolge lies es sich besser in Quellcode programmieren.
Ein komprimiertes Zeichen wird also gespeichert mit diesen 2 Bytes:
<Zeichen/Byte> + <111<Wiederholungen>>

Eine Komprimierung erfolgt erst bei 3 Wiederholungen. 2 Wiederholungen würden sich zwar auch kodieren lassen, aber ohne Speicherersparnis und da dies keine Vorteile bringt sondern nur mehr Aufwand für die CPU wäre, wird erst bei 3 Wiederholung komprimiert.


Was ich damit sagen will: Selbst so etwas eigentlich simples wie die Lauflängenkodierung, hat schon einige Fallstricke und Sondersituationen die man beachten muss, damit sie absolut Fehlerfrei arbeitet. Und dies wiederum führt dazu, dass erst bei mehr als 2x gleiches Zeichen/Byte eine Komprimierung erfolgen kann. Zumindest gilt dies, wenn nicht nur ausschließlich ASCII Zeichen bis 127 komprimiert werden sollen. Also bereits bei UTF8 / Unicode Texte, braucht es das … netter Nebeneffekt ist dann jedoch, dass Binärdaten dann auch genauso problemlos funktionieren :-D


Falls jemand Interesse hat... im Anhang ist der Quellcode dazu. Der Code ist allerdings wegen der Performanceoptimierungen nicht sonderlich schön und die Variablennamen würde ich Heute auch anders benennen.
XCompress.cs

Die Benutzung ist ganz einfach. Es sind 2 static Funktionen in einer static Class:
byte[] Compress(byte[] data, ref ushort dataSize)
byte[] DeCompress(byte[] data, ref ushort dataSize)

Übergeben wird jeweils ein byte Array und die Größe als ushort.
Das Array darf also größer sein als die darin enthaltenen Nutzdaten. Und, wegen ushort, können nur maximal 65535 Bytes auf einmal komprimiert/dekomprimiert werden.
Zurück gegeben wird jeweils auch wieder ein byte Array. Entweder sind dies dann komprimierte Daten, oder die unveränderten original Daten.
Und zurück kommt bei BEIDEN Funktionen, auch wieder die Größe der Nutzdaten des zurückgegebenen byte Arrays (deswegen ref ushort).
Compress() gibt Original zurück wenn sich Komprimierung nicht gelohnt hat. Und DeCompress() gibt Original zurück wenn die Input-Daten nicht komprimiert waren.