One-Hot Sequence Encoder
Given a vocabulary and a sequence of words, encode each word as a one-hot vector.
Input format:
- Line 1: Comma-separated vocabulary (sorted)
- Line 2: Space-separated words to encode
Each word becomes a vector of length |vocab| with 1 at the word's index and 0 elsewhere. If a word is not in the vocabulary, use all zeros.
Output: One vector per line as a list.
Example:
cat,dog,fish dog cat fish
[0, 1, 0] [1, 0, 0] [0, 0, 1]
Step 1: Build vocabulary index cat=0, dog=1, fish=2
Step 2: Encode each word "dog" → index 1 → [0, 1, 0] "cat" → index 0 → [1, 0, 0] "fish" → index 2 → [0, 0, 1]
Constraints:
- Vocabulary is comma-separated and sorted
- Each output vector has length = vocabulary size
- Unknown words get all-zero vectors
- Output each vector as a Python list
Background Knowledge
The problem involves Natural Language Processing (NLP), specifically sequence processing, where we deal with sequences of words or tokens. A key concept here is the vocabulary, which is the set of unique words in our dataset. In this problem, we're given a sorted vocabulary and a sequence of words to encode. One-hot encoding is a technique used to represent categorical data, such as words, as numerical vectors. This is useful for feeding data into machine learning models.
In the context of NLP, one-hot encoding is often used to represent words as vectors, where each word is associated with a unique vector. The vector has a length equal to the size of the vocabulary, with a 1 at the index corresponding to the word and 0s elsewhere. For example, if our vocabulary is [apple, banana, cherry], the one-hot encoding for apple would be [1, 0, 0]. This representation allows us to treat words as numerical data, enabling us to perform mathematical operations and feed them into machine learning models.
The problem also involves sequence processing, where we need to handle a sequence of words and encode each word individually. This requires us to iterate over the sequence, look up each word in the vocabulary, and generate the corresponding one-hot vector. If a word is not in the vocabulary, we need to handle this case by generating a vector of all zeros.
Algorithm/Approach
The general approach to solving this problem involves the following algorithm pattern:
- Iterate over the input sequence of words
- For each word, look up its index in the vocabulary
- Generate the one-hot vector based on the index
- Handle cases where the word is not in the vocabulary This approach involves basic data structures, such as lists or arrays, and simple iteration and lookup operations.
Step-by-Step Strategy
To implement the solution, follow these steps:
- Read the input vocabulary and sequence of words
- Split the vocabulary into a list of words and store it in a data structure
- Iterate over the sequence of words to encode
- For each word, check if it exists in the vocabulary
- If the word exists, generate its one-hot vector based on its index in the vocabulary
- If the word does not exist, generate a vector of all zeros
- Output the one-hot vector for each word
Common Pitfalls
When implementing the solution, watch out for the following:
- Incorrectly handling cases where the word is not in the vocabulary
- Failing to initialize the one-hot vector with the correct length
- Incorrectly indexing into the vocabulary or one-hot vector
- Not handling edge cases, such as an empty vocabulary or sequence
Time & Space Complexity
The expected time complexity for this problem is O(n×m), where n is the length of the sequence and m is the size of the vocabulary. This is because we need to iterate over the sequence and for each word, look up its index in the vocabulary. The space complexity is O(m), as we need to store the vocabulary and the one-hot vectors. However, the actual space complexity may be higher if we store the output vectors, which would be O(n×m).