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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Aug 4, 2018 at 13:14
-
$\begingroup$ Does this method need the same amount of space? $\endgroup$– SimdCommented Aug 4, 2018 at 13:29
-
$\begingroup$ The DP solution only requires storing two rows, and the same should be true here. $\endgroup$ Commented Aug 4, 2018 at 13:31