Где ошибка в моей реализации LZW алгоритма?

Question

Есть Такой код, в котором пытаюсь реализовать сжатие, но словарь у меня формируется некорректно. Помогите разобраться в чем дело.

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

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

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

    // Проверяем словарь

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

             // Теперь текущим словом должен стать суффикс расширенного слова

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

             free (sufix.value);
             // Далее я вывожу на консоль значения всех новых слов
             printf("%d word in dictionary = %s\t wordsize = %d \n", freeCode, dictionary[freeCode]->value, sizeof(dictionary[freeCode]->value));
             // и увеличиваю код свободного слова
             freeCode++;
        // цикл while идет дальше
        }

        fclose (inFile);
    fclose (outFile);

    return outFile;
}

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

     char * s = "toCompress.txt";

    FILE* compressed = compress(s); 

    return 0;
}

В качестве теста во входной поток я занес строку "abacabadabacabae" из примера на хабре Вот какие "новые слова" сформировала мне функция

А вот что в выходном файле

то есть сжатия не происходит, комбинации из двух букв попадают в словарь несколько раз, а в выходном файле содержится несжатая строка. Почему так происходит? Я не могу найти ошибку. И еще : почему это у С-строки из символов "ab\0" и подобных размер 4 байта, а не 3?

БЛОГ НА HUSL

Где ошибка в моей реализации LZW алгоритма?

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