Module dsi_bitstream::codes::minimal_binary

Minimal binary codes.

A minimal binary code with upper bound u > 0 (AKA truncated binary encoding) is an optimal prefix-free code for the first u natural numbers with uniform distribution.

There are several such prefix-free codes, and the one implemented here is defined as follows: if s = ⌊log₂u⌋, then the first 2^(s+1) - u codewords are the first binary numbers of length s – 1, and the remaining codewords are the last 2u - 2^(s+1) binary numbers of length s.

Traits

• MinimalBinaryRead
  Trait for reading minimal binary codes.
• MinimalBinaryWrite
  Trait for writing minimal binary codes.

Functions

• len_minimal_binary
  Return the length of the minimal binary code for n with upper bound max.