Shannon-Fano Average Length

Problem

Build a Shannon-Fano code from probabilities given in descending order. Recursively split the list at the index k that minimizes the absolute difference between the sum of the first k probabilities and the rest, breaking ties toward the smaller k, and give every symbol one more bit per recursion level. Return the probability-weighted average codeword length, 0.0 for fewer than two symbols, and 0.0 for an empty list.

Hint

Each recursive split adds one bit to every symbol on both sides.

Test cases

case 1

in: [[0.5,0.5]]

expected: 1

case 2

in: [[1]]

expected: 0

case 3

in: [[0.4,0.3,0.2,0.1]]

expected: 1.9

case 4

in: [[0.25,0.25,0.25,0.25]]

expected: 2

Starter codePython

def shannon_fano_average_length(probs):
    # Your code here
    pass

4 test cases · run your code against them in the editor