3
$\begingroup$

Which algorithms would people use for computing the minimum edit distance from one string to a set of strings? (for any definitions of edit distance, for instance Levenshtein's)

It seems trivial to improve upon computing all distances and take the minimum, by computing one distance and using it as a threshold to interrupt future edit distance computations once "proven" that the edit distance will be superior to this threshold. Even if such "trick" does not improve the complexity in the worst case (and hence would required to be analyzed through a parameterized complexity as an "adaptive" algorithm to get any formal result), it seems that it should have enough of a practical impact to be studied at least as a heuristic.

I know various results about edit distance, and I saw such a "many to one" application mentioned many times, but I do not remember seeing any algorithm specifically designed/optimized for it, and some quick searches (e.g. for "many to one edit distance" "edit distance from string to set of strings") yield very few relevant references, and only to heuristics (e.g. "Accordingly, a number of heuristics are used in practice to efficiently retrieve vocabulary terms likely to have low edit distance to the query term(s)." [https://nlp.stanford.edu/IR-book/html/htmledition/edit-distance-1.html]).

I believe I can define a certificate of such "many to one" answers (extending the previous definition of certificates for one to one edit distances and Fréchet distance) and analyze algorithms in function of the complexity of such certificate, but I am afraid of "reinventing the wheel" :(

$\endgroup$

1 Answer 1

0
$\begingroup$

A colleague pointed out to me the name of "Approximate Dictionary Matching", which does point out to various articles doing "Many to One" edit distance for some specific edit distances.

The solutions seem mostly based on concatenating all dictionary entries (separated by special symbols), indexing the resulting string and doing approximate pattern matching on it.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.