Question

Write a program named text_indexing.c that does the following:

Reads text and stores it as one string called text. You can read from a file or from the user. (In my implementation, I read only one paragraph (up to new line) from the user. With this same code, I am able to read data from a file by using input redirection (executable < filename) when I run the program. See sample runs below).

You can assume that the text will not have more than 10000 characters.

We want to be able to perform fast searches in this text. We will index it by keeping the indexes where each word starts in alphabetical order.

Find, store (in an array) and print the index for each word and the word itself. They should show in the order in which they appear in the text. (See sample run.)

Sort using INSERTION SORT the indexes and print again the indexes and the words. They should show in sorted order now.(See sample run.)

The sorting must be case insensitive for the first letter. That is, if the first letter of any of the two words you are comparing is upper case, you must use the lower case value in your comparison. (Notice in the sample run with data1.txt that 'Chemical' is placed after 'application'.). You may want to write your own string compare method.

When searching for words (with binary search) count the number of words you look at until you get the answer (found or not found). Display that number in the run.

When searching (not when sorting) you should ignore the punctuation at the end of words. See the run with data0.txt:

        ./textidx.exe < data0.txt
        Enter the text:

        ...
        ...
        processes - found (3 iterations)
        processes. - not found (4 iterations)
        ...
        

REQUIREMENT: you must NOT make a copy of the data. That is, you must keep it still as one long string and process the words in it. DO NOT create an array of individual words. (-20 points if you make an array. If you do make the array, it should NOT be in sorted order. The goal here is to use indirect sorting and if you create a sorted array you would not be doing an indirect sort. You will sort the indexes into this array. See the indirect sorting with selection sort in the slides.)

8 points will be given for good practices: variable names, comments, descriptions. These will only be earned if the program is 75 correct. Non-working programs or programs that implement too few of the requirements will not get them.

C function that I used:scanf - to read the whole text:

                scanf("%[^\n]s",text); // the [^\n] part makes it stop reading when it reaches the first \n.
                

sscanf - to read from the string with the whole text one word in a separate variable

if text is a char array, text[i] is a char, and &text[i] is a pointer. Note that in class I showed the incorrect expression: *text[i].

Words are 'cleaned-up' by: making them all lower case and looking at the last symbol. If it was not a letter, that symbol was cut from the word (and so . and , at the end of some words can be removed). However this clean-up is also applied to the words that I am searching for.

Sample runs

compile:
gcc -o textidx text_indexing.c

Sample run 1 with input redirected from a file (not typed by the user):
./textidx.exe < data0.txt
Enter the text:

Words and indexes (the printed words are 'cleaned'):
 i   |index[i]|  word
-----|--------|------------------
   0 |      0 |  chemical
   1 |      9 |  engineering
   2 |     21 |  encompasses
   3 |     33 |  the
   4 |     37 |  development
   5 |     50 |  application
   6 |     63 |  and
   7 |     67 |  operation
   8 |     77 |  of
   9 |     80 |  processes

The sorted data (the printed words are 'cleaned'):
 i   |index[i]|  word
-----|--------|------------------
   0 |     63 |  and
   1 |     50 |  application
   2 |      0 |  chemical
   3 |     37 |  development
   4 |     21 |  encompasses
   5 |      9 |  engineering
   6 |     77 |  of
   7 |     67 |  operation
   8 |     80 |  processes
   9 |     33 |  the

Binary search. ---- Enter words to search for. Stop with -1.
(original: that)
cleaned: that - not found (4 iterations)
(original: at)
cleaned: at - not found (3 iterations)
(original: the)
cleaned: the - found (4 iterations)
(original: application)
cleaned: application - found (2 iterations)
(original: processes)
cleaned: processes - found (3 iterations)
(original: processes.)
cleaned: processes - found (3 iterations)
(original: and)
cleaned: and - found (3 iterations)


 The original text is still the same: Chemical engineering encompasses the development, application, and operation of processes.




Sample run 2 (with user typing the text):

./textidx.exe
Enter the text:
THIS, is another, EXAMple.

Words and indexes (the printed words are 'cleaned'):
 i   |index[i]|  word
-----|--------|------------------
   0 |      0 |  this
   1 |      6 |  is
   2 |      9 |  another
   3 |     18 |  example

The sorted data (the printed words are 'cleaned'):
 i   |index[i]|  word
-----|--------|------------------
   0 |      9 |  another
   1 |     18 |  example
   2 |      6 |  is
   3 |      0 |  this

Binary search. ---- Enter words to search for. Stop with -1.
THis
(original: THis)
cleaned: this - found (3 iterations)
THIS
(original: THIS)
cleaned: this - found (3 iterations)
this,
(original: this,)
cleaned: this - found (3 iterations)
is,
(original: is,)
cleaned: is - found (2 iterations)
is,,
(original: is,,)
cleaned: is, - not found (3 iterations)
ANTOTHER
(original: ANTOTHER)
cleaned: antother - not found (2 iterations)
ANOTHER
(original: ANOTHER)
cleaned: another - found (2 iterations)
EXAMPLE
(original: EXAMPLE)
cleaned: example - found (1 iterations)
-1

 The original text is still the same: THIS, is another, EXAMple.


Sample run 3:  - Posted at 6pm, 9/14
Enter the text:
TT tabc

Words and indexes (the printed words are 'cleaned'):
 i   |index[i]|  word
-----|--------|------------------
   0 |      0 |  tt
   1 |      3 |  tabc

The sorted data (the printed words are 'cleaned'):
 i   |index[i]|  word
-----|--------|------------------
   0 |      3 |  tabc
   1 |      0 |  tt

Binary search. ---- Enter words to search for. Stop with -1.
-1

 The original text is still the same: TT tabc