This recipe will demonstrate how to find strings that are one-edit distance away from a specified string. This function can be used to correct spelling.
The algorithm in this recipe is based heavily on Peter Norvig's spell corrector algorithm described at http://norvig.com/spell-correct.html. Take a look at and study the edits1
Python function implemented there.
Import a couple of character and list functions as follows:
import Data.Char (toLower) import Data.List (group, sort)
Define a function to return strings that are one-edit distance away, as shown in the following code snippet:
edits1 :: String -> [String] edits1 word = unique $ deletes ++ transposes ++ replaces ++ inserts where splits = [ (take i word', drop i word') | i <- [0..length word']]
Create a list of strings with one character deleted, as follows:
deletes = [ a ++ (tail b) | (a,b) <- splits, (not.null) b]
Create a list of...