Answer in C . How would I make this using a Hahtable? Also what would be a good algorithm to help me understand?

Warning:

As you will see below, the descriptions of the assignments will be increasingly complex

because we are asking you to build increasingly bigger programs.

Make sure to read the assignment

carefully!

0

. Introduction

In this assignment you will practice using the file system API (as well as pointers in different

data structures). In particular you will be creating, opening, reading, writing, and deleting files. Your

task is to write an indexing program, called an indexer. Given a set of files, an indexer will parse the

files and create an inverted index, which maps each token found in the files to the subset of files that

contain that token. In your indexer, you will also maintain the frequency with which each token appears

in each file. The indexer should

tokenize

the files and produce an inverted index

of how many times

the word occurred in each file,

sorted by word.

Y

our output should

be in the following format

:

"

?>

count0

count1

count2

count3

count4

The above depiction gives a logical view of the inverted index. In your program, you

have to define data structures to hold the mappings (token to list) and the records (file

name, count).

An inverted index is a sequence of mappings where each mapping maps a token (e.g.,

dog) to a list of records, with each record containing the name of a file whose content

contains the token and the frequency with which the token appears in that filename.

Here is an example of how the indexer should work. If you are given the following set of files:

File Path

File Content

/adir/boo

A dog named named Boo

/adir/baa

A cat named Baa

/adir/bdir/baa

Cat cat

Your indexer should output:

"

?>

1

1

1

1

3

1

2

1

The inverted index file that your indexer writes must follow the XML format defined above. Words

must be sorted in alphanumeric order. All characters of a word should be first converted to lowercase

before the word is counted. Your output should print with the lists arranged in alphanumeric order (a to

z, 0 to 9) of the tokens. The filenames in your output should be in descending order by frequency

count (highest frequency to lowest frequency).If there is a word with the same frequency in two or

more files, order them by path name alphanumerically (a to z, 0 to 9).

After constructing the entire inverted index in memory, the indexer will save it to a file.

2. Implementation

Y

our program must implement the following command-line interface:

invertedI

ndex

The first argument, , gives the name of a file that you should create to

hold your inverted index. The second argument, , gives the name of the

directory

or

file that your indexer should index. If the second argument is a directory, you need to

recursively index all files in the directory (and its sub-directories). If the second argument is a file,

you just need to index that single file.

When indexing files in a directory, you may have files that have the same name in separate

directories. You should

combine all token frequencies for the same filename regardless of which

directory it appears in.

W

e define tokens as any sequence of consecutive alphanumeric characters (a-

z, A-Z, 0-9) starting with an alphabetic character.

Examples of tokens according to the above definition include:

a, aba, c123

If a file contains

This an$example12 mail@rutgers

it should tokenize to

this

an

example12

mail

rutgers

The XML format lets us easily read the inverted index for debugging. You should carefully consider

how the program may break and code it robustly. You should outline and implement a strategy to deal

with potential problems and inconsistencies. For example, if a file already exists with the same name

as the inverted-index file name, you should ask the user if they wish to overwrite it. If the name of the

directory or file you want to index does not exist, your indexer should print an error message and exit

gracefully rather than crash. There are many other error cases that you ought to consider.

3. Hints

Data structures that might be useful include a list that sorts as you insert and/or a hash table.

A custom record type (e.g., a record ({"baa" : 3}) that can be inserted into multiple data

structures, such as a sorted list and/or a hash table).

You should probably approach this in steps:

o First, build a simple tokenizer to parse tokens from a file.

o Next, get your program to walk through a directory.

o Next, implement a data structure that allows you to count the number of occurrences of each

unique token in a file.

And so on ...