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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 42, средняя оценка - 4.88
dmmih
1 / 1 / 0
Регистрация: 21.12.2012
Сообщений: 15
#1

Алгоритм Шеннона-Фано - C++

18.11.2013, 02:16. Просмотров 6500. Ответов 3
Метки нет (Все метки)

Приветствую всех в этой теме.
Создаю архиватор по методу Шеннона-Фано.
И трудность возникла в программной реализации получения кодовых слов. В теории и на бумаге трудностей в этом нет, чего нельзя сказать про попытки реализовать метод в C++.
Предпринимались некоторые попытки, но они особо ни к чему не привели.
Как понял, данный метод можно сделать через массив структур или рекурсию. Предпочтительнее сделать массивом структур, так как рекурсию пока что в 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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
 
int main(int argc, char *argv[])
{
    unsigned int c[256], mal2; // массив c[256] - количество повторений байта
    char filename[50]; // массив для имени файла
    FILE* f; 
    unsigned char b; 
    int i=0,j=0; 
    int n[256],mal1; // массив n[256] - массив под индексы байтов
    double p[256], mal; // массив p[256] - массив вероятностей
    double s=0; 
    double L=1/log(2); // необходимая переменная для подсчёта ср.кол-ва инф.
    double I=0; // обнуляем значение среднего количества информации
    printf("Input a filename:\n"); 
    scanf ("%s",&filename); // ввод имени файла
    
    for(i=0;i<256;i++) // обнуляем элементы массива количества повторений байтов по циклу
    {c[i]=0;}
    f = fopen(filename,"rb"); // открываем файл в бинарном режиме чтения
 
 /*Считаем количество повторений*/   
    do
{
    fread (&b,1,1, f); 
    c[b]++; 
}
    while (!feof(f));
    c[b]--;
    /*Считаем вероятности повторений байтов*/
    for(i=0; i<256;i++)
    {s=s+c[i];}
    for(i=0; i<256;i++)
    {p[i]=c[i]/s;}
   for(i=0; i<256;i++)
    {
    if (p[i]!=0) 
    {I = I+p[i]*log(1/(p[i]))*L;} // считаем среднее кол-во информации по формуле
    }  
    fclose(f); 
    
    /*Сортируем данные по невозрастанию пузырьковой сортировкой*/    
    for (i=0;i<256;i++) //Данный цикл нужен для того, чтобы у каждого значения байта оставались свои значения вероятности и повторений после сортировки
          { n[i]=i; }  // иначе значения повторения и вероятности у байтов поменяются при выводе результатов, так как индексы остались на своих местах
    for (i=255;i>=0;i--) // сама сортировка
    {
        for (j=i;j<255;j++)
        {
            if (p[j]<p[j+1])
            {
                            mal=p[j];
                            p[j]=p[j+1];
                            p[j+1]=mal;
                            mal1=n[j];
                            n[j]=n[j+1];
                            n[j+1]=mal1;
                            mal2=c[j];
                            c[j]=c[j+1];
                            c[j+1]=mal2;                         
                      }}}
 for (i=0; i<256; i++)   // вывод индексов байтов, кол-ва повторений и вероятности повторений по циклу
{ printf("indeks=%d, kolichestvo=%d, veroyatnost=%f\n", n[i],c[i],p[i]); }
printf("Kol-vo informacii= %lf\n",I); //вывод среднего количества информации    
    system("PAUSE");
    return EXIT_SUCCESS;
}
Хочу заметить то, что искал в интернете исходники(в том числе и на англоязычных форумах), но они оказались довольно трудными для понимания.
Находил исходники с использованием стандартных шаблонов С++, но нужно обойтись без этого.
Прошу помочь с реализацией получения кодовых слов.
__
Как я понял, нужно сделать массив структур в виде таблицы и дальше работать с этим массивом, и обращаться к его элементам при разбиении вероятностей на части. Примерные идеи и некоторые совсем небольшие наработки есть, но дальше дело не идёт.
_
Также выкладываю результат работы программы, код которой изложен выше.
Мы вводим имя(на скриншоте - изображения), с байтами которого мы хотим работать(и в будущем который мы хотим сжимать/разжимать)
Миниатюры
Алгоритм Шеннона-Фано  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.11.2013, 02:16     Алгоритм Шеннона-Фано
Посмотрите здесь:

Алгоритм шеннона фано - C++
Помогите реализовать алгоритм шеннона фано, курсовую скоро сдавать, а у меня ничего не готово, очень нужна помощь!!!!

Алгоритм Шеннона-Фано - C++
Помогите, реализовать Алгоритм Шеннона-Фано на С ++, так чтобы мы вводили сроку из символов, а на выходе получали закодированную сроку из...

Реализовать алгоритм Шеннона-Фано - C++
есть ли кого-то алгоритм шеннона-фано на c++ или java ? нужен код

Алгоритм сжатия методом Шеннона-Фано - C++
Народ, нужна помощь в поиске кода реализующего алгоритм кодирования и декодирования сообщения методом Шеннона-Фано на Си. Заранее...

Двоичный вывод (алгоритм Шеннона Фано) - C++
Здравствуйте! У меня вопрос по поводу реализации алгоритма Шеннона Фано. В соответствие с алгоритмом надо построить бинарное...

Метод Шеннона фано - C++
Помогите пожалуста реализовать самый простой способ этого алгоритма сжатия на С/С++ Добавлено через 14 минут с задаными ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dmmih
1 / 1 / 0
Регистрация: 21.12.2012
Сообщений: 15
18.11.2013, 19:46  [ТС]     Алгоритм Шеннона-Фано #2
Поднимаю тему.
dmmih
1 / 1 / 0
Регистрация: 21.12.2012
Сообщений: 15
21.11.2013, 00:38  [ТС]     Алгоритм Шеннона-Фано #3
Поднимаю тему.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.11.2013, 06:32     Алгоритм Шеннона-Фано
Еще ссылки по теме:

Метод Шеннона-Фано - C++
метод Шеннона-Фано, рассортировал вероятности по убыванию, а после не могу ничего сделать(( помогите плиз, там надо пополам делить и 0 или...

Кодирование Шеннона-Фано - C++
Окей мы посчитали вероятности символов и прочие штуки.. Далее нужно создать таблицу уник. символов.. Сделали.. отсортировали... В...

Метод архивации Шеннона-Фано - C++
Не подскажите,может есть у кого исходник кода архивации(сжатия и восстановления) методом Шеннона-Фано на С++?

Метод Шеннона-Фано и контейнер Map - C++
Пишем лабораторную работу по кодированию - выпал метод Шеннона-Фано, и вторую неделю не получается исправить ошибку с...

Сжатие методом Шеннона-Фано (Pascal -> C++) - C++
Есть код на pascal может кто-нибудь помочь перевести на с++ ? uses crt; var c:char; s,s1,s2:string; i,n,j,j1:byte; ...

Реализация алгоритма кодирования Шеннона-Фано - C++
задание: реализовать алгоритм кодирования Шеннона-Фано, ввести строку символов, на выходе получить таблицу&quot;символ, вероятность, код...


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

Или воспользуйтесь поиском по форуму:
gazlan
3130 / 1905 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
21.11.2013, 06:32     Алгоритм Шеннона-Фано #4
Методы Хаффмана и Шеннона-Фано

+ код ваш совершенно нечитаем, сортировка в C реализована библиотечной функцией, строить нужно не массив, а дерево

+ инет просто завален примерами
Миниатюры
Алгоритм Шеннона-Фано  
Yandex
Объявления
21.11.2013, 06:32     Алгоритм Шеннона-Фано
Ответ Создать тему
Опции темы

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