2
$\begingroup$

I have a web site that process text documents (typically 10-100 pages) submitted by users. Each time a user submits a document, I'd like to store a hash of the document, but I'd like similar documents to map to the same hash value. I essentially want to know whether a user is resubmitting a slightly changed document or a new document.

I don't store the documents, so I can only compare hash values and I can't compare the documents to each other.

I've done a lot of reading about MinHash and LSH, but these all seem to be based on having a corpus of a large number of documents and then finding similar documents within the corpus. I think these don't work for me because I need to compute my hash vector on a single document at a time without knowing anything about other documents.

In some ways I feel like this should be an easy problem. Something like computing a hash of a bag-of-words vector, but I'm struggling to figure out a good way to do this.

My comparison is based on text and not meaning so I don't need anything like word embeddings.

$\endgroup$
1
$\begingroup$

Hashing the unique copies of anything, including documents, is most commonly called fingerprinting.

Picking the fingerprinting hash function depends on your use case. For your use case, pick a rolling, non-cryptographic hash function. One of the simplest examples is Rabin–Karp algorithm. Once applied, similar documents will have similar hash values.

Another issue is comparing hash values to identify near-duplicates. Exact nearest-neighbors algorithms work best but are not scalable. Approximate nearest-neighbors algorithms are scalable but can have errors. Locality-sensitive hashing (LSH) is an example of an approximate nearest-neighbors search algorithm. You'll have to decide the trade-off between scale and potential errors.

| improve this answer | |
$\endgroup$
0
$\begingroup$

What you’re looking at here is a fuzzy matching exercise! It doesn’t look quite like that because fuzzy matching is usually done between short strings, but what you’re trying to achieve is to match two nearly identical (albeit very long) strings. I suggest you use the approach described here, which is fast enough to compare whole documents. It works by creating a vector of character ngram counts for a document and comparing documents by cosine similarity. You can set a cosine similarity threshold to raise a warning when two documents are too cosine similar. It involves using scikit-learn’s TfidfVectorizer, which you can fit once on any group of documents in the appropriate language(s) as the vectoriser only needs to get an idea of what character n grams are unusual.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.