Suppose I have two sets,
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
Awill 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.
Bwill 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.