I have a database of about 200 documents who's ngrams I have extracted. I want to find the document in my database that is most similar to a query document. In otherwords, I want to find the document in the database that shares the most number of ngrams with the query document. Right now, I can go through each one and compare it one by one, but this will take O(N) time and is expensive if N is very large. I was wondering if there are any efficient data structures or methods in doing efficient similarity search. Thanks
You could use a hashing vectorizer on your documents. The result will be a list of vectors. Then vectorize your ngrams in the same way and calculate the projection of this new vector on the old ones. This is equivalent to the database join on an index, but may have less overhead.
PK (primary key) ngram, docID
depending the database may change a bit but this is for TSQL
x is the document you are matching
select top(1) with ties * from ( select tm.docID, count(*) as count from table td join table tm on tm.docID <> td.docID and tm.ngram = td.ngram and td.docID = x group by tm.docID ) tt order by count desc
The join is on an index (PK) so this is very fast. I do this on a million documents in just a few seconds (with more advanced conditions).
This is going to favor larger documents but that is what you asked for.
Question seems to be changing
declare table @query (varchar ngram); insert into @query values ('ng1'), ('ng2'), ('ng3'); select top(10) with ties * from ( select tm.docID, count(*) as count from table td join @query on tm.ngram = @query.ngram group by tm.docID ) tt order by count desc
From your clarification -
By database, lets just say that there is a huge list of the ngram model that represents the document
You would do well to do something a bit more structured and put the data into a relational database. This would allow you to do much more detailed analysis more easily and quickly.
I guess when you say "ngram" you mean "1gram". You could extend the analysis to include 2grams, 3grams etc, if you wanted.
I would have a table structure that looks something like this -
So, in the record in the Docs1Grams table when 1GramID points to the 1gram "the" and the DocID points to the document "War and Peace" then 1GramCount will hold the number of times the 1gram "the" appears in War and Peace.
If the DocID for 'War and Peace" is 1 and the DocId for "Lord of the Rings" is 2 then to calculate the 1gram similarity score for these two documents you would this query -
Select count(*) from Docs1Grams D1, Docs1Grams D2 where D1.DocID = 1 and D2.DocID = 2 and D1.1GramID = D2.1GramID and D1.1GramCount > 0 and D2.1GramCount > 0
By generalizing and expanding the query this could be easily changed to automatically pick the highest such score / count comparing your chosen document with all the others.
By modifying / expanding the
D1.1GramCount > 0 and D2.1GramCount > 0 part of the query you could easily make the comparison more sophisticated by, for instance, adding 2Grams, 3Grams, etc. or modifying the simple match to score according to the percentage match per ngram.
So if your subject document has 0.0009% of the 1grams being "the", document 1 has 0.001% and document 2 has 0.0015% then document 1 would score higher on "the" because the modulus of the difference (or whatever other measure you chose to use) is smaller.
If you want to check for the presence of your n grams in the document you will need to convert the query document also into n grams. To accomplish this you can use the TFIDF vectorizer.
from nltk.tokenize import word_tokenize from sklearn.feature_extraction.text import TfidfVectorizer vect = TfidfVectorizer(tokenizer=word_tokenize,ngram_range=(1,2), binary=True, max_features=10000) TFIDF=vect.fit_transform(df_lvl0['processed_cv_data'])
To explain the above code:
word_tokenize : this function converts the text into string tokens but you will have to clean the data accordingly.
ngram_range : sets the number of ngrams you need. In this case it will take both 1 word and 2 words.
max_features : limits the total no. of features. I recommend using it if you want to tokenize a couple of documents as the no. of features is very high(in the order of 10^6).
Now after you fit the model the features are stored in "vect". You can view them using:
Now that you have the grams of your query document stored in a set, you can perform set operations which are much faster compared to loops. Even if the length of each set is in the order of 10^5 you will get results in seconds. I highly recommend trying sets in python.
matching_keys = keywords.intersection(all_grams) //all_grams is the set of your collected grams
Finally you will get all the matching keywords into "matching_keys".