LZW кодирование для большого файла

Question

Я строй алгоритма кодирования LZW, который использует словаря и хэширования так что он может достичь достаточно быстро для рабочих слов уже хранящихся в словаре.

Алгоритм дает правильные результаты при работе с меньшими файлами (всего несколько сотен символов), но в больших файлах (и особенно в тех файлах, которые содержат менее разные символы), например, он дает наихудшую производительность при запуске в файле, который состоит только из 1 символа, 'y', допустим). Худшая производительность, с точки зрения того, что он просто падает, когда словарь даже не близок к полному. Однако, когда большой входной файл состоит из более чем одного символа, словарь приближается к полному, примерно 90%, но опять же он падает.

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

хэш-функция Я использую можно найти здесь, и от того, что я испытал, он дает хорошие результаты: алгоритм кодирования oat_hash

LZW основан на этой ссылке, с небольшим изменением, что это работает до тех пор, словарь не является полным: LZW encoder

Давай залезать в код:

Примечания: oat_hash изменяется таким образом, он возвращается в LUE% емкости, так что каждый индекс от СЛОВАРЬ

// Globals 
#define CAPACITY 100000 
char *DICTIONARY[CAPACITY]; 
unsigned short CODES[CAPACITY]; // CODES and DICTIONARY are linked via index: word from dictionary on index i, has its code in CODES on index i 
int position = 0; 
int code_counter = 0; 

void encode(FILE *input, FILE *output){ 

int succ1 = fseek(input, 0, SEEK_SET); 
if(succ1 != 0) printf("Error: file not open!"); 

int succ2 = fseek(output, 0, SEEK_SET); 
if(succ2 != 0) printf("Error: file not open!"); 

//1. Working word = next symbol from the input 
char *working_word = malloc(2048*sizeof(char)); 
char new_symbol = getc(input); 
working_word[0] = new_symbol; 
working_word[1] = '\0'; 



//2. WHILE(there are more symbols on the input) DO 
//3. NewSymbol = next symbol from the input 
while((new_symbol = getc(input)) != EOF){ 

    char *workingWord_and_newSymbol= NULL; 
    char newSymbol[2]; 
    newSymbol[0] = new_symbol; 
    newSymbol[1] = '\0'; 

    workingWord_and_newSymbol = working_word_and_new_symbol(working_word, newSymbol); 

    int index = oat_hash(workingWord_and_newSymbol, strlen(workingWord_and_newSymbol)); 

    //4. IF(WorkingWord + NewSymbol) is already in the dictionary THEN 
    if(DICTIONARY[index] != NULL){ 
     // 5. WorkingWord += NewSymbol 
     working_word = working_word_and_new_symbol(working_word, newSymbol); 

    } 
    //6. ELSE 
    else{ 
     //7. OUTPUT: code for WorkingWord 
     int idx = oat_hash(working_word, strlen(working_word)); 

     fprintf(output, "%u", CODES[idx]); 

     //8. Add (WorkingWord + NewSymbol) into a dictionary and assign it a new code 
     if(!dictionary_full()){ 
      DICTIONARY[index] = workingWord_and_newSymbol; 
      CODES[index] = code_counter + 1; 
      code_counter += 1; 
      working_word = strdup(newSymbol); 
     }else break; 

    } 
    //10. END IF 
} 
//11. END WHILE 

//12. OUTPUT: code for WorkingWord 
int index = oat_hash(working_word, strlen(working_word)); 
fprintf(output, "%u", CODES[index]); 

free(working_word); 

}

Answer 1

сжатия LZW, безусловно, используется для построения бинарных файлов и обычно способен считывать двоичные файлы.

Следующий код является проблематичным, поскольку он полагается на new_symbol, никогда не являющийся \0.

newSymbol[0] = new_symbol; newSymbol[1] = '\0'; 
strlen(workingWord_and_newSymbol) 
strdup(newSymbol) 

Нуждается в повторной записи для работы с массивами байтов, а не строк.

---

fopen() не был показан. Убедитесь, что один открывается в двоичном формате. input = fopen(..., "rb");

@Wumpus Q. Wumbley является правильным, используйте int newSymbol.

---

Minor:

new_symbol и newSymbol запутаны.

Рассмотрим:

// char *working_word = malloc(2048*sizeof(char)); 
#define WORKING_WORD_N (2048) 
char *working_word = malloc(WORKING_WORD_N*sizeof(*working_word)); 
// or 
char *working_word = malloc(WORKING_WORD_N); 

Answer 2

int index = oat_hash(workingWord_and_newSymbol, strlen(workingWord_and_newSymbol)); 

И позже

int idx = oat_hash(working_word, strlen(working_word)); 

    fprintf(output, "%u", CODES[idx]); 

    //8. Add (WorkingWord + NewSymbol) into a dictionary and assign it a new code 
    if(!dictionary_full()){ 
     DICTIONARY[index] = workingWord_and_newSymbol; 
     CODES[index] = code_counter + 1; 
     code_counter += 1; 
     working_word = strdup(newSymbol); 
    }else break; 

IDX и индекс неограниченны и использовать их, чтобы получить доступ к ограниченному массиву. Вы получаете доступ к памяти за пределами допустимого диапазона. Вот предложение, но оно может исказить распределение. Если ваш диапазон хэшей намного больше, чем CAPACITY, это не должно быть проблемой. Но у вас также есть другая проблема, о которой упоминалось, коллизии, вам нужно справиться с ними. Но это другая проблема.

int index = oat_hash(workingWord_and_newSymbol, strlen(workingWord_and_newSymbol)) % CAPACITY; 
// and 
int idx = oat_hash(working_word, strlen(working_word)) % CAPACITY;