Run Length Encoding problem

[TriKri]

Hello!

I have to solve a run length coding problem in matlab, compressing a vector containing integer numbers between 0 and 255, to a new vector with numbers between 0 and 255 using the following method:

* A number 0 ≤ n ≤ 127 in the encoded data means that the following n+1 numbers will be direct copies from the original data
* A number 129 ≤ n ≤ 255 in the encoded data means that the next number has existed 257-n times in a row in the original data
* The number 128 means that the sequence is over.

For example, the following vector: [0 1 2 9 9 9 4 5 6 7]
can be encoded to: [2 0 1 2 254 9 3 4 5 6 7 128]
or to: [9 0 1 2 9 9 9 4 5 6 7 128]
of which each encoding is equally good, since they are equally long (but longer than the original though).


Now I tried to find an algorithm which will always provide an optimal solution to this problem, using dynamic programming, but I realized it was too long since I last solved a similar problem. I just can't figure out how to come up with such an algorithm, but I suspect one could do it with dynamic programming. I would really appreciate if someone could help me out here!

Thanks in advance!

[morefood2001]

I don't know matlab so I have no clue how to do it in that program.

However if you were to do it in an actual programming language such as c++, a couple of if statements and perhaps a for loop would do the trick. Of course, any language would do the trick the same way.