TI-BASIC:Rle Decompress

Routine Summary

Decompresses a run length-encoded list.

Inputs

L₁ - The compressed list

Outputs

L₁ - The decompressed list

Variables Used

L₁, I, J

Calculator Compatibility

TI-83/84/+/SE

Download

rledecompress.zip

:dim(L₁→J
:sum(E3fPart(L₁)+not(fPart(L₁→dim(L₁
:For(I,Ans,1,-1
:int(L₁(J→L₁(I
:If .001<fPart(L₁(J:Then
:L₁(J)-.001→L₁(J
:Else
:J-1→J
:End:End

[wikipedia:Run-length_encoding Run-length encoding (RLE)] is a very easy compression algorithm that you can use for compressing a list of numbers. The way it works is that you remove all of the consecutive repeated numbers from the list, and modify the first instance of the numbers with how many repeated numbers there were.

For example, say you have a list of numbers 1,2,2,3,3,3,4. You start with the 1, and since there is only one 1, it wouldn't be modified. There are two 2's, however, so you would remove the second two, and add a decimal part (using FPart() of how many 2's there were (in this case, just two, which we represent as .002). You would do this for the rest of the list, and the final list would be 1,2.002,3.003,4.

This routine could loosely be described as the RLE compression routine, but backwards. We start by calculating the length of the decompressed list. This is the sum of the length of the runs -- E3fPart(L₁) -- plus the number of elements with no runs -- not(fPart(L₁)). Here E represents the scientific E.

Then, the decompression begins. The routine keeps the following loop invariants (things that stay true after each iteration of the loop):

• Every element after the Ith element is the correct decompressed element in that spot.
• The portion of the list up to and including the Jth element is the compressed version of the list elements that will be 1 through I.

We "unpack" one element from the end of the compressed portion: int(L₁(J→L₁(I. Then we test if this compressed portion is a run that still contains more elements. If it is, we subtract .001, reducing the number of elements in the run by 1. If it's not, we decrease J by 1 to move on to the previous compressed element. As you can see, the conditions listed above are still true.

Once the loop ends, the first condition of the ones above ensures that all elements have been correctly decompressed.

Note that we never store anything to L₁ itself, only to its elements. This is done to avoid using any more memory than necessary: if we stored to L₁, a copy of the list would get temporarily stored to Ans, and we would be using twice the memory we need. This way, the routine will work even for large lists. As a bonus, the only time we change the size of the list is the very beginning. So if the decompressed list wouldn't fit in memory, the routine crashes immediately and keeps the list intact.

Error Conditions

• ERR:MEMORY is thrown if there is not enough space to store the decompressed list.
• ERR:INVALID DIM is thrown if the decompressed list would be longer than 999 elements.

Related Routines

• RLE Compression
• RLE Decompression for Strings