Question

Implement the histogram function to complete the desired program.

You must use dynamically allocated arrays for this purpose.

For your initial implementation, use ordered insertion to keep the words in order and ordered sequential search when looking for words. Note that the array utility functions from the lecture notes are available to you as art of the provided code.

Although we are counting words in this program, the general pattern of counting occurrences of things is a common analysis step in laboratory work, statistical studies, and business tasks. The results of such a program are often fed into other programs for further processing and/or display. Such results are often displayed as histograms. The CSV output format is a common “data exchange” format recognized by many programs. Almost all spreadsheets, for example, will read CSV files.

When you have the program running, execute it using a short paragraph of text as an input, saving the output in a file ending with a “.csv” extension. Run a spreadsheet program (e.g., Microsoft Excel). You should be able to load your .csv file directly into the spreadsheet.

Try displaying your results as a histogram. In Excel, for example, select the two columns of data, choose “Sort” from the Data tab and sort your data on the numeric column. Then, with the two sorted columns of data still selected, go to the Insert tab and select a 2D Bar chart. Save your spreadsheet in Excel (.xsl) format. You will turn this in later.

As documents get larger, the total number of words increases far, far faster than does the number of distinct words. Our personal vocabularies are only so large, after all. In fact, most writers unconsciously limit themselves to writing with a small fraction of their personal “reading” vocabularies. So most words in a large document are bound to be repeats. That means that, for this application, the speed of the functions for searching for words is probably more important than the speed of the functions for inserting new words into the array. We do many more searches than insertions.

Try running your program on one of the large text files provided in the assignment directory. Time it to see how long it takes. Now replace all uses of ordered sequential search by calls to the binary search function. Run it on the same output, timing it again. You should see a substantial improvement.

Problem Description:

Develop a program to prepare a list of all words occurring in a plain-text document, counting how many times each word occurs. In determining whether two words are different, punctuation (non-alphabetic characters) other than hyphens and differences in upper/lower case should be ignored. Portions of text that cannot be interpreted as words (e.g.: “ !@#%* ”) should be ignored.

The program will be launched with either one or three parameters on the command line. The first parameter is always the maximum number of distinct words (i.e., discounting repetitions of the same word) expected in the input.

If that is the only parameter supplied, e.g.,

./countwords.exe 1000

then the program reads from the standard input (cin) and writes its output to the standard output (cout).

Optionally, the program can be run with two additional parameters, the file names to be used for input and output respectively, e.g.,

./countwords.exe 1000 aDocument.txt aDocument.csv

The function you will write, which does the actual input, counting, and output, should read a word at a time (the usual >> string operator will do just fine). Each word should be processed to remove punctuation and replace upper-case characters, then checked against an array of already encountered words. If it is in there, increment an associated counter. If not, it must be added.