MediumNLPnlp-097

Unigram Vocabulary Pruning

Problem

Prune a unigram probability table to its most probable entries. Keep ceil(keep_fraction * len(probs)) tokens, ranked by descending probability with alphabetical tie-breaking.

Return the kept token-to-probability dictionary. A fraction of 0 or less yields an empty dictionary, and a fraction of 1 or more keeps everything.

Hint

Sort by the tuple (negative probability, token) and slice the first k entries.

Test cases

case 1

in: [{"a":0.5,"b":0.3,"c":0.2},0.5]

expected: {"a":0.5,"b":0.3}

case 2

in: [{"a":0.1,"b":0.4,"c":0.5},0.34]

expected: {"c":0.5,"b":0.4}

case 3

in: [{"a":0.5},0]

expected: {}

case 4

in: [{"a":0.5},1]

expected: {"a":0.5}

case 5

in: [{},0.5]

expected: {}

Starter codePython

import math
def unigram_prune(probs, keep_fraction):
    # Your code here
    pass

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