2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение07.02.2017, 20:19 


02/10/12
172
Я написал программу для вычисления кодов Хаффмана, вроде бы работает. Предназначена для deflate-сжатия. Алгоритм построения дерева Хаффмана и заготовка кода взяты из статьи, скрин в офтопе.

(Оффтоп)


Терминология: я условно листья называю листьями, а узлами называю те узлы, которые не являются листьями.
код: [ скачать ] [ спрятать ]
Используется синтаксис C
//   gcc hfm_tree.c -o hfm_tree.cgi -Wall -Werror -O3
//   ./hfm_tree.cgi



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


// структура для построения дерева Хаффмана
struct s_zipc_hfm{
    int a[288];
    int b[288];
    int pl[288];
    int pr[288];
    int pp[288];
    int p[288];
    int bl_count[288];
};

// структура кодов Хаффмана
struct s_zipc_sym {
    int   freq; // частота символа
    int   hcod; // код Хаффмана
    int   bits; // длина кода Хаффмана
};


//-------------- zipc_haffman_code --------------------
// расчет кодов Хаффмана
int zipc_haffman_code(struct s_zipc_hfm *tree, struct s_zipc_sym *sym,
                      int Max_sym, int Max_bits)
{
    int i, j, k, k1, k2, n, t1, t2, fl, cod, bits, len, aa, ab, bb;
    int *a  = tree->a;  // частоты листьев отсортированы по нарастанию
    int *b  = tree->b;  // частоты узлов
    int *pl = tree->pl; // левый потомок узла
    int *pr = tree->pr; // правый потомок узла
    int *pp = tree->pp; // родительский узел
    int *p  = tree->p;  // номер символа, его значение
    int *bl_count = tree->bl_count; // счетчики числа кодов для разных длин
    int next_code[20];  // счетчики значений кодов для разных длин (из deflate)

    // зарядка исходных массивов
    memset(tree, 0, sizeof(struct s_zipc_hfm));
    for(i = 0, n=0; i < Max_sym; i++){
        if(sym[i].freq > 0){
            a[n] = sym[i].freq;
            p[n] = i;
            n++;
        }
    }
    if(n==0) return(0); // n -число используемых символов алфавита
    if(n > (1 << Max_bits)) return(-1);
    if(n==1){ bl_count[1]++; goto RET;}

    // сортировка по возрастанию частоты символов
    for(i=0; i<n; i++){
        for(j=n-1; j>i; j--){
            if(a[j] < a[j-1]){
                t1     = a[j];      t2     = p[j];
                a[j]   = a[j-1];    p[j]   = p[j-1];
                a[j-1] = t1;        p[j-1] = t2;
            }
        }
    }

    // создание дерева
    // aa, ab, bb -суммы частот двух текущих узлов или листьев
    // k -индекс вновь создаваемого узла
    // i -индекс текущего листа
    // j -индекс текущего узла
    for(k=0, i=0, j=0; k<(n-1); k++){
        if(i<(n-1))    aa = a[i] + a[i+1]; else aa = 1000000;
        if(i<n && j<k) ab = a[i] + b[j];   else ab = 1000000;
        if(j<(k-1))    bb = b[j] + b[j+1]; else bb = 1000000;

        if(aa <= ab && aa <= bb){
            b[k] = aa;
            pl[k] = pr[k] = -1; // оба потомка листья, -1 -признак листа
            i += 2;
        }
        else if(ab <= aa && ab <= bb){
            b[k] = ab;
            pl[k] = j;  // левый потомок
            pr[k] = -1; // правый потомок это лист, -1 -признак листа
            pp[j] = k;  // родительский узел в левом потомке
            i++;
            j++;
        }
        else{
            b[k] = bb;
            pl[k] = j;   // левый потомок
            pr[k] = j+1; // правый потомок
            pp[j] = pp[j+1] = k; // родительский узел в потомках
            j += 2;
        }
    }

    // обход дерева
    for(k--, len=0, fl=0, i=0; i<(2*n); i++){ // k -индекс корневого узла
        if(fl==0){ // вниз по дереву
            len++;
            k1 = pl[k]; k2 = pr[k];
            if(k2<0) bl_count[len]++;
            if(k1<0){ bl_count[len]++; fl=1;} // если слева лист, то вверх
            else k=k1; // в левую ветвь.
        }
        if(fl==1){ // вверх по дереву
            len--;
            if(len<=0) break;
            k = k1 = pp[k];  // k, k1 -индекс родителя
            if(pr[k1] >= 0){ // если правая ветвь не пройдена, то туда
                k = pr[k1];  // k -индекс правой ветви родителя
                pr[k1] = -1; // отмечаем правую ветвь как пройденную
                fl=0;
            }
        }
    }

    // уменьшение длин кодов
    for(i=n-1; i>Max_bits; i--){
        for(; bl_count[i]>0;){
            for(j=i-2; j>0 && bl_count[j]<=0; j--);
            bl_count[i] -= 2;
            bl_count[i-1]++;
            bl_count[j]--;
            bl_count[j+1] += 2;
        }
    }

RET:

    // зарядка выходного массива
    for(cod=0, i=n-1, bits=1; bits <= Max_bits; bits++){
        if(bl_count[bits] > 0){
            for(j=0; j < bl_count[bits]; j++){
                sym[p[i--]].bits = bits;
            }
        }
    }

    for(bits = 1; bits <= Max_bits; bits++){
        cod = (cod + bl_count[bits-1]) << 1;
        next_code[bits] = cod;
    }
    for(i = 0;  i < Max_sym; i++){
        len = sym[i].bits;
        if(len != 0){
            sym[i].hcod = next_code[len];
            next_code[len]++;
        }
    }
    return(n);
}




//============= Тестовая обертка ==================


// Запустить программу. Для выбора одного из тестовых массивов частот, которые
// есть в функции main (по умолчанию - первый массив), ввести:
// --> arr 2  (или другой номер массива от 1 до 6)
// Для изменения частот символов и для введения новых символов ввести:
// --> A 510  (A -это старый или вновь введенный символ, 510 -его частота)
// Для изменения максимальной длины кодов (по умолчанию 15) ввести:
// --> max 4  (4 -максимальная длина кодов)
// Для запуска вычисления кодов ввести пустую строку.
// Настройки arr и max держатся до явной их смены. Введённые символы и частоты
// держатся до смены массива.

//-------------- print_bits ----------------
// Распечатать число в двоичном виде. len -длина(бит).
int print_bits(int val, int len)
{
    int i, maska = 1 << (len - 1);
    if((val >> len) != 0) printf("Error: val=%d; len=%d; ", val, len);
    for(i=0; i<len; i++){
        if((val & maska) != 0) printf("1");
        else printf("0");
        maska = maska >> 1;
    }
    return(0);
}

//---------------- main -----------------------
//printf("\n");
int main()
{

    int x1[]={
        'A', 900,
        'B', 370,
        'C', 350,
        'D', 79,
        'E', 57,
        'F', 54,
        'G', 9,
        'H', 7,
        'I', 1,
    };

    int x2[]={
        'A', 900,
        'B', 370,
        'C', 350,
        'D', 350,
        'E', 350,
        'F', 350,
        'G', 350,
        'H', 350,
        'I', 350,
        'J', 350,
        'K', 350,
        'L', 350,
        'M', 1,
    };

    int x3[]={
        'A', 5200,
        'B', 1100,
        'C', 1000,
        'D', 900,
        'E', 800,
        'F', 700,
        'G', 600,
        'H', 500,
        'I', 400,
        'J', 300,
        'K', 200,
        'L', 100,
        'M', 1,
        'N', 1,
        'O', 1,
        'P', 1,
    };

    int x4[]={
        'A', 5200,
    };

    int x5[]={
        'A',  500,
        'B', 1200,
        'C',   34,
        'D',  800,
        'E',   67,
        'F', 1009,
        'G',  654,
    };

    int x6[]={
        'A',  5,
        'B',  4,
        'C',  3,
        'D',  2,
        'E',  1,
    };

    char *ptr, buf[100];
    unsigned char ch;
    int i, k, fr, len, S, S0, arrnum, Nsym;
    struct s_zipc_hfm tree[1];
    struct s_zipc_sym sym[286];
    int Max_sym = 286;
    int Max_bits = 15;
    int a1[2*286];

    Nsym = (sizeof(sym)/sizeof(struct s_zipc_sym)); // число элементов sym

    memset(sym, 0, sizeof(sym));
    for(k=0; k<(int)(sizeof(x1)/(sizeof(x1[0]))); k=k+2){
        sym[x1[k]].freq = x1[k+1];
    }

START:

    // ввод данных
    printf("-----------------\n");
    while(1){
        printf("--> "); fflush(stdout);
        ptr = fgets(buf, sizeof(buf), stdin);
        if(ptr==NULL) exit(0);
        k = strlen(buf);
        if(k>0 && buf[k-1]=='\n') buf[--k]=0;
        if(k==0) break;
        if(strncmp(buf, "max", 3)==0){
            Max_bits = atoi(buf+3);
            printf("Max_bits=%d\n", Max_bits);
        }
        else if(strncmp(buf, "arr", 3)==0){
            arrnum = atoi(buf+3);
            printf("arrnum=%d\n", arrnum);
            memset(a1, 0, sizeof(a1));
            if(arrnum == 1) memmove(a1, x1, sizeof(x1));
            else if(arrnum == 2) memmove(a1, x2, sizeof(x2));
            else if(arrnum == 3) memmove(a1, x3, sizeof(x3));
            else if(arrnum == 4) memmove(a1, x4, sizeof(x4));
            else if(arrnum == 5) memmove(a1, x5, sizeof(x5));
            else if(arrnum == 6) memmove(a1, x6, sizeof(x6));
            else{ printf("Error\n"); continue;}
            memset(sym, 0, sizeof(sym));
            for(k=0; k<(int)(sizeof(a1)/(sizeof(a1[0]))); k=k+2){
                sym[a1[k]].freq = a1[k+1];
            }
        }
        else{
            k=sscanf(buf, "%c %d", &ch, &fr);
            if(k!=2){ printf("Error\n"); continue;}
            sym[(int)ch].freq = fr;
        }
    }

    for(i=0; i<Nsym; i++){ //обнулить
        sym[i].bits = 0;
        sym[i].hcod = 0;
    }

    k = zipc_haffman_code(tree, sym, Max_sym, Max_bits); // рассчет кодов
    printf("k = zipc_haffman_code()=%d\n", k);

    // распечатка кодов Хаффмана
    S=0; S0=0; len=0;
    for(i=0, k=1; i<Max_sym; i++){
        if(sym[i].freq > 0){
            printf("%2d. %c  len=%2d  freq=%5d  ",
                   k++, i, sym[i].bits, sym[i].freq);
            print_bits(sym[i].hcod, sym[i].bits);
            printf("\n");
            if(len < sym[i].bits) len = sym[i].bits;
            S = S + (sym[i].bits * sym[i].freq);
            S0 = S0 + 8 * sym[i].freq;
        }
    }
    printf("S =%d\n", S);
    printf("S0=%d\n", S0);
    printf("L =%0.3f  bit/symbol; max_len=%d\n", 8.0 * S / S0, len);

    goto START;
}
 

Рассмотрим блок "создание дерева" на конкретном примере (n -число используемых символов алфавита).
код: [ скачать ] [ спрятать ]
Используется синтаксис C
    // int a[] -содержит частоты символов, отсортированные по возрастанию
    // int b[] -сюда заносятся частоты узлов
    // pl[] -левый потомок.
    // pr[] -правый потомок.
    // pp[] -родительский узел.

    // создание дерева
    // aa, ab, bb -суммы частот двух текущих узлов или листьев
    // k -индекс вновь создаваемого узла
    // i -индекс текущего листа
    // j -индекс текущего узла
    for(k=0, i=0, j=0; k<(n-1); k++){
        if(i<(n-1))    aa = a[i] + a[i+1]; else aa = 1000000;
        if(i<n && j<k) ab = a[i] + b[j];   else ab = 1000000;
        if(j<(k-1))    bb = b[j] + b[j+1]; else bb = 1000000;

        if(aa <= ab && aa <= bb){
            b[k] = aa;
            pl[k] = pr[k] = -1; // оба потомка листья, -1 -признак листа
            i += 2;
        }
        else if(ab <= aa && ab <= bb){
            b[k] = ab;
            pl[k] = j;  // левый потомок
            pr[k] = -1; // правый потомок это лист, -1 -признак листа
            pp[j] = k;  // родительский узел в левом потомке
            i++;
            j++;
        }
        else{
            b[k] = bb;
            pl[k] = j;   // левый потомок
            pr[k] = j+1; // правый потомок
            pp[j] = pp[j+1] = k; // родительский узел в потомках
            j += 2;
        }
    }

 

Пусть используются пять символов с частотами 1, 2, 3, 4, 5. В массиве a эти частоты отсортированы по возрастанию, на рисунке этот массив синий. В массив b заносятся частоты узлов, на рисунке он оранжевый.
Изображение
В блоке "создание дерева" есть три больших if-а, можно заметить, что возможны следующие комбинации узлов и листьев (узлы оранжевые, листья синие):
Изображение
Листья не имеют индексов: где потомок узла это лист, там индекс потомка отмечен как минус единица. Получившееся дерево есть ниже на рисунке.

Рассмотрим блок "обход дерева". Задача этого блока - заполнить массив bl_count[len], в нем каждый элемент должен содержать число кодов длины len.
код: [ скачать ] [ спрятать ]
Используется синтаксис C
    // обход дерева
    for(k--, len=0, fl=0, i=0; i<(2*n); i++){ // k -индекс корневого узла
        if(fl==0){ // вниз по дереву
            len++;
            k1 = pl[k]; k2 = pr[k];
            if(k2<0) bl_count[len]++;
            if(k1<0){ bl_count[len]++; fl=1;} // если слева лист, то вверх
            else k=k1; // в левую ветвь.
        }
        if(fl==1){ // вверх по дереву
            len--;
            if(len<=0) break;
            k = k1 = pp[k];  // k, k1 -индекс родителя
            if(pr[k1] >= 0){ // если правая ветвь не пройдена, то туда
                k = pr[k1];  // k -индекс правой ветви родителя
                pr[k1] = -1; // отмечаем правую ветвь как пройденную
                fl=0;
            }
        }
    }

k -индекс текущего узла.
len -текущая длина кодов.
pl[k] -левый потомок.
pr[k] -правый потомок.
pp[k] -родительский узел.
Рассмотрим на конкретном дереве из примера выше. В узлах дерева на рисунке указаны индексы этих узлов в массиве b и в сопряженных массивах pl, pr, pp. Если на текущем шаге лист посчитан счетчиком bl_count[len], то на рисунке цвет его меняется с синего на голубой. Красные стрелки показывают пройденный путь от узла к узлу. Красными кружками отмечены if-ы, выполняющиеся на текущем шаге.
Изображение
Можно сказать, что блок (fl==0) всегда идет вниз по дереву нехожеными тропами, попутно считая встретившиеся листья. Блок (fl==1) наоборот, идет хожеными тропами, за исключением случая перехода на соседнего потомка (как на шаге-5).

Рассмотрим блок "уменьшение длин кодов". На рисунке показан один шаг модификации дерева, листья, подлежащие переносу, выделены яркими цветами
Изображение
Используется синтаксис C
    // уменьшение длин кодов
    for(i=n-1; i>Max_bits; i--){
        for(; bl_count[i]>0;){
            for(j=i-2; j>0 && bl_count[j]<=0; j--);
            bl_count[i] -= 2;
            bl_count[i-1]++;
            bl_count[j]--;
            bl_count[j+1] += 2;
        }
    }

Внешний цикл выискивает коды, вылезшие за максимально-допустимую длину. Вернее, не сами коды, а счетчики числа кодов больших длин. Вложенный цикл крутится до обнуления счетчика этой большой длины. Самый глубоко вложенный маленький цикл выискивает, куда бы приткнуть лишние листья. bl_count[i] это счетчики, но за ними всегда подразумеваются листья.

До метки RET: счетчики отвязаны от символов алфавита и кодов. Обратная привязка ниже метки RET:, там в первом цикле длины привязываются к символам в порядке частот этих символов, а два нижних цикла окончательно присваивают символам их коды Хаффмана по правилу, прямо записанному в протоколе deflate.

 Профиль  
                  
 
 Re: СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение07.02.2017, 21:32 
Заслуженный участник


08/04/08
8332

(Оффтоп)

О! Я когда-то тоже так писал: и -1 и 1000000 и никаких сишных извращений. Приятно вспомнить :-) Хотя тут извращения имеются.

А в чем вопрос-то?

 Профиль  
                  
 
 Re: СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение07.02.2017, 21:36 


04/02/17

47
Sonic86 в сообщении #1190584 писал(а):

(Оффтоп)

О! Я когда-то тоже так писал: и -1 и 1000000 и никаких сишных извращений. Приятно вспомнить :-) Хотя тут извращения имеются.

А в чем вопрос-то?


Проблема в создании программы.

 Профиль  
                  
 
 Re: СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение07.02.2017, 22:54 


02/10/12
172
Sonic86 в сообщении #1190584 писал(а):
А в чем вопрос-то?

Первый вопрос, можно ли это сделать проще? Декодировать коды Хаффмана намного проще. В статье приведен код, и сразу получается число бит для кодирования всего сообщения. Можно ли вычислить сразу коды или их длины без обхода дерева? В статье об этом не написано. Обход я сам придумал.
Второй вопрос. Если проще нельзя, если обход дерева неизбежен, то вопрос. Цикл обхода выглядит непривычно, в нем в явном виде нет ни проверки на выход за края массива, ни устойчивости на зацикливание. Счетчик я на всякий случай поставил, но по замыслу его там не должно быть. Работа этого цикла без сбоев по замыслу должна быть за счет правильного дерева, и чтоб написано без ошибок. В общем, я боюсь этого цикла, непривычно. Поэтому по шагам расписал, а страх-то остался. Я написал большую программу сжатия (32 кб СИ-кода), аналог gzip, там применил эту функцию вычисления кодов, протестил на трёх файлах - видео, bmp-рисунок и текстовой файл. Работает. Короче, и уверенности нет, и не удалось получить сбой. Сбой это падение, порча памяти, как-нибудь проявившаяся, или зацикливание.
Если укажете имеющиеся извращения, тоже бы хорошо. Может не сразу, но всё равно на пользу пойдёт.

 Профиль  
                  
 
 Re: СИ. Коды Хаффмана. Дерево Хаффмана.
Сообщение12.02.2017, 07:46 


02/10/12
172
Сразу не догадался. Можно и по-другому сделать обход дерева - от каждого листа к корню с подсчётом длины кода этого листа. Блок "обход дерева" получается компактней и понятней. Ниже функция, введен дополнительный массив pa -родители листьев. А массивы потомков pl, pr не нужны, т. к. обход только вверх, от листа к корню.
код: [ скачать ] [ спрятать ]
Используется синтаксис C
// структура для построения дерева Хаффмана
struct s_zipc_hfm{
    int a[288];
    int b[288];
    int pa[288];
    int pp[288];
    int p[288];
    int bl_count[288];
};

// структура кодов Хаффмана
struct s_zipc_sym {
    int   freq; // частота символа
    int   hcod; // код Хаффмана
    int   bits; // длина кода Хаффмана
};


//-------------- zipc_haffman_code --------------------
// рассчет кодов Хаффмана
int zipc_haffman_code(struct s_zipc_hfm *tree, struct s_zipc_sym *sym,
                      int Max_sym, int Max_bits)
{
    int i, j, k, n, t1, t2, cod, bits, len, aa, ab, bb;
    int *a  = tree->a;  // частоты листьев отсортированы по нарастанию
    int *b  = tree->b;  // частоты узлов
    int *pa = tree->pa; // родительский узел листа
    int *pp = tree->pp; // родительский узел узла
    int *p  = tree->p;  // номер символа, его значение
    int *bl_count = tree->bl_count; // счетчики числа кодов для разных длин
    int next_code[20];  // счетчики значений кодов для разных длин (из deflate)

    // зарядка исходных массивов
    memset(tree, 0, sizeof(struct s_zipc_hfm));
    for(i = 0, n=0; i < Max_sym; i++){
        if(sym[i].freq > 0){
            a[n] = sym[i].freq;
            p[n] = i;
            n++;
        }
    }
    if(n==0) return(0); // n -число используемых символов алфавита
    if(n > (1 << Max_bits)) return(-1);
    if(n==1){ bl_count[1]++; goto RET;}

    // сортировка по возрастанию частоты символов
    for(i=0; i<n; i++){
        for(j=n-1; j>i; j--){
            if(a[j] < a[j-1]){
                t1     = a[j];      t2     = p[j];
                a[j]   = a[j-1];    p[j]   = p[j-1];
                a[j-1] = t1;        p[j-1] = t2;
            }
        }
    }

    // создание дерева
    // aa, ab, bb -суммы частот двух текущих узлов или листьев
    // k -индекс вновь создаваемого узла
    // i -индекс текущего листа
    // j -индекс текущего узла
    for(k=0, i=0, j=0; k<(n-1); k++){
        if(i<(n-1))    aa = a[i] + a[i+1]; else aa = 1000000;
        if(i<n && j<k) ab = a[i] + b[j];   else ab = 1000000;
        if(j<(k-1))    bb = b[j] + b[j+1]; else bb = 1000000;

        if(aa <= ab && aa <= bb){
            b[k] = aa;
            pa[i] = pa[i+1] = k; // родительский узел
            i += 2;
        }
        else if(ab <= aa && ab <= bb){
            b[k] = ab;
            pa[i] = pp[j] = k; // родительский узел
            i++;
            j++;
        }
        else{
            b[k] = bb;
            pp[j] = pp[j+1] = k; // родительский узел
            j += 2;
        }
    }

    // обход дерева
    for(--k, i=0; i<n; i++){ // k -индекс корневого узла
        for(len=1, j=pa[i]; j<k; j=pp[j], len++);
        bl_count[len]++;
    }

    // уменьшение длин кодов
    for(i=n-1; i>Max_bits; i--){
        for(; bl_count[i]>0;){
            for(j=i-2; j>0 && bl_count[j]<=0; j--);
            bl_count[i] -= 2;
            bl_count[i-1]++;
            bl_count[j]--;
            bl_count[j+1] += 2;
        }
    }

RET:

    // зарядка выходного массива
    for(cod=0, i=n-1, bits=1; bits<(Max_bits+1); bits++){
        for(j=0; j < bl_count[bits]; j++){
            sym[p[i--]].bits = bits;
        }
    }

    for(bits = 1; bits <= Max_bits; bits++){
        cod = (cod + bl_count[bits-1]) << 1;
        next_code[bits] = cod;
    }
    for(i = 0;  i < Max_sym; i++){
        len = sym[i].bits;
        if(len != 0){
            sym[i].hcod = next_code[len]++;
        }
    }
    return(n);
}
 

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: maxal, Karan, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group