Build a B-Tree with min degree t=2 (each node can contain 1-3 keys) by inserting in order following keys: 35, 2, 1, 89, 4, 33, 24, 6, 7, 88, 14, 23, 22
Build a B-Tree with min degree t=3 (each node can contain 2-5 keys) by inserting in order following keys: 35, 2, 1, 89, 4, 33, 24, 6, 7, 88, 14, 23, 22
Draw the contents of a trie tree datastructure that stores following set of words: all, alternate, alternative, are, arc, archbishop, bear, beard, bee, hear, horse, horseshoe.
If you chose to do Tool project 1 or Tool project 2 this replaces also the implementation homework from this lab !
Implement a primitive autocomplete function, using trie trees to store a language dictionary.
Minimal requirements:
Implement a trie tree datastructure and add operations to:
Complete requirements:
Use an english language dictionary for the list of words. You can find such dictionaries given as text files containing a list of words:
58.000 words: corncob_lowercase.txt(from http://mieliestronk.com/corncob_lowercase.txt)
109.582 words: wordsEn.txt(from http://www-01.sil.org/linguistics/wordlists/english/)
The dictionaries are given as text files, containing a word on every line. A word may contain lowercase letters and the symbols ' (apostrophe) and - (hyphen). The trie tree alphabet contains thus 28 symbols.
Initialize a dictionary data structure based on trie trees by adding all the words from a dictionary file.
Improve the trie tree datastructure to handle large dictionaries such as wordsEn.txt in a memory-efficient way.
Implement a simple autocomplete feature that will display dictionary-based suggestions while you type a word. The autocomplete feature starts giving suggestions when the current word has at least L letters (the value of L must be configurable when starting the program, default value L=4). It will display as suggestions all the words from the dictionary that start with the current prefix. The suggestions are listed in increasing order of the word lengths.
For example, when using the wordsEn.txt dictionary, and having the current prefix rocke, you should get, in order, the following list of suggestions: rocked, rocker, rocket, rockers, rockery, rockets, rocketed, rocketer, rocketry, rockeries, rocketers, rocketing, rocketlike rocketries.
For this assignment, it is OK to read a whole word from standard input and display all the suggestions that would be given, starting from its prefixes of L, L+1, L+2, ... characters. Implementing a real autocomplete feature (giving the suggestions while the user is typing) requires using non-blocking keyboard input (reading a character while the user is typing it, no Enter pressed).
simulateAutocomplete(String word) {
startWordSpelling(); // reset current position in trie tree to the root
for (int i = 0; i < word.length(); i++)
keypressed(word.charAt(i)); // simulate that the key has been pressed:
// advance in trie tree and print all current suggestions
}
If simulateAutocomplete("rocket") is executed, with L=4, the results are:
Suggestions for rock : rocks rocky rocked rocker rocket rockaby rockers rockery rockets rockier rockies rocking rockabye rocketed rocketer rocketry rockfall rockfish rockiest rockless rocklike rockabies rockabyes rockaways rockeries rocketers rocketing rockfalls rockiness rockroses rockworks rocketlike rocketries rockfishes Suggestions for rocke : rocked rocker rocket rockers rockery rockets rocketed rocketer rocketry rockeries rocketers rocketing rocketlike rocketries Suggestions for rocket : rockets rocketed rocketer rocketry rocketers rocketing rocketlike rocketries