Character-Level Tokenizer

easyFREETokenization AlgorithmsLLM 1: Foundations

Build a character-level tokenizer that converts text to token IDs and back.

Given a text string, build a vocabulary mapping each unique character to an integer ID (sorted by character order, starting from 0). Then encode the text as a list of IDs and decode it back.

Implement char_tokenizer(text) that returns a tuple (encoded_ids, decoded_text): a list of integer IDs and the decoded string.

Input:

A single line of text

Output (as printed by the tests):

Line 1: The encoded token IDs (space-separated)
Line 2: The decoded text (should match input)

Example

Input

hello

Output

1 0 2 2 3
hello

Reasoning

The input is the string hello: five characters, but only four distinct ones, since l appears twice.
The vocabulary orders the distinct characters by Unicode code point: e $=101$ , h $=104$ , l $=108$ , o $=111$ . Numbering them from 0 gives e $\to 0$ , h $\to 1$ , l $\to 2$ , o $\to 3$ .
Encoding replaces each character of the text, in its original position, with its ID: h, e, l, l, o becomes $1, 0, 2, 2, 3$ , which is the first output line 1 0 2 2 3.
Decoding reads the same table in the other direction: $1 \to$ h, $0 \to$ e, $2 \to$ l, $2 \to$ l, $3 \to$ o, giving back hello.
Notice that the IDs follow alphabetical order, not order of first appearance. That is why h, the first letter, gets ID 1 rather than 0. Repeated characters share one ID, so the vocabulary size is 4 while the encoded list has length 5. A space would get an ID too (code point 32, so it sorts before any letter).

Constraints

Characters are sorted by their Unicode code point for ID assignment
IDs start from 0
Space characters are included in the vocabulary
Output IDs space-separated on line 1, decoded text on line 2

Learn this in

Tokenization & EmbeddingsLLM Study Plan NLP FundamentalsML Study Plan Text PreprocessingNLP Study Plan

More from LLM 1: Foundations

Transformer Block Forward Passhard Feed-Forward Networkeasy Layer Normalizationeasy KV-Cache Attentionhard Multi-Head Attentionmedium

Concept primer

Background Knowledge

The problem of building a character-level tokenizer involves understanding the basics of tokenization, which is a fundamental step in natural language processing (NLP). Tokenization is the process of breaking down text into individual units, called tokens, which can be characters, words, or subwords. In this case, we are dealing with character-level tokenization, where each character in the text is treated as a separate token. The goal is to create a vocabulary that maps each unique character to a unique integer ID.

To approach this problem, it's essential to understand the concept of encoding and decoding. Encoding refers to the process of converting text into a numerical representation, while decoding is the reverse process of converting numerical representation back into text. In the context of character-level tokenization, encoding involves replacing each character with its corresponding integer ID, and decoding involves replacing each integer ID with its corresponding character. This process relies on a mapping between characters and their IDs, which needs to be consistent for both encoding and decoding.

The problem also touches on the idea of sorting and ordering, as the vocabulary is required to be sorted by character order. This means that the integer IDs should be assigned in a way that preserves the alphabetical order of the characters. Understanding how to create and manage this mapping is crucial to solving the problem.

Algorithm/Approach

The general approach to solving this problem involves creating a character-to-ID mapping and then using this mapping to encode and decode the text. This can be achieved through a combination of string manipulation and data structure operations. The algorithm pattern that emerges from this problem is one of mapping and lookup, where we create a mapping between characters and IDs and then use this mapping to perform the encoding and decoding operations.

Step-by-Step Strategy

To implement the solution, follow these steps:

Create a set or dictionary to store unique characters from the input text.
Sort the unique characters in alphabetical order.
Assign a unique integer ID to each character, starting from 0.
Use the created mapping to encode the input text by replacing each character with its corresponding ID.
Use the same mapping to decode the encoded IDs back into the original text.

Common Pitfalls

Things to watch out for include:

Ensuring that the mapping between characters and IDs is consistent and correctly implemented.
Handling cases where the input text contains special characters or non-alphabetical characters.
Preserving the original order of characters during the encoding and decoding process.

Time & Space Complexity

The expected time complexity for this problem is $O(n \log n)$ due to the sorting operation, where $n$ is the number of unique characters in the input text. The space complexity is $O(n)$ , as we need to store the mapping between characters and IDs. However, in the worst-case scenario where all characters in the input text are unique, the time complexity could be $O(m \log m)$ and the space complexity could be $O(m)$ , where $m$ is the length of the input text.

solution.py

Python 3.13

Test results