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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.81
Apoka5555
2 / 2 / 1
Регистрация: 18.04.2013
Сообщений: 126
#1

Арифметическое кодирование на С++ - C++

18.04.2013, 17:18. Просмотров 3492. Ответов 9
Метки нет (Все метки)

Здравствуйте. Такая проблема: нужно реализовать алгоритм арифметического кодирования и декодирования. Кодирование у меня получилось. Но никак не могу сделать декодирование. Помогите пожалуйста. Вот мой код:
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
#include "stdafx.h"
#include <iostream>
using namespace std;
 
/*
Алфавит {'a','e','i','o','u','!'}
Символ   Вероятность   Интервал
a           .2         [0.0; 0.2)
e           .3         [0.2; 0.5)
i           .1         [0.5; 0.6)
o           .2         [0.6; 0.8)
u           .1         [0.8; 0.9)
!           .1         [0.9; 1.0)
*/
char Alph[] = {'a','e','i','o','u','!'};
double cum_freq[] = {0.2, 0.5, 0.6, 0.8, 0.9, 1.0};
 
double low = 0.0;
double high = 1.0;
 
void encode_symbol(int symbol)
{
    double range = high - low;
    high = low + range * cum_freq[symbol];
    low = low + range * cum_freq[symbol - 1];
    cout << low <<" - "<< high << endl;
}
 
void decode_symbol()
{
    
}
 
void main()
{
    cout << low << " - "<< high << endl;
    string s = "eaii!";
    for (int i = 0; i < s.length(); i++)
    {
        for (int j = 0; j < 6; j++)
        if (s[i] == Alph[j])
        {
            cout << s[i] <<" - ";
            encode_symbol(j);
        }
    }
    
 
    system("pause");
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.04.2013, 17:18     Арифметическое кодирование на С++
Посмотрите здесь:

Арифметическое кодирование - C++
Мне задали задание по арифм. кодировании. Я что-то не очень знаю что это такое и зчем его едят.... Прошу вас о помощи... Конкретнее было...

Арифметическое кодирование - C++
Добрый день. задали мне лабу: реализовать арифметическое кодирование. но мне не всё понятно в реализации... Надо ли разбивать на блоки...

Кодирование, C++ - C++
Закодировать каждую букву произвольного символьного массива равномерным кодом.

Кодирование - C++
В какой тип данных можно записывать по одному биту 0 или 1, чтобы потом можно было считать целиком последовательность. Например, 010 или 1.

кодирование текста - C++
задачка такая: Написать программу,&quot;шифрующую(расшифровывающею)&quot; текст из файла указанного пользователем,путем добавления (вычитания) к...

Кодирование файла - C++
Задача написать часть полиморфного вируса для курсовой. Т.е нужно подать нашей программе на вход файл она должна зашифровать его по...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
18.04.2013, 17:57
  #2

Не по теме:

Цитата Сообщение от Apoka5555 Посмотреть сообщение
Здравствуйте. Такая проблема: нужно реализовать алгоритм арифметического кодирования и декодирования. Кодирование у меня получилось.
- я бы не был так уверен и думаю лучше было написать так : необратимо исковеркать информацию шифруемого сообщения до неузнаваемости получилось...

Apoka5555
2 / 2 / 1
Регистрация: 18.04.2013
Сообщений: 126
19.04.2013, 16:29  [ТС]     Арифметическое кодирование на С++ #3
Напишите пожалуйста алгоритм декодирования или подскажите как написать. Заранее благодарен.
Zorkina
0 / 0 / 0
Регистрация: 11.12.2016
Сообщений: 16
17.05.2017, 14:33     Арифметическое кодирование на С++ #4
поделитесь программной реализацией пожалуйста, если Вам удалось решить задачу?
Apoka5555
2 / 2 / 1
Регистрация: 18.04.2013
Сообщений: 126
17.05.2017, 16:04  [ТС]     Арифметическое кодирование на С++ #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Есть программа на C#, я уже не помню как она работает, но она работает, по крайней мере работала:
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
143
144
145
146
147
148
149
150
151
152
153
154
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
 
namespace Arifm_coding
{
    class Program
    {
        static void Main(string[] args)
        {
            string word = "PROGRAM";
            
            ArifmCode code = new ArifmCode();
 
            code.Build(word);
            List<Node> nodes = code.GetSymbolsRanges(word);
            List<Node> allCodedNodes = code.Encode(word);
            string decodedNodes = code.Decode(allCodedNodes, word.Length);
 
            Console.ForegroundColor = ConsoleColor.Magenta;
            Console.WriteLine("\n  КОДИРУЕМОЕ СЛОВО:   " + word + "\n");
            Console.WriteLine("\n  Символ  |   Границы символa  | Частота появления");
            Console.WriteLine("----------------------------------------------------");
            foreach (Node node in nodes)
            {
                Console.Write("{0,5}:    |", node.Symbol);
                Console.Write("{0,8:f1}  -", node.Low);
                Console.Write("{0,5:f1}    |", node.High);
                Console.WriteLine("{0,8}", node.Frequency);
            }
            Console.WriteLine("----------------------------------------------------");
            
            Console.WriteLine("\n\n\n\n    НОВЫЕ ГРАНИЦЫ ДЛЯ СИМВОЛОВ: \n");
            Console.WriteLine("\n  Символ  |   Границы символa");
            Console.WriteLine("----------------------------------------------------");
            foreach (Node codedNode in allCodedNodes)
            {
                Console.Write("{0,5}:    |", codedNode.Symbol);
                Console.Write("{0,12}   -", codedNode.Low);
                Console.WriteLine("{0,12}", codedNode.High);
            }
            Console.WriteLine("----------------------------------------------------");
            Console.WriteLine("\n");
 
            Console.WriteLine("  ДЕКОДИРОВАНИЕ:   " + decodedNodes);
            Console.ReadLine();
        }       
    }
 
    public class Node
    {
        public char Symbol { get; set; }
        public double Low { get; set; }
        public double High { get; set; }
        public double Range { get; set; }
        public int Frequency { get; set; }
    }
 
public class ArifmCode
    {
        private List<Node> nodes = new List<Node>();
        public Dictionary<char, int> Frequencies = new Dictionary<char, int>();
 
        public void Build(string source)
        {
            for (int i = 0; i < source.Length; i++)
            {
                if (!Frequencies.ContainsKey(source[i]))
                {
                    Frequencies.Add(source[i], 0);
                }
 
                Frequencies[source[i]]++;
            }
 
            foreach (KeyValuePair<char, int> symbol in Frequencies)
            {
                nodes.Add(new Node() { Symbol = symbol.Key, Frequency = symbol.Value });
            }
 
            nodes = nodes.OrderBy(node => node.Frequency).ToList<Node>();
        }
 
        public List<Node> GetSymbolsRanges(string source)
        {
            double low = 0;
            foreach (Node node in nodes)
            {
                node.Range = Math.Round(((double)(node.Frequency) / (source.Length)), 1);
                node.Low = Math.Round(low, 1);
                node.High = low + node.Range;
                low += node.Range;
            }
            return nodes;
        }
 
        public List<Node> Encode(string source)
        {
            nodes.Reverse();
            List<Node> allNodes = new List<Node>();
            
            for (int i = 0; i < source.Length; i++)
            {
                for (int j = 0; j < nodes.Count; j++)
                {
                    if (source[i] == nodes[j].Symbol)
                    {
                        allNodes.Add(new Node() { Symbol = nodes[j].Symbol, Low = nodes[j].Low, High = nodes[j].High });
                    }
                }
            }
 
            for (int i = 1; i < allNodes.Count; i++)
            {
                for (int j = 0; j < nodes.Count; j++)
                {
                    if (allNodes[i].Symbol == nodes[j].Symbol)
                    {
                        allNodes[i].High = allNodes[i - 1].Low + (allNodes[i - 1].High - allNodes[i - 1].Low) * nodes[j].High;
                        allNodes[i].Low = allNodes[i - 1].Low + (allNodes[i - 1].High - allNodes[i - 1].Low) * nodes[j].Low;
                    }
                }
            }
            return allNodes;
        }
 
        public string Decode(List<Node> allNodes, int count)
        {
            string decode = "";
            double code = allNodes[allNodes.Count - 1].Low;
            int symbolsCount = 0;
 
            while (true)
            {
                for (int i = 0; i < nodes.Count; i++)
                {
                    if (code >= nodes[i].Low && code < nodes[i].High)
                    {
                        decode += nodes[i].Symbol;
                        code = Math.Round((code - nodes[i].Low) / (nodes[i].High - nodes[i].Low), 8);
 
                        symbolsCount++;
                        if (symbolsCount == count)
                            return decode;
                    }
                }
            }
        }
    }
 
 
}
Zorkina
0 / 0 / 0
Регистрация: 11.12.2016
Сообщений: 16
20.05.2017, 12:00     Арифметическое кодирование на С++ #6
спасибо большое за код
вот только не пойму почему при декодирвании с одними данными она работает отлично, а с другими возникают проблемы?
Apoka5555
2 / 2 / 1
Регистрация: 18.04.2013
Сообщений: 126
20.05.2017, 12:11  [ТС]     Арифметическое кодирование на С++ #7
у меня тоже с этим были проблемы, но я так и не смог это решить. Алгоритм та правильно работает, просто с округлением десятичных чисел недостатки в самом языке, он их округляет не так как это нужно вам. Думаю остается только подставлять подходящие данные.
Zorkina
0 / 0 / 0
Регистрация: 11.12.2016
Сообщений: 16
20.05.2017, 13:07     Арифметическое кодирование на С++ #8
наши рассуждения сошлись
спасибо огромное ещё раз
Zorkina
0 / 0 / 0
Регистрация: 11.12.2016
Сообщений: 16
28.05.2017, 22:10     Арифметическое кодирование на С++ #9
подскажите пожалуйста, а почему выбраны именно такие границы интервалов?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.05.2017, 21:21     Арифметическое кодирование на С++
Еще ссылки по теме:

Шифрование и кодирование (lz77) - C++
помогите написать програму!!!! метод шифрования LZ77

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

Кодирование информации! - C++
ПОДСКАЖИТЕ, в чем может быть ошибка! #include &lt;iostream&gt; #include &lt;fstream&gt; using namespace std; void code() { ifstream...

Равномерное кодирование - C++
Задача такова: Программа должна запускаться с командной строки с темя параметрами: имя входного файла, имя выходного файла и режим работы...

Кодирование по Хаффману, C++ - C++
Закодируйте какой-нибудь символьный массив по Хаффману примера ради.

Кодирование слов - C++
Здравствуйте, форумчане. Тренируюсь в с++ - пишу программу. Смысл её в кодировании в ту и в другую сторону слов, учитывая, что a-1, b-2,...


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

Или воспользуйтесь поиском по форуму:
Apoka5555
2 / 2 / 1
Регистрация: 18.04.2013
Сообщений: 126
29.05.2017, 21:21  [ТС]     Арифметическое кодирование на С++ #10
просто на этих границах алгоритм работает.
Yandex
Объявления
29.05.2017, 21:21     Арифметическое кодирование на С++
Ответ Создать тему
Опции темы

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