CSE225-Project 1 Solved

Traditional representation methodology of documents in the literature is called Bag of Words (BOW) feature representation.  This representation symbolizes the terms and their corresponding frequencies in a document and it is also named as Vector Space Model (VSM).  Each of these terms in the same document represents an independent dimension in a vector space [1]. The order of words in the sentences is completely lost in bag representation like in sets. This approach mainly emphasizes the frequency of terms. The BOW methodology makes the representation of words simpler in documents; still; it has several problems. One of them is sparse vector representation. This makes the computation expensive especially for real world scenarios, which include big data in textual domains. To address this problem; this project aims to create more a more efficient representation of BOW model by using LinkedLists. Consequently, this project is a programming assignment in C, which aims to build an algorithm based on linked-lists that will build an efficient representation of documents.

Your program needs to open and read text files under the following directories: sport, magazine and health. These are 3 categories of 1150Haber dataset [2]. The number of documents in these categories will be arbitrary. Furthermore, the number of terms in these documents will also be arbitrary.  In other words, the length of these files will be arbitrary.

Your program is expected to do the followings:

a)     (40 points)  You need to read all the documents under all the categories. Then you need to build a Master Linked-List (MLL). Each node in this MLL needs to represent a different term in these documents. All the terms in these documents are expected to be in the MLL. There will be cases, the same word occur in different documents, or in the same document. Then, you do not need to add a term into the MLL if it already exists. In other words, be careful about not entering the duplicate records into the MLL. This list needs to be in ascending order.  

 

Each record in MLL has 2 pointers: The first of them is for the next record in MLL. The second of them is for the starting record of another Linked-List. This sub LinkedList will represent the documents that contain the term in this record of MLL. Figure-1 shows the structure of MLL.

 

 

 

 

                                             Master Linked List (MLL) with N nodes (master-linked-list) 

  

 

 

Figure.1. Schema of the Master-Linked-List and the Linked-List of Documents

 

 

 

 

 

b)     (30 points) Finding stop words/general words (noise in the documents): You need to find the first 5 general words which occur in all of the categories. In other words, you need to list the terms that are common for all of the categories. The output will be like the following (it needs to be listed in ascending order):

 

Term-1: aaa

Term-2: bbb

Term-3: ccc

Term-4: ddd

Term-5: eee

 

c)     (30 points) Finding discriminating words: You need to find the first 5 words for each category which occur in that category only, not in other categories. The output will be like the following: (it needs to be listed in ascending order)

 

Category-1
Category-2
Category-3
Term-1
Term-1a
Term-1b
Term-2
Term-2a
Term-2b
Term-3
Term-3a
Term-3b
Term-4
Term-4a
Term-4b
Term-5
Term-5a
Term-5b