One-Hot Sequence Encoder

easyFREESequence ProcessingNLP 2: Applications

Given a vocabulary and a sequence of words, encode each word as a one-hot vector.

Input:

vocab: list of vocabulary words (sorted); a word's index is its position in this list
words: list of 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: A list of vectors (one list of 0s and 1s per input word, in the same order as words).

Example

Input

cat,dog,fish
dog cat fish

Output

[0, 1, 0]
[1, 0, 0]
[0, 0, 1]

Reasoning

Inputs: vocab is the ordered list cat, dog, fish, so $|V| = 3$ and each word's position is fixed by that order: cat $\to 0$ , dog $\to 1$ , fish $\to 2$ . words is the sequence dog cat fish to encode.
The math: a word at vocabulary position $i$ maps to the standard basis vector $e_i \in \{0,1\}^{|V|}$ , whose entry $k$ is $1$ if $k = i$ and $0$ otherwise.
Worked through: "dog" sits at position $1$ , giving $e_1 =$ [0, 1, 0]; "cat" at position $0$ gives $e_0 =$ [1, 0, 0]; "fish" at position $2$ gives $e_2 =$ [0, 0, 1].
Output: one vector per input word, in the order the words appear, each of length $|V| = 3$ and summing to exactly $1$ .
Notice that stacking the three rows gives a permutation of the $3 \times 3$ identity matrix, because each vocabulary word appears once. A repeated word repeats its row, and a word outside the vocabulary has no position, so its vector is all zeros and sums to $0$ .

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

Learn this in

Tokenization & EmbeddingsLLM Study Plan Text RepresentationNLP Study Plan

More from NLP 2: Applications

BIO Entity Span Extractoreasy Simple Entity Taggereasy Sentiment Word Countereasy Keyword Classifiereasy Sequence Paddereasy

Concept primer

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 \times 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 \times m)$ .

solution.py

Python 3.13

Test results