Рубрики

Найти k наиболее часто встречающихся слов из файла

Дана книга слов. Предположим, у вас достаточно основной памяти, чтобы вместить все слова. спроектировать структуру данных, чтобы найти максимальное число K встречающихся слов. Структура данных должна быть динамичной, чтобы можно было добавлять новые слова.

Простым решением является использование хеширования . Хеш все слова одно за другим в хэш-таблице. Если слово уже присутствует, увеличьте его количество. Наконец, пройдите через хеш-таблицу и верните k слов с максимальным количеством.

Мы можем использовать Trie и Min Heap, чтобы эффективно получить k наиболее часто встречающихся слов. Идея состоит в том, чтобы использовать Trie для поиска существующих слов, эффективно добавляя новые слова. Три также хранит количество вхождений слов. Min Heap размера k используется для отслеживания k наиболее часто встречающихся слов в любой момент времени (использование Min Heap такое же, как мы использовали его, чтобы найти k самых больших элементов в этом посте).
Trie и Min Heap связаны друг с другом путем хранения дополнительного поля в Trie «indexMinHeap» и указателя «trNode» в Min Heap. Значение 'indexMinHeap' поддерживается равным -1 для слов, которые в данный момент отсутствуют в Min Heap (или в настоящее время не входят в число самых популярных k слов). Для слов, присутствующих в Min Heap, 'indexMinHeap' содержит индекс слова в Min Heap. Указатель 'trNode' в Min Heap указывает на листовой узел, соответствующий слову в Trie.

Ниже приводится полный процесс печати k наиболее часто встречающихся слов из файла.

Прочитайте все слова одно за другим. Для каждого слова вставьте его в Trie. Увеличьте счетчик слова, если он уже существует. Теперь нам нужно вставить это слово также в min heap. Для вставки в минимальную кучу возникает 3 случая:

1. Слово уже присутствует. Мы просто увеличиваем соответствующее значение частоты в min heap и вызываем minHeapify () для индекса, полученного с помощью поля «indexMinHeap» в Trie. Когда узлы минимальной кучи меняются местами, мы меняем соответствующий minHeapIndex в Trie. Помните, что каждый узел кучи min также имеет указатель на конечный узел Trie.

2. MinHeap не заполнен. мы вставим новое слово в min heap и обновим корневой узел в узле min heap и в индекс min heap в листовом узле Trie. Теперь вызовите buildMinHeap ().

3. Мин куча заполнена. Возникают два случая.
…. 3.1 Частота добавления нового слова меньше частоты слова, хранящегося в заголовке min heap. Ничего не делать.

…. 3.2 Частота добавления нового слова больше, чем частота слова, хранящегося в заголовке min heap. Заменить и обновить поля. Обязательно обновите соответствующий индекс минимальной кучи «заменяемого слова» в Trie на -1, так как слово больше не находится в минимальной куче.

4. Наконец, Min Heap будет иметь k наиболее часто встречающихся слов из всех слов, представленных в данном файле. Так что нам просто нужно напечатать все слова, присутствующие в Min Heap.

// Программа для поиска k наиболее часто встречающихся слов в файле
#include <stdio.h>
#include <string.h>
#include <ctype.h>

  
# define MAX_CHARS 26
# define MAX_WORD_SIZE 30

  
// Узел Trie

struct TrieNode

{

    bool isEnd; // указывает конец слова

    unsigned frequency;  // количество вхождений слова

    int indexMinHeap; // индекс слова в minHeap

    TrieNode* child[MAX_CHARS]; // представляет 26 слотов каждый от 'a' до 'z'.

};

  
// Узел Min Heap

struct MinHeapNode

{

    TrieNode* root; // указывает на конечный узел TRIE

    unsigned frequency; // количество вхождений

    char* word; // фактическое слово сохранено

};

  
// Мин куча

struct MinHeap

{

    unsigned capacity; // общий размер кучи мин

    int count; // указывает количество заполненных слотов.

    MinHeapNode* array; // представляет коллекцию minHeapNodes

};

  
// Служебная функция для создания нового узла Trie
TrieNode* newTrieNode()
{

    // Выделим память для узла Trie

    TrieNode* trieNode = new TrieNode;

  

    // Инициализировать значения для нового узла

    trieNode->isEnd = 0;

    trieNode->frequency = 0;

    trieNode->indexMinHeap = -1;

    for( int i = 0; i < MAX_CHARS; ++i )

        trieNode->child[i] = NULL;

  

    return trieNode;

}

  
// Вспомогательная функция для создания Min Heap заданной емкости

MinHeap* createMinHeap( int capacity )

{

    MinHeap* minHeap = new MinHeap;

  

    minHeap->capacity = capacity;

    minHeap->count  = 0;

  

    // Выделить память для массива узлов с минимальной кучей

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

  

    return minHeap;

}

  
// Вспомогательная функция для замены двух минимальных узлов кучи. Эта функция
// нужен в minHeapify

void swapMinHeapNodes ( MinHeapNode* a, MinHeapNode* b )

{

    MinHeapNode temp = *a;

    *a = *b;

    *b = temp;

}

  
// Это стандартная функция minHeapify. Это делает одну вещь дополнительно.
// Обновляет minHapIndex в Trie, когда два узла меняются местами
// в минимальной куче

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 )

    {

        // Обновляем соответствующий индекс в узле Trie.

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

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

  

        // Переставляем узлы в мин куче

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

  

        minHeapify( minHeap, smallest );

    }

}

  
// Стандартная функция для построения кучи

void buildMinHeap( MinHeap* minHeap )

{

    int n, i;

    n = minHeap->count - 1;

  

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

        minHeapify( minHeap, i );

}

  
// Вставляем слово в кучу, функция обрабатывает 3 случая, описанных выше

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

{

    // Случай 1: слово уже присутствует в minHeap

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

    {

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

  

        // просачиваться вниз

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

    }

  

    // Случай 2: слово отсутствует и куча не заполнена

    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 );

    }

  

    // Случай 3: слово отсутствует и куча заполнена. И частота слова

    // больше, чем root. Корень является наименее частым словом в куче,

    // заменить корень новым словом

    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 );

    }

}

  
// Вставляет новое слово в Trie и 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 );

    }

}

  

  
// добавить слово в Trie & min heap. Обертка над вставкой Util

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

{

    insertUtil( root, minHeap, word, word );

}

  
// Вспомогательная функция для отображения результатов, минимальная куча
// содержит k наиболее часто встречающихся слов на данный момент, в любое время

void displayMinHeap( MinHeap* minHeap )

{

    int i;

  

    // печатаем верхнее слово K с частотой

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

    {

        printf( "%s : %d\n", minHeap->array[i].word,

                            minHeap->array[i].frequency );

    }

}

  
// Основная функция, которая принимает файл в качестве входных данных, добавляет слова в кучу
// и Trie, наконец, показывает результат из кучи

void printKMostFreq( FILE* fp, int k )

{

    // Создаем минимальную кучу размера k

    MinHeap* minHeap = createMinHeap( k );

     

    // Создать пустую Trie

    TrieNode* root = NULL;

  

    // Буфер для хранения одного слова за раз

    char buffer[MAX_WORD_SIZE];

  

    // Читаем слова одно за другим из файла. Вставьте слово в Три и Мин Хип

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

        insertTrieAndHeap(buffer, &root, minHeap);

  

    // Min Heap будет иметь k наиболее часто встречающихся слов, поэтому выведите узлы Min Heap

    displayMinHeap( minHeap );

}

  
// Программа драйвера для проверки вышеуказанных функций

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;

}

Выход:

your : 3
well : 3
and : 4
to : 4
Geeks : 6

Приведенный выше вывод для файла со следующим содержанием.

Welcome to the world of Geeks 
This portal has been created to provide well written well thought and well explained 
solutions for selected questions If you like Geeks for Geeks and would like to contribute 
here is your chance You can write article and mail your article to contribute at 
geeksforgeeks org See your article appearing on the Geeks for Geeks main page and help 
thousands of other Geeks

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти k наиболее часто встречающихся слов из файла

0.00 (0%) 0 votes