Length-Normalized Beam Search

Pick the best finished beam by length-normalised score $\text{score}\mathrm{/}{\text{len}}^{\alpha }\backslash text\{score\}/\backslash text\{len\}^\{\backslash alpha\}$ (a length of 0 counts as 1). beams is a list of (tokens, score) pairs. Ties are broken in favour of the lexicographically smaller token list. alpha must be non-negative and beams must not be empty (otherwise ValueError).

Implement solve(beams, alpha).

Returns. Return the winning (tokens, score) pair.

Examples

Example 1

Input:

solve([([1, 2], -3.0), ([3], -1.0)], 1.0)

Output:

([3], -1.0)

Example 2

Input:

solve([([1, 2, 3], -3.0), ([3], -2.0)], 1.0)

Output:

([1, 2, 3], -3.0)

Example 3

Input:

solve([([1, 2, 3], -3.0), ([3], -2.0)], 0.0)

Output:

([3], -2.0)