Хаффман на Си

[FRikaZOid]

Я реализую алгоритм Хаффмана в Си, т.е. каждый символ (8 бит) заменяю на более короткие коды и записываю в файл. Допустим, я вычислил какой символ на какой код буду заменять, у меня вышло:

H - 0

E - 111

F - 11000

B - 11001

и т.д.

Эта таблица хранится в структуре, где есть сам символ, его заменяющий код и длина этого кода.

Теперь, если закодировать строку HEFB, то как можно соответствующий код записать в новый файл, учитывая то, что 1 символ - 8 бит, а у меня, к примеру, H - всего 1 бит.

Comments

[O]

Вроде работающий способ: (прогоняя с этими данными, всё работает)

char *str="HEFB";



#define CODETYPE char

struct hash{

  char symb;

  CODETYPE code; // Код. Пусть будет char - общности не нарушит.

  char codelen;  // Длина в битах

};



#define TABLEN 4

struct hash table[]={

  {'H',0x00,1}, // 0

  {'E',0x07,3}, // 111

  {'F',0x18,5}, // 11000

  {'B',0x19,5}};// 11001

// итого, от строки HEBF должно получиться:

//Первый байт '1000][111][0]' Второй байт: '00[11001][1'.



#define BUFLEN 255

char buf[BUFLEN];     // буфер, накапливает коды



unsigned int i,j,k=0; // i - индекс символа в строке str

                      // j - индекс элемента массива table

                      // k - индекс текущего байта в буфере buf

char cb1,cb2, cbc=0;  // cb2 и cb1 - буферные байты

                      // cbc - число зполненных бит в cb2

                      // cb2 - скидывается в buf по заполнению всех 8 битов

CODETYPE cod;         // буфер для кода

char len;             // кода в буфере cod



int main(){

for (i=0;i<strlen(str);i++){                          //проходим строку посимвольно

  for (j=0; (j<TABLEN)&&(table[j].symb!=str[i]); j++); //определяем элемент table, соответствующей текущему символу

  len=table[j].codelen;   // сохраняем длину кода

  cod=table[j].code;      // и сам код в буферах

  do{ 

    if (cbc+len>8){           // Если у нас остатки кода не влезают cb2

      cb1=(char)cod<<cbc;     // Производим  

      cod>>=cbc;              // слабообъяснимые

      len-=8-cbc;             // манипуляции

      cbc=8;                  // Которые заполняют буфер cb2 до конца

    }

    else{                     // Если код вмещается в буфер целиком

      cb1=(char)cod<<cbc;     // Сдвигаем его на число заполенных бит

      cbc+=len;               // Засчитываем увеличение числа запоненных бит в cb2

      len=0;                  // А буфер кода - пуст.

    }

    cb2|=cb1;                 // Заполняем пустые биты куском кода

    if (cbc==8){              // Если буфер cb2 полностью заполнен

      buf[k]=cb2;             // Скидываем его в buf

      cb2=0;                  // обнуляем

      k++;                    // Переходим к следующему байту в buf

      cbc=0;                  // Отмечаем обнуление cb2

      if (k==BUFLEN){         // Если buf заполнен

        k=0;                  // J,yekztv cx`nxbr

        //скидываем буфер buf в файл

        strnset(buf,0,BUFLEN); // очищаем buf

      }

    }

  }while(len!=0);

}

buf[k]=cb2;                   // заключительный аккорд

//скидываем буфер buf в файл

}

Если что не понятно, спрашивайте.

Да! Это далеко не самый оптимальный вариант.

Да! И ещё! Си я не знаю.

[FRikaZOid]

O Нравится мне последняя фраза Да! И ещё! Си я не знаю.))



Спасибо и за такой вариант.



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

[Vj_o-oy]

FRikaZOid а что мешает догнать все символы до 8 бит ведущими нулями? Или в таблице 01xy и 001xy будут одинаково восприниматься?

E - 00000111

H - 00000000

и т.д.

[alexp]

FRikaZOid

С битами работай: пичкай результирующие коды шифтом.

Приведенный выше код, как раз это и делает, но как хорошо он это делает судить не берусь (Си я знаю, но мне невообразимо влом читать на нем во время отпуска)



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

Да, нельзя. Подумай, к примеру, почему нельзя сжать уже сжатый файл?



Vj_o-oy

Ничто не мешает, но цель алгоритма – сжать информацию. Теперь делай вывод – стоит ли «догонять нулями» уже сжатое до прежних размеров?...

[FRikaZOid]

Ок, всем спасибо, больше вопросов пока не возникает. Если что, буду еще спрашивать..

[O]

Что-то подумалось, безотносительно алгоритма Хаффмана (я его попросту не помню, или даже не знаю), а если наиболее редко встречающимся символам назначать код длиннее (пусть, 9 бит), а наиболее часто встречающимся - код меньше (скажем, 7 бит)?

[FRikaZOid]

O При построении дерева у меня так и получается, но толку от этого мало, теоретически, размер то такой же будет..

[FRikaZOid]

Вопрос: какие типы переменных вообще нужно использовать? Для чтения файла использую c=getc(file), где c - просто int, которая после чтения присваивается переменной unsigned char, с которой и работает дальше программа. Запись проходит аналогично. Правильно ли это? Моя программа текст сжимает\разжимает нормально, а вот с двоичными файлами не работает никак..

[SilentDeath]

class BitStream

{

private:

char *mStream;

uint cBitPos;



public:

BitStream(void *Stream)

{

mStream=(char*)Stream;

cBitPos=0;

};



inline uint GetPos(){ return cBitPos%8?cBitPos/8+1:cBitPos/8; };

inline void SetVal(uint Val, uint n)

{

uint cBit=cBitPos%8;

uint *cSeg=(uint*)&mStream[cBitPos/8];

*cSeg|=Val<<cBit;

cBitPos+=n;

};

inline void GetVal(uint &Val, uint n)

{

uint cBit=cBitPos%8;

uint *cSeg=(uint*)&mStream[cBitPos/8];

Val=((*cSeg)>>cBit)&((1<<n)-1);

cBitPos+=n;

};

};



// C++, но на C переделать недолго

// Val - значние

// n - кол-во бит в значении, максимум 16

// перед записью mStream иницеализировать нулями

// потом функцией fwrite сбрасываем весь поток



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

// по битику через GetVal дастаём значение