C++ Program to Find Most Frequent Words from a File
Posted by Superadmin on August 10 2022 12:51:10

C++ Program to Find Most Frequent Words from a File

This C++ Program Finds the Most Frequent Words in a File.

Here is source code of the C++ Program to Find k Most Frequent Words in a File. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/* 
```

 * C++ Program to Find k Most Frequent Words in a File

    minHeap->array = new MinHeapNode [minHeap->capacity];

```
    return minHeap;
```
```
}
```
```
/* 
```
```
 * swap two min heap nodes.
```
```
 */  
```

void swapMinHeapNodes (MinHeapNode* a, MinHeapNode* b)

```
{
```
```
    MinHeapNode temp = *a;
```
```
    *a = *b;
```
```
    *b = temp;
```
```
}
```
```
 
```
```
/* 
```
```
 * min heapify
```
```
 */
```

void minHeapify(MinHeap* minHeap, int idx)

```
{
```
```
    int left, right, smallest;
```
```
    left = 2 * idx + 1;
```
```
    right = 2 * idx + 2;
```
```
    smallest = idx;
```

    if (left < minHeap->count && minHeap->array[left].frequency < minHeap->array[smallest].frequency)

```
        smallest = left;
```

    if (right < minHeap->count && minHeap->array[right].frequency < minHeap->array[smallest].frequency)

```
        smallest = right;
```
```
    if (smallest != idx)
```
```
    {
```

        minHeap->array[smallest].root->indexMinHeap = idx;

        minHeap->array[idx].root->indexMinHeap = smallest;

        swapMinHeapNodes (&minHeap->array[smallest], &minHeap->array[idx]);

```
        minHeapify(minHeap, smallest);
```
```
    }
```
```
}
```
```
 
```
```
/* 
```
```
 * build a heap
```
```
 */
```
```
void buildMinHeap(MinHeap* minHeap)
```
```
{
```
```
    int n, i;
```
```
    n = minHeap->count - 1;
```

    for (i = ( n - 1 ) / 2; i >= 0; --i)

```
        minHeapify(minHeap, i);
```
```
}
```
```
 
```
```
/* 
```
```
 * inserts a word to heap
```
```
 */
```

void insertInMinHeap(MinHeap* minHeap, TrieNode** root, const char* word)

```
{
```
```
    if ((*root)->indexMinHeap != -1)
```
```
    {
```

        ++( minHeap->array[(*root)->indexMinHeap].frequency);

        minHeapify(minHeap, (*root)->indexMinHeap);

```
    }
```

    else if (minHeap->count < minHeap->capacity)

```
    {
```
```
        int count = minHeap->count;
```

        minHeap->array[count].frequency = (*root)->frequency;

        minHeap->array[count].word = new char [strlen( word ) + 1];

        strcpy(minHeap->array[count].word, word);

        minHeap->array[count].root = *root;

        (*root)->indexMinHeap = minHeap->count;

```
        ++( minHeap->count );
```
```
        buildMinHeap( minHeap );
```
```
    }
```

    else if ((*root)->frequency > minHeap->array[0].frequency)

```
    {
```

        minHeap->array[0].root->indexMinHeap = -1;

```
        minHeap->array[0].root = *root;
```

        minHeap->array[0].root->indexMinHeap = 0;

        minHeap->array[0].frequency = (*root)->frequency;

        delete [] minHeap->array[0].word;

        minHeap->array[0]. word = new char [strlen( word ) + 1];

        strcpy( minHeap->array[0].word, word );

```
        minHeapify (minHeap, 0);
```
```
    }
```
```
}
```
```
/* 
```

 * Inserts a new word to both Trie and Heap

```
 */ 
```

void insertUtil (TrieNode** root, MinHeap* minHeap, const char* word, const char* dupWord)

```
{
```
```
    if (*root == NULL)
```
```
        *root = newTrieNode();
```
```
    if (*word != '\0')
```

        insertUtil (&((*root)->child[tolower( *word ) - 97]), minHeap, word + 1, dupWord);

```
    else
```
```
    {
```
```
        if ((*root)->isEnd)
```
```
            ++((*root)->frequency);
```
```
        else
```
```
        {
```
```
            (*root)->isEnd = 1;
```
```
            (*root)->frequency = 1;
```
```
        }
```

        insertInMinHeap(minHeap, root, dupWord);

```
    }
```
```
}
```
```
/* 
```
```
 * add a word to Trie & min heap
```
```
 */  
```

void insertTrieAndHeap(const char *word, TrieNode** root, MinHeap* minHeap)

```
{
```

    insertUtil(root, minHeap, word, word);

```
}
```
```
 
```
```
/* 
```
```
 * Display Min Heap
```
```
 */
```
```
void displayMinHeap(MinHeap* minHeap)
```
```
{
```
```
    int i;
```

    for (i = 0; i < minHeap->count; ++i)

```
    {
```

       cout<<minHeap->array[i].word<<" : "<<minHeap->array[i].frequency<<endl;

```
    }
```
```
}
```
```
/* 
```

 * takes a file as input, add words to heap and Trie

```
 */ 
```
```
void printKMostFreq(FILE* fp, int k)
```
```
{
```

    MinHeap* minHeap = createMinHeap(k);

```
    TrieNode* root = NULL;
```
```
    char buffer[MAX_WORD_SIZE];
```

    while (fscanf(fp, "%s", buffer) != EOF)

        insertTrieAndHeap(buffer, &root, minHeap);

```
    displayMinHeap(minHeap);
```
```
}
```
```
/* 
```
```
 * Main
```
```
 */ 
```
```
int main()
```
```
{
```
```
    int k = 5;
```
```
    FILE *fp = fopen("file.txt", "r");
```
```
    if (fp == NULL)
```
```
        printf ("File doesn't exist ");
```
```
    else
```
```
        printKMostFreq (fp, k);
```
```
    return 0;
```
```
}
```

$ g++ mosty_frequent.cpp
$ a.out
---------------------file.txt----------------------
Bessie can score a point in the game by picking two of the dots and drawing a straight line between them; however, she is not allowed to draw a line if she has already drawn another line parallel to it. Bessie would like to know her chances of winning, so she has asked you to help find the maximum score she can obtain.
------------------------------------------------------
 
the : 3
line : 3
she : 4
to : 4
a : 3
 
------------------
(program exited with code: 1)
Press return to continue