Bag of Words

easyFREEText RepresentationNLP 1: Foundations

Build a Bag-of-Words (BoW) representation for a corpus of documents.

Algorithm:

Build a vocabulary: collect all unique words across all documents, sorted alphabetically
For each document, create a vector where each element is the count of the corresponding vocabulary word in that document

Input:

docs: a list of N document strings (lowercase, space-separated words)

Output:

A tuple (vocabulary, matrix):
- vocabulary: the sorted list of unique words
- matrix: the BoW matrix (list of lists, one row per document)

Example

Input

3
the cat sat
the dog sat
the cat and the dog

Output

['and', 'cat', 'dog', 'sat', 'the']
[[0, 1, 0, 1, 1], [0, 0, 1, 1, 1], [1, 1, 1, 0, 2]]

Reasoning

Input: docs holds three strings of space-separated lowercase words: "the cat sat", "the dog sat" and "the cat and the dog". They hold 11 words, only 5 of them distinct.
Vocabulary: the distinct words are the, cat, sat, dog, and. In alphabetical order they become ['and', 'cat', 'dog', 'sat', 'the']; column $j$ of the matrix means "vocabulary word $j$ ".
Counting: entry $c_{ij}$ is how many times vocabulary word $j$ appears in document $i$ . Document 0 has one cat, one sat and one the, giving $[0, 1, 0, 1, 1]$ . Document 1 swaps cat for dog: $[0, 0, 1, 1, 1]$ .
Repeats add up: document 2 contains the twice, so its last entry is $2$ : $[1, 1, 1, 0, 2]$ . In general $\sum_j c_{ij}$ equals the length of document $i$ .
Output: a pair made of the vocabulary and a $3 \times 5$ matrix (one row per document, one column per word). Notice that word order inside a document is lost: "sat the cat" would produce the same row as document 0.

Constraints

All words are already lowercase
Vocabulary is sorted alphabetically
Each row of the BoW matrix corresponds to a document
Each column corresponds to a vocabulary word

Learn this in

Introduction to NLPNLP Study Plan Text RepresentationNLP Study Plan Contrastive Learning & CLIPVLM Study Plan

More from NLP 1: Foundations

Embedding Lookupeasy Cosine Similarity Calculatoreasy Binary Vectorizereasy Document Term Matrixeasy Character Frequency Countereasy

Concept primer

Background Knowledge

The Bag-of-Words (BoW) model is a fundamental concept in Natural Language Processing (NLP), used for text representation. It represents a document as a bag, or a set, of its word occurrences, disregarding grammar and word order. This model is based on a vector space model, where each document is represented as a vector in a high-dimensional space. The BoW model is widely used in text classification, clustering, and information retrieval tasks.

In the context of the BoW model, a vocabulary is a set of unique words across all documents. The vocabulary is used to create a feature space, where each feature corresponds to a word in the vocabulary. The dimensionality of the feature space is equal to the number of unique words in the vocabulary. The BoW representation of a document is a vector where each element represents the count of the corresponding word in the vocabulary.

The BoW model has its limitations, such as ignoring word order and context, but it provides a simple and effective way to represent text data. It is often used as a baseline model for more complex text representation techniques, such as term frequency-inverse document frequency (TF-IDF) and word embeddings.

Algorithm/Approach

The general approach to solving this problem involves the following steps:

Building a vocabulary by collecting unique words across all documents
Creating a vector representation for each document based on the vocabulary
The algorithm pattern used here is a simple tokenization and counting approach, where each document is tokenized into individual words, and the count of each word is used to create the BoW representation.

Step-by-Step Strategy

To implement the solution, follow these steps:

Read the input data and store the documents in a list.
Create an empty set to store the unique words (vocabulary) across all documents.
Iterate over each document, split it into individual words, and add each word to the vocabulary set.
Sort the vocabulary set alphabetically to ensure consistency.
Create a matrix to store the BoW representation of each document.
Iterate over each document, and for each word in the document, increment the corresponding count in the BoW matrix.

Common Pitfalls

When implementing the solution, watch out for the following:

Make sure to handle duplicate words correctly, as they should only be counted once in the vocabulary.
Ensure that the vocabulary is sorted alphabetically to maintain consistency.
Be careful when creating the BoW matrix, as the order of the words in the vocabulary must match the order of the counts in the matrix.

Time & Space Complexity

The expected time complexity of the solution is $O(N \cdot M \cdot \log M)$ , where $N$ is the number of documents, $M$ is the maximum number of words in a document, and $\log M$ is the time complexity of sorting the vocabulary. The space complexity is $O(N \cdot M)$ , as we need to store the BoW matrix and the vocabulary. Note that these complexities assume that the input data is well-formed and that the vocabulary size is reasonable.

solution.py

Python 3.13

Test results