Задания четвертой недели курса CS50 (Speller хеш таблицы и Speller префиксного дерева)

4.7 (93.33%) 9 vote[s]

Задача по проверке орфографии Speller. В этом задании предлагается решить одну из задач (на оценку):

  • Speller (с использованием хэш-таблицы).
  • Speller (с использованием префиксного дерева).

Понимание

Теоретически, на входных данных размера n, алгоритм со временем выполнения n симптотично эквивалентный в терминах O-нотации алгоритму с временем выполнения 2n. На самом деле, когда мы описываем время выполнения алгоритма, то обычно сосредотачиваемся на основном (потому, что имеет наибольшее влияние) времени (в данном случае — n, поскольку n может быть гораздо большим, чем 2). В реальном мире же, 2n выполняется вдвое медленнее n.

Ваша задача — реализовать как можно более быструю программу для проверки орфографии! Когда мы говорим о перспективе программы, мы имеем в виду такую, что будет быстрее выполняться в условиях реального времени, а не в условиях асимптотики.

Для работы нужно скачать speller.zip с необходимыми для работы файлами.

Speller с использованием хеш-таблиц

В файле speller.c находится программа созданная для проверки орфографии в файле после загрузки словаря с диска в память. Словарь размещено в файле dictionary.c. (Его можно было бы включить в speller.c, но программы становятся все более сложными, поэтому время от времени логично разбивать их на отдельные файлы.) Прототипы функций одновременно определены не в самом файле dictionary.c, а в файле dictionary.h. Таким образом, оба файла — speller.c и dictionary.c могут подключать этот файл с помощью #include.

Нужно реализовать часть с проверкой орфографии.

dictionary.h

Откройте файл dictionary.h, и вы увидите новый синтаксис, включая строки, с  DICTIONARY_H. Эти строки позволяют убедиться, что, несмотря на то, что dictionary.c и speller.c подсоединяют этот файл с помощью #include, clang скомпилирует его только один раз.

Далее с помощью #include добавляем файл stdbool.h. В нем определен тип bool. Ранее он не был нужен, поскольку использовалась библиотека CS50.

Директива  # define препроцессора определяет константу LENGTH со значением 45. Она является константой. Вы не можете менять ее в собственном коде. Компилятор clang автоматически заменит все упоминания о LENGTH в коде 45.  Другими словами, это не переменная, это просто трюк с поиском и заменой текста.

Обратите внимание на четыре функции: check, load, size, и unload. Две из них при помощи * принимают указатели  як аргументы :

bool check(const char *word);

bool load(const char *dictionary);

dictionary.c

Это файл, который требуется завершить.

Сверху файла определен struct под названием node. Эта структура представляет узел в хэш-таблице. Также мы объявили глобальный массив hashtable. В нем хватит места для N указателей на узлы, где N инициализирован перед этим массивом как 26 (по одной ячейке для каждой буквы английского алфавита).

Далее имплементирована функция hash хеша слова. Она возвращает 0 для каждого слова, которое начинается с a (или A), 1 для каждого слова, которое начинается с b (или B), 25 для каждого слова, которое начинается с z (или Z), а так же для каждой буквы внутри.

Функция load, которая будет загружать словарь слов к хэш-таблицы. В этом файле есть часть кода который инициализирует все ячейки (указатели) в hashtable к NULL. Также есть код  открывания dictionary (что является названием файла словаря, который надо загрузить) и код, который проходит этим словарем и читает слова в нем по одному за раз, в буфер ((т.е. string), который называется word).

check, size, и unload имплементированы вскользь, чтобы скомпилировался файл.

Файл speller.c изменять нельзя!

Рекомендуется просто изучить его для понимания логики работы кода.

texts

Чтобы вы могли проверить реализацию speller и сравнить с реализацией кода командой CS50 используем texts. В неммного различных текстов. Среди них есть сценарий La La Land, три миллиона байтов текстов Толстого, некоторые выдержки из Записок Федералиста и Шекспира, полный текст Библии Короля Якова V и Корана и тому подобное. Для того, чтобы знать, чего ожидать, откройте и посмотрите каждый из этих файлов, все из которых находятся в папке texts.

После компиляции и выполнения кода командой ./speller texts/lalaland.txt вывод должен выглядеть так:

 MISSPELLED WORDS
  
 [...]
 AHHHHHHHHHHHHHHHHHHHHHHHHHHHT
 [...]
 Shangri
 [...]
 fianc
 [...]
 Sebastian's
 [...]
  
 WORDS MISSPELLED:
 WORDS IN DICTIONARY:
 WORDS IN TEXT:
 TIME IN load:
 TIME IN check:
 TIME IN size:
 TIME IN unload:
 TIME IN TOTAL: 

Где:

      • TIME IN load — это время (в секундах) необходим speller на выполнение вашей реализации load.
      • TIME IN check — это время (в секундах) необходим speller на выполнение вашей реализации check.
      • TIME IN size — это время (в секундах) необходим speller на выполнение вашей реализации size.
      • TIME IN unload — это время (в секундах) необходимое speller на выполнение вашей реализации unload.
      • TIME IN TOTAL — сумма 4-х предыдущих значений.

Спецификация

Реализуйте  load, size, check, и unload так эффективно, как только это только возможно, чтобы минимизировать TIME IN load, TIME IN check, TIME IN size, и TIME IN unload. В данном случае речь не идет об  эффективности использования памяти, а именно о фактическом быстродействии:

      • Нельзя изменять speller.c или Makefile.
      • Изменяется только dictionary.c (завершить реализацию load, size, check, и unload), но нельзя изменять объявления load, size, check, или unload. Можно добавлять новые глобальные или локальные функции.
      • Реализация check должна быть нечувствительна к регистру. Иными словами, если foo в словаре, то check должен вернуть true для любого слова, отличается от foo только регистром символов. Любое слово из списка foo, foO, fOo, fOO, fOO, Foo, FoO, FOo, и FOO является корректным.
      • Реализация check должна возвращать true только для имеющихся в dictionary слов. Не нужно возвращать true для притяжательных прилагательных, если их нет в словаре dictionary. Если в словаре есть слово foo, но нет foo’s, check должен вернуть true для foo и false для foo’s. Главное правило: true возвращается только для слов, имеющихся в словаре без учета регистра

Можно считать, что:

      • Любой словарь dictionary, переданный программе, будет структурирован так же, как наш, лексикографически отсортированный сверху вниз, словом в строке, каждое из которых заканчивается на \ n.
      • Словарь содержит хотя бы одно слово и ни одно слово не будет дольше LENGTH (константа в dictionary.h) символов.
      • Ни одно слово не появится чаще одного раза, и каждое слово состоит только из символов (букв алфавита) в нижнем регистре и апострофов. Также, ни одно слово не начнется с апострофа
      • check будет получать только строки с символами из алфавита и, возможно, апострофами.

В программе не должно быть утечек памяти. Обязательно проверьте на утечки с помощью valgrind (valgrind ./speller texts/cat.txt).

Вот вариант реализации кода dictionary.c с комментариями:

// Implements a dictionary's functionality
#include <stdio.h>
#include <stdbool.h>
#include <cs50.h>
#include <string.h>
#include <ctype.h>

#include "dictionary.h"
#define HASHTABLE_SIZE 1985

//Устанавливает указатель для связанного списка
typedef struct node
{
    char word[LENGTH + 1];
    struct node* next;
}
node;

//Хэш-прототип
unsigned long hash(char *str);

//Установить указатель на хеш-таблицу
node *hashtable[HASHTABLE_SIZE];

//Счетчик слов в функции размера
int word_count = 0;

// Возвращает true, если слово находится в словаре, иначе false
bool check(const char *word)
{
    //Преобразовать слово в нижний регистр
    int n = strlen(word);
    char copy[n + 1];

    //Добавить нулевой терминатор в конец слова нижнего регистра
    copy[n] = '\0';

    for(int i = 0; i < n; i++)
    {
        copy[i] = tolower(word[i]);
    }
    //Передайте слово в нижнем регистре хэш-функции, чтобы получить индекс
    int index = hash(copy) % HASHTABLE_SIZE;

    //Установить заголовок связанного списка
    node* head = hashtable[index];

    if (head != NULL)
    {
        //Направляет курсор на то же место
        node* cursor = head;

        //Пройдите по связанному списку
        while(cursor != NULL)
        {
            if(strcmp(copy, cursor->word) == 0)
            {
          //Вернуть true, если слово соответствует слову в нашем словаре
                return true;
            }
            //В противном случае переместите курсор на следующий связанный список
            cursor = cursor->next;
        }
    }
    return false;
}
// Загружает словарь в память, возвращая true, если успешно, иначе false
bool load(const char *dictionary)
{
    //Открыть словарь только для чтения
    FILE* file = fopen(dictionary, "r");
    //Проверьте, если словарь пуст
    if (file == NULL)
    {
        fprintf(stderr, "Could not open file %s.\n", dictionary);
        return false;
    }
    // установить буфер для хранения выходного слова
    char buffer[LENGTH + 1];
    int n = LENGTH + 2;
    // цикл по словарю до нулевого символа
    while (fgets(buffer, n, file) != NULL)
    {
        // добавить нулевой терминатор в конце слова
        buffer[strlen(buffer) - 1] = '\0';
        //хэш слово
        int index = hash(buffer) % HASHTABLE_SIZE;
    	// создать временный узел
    	node* temp = malloc(sizeof(node));
    	//Проверьте, не является ли узел нулевым
    	if (temp == NULL)
    	{
    	    fclose(file);
    	    return false;
    	}
        //Перейти к следующему узлу в списке
    	strcpy(temp -> word, buffer);
        temp -> next = hashtable[index];
        hashtable[index] = temp;
        word_count++;
    }
    // закройте файл
    fclose(file);
    return true;
}
// Возвращает количество слов в словаре, если загружено, иначе 0, если еще не загружено
unsigned int size(void)
{
    return word_count;
}
// Выгружает словарь из памяти, возвращая true в случае успеха, иначе false
bool unload(void)
{
    // для каждого узла в хеш-таблице
    for (int i = 0; i < HASHTABLE_SIZE; i++)
    {
        // проверить таблицу для узла по этому индексу
        node* cursor = hashtable[i];
        while (cursor != NULL)
        {
            // создать временный узел
            node* temp = cursor;
            cursor = cursor -> next;

            // освободить текущий узел
            free(temp);
        }
    }
    return true;
}
unsigned long hash(char *str)
{
    unsigned long hash = 5381;
    int c;

    while ((c = *str++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

Тестирование

Проверка работы программы выполняется командами

./speller texts/lalaland.txt > student.txt

~cs50/pset4/speller texts/lalaland.txt > staff.txt

В папке будет записано два файла student.txt(ваш результат) и staff.txt (результат команды).

Сравнить результаты в одном окне терминала (так удобнее) можно командой:

diff -y student.txt staff.txt

Столбцы должны полностью быть идентичными. Допускается небольшое отклонение в TIME IN load, TIME IN check, TIME IN size, и TIME IN unload.

Народная мудростьПословица

 

Speller с использованием префиксного дерева

Для работы с этим заданием необходимо скачать архив с исходными файлами speller_trie.zip.

В файле dictionary.c уже определена struct под названием node. Эта структура представляет узел в дереве. Также уже объявлен глобальный массив, root, который представляет главный узел в дереве.

Спецификация задания аналогичная. Вот вариант решения к этому заданию с комментариями:

#include <stdbool.h>
#include <ctype.h>    
#include "dictionary.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

// глобальный счетчик
int count = 0;     

// структура данных
typedef struct node {         
    bool end_word;
    struct node *children[27];
    } node;

// прототип функции
int
charNumber(char c);   
void 
freeNode(node *currentNode);

node root = {false,{NULL}};

/*
 * Возвращает true, если слово в словаре, иначе false.
 */

bool
check(const char *word)
{
    node *ptr = &root;
    for (int i=0;i<strlen(word);i++)
    {     
         // проверка очень эффективна в древовидной структуре!Время проверки связано только с длиной слова.
        if (ptr->children[charNumber(word[i])] == NULL)  
            return false;                                
        ptr = ptr->children[charNumber(word[i])];       
    } 
        // обратите внимание, здесь вы должны проверить, действительно ли это конец слова в словаре.
    if (ptr->end_word)  
        return true;
    else
        return false;
}

/*
 * Загружает словарь в память. Возвращает true, если успешно, иначе false.
 */

bool
load(const char *dictionary)
{
    FILE *fp = fopen(dictionary,"r");
    if (fp == NULL)
        return false;
    while (!feof(fp))
    {
        char word[LENGTH+1] = {};
        fscanf(fp,"%s\n",word); // нужно использовать "% s \ n" вместо "% s", иначе счет будет неправильным.
        count++;    
        node *ptr = &root;
        for (int i=0;i<strlen(word);i++)
        {
            if (ptr->children[charNumber(word[i])] == NULL)  // если это NULL, malloc новый узел, укажите на него.
            {
                node *new = malloc(sizeof(node));   
                *new = (node) {false,{NULL}};       // инициализация
                ptr->children[charNumber(word[i])] = new;
                ptr = new;
            }
            else
            {
                ptr = ptr->children[charNumber(word[i])];  // если это не так, просто укажите на следующий узел.
            }
         }
         ptr->end_word = true;  // если слово заканчивается, пометьте «end_word» как true.
    }
fclose(fp);          // Вы не хотите забыть файл.
return true;
}

/*
 * рассчитать число для персонажа
 */

int
charNumber(char c)
{
    int num;
    if (c == '\'')
        return 26;
    else if(c >= 'A' && c <= 'Z')
        c += 32;
    num = c - 'a';
    return num;
}

/*
 * Возвращает количество слов в словаре, если загружено, иначе 0, если еще не загружено.
 */

unsigned int
size(void)
{
    if (count)
        return count;
    else
        return 0;
}

/*
 * Выгружает словарь из памяти. Возвращает true, если успешно, иначе false.
 */

bool
unload(void)
{
    for (int i=0;i<27;i++)            // нельзя просто вызвать freeNode (& root), это приведет к свободному (& root), но
    {
        if (root.children[i] != NULL)  //root не в куче (потому что он не выделен malloc)
            freeNode(root.children[i]);
    }
    return true;         
}
void freeNode(node *currentNode)
{
    for (int i=0;i<27;i++)
    {
        if (currentNode->children[i] != NULL)   
            freeNode(currentNode->children[i]); 
    }
    free(currentNode);
 }

Читайте больше по теме:

Подписаться
Уведомление о
guest
0 комментариев
Inline Feedbacks
View all comments
Просмотры: 2557

Популярные записи