2
$\begingroup$

Suppose I have two sets, A and B, which each have one or more strings.

I'm looking for an algorithm that'll go through each string in A and find the string(s) in B with minimal Levenshtein distance.

Lets assume the following constraints:

  • Strings won't be too long: probably between 20 and 30 characters.
  • The alphabet will be small: probably 5 different letters.
  • We can assume that no string in A will be largely distant from a string in B: a maximum Levenshtein distance of 10 is imposed where strings which don't conform can be discarded/ignored.
  • A and B will be large, easily containing hundreds of millions of strings.
  • I need exact matching - not approximate.. I think. I'm actually not 100% sure what approximate means in this context, but I need the result to be "exactly" exist in B - not some generated approximation with a lower distance.

In my head I imagine this being abstracted to some sort of a graph processing problem, but I want to look around and see what already exists (because it seems like a problem someone might already have solved) before putting pen to paper.

I've tried Googling things like "Levenshtein graph" and exploring the links from Wikipedia's Edit distance and Levenshtein distance to find something relevant, but I mostly bumped into approximate and pattern matching algorithms as opposed to ones with a specific set of strings (B) to search through.

Improve this question
$\endgroup$
5
  • $\begingroup$ Well, since Levenshtein distance is a distance, you can use it to order strings in a set. I.e. you can represent the set as an ordered vector. Then you can compare two ordered vectors. But maybe there's something more efficient. Perhaps you can do it with tries somehow... $\endgroup$
    – wvxvw
    Commented Oct 11, 2015 at 10:14
  • $\begingroup$ Check out BK-trees and Levenshtein automata and metric trees. See also cs.stackexchange.com/q/27539/755 and cs.stackexchange.com/q/2093/755 and cs.stackexchange.com/q/1626/755 and cstheory.stackexchange.com/q/4165/5038. If you expect that the closest match for each string will match very closely (very few mismatches), another approach to get approximate results is to use shingling. See, e.g., cs.stackexchange.com/q/47794/755. See if this answers your question, and if not, edit your question accordingly. $\endgroup$
    – D.W. ♦
    Commented Oct 11, 2015 at 10:37
  • $\begingroup$ Thanks @D.W. - I'll need more time to look through each of those links but what I can say now (and appropriately edit my question to communicate) is that I need exact searching - not approximate. I'll also address patterns regarding the number of mismatches (or the distance). $\endgroup$
    – Bilal Akil
    Commented Oct 11, 2015 at 10:57
  • $\begingroup$ What's wrong with the brute-force approach? Given the limitations you list, every pairwise comparison would be fast (and $O(1)$)) so you'd have a $\Theta(|A| \cdot |B|)$-time algorithm. Is this too slow in your context? $\endgroup$
    – Raphael
    Commented Oct 11, 2015 at 11:12
  • $\begingroup$ @Raphael I think it is too slow. Suppose |A| = |B| = 1bil. I was hoping there'd be something smarter than brute force so each A doesn't need to compare to each B. I'll update the question to highlight the size better. I didn't think that brute force would've been considered :P $\endgroup$
    – Bilal Akil
    Commented Oct 11, 2015 at 11:36

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.