Document Term Matrix

easyFREEText RepresentationNLP 1: Foundations

Given a list of documents, build a document-term matrix where each row represents a document and each column represents a unique word from the vocabulary.

The vocabulary should be sorted alphabetically. Each cell contains the count of that word in that document. All words should be lowercased.

Input: docs, a list of n document strings (words separated by spaces).

Output: Return the matrix as a list of lists of integers, one row per document in input order (the tests print each row).

Example

Input

2
the cat sat
the dog sat

Output

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

Reasoning

Input: docs holds 2 documents, "the cat sat" and "the dog sat". Words are separated by spaces.
Columns (vocabulary): the distinct lowercase words across both documents are cat, dog, sat and the. In alphabetical order they fix 4 columns: cat, dog, sat, the. Shared words (sat, the) get one column.
Rows (counts): entry $c_{dj}$ is how many times vocabulary word $j$ occurs in document $d$ . Document 1 has cat, sat and the once each and no dog, giving [1, 0, 1, 1]. Document 2 has no cat and one each of dog, sat, the, giving [0, 1, 1, 1].
Output shape: a $2 \times 4$ matrix of integers, one row per document in input order. Every row has length 4 even though each document only uses 3 words, so the zeros mark words a document lacks.
Notice: counts are not capped at 1. For "a a a" the word a scores 3, and each row sums to its document's word count: $1 + 0 + 1 + 1 = 3$ .

Constraints

1 ≤ n ≤ 10
Words are separated by spaces
Convert all words to lowercase
Vocabulary sorted alphabetically
Output each row as a Python list of integers

Learn this in

Text RepresentationNLP Study Plan

More from NLP 1: Foundations

Embedding Lookupeasy Cosine Similarity Calculatoreasy Binary Vectorizereasy Character Frequency Countereasy Word Reversereasy

Concept primer

Background Knowledge

The Document Term Matrix is a fundamental concept in Natural Language Processing (NLP), specifically in the area of Text Representation. It is a mathematical representation of a collection of documents, where each row represents a document, and each column represents a unique word from the vocabulary. The cell at row $i$ and column $j$ contains the count of the $j^{th}$ word in the $i^{th}$ document. This matrix is useful for various NLP tasks, such as text classification, information retrieval, and topic modeling.

The vocabulary is the set of unique words in the collection of documents. In this problem, the vocabulary should be sorted alphabetically, which means that the columns of the matrix will be arranged in alphabetical order of the words. The word count is the number of times a word appears in a document. This is a simple yet effective way to represent the content of a document. By using word counts, we can capture the frequency of each word in each document, which can be useful for understanding the topic or theme of the document.

The preprocessing step is crucial in NLP tasks, including building a document-term matrix. In this problem, all words should be lowercased, which means that words like "The" and "the" will be treated as the same word. This helps to reduce the size of the vocabulary and improves the accuracy of the word counts. Additionally, punctuation and stop words (common words like "is", "and", etc. that do not carry much meaning) may need to be removed or handled separately, but in this problem, we are only concerned with building the matrix using the given documents.

Algorithm/Approach

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

Read and preprocess the input documents
Build the vocabulary by extracting unique words from the documents
Create the document-term matrix by counting the occurrences of each word in each document
Sort the vocabulary alphabetically and arrange the columns of the matrix accordingly This approach can be implemented using various data structures and algorithms, such as hash tables or dictionaries for efficient word counting and vocabulary building.

Step-by-Step Strategy

To implement the solution, follow these steps:

Read the number of documents $n$ and store the documents in a list or array.
Preprocess each document by lowercasing all words and splitting the document into individual words.
Build the vocabulary by iterating through each document and extracting unique words.
Create the document-term matrix by iterating through each document and counting the occurrences of each word.
Sort the vocabulary alphabetically and arrange the columns of the matrix accordingly.
Print each row of the matrix as a list of integers.

Common Pitfalls

Some common pitfalls to watch out for when implementing this solution include:

Not handling punctuation or special characters correctly
Not lowercasing all words, which can lead to incorrect word counts
Not sorting the vocabulary alphabetically, which can result in an incorrect matrix
Not handling empty documents or documents with no words

Time & Space Complexity

The expected time complexity of this solution is $O(n \cdot m \cdot k)$ , where $n$ is the number of documents, $m$ is the average number of words per document, and $k$ is the average number of unique words per document. The space complexity is $O(n \cdot k)$ , where $n$ is the number of documents and $k$ is the total number of unique words in the vocabulary. Note that these complexities assume that the vocabulary is relatively small compared to the number of documents.

solution.py

Python 3.13

Test results