Implement TF-IDF scoring for documents

Problem

Implement a simplified TF–IDF scorer.

You are given:

• A list of documents docs, where each document is a string.
• A query string q.

Tokenization rules (for this problem):

• Lowercase everything.
• Split on non-letters/digits (you may assume a helper tokenizer is available or implement a simple one).
• Ignore empty tokens.

Definitions

• Term frequency: $tf(t, d) = \#(t \text{ in } d)$
• Document frequency: $df(t) = \#\{ d \in docs : t \in d \}$
• Inverse document frequency (smoothed):

$idf(t) = \log\left(\frac{N + 1}{df(t) + 1}\right) + 1$

where $N = |docs|$.

• Document score for query:

$score(d, q) = \sum_{t \in tokens(q)} tf(t, d) \cdot idf(t)$

Task

Return the document indices sorted by descending score(d, q). Break ties by smaller index.

Constraints

• 1 <= len(docs) <= 10^4
• Total tokens across all documents up to ~2 * 10^6

Example

If docs = ["red apple", "green apple", "banana"] and q = "apple", documents 0 and 1 should rank above 2.

Implement TF-IDF Scoring for Documents

Implement a simplified TF-IDF scorer.

You are given a list of documents docs, where each document is a string, and a query string q.

Tokenization rules:

• Convert text to lowercase.
• Split on any non-letter/non-digit character.
• Ignore empty tokens.

Definitions:

• tf(t, d) = number of times token t appears in document d
• df(t) = number of documents that contain token t at least once
• idf(t) = log((N + 1) / (df(t) + 1)) + 1, where N is the number of documents
• score(d, q) = sum of tf(t, d) * idf(t) over all tokens in the query

Important: if a query token appears multiple times, it contributes multiple times to the sum.

Return a list containing every document index exactly once, sorted by descending score. If two documents have the same score, the smaller index comes first.

Use the natural logarithm.

Hints

1. You only need document frequencies for terms that actually appear in the query.
2. To save memory, compute document frequencies in one pass, then compute scores in a second pass once IDF values are known.