Run Length En/Decoding [Komprimierung B+/BB]

Übersicht BlitzBasic Codearchiv

Neue Antwort erstellen

ozzi789

Betreff: Run Length En/Decoding [Komprimierung B+/BB]

BeitragDo, Nov 24, 2011 22:34
Antworten mit Zitat
Benutzer-Profile anzeigen
Abend liebe Community

Momentan behandeln wir in der Schule diverse Komprimierungsverfahren.
Da es mich sehr interessiert habe ich RLE in BB umgesetzt.

Für die Leute denen dies jetzt nichts sagt, RLE komprimiert Strings/Daten.
Der Trick dabei ist, sich wiederholende Zeichen, z.B bei einer 2D Map mit einer Runlenght zu speichern.

Soll heissen 00000011111111110000 (0 ist ein leerer Block, 1 eine Wand)
wird zu 6x010x14x0
Um das Ganze wieder ohne Verluste zu decoden, muss jedoch ein Markerbyte gesetzt werden (sodass man weiss, dass jetzt eine Wiederholung anfängt)
Sagen wir & ist unser Markerbyte.
Hier unterscheidet sich mein Algo mit dem "Normalen", da ich die die Stellenzahl des Runcounts auch übergebe und trotzdem alle möglichen ASCII Zeichen verwenden kann.
D.h unser 00000011110000 wird zu &160&2101&40
Das Rote &210 soll heissen &-hier fängt eine Wiederholung an, die Anzahl Chars die die Anzahl beschreiben sind 2 ('1'+'0') also 10 mal das nächste Zeichen wiederholen.

Wir haben also doch einige Zeichen gesparrt, stellt euch dass jetzt bei grösseren Maps vor Wink


Für die denen das jetzt Konfus erscheint (bin auch schon etwas müde Wink)
Hier der Wikipedia Link http://en.wikipedia.org/wiki/Run-length_encoding


Eine Demo gibt es hier zum Download (OZ_RLE.exe)
http://zgheb.com/cms/downloads...p;dir=desc

Ohne Pics saug ich nix
user posted image


Und hier der BB Code

V.1.1 - Performance optimiert
BlitzBasic: [AUSKLAPPEN]

Function RLE_ENCODE$(strng$,offset=4,marker=1)
;Variablen zurücksetzen
x=0 ;Pointer im String
count=1 ;Runcount
strng_len=Len(strng$)
While (x<strng_len) ;Abfangen wenn wir den String durchlaufen haben
x=x+1 ;Den Pointer im String um eins erhöhen

cursign$= Mid(strng$,x,1) ;Zeichen beim Pointer auslesen
nextsign$= Mid(strng$,x+1,1) ;Das nächste Zeichen auslesen

If cursign$=nextsign$ ; Falls das jetzige und das nächste gleich sind
count=count+1 ; Runcount erhöhen
Else
If count>=offset ; Falls die Zeichen nicht gleich waren, aber der Runcount grösser/gleich der Offset ist
newstrng$=newstrng$+Chr(marker)+Len(Str(count))+count ;Den codierten String um den Marker, die Runcount Char Anzahl und den Runcount ergänzen
Else If count>1 ; Falls wir weniger Wiederholungen hatten als der Offset
newstrng$=newstrng$+String(cursign$,count-1) ; Die Zeichen sooft ausgeben wie sie vorkamen
EndIf
count=1 ; Count zurücksetzen
newstrng$=newstrng+cursign$ ;Das eigentliche Zeichen hinzufügen
EndIf
Wend
Return newstrng$ ;Fertigen String zurückgeben
End Function



Function RLE_DECODE$(strng$,marker=1)
x=0 ;Pointer im String.
strng_len=Len(strng$)
While (x=<strng_len) ;Abfangen wenn wir den String durchlaufen haben

cursign$= Mid(strng$,x,1) ;Zeichen beim Pointer auslesen
nextsign$= Mid(strng$,x+1,1) ;Das nächste Zeichen auslesen

If cursign$=Chr(marker) ;Falls das aktuelle Zeichen ein Marker ist
countlenght=Int(nextsign$) ; Die Runcount Char Anzahl auslesen, zB bei 2 ist es 1, bei 10 ist es 2, bei 245 ist es 3
count=Int(Mid(strng$,x+2,countlenght)) ; Den Count auslesen anhand der ermittelten Länge
newstrng$=newstrng$+String(Mid(strng$,x+3+countlenght-1,1),count-1) ;Die ermittelte Anzahl des Zeichens ausgeben
x=x+2+countlenght ; Den Pointer weitersetzen
Else
newstrng$=newstrng$+cursign$ ;Das eigentliche Zeichen hinzufügen
x=x+1 ; Den Pointer um eins erhöhen
EndIf
Wend
Return newstrng$ ;Fertigen String zurückgeben
End Function



Der Code kann sicherlich noch optimiert werden, er ist aber 100% einsatzfähig und schon ziemlich flink.
Feedback ist wie immer, sehr erwünscht!

Grüsse
Ozzi
0x2B || ! 0x2B
C# | C++13 | Java 7 | PHP 5
  • Zuletzt bearbeitet von ozzi789 am Mo, Nov 28, 2011 11:14, insgesamt einmal bearbeitet

Propellator

BeitragDo, Nov 24, 2011 22:40
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi,
coole Sache!

Einfacher Optimierungsvorschlag: cursign den Wert von nextsign zuweisen, und cursign nur vor der Schleife auf die Stringopteration setzen. Ausserdem wäre es evtl. nützlich, anstatt Strings zu vergleichen diese mit Chr() als Integer zu vergleichen, oder gar die String-Abfolge gleich als Bank einlesen.
Ich weiss jedoch nicht, wie viel Performanceschub die beiden Methoden bringen.

MfG
Propellator - Alles andere ist irrelephant.
Elefanten sind die Könige der Antarktis.

ozzi789

BeitragFr, Nov 25, 2011 19:22
Antworten mit Zitat
Benutzer-Profile anzeigen
Abend Propellator,

Danke für die Rückmeldung, werd mich gleich ans Werk machen Smile

Grüsse
0x2B || ! 0x2B
C# | C++13 | Java 7 | PHP 5

Neue Antwort erstellen


Übersicht BlitzBasic Codearchiv

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group