# Run Length Encoding & Dictionary Coding ## What is run length encoding? - Run length encoding (RLE) is a **lossless compression technique** that reduces file size by condensing consecutive identical elements - The method replaces sequences of repeating data with a **single value and a count** of how many times it repeats

Run Length Encoding (RLE) compresses data by storing a count and value for consecutive identical elements

- Works by identifying **runs** of identical data and representing them more efficiently - Particularly effective when data contains long sequences of repeated values ### RLE in text compression - Consider the text string: `WWWWWWAAABBBBCCDDDDDD` - RLE compresses this to: `6W3A4B2C6D` - The compressed version stores the count before each character - Original string: 22 characters - Compressed string: 12 characters - Achieved approximately 45% reduction in size ### RLE in image compression - Commonly used for **bitmap images** where pixels of the same colour appear consecutively - A horizontal line in an image with 8 yellow pixels followed by 5 green pixels becomes `8Y5G` - Especially effective for: - Simple graphics with large areas of solid colour - Line drawings - Icons and logos - Images with limited colour palettes ### Limitations of RLE - **Ineffective** when data has little or no repetition - Can actually **increase file size** if the data is highly varied - Example: `ABCDEFGH` would compress to `1A1B1C1D1E1F1G1H` - doubling the size - Best suited for data with significant consecutive repetition ## What is dictionary coding? - Dictionary coding is a **lossless compression method** that replaces frequently occurring sequences with shorter codes - A **dictionary** (lookup table) is built to map original data sequences to replacement codes - The dictionary is stored alongside the compressed data for decompression

Dictionary coding compresses data by replacing recurring patterns with shorter codes from a lookup table

### How dictionary coding works 1. Scan the original data to identify **frequently occurring patterns** 2. Create a **dictionary** assigning short codes to these patterns 3. Replace patterns in the data with their corresponding codes 4. Store both the dictionary and coded data ### Key features - Effective for both **text and binary data** - Works well when patterns repeat throughout the data - The dictionary itself adds some overhead, so only worthwhile for sufficiently repetitive data - More versatile than RLE but requires more computational resources ## Example of dictionary coding Consider this sentence describing programming languages: ```text Python is versatile but JavaScript is popular and Python syntax is clean while JavaScript syntax is flexible ``` ### Step 1: Identify repeated sequences - "Python" appears 2 times - "JavaScript" appears 2 times - "syntax is" appears 2 times ### Step 2: Build the dictionary | Original Sequence | Code | |-------------------|------| | Python | P | | JavaScript | J | | syntax is | SI | ### Step 3: Replace sequences with codes Original (104 characters): ```text Python is versatile but JavaScript is popular and Python syntax is clean while JavaScript syntax is flexible ``` Compressed (79 characters): ```text P is versatile but J is popular and P SI clean while J SI flexible ``` ### Analysis - Original message: 104 characters - Compressed message: 79 characters - Space saved: 25 characters (24% reduction) - The dictionary must be stored/transmitted alongside the compressed data - Receiver uses the dictionary to restore the original message ### Dictionary coding for binary data - The binary sequence `11001100` could be replaced by a shorter unique code - Useful when certain bit patterns repeat throughout a file - Common in file compression formats like **ZIP** and **GIF** ## Comparing RLE and dictionary coding | Feature | Run Length Encoding | Dictionary Coding | |---------|---------------------|-------------------| | **Best used for** | Data with long runs of identical values | Data with repeated patterns or sequences | | **Compression method** | Count + value pairs | Pattern substitution using lookup table | | **Overhead** | Minimal | Dictionary must be stored | | **Computational complexity** | Low (simple algorithm) | Higher (pattern matching required) | | **Effectiveness** | Excellent for repetitive data, poor for varied data | Good for patterned data, flexible | | **Example use case** | Simple graphics, fax transmissions | Text files, general file compression |

RLE excels with consecutive repetition; dictionary coding excels with repeated patterns anywhere in the data

### When to use RLE - Data contains long sequences of identical consecutive elements - Need for **fast compression** with minimal computational overhead - Simple images or graphics - Data transmission where speed is critical ### When to use dictionary coding - Data contains **repeated patterns** that aren't necessarily consecutive - Willing to accept higher computational cost for better compression - Text documents with repeated words or phrases - General-purpose file compression ## Worked examples ### Example 1: Traffic monitoring system A traffic monitoring system records vehicle types passing a checkpoint. Each vehicle type is coded: - Car = `C` - Motorbike = `M` - Bus = `B` - Truck = `T` The following sequence represents vehicles detected over 10 minutes: ```text CCCCMMMMMCCCCCCCBCCCCC ``` **Using RLE, compress this sequence.** **Solution:** Break down the consecutive runs: - 4 cars (`CCCC`) - 5 motorbikes (`MMMMM`) - 7 cars (`CCCCCCC`) - 1 bus (`B`) - 5 cars (`CCCCC`) **Compressed result:** `4C5M7C1B5C` **Analysis:** - Original: 22 characters - Compressed: 10 characters - Reduction: 55% --- ### Example 2: Decompressing RLE data The traffic system has compressed another sequence using RLE: ```text 2T6C3M1B8C ``` **Show the result of decompressing this sequence.** **Solution:** Expand each count-value pair: - `2T` → `TT` - `6C` → `CCCCCC` - `3M` → `MMM` - `1B` → `B` - `8C` → `CCCCCCCC` **Decompressed result:** `TTCCCCCCMMMBC CCCCCCCC` --- ### Example 3: Implementing RLE in pseudocode **Write a function named `compress` that takes a string of vehicle codes and returns the RLE compressed version.** For example: `compress("CCCMMCC")` should return `"3C2M2C"` **Solution:** ```pseudocode function compress(data: String) -> String: if data is empty: return "" compressed = "" current_char = data[0] count = 1 for i from 1 to length(data) - 1: if data[i] equals current_char: count = count + 1 else: compressed = compressed + str(count) + current_char current_char = data[i] count = 1 // Add the last run compressed = compressed + str(count) + current_char return compressed endfunction ``` **How it works:** 1. Initialize with the first character and count of 1 2. Iterate through remaining characters 3. If current character matches, increment count 4. If different, append count+character to result and reset 5. Don't forget to add the final run after the loop **Alternative Python implementation:** ```python def compress(data): if not data: return "" compressed = "" current_char = data[0] count = 1 for char in data[1:]: if char == current_char: count += 1 else: compressed += str(count) + current_char current_char = char count = 1 compressed += str(count) + current_char return compressed ``` --- ### Example 4: Finding longest sequence **Write a function named `longest_run` that takes a string of vehicle codes and returns the length of the longest consecutive sequence of cars (C).** For example: `longest_run("MCCCTMCCCCCM")` should return `5` **Solution:** ```pseudocode function longest_run(data: String) -> Integer: max_length = 0 current_length = 0 for each character in data: if character equals 'C': current_length = current_length + 1 if current_length > max_length: max_length = current_length else: current_length = 0 return max_length endfunction ``` **Trace through example `"MCCCTMCCCCCM"`:** | Position | Character | current_length | max_length | |----------|-----------|----------------|------------| | 0 | M | 0 | 0 | | 1 | C | 1 | 1 | | 2 | C | 2 | 2 | | 3 | C | 3 | 3 | | 4 | T | 0 | 3 | | 5 | M | 0 | 3 | | 6 | C | 1 | 3 | | 7 | C | 2 | 3 | | 8 | C | 3 | 3 | | 9 | C | 4 | 4 | | 10 | C | 5 | 5 | | 11 | M | 0 | 5 | **Result: 5** --- ## Advantages and limitations ### Run Length Encoding **Advantages:** - Extremely simple to implement - Fast compression and decompression - No dictionary overhead - Deterministic - same input always produces same output - Works well for data with long consecutive runs **Limitations:** - Ineffective for data without repetition - Can increase file size if data is too varied - Only compresses consecutive identical values - Not suitable for complex data patterns ### Dictionary Coding **Advantages:** - Detects patterns throughout entire data set (not just consecutive) - More flexible and versatile than RLE - Effective for text and binary data - Can achieve significant compression ratios - Forms the basis of many popular compression algorithms **Limitations:** - More computationally expensive - Dictionary adds storage overhead - Requires pattern analysis phase - More complex to implement - Dictionary must be transmitted/stored with compressed data

Both methods only work for lossless compression - the original data can be perfectly reconstructed

## Real-world applications ### RLE applications - **Fax transmission** - documents have long runs of white and black pixels - **Simple graphics formats** - PCX, BMP formats use RLE - **Video compression** - used within more complex codecs for frame data - **Data storage** - databases use RLE for storing columnar data ### Dictionary coding applications - **ZIP compression** - uses dictionary-based algorithms (DEFLATE) - **GIF images** - LZW dictionary coding - **Network protocols** - HTTP compression - **Text compression** - document archiving systems - **Database compression** - column-store databases