Rare words can be built from common pieces. Split words into subword tokens with greedy longest matching.
What to build
A program that tokenizes words into the longest matching vocabulary pieces.
Requirements
- From the start of each word, take the longest piece of the vocabulary that matches at the current position, then continue after it.
- If no piece matches, output
[UNK]for that character and move on by one character. - Print one line per word:
WORD: T1 T2 ....
Input
Line 1: the vocabulary pieces. Line 2: the words.
Output
One line per word.
Constraints
1 to 1000 pieces; 1 to 100 words, each at most 50 characters.
Example
Input:
un happi happy ness play ing ed s ly
unhappiness playing
Output:
unhappiness: un happi ness
playing: play ing
Why it works
Taking the longest piece first uses the biggest known chunks, so common words stay whole and rare words split into as few pieces as this method can find.
Examples
un happi happy ness play ing ed s ly unhappiness playing
unhappiness: un happi ness playing: play ing
a ab abc abcab
abcab: abc ab
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
At each position, try the longest remaining slice first and shrink it until a slice is a vocabulary piece.
Hint 2
If no slice matches, output [UNK] for that one character and move on by one.
Solution
Show one correct solution (try it yourself first)
pieces = set(input().split())
for word in input().split():
tokens, i = [], 0
while i < len(word):
for j in range(len(word), i, -1):
if word[i:j] in pieces:
tokens.append(word[i:j])
i = j
break
else:
tokens.append("[UNK]")
i += 1
print(f"{word}: {' '.join(tokens)}")