CODEWITHSUNDEEP
algorithmdata-structuresspell-checkingternary-search-tree
Parul Setia
Parul Setia

Reputation: 23

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/

Upvotes: 0

Views: 1101

Answers (2)

Cybercartel
Cybercartel

Reputation: 12592

You can try a wildcard. For example replace somewhere in your search word a letter with a wildcard then split the word into two substrings and insert them into the TST. Then search for all patterns and not only the exact match. It works by createing every prefices of the dictionary word. But I recommend to try the aho-corasick algorithm with a TST.

Upvotes: 0

rici
rici

Reputation: 241731

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.

Upvotes: 1

Related Questions