| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Stop wasting time looking for files and revisions. Connect your Gmail, DriveDropbox, and Slack accounts and in less than 2 minutes, Dokkio will automatically organize all your file attachments. Learn more and claim your free account.

View
 

Assignment 13 - TRIE Spellchecker

Page history last edited by Dr. Ron Eaglin 3 years ago

Assignment 13 - TRIE Spellchecker

Objectives

 

Implement the TIRE Data Structure and use it to implement a complex algorithm

 

Supports Leaning Outcome  3

 

3. Implement data structures and algorithms in computer code.

 

Lectures

 

You should have gone through all the tree based structures prior to this assignment. We are now going to move into more independent research and implementation. One of the objectives is that all students can research, implement, and use a data structure.

 

First take a look at the Wikipedia article on TRIE - https://en.wikipedia.org/wiki/Trie .It is worth noting that in a TRIE each node can have more than one child node, so a TRIE is NOT a binary tree. 

 

Now let's look into what we want to be able to do with a TRIE - in this case implement a spellchecker. A spellchecker needs to determine if a word is spelled correctly, so the TRIE needs to be able to store the list of all words to check against.  We must be able to add words to the TRIE, so we must implement the function;

 

function AddToTRIE(word)

 

The TRIE in the Wikipedia article uses clusters of letters, but we can also model each letter as a branch in the TRIE. The example at Top Coder takes this approach https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/ and it may be a simpler approach for you as it more closely approximates structures that you have used (like a list). This should be enough to get you started. You will still need to make some decisions of how to implement the list of nodes that are in each node. Use the bulletin board to discuss this choice.

 

The other algorithm that you need to implement will be to check spelling.

 

function CheckSpelling(word) {

  returns true or false

}

 

Assignment

 

Implement a TRIE that has both the functions AddToTRIE and CheckSpelling. 

 

Once you have created the TRIE add the words (hard code) I, in, into, inlet, inn, inner, innate, ink. These are good words to use to test your TRIE

 

Create an interface that has one text box for entry and 2 buttons - Add To Dictionary and Spell Check. They should ad the word to the TRIE (feedback - word added) and check the word against the TRIE and return in the word was in or not in the dictionary.

 

Upload your Fiddle.

 

 

 

Comments (0)

You don't have permission to comment on this page.