algorithmdata-structuresspell-checkingternary-search-tree

Spell Checker using Ternary Search tree

I made a spell checker using Ternary search tree (TST). Can anybody tell me how to find the next possible word in the TST?

eg: If i want to search the word "Manly" in spell checker and if the word is not present in the TST, so that it outputs near words like this:

DO YOU MEAN: "Man" "Mango" .

Here is the code for implementing ternary search tree. Can any body please modify to find nearest possible word. http://www.geeksforgeeks.org/ternary-search-tree/

Solution

  • A spell-checker would probably want to find the nearest matches to a target word, rather than words which happen to have the same prefix. TSTs are good at finding prefixes, but they're not going to help you much if you want to find similar words.

    In your example (assuming that "manly" is not in your dictionary, although it is a word), the suggestion "mainly" is much more likely than "mango", but it won't be found by a scan starting with the longest matching prefix.

    However, if you want the scan starting at the longest match prefix:

    1) Modify searchTST so that it returns a struct Node*, and replace the last else clause with:

    else if (*(word+1) == '\0')
  return root;
else {
  struct Node* child = searchTST(root->eq, word+1);
  return child ? child : root;
}

    2) searchTST will now return the root for the longest-matching prefix to the target. The caller will have to check whether the returned Node's isEndOfString flag is set.

    3) You can use something like traverseTST on the node returned by searchTST in order to produce all the words starting with that prefix.