2
$\begingroup$

My question is simple but I don't know if the answer is.

If you have two strings of length 10 million each, is there an algorithm that would allow you in practice to compute their edit distance (Levenshtein) if you are told it is at most 100?

$\endgroup$
3
$\begingroup$

You can use the usual dynamic programming algorithm. Instead of computing the edit distance between all prefixes of the input strings, compute only the edit distance between prefixes whose length is at most 100 apart. This reduces the number of entries to compute from $10^{14}$ to roughly $2\cdot 10^9$, which is feasible.

$\endgroup$
  • $\begingroup$ Does this method need the same amount of space? $\endgroup$ – Anush Aug 4 '18 at 13:29
  • $\begingroup$ The DP solution only requires storing two rows, and the same should be true here. $\endgroup$ – Yuval Filmus Aug 4 '18 at 13:31

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.