Author Topic: Run-Length Encoding for Strings (Read 10709 times)

nemo · « **Reply #15 on:** August 25, 2010, 08:30:53 pm »

just changed a few minor things.

"_→Str3
Str1+Ans→Str1
"sub(Str1,B+1,1→u    .[2nd]+[7] u, not the lowercase one.
{0,1→L1
DelVar B1→A
Repeat u="     .again, the equation variable u. one space.
Repeat u≠sub(Str1,B+A,1
A+1→A
End
{0,A-1→L2
LinReg(ax+b) Y1
Equ►String(Y1,Str4
Str3+sub(Str4,1,length(Str4)-3)+u→Str3      .must be in this order 
B+A-1→B
1→A
End
sub(Str3,2,length(Str3)-1→Str3

i'm not 100% sure all the changes are made are valid, since i don't have any strings to compress into RLE and only tested things on the homescreen. something you might want to consider is to initialize A as 0 instead of one. for one, this allows you to use DelVar. secondly, statements like B+A-1→B and {0,A-1→L2 become B+A→B and {0,A→L2, saving a few bytes. also, one thing to consider is a limit. since one character can only hold numbers 0-9, what if someone in their string has 13 2's in a row? your compressed string would show 132, but the decompression routine would read it as 1 tile #3, and then 2 of the next tile #.

meishe91 · « **Reply #16 on:** August 25, 2010, 08:58:17 pm »

Well just from looking at it it looks like those are all valid. Thanks. I didn't think about using u to store sub(Str1,B+1,1, though that is still a new thing for me. I'm testing it all right now. As for the set A to zero first thing, I thought of that but didn't wanna bother with adjusting things if it needed to be done at the time but I can look at it. It looks like you're right though, I think the only change would be to change row seven to Repeat u≠(Str1,B+A+1,1. As for the limit thing I'm not sure. I mean I know what you mean, since my original string was just numbers, but that's why I provided that second set of code to replace the numbers with a different token so it can be read easily.

So, as I was writing this it finished compressing and those changes did work. Though it took a little longer because, I think, it has to solve u each time it comes up. Which isn't a big deal though. I'm currently testing the changes with A.

As for a decompresser, I am still working on it. I'm close, I think. I got something to work but I don't think it worked properly because the final string ended up being like 200 bytes less than it normally is

The weird part is that the beginning and end both match up just fine though, so I don't know what is going wrong with it (unless someone else can explain a loss in bytes).

And again, while writing this the changing A program finished and it seemed to work as well. I'll make these changes to the first post though. Thanks again, nemo.

nemo · « **Reply #17 on:** August 25, 2010, 09:39:52 pm »

np meishe. yeah, the slowdown is probably due to u being solved each time. but i never aim for speed in a compression routine, since compression routines aren't likely to be used in games, just the corresponding decompression routine.

i'm thinking your data loss is due to the limit issue i have with your code. make your first 11 characters in the string your trying to compress the same tile number, and then compress the string. see if you get a matching beginning sequence after decompressing the compressed string.
i'm thinking that the string "111111111111" 12 1's, will compress to "121" which will then give an error during decompression.

made a few more changes, added in my limit idea (i still think it's a good idea):

Code: [Select]

DelVar BDelvar A"_→Str3
Str1+Ans→Str1
"sub(Str1,B+1,1→u    
Repeat u="     
Repeat A=9 or u≠sub(Str1,B+A+1,1
A+1→A
End
Str3+sub("0123456789",A+1,1)+u→Str3      .must be in this order 
B+A→B
Delvar AEnd
sub(Str3,2,length(Str3)-1→Str3

if you want to have your strings be compressed where the highest run can be greater than ten, you can easily substitute A=9 for a higher number, and add onto the sub("0123456789") command. for example, to expand it to 13 you would have A=12 and sub("0123456789ABCD",A+1,1), but your decompression routine would have to be modified to allow that.

meishe91 · « **Reply #18 on:** August 25, 2010, 09:50:25 pm »

I'm fairly sure the limit thing is not the issue because I don't have my map as numbers. I changed the whole map to letter tokens to help make it readable, via the second code. So my compressed data looks something like "19A12B4D5A..." I actually might have been reading the wrong string data though, though I never checked. Probably should have

I can check later. But the decompression routine I have now relies on the fact that you are using a non-integer token for your map. I'm still working on it but it looks like it is working.

On the limit thing, I never said it wasn't a good idea. I said it was unnecessary for what I was doing because it was just to compress the data, which is in letter tokens, down. If I were to use RLE for my game I would probably have the limit thing for a couple reasons.

nemo · « **Reply #19 on:** August 25, 2010, 09:54:08 pm »

i don't follow how you store your data, but ok. good luck with your routines, i hope to see them (:

meishe91 · « **Reply #20 on:** August 25, 2010, 10:12:04 pm »

Ok, sorry. I'll try to explain. I'll use part of my actual map as the example. So my original map data goes as shown:

Code: [Select]

111111111111111
100300020000000
100305020000000
100300020000000
100344420000000

So the actual sting looks like:

Code: [Select]

"111111111111111100300020000000100305020000000100300020000000100344420000000→Str1
When I was going to compress the data the first time I ran into that issue you were saying, how like the first part will say "151." So instead of setting a limit, which I thought about, I decided I just wanted to compress this thing in whole without a limit to see how much memory I could save. But with the map being in numbers it was to hard to read so I came up with that second program:

Code: [Select]

"_"+Str1→Str2
For(A,2,1+length(Str2
sub(Str2,1,A-1)+sub("SATRWHM",expr(sub(Str2,A,1))+1,1)+sub(Str2,A+1,length(Str2)-A→Str2
End
sub(Str2,2,length(Str2)-1,Str2

So since each number represented a different tile I just matched the number up with a letter that represented the tile.

0=Space=S
1=Border Tree=A
2=Mid-Map Tree=T
3=Rock=R
4=Water=W
5=House=H
6=Mart=M

That program just replaces each number with its respective token turning the map into:

Code: [Select]

AAAAAAAAAAAAAAA
ASSRSSSTSSSSSSS
ASSRSHSTSSSSSSS
ASSRSSSTSSSSSSS
ASSRWWWTSSSSSSS

Therefore making the string now:

Code: [Select]

AAAAAAAAAAAAAAAASSRSSSTSSSSSSSASSRSHSTSSSSSSSASSRSSSTSSSSSSSASSRWWWTSSSSSSS→Str1
Using that string there is no issue reading "16A2S1R3S..." So now if I can get the decompression to work correctly you don't run into the issue of it reading three numbers in a row or only two or something. Does that make more sense?

DJ Omnimaga · « **Reply #21 on:** August 25, 2010, 10:21:35 pm »

Quote from: meishe91 on August 25, 2010, 05:18:31 pm

In a game or just in general? Because just in general it's not all that exciting to wait for a string to compress

in a game demo or something. Just to see how fast it decompresses

meishe91 · « **Reply #22 on:** August 25, 2010, 11:45:33 pm »

Ok, so a little update. First I'm gonna post the modified code that nemo made that just cleans everything up so you only have your original string and the outputted string left. Just makes it a little cleaner in the end, I think.

Code: (RLECMPN) [Select]

DelVar BDelVarA"_→Str2
Str1+Ans→Str1
"sub(Str1,B+1,1→u
Repeat u="_
Repeat A=9 or u≠sub(Str1,B+A+1,1
A+1→A
End
Str2+sub("0123456789",A+1,1)+u→Str2
B+A→B
DelVar AEnd
DelVar ADelVar BDelVar usub(Str1,1,length(Str1)-1→Str1
sub(Str2,2,length(Str2)-1→Str2

Ok, now for the decompression part. While I am still working on decompressing what my compression makes but I do have a way of decompressing what nemo's code gives you.

Code: (RLEDECMN) [Select]

"_→Str3
For(A,1,length(Str2)-1,2
For(B,1,expr(sub(Str2,A,1
Str3+sub(Str2,A+1,1→Str3
End
End
DelVar ADelVar Bsub(Str3,2,length(Str3)-1→Str3

Edit:
Figured out how to decompress mine now too

Code: (RLEDECMP) [Select]

"_→Str3
Str2+Ans→Str2
DelVar A1→B
Repeat "_"=sub(Str2,B+A,1
Repeat not(inString("0123456789",sub(Str2,B+A,1
A+1→A
End
For(C,1,expr(sub(Str2,B,A
Str3+sub(Str2,B+A,1→Str3
End
B+A+1→B
DelVar AEnd
DelVar ADelVar BDelVar Csub(Str2,1,length(Str2)-1→Str2
sub(Str3,2,length(Str3)-1→Str3

I'm sure there are some optimizations to be made.

ztrumpet · « **Reply #23 on:** August 26, 2010, 10:03:30 am »

Cool! How does this impact the speed of your game?

meishe91 · « **Reply #24 on:** August 26, 2010, 05:57:03 pm »

I haven't implemented any of it yet

I'm debating what I wanna do in terms of using this stuff.

Author Topic: Run-Length Encoding for Strings (Read 10709 times)

nemo

Re: Run-Length Encoding for Strings

meishe91

Re: Run-Length Encoding for Strings

nemo

Re: Run-Length Encoding for Strings

meishe91

Re: Run-Length Encoding for Strings

nemo

Re: Run-Length Encoding for Strings

meishe91

Re: Run-Length Encoding for Strings

DJ Omnimaga

Re: Run-Length Encoding for Strings

meishe91

Re: Run-Length Encoding for Strings

ztrumpet

Re: Run-Length Encoding for Strings

meishe91

Re: Run-Length Encoding for Strings