Random variable entropy meter

ngram-entropy.py

#!/usr/bin/python3

from collections import defaultdict
from math import log

def entropy(n, sequence):
    """
    Estimates entropy of random sequence of elements
    based on ngram distribution.

    Args:
        n           order of ngram to be used
        sequence    sequence of random elements
    
    Return:
        Entropy in bits per element
    """
    ngram = (None,)*n
    ngram_counts = defaultdict(int)
    all_ngrams = 0
    for event in sequence:
        ngram = ngram[1:] + (event,)
        if not None in ngram:
            ngram_counts[ngram] += 1
            all_ngrams += 1

    entropy = sum(c/all_ngrams * log(c/all_ngrams, 0.5) for c in ngram_counts.values())
    return entropy / n