Run Length Encoding

Introduction

Compression algorithms are an important aspect of computer science. Compaction is the method of minimizing the quantity of data required for a given piece of information to be stored or transmitted, usually by the use of encoding techniques. Today, when 20 megabytes may be needed for an uncompressed digital image, data compression is critical in digitally loading information on computer discs and conveying it to communication links.

Knowledge is stored in patterns of 0s and 1s, or bits. Two bits per character would be required for the alphabet (a, e, r, t) if all characters were likewise. Therefore, all the letters in the expression “A rat ate a tart at a tea,” could be coded with 2 x 18 = 36 bits. Since “a” is the most common in this text, assigning a variable-length binary code, a = 0, t = 10, r = 110, e = 111, with “t” the second most common, will result in a flattened message of only 32 bits. The essential feature of this encoding is that no code is a prefix of any other one. That is, to separate letter codes, no extra bits are required: 010111 decodes unambiguously as ate.

Lossless (exact) or lossy (inexact) can be the compression of data. In order to produce the original data, lossless compression may be reversed, whereas lossy compression removes information or presents minor errors in reversal. For text, lossless compression is appropriate, where each digit is significant, while lossy compression might be reasonable for pictures or speech (The limitation of the frequency spectrum is an example of lossy compression in telephony).

Technique to minimise the initial bits of information to a smaller number of bits. Lossless compression is a special type of compression of information the algorithm requires the reduction of bits by recognising and removing Redundancy in statistics. A simple framework that delivers strong loss lessness Data compression that contains several runs of the same value is Run Length Encoding. One of the most important aspects of increasing device efficiency is compression technique in the computer system. For performing RLE encoding for lossless data compression is fine.

Encoding:

The code would need to loop finish each character of the data and tally the occurrences to encode a string of data. When you perceive a character that varies from the preceding character, the number of incidences and the character will be appended to your encoding.

Decoding:

In fact, decoding an RLE encoded data stream is quite easy than encoding it. You iterate, as formerly, one character at a time via the data stream. If you see a numeric character, you increase your sum, and if you see a non-numeric character, you add the amount to your encoding of these characters, which is returned to the caller after you have iterated all the input data.

RLE Definition:

It is a process which analyses the communication into successive arrangements of identical occurrences (runs). It takes many forms, as with Huffman coding, and used as an aspect in many encoding algorithms. Run length coding may typically be characterised via a sole instance of a frequent value tailed by a replication count by its trademark of encoding a run of equivalent data standards.

Run Length Codes:

Signal sources can generate “runs” or just 1s or 0s long sequences. In these situations, transmitting the cypher for the duration of the run is more effective than the total bits which embody the run itself. The fax machine is one cause of long runs. The working of a fax machine is by mapping a black or a white pixel after scanning the document into very small areas of the document. The paper is split into lines (about 100 per inch), with 1728 pixels (at standard resolution) in every line. If all black picture elements are plotted to 1s and all white picture elements to 0s, then 1857600 bits (for a regular 11-inch) would be represented by the scanned text. At older modem communication speeds of 4,800 bt/s, sending a single page will take 6 minutes and 27 seconds. However, if a run-length code is used to compact the sequence of 0s and 1s, substantial reductions would be made in transmission time.

It plots run lengths into codewords, and two sections of the codebook are subdivided. The very first part includes symbols for longitudinal runs with a multiple of 64; the second part consists of 0 to 63 pixel runs. It would then reflect every run length as a multiple of 64 plus and a remainder. For e.g., a run of 205 pixels for a run of length 192 (3 x 64) plus the code word for a run of length 13 will be sent using the code word. The amount of bits required to reflect the run is substantially reduced in this way. Furthermore, certain runs that are considered to take a greater likelihood of incidence are compressed into short-length code words, further decreasing the amount of bits that need to be conveyed. Typical compressions for duplicate transmission vary b/w four to one and eight to one using this method of encoding. These compressions, combined with higher modem data rates, decrease the communication time of a sole page from 48 seconds to 1 minute 37 s.

Run Length Encoding for Textual Data

This approach includes working over the text and tallying the amount of each character’s successive incidences (called “a run”). The count is the first portion of the couple and the character is the second portion.

Example: aaaabbbb bbc ddddddddd.

In this example, there are sixteen characters, so sixteen bytes are required (let suppose ASCII being used) to stock these characters in an uncompressed format:

Being an ASCII example: 97 97 97 97 98 98 98 98 98 98 99 100 100 100 100 100

RLE can, however, be used to stock the same information using less bytes. The character ‘a ‘has four successive incidences, tailed by six successive incidences of’ b ‘, one’ c ‘, and lastly five successive incidences of’ d ‘. It might be inscribed as the next occurrence-character pair arrangement:

Run-length encoding E.g.: 4 à a ; 6 à b ; 1 à c ; 5 à d

We would end up with: 04 97 06 98 01 99 05 100 if this manuscript is being compressed using Run Length Encryption. As we can see, only 8 bytes are needed for this compressed version-a removed from the real 16 bytes (pretentious one byte is still used to represent each number). Manuscript that has characters with a high recurrence can be effectively encoded. If the encoded form requires more storage space than the uncompressed version, text with rare recurrences, that is, additional arbitrary text, will not encode fine and will also result in bad encoding. Using a distinct byte value that ‘marks’ when a run will occur is a potential solution to this. However, this ensures that there is automatically an additional byte applied to every byte run. The next byte(s) will be booked as their face value and with a run of 1 when there is no flag.

Example

Non-compressed

Aaaaaaaaabbbbbbecececececececececddddddddddddddddecb (46 bytes)

No RLE flag

10 97 06 98 01 101 01 99 01 101 01 99 01 101 01 99 01 101 01 99 01 101 01 99 01 101 01 99 15 100 01 101 01 99 01 98           36 bytes

RLE Flag (value 255) 255 10 97 255 06 98 101 99 101 99 101 99 101 99 101 99 101 99 101 99 101 99 255 15 100 101 99 98 15 100 101 99 98   (Twenty-four bytes)

Binary Run Length Coding:

These codes are of special attention because they display their figures as a series of substitute 0 and 1 run lengths; it is not necessary to send the symbol repeated in each run. In addition, since binary codes have a small alphabet, it is possible that there will be long runs of extra common character instances. Two Coding schemes are available

Variable to Fixed Run Length Code:

For selecting an N, the likelihood p of the most possible number is being used. N bit words that comprise the dimensions of sequential runs of 0s and ls are then transmitted. The supreme value is conveyed and counter is returned if the run length surpasses the total size of word size. “An alternative approach is to transmit a sequence of” run “lengths specified as zero or more than zero sequences, as tailed by a single 1.

Variable to Variable Run Length Code:

It is enough to tell that run lengths are encoded using binary codes of different lengths with petite run lengths allocated to codes that are shorter than longer run lengths. Shorter codes are allocated to the more likely run lengths by an additional modification, called multimode Golomb coding. Since a memoryless source generates a symmetrical run length distribution, runs with an average length are allocated to the shortest codes pretty much runs with petite lengths.

It is worth noting a variety of added strategies for compression of binary memoryless sources even if they do not precisely use run-lengths. These approaches are often stated as techniques for bit vector compression. While run-length coding depends totally on the incidence of symbol runs, bit vector method trust on the more frequent symbol’s increased occurrence.

RLE Case Study:

Data compression to take advantage of this redundancy. Consider the following 40-bit string, for instance:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

This string consists of Fifteen 0s, then Seven 1s, then Seven 0s, then Eleven 1s, so that we can compress the numbers 15, 7, 7, and 11 in the bit string. The alternating runs of 0s and 1s consist of all bit-strings; we only compress the duration of the runs. In the following example, we get a 16-bit string:

1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1  (15 = 1111, then 7 = 0111, then 7 = 0111, then 11 = 1011) for a 16/40 = 40 percent compression ratio. We have to consider the following problems so that we can transform this definition into an efficient form of data compression:

• How many bits are we going to use to stock the numbers?
• What to do when a run is longer than the limit found?
• The number implied by this choice?
• What to do when the runs that are shorter than the amount of bits required for their duration to be stored?

We mainly focus on long bitstreams with very few short runs, so by making the following choices, we answer these questions:

• There are counts between 0 and 255, all of which are encoded with 8 bits.
• By including the runs of length 0 if desired, we make all run lengths less than 256.

Even though doing so could lengthen the production, we encode short runs,These choices for several types of bitstreams that are commonly encountered in practise are very simple to implement and also very effective. When short runs are numerous, they are not effective; we only keep bits on run when the run duration is greater than the amount of bits required to signify itself in binary notation.

Example:

RLE for bitmapped image data

RLE works in an alike manner to manuscript for bitmapped image encoding. Efficiency is dependent on the compression of the image; images with large pixel ranges of the similar colour will have a higher compression proportion than pictures that change colours often. On bitmapped images, there are various ways to use RLE: Bit level, Byte level, and Pixel level.

We consider bitmaps, which are commonly used to represent images and scanned documents, as an example of the efficiency of run length encoding. We ponder binary valued bitmaps, organised as bitstreams generated by taking the picture element in row major order, for brevity and simplicity. We use PictureDump to display the contents of a bitmap. It is a simple matter to write a programme to alter an image from one of the many prevalent lossless image formats specified for “screenshots” or scanned forms into a bitmap.

Working:

The casual definition just given leads instantly to the implementation of compress () and expand () function on the next section. As normal, the execution of expand () is the easiest of the others: read a run length, print the recent bit with several copies, match the current bit, and proceed until the input is exhausted. The compress () solution is not complicated, containing the subsequent steps when the input stream has bits:

Read a bit.

• Write the last bit as if it varies from the last bit read.
• Present count and the count are reset to zero. As if it is the same as reading the last bit and the count is supreme, write the count,
• Write a count of zero, and reset it to zero.
• Increase the count.

As the input stream drains, the input stream writes the Count (length of the last run) finishes the method.

The key reason why RLE is commonly used for bitmaps is as resolution increases, its usefulness increases intensely. It’s easy to see why it’s true here. Suppose we are doubling the resolution for our case.

The following facts are obvious then:

• By a feature of 4, the number of bits increases.
• Number of runs is increased by a feature of 2.
• Length of the run increases by a feature of about 2.
• The number of bits rises by around a factor of 2 in the compressed version.
• The compression ratio as a result is halved!

Without run-length encoding, when the resolution is doubled, space requirements increase by a factor of 4; with RLE space necessities for the compressed bitstream are only doubled when the resolution is doubled. That is, space expands and, with resolution, the compression ratio decreases linearly.

In many cases, run-length encoding is very effective, but there are many instances where the bitstream we want to compress (for example, standard English-language text) does not have any long runs in them.

Bit Level RLE (for pictures in black and white)

It is efficient when a single bit is used to signify the colour of every ground a pixel. An individual byte here signifies a pixel ‘s cost and the duration of run. The LMB (Left Most Bit) determines shade inside the 8 bits (e.g. 1 = white and 0 = Black) the run length is defined by the next 7 bits.

Example: 32-pixel segment from a monochrome bitmap:

The representation of the uncompressed will be

1111110000000000111111111111111111111111111111.

The starting six pixels indicate black when compressed, so the LMB in the initial byte of encoding will be 1 (in double quotation), followed by the binary 7 bit number showing 6.

“1”0000110

The secondary ten pixels are white in colour (in illustration below, see 0 in double quotation) and the next byte in the encoding will then be:

“0”0001010

For the last 16 black pixels, the full encoding is:

10000110 00001010 10010000 10010000110

32 bits are used in the original bitmap, while the bit level RLE used 24 bits. This encoding operates just because of comparatively lengthy sequences of Picture element that are successively coloured.

Byte level RLE-( for pictures of 256 colors)

Each picture element is signified by a single byte that offers 256 options. The colour table will be saved in an image file, codes for the colours that would be detailed. The colour palette is random and is defined by variables such as hardware, composition of the image or type of file. Then the data of the image is signified by couples of bytes on behalf of the duration of the run and then the colour of the run.

If the colour table for the sample specifies black is Sixteen, yellow is One Hundred and Twenty-Six, and blue as Twenty then the conforming bytes will be:

00000110 00010000 00001010 01111110 00010000 0001010000 0111110 00010000 0001010000

Flag byte may be implemented to avoid adverse compression, as with text compression.

Pixel level RLE (16.7 million pictures in color)

For an RGB bitmap, each pixel is signified by many bytes, i.e. four bytes. A run length byte will consist of each pair, tailed by the three bytes that It represents colour of the pixels.

For bitmap, the meta-data may contain rows and columns (e.g. 8*8), so it is easy and harmless to run over a row for RLE, i.e. to read from. The picture is encoded alike two blue picture element, four black picture element, three blue picture elements. The top-left picture element

Summary:

RLE is a very modest type of data compression in which the input (i.e.’AAABBCCCC’) is given as a stream of data and the productivity is a series of successive data values counted in a row (‘3A2B4C’). This form of data compression is lossless, which means that the data is returned to its original form after being decoded. Its effortlessness in both compression and decoding is one of the algorithm’s utmost appealing features.

The more consecutive values in a row, as you might have noted, the more space we save. On the other side, if you have a data sequence which switches between values often (“BEEF FADED”), then no space is going to be saved at all. In fact, since a single occurrence of a character results in two characters (‘A’ becomes ‘1A’) in the output of the encoding, we might also increase the size of our data.

RLE is suitable for some kinds of data and applications because of this. The Pixy camera, for example, that is a robotic camera that lets you simply monitor obstacles, uses RLE to encode labelled video data before moving it to an external application from the embedded camera system. Because of its ease, swiftness, and capacity to compress low entropy label data, this is the flawless encoding for the application like these.

References:

1. Adaptive Data Compression by Williams, Rose N. (Springer)
2. Algorithms Fourth Edition Part II BY Robert Sedgewick and Kevin Wayne
3. https://www.britannica.com/technology/telecommunication/Bit-mapping#ref608191
4. https://filestore.aqa.org.uk/resources/computing/AQA-8520-TG-RLE.PDF
5. https://en.wikipedia.org/wiki/Run-length_encoding#:~:text=Run%2Dlength%20encoding%20(RLE),than%20as%20the%20original%20run.
6. https://stackabuse.com/run-length-encoding/