Du bist nicht angemeldet.

Werbeanzeige

1

08.11.2020, 21:25

Zahlen komprimieren

Hallo, kann mir das bitte einer übersetzen was er damit meint? Ich verstehe das nicht ganz. Ich will ein Rle programmieren.


- Pick the first character from the source string.
- Append the picked character to the destination string.
- Count the number of subsequent occurrences of the picked character and append the count to the destination string.
- Pick the next character and repeat steps b) c) and d) if the end of the string is NOT reached.

Schorsch

Supermoderator

Beiträge: 5 198

Wohnort: Wickede

Beruf: Student

  • Private Nachricht senden

2

09.11.2020, 09:12

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
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Jonathan

Community-Fossil

  • Private Nachricht senden

3

09.11.2020, 09:59

@Schorsch: Man kann das nicht einfach weglassen:

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

Wohl also eher:

"213" -> "201030"
"223" -> "2130"
Lieber dumm fragen, als dumm bleiben!

4

09.11.2020, 10:11

Hallo -> Hal1o
Brunnen -> Brun1en
Schifffahrtsgesellschaft -> Schif2ahrtsgesel1schaft


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

Schorsch

Supermoderator

Beiträge: 5 198

Wohnort: Wickede

Beruf: Student

  • Private Nachricht senden

5

09.11.2020, 12:50

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.
@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.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

6

09.11.2020, 22:10

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.

7

09.11.2020, 23:05

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.
Cube Universe
Entdecke fremde Welten auf deiner epischen Reise durchs Universum.

Jonathan

Community-Fossil

  • Private Nachricht senden

8

10.11.2020, 22:39

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.
Lieber dumm fragen, als dumm bleiben!

9

13.11.2020, 04:16

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.

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »Audori« (13.11.2020, 04:32)


Werbeanzeige