English
Menu

What is Run-length encoding?

A lossless compression method that shrinks data by replacing each stretch of the same value (a run) with a pair of that value and the length of the run. For example, the black-and-white pixel sequence 0000000011110000 can be written as "eight 0s, four 1s, four 0s". It works well on data in which the same value continues for a long time, such as drawings on a mostly white background, fax images and images with large areas of a single color. On data whose values change finely, the runs are short and the result can even be larger than the original. Also called RLE.

Japanese name: ランレングス符号化

Run-length encoding appears in 2 practice questions across 1 topic, including Information Theory and Coding Basics.

Field: Information Theory and Coding Basics

Try it: questions about Run-length encoding

The 40-character string AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD (12 As, 4 Bs, 20 Cs and 4 Ds) is compressed with run-length encoding, which represents each run of the same character as a pair of "character (1 byte) and count (1 byte)". The original string uses 1 byte per character. Defining the compression ratio as "size after compression ÷ size before compression", which of the following is the compression ratio?

  1. A10%
  2. B20%
  3. C80%
Show answer and explanation

Answer: B. 20%

There are four runs of the same character, A, B, C and D, so the compressed data are 4 × 2 = 8 bytes. The original is 40 bytes, so the compression ratio is 8 ÷ 40 = 0.2, that is, 20%. Run-length encoding shrinks data better the longer the same value continues.

Which of the following data is most likely to be made smallest by run-length encoding?

  1. AA drawing of black lines on a white background, represented as a two-level black-and-white image
  2. BAn image such as a photograph, in which the values of neighboring pixels change finely
  3. CData after encryption, in which 0s and 1s appear to be arranged at random
Show answer and explanation

Answer: A. A drawing of black lines on a white background, represented as a two-level black-and-white image

Run-length encoding represents the length of a run of the same value as a number, so data in which the same value continues for a long time shrink the most. In a two-level drawing with a mostly white background, white pixels continue for long stretches, so the effect is large; fax coding also uses this idea. In data whose values change finely, the runs are short and the result can even be larger than the original.

Run-length encoding in the explanations

Questions that mention Run-length encoding (2)

  1. The 40-character string AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD (12 As, 4 Bs, 20 Cs and 4 Ds) is compressed with run-length encoding, which represents each run of the same character as a pair of "character (1 byte) and count (1 byte)". The original string uses 1 byte per character. Defining the compression ratio as "size after compression ÷ size before compression", which of the following is the compression ratio?
  2. Which of the following data is most likely to be made smallest by run-length encoding?

Books on Information Theory and Coding Basics Ad

As an Amazon Associate I earn from qualifying purchases.

Related terms

Average code length Binary symmetric channel Forward error correction (FEC) Hamming code Hamming distance Huffman coding Information entropy Kraft inequality Lossless compression Lossy compression

Back to the glossary