TF-IDF Document Ranking
MediumHash Map · Apple
You are given a list of documents docs and a search query. Rank the documents using TF-IDF.
Tokenizing. Lowercase the text and split it into tokens, where a token is a maximal run of letters a-z and digits 0-9. Everything else separates tokens.
Scoring. Let N be the number of documents.
tf(t, d)is the number of times tokentappears in documentd.df(t)is the number of documents that containtat least once.idf(t) = ln((N + 1) / (df(t) + 1)) + 1, using the natural logarithm.- The score of document
dis the sum oftf(t, d) * idf(t)over the query's tokens. If a token appears several times in the query, it is added that many times.
Output. Return the indices of the documents whose score is greater than 0, ordered by score from highest to lowest. Compare scores after rounding them to 6 decimal places, and order documents with equal rounded scores by smaller index first.
Example 1
- Input:
- docs = ["swift ui swift", "ui kit", "metal shaders", "UI layout in Swift"], query = "swift ui"
- Output:
- [0, 3, 1]
- Explanation
- Here
N = 4,df(swift) = 2anddf(ui) = 3, soidf(swift) = ln(5/3) + 1 = 1.5108andidf(ui) = ln(5/4) + 1 = 1.2231. Document 0 scores2 * 1.5108 + 1.2231 = 4.2448, document 3 scores1.5108 + 1.2231 = 2.7340(case does not matter), document 1 scores1.2231, and document 2 scores 0 and is left out.
Example 2
- Input:
- docs = ["cloud sync", "photo sync", "photo photo photo"], query = "photo"
- Output:
- [2, 1]
- Explanation
photois in two of the three documents. Document 2 has it three times and document 1 once, so document 2 ranks first. Document 0 does not contain it.
Example 3
- Input:
- docs = ["camera app", "audio app"], query = "keyboard"
- Output:
- []
- Explanation
- No document contains
keyboard, so every score is 0 and nothing is returned.
Constraints
1 <= docs.length <= 10^4- The total length of all documents is at most
10^6characters 0 <= query.length <= 1000