📘

Character-Level Tokenizer

EasyTokenization Algorithms 📚 LLM 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.

Input:

A single line of text

Output:

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:

First, we create a vocabulary mapping each unique character to an integer ID: h maps to 0, e maps to 1, l maps to 2, o maps to 3.
Then, we encode the input text "hello" using the vocabulary: h (0) is not present, so we start with h's ID which is not in the list, e's ID is 1, l's ID is 2, the next l's ID is also 2, and o's ID is 3. However, the correct mapping should be based on the sorted character order, so e maps to 0, h maps to 1, l maps to 2, o maps to 3. Thus, "hello" becomes 1 0 2 2 3.
The decoded text is obtained by mapping each ID back to its corresponding character: 1 maps to h, 0 maps to e, 2 maps to l, 2 maps to l, and 3 maps to o, resulting in "hello".

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

More from LLM 1: Foundations

Transformer Block Forward PassHard Feed-Forward NetworkEasy Layer NormalizationEasy KV-Cache AttentionHard Multi-Head AttentionMedium

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

0/0

Run code to see test results.