[Haskell-cafe] Re: Haskell version of Norvig's Python Spelling Corrector

[Ketil Malde]

On Sun, 2007-04-22 at 13:15 -0700, Stefan O'Rear wrote:

> You can almost always do DP with less space, and this is no exception:
> linear space for full Levenschtein, constant for the diagonal band. 

Right.  Especially as we only want the final score and not the exact
edits, we only need to keep one column of the matrix.  If you want the
actual edits, you must backtrack from the optimal score -- or, since
this is Haskell, keep the edits around as lazy lists, which, I think,
amounts to the same thing.

Even if we do want the exact edits we can get linear space with a divide
and conquer approach by finding the position in the middle column with
the best score (summing the alignment scores of the prefix of xs vs ys
and the suffix of xs vs ys), and then doing a separate alignment in the
two quadrants (and recurse, of course).  This means an extra log n time
factor, though.

This is all very theoretical for a problem where we align words of about
ten characters, of course. :-)

-k