2
$\begingroup$

In the Wagner Fischer algorithm to calculate the Levenshtein distance for two input strings, the first step is to compare each input string with the empty string for each input. Why is this step necessary? Is the purpose simply to keep the algorithm consistent when checking the strings for matches and mismatches to determine the distance between two prefixes?

Thanks!

$\endgroup$
2
$\begingroup$

The Wagner–Fischer is a dynamic programming algorithm. You can think of a dynamic programming algorithm like a recursion. Every recursion needs a base case (like in induction). In this case, the base case is prefixes of length zero. We could also use prefixes of length one as a base case, but the simplest implementation of the algorithms starts with prefixes of length zero.

The prefix zero case can actually happen, for example when both strings have disjoint sets of letters.

$\endgroup$
  • $\begingroup$ Thanks Yuval for your reply. I'm still not completely certain why the comparison against the empty string is necessary. Like you said, the base case can be of length one, so the first row and column of the matrix would filled with the distance of each prefix of each string against the first character of each input string. The final edit distance for both strings would be the same, so why waste additional time and space for the empty string comparison? $\endgroup$ – 201403540 Apr 22 '14 at 17:04
  • $\begingroup$ The algorithm is not set in stone. A different variant of the algorithm would have a base case of length one rather than zero. $\endgroup$ – Yuval Filmus Apr 22 '14 at 17:42

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.