Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
nikola166
8 / 8 / 0
Регистрация: 18.03.2010
Сообщений: 142
#1

Псевдоалгоритм Хаффмана - C++

18.10.2011, 15:05. Просмотров 967. Ответов 2
Метки нет (Все метки)

есть алгоритм

n – количество символов исходного алфавита
P – массив вероятностей, упорядоченных по убыванию
C – матрица элементарных кодов
L – массив длин кодовых слов
Huffman (n,P)
IF (n=2) C [1,1]:= 0, L [1]:= 1
C [2,1]:=1, L [2]:=1
ELSE q:= P [n-1]+P [n]
j:= Up (n,q) (поиск и вставка суммы)
Huffman (n-1,P)
Down (n,j) (достраивание кодов)
FI

Функция Up (n,q) находит в массиве P место, куда вставить число q, и вставляет его, сдвигая вниз остальные элементы.

DO (i=n-1, n-2,…,2)
IF (P [i-1]≤q) P [i]:=P [i-1]
ELSE j:=i
OD
FI
OD
P [j]:= q

Процедура Down (n,j) формирует кодовые слова.

S:= C [j,*] (запоминание j-той строки матрицы элем. кодов в массив S)
L:= L[j]
DO (i=j,…,n-2)
C [i,*]:= C[i+1,*] (сдвиг вверх строк матрицы С)
L [i]:=L [i+1]
OD
C [n-1,*]:= S, C [n,*]:= S (восстановление префикса кодовых слов из м-ва S)
C [n-1,L+1]:=0
C [n,L+1]:=1
L [n-1]:=L+1
L [n]:=L+1
Здесь я понимаю все кроме процедуры Down(n,j)
т.е конкретно
C [n-1,L+1]:=0
C [n,L+1]:=1
как такое можно написать если L- массив

Добавлено через 1 час 16 минут
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
class A
{
 
 
 
 
 
    double[] P1 = { 0.062, 0.014, 0.038, 0.013, 0.025, 0.072, 0.072, 0.007, 0.016, 0.062, 0.010, 0.028, 0.035, 0.026, 0.053, 0.090, 0.023, 0.040, 0.045, 0.053, 0.021, 0.002, 0.009, 0.004, 0.012, 0.006, 0.003, 0.014, 0.003, 0.014, 0.003, 0.006, 0.018 };
    char[] Alpha = { 'А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ё', 'Ж', 'З', 'И', 'Й', 'К', 'Л', 'М', 'Н', 'О', 'П', 'Р', 'С', 'Т', 'У', 'Ф', 'Х', 'Ц', 'Ч', 'Ш', 'Щ', 'Ъ', 'Ы', 'Ь', 'Э', 'Ю', 'Я' };
 
    string[] Res = new string[33];
   
 
 
    public void Sort()
    {
        for (int i = 0; i < P1.Length; i++)
        {
            for (int j = 0; j < P1.Length - i - 1; j++)
            {
                if (P1[j] < P1[j + 1])
                {
                    char temp2;
                    double temp1 = 0;
 
                    temp1 = P1[j];
                    temp2 = Alpha[j];
                    P1[j] = P1[j + 1];
                    Alpha[j] = Alpha[j + 1];
                    P1[j + 1] = temp1;
                    Alpha[j + 1] = temp2;
 
                }
            }
        }
    }
 
    public void Down(int n, int j)
    {
        string S;
        //S:= C [j,*]  //запоминание j-той строки матрицы элем. кодов в массив S) 
        S = Res[j];
        for (int i = j; i <= n - 2; i++)
        {
           
            Res[i] = Res[i + 1]; //(сдвиг вверх строк матрицы С)
 
        }
      
        Res[n - 1] = S;
      
        Res[n] = S;
        Res[n - 1] += Convert.ToString(0);
        Res[n] += Convert.ToString(1);
        
 
    }
   
    public int Up(int n, double q)
    {
       
        int j = 0;
 
        for (int i = n - 1; i >= 2; i--)
        {
            if (P1[i - 1] <= q)
                P1[i] = P1[i - 1];
            else
                j = i;
        }
        P1[j] = q;
        return j;
 
    }
    public void Haff(int n, double[] P)
    {
      
        double q;
        if (n == 2)
        {
            Res[1] += Convert.ToString(0);
            Res[2] += Convert.ToString(1);
 
        }
        else
        {
            q = Convert.ToDouble(P[n - 1]) + Convert.ToDouble(P[n]);
           int j= Up(n, q);
            Haff(n - 1,P);
            Down(n,j);
 
        }
    }
    public static void Main()
    {
 
        A ob = new A();
        ob.Sort();
         ob.Haff(32,ob.P1);
        
        for (int i = 0; i < 33; i++)
        {
 
          Console.WriteLine(ob.Alpha[i] + " " + ob.Res[i]);
            
         
 
 
        }
 
    }
}
в чем тут ошибка, вроде все по алгоритму а строит не то что надо, а надо чтобы построил коды для алфавита

Добавлено через 2 минуты
можно на С++ переписать, но здесь разницы никакой
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.10.2011, 15:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Псевдоалгоритм Хаффмана (C++):

кодирование хаффмана - C++
здравствуйте! я пишу программу сжатия jpeg. написала код для кодирования хаффмана по дереву. и столкнулась с такой проблемой записываю в...

Алгоритм Хаффмана - C++
Ребят, подскажите как реализовать кодирование по алгоритму Хаффмана.. Может есть какие то идеи или исходники (желательно с пояснением)? ...

Архиватор Хаффмана c++ - C++
Пишу архиватор на c++ методом Хаффмана. Не могу найти как считывать байты из файла в c++.

Дерево Хаффмана - C++
Здравствуйте. Хотел узнать как работает дерево Хаффмана и 4 дня изучал материалы в интернете (статьи, видеоуроки) и т.д.), написал...

Сжатие Хаффмана - C++
Как изменить данный алгоритм, чтобы ограничить длину кода символа заданным числом Nmax? Спасибо! #include &quot;stdafx.h&quot; #include...

Алгоритм Хаффмана - C++
Возможно и наболевшая тема на форуме, но всё же есть реализация алгоритма Хаффмана. Допустим, у меня в файле есть следующая строка: ...

2
Wanderer1
23 / 23 / 4
Регистрация: 26.03.2011
Сообщений: 54
18.10.2011, 17:01 #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace AlgoritmHuffmana1
{
    class Program
    {
        static void Main(string[] args)
        {            
            Program ob = new Program();
            ob.Sort();
            ob.Haff(32, ob.P1);
            ob.SortAlpha();
            for (int i = 0; i < 33; i++)
            {
                Console.WriteLine(ob.Alpha[i] + "\t" + ob.Res[i] + "\t" + ob.P1[i] + "\t" + ob.P2[i]);
            }
            Console.Read();
        }
 
        double[] P1 = { 0.062, 0.014, 0.038, 0.013, 0.025, 0.072, 0.072, 0.007, 0.016, 0.062, 0.010, 0.028, 0.035, 0.026, 0.053, 0.090, 0.023, 0.040, 0.045, 0.053, 0.021, 0.002, 0.009, 0.004, 0.012, 0.006, 0.003, 0.014, 0.003, 0.014, 0.003, 0.006, 0.018 };
        char[] Alpha = { 'А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ё', 'Ж', 'З', 'И', 'Й', 'К', 'Л', 'М', 'Н', 'О', 'П', 'Р', 'С', 'Т', 'У', 'Ф', 'Х', 'Ц', 'Ч', 'Ш', 'Щ', 'Ъ', 'Ы', 'Ь', 'Э', 'Ю', 'Я' };
        int[] P2 = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33 };
        string[] Res = new string[33];
 
 
        public void SortAlpha()
        {
            int i=1;
            while (i != 0)
            {
                i = 0;
                for (int j = 0; j < P2.Length - 1; j++)
                {
                    if (P2[j] > P2[j + 1])
                    {
                        int temp3;
                        char temp2;
                        double temp1 = 0;
 
                        temp1 = P1[j];
                        temp2 = Alpha[j];
                        temp3 = P2[j];
                        P1[j] = P1[j + 1];
                        Alpha[j] = Alpha[j + 1];
                        P2[j] = P2[j + 1];
                        P1[j + 1] = temp1;
                        Alpha[j + 1] = temp2;
                        P2[j + 1] = temp3;
                        i++;
                    }
                }
            }
        }
        public void Sort()
        {
            for (int i = 0; i < P1.Length; i++)
            {
                for (int j = 0; j < P1.Length - i - 1; j++)
                {
                    if (P1[j] < P1[j + 1])
                    {
                        char temp2;
                        double temp1 = 0;
 
                        int temp3;
                        temp3 = P2[j];
                        P2[j] = P2[j + 1];
                        P2[j + 1] = temp3;
 
                        temp1 = P1[j];
                        temp2 = Alpha[j];
                        P1[j] = P1[j + 1];
                        Alpha[j] = Alpha[j + 1];
                        P1[j + 1] = temp1;
                        Alpha[j + 1] = temp2;
 
                    }
                }
            }            
        }
 
        public void Down(int n, int j)
        {
            string S;
            //S:= C [j,*]  //запоминание j-той строки матрицы элем. кодов в массив S) 
            S = Res[j];
            for (int i = j; i <= n - 2; i++)
            {
 
                Res[i] = Res[i + 1]; //(сдвиг вверх строк матрицы С)
 
            }
 
            Res[n - 1] = S;
 
            Res[n] = S;
            Res[n - 1] += Convert.ToString(0);
            Res[n] += Convert.ToString(1);
 
 
        }
 
        public int Up(int n, double q)
        {
 
            int j = 0;
 
            for (int i = n - 1; i >= 2; i--)
            {
                if (P1[i - 1] <= q)
                    P1[i] = P1[i - 1];
                else
                    j = i;
            }
            P1[j] = q;
            return j;
 
        }
        public void Haff(int n, double[] P)
        {
 
            double q;
            if (n == 2)
            {
                Res[1] += Convert.ToString(0);
                Res[2] += Convert.ToString(1);
 
            }
            else
            {
                q = Convert.ToDouble(P[n - 1]) + Convert.ToDouble(P[n]);
                int j = Up(n, q);
                Haff(n - 1, P);
                Down(n, j);
 
            }
        }
    }
}
L - строка матрицы
С - матрица
C [n-1,L+1]:=0 вроде как добавляет символ в конец строки и обнуляет
C [n,L+1]:=1
0
nikola166
8 / 8 / 0
Регистрация: 18.03.2010
Сообщений: 142
18.10.2011, 17:11  [ТС] #3
спасибо, но коды получаются неправильные, может псевдоалгоритм неправильны
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.10.2011, 17:11
Привет! Вот еще темы с ответами:

Код Хаффмана - C++
Всем доброго дня! имеется код хафманна, работает, но считает неправильно! кто может объяснить в чем дело? #include &lt;iostream&gt; ...

Кодирование Хаффмана - C++
Есть дерево Хаффана, с помощью функции, приведенной ниже прохожусь по дереву и &quot;выписываю&quot; 0 и 1, получившиеся коды символов записываю в...

Кодирование Хаффмана - C++
Добрый вечер. Я за эту неделю малость зафлудил форум наверно. Прошу прощения за это. Просто уже не знаю, куда ещё обратиться со всем...

Сжатие Хаффмана - C++
Есть прога, реализующая сжатие Хаффмана: #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;map&gt; #include...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru