Frequency-Weighted Next-Word Sampling
Learn this problem
GoogleNEW GRADPHONE SCREENProblem statement
Train a next-word model from several token sequences. Within each sequence, every adjacent pair contributes one observation from its first token to its second; sequence boundaries never create observations.
For query queries[i], let its observed successors be sorted lexicographically. Their frequencies form consecutive weighted ranges in that order. If the query has total successor observations, tickets[i] is an integer from 0 through total - 1; return the successor whose range contains that ticket. Thus a successor observed f times owns exactly f tickets.
If a query has no observed successor, its ticket is 0 and the answer is the empty string. Return one sampled word per query.
Function
sampleNextWords(training: String[][], queries: String[], tickets: int[]) → String[]Examples
Example 1
training = [["a","b","c"],["a","s","d"],["a","b","d"]]queries = ["a","b","x"]tickets = [2,1,0]return = ["s","d",""]After a, lexicographic successor ranges are b:[0,2) and s:[2,3). After b, c owns ticket 0 and d owns ticket 1. The unseen query x returns an empty string.
Example 2
training = [["go","left"],["go","right"],["go","right"]]queries = ["go","go","go"]tickets = [0,1,2]return = ["left","right","right"]Lexicographic order gives left the first ticket and right the next two tickets, matching their frequencies one and two.
Constraints
1 <= training.length, queries.length <= 100000- Each training sequence contains between
1and100000tokens. - The total number of training tokens and query tokens is at most
300000. - Every token contains
1to40printable ASCII characters. queries.length == tickets.length.- For a query with successor count
total > 0,0 <= tickets[i] < total; otherwisetickets[i] == 0.