HardNLPnlp-235

Unigram Tokenization Report

Problem

Report on unigram tokenization of word with piece probabilities probs. Count every segmentation of word into vocabulary pieces and find the segmentation with the highest product of probabilities.

Return [count, loss] where loss is the negative log probability of the best segmentation. An empty word has one empty segmentation with loss 0.0, and a word with no segmentation returns [0, -1.0].

Hint

Track two DP arrays: one summing segmentation counts and one keeping the best log probability.

Test cases

case 1

in: ["abcd",{"a":0.5,"b":0.5,"c":0.5,"d":0.5,"ab":0.3,"cd":0.3,"abcd":0.1}]

expected: [5,2.3025850929940455]

case 2

in: ["a",{"a":0.4}]

expected: [1,0.916290731874155]

case 3

in: ["xyz",{"x":0.5,"y":0.5}]

expected: [0,-1]

case 4

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

expected: [1,0]

case 5

in: ["ab",{"a":0.5,"b":0.5,"ab":0.9}]

expected: [2,0.10536051565782628]

Starter codePython

import math
def unigram_tokenization_report(word, probs):
    # Your code here
    pass

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