Subword tokens by longest match

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

Example 1 · Input
un happi happy ness play ing ed s ly
unhappiness playing
Expected output
unhappiness: un happi ness
playing: play ing
Example 2 · Input
a ab abc
abcab
Expected output
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)}")

Lesson: Tokens and context windows →