[자료구조 - C++] Assignment 3 Hash Map을 통해 단어 빈도수 확인 기능 구현하기

세번째 과제는 바로 Hash Map을 응용하여 문장에서 단어의 빈도수를 파악하는 프로그램을 제작하는 것이었다. 특이 사항은 모든 단어를 소문자로 바꿔서 생각하고, non-alphabetic 글자들을 무시하도록 하는 것이다. 더불어 non-alphabetic한 글자들이 들어가있을 경우 그것을 delimiter로 사용하여 글자를 분리시킨다. 예컨대, "I'm"은 "i" + "m"으로 각각 취급한다. 

주어진 파일은 총 9개. 이 중에서 map.txx 파일과 wordfrequency.cpp 파일을 수정 및 구현하여 제출하도록 되어있었다.

1-1) 구현해야 하는 함수들 - map.txx

// destructor
template <class HashMapElemType>
HashMap<HashMapElemType>::~HashMap() 
{
	// ToDo
}
	
template <class HashMapElemType>
HashMapElemType* 
HashMap<HashMapElemType>::find(const KeyType k) 
{ 
	// ToDo
}
	
template <class HashMapElemType>
void 
HashMap<HashMapElemType>::insert(const KeyType k, const ValType v) 
{
	// ToDo
}
		
template <class HashMapElemType>
bool 
HashMap<HashMapElemType>::remove(const KeyType k) 
{
	// ToDo	
	return true;
}
	
template <class HashMapElemType>
unsigned int 
HashMap<HashMapElemType>::hashfunction(const KeyType k)
{
	// ToDo	
	int hash_val;
	
	return hash_val;
}

template <class HashMapElemType>
void 
HashMap<HashMapElemType>::print()
{
	// ToDo
}

참고사항 : 

(1) Constructor with initial hash table size of c. : c의 사이즈를 가진 해쉬 테이블을 생성하는 생성자.

HashMap(unsigned int c)

(2) Return the size of the key-value pair : key-value 쌍의 개수를 반환하는 함수.

int size()

(3) Return true if no key-value pair is in the map : 만약 key-value 쌍이 존재하지 않으면 true를 반환, 이외의 경우 false 반환.

bool isEmpty()

(4) If k is in the map, return the pair (k,v) as MapElem. If find is not successful, return NULL. : 만약 k가 맵에 존재하면 key와 value 쌍을 반환하라. 만약 존재하지 않는다면 NULL을 반환.

HashMapElem* find(const key k)

(5) Insert a pair (k, v) in the map. If k is already in the map, change its value with v. : (k, v)를 맵에 저장. 이미 k가 맵에 존재한다면 value를 v로 바꿀 것.

void insert(const key k, const value v)

(6) If k is in the map, remove its pair (k,v) and return true. If k is not in the map, return false. : 만약 k가 맵에 있으면 key와 value쌍을 맵에서 제거하고 true를 반환하라. 만약 k가 맵에 없으면 false를 반환하라.

bool remove(const key k)

(7) Print all key:value pair in decreasing order of value. : 맵에 존재하는 모든 key를 내림차순으로 출력하라.

void print()

(8) Returns an integer hash value converted from a key k. : key인 k를 해쉬함수에 넣어서 변환한 후 반환.

 

unsigned int hashfunction(const KeyType k)

 

1-2) 구현해야 하는 함수들 - wordfrequency.cpp

WordFrequency::WordFrequency()
{
	// ToDo
}

WordFrequency::~WordFrequency()
{
	// ToDo
}

void WordFrequency::ReadText(const char* filename)
{
	// ToDo
}

int WordFrequency::GetFrequency(const std::string word)
{
	// ToDo
	
	return 0;
}

void WordFrequency::IncreaseFrequency(const std::string word)
{
	// ToDo
}

참고사항 :

Find the frequency of a given word. If the word is not found, return 0. : 주어진 단어의 빈도수를 찾아라. 만약 단어를 찾을 수 없으면 0을 반환하라.

int GetFrequency(const std::string word)

Find the frequency of a given word and increase it by 1. If the word is not found, set its frequency by 1. : 주어진 단어의 빈도수를 찾아 1만큼 증가시켜라. 만약 단어를 찾을 수 없으면 해당 단어의 빈도수를 1로 설정하라.

 

void IncreaseFrequency(const std::string word)

Print out the frequency of all words in the text in decreasing order of its occurrence : 모든 단어의 빈도수를 내림차순으로 출력하라.

 

 

void PrintAllFrequency()

 

2) map.h

#ifndef HASHMAP_H
#define HASHMAP_H

#include <iostream>

// Map element
template <class KeyType, class ValType>
class MapElem
{
public:
	typedef KeyType ktype;
	typedef ValType vtype;

	KeyType key;
	ValType val;

	MapElem* link;
};

//
// Map data structure
//
template <class HashMapElemType>
class HashMap
{
public:
	typedef typename HashMapElemType::ktype KeyType;
	typedef typename HashMapElemType::vtype ValType;

	// constructor
	HashMap(unsigned int c = 1000) {
		mapsize  = 0;
		capacity = c;
		divisor  = c - (1-c%2); // biggest odd number smaller than c
		ht = new HashMapElemType* [capacity];
		for(int i=0; i<capacity; i++) ht[i] = NULL;
	};

	// destructor
	~HashMap();

	// Modify below functions
	int size() { return mapsize; };

	bool isEmpty() { return (mapsize == 0); };

	// ToDo
	HashMapElemType* find(const KeyType k);

	void insert(const KeyType k, const ValType v);

	bool remove(const KeyType k);

	void print();

private: // Member function
	// Hash function
	unsigned int hashfunction(const KeyType k);

private: // Member variables
	// Hash Table
	HashMapElemType** ht;

	unsigned int mapsize, capacity, divisor;
};

#ifndef HASHMAP_HPP
#define HASHMAP_HPP
#include "map.txx"
#endif

#endif

3) map.txx - 구현 파일

// destructor
template <class HashMapElemType>
HashMap<HashMapElemType>::~HashMap() 
{
HashMapElemType* del_hash;
HashMapElemType* hash_check;    //traversing the hash map
for(int i = 0; i < capacity; i++)
    {
        if(ht[i] != NULL)
        {
            hash_check = ht[i];
            while(hash_check != NULL)
            {
                del_hash = hash_check;  //temporarily saving the value 
                			//at the del_hash
                remove(del_hash->key);
                hash_check = hash_check->link;
            }
        }
    }
delete[] ht;   //because it is two dimension array, 
		//we have to delete it twice.
}

template <class HashMapElemType>
HashMapElemType* 
HashMap<HashMapElemType>::find(const KeyType k) 
{
    if(isEmpty())
        return NULL;
    else
    {
        int hash_key = hashfunction(k);
        HashMapElemType* hash_check = ht[hash_key];
        if(ht[hash_key] == NULL)
            return NULL;
        else
        {
            while(hash_check != NULL)
            {
                if(hash_check->key == k)
                    return hash_check;
                hash_check = hash_check->link;
            }
            return NULL;
        }
    }
}
	
template <class HashMapElemType>
void 
HashMap<HashMapElemType>::insert(const KeyType k, const ValType v) 
{
    HashMapElemType* hash_temp;
    int hash_key = hashfunction(k);
    
    if(ht[hash_key] == NULL){   //when ht[hash_key] is empty, 
    				//just insert at the ht.
        ht[hash_key] = new HashMapElemType;
        ht[hash_key]->key = k;
        ht[hash_key]->val = v;
        ht[hash_key]->link = NULL;
        mapsize++;
        }
    else{
            HashMapElemType* trav = ht[hash_key];
            if(find(k) != NULL) //if same key already exitsts 
            		//then replace it.
                find(k)->val = v;
            else
            {
            hash_temp = new HashMapElemType;
            hash_temp->val = v;
            hash_temp->key = k;
            hash_temp->link = NULL;
            while(trav->link != NULL){trav = trav->link;}
            trav->link = hash_temp;
            mapsize++;
        }
        }
}

    
		
template <class HashMapElemType>
bool 
HashMap<HashMapElemType>::remove(const KeyType k) 
{
    int hash_key = hashfunction(k);
    HashMapElemType* hash_check;
    HashMapElemType* prev_hash; //we need prev pointer because 
    				//we need to link it the next one before 
                    //we remove the one.
    HashMapElemType* hash_temp;
    if(isEmpty())
        return false;
    else
    {
        if(ht[hash_key] == NULL)
            return false;
        else
        {
            if(ht[hash_key] == find(k)){   //when the first slot is the finding one
            hash_temp = ht[hash_key]->link;  //save the next one
            delete ht[hash_key];
            ht[hash_key] = hash_temp;    //resaving with the preserved one
            mapsize--;
            return true;
            }
            else
            {
                hash_check = ht[hash_key];
                    while(hash_check != NULL)
                    {
                        prev_hash = hash_check;
                        hash_check = hash_check->link;
                        if(hash_check->key == k)
                        {
                            prev_hash->link = hash_check->link;
                            delete hash_check;
                            mapsize--;
                            return true;
                        }
                    }
                return false;
            }
        }
    }
}
	
template <class HashMapElemType>
unsigned int 
HashMap<HashMapElemType>::hashfunction(const KeyType k)
{
    int hash_val;
    unsigned int h = 0;
    int key_size = k.size();    //you can use k.length() instead.
    for(int i = 0; i < key_size; i++){ //cyclic shift hash function
        h = (h << 5) | (h >> 27);   //5 bit
        h += (unsigned int) k[i];
    }
    hash_val = h % divisor;
    return hash_val;
}

template <class HashMapElemType>
void 
HashMap<HashMapElemType>::print()   //use signly linked list to print 
						//the sorted hash map key & values
{
    HashMapElemType* trav;
    HashMapElemType* sorted[size()];
    HashMapElemType* iter;
    HashMapElemType* new_node;
    
    if(isEmpty())
        std::cout << "(This map is empty.)" << std::endl;

    else
    {
        for(int k = 0; k < size(); k++)
            sorted[k] = NULL;
        for(int i = 0; i < capacity; i++)
        {
            for(trav = ht[i]; trav != NULL; trav = trav->link)
            {
                new_node = new HashMapElemType;
                new_node->key = trav->key;
                new_node->val = trav->val;
                if(sorted[0] == NULL || trav->val > sorted[0]->val)
                {
                    new_node->link = sorted[0];
                    sorted[0] = new_node;
                }
                else
                {
                    iter = sorted[0];
                    while(iter->link != NULL && iter->link->val > new_node->val)
                    iter = iter->link;
                    new_node->link = iter->link;
                    iter->link = new_node;
                }
            }
        }
        for(iter = sorted[0]; iter != NULL; iter = iter->link)
        std::cout << iter->key << " : " << iter->val << std::endl;
    }
}

4) wordfrequency.h

#ifndef WORDFREQUENCY_H
#define WORDFREQUENCY_H

#include "map.h"
#include <iostream>

typedef MapElem<std::string,int> WordFreqElem;
typedef HashMap<WordFreqElem> WordFreqMap;

// WORDFREQUENCY class
class WordFrequency {
public:
	WordFrequency();
	~WordFrequency();
	
	void ReadText(const char* filename);
		
	int GetFrequency(const std::string word);
	
	void IncreaseFrequency(const std::string word);
	
	void PrintAllFrequency()
	{
		map->print();
	}
	
private:
	// add whatever you want
	WordFreqMap *map;
};

#endif

5) wordfrequency.cpp - 구현 파일

#include "wordfrequency.h"
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>

WordFrequency::WordFrequency()
{
    map = new WordFreqMap;
}

WordFrequency::~WordFrequency()
{
    map = nullptr;
    delete map;
}

void WordFrequency::ReadText(const char* filename)
{
    std::fstream file;
    file.open(filename, std::ios::in);
    if(!file.is_open())
    {
        std::cout << "Error! Unable to open '" << filename << "'"  << std::endl;
    }
    else
    {
        std::string s;
        std::string str;
        while(!file.eof())
        {
            std::getline(file, s);
            str += s + ' ';
        }
        str.pop_back(); //erase the last space
        std::istringstream iss(str);
        
        do{
            std::string sub;
            std::string newsub;
            iss >> sub;
            std::transform(sub.begin(), sub.end(),
                           sub.begin(), ::tolower); //make the character to lower case
            int len = sub.length();
            for(int i = 0; i < len; i++)
            {
                if(sub[i] > 96 && sub[i] < 123) //only if it is low case alphabet, store it.
                    newsub += sub[i];
                else    //think all non alphabetic letter as delimiter. Then stores the letters before it came out to the hash map, and it clears the buffer so that the letters come out next to it can be stored again.
                {
                    if(newsub.length()>0)   //only cares if the letters' length is bigger than zero
                    {
                        IncreaseFrequency(newsub);
                        newsub.clear();
                    }
                }
                
            }
            if(newsub.length() > 0)
                IncreaseFrequency(newsub);
        }while(iss);
    }
}

int WordFrequency::GetFrequency(const std::string word)
{
    WordFreqElem* is_freq;
    is_freq = map->WordFreqMap::find(word);
    if(is_freq != NULL)
    {
        int freq = 0;
        freq = is_freq->val;
        return freq;
    }
    else
    {
        return 0;
    }
}

void WordFrequency::IncreaseFrequency(const std::string word)
{
    if(GetFrequency(word) != 0) //as GetFrequency function returns zero or the int values, we only need to check its frequency is whether zero or else.
    {
        int freq = 0;
        freq = this->map->WordFreqMap::find(word)->val;
        freq++;
        map->WordFreqMap::insert(word, freq);
    }
    else
    {
        map->WordFreqMap::insert(word, 1);
    }
    
}

6) cat_in_the_hat.txt

THE CAT IN THE HAT

Then our mother came in
And she said to us two,
“Did you have any fun?
Tell me. What did you do?”

And Sally and I did not
know what to say.
Should we tell her
The things that went on
there that day?

Well... what would YOU do
If your mother asked you?

Look at me!
Look at me!
Look at me NOW!
It is fun to have fun
But you have
to know how.

7) cat_in_the_hat2.txt

THE CAT IN THE HAT Then our mother came in And she said to us two Did you have any fun Tell me What did you do And Sally and I did not know what to say Should we tell her The things that went on there that day Well what would YOU do If your mother asked you Look at me Look at me Look at me NOW It is fun to have fun But you have to know how

8) input.txt

I like a coffee and you like a tea.
We like a coffee and a tea.

9) steve_jobs.txt

I am honored to be with you today at your commencement from one of the finest universities in the world. I never graduated from college. Truth be told, this is the closest I've ever gotten to a college graduation. Today I want to tell you three stories from my life. That's it. No big deal. Just three stories.

The first story is about connecting the dots.

I dropped out of Reed College after the first 6 months, but then stayed around as a drop-in for another 18 months or so before I really quit. So why did I drop out?

It started before I was born. My biological mother was a young, unwed college graduate student, and she decided to put me up for adoption. She felt very strongly that I should be adopted by college graduates, so everything was all set for me to be adopted at birth by a lawyer and his wife. Except that when I popped out they decided at the last minute that they really wanted a girl. So my parents, who were on a waiting list, got a call in the middle of the night asking: "We have an unexpected baby boy; do you want him?" They said: "Of course." My biological mother later found out that my mother had never graduated from college and that my father had never graduated from high school. She refused to sign the final adoption papers. She only relented a few months later when my parents promised that I would someday go to college.

And 17 years later I did go to college. But I naively chose a college that was almost as expensive as Stanford, and all of my working-class parents' savings were being spent on my college tuition. After six months, I couldn't see the value in it. I had no idea what I wanted to do with my life and no idea how college was going to help me figure it out. And here I was spending all of the money my parents had saved their entire life. So I decided to drop out and trust that it would all work out OK. It was pretty scary at the time, but looking back it was one of the best decisions I ever made. The minute I dropped out I could stop taking the required classes that didn't interest me, and begin dropping in on the ones that looked interesting.

It wasn't all romantic. I didn't have a dorm room, so I slept on the floor in friends' rooms, I returned coke bottles for the 5¢ deposits to buy food with, and I would walk the 7 miles across town every Sunday night to get one good meal a week at the Hare Krishna temple. I loved it. And much of what I stumbled into by following my curiosity and intuition turned out to be priceless later on. Let me give you one example:

Reed College at that time offered perhaps the best calligraphy instruction in the country. Throughout the campus every poster, every label on every drawer, was beautifully hand calligraphed. Because I had dropped out and didn't have to take the normal classes, I decided to take a calligraphy class to learn how to do this. I learned about serif and san serif typefaces, about varying the amount of space between different letter combinations, about what makes great typography great. It was beautiful, historical, artistically subtle in a way that science can't capture, and I found it fascinating.

None of this had even a hope of any practical application in my life. But ten years later, when we were designing the first Macintosh computer, it all came back to me. And we designed it all into the Mac. It was the first computer with beautiful typography. If I had never dropped in on that single course in college, the Mac would have never had multiple typefaces or proportionally spaced fonts. And since Windows just copied the Mac, it's likely that no personal computer would have them. If I had never dropped out, I would have never dropped in on this calligraphy class, and personal computers might not have the wonderful typography that they do. Of course it was impossible to connect the dots looking forward when I was in college. But it was very, very clear looking backwards ten years later.

Again, you can't connect the dots looking forward; you can only connect them looking backwards. So you have to trust that the dots will somehow connect in your future. You have to trust in something — your gut, destiny, life, karma, whatever. This approach has never let me down, and it has made all the difference in my life.

My second story is about love and loss.

I was lucky — I found what I loved to do early in life. Woz and I started Apple in my parents garage when I was 20. We worked hard, and in 10 years Apple had grown from just the two of us in a garage into a $2 billion company with over 4000 employees. We had just released our finest creation — the Macintosh — a year earlier, and I had just turned 30. And then I got fired. How can you get fired from a company you started? Well, as Apple grew we hired someone who I thought was very talented to run the company with me, and for the first year or so things went well. But then our visions of the future began to diverge and eventually we had a falling out. When we did, our Board of Directors sided with him. So at 30 I was out. And very publicly out. What had been the focus of my entire adult life was gone, and it was devastating.

I really didn't know what to do for a few months. I felt that I had let the previous generation of entrepreneurs down - that I had dropped the baton as it was being passed to me. I met with David Packard and Bob Noyce and tried to apologize for screwing up so badly. I was a very public failure, and I even thought about running away from the valley. But something slowly began to dawn on me — I still loved what I did. The turn of events at Apple had not changed that one bit. I had been rejected, but I was still in love. And so I decided to start over.

I didn't see it then, but it turned out that getting fired from Apple was the best thing that could have ever happened to me. The heaviness of being successful was replaced by the lightness of being a beginner again, less sure about everything. It freed me to enter one of the most creative periods of my life.

During the next five years, I started a company named NeXT, another company named Pixar, and fell in love with an amazing woman who would become my wife. Pixar went on to create the worlds first computer animated feature film, Toy Story, and is now the most successful animation studio in the world. In a remarkable turn of events, Apple bought NeXT, I returned to Apple, and the technology we developed at NeXT is at the heart of Apple's current renaissance. And Laurene and I have a wonderful family together.

I'm pretty sure none of this would have happened if I hadn't been fired from Apple. It was awful tasting medicine, but I guess the patient needed it. Sometimes life hits you in the head with a brick. Don't lose faith. I'm convinced that the only thing that kept me going was that I loved what I did. You've got to find what you love. And that is as true for your work as it is for your lovers. Your work is going to fill a large part of your life, and the only way to be truly satisfied is to do what you believe is great work. And the only way to do great work is to love what you do. If you haven't found it yet, keep looking. Don't settle. As with all matters of the heart, you'll know when you find it. And, like any great relationship, it just gets better and better as the years roll on. So keep looking until you find it. Don't settle.

My third story is about death.

When I was 17, I read a quote that went something like: "If you live each day as if it was your last, someday you'll most certainly be right." It made an impression on me, and since then, for the past 33 years, I have looked in the mirror every morning and asked myself: "If today were the last day of my life, would I want to do what I am about to do today?" And whenever the answer has been "No" for too many days in a row, I know I need to change something.

Remembering that I'll be dead soon is the most important tool I've ever encountered to help me make the big choices in life. Because almost everything — all external expectations, all pride, all fear of embarrassment or failure - these things just fall away in the face of death, leaving only what is truly important. Remembering that you are going to die is the best way I know to avoid the trap of thinking you have something to lose. You are already naked. There is no reason not to follow your heart.

About a year ago I was diagnosed with cancer. I had a scan at 7:30 in the morning, and it clearly showed a tumor on my pancreas. I didn't even know what a pancreas was. The doctors told me this was almost certainly a type of cancer that is incurable, and that I should expect to live no longer than three to six months. My doctor advised me to go home and get my affairs in order, which is doctor's code for prepare to die. It means to try to tell your kids everything you thought you'd have the next 10 years to tell them in just a few months. It means to make sure everything is buttoned up so that it will be as easy as possible for your family. It means to say your goodbyes.

I lived with that diagnosis all day. Later that evening I had a biopsy, where they stuck an endoscope down my throat, through my stomach and into my intestines, put a needle into my pancreas and got a few cells from the tumor. I was sedated, but my wife, who was there, told me that when they viewed the cells under a microscope the doctors started crying because it turned out to be a very rare form of pancreatic cancer that is curable with surgery. I had the surgery and I'm fine now.

This was the closest I've been to facing death, and I hope it's the closest I get for a few more decades. Having lived through it, I can now say this to you with a bit more certainty than when death was a useful but purely intellectual concept:

No one wants to die. Even people who want to go to heaven don't want to die to get there. And yet death is the destination we all share. No one has ever escaped it. And that is as it should be, because Death is very likely the single best invention of Life. It is Life's change agent. It clears out the old to make way for the new. Right now the new is you, but someday not too long from now, you will gradually become the old and be cleared away. Sorry to be so dramatic, but it is quite true.

Your time is limited, so don't waste it living someone else's life. Don't be trapped by dogma — which is living with the results of other people's thinking. Don't let the noise of others' opinions drown out your own inner voice. And most important, have the courage to follow your heart and intuition. They somehow already know what you truly want to become. Everything else is secondary.

When I was young, there was an amazing publication called The Whole Earth Catalog, which was one of the bibles of my generation. It was created by a fellow named Stewart Brand not far from here in Menlo Park, and he brought it to life with his poetic touch. This was in the late 1960's, before personal computers and desktop publishing, so it was all made with typewriters, scissors, and polaroid cameras. It was sort of like Google in paperback form, 35 years before Google came along: it was idealistic, and overflowing with neat tools and great notions.

Stewart and his team put out several issues of The Whole Earth Catalog, and then when it had run its course, they put out a final issue. It was the mid-1970s, and I was your age. On the back cover of their final issue was a photograph of an early morning country road, the kind you might find yourself hitchhiking on if you were so adventurous. Beneath it were the words: "Stay Hungry. Stay Foolish." It was their farewell message as they signed off. Stay Hungry. Stay Foolish. And I have always wished that for myself. And now, as you graduate to begin anew, I wish that for you.

Stay Hungry. Stay Foolish.

Thank you all very much.

10) main.cpp

#include "wordfrequency.h"
 
using namespace std;

int main()
{
	typedef MapElem<std::string,int> ElemType;
	typedef HashMap<WordFreqElem> MapType;	

	// Map Test
	MapType myMap;
    
	myMap.insert("James", 35);
	myMap.insert("Tom", 12);
	myMap.insert("Kevin", 27);
	myMap.insert("Jessica", 43);
  
    myMap.print();
	
	
	// Word Frequency Test
	WordFrequency freqChecker;
    
	freqChecker.ReadText("input.txt");
    
	cout << "Print all results" << endl;
	freqChecker.PrintAllFrequency();
	
	
	return 0;
}

도출해야 하는 결과 : 

input.txt를 읽었을 때 나와야 하는 결과

steve_jobs.txt를 읽었을 때 나와야 하는 결과

구현한 파일의 결과 : 

input.txt 파일의 결과

steve_jobs.txt 파일의 결과

점수 : 100/100

어렵지만 재밌었던 과제였다. 나에게 있어 이 과제에서의 관건은 어떻게 Hash Map의 Value대로 정렬을 하느냐였는데, 고민했던 건 새로운 Array를 만들어서 거기에 저장한 후 sorting을 하거나 아니면 linked list처럼 체인으로 엮어서 insertion sort를 하느냐였는데, 결국 선택한 것은 후자였다. 선택한 이유는 이전 과제에서 doubly linked list를 써보고 신세계를 맛보기도 했을 뿐더러 굳이 배열에 저장하고 그 후에 정렬을 하자니 차라리 linked list를 통해서 넣는 즉시 정렬을 하는 것이 낫다고 판단했기 때문이다.