БЛОГ НА HUSL


В чем причина такого поведения программы?

Автор вопроса: Konstantin_SH

Пытаюсь реализовать алгоритм Лемпеля-Зива-Вейча на С. Есть структура

// слова будем хранить в структуре

typedef struct Word {

unsigned int code; 
char * value; 
} Word;

Есть словарь

// Словарь может хранить 4096 слов

Word * dictionary [4096];

Этот словарь я изначально заполнил ASCII таблицей

// Префикс и суффикс текущего слова
Word prefix;
Word sufix;

// Начальная инициализация словаря
// Значения Суффикса и префикса будем хранить в виде С-строк, чтобы иметь возможность использовать функции strcat() strcpy()
 // значению суффикса выделяем 2 байта

sufix.value = malloc(2* sizeof(char)); 
for (int i = 0; i < 256; i++){
 // Переводим ASCII В C-строку, записываем ее в словарь
 sufix.value [0] = i;
 sufix.value [1] = '\0';
 dictionary[i] = malloc (sizeof(Word));
 dictionary[i] -> value = malloc (2* sizeof(char));
 strcpy (dictionary[i]->value, sufix.value);
 dictionary [i] ->code = i;

}

// После инициализации в словаре хранятся строки "[ASCII-код]\0"

free(sufix.value);

Цикл сжатия:

    // будем использовать переменную для проверки есть ли слово в словаре
    int inDictionary =1;

// пока не конец файла Переприсваиваем currentCharCode код нового символа 

while ((currentCharCode = fgetc(inFile)) != EOF ){
    // формируем суффикс
    realloc (sufix.value, 2*sizeof(char));
    realloc (prefix.value, sizeof(prefix.value+ sizeof(char)));
    sufix.value[0] = currentCharCode;
    sufix.value[1] = '\0';
    sufix.code = currentCharCode;
    
    if (prefix.value == NULL) strcpy(prefix.value, sufix.value);
    // К нашему текущему префиксу добавляем суффикс Теперь слово у нас расширилось на один символ       
    else strcat (prefix.value, sufix.value);

            // Проверяем словарь
                for (int i = 0 ; i< freeCode; i++){
                // если мы найдем в словаре наш префикс, то коду префикса назначаем соответствующий код из словаря 
                    if (strcmp (prefix.value, dictionary[i]->value) == 0){
                    prefix.code = dictionary[i]->code;
                inDictionary = 1;
                // Выходим из цикла проверки, возвращаемся к основному циклу            
                    }
                    else {
                        inDictionary =0;
                    }
                }
            if(inDictionary ==0){
               //Если выполнилось условие проверки, то это значит, что расширенного слова нет в нашем словаре, значит
            // выделяем память под слово с первым свободным кодом 
             dictionary [freeCode] = malloc (sizeof(Word));
             // выделяем память под значение нового слова в словаре
             dictionary [freeCode]-> value = malloc (sizeof(prefix.value));
             // копируем новое слово в словарь
             dictionary[freeCode] -> value = strcpy (dictionary [freeCode]->value, prefix.value);
             // Назначаем ему код
             prefix.code = freeCode;

             dictionary[freeCode]->code = prefix.code;
             // Мы записали расширенное в словарь 

             // Выводим в выходной поток код слова, которое есть в словаре
            fprintf (outFile, "%d", prefix.code);
            
             // Теперь текущим словом должен стать суффикс расширенного слова

             strcpy (prefix.value, sufix.value);
             prefix.code = sufix.code;
             
             free (sufix.value);

             // и увеличиваю код свободного слова
             freeCode++;
            }
        }

В файле для сжатия у меня строка abacabadabacabae, как в примере. Мой алгоритм справляется с расширенными словами из двух символов, а вот дальше его глючит. После завершения цикла сжатия я вывел на консоль весь словарь:

    for (int i = 0; i < freeCode; i++){
        printf ("it`s %d word in dictionary = %s\r\n", dictionary[i]->code, dictionary[i]->value);
    }
    return outFile;
}

Вывод такой:

   it`s 0 word in dictionary =
   it`s 1 word in dictionary = 
   it`s 2 word in dictionary = 
   it`s 3 word in dictionary = 
   it`s 4 word in dictionary = 
   ...
   it`s 254 word in dictionary = ■
   it`s 255 word in dictionary =  
   it`s 254 word in dictionary = ■
   it`s 255 word in dictionary =  
   it`s 256 word in dictionary = ab
   it`s 257 word in dictionary = ba
   it`s 258 word in dictionary = ac
   it`s 259 word in dictionary = ca
   it`s 260 word in dictionary = ab
   it`s 261 word in dictionary = ba
   it`s 262 word in dictionary = dabacabae

А дальше консоль зависает и ее приходится закрывать.

У меня три вопроса, помогите разобраться:

  1. Почему происходит зависание программы?

  2. С чем связан баг с 262 словом в словаре и как его исправить?

  3. Опять же по поводу 262 слова: почему не формируются слова из трех символов? Я думал, что

      realloc (prefix.value, sizeof(prefix.value+ sizeof(char)));

добавит 1 байт памяти для слова любой длинны и то, что было 2 байта станет 3 и т.д.

P.S Полный код программы

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

#include "lzwlib.h"
// слова будем хранить в структуре

typedef struct Word {

unsigned int code; 
char * value; 
} Word;



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

FILE * compress (const char* inputFileName) {
// Далее идет код, в котором формирую имя файла с расширением .lzw, наш выходной поток
//... 

char * outputFileName = malloc (strlen (inputFileName)+5);

strcpy (outputFileName, inputFileName);

char * ex = strchr (outputFileName, '.');

if (ex) strcpy (ex, ".lzw");

else strcat (outputFileName, ".lzw");
// Теперь открываем наши файлы


FILE* outFile;
outFile = fopen (outputFileName, "w");

FILE* inFile; 
inFile = fopen (inputFileName, "r");

free (outputFileName);

// свободный код 

unsigned int freeCode = 256;
// Переменная, где будем хранить текущий код символа из входного файла
int currentCharCode;


// Словарь состоит из 4096 слов

Word * dictionary [4096];
// Префикс и суффикс текущего слова
Word prefix;
Word sufix;

// Начальная инициализация словаря
// Значения Суффикса и префикса будем хранить в виде С-строк, чтобы иметь возможность использовать функции strcat() strcpy()
 // значению суффикса выделяем 2 байта

sufix.value = malloc(2* sizeof(char)); 
for (int i = 0; i < 256; i++){
 // Переводим ASCII В C-строку, записываем ее в словарь
 sufix.value [0] = i;
 sufix.value [1] = '\0';
 dictionary[i] = malloc (sizeof(Word));
 dictionary[i] -> value = malloc (2* sizeof(char));
 strcpy (dictionary[i]->value, sufix.value);
 dictionary [i] ->code = i;

}

// После инициализации в словаре хранятся строки "[ASCII-код]\0"

free(sufix.value);

// Записываем в префикс с-строку [ASCII-код]\0 первого символа из входного потока 

currentCharCode = fgetc(inFile);

prefix.value = malloc(2*sizeof(char));
prefix.value[0] = currentCharCode;
prefix.value[1] = '\0';
prefix.code = currentCharCode;
// Сразу выводим в выходной файл код первого символа

fprintf (outFile, "%d", prefix.code);
    // будем использовать переменную для проверки есть ли слово в словаре
    int inDictionary =1;

// пока не конец файла Переприсваиваем currenCharCode код нового символа 

while ((currentCharCode = fgetc(inFile)) != EOF ){
    // формируем суффикс
    realloc (sufix.value, 2*sizeof(char));
    prefix.value = realloc(prefix.value, strlen(prefix.value) + 2);
    sufix.value[0] = currentCharCode;
    sufix.value[1] = '\0';
    sufix.code = currentCharCode;
    
    if (prefix.value == NULL) strcpy(prefix.value, sufix.value);
    
    // К нашему текущему префиксу добавляем суффикс Теперь слово у нас расширилось на один символ       
    else strcat (prefix.value, sufix.value);



            // Проверяем словарь
                for (int i = 0 ; i< freeCode; i++){
                // если мы найдем в словаре наш префикс, то коду префикса назначаем соответствующий код из словаря 
                    if (strcmp (prefix.value, dictionary[i]->value) == 0){
                    prefix.code = dictionary[i]->code;
                inDictionary = 1;
                // Выходим из цикла проверки, возвращаемся к основному циклу 
                
                    }
                    else inDictionary = 0;
                }
            if(inDictionary ==0){
               //Если выполнилось условие проверки, то это значит, что расширенного слова нет в нашем словаре, значит
            // выделяем память под слово с первым свободным кодом 
             dictionary [freeCode] = malloc (sizeof(Word));
             // выделяем память под значение нового слова в словаре
             dictionary [freeCode]-> value = malloc (strlen(prefix.value) + 1);
             // копируем новое слово в словарь
             dictionary[freeCode] -> value = strcpy (dictionary [freeCode]->value, prefix.value);
             // Назначаем ему код
             prefix.code = freeCode;

             dictionary[freeCode]->code = prefix.code;
             // Мы записали расширенное в словарь 

             // Выводим в выходной поток код слова, которое есть в словаре
            fprintf (outFile, "%d", prefix.code);
            
             // Теперь текущим словом должен стать суффикс расширенного слова

             strcpy (prefix.value, sufix.value);
             prefix.code = sufix.code;
             
             free (sufix.value);
             

             // и увеличиваю код свободного слова
             freeCode++;
             inDictionary =1;
            }
        
            
        }
  fclose (inFile);
    fclose (outFile);

    for (int i = 0; i < freeCode; i++){
        printf ("it`s %d word in dictionary = %s\r\n", dictionary[i]->code, dictionary[i]->value);
    }

    return outFile;
}

// тестирую сжатие
int main (){

     char * s = "toCompress.txt";
    
    FILE* compressed = compress(s); 

    return 0;
}

Источник

Ответы (0 шт):

licensed under cc by-sa 3.0 with attribution.