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.

$\endgroup$
  • $\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 Oct 11 '15 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. Oct 11 '15 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 Oct 11 '15 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 Oct 11 '15 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 Oct 11 '15 at 11:36

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.