TF-IDF From Scratch: Implementation, Sparse Storage for Millions of Terms, Complexity

Given a corpus of strings, implement a class or function that computes TF-IDF. Then explain how you would store and optimize TF-IDF for about 10 thousand documents and a vocabulary of several million words, which sparse matrix formats exist, and the time and space complexity of `fit` and `transform`. ### Clarifying Questions - Which TF and IDF variants are expected: raw counts or length-normalized frequencies, smoothed or unsmoothed IDF, and should each document vector be L2-normalized? - How should text be tokenized: lowercasing, punctuation, stop words? - Should `transform` accept new documents after `fit`, and what happens to words not seen during fitting? - Should the output be a dense array, a sparse matrix, or a per-document dictionary? ### Part 1 — Implement TF-IDF Write a class with `fit`, `transform` and `fit_transform` (or an equivalent function) that turns a list of strings into TF-IDF vectors. ```hint Two passes Document frequencies must be known before any weight can be computed. Decide what `fit` stores and what `transform` recomputes for each document. ``` #### What This Part Should Cover - Correct TF, IDF and normalization formulas, with the chosen variants stated - A vocabulary mapping, and the handling of unseen terms and empty documents - Clean, testable code with a small worked check ### Part 2 — Storage and optimization at scale With about 10 thousand documents and a vocabulary of several million words, how would you store and optimize the TF-IDF matrix? What sparse matrix formats exist, and which would you use here? ```hint Count the nonzeros Estimate how many distinct words a typical document contains compared with the vocabulary size, then size a dense matrix and a sparse one. Do not forget the vocabulary itself. ``` #### What This Part Should Cover - A size estimate for dense versus sparse storage - The main sparse formats, how each lays out its data, and which operations each one is good at - Vocabulary-side optimizations: pruning, hashing, compact types, streaming ### Part 3 — Complexity of fit and transform State the time and space complexity of `fit` and of `transform`. ```hint Name the variables Express the costs in total tokens, number of documents, vocabulary size and number of nonzero entries rather than a single n. ``` #### What This Part Should Cover - Time of `fit` and `transform` in terms of tokens and nonzero entries - Memory for the vocabulary, the IDF vector and the output matrix - How the answer changes with a dense output or with feature hashing ### What a Strong Answer Covers - Working code with clearly stated TF and IDF conventions - A quantitative storage estimate that justifies a sparse representation - An accurate comparison of sparse formats tied to the operations TF-IDF needs - Complexity expressed with the right variables, including the dense-output trap - Practical scaling choices for a vocabulary of several million words ### Follow-up Questions - How would you compute TF-IDF when the corpus does not fit in memory? - How would you compute the cosine similarity between all pairs of documents efficiently with this matrix? - What changes if new documents keep arriving after the model is fitted? - What do you lose by using feature hashing instead of an explicit vocabulary?