Recitation 3

Table of Contents

In this recitation, you will get to see structs in action and familiarize yourself with some of the useful functions from string.h.

1) Text document similarity

A problem that commonly shows up in many fields is finding the similarity between text documents. For this purpose, we typically use the vector space model to represent text documents, wherein each document is represented with a vector.

Assume that we have pre-processed the documents and counted the number of times each word appears in a given document for you. You have access to files (each of which represents a document) where each line is in the following comma-delimited format:

word,frequency_in_doc

Each word is unique in that it only appears once in a given file. frequency_in_doc is a number that describes how many times the word appears in the document that the file represents.

1.1) Structs

1.1.1) wordFreq

As a first step in this direction, we would need a way to store, for each word, how many times it occurs in a particular document.

Write a struct called wordFreq that holds a string named word (at most 15 letters) and an integer named freq representing the frequency of the word.

struct wordFreq { // TODO };

Loading...

1.1.2) wordFreqs

You have designed a struct wordFreq, which stores one word and its frequency in a document.

Working on top of that, let us define for you an additional struct wordFreqs, as follows.

struct wordFreqs {
  struct wordFreq words[50];
  int length;
};

Assuming that there are at most 50 unique words in a document, each file can be represented with a single struct wordFreqs! The words array is an array consisting of every relevant wordFreq struct. length represents exactly how many words are currently valid in the struct.

1.2) Reading files

To avoid having to learn how C handles file input and output, we have put each file into a char array, where each line is separated by the newline character (\n).

1.2.1) Separating a string into lines (optional)

First, we need to find a way to extract lines from the provided char[]. In particular, we want a char[] (a char array) for each line in the input file.

To do this using the standard C library, we would use strtok, which splits up a char[] based upon some delimiter character(s). It is similar to str.split() from Python, but this function in C is stateful and works as an iterator. The value returned from strtok will be a pointer to the next delimited string; if one does not exist, then this value is the null pointer.

We'll show some slides here to go a bit more into strtok since it is likely the tricksiest of the string.h functions.

Note that strtok modifies the string that it works upon! It does NOT return copies of the substrings, but merely pointers to certain spots inside the original string which can now be treated as individual c-strings (since the function also inserts null characters for you).

Slides on strtok

Try filling out the missing code in this example that chops up the input string and prints every line from the input string. In addition, while doing this, the function should calculate and ultimately return the number of lines in the input string. We highly recommend that you look at the View Answer/View Explanation after solving this problem.

// this problem is optional int readFile(char *text){ int count = // TODO char delim // TODO, what can split the lines of a file? char* splitter = strtok(text, // TODO); while (splitter != // TODO) { printf("Printing current line %s\n", splitter); splitter = strtok(NULL, //TODO); } return count; }

Loading...

1.2.2) Creating wordFreq from a line

Great, so now we have a way to parse the lines in a string and can get access to the frequency count of each word in the document. However, each of these frequencies is a string, and we would like to represent these strings as integers, so that we can run calculations on them.

In Python, we could cast this value to an integer using int(). In C, we use the function atoi, which takes a char[] as an input and returns an integer representation of the string.

For each line in our string, we have a word, and its frequency in the document. Try writing a function that uses atoi to return a wordFreq struct that contains both the word in question as well as its frequency.

Hint: There are many string.h functions that can be useful here! We mention strtok above, but strcpy, strncpy, or strchr may also handy, depending on your approach.

struct wordFreq createWordFreq(char *line){ // TODO }

Loading...

1.2.3) Creating wordFreqs from a string (optional)

Now, write a function that populates the array within a wordFreqs struct and returns it.

struct wordFreqs parseFile(char *text){
    struct wordFreqs ret;
    // TODO
    return ret;
}

// this problem is optional struct wordFreqs parseFile(char *text){ struct wordFreqs ret; // TODO return ret; }

Loading...

Good job! But hang on a minute- the wordFreqs structure is actually quite large. Each wordFreq struct is 16 + 4 = 20 bytes, so each wordFreqs is 20 \times 50 + 4 = 1004 bytes. Passing it around (either as an input parameter or a return value) can cause an overhead.

Instead, we could design parseFile to be a function that takes in as a parameter a pointer to a pre-allocated wordFreqs struct. This way, we could populate the struct inside the function and wouldn't need to return a struct to the caller.

void parseFile(struct wordFreqs* w, char *text){
    // TODO: do something with w and text!
    return;
}

And then we could use it like so:

struct wordFreqs a;
parseFile(&a, some_text);

Yes, this feels better, much better! Now, your task is to implement our new parseFile.

Review: try using the arrow operator -> from lecture!

// let's say variable struct_ptr is a struct pointer
// to access the member "foo" of the struct that struct_ptr points to,
// you can do the following:

(*struct_ptr).foo = 9; // this sets the foo member = 9

// you need the parentheses because of the C Operator Hierarchy (for more info review the lecture slides!)

// instead you can use the arrow operator!:
struct_ptr->foo = 9; // this does the same thing

// this problem is optional void parseFile(struct wordFreqs* w, char* text){ // TODO return; }

Loading...

1.3) Partial similarity w.r.t. a particular word

Let's try using the structs and functions we have implemented above!

Let freq_K(w) be the frequency of word w in document K.

Let n_K be the total number of words in document K.

Define the partial similarity between documents A and B with respect to a particular word w as:

This quantity is between 0 and 1. Think about when it is closer to 1 and when it is closer to 0.

We will create a function that computes this quantity given two documents and a word.

1.3.1) Computing num_of_words

Let's write a function numOfWords to calculate the total number of (not necessarily distinct) words in the document. (This would simply be the sum of word frequencies in the document.) The function should take in a pointer to a wordFreqs struct and should return an int that is the total number of words.

Review: try using the arrow operator -> from lecture!

// let's say variable struct_ptr is a struct pointer
// to access the member "foo" of the struct that struct_ptr points to,
// you can do the following:

(*struct_ptr).foo = 9; // this sets the foo member = 9

// you need the parentheses because of the C Operator Hierarchy (for more info review the lecture slides!)

// instead you can use the arrow operator!:
struct_ptr->foo = 9; // this does the same thing

int numOfWords(struct wordFreqs* wfs){ //TODO }

Loading...

1.3.2) Computing the partial similarity(optional)

Now, write a function to compute the partial similarity as defined above!

You can call the parseFile (the version with 2 arguments) and numOfWords functions that we just implemented.

Hint: use strcmp() to compare whether two strings are equal.

// this problem is optional float calcSimilarity(char *text1, char *text2, char *word){ }

Loading...

2) Other exercises

2.1) Checking if a string contains a particular substring

There are many ways to do this - one way is to use strstr. strstr checks for the existence of a string needle (its second parameter) in a string haystack (its first parameter). If it is found, it will return a pointer to this occurrence. If it is not found it will return a null pointer.

Write a function that checks for the existence of a word in the text string. The function should return a 1 if the string exists and a 0 if the string doesn’t exist.

int checkWord(char *text, char *word){ //to do }

Loading...