Is there a data structure or an algorithm or a combination of both to allow me to filter a set of documents based on the number of missing words (compared to another list)?
Problem Definition
We have a list of documents $ D = \{d_1, d_2, \dots, d_n\}$ . Each document $ d_i$ consists of a subset of words from a word pool $ W = \{w_1, w_2, \dots, w_k\}$ . For example, $ \text{words}(d_1) = \{w_1, w_5, w_{7}\}$ .
Each person $ p_j$ also has a set of words $ \text{words}(p_j)$ .
The goal is to find all documents where the length of the set difference between both is smaller than a threshold $ t$ :
$ $ |\text{words}(d_i) \setminus \text{words}(p_j)| < t $ $
Complexity
The sizes will probably be around these numbers:
- documents: millions or tens of millions of documents
- words: around 100k different words (per independent set)
- person: between 1 and 1000 people
Use Cases
My actual use case for this is to retrieve foreign language texts where I do not know all the vocabulary, yet. I have a list of words that I know for each language and I want to find documents from a collection of texts that contain between 1 and 10 words that I do not know, yet. That way, I expect to be able to find texts that I can understand while also improving my vocabulary skills.
Another use case might be finding recipes that match a user’s stock at home. In this case, you might want to find documents (recipes) that contain between 0 and 2 missing items, so that the user either has to buy nothing or can replace the few missing items with something similar.
My current approach
While it is easy to find documents that have an overlap of at least $ t$ words, I found the opposite (find documents that have a difference of at most $ t$ words) quite complex. At the moment I fell back to a two stage approach:
- I first filter documents by the length of the text and the length of the sentences and compare them to an average value I store for myself
- In the filtered list I then loop in my code and calculate the set difference for each document and delete all that have more than $ t$ unknown words.
