C++ Binary Tree Sorting of text words
As different authors tend to use different vocabularies and to use common words with differing frequencies. Given an essay or other text, it is interesting to find what distinct words are used and how many times each is used.
I’m trying to produce a driver program and the information-retrieval package using ordinary binary search trees.
I really want to complete this program using the outline I’m presenting you here:
1) Create the data structure (binary search tree).
2) Ask the user for the name of a text file and open it to read.
3) Read the file, split it apart into individual words, and insert the words into the data structure. With each word will be kept a frequency count (how many times the word appears in the input), and when duplicate words are encountered, the frequency count will be increased. The same word will not be inserted twice in the tree.
4) Print the number of comparisons done and the CPU time used in part 3. (By CPU time, I mean the amount of time for which the CPU was used for processing the comparisons (reading the file, splitting & inserting words)).
5) That I can, If I wish, print out all the words in the data structure, in alphabetical
order, with their frequency counts.
6) Put everything in parts 2-5 into a do . . . while loop that will run as many
times as the user wishes. Thus the user can build the data structure with
more than one file if desired. By reading the same file twice, the user can
compare time for retrieval with the time for the original insertion. (Let me clarify here, because parts 2 to 5 will be in a “do while” loop, then I can compare time for retrieval with the time for the original insertion).
Some additional specifications I was trying to implement to the program:
* I want the input to the driver will to be a file. The program will be executed with several different files; the name of the file to be used should be requested from the user while the program is running.
* A word is defined as a sequence of letters, together with apostrophes (‘) and hyphens (-), provided that the apostrophe or hyphen is both immediately preceded and followed by a letter. Uppercase and lowercase letters should be regarded as the same (by translating all letters into either uppercase or lowercase, as you prefer). A word is to be truncated to its first 20 characters (that is, only 20 characters are to be stored in the data structure) but words longer than 20 characters may appear in the text. Non-alphabetic characters (such as digits, blanks, punctuation marks, control characters) may appear in the text file. The appearance of any of these terminates a word, and the next word begins only when a letter appears.
* The program should not allow to be changed at all when I change implementation of data structures later.
Final specifications for the functions to I want implemented first with binary
search trees:
=========================================================
void update(const String &word,
Search_tree< Record > &structure, int &num_comps);
postcondition: If word was not already present in structure, then word has been inserted into structure and its frequency count is 1. If word was already present in structure, then its frequency count has been increased by 1. The variable parameter num_comps is set to the number of comparisons of words done.
=========================================================
void print(const Search_tree< Record > &structure);
postcondition: All words in structure are printed at the terminal in alphabetical order together with their frequency counts.
=========================================================
