MTF Entropy Estimate

Problem

Transform a sequence with move-to-front coding and then estimate its compressibility as the empirical Shannon entropy in bits of the rank sequence. Return 0.0 for an empty sequence. Use the given initial alphabet order for the move-to-front step.

Hint

Clustered symbols produce mostly low ranks, which lowers the entropy.

Test cases

case 1

in: [["a","a","a","a","a"],["a","b"]]

expected: 0

case 2

in: [["a","b","a","b","a","b"],["a","b"]]

expected: 0.6500224216483541

case 3

in: [[],["a","b"]]

expected: 0

case 4

in: [["a"],["a"]]

expected: 0

Starter codePython

import math
def mtf_entropy(seq, alphabet):
    # Your code here
    pass

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