Bag of Words
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 format:
- Line 1: Number of documents N
- Lines 2 to N+1: One document per line (lowercase, space-separated words)
Output:
- Line 1: The vocabulary (sorted list of unique words)
- Line 2: The BoW matrix (list of lists, one per document)
Example:
3 the cat sat the dog sat the cat and the dog
['and', 'cat', 'dog', 'sat', 'the'] [[0, 1, 0, 1, 1], [0, 0, 1, 1, 1], [1, 1, 1, 0, 2]]
Step 1: Build vocabulary All unique words: {"the", "cat", "sat", "dog", "and"} Sorted: ["and", "cat", "dog", "sat", "the"]
Step 2: Count words per document
- Doc 0 "the cat sat": and=0, cat=1, dog=0, sat=1, the=1 => [0,1,0,1,1]
- Doc 1 "the dog sat": and=0, cat=0, dog=1, sat=1, the=1 => [0,0,1,1,1]
- Doc 2 "the cat and the dog": and=1, cat=1, dog=1, sat=0, the=2 => [1,1,1,0,2]
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
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⋅M⋅logM), where N is the number of documents, M is the maximum number of words in a document, and logM is the time complexity of sorting the vocabulary. The space complexity is O(N⋅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.