Luke Plant avatar Luke Plant committed c9e20a8

Added code comments.

Comments (0)

Files changed (1)

 {-# 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)
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.