- Forum
- General C++ Programming
- run length coding
run length coding
| how can i create run length coding using dynamic arrays |
Last edited on
Run Length Encoding is a simple compression technique.
The dynamic arrays are not an essential part of the algorithm -- but they are necessary to manage the data.
RLE works by finding a lot of repeats in the data. For example, given:
1 3 7 3 3 3 3 3 3 3 9 4 2 2 2 2 2 1
The first thing we notice is that there are long "runs" of threes and twos. We can replace them with just the number of values, and the value to be used:
1 3 7 (7 3) 9 4 (5 2) 1
The "header" number (which tells us how many times to repeat the item) can also be used to tell us how many not-repeatable items there are:
(3 1 3 7) (7 3) (2 9 4) (5 2) (1 1)
The problem now is knowing whether we are repeating a single value or just counting a whole bunch of different values. Let's make the header number negative if we are repeating:
(3 1 3 7) (-7 3) (2 9 4) (-5 2) (1 1)
At this point, those parentheses are no longer necessary. We can remove them:
3 1 3 7 -7 3 2 9 4 -5 2 1 1
We went from having 18 numbers down to 13 numbers. That's a compression of 72% of the original. Not bad!
We can decompress it by looking at the first/next number:
3 --> 1 3 7
-7 --> 3 3 3 3 3 3 3
2 --> 9 4
-5 --> 2 2 2 2 2
1 --> 1
1 3 7 3 3 3 3 3 3 3 9 4 2 2 2 2 2 1
Also, Wikipedia has a good overview with links to other varieties of implementation http://en.wikipedia.org/wiki/Run_length_encoding
Hope this helps.
The dynamic arrays are not an essential part of the algorithm -- but they are necessary to manage the data.
RLE works by finding a lot of repeats in the data. For example, given:
1 3 7 3 3 3 3 3 3 3 9 4 2 2 2 2 2 1
The first thing we notice is that there are long "runs" of threes and twos. We can replace them with just the number of values, and the value to be used:
1 3 7 (7 3) 9 4 (5 2) 1
The "header" number (which tells us how many times to repeat the item) can also be used to tell us how many not-repeatable items there are:
(3 1 3 7) (7 3) (2 9 4) (5 2) (1 1)
The problem now is knowing whether we are repeating a single value or just counting a whole bunch of different values. Let's make the header number negative if we are repeating:
(3 1 3 7) (-7 3) (2 9 4) (-5 2) (1 1)
At this point, those parentheses are no longer necessary. We can remove them:
3 1 3 7 -7 3 2 9 4 -5 2 1 1
We went from having 18 numbers down to 13 numbers. That's a compression of 72% of the original. Not bad!
We can decompress it by looking at the first/next number:
3 --> 1 3 7
-7 --> 3 3 3 3 3 3 3
2 --> 9 4
-5 --> 2 2 2 2 2
1 --> 1
1 3 7 3 3 3 3 3 3 3 9 4 2 2 2 2 2 1
Also, Wikipedia has a good overview with links to other varieties of implementation http://en.wikipedia.org/wiki/Run_length_encoding
Hope this helps.
Topic archived. No new replies allowed.