1. Luke Plant
  2. phone2word


Luke Plant  committed c9e20a8

Added code comments.

  • Participants
  • Parent commits 636ffa6
  • Branches default

Comments (0)

Files changed (1)

File phone2word.hs

View file
 {-# LANGUAGE BangPatterns #-}
-Attempt to convert numbers like 01523 568304 into
-words/numbers, using the map used on most mobile
-phone keypads.
+Attempt to convert numbers like 01523 568304 into words/numbers, using the map
+used on most phone keypads.
     then Just char
     else Map.lookup (toUpper char) numbersMap
+-- Dictionary storage
+To quickly determine if a series of digits corresponds to a word, we create a
+tree that stores all our dictionary words.  Each node is (effectively) labelled
+with a digit, and words are 'hung' onto the tree at nodes where the path to the
+node is the series of digits needed to 'spell' the word on a phone keypad.  The
+tree is sparse i.e. nodes are only created as they are need to store words or
+store the route to a word.
+In this way, looking up any series of digits becomes very quick, as for most
+series of digits we 'fall off the bottom' of the tree very quickly, and always
+fall off after n moves, where n is the maximum word length in the dictionary.
+Each node does not actually store the digit label - the root node does not have
+a digit, and children are stored in a Map where the key is the digit, so we know
+what digit each child node corresponds to by the path we have followed.
 data WordTree = Node { nodeSubForest :: !(Map.Map Char WordTree) -- children
                      , nodeWords :: ![B.ByteString]              -- words that correspond to this node
                      } deriving (Eq, Read, Show)