Haskell中Run Length Encoding的编码与解码实现优化问询

Hey there! Great job getting Run Length Encoding (RLE) up and running already—let’s dive into some tweaks and optimizations that can make your implementation cleaner, more efficient, and more robust. Below are targeted suggestions for both encoding and decoding functions, with code examples to illustrate the improvements.

Key Improvements to Focus On #

• Single-pass iteration: Avoid redundant scans of the input string to cut time complexity to O(n).
• Efficient string building: Use a list to collect encoded segments instead of repeated string concatenation (strings are immutable in most languages, so this reduces overhead).
• Clean edge case handling: Explicitly manage empty inputs, single-character strings, and non-repeating characters.

Example Implementation (Python) #

def optimized_rle_encode(input_str):
    if not input_str:
        return ""
    
    encoded_segments = []
    current_char = input_str[0]
    char_count = 1
    
    for char in input_str[1:]:
        if char == current_char:
            char_count += 1
        else:
            # Append segment: only include count if it's greater than 1 for compactness
            encoded_segments.append(f"{current_char}{char_count}" if char_count > 1 else current_char)
            current_char = char
            char_count = 1
    
    # Don't forget to add the final segment
    encoded_segments.append(f"{current_char}{char_count}" if char_count > 1 else current_char)
    
    return "".join(encoded_segments)

Key Improvements to Focus On #

• Regex pattern matching: Cleanly parse encoded segments (either [count][char] or single char) without manual string slicing.
• Robust error handling: Validate the input format to catch invalid RLE strings early and provide meaningful error messages.
• Batch string construction: Again, use a list to build the decoded output for better performance with large inputs.

Example Implementation (Python) #

import re

def robust_rle_decode(encoded_str):
    if not encoded_str:
        return ""
    
    decoded_segments = []
    # Regex pattern: matches either (one+ digits + non-digit) OR a single non-digit
    rle_pattern = re.compile(r'(\d+)(\D)|(\D)')
    matches = list(rle_pattern.finditer(encoded_str))
    
    # Verify the entire input was parsed (catch invalid trailing characters)
    total_parsed_length = sum(len(match.group()) for match in matches)
    if total_parsed_length != len(encoded_str):
        invalid_segment = encoded_str[total_parsed_length:]
        raise ValueError(f"Invalid RLE format starting at position {total_parsed_length}: '{invalid_segment}'")
    
    for match in matches:
        try:
            if match.group(1):
                # Handle segments with a count
                count = int(match.group(1))
                char = match.group(2)
                decoded_segments.append(char * count)
            else:
                # Handle single characters
                decoded_segments.append(match.group(3))
        except ValueError as e:
            raise ValueError(f"Invalid count in RLE segment at position {match.start()}: '{match.group()}'") from e
    
    return "".join(decoded_segments)

Bonus Tips #

• Case sensitivity: If your use case requires case-insensitive encoding, add a normalization step (e.g., input_str.lower()) before processing.
• Binary data support: For non-text inputs (like images), adapt the functions to work with byte arrays instead of strings—logic remains similar, but you’ll handle bytes instead of characters.
• Performance testing: For large inputs, benchmark your implementation against these optimized versions to see the speed gains (especially with list-based string building).

内容的提问来源于stack exchange，提问作者Alexia Desouza