[Haskell-cafe] Re: Haskell version of Norvig's Python Spelling
Corrector
Stefan O'Rear
stefanor at cox.net
Sun Apr 22 16:15:07 EDT 2007
On Sun, Apr 22, 2007 at 10:10:44PM +0200, Ketil Malde wrote:
> On Sun, 2007-04-22 at 11:51 -0400, Pete Kazmier wrote:
>
> > type WordFreq = M.Map B.ByteString Int
> >
> > train:: [B.ByteString] -> WordFreq
> > train words = frequencyMap
> > where
> > frequencyMap = foldr incWordCount M.empty words
> > incWordCount w m = M.insertWith (+) w 1 m
>
> Isn't this going to build unevaluate thunks for the counts? This is
> what frequency counting looks like in some of my old code:
>
> -- IM is Data.IntMap
> index ss = foldl' myupdate IM.empty ss
> where myupdate m k = let x = 1 + IM.findWithDefault 0 k m
> in x `seq` IM.insert k x m
>
> (edited a bit, but hopefully correct)
>
> I.e. use foldl', and look up previous value, succ and seq it, and put it
> back.
>
> Generally, I only seem to want strict Maps. It seems so easy to build a
> lazy one if you need it (data Lazy a = Lazy a), so I wonder if strict
> should be the default?
>
> > > Instead of generating the (huge) list of misspelled words, you could
> > > calculate edit distance to each correctly spelled word? With a bound on
> > > allowable mistakes, this is a linear time operation using the standard
> > > dynamic programming algorithm.
> >
> > Could you provide additional information on this "standard dynamic
> > programming algorithm?" I'm not familiar with dynamic programming.
>
> Sorry! Dynamic programming just means using memoizing on a recursive
> function to reduce its run time complexity (although I don't think I've
> seen that definition anywhere?). A simple example is finding the n'th
> Fibonacci number by calculating (and referring to) the whole list.
>
> For edit distance, you can do something like:
>
> data Edit a = Repl a a | Delete a | Insert a
>
> align (x:xs) (y:ys) = best [ Repl x y : align xs ys,
> Insert y : align (x:xs) ys,
> Delete x : align xs (y:ys)]
>
> Where 'best' is some fitness function, selecting the best alignment.
>
> Applying this directly gives an exponential algorithm, but since there
> are only n*m (n = lenght (x:xs), m = length (y:ys) possible ways to pick
> the remainders in the recursive calls throughout the execution, you
> might as well store them all in an n*m matrix - which only takes O(nm)
> time.
>
> This is probably the worst explanation of DP so far this century, but if
> you Google for it, you'll find tons of information. Wikipedia has an
> entry as well.
>
> Anyway: since the number of edits in this case is bounded (to four,
> since transposition can be modelled by an insertion and a deletion), you
> know the optimal solution will never stray further than two off the
> diagonal of the DP matrix, so you only need to caclulate a diagonal band
> (linear space/time), not the full matrix (quadratic).
You can almost always do DP with less space, and this is no exception:
linear space for full Levenschtein, constant for the diagonal band.
http://www.haskell.org/haskellwiki/Dynamic_programming_example#Optimization
Stefan
More information about the Haskell-Cafe
mailing list