This course's exercises so far skew OLTP (B-trees, WAL, MVCC, row-at-a-time locking) -- this one is squarely OLAP. Analytical column stores like DuckDB and ClickHouse spend a lot of effort shrinking each column, both to save disk space and because a smaller column is faster to scan (less I/O, more of it fits in cache). Two of the most common, complementary schemes:

• Dictionary encoding: map each DISTINCT value in the column to a small integer code, assigned in FIRST-SEEN order, and store the codes instead of the repeated original values. A "country" column with millions of rows but ~200 distinct values shrinks enormously this way.
• Run-length encoding (RLE): collapse a run of CONSECUTIVE repeats of the same value into one (value, count) pair. Columnar data is often sorted or naturally clustered, which is exactly the shape RLE compresses well.

Real engines usually chain the two: dictionary-encode first, then run-length-encode the resulting CODES (repeated values become repeated small integers, which is a great fit for RLE).

Implement:

• dictionary_encode(column) -> (codes, dictionary): dictionary is the list of distinct values in first-seen order; codes[i] is column[i]'s index into dictionary.
• dictionary_decode(codes, dictionary) -> the original column.
• run_length_encode(codes) -> a list of (value, count) tuples for consecutive runs.
• run_length_decode(runs) -> the original flat list.
• compress_column(column) -> {"dictionary": ..., "runs": ...} by chaining dictionary_encode then run_length_encode.
• decompress_column(compressed) -> the original column, reversing compress_column in the opposite order.

Example

dictionary_encode(["b", "a", "b", "c", "a"])
# -> ([0, 1, 0, 2, 1], ["b", "a", "c"])

run_length_encode([0, 0, 0, 1, 1, 0])
# -> [(0, 3), (1, 2), (0, 1)]   -- NOT [(0, 4), (1, 2)] -- the two "0"
#    runs are separated by a "1" and must stay separate runs

Constraints

• Dictionary codes are assigned in the order a value is FIRST seen, not sorted order.
• RLE only ever merges values that are ADJACENT in the sequence -- the same value reappearing later, after something else in between, starts a brand new run rather than extending the earlier one.
• compress_column's "runs" must be runs over the small integer CODES, not the raw column values.

Real-world grounding

• DuckDB's dictionary compression: src/storage/compression/dictionary_compression.cpp
• DuckDB's run-length encoding compression: src/storage/compression/rle.cpp

Real column stores go further: choosing WHICH compression scheme to apply per column/segment based on measured cardinality and run lengths rather than always applying both, bit-packing the codes/counts down to the minimum width that fits their range instead of using full machine words, and combining these with other schemes (FSST, bit-packing, delta encoding) -- but "map to small codes, then collapse runs of the same code" is the core idea behind both.