TF-IDF

Turn a list of documents into a TF-IDF matrix.

Each document is a list of tokens. Build the vocabulary from every token that appears anywhere, sorted alphabetically, then fill an (n_docs, n_vocab) matrix.

tf(t, d)  = count of t in d / number of tokens in d
idf(t)    = log((1 + N) / (1 + df(t))) + 1
tfidf     = tf * idf

where N is the number of documents and df(t) is how many contain t.

The 1 + terms are smoothing, and they are what stop a term that appears in every document from producing log(1) = 0 and erasing it entirely. The trailing + 1 keeps every idf strictly positive. This is the same formula scikit-learn uses with default settings.

TF alone ranks "the" above every content word. IDF is the correction: it down-weights terms that are common across the corpus and so carry no signal about which document you are looking at.

Return (matrix, vocabulary). Do not L2 normalise the rows.

Function signature

def tf_idf(docs):

Example

Input

docs = [["a", "b"], ["b", "c"]]
matrix, vocabulary = tf_idf(docs)
matrix, vocabulary

Output

(array([[0.70273255, 0.5       , 0.        ],
       [0.        , 0.5       , 0.70273255]]), ['a', 'b', 'c'])

Reasoning

Each token has tf = 0.5 in its document. b is in both documents, so idf(b) = log(3/3) + 1 = 1. a and c are in one each, so their idf is log(3/2) + 1 = 1.405, and 0.5 * 1.405 = 0.703.

Constraints and notes

• Sort the vocabulary alphabetically.
• Use the smoothed idf with the trailing + 1.
• Do not normalise the rows.