HardNLPnlp-098

WordPiece Segmentation Score

Problem

Return the best WordPiece segmentation score for a word: the maximum sum of log piece probabilities over all valid segmentations.

A piece starting the word uses its plain form as the dictionary key, while every later piece must use the continuation form prefixed with '##'. Return 0.0 when no full segmentation exists or the word is empty.

Hint

dp[i] is the best score for the prefix of length i; only position 0 may use a non-continuation piece.

Test cases

case 1

in: ["ab",{"a":0.5,"b":0.5,"##b":0.4,"ab":0.3}]

expected: -1.2039728043259361

case 2

in: ["abc",{"a":0.5,"##b":0.5,"##c":0.5}]

expected: -2.0794415416798357

case 3

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

expected: 0

case 4

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

expected: 0

case 5

in: ["hello",{"hel":0.5,"##lo":0.25,"h":0.9,"##ello":0.9}]

expected: -0.21072103131565256

Starter codePython

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

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