Let's say we have some function,

float distance(String a, String b) { /*...*/ }

to find the Levenshtein distance between two strings, and we have a large array of strings.

String[] strings = new String[1_000_000];

What would be an acceptable approach to map a String a to its closest match (i.e., the String b that produces the lowest result of distance(a, b)) in that array? This will need to be done often, and so going through the entire array every time would not make sense.

Of course, strings need not be an array.

  • 2
    $\begingroup$ I can't answer this, since you haven't defined what you mean by "acceptable". What would you count as acceptable? How will you evaluate answers? What approaches have you considered and rejected? What research have you done? Have you searched thoroughly? We have entire tags for questions related to edit distance; have you looked through all those questions? I encourage you to read cs.stackexchange.com/help/how-to-ask. $\endgroup$
    – D.W.
    Commented Aug 17, 2015 at 21:23
  • $\begingroup$ See also cs.stackexchange.com/q/1626/755, cs.stackexchange.com/q/27539/755, cs.stackexchange.com/q/4797/755. $\endgroup$
    – D.W.
    Commented Aug 17, 2015 at 21:28
  • $\begingroup$ @D.W. to be fair though there are only 30 posts tagged "string-metrics"... relatively poorly charted territory here. Thanks for the reading! Hard to know where to start without this. $\endgroup$ Commented Aug 18, 2015 at 14:20