Shannon Code Expected Length

Problem

Compute the expected codeword length of a Shannon code for the given symbol probabilities. Each symbol gets length ceil(-log2(p)), skipping symbols with p <= 0, and a probability of 1.0 gets length 0. Return the weighted sum sum(p * length).

Hint

Shannon's code assigns each symbol ceil(-log2 p) bits and is within one bit of the entropy.

Test cases

case 1

in: [[0.5,0.25,0.25]]

expected: 1.5

case 2

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

expected: 2

case 3

in: [[1]]

expected: 0

case 4

in: [[0,1]]

expected: 0

Starter codePython

import math
def shannon_expected_length(probs):
    # Your code here
    pass

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