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

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

Восстановить пароль Регистрация
 
nikola166
 Аватар для nikola166
8 / 8 / 0
Регистрация: 18.03.2010
Сообщений: 142
18.10.2011, 15:05     Псевдоалгоритм Хаффмана #1
есть алгоритм

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 минуты
можно на С++ переписать, но здесь разницы никакой
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.10.2011, 15:05     Псевдоалгоритм Хаффмана
Посмотрите здесь:

кодирование хаффмана C++
Алгоритм Хаффмана C++
C++ Алгоритм Хаффмана
C++ Код Хаффмана
C++ Алгоритм Хаффмана
Сжатие Хаффмана C++
Кодирование Хаффмана C++
C++ Дерево Хаффмана

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
nikola166
 Аватар для nikola166
8 / 8 / 0
Регистрация: 18.03.2010
Сообщений: 142
18.10.2011, 17:11  [ТС]     Псевдоалгоритм Хаффмана #3
спасибо, но коды получаются неправильные, может псевдоалгоритм неправильны
Yandex
Объявления
18.10.2011, 17:11     Псевдоалгоритм Хаффмана
Ответ Создать тему
Опции темы

Текущее время: 08:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru