Input: A single long string (<10MB) and a number k

Definition: A unique k-substring is a substring of length k, which occurs exactly once in the input document.

Output (Approach 1): Either print each unique k-substring OR

Output (Approach 2): Output a DFA which matches unique k-substrings in the given document in a streaming fashion (KNP-style search)

Given a large string, I'd like to preprocess it find a "fingerprint" of all fixed-length (say, length 20) unique substrings. These are typically phrases specific to the document.

Then, I want to use find approximate copies of the document inside other documents. I have this process working already, it's just too slow.

So far, I've been looking at suffix tries and KNP-style search. Aho-Corasick algorithm adapts KNP to recognize multiple strings, and Incremental String Match, further allows adding strings while running. If I add removing search strings while running I think I'll be at a solution, but this is quickly getting complicated for a problem with such simple structure.

Is there a simpler algorithm / data structure, or a known one?

  • 2
    $\begingroup$ Did you try Rabin-Karp? Suffix trees will also work (as they usually do) but are more complicated. $\endgroup$ – David Eppstein Jun 4 '20 at 17:41
  • $\begingroup$ Can you recommend a <50page text about suffix trees and applications? I haven't tried Rabin-Karp or any hashing (well, my python prototype...). A hash also reduces memory from a trie, which is turning out to be my limiting factor. I'd love to compare everything vs everything, but with millions of documents, a trie can't fit in main memory. I have to compare one subset vs everything, then the next subset vs everything, etc. Halving memory usage halves the number of passes. It looks like I may not have picked the right subproblem, open to suggestions. $\endgroup$ – Zachary Vance Jun 5 '20 at 4:51
  • $\begingroup$ What I ended up finding useful to learn suffix trees was MIT's "Advanced Data Structures". Video lectures free at: youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf $\endgroup$ – Zachary Vance Nov 12 '20 at 23:18

Your Answer

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

Browse other questions tagged or ask your own question.