Bag of Words › Sparse Matrix Representation
Language AI HandbookAll chapters Bag of Words › Sparse Matrix RepresentationOne section · Sections in this chapter6 / 14 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
Real-world vocabularies contain tens of thousands of words, yet most documents use only a small fraction. A news article with 500 words might touch only 200 unique vocabulary terms out of 50,000. If you store this as a dense array with one float per vocabulary term, you need 50,000 floating-point numbers to represent each document, of which 49,800 are exactly zero. That's 49,800 zeros sitting in memory, contributing nothing to any computation.
This is the sparsity problem, and it gets dramatically worse as vocabulary size grows. The mathematics are unforgiving: if your vocabulary has words and each document uses an average of unique words, then the sparsity is approximately . For a vocabulary of 100,000 words and documents that use 300 unique words, that's 99.7% zeros. Storing and operating on dense matrices of this kind is not just inefficient, it's often completely impractical.
A sparse matrix is a matrix where most elements are zero. Sparse matrix formats store only the non-zero values and their positions, dramatically reducing memory usage for high-dimensional, mostly-empty data like document-term matrices.
The Sparsity Problem
Sparsity measures the proportion of zero elements in a matrix. For a document-term matrix with documents (rows) and vocabulary words (columns), the total number of elements in a dense representation is . The sparsity tells us what fraction of those elements are zero:
where:
- : the number of documents (rows in the matrix)
- : the vocabulary size (columns in the matrix)
- : the number of non-zero elements in the matrix
A sparsity of 0.99 means 99% of the matrix elements are zeros. In NLP, high sparsity is the norm because each document uses only a tiny fraction of the total vocabulary.
Let's quantify the sparsity in a typical document-term matrix:
# Create full document-term matrix for our corpus
doc_term_matrix = np.array(
[to_count_vector(doc, word_to_idx) for doc in tokenized_corpus]
)
# Calculate sparsity
total_elements = doc_term_matrix.size
non_zero_elements = np.count_nonzero(doc_term_matrix)
zero_elements = total_elements - non_zero_elements
sparsity = zero_elements / total_elementsDocument-Term Matrix Statistics: Shape: (5, 23) (documents × vocabulary) Total elements: 115 Non-zero elements: 35 Zero elements: 80 Sparsity: 69.6% Memory comparison: Dense matrix: 920 bytes
Even in this small example, most of the matrix consists of zeros. Each document only uses a fraction of the vocabulary. In real applications with vocabularies of 100,000+ words and millions of documents, sparsity typically exceeds 99%. Storing a dense matrix would require terabytes of memory for mostly zeros.
CSR Format
The Compressed Sparse Row (CSR) format stores only non-zero values along with their column indices and row boundaries. This is the standard format for document-term matrices because NLP operations typically process one document (row) at a time.
Think of CSR as storing three parallel arrays. The data array holds the actual non-zero values. The indices array holds the column position (vocabulary index) of each non-zero value. The indptr array holds boundary markers that tell you where each row's values begin and end in the other two arrays. To reconstruct any row of the original matrix, you look up the row's boundary in indptr, then read the corresponding slice of data and indices. This design makes row access very fast, which is exactly what you need when processing documents one at a time.
from scipy import sparse
# Convert to CSR format
sparse_matrix = sparse.csr_matrix(doc_term_matrix)
# Examine the internal structure
data = sparse_matrix.data # Non-zero values
indices = sparse_matrix.indices # Column indices of non-zero values
indptr = sparse_matrix.indptr # Row boundariesCSR Format Internals:
--------------------------------------------------
data (non-zero values): [1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 2. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
indices (column positions): [ 0 4 7 8 10 11 15 18 0 5 8 10 11 15 18 9 10 11 12 17 20 22 1 2
3 6 10 11 21 5 10 13 14 16 19]
indptr (row boundaries): [ 0 8 15 22 29 35]
How to read this:
Row 0: values at columns indices[0:3] = indices[0:3]
→ columns [ 0 4 7 8 10 11 15 18], values [1. 1. 1. 1. 1. 1. 1. 1.]
Row 1: columns [ 0 5 8 10 11 15 18], values [1. 1. 1. 2. 1. 1. 1.]
Row 2: columns [ 9 10 11 12 17 20 22], values [1. 1. 1. 1. 1. 1. 1.]
The indptr array is the key to CSR. To find the non-zero values in row , look at positions indptr[i] through indptr[i+1] in both data and indices. This makes row slicing extremely efficient. In a dense matrix, accessing a row requires touching all columns even if 99% are zero. In CSR format, you touch only the non-zero elements, making operations on sparse matrices scale with the actual content density rather than the theoretical maximum.
Memory Savings
The memory advantage of sparse matrices grows dramatically with vocabulary size:
# Simulate larger matrices to show memory scaling
def estimate_memory(num_docs, vocab_size, avg_words_per_doc):
"""Estimate memory usage for dense vs sparse representations."""
# Dense: store every element (8 bytes for float64)
dense_bytes = num_docs * vocab_size * 8
# Sparse CSR: store only non-zero elements
# data array: avg_words_per_doc * num_docs * 8 bytes
# indices array: avg_words_per_doc * num_docs * 4 bytes (int32)
# indptr array: (num_docs + 1) * 4 bytes
nnz = avg_words_per_doc * num_docs
sparse_bytes = nnz * 8 + nnz * 4 + (num_docs + 1) * 4
return dense_bytes, sparse_bytes
# Test different scales
scales = [
(100, 1000, 50), # Small: 100 docs, 1K vocab
(10000, 50000, 200), # Medium: 10K docs, 50K vocab
(1000000, 100000, 300), # Large: 1M docs, 100K vocab
]Memory Usage: Dense vs Sparse ====================================================================== Scale Dense Sparse Savings ---------------------------------------------------------------------- 100 × 1,000 800.0 KB 60.4 KB 92.4% 10,000 × 50,000 4.0 GB 24.0 MB 99.4% 1,000,000 × 100,000 800.0 GB 3.6 GB 99.5%
For a realistic corpus of 1 million documents with a 100,000-word vocabulary, sparse representation uses less than 1% of the memory required by dense storage. This is the difference between fitting in RAM and requiring distributed storage. The practical implication is that sparse matrix libraries like SciPy make BoW-based NLP computationally feasible at scales where the naive dense approach would simply run out of memory.
