Блог

Мой код где-то вызывает ошибку сегментации. Я не совсем уверен, как. Я не думаю, что это проблема с загрузкой, поскольку программа начинает перечислять слова с ошибками, прежде чем резко остановиться и выдать мне ошибку seg fault.

 // Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "dictionary.h"
#define HASHTABLE_SIZE 80000
unsigned int count = 0;

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH   1];
    struct node *next;
}
node;

// Number of buckets in hash table
const unsigned int N = HASHTABLE_SIZE;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    node *tmp = NULL;
    int ch = hash(word);
    int len = strlen(word);
  char w[len 1];
  
  for(int i = 0; i<len; i  )
  {
      w[i] = tolower(word[i]);
  }
  w[len] = '';
        tmp = table[ch];
        while(tmp->next != NULL)
        {
            if(strcmp(tmp->word, w) == 0)
            {
                return true;
            }
            if(tmp->next != NULL)
            {
             tmp = tmp->next;   
            }
            
        }
        return false;
  }



// Hashes word to a number
unsigned int hash(const char *word)
{
    int len = strlen(word);
    char key[len 1];
    for(int p = 0; p < len; p  )
    {
        key[p] = tolower(word[p]);
    }
    key[len] = '';
    
    unsigned int hash = 0;
    for (int i = 0, n = strlen(key); i < n; i  )
        hash = (hash << 2) ^ key[i];

    return hash % HASHTABLE_SIZE;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    
    FILE *file = fopen(dictionary, "r");
    if(file == NULL)
    {
        printf("could not open file.n");
        fclose(file);
        return false;
    }
    char temp[LENGTH   1];
    while(fscanf(file, "%s", temp) != EOF)
    {
        node *tmp = malloc(sizeof(node));
        strcpy(tmp->word, temp);
        unsigned int code = hash(temp);
        count  ;
        if(table[code] == NULL)
        {
            table[code] = tmp;
        }
        else if(table[code] != NULL)
        {
            
            node *pointer = table[code];
            while(pointer->next != NULL)
            {
              tmp->next = table[code];
              table[code] = tmp;
            }
                //YOU ARE HERE
            
        }
    }
    
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
  
    node* tmp = NULL;
    for(int i=0; i< N; i   )
    {
        if(table[i]!=NULL)
        {
            tmp = table[i];
            while(tmp->next != NULL)
            {
                tmp = tmp->next;
                count  ;
            }
        }
    }
   
    return count;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    node *tmp = NULL;
    node *del;
    for(int i = 0; i < N; i  )
    {
        tmp = table[i];
        while(tmp->next != NULL)
        {
            del = tmp;
            if(tmp->next != NULL)
            {
             tmp = tmp->next; 
            }
            free(del);
        }
        return true;
    }
    return false;
}

  

При запуске программы я получаю это:

 ~/pset5/speller/ $ ./speller dictionaries/large keys/her.txt

MISSPELLED WORDS

MISSPELLED
WORDS
Jonze
INT
Segmentation fault
  

Похоже, что он правильно загружает словарь и текст.

У вас есть несколько неправильных представлений о CS50 Speller. В частности, требование:

Ваша реализация проверки должна быть нечувствительной к регистру. Другими словами, если foo находится в словаре, то проверка должна возвращать значение true с учетом любой его заглавной буквы; ни один из foo , foO , fOo fOO , fOO Foo FoO , FOo FOO ,,,,,,,,,,,,,,,,,,,,, и,,,,, следует считать написанным с ошибкой.

Это означает, что при загрузке словаря в хэш-таблицу необходимо преобразовать словарное слово в нижний регистр перед вычислением хэша. В противном случае, когда вы check(word) и вы конвертируете копию word в нижний регистр, вы никогда не вычислите тот же хэш, если исходное словарное слово не было преобразовано в нижний регистр перед хэшированием.

Ваша check(word) функция также не преобразуется в нижний регистр перед вычислением хэша. Это приведет к пропуску словарного слова, которое было хэшировано со строчной формой словарного слова. Вы также допускаете ошибку сегментации, потому что вы не можете проверить, что это tmp не NULL перед разыменованием tmp->next . Но вы были на правильном пути с основами того, как проверить хэш-таблицу в противном случае.

Поскольку вы будете преобразовывать в нижний регистр как перед хэшированием и сохранением словарного слова, так и перед хэшированием копии слова для проверки, имело бы смысл использовать простую функцию преобразования строки в нижний регистр. Затем вы можете уменьшить свою check() функцию до:

 // string to lower
char *str2lower (char *str)
{
    if (!str) return NULL;

    char *p = str;

    for (; *p; p  )
        if (isupper((unsigned char)*p))
            *p ^= ('A' ^ 'a');

    return str;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    char lcword[LENGTH 1];          /* make a copy of word from txt to convert to lc */
    size_t len = strlen (word);     /* get length of word */
    unsigned h;
    
    if (len > LENGTH) { /* validate word will fit */
        fprintf (stderr, "error: check() '%s' exceeds LENGTH.n", word);
        return false;
    }
    memcpy (lcword, word, len 1);   /* copy word to lower-case word */
    
    h = hash (str2lower(lcword));   /* convert to lower-case then hash */
    for (node *n = table[h]; n; n = n->next)    /* now loop over list nodes */
        if (strcmp (lcword, n->word) == 0)      /* compare lower-case words */
            return true;
        
    return false;
}
  

Next, though not discussed in the problem-set, you should not skimp on hash-table size. There are 143091 words in dictionaries/large . Ideally, you want to keep the load-factor of your hash table less than 0.6 (no more than 60% of your buckets filled to minimize collisions) I haven’t tested the actual load factor for your table, but I wouldn’t want anything less than N == 8000

обновление: я проверил, и с N == 131072 вашим коэффициентом загрузки загрузка large словаря с использованием lh_strhash() будет 0.665 такой, что вы захотите повторно хэшировать, но для ваших целей все должно быть в порядке. (примечательно, что все дополнительные хранилища не улучшают загрузку времени проверки более чем на сотую долю секунды (что указывает на то, что они достаточно эффективны даже при обработке дополнительных столкновений)

Хэш-функции

Вы можете поэкспериментировать с несколькими, но используя /usr/share/dict/words (откуда large берется) Я обнаружил, что хеш-функция OpenSSL lh_strhash() обеспечивает минимальное количество коллизий, будучи при этом довольно эффективной. Вы можете реализовать свою hash() функцию как оболочку и таким образом быстро попробовать несколько разных хэшей, например

 // openSSL lh_strhash
uint32_t lh_strhash (const char *s)
{
    uint64_t ret = 0, v;
    int64_t n = 0x100;
    int32_t r;

    if (!s || !*s) return (ret);

    for (; *s; s  ) {
        v = n | (*s);
        n  = 0x100;
        r = (int32_t)((v >> 2) ^ v) amp; 0x0f;
        ret = (ret << r) | (ret >> (32 - r));
        ret amp;= 0xFFFFFFFFL;
        ret ^= v * v;
    }
    return ((ret >> 16) ^ ret);
}

// Hashes word to a number
unsigned int hash (const char *word)
{
    return lh_strhash (word) % N;
}
  

Ваша load() функция страдает от той же ошибки при преобразовании в нижний регистр перед хэшированием. Вы не можете переставлять и сохранять каждую перестановку заглавных букв для каждого слова в словаре в своей хэш-таблице. Поскольку вы должны выполнять преобразование без учета регистра check() , имеет смысл только преобразовать (в верхний или нижний — быть последовательным) перед хэшированием и сохранением.

Кроме того, нет необходимости выполнять итерацию до последнего узла для корзины перед вставкой новой записи в список этой корзины. (это довольно неэффективно) Вместо этого просто используйте метод, называемый «прямая цепочка«, чтобы вставить новый узел по адресу корзины, переместив то, что там было, на ->next указатель, прежде чем устанавливать корзину на адрес нового узла. Это приводит к O (1) временным вставкам. Например:

 // Loads dictionary into memory, returning true if successful else false
bool load (const char *dictionary)
{
    char word[MAXC];
    FILE *fp = fopen (dictionary, "r");
    
    if (!fp) {
        perror ("fopen-dictionary");
        return false;
    }
    
    while (fgets (word, MAXC, fp)) {
        unsigned h;
        size_t len;
        node *htnode = NULL;
        
        word[(len = strcspn(word, " rn"))] = 0;   /* trim n or terminate at ' ' */
        if (len > LENGTH) {
            fprintf (stderr, "error: word '%s' exceeds LENGTH.n", word);
            continue;
        }
        
        if (!(htnode = malloc (sizeof *htnode))) {
            perror ("malloc-htnode");
            return false;
        }
        h = hash (str2lower(word));
        
        memcpy (htnode->word, word, len 1);     /* copy word to htnode->word */
        htnode->next = table[h];                /* insert node at table[h] */
        table[h] = htnode;                      /* use fowrard-chaining for list */
        
        htsize  ;                               /* increment table size */
    }
    
    fclose (fp);
    
    return htsize > 0;
}
  

Что касается размера хэш-таблицы, просто добавьте значение global в dictionary.c и увеличьте это значение, как сделано в load() выше (это htsize переменная). Это делает работу таблицы size() такой простой, как:

 // Hash table size
unsigned htsize;
...
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size (void)
{
    return htsize;
}
  

Ваш unload() немного запутанный и не сможет освободить выделенную память, в которой есть один узел table[i] . Вместо этого вы можете сократить свою логику и выполнить то, что вам нужно с:

 // Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i  ) {
        node *n = table[i];
        while (n) {
            node *victim = n;
            n = n->next;
            free (victim);
        }
    }
    
    htsize = 0;
    
    return true;
}
  

Пример использования / разница с ключами

Создание test/ каталога и последующее перенаправление выходных данных в файлы в test/ каталоге позволит вам сравнить результаты с ожидаемыми результатами:

 $ ./bin/speller texts/bible.txt > test/bible.txt
  

keys/ Каталог содержит выходные данные из кода «staff». Эта реализация соответствует выводам ключей, но также включает информацию о времени (это не то, что вы можете изменить — это жестко запрограммировано в speller.c , которое вы не можете изменить в соответствии с ограничением на упражнение):

 $ diff -uNb keys/bible.txt test/bible.txt
--- keys/bible.txt      2019-10-08 22:35:16.000000000 -0500
    test/bible.txt      2020-09-01 02:09:31.559728835 -0500
@@ -33446,3  33446,9 @@
 WORDS MISSPELLED:     33441
 WORDS IN DICTIONARY:  143091
 WORDS IN TEXT:        799460
 TIME IN load:         0.03
 TIME IN check:        0.51
 TIME IN size:         0.00
 TIME IN unload:       0.01
 TIME IN TOTAL:        0.55
 
  

(примечание: -b опция позволяет diff "ignore changes in the amount of white space" игнорировать изменения в окончаниях строк, например, в DOS "rn" по сравнению с Linux 'n' )

Единственными различиями между выводом кода и файлами в keys/ каталоге являются строки, отмеченные ' ' знаком в первом столбце (последние 6 строк), показывающие информацию о времени — единственное отличие.

Использование памяти / проверка ошибок

Вся память правильно освобождена:

 $ valgrind ./bin/speller texts/lalaland.txt > test/lalaland.txt
==10174== Memcheck, a memory error detector
==10174== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==10174== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==10174== Command: ./bin/speller texts/lalaland.txt
==10174==
==10174==
==10174== HEAP SUMMARY:
==10174==     in use at exit: 0 bytes in 0 blocks
==10174==   total heap usage: 143,096 allocs, 143,096 frees, 8,026,488 bytes allocated
==10174==
==10174== All heap blocks were freed -- no leaks are possible
==10174==
==10174== For counts of detected and suppressed errors, rerun with: -v
==10174== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
  

Просмотрите все и дайте мне знать, если у вас возникнут дополнительные вопросы.

Если вы затрудняетесь с деталями, это полное dictionary.c использование, и я добавил loadfactor() функцию в конце, чтобы вы могли вычислить коэффициент загрузки для различных значений на N , если вам интересно:

 // Implements a dictionary's functionality

#include "dictionary.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <ctype.h>

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH   1];
    struct node *next;
}
node;

// Number of buckets in hash table
#define N 131072

// Max Characters Per-Line of Input
#define MAXC 1024

// Hash table
node *table[N];

// Hash table size
unsigned htsize;

// string to lower
char *str2lower (char *str)
{
    if (!str) return NULL;

    char *p = str;

    for (; *p; p  )
        if (isupper((unsigned char)*p))
            *p ^= ('A' ^ 'a');

    return str;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    char lcword[LENGTH 1];          /* make a copy of word from txt to convert to lc */
    size_t len = strlen (word);     /* get length of word */
    unsigned h;
    
    if (len > LENGTH) { /* validate word will fit */
        fprintf (stderr, "error: check() '%s' exceeds LENGTH.n", word);
        return false;
    }
    memcpy (lcword, word, len 1);   /* copy word to lower-case word */
    
    h = hash (str2lower(lcword));   /* convert to lower-case then hash */
    for (node *n = table[h]; n; n = n->next)    /* now loop over list nodes */
        if (strcmp (lcword, n->word) == 0)      /* compare lower-case words */
            return true;
         
    return false;
}

// openSSL lh_strhash
uint32_t lh_strhash (const char *s)
{
    uint64_t ret = 0, v;
    int64_t n = 0x100;
    int32_t r;

    if (!s || !*s) return (ret);

    for (; *s; s  ) {
        v = n | (*s);
        n  = 0x100;
        r = (int32_t)((v >> 2) ^ v) amp; 0x0f;
        ret = (ret << r) | (ret >> (32 - r));
        ret amp;= 0xFFFFFFFFL;
        ret ^= v * v;
    }
    return ((ret >> 16) ^ ret);
}

// Hashes word to a number
unsigned int hash (const char *word)
{
    return lh_strhash (word) % N;
}

// Loads dictionary into memory, returning true if successful else false
bool load (const char *dictionary)
{
    char word[MAXC];
    FILE *fp = fopen (dictionary, "r");
    
    if (!fp) {
        perror ("fopen-dictionary");
        return false;
    }
    
    while (fgets (word, MAXC, fp)) {
        unsigned h;
        size_t len;
        node *htnode = NULL;
        
        word[(len = strcspn(word, " rn"))] = 0;   /* trim n or terminate at ' ' */
        if (len > LENGTH) {
            fprintf (stderr, "error: word '%s' exceeds LENGTH.n", word);
            continue;
        }
        
        if (!(htnode = malloc (sizeof *htnode))) {
            perror ("malloc-htnode");
            return false;
        }
        h = hash (str2lower(word));
        
        memcpy (htnode->word, word, len 1);     /* copy word to htnode->word */
        htnode->next = table[h];                /* insert node at table[h] */
        table[h] = htnode;                      /* use fowrard-chaining for list */
        
        htsize  ;                               /* increment table size */
    }
    
    fclose (fp);
    
    return htsize > 0;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size (void)
{
    return htsize;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i  ) {
        node *n = table[i];
        while (n) {
            node *victim = n;
            n = n->next;
            free (victim);
        }
    }
    
    htsize = 0;
    
    return true;
}

float loadfactor (void)
{
    unsigned filled = 0;
    
    for (int i = 0; i < N; i  )
        if (table[i])
            filled  ;
    
    return (float)filled / N;
}