Run-length encoding
Run-length encoding represents a sequence of equal values by storing the value and the extent of its repetition.
Runs: Adjacent equal values can share one representation. Arrow's run-end encoding stores cumulative end positions rather than separate run lengths, so an RLE label does not identify one interchangeable byte format. [3]
Blocks: A Zstandard RLE_Block carries one content byte. Its Block_Size field gives the number of decoded repetitions, not the encoded content size. The three-byte block header and frame overhead are additional. [2]
Hybrid: Parquet combines repeated-value runs with bit-packed groups. At width 3, eight copies of 5 give the hexadecimal run fragment 10 05: a count header followed by the repeated value. This excludes external width information and page framing. [1]
Framing: Parquet level streams prepend a four-byte encoded length in data page v1, but not v2. Dictionary indices omit that prefix in both versions; RLE Boolean streams retain it in both. The enclosing page and data kind select the rule. [1]
Relations
Limitations
- The decoder must enforce format-specific size limits before expanding a run into output. [2]
Citations
- Apache Parquet: RLE/bit-packing hybrid and deprecated BIT_PACKED encodings
- RFC 8878: Zstandard block header and RLE_Block, section 3.1.1.2
- Apache Arrow: Boolean, validity bitmap and run-end encoded layouts
Sources & caveats
- Source synthesis and exact illustrative bytes, not a compression-ratio or performance measurement. Run-length-limited recording codes are a separate concept.