Code Redundancy Fraction

Problem

Compute the redundancy fraction of a code, (L - H) / L, where H is the source entropy in bits and L is the expected codeword length. Probabilities are normalized before use and zero-probability symbols are skipped. Return 0.0 when L equals 0.

Hint

Compute H and L over the normalized probabilities, then divide the gap by L.

Test cases

case 1

in: [[0.5,0.25,0.25],[1,2,2]]

expected: 0

case 2

in: [[0.5,0.5],[1,2]]

expected: 0.3333333333333333

case 3

in: [[1],[0]]

expected: 0

case 4

in: [[1,1],[2,2]]

expected: 0.5

Starter codePython

import math
def code_redundancy(probs, lengths):
    # Your code here
    pass

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