An Auto Completion Engine that uses a Prefix Tree (also known as Trie). Can be used for implementing auto completion, where the engine suggests possible word completions based on the characters entered so far (also does other things like spell-checking, generating dictionary graph, loading dictionary).
Graphviz is used for visualizing tree. See Trie Visualization
Installation instructions for Graphviz
DEBUG flag compiles application with debug mode (includes logging, auto graph generation after each trie mutation)
$ make DEBUG=true|falseFor tests
$ make testFor cleaning up
$ make clean[A-Za-z] are supported as a character set, but can be easily extended by modifying:
#define NUMBER_OF_LETTERS 52macro that defines number of acceptable lettersint hash(char ch)function to choose unique slot between [0 .. NUMBER_OF_LETTERS]
- Adding new word
- Loading file of words
- Deleting existing word
- Spell-checking
- Completing prefix
- Generating dot and svg file for trie
- Generating dictionary txt file from existing trie
$ ./bin/fcmpl
> .add accept
> .add account
> .add air
> .add above
> .delete above
> a
accept
account
air
> .load res/9-words.txt
> a
accept
account
air
apple
application
> .generate res/out.txt # will generate res/out.txt (list of words) from trie
> .generate res/out # will generate res/out.dot and res/out.svg
> .quit
Have a good day!
$
Trie can be visualized with .visualize operation
If res/9-words.txt is taken as a dictionary file, then two files will be generated after .visualize operation.
- out.dot
- out.svg
out.dot is dot file (the dot language Graphviz uses for generating graphs in different formats) that is generated from trie.
digraph {
"0x5590788182c0" [label=".";fillcolor=red;style=filled;fontcolor=white]
"0x55907881a050" [label="a";fillcolor=black;style=filled;fontcolor=white]
"0x5590788182c0" -> "0x55907881a050"
...
}out.svg
After certain number of deletions, trie should be balanced for better performance and memory by removing orphan nodes. DELETE_THRESHOLD is macro and equals to 50 (in compilation with DEBUG flag, equals to 5). It means trie will be rebalanced after DELETE_THRESHOLD times deletions.
| Before Rebalance | After Rebalance |
|---|---|
Valgrind memory leak possibility test result with 999 word insertions and deletions: