Greedy Longest-Match Tokenization of a String Against a Fixed Vocabulary
Company: Anthropic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A tokenizer splits text into tokens drawn from a fixed vocabulary. You are given a string `text` and a list `vocab` of distinct, non-empty strings. The token ID of `vocab[i]` is `i`.
Tokenize `text` with the **greedy longest-match** rule: start at the beginning of `text`; at the current position, choose the longest vocabulary string that `text` continues with at that position, emit its token ID, and move the position forward by that string's length. Repeat until the whole of `text` has been consumed.
Return the list of emitted token IDs, in order.
### Function Signature
```python
def longest_match_tokenize(text: str, vocab: list[str]) -> list[int]:
```
### Rules
- The choice at each position is always the longest matching vocabulary string, even when a different choice would produce fewer tokens overall.
- Because vocabulary strings are distinct, the longest match at a position is unique, so the output is uniquely determined.
- Matching is exact and case-sensitive; spaces and punctuation are ordinary characters.
### Constraints
- `1 <= len(text) <= 100000`
- `1 <= len(vocab) <= 10000`
- `1 <= len(vocab[i]) <= 50` for every `i`, and the total length of all vocabulary strings is at most `200000`.
- All vocabulary strings are distinct.
- `text` and every vocabulary string consist of printable ASCII characters (character codes 32 to 126 inclusive).
- Every character that occurs in `text` is also present in `vocab` as a single-character string, so tokenization never gets stuck.
- The output has between `1` and `len(text)` token IDs, each in the range `0` to `len(vocab) - 1`.
### Examples
**Example 1**
- Input: `text = "abcab"`, `vocab = ["a", "b", "c", "ab", "abc"]`
- Output: `[4, 3]`
- Explanation: At position 0 the candidates are `"a"`, `"ab"` and `"abc"`; the longest is `"abc"` (ID 4). At position 3 the candidates are `"a"` and `"ab"`; the longest is `"ab"` (ID 3).
**Example 2**
- Input: `text = "abcd"`, `vocab = ["a", "b", "c", "d", "ab", "bcd"]`
- Output: `[4, 2, 3]`
- Explanation: At position 0 the longest match is `"ab"`, leaving `"cd"`, which is tokenized as `"c"` then `"d"`. The split `"a"` + `"bcd"` would use only two tokens, but greedy longest-match never looks ahead.
**Example 3**
- Input: `text = "to be"`, `vocab = [" ", "b", "e", "o", "t", "to", "be", " b"]`
- Output: `[5, 7, 2]`
- Explanation: `"to"` (ID 5) is the longest match at position 0, `" b"` (ID 7) beats `" "` at position 2, and `"e"` (ID 2) remains.
Overview: Tokenize a string against a fixed vocabulary by repeatedly taking the longest vocabulary entry that matches at the current position, and return the token IDs in order. It tests exact greedy semantics, efficient prefix matching over up to 100,000 characters, and careful handling of overlapping vocabulary entries.
A tokenizer splits text into tokens drawn from a fixed vocabulary. You are given a string `text` and a list `vocab` of distinct, non-empty strings. The token ID of `vocab[i]` is its index `i`.
Tokenize `text` with the **greedy longest-match** rule:
1. Start at position 0 of `text`.
2. Among all vocabulary strings that `text` continues with at the current position, choose the **longest** one.
3. Emit its token ID and advance the position by that string's length.
4. Repeat until all of `text` has been consumed.
Return the emitted token IDs as a list, in the order they were emitted.
**Rules**
- The choice at each position is always the longest matching vocabulary string, even when a different choice would produce fewer tokens overall. Greedy longest-match never looks ahead.
- Vocabulary strings are distinct, so the longest match at a position is unique and the output is uniquely determined.
- Matching is exact and case-sensitive; spaces, quotes, backslashes and other punctuation are ordinary characters.
- Every character of `text` appears in `vocab` as a single-character string, so tokenization never gets stuck.
**Example 1**
```
Input: text = "abcab", vocab = ["a", "b", "c", "ab", "abc"]
Output: [4, 3]
```
At position 0 the matching strings are `"a"`, `"ab"` and `"abc"`; the longest is `"abc"` (ID 4). At position 3 the matching strings are `"a"` and `"ab"`; the longest is `"ab"` (ID 3).
**Example 2**
```
Input: text = "abcd", vocab = ["a", "b", "c", "d", "ab", "bcd"]
Output: [4, 2, 3]
```
At position 0 the longest match is `"ab"` (ID 4), leaving `"cd"`, which becomes `"c"` (ID 2) then `"d"` (ID 3). The split `"a"` + `"bcd"` would use only two tokens, but greedy longest-match does not look ahead.
**Example 3**
```
Input: text = "to be", vocab = [" ", "b", "e", "o", "t", "to", "be", " b"]
Output: [5, 7, 2]
```
`"to"` (ID 5) is the longest match at position 0, `" b"` (ID 7) beats `" "` at position 2, and `"e"` (ID 2) remains.
**Constraints**
- `1 <= len(text) <= 100000`
- `1 <= len(vocab) <= 10000`
- `1 <= len(vocab[i]) <= 50` for every `i`, and the total length of all vocabulary strings is at most `200000`.
- All vocabulary strings are distinct.
- `text` and every vocabulary string consist of printable ASCII characters (character codes 32 to 126 inclusive).
- Every character that occurs in `text` is also present in `vocab` as a single-character string.
- The output has between `1` and `len(text)` token IDs, each in the range `0` to `len(vocab) - 1`. Every value involved fits in a signed 32-bit integer.
Constraints
- 1 <= len(text) <= 100000
- 1 <= len(vocab) <= 10000
- 1 <= len(vocab[i]) <= 50 for every i, and the total length of all vocabulary strings is at most 200000
- All vocabulary strings are distinct
- text and every vocabulary string consist of printable ASCII characters (character codes 32 to 126 inclusive)
- Every character that occurs in text is also present in vocab as a single-character string
- The output has between 1 and len(text) token IDs, each in the range 0 to len(vocab) - 1
Examples
Input: ('abcab', ['a', 'b', 'c', 'ab', 'abc'])
Expected Output: [4, 3]
Input: ('abcd', ['a', 'b', 'c', 'd', 'ab', 'bcd'])
Expected Output: [4, 2, 3]
Hints
- Checking every vocabulary string at every position is too slow when both text and vocab are large. Many vocabulary strings share prefixes; look for a structure that tests all strings with a common prefix in one pass.
- When you follow characters of text forward from the current position, the walk can go past the end of a valid vocabulary string and then fail. Keep track of the most recent point where a complete vocabulary string ended.
- No vocabulary string is longer than 50 characters, so the work done at each position is bounded by a small constant.
Community answers
Answer by shail.finaspirant
def longest_match_tokenize(text: str, vocab: list[str]) -> list[int]:
ans = []
vdict = {v:i for i, v in enumerate(vocab)}
i = 0
n = len(text)
while i < n:
currlen = min(50,n-i)
for L in range(currlen,0,-1):
currstr = text[i:i+L]
if currstr in vdict:
ans.append(vdict[currstr])
i += L
break
return ans