2 / 2 / 0
Регистрация: 21.12.2012
Сообщений: 15

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

18.11.2013, 02:16. Показов 26428. Ответов 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;
}
Хочу заметить то, что искал в интернете исходники(в том числе и на англоязычных форумах), но они оказались довольно трудными для понимания.
Находил исходники с использованием стандартных шаблонов С++, но нужно обойтись без этого.
Прошу помочь с реализацией получения кодовых слов.
__
Как я понял, нужно сделать массив структур в виде таблицы и дальше работать с этим массивом, и обращаться к его элементам при разбиении вероятностей на части. Примерные идеи и некоторые совсем небольшие наработки есть, но дальше дело не идёт.
_
Также выкладываю результат работы программы, код которой изложен выше.
Мы вводим имя(на скриншоте - изображения), с байтами которого мы хотим работать(и в будущем который мы хотим сжимать/разжимать)
Миниатюры
Алгоритм Шеннона-Фано  
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
18.11.2013, 02:16
Ответы с готовыми решениями:

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

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

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

3
2 / 2 / 0
Регистрация: 21.12.2012
Сообщений: 15
18.11.2013, 19:46  [ТС]
Поднимаю тему.
0
2 / 2 / 0
Регистрация: 21.12.2012
Сообщений: 15
21.11.2013, 00:38  [ТС]
Поднимаю тему.
1
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
21.11.2013, 06:32
Методы Хаффмана и Шеннона-Фано

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

+ инет просто завален примерами
Миниатюры
Алгоритм Шеннона-Фано  
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
21.11.2013, 06:32
Помогаю со студенческими работами здесь

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

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

Кодирование Фано-Шеннона
Добрый день. Есть недочет в коде, цель закодировать и декодировать строку алгоритмом Фано-Шеннона. Проблема в том, что если кодировать...

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

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


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

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

Новые блоги и статьи
Оптимизация производительности Express.js бэкенда
Reangularity 23.05.2025
Express. js заслуженно остаётся одним из самых популярных инструментов для создания бэкенда, но даже он не застрахован от проблем с производительностью. Многие разработчики сталкиваются с ситуацией,. . .
Продвинутая обработка данных с LINQ в C#
stackOverflow 23.05.2025
LINQ (Language Integrated Query) — это фундаментальное изменение парадигмы работы с данными в C#. Простые запросы Where и Select знакомы любому разработчику, но настоящая мощь LINQ раскрывается в. . .
Инфраструктура PKI и сертификатов безопасности
Mr. Docker 23.05.2025
PKI (Public Key Infrastructure) — это невидимый фундамент цифрового доверия, без которого современный интернет просто рассыпался бы как карточный домик. За этой аббревиатурой скрывается целый. . .
Аутентификация OAuth в Python
py-thonny 22.05.2025
OAuth (Open Authorization) — это целый стандарт для делегированного доступа. Звучит занудно? Давайте проще: OAuth позволяет приложениям получать доступ к информации пользователя на сторонних сервисах. . .
Хеширование и соль паролей в веб-приложениях C#
stackOverflow 22.05.2025
Когда-то в начале своей карьеры я тоже грешил простейшими подходами к хранению паролей – MD5-хеширование казалось верхом защиты. Но технологии не стоят на месте, вычислительные мощьности растут, и. . .
Генераторы Python для эффективной обработки данных
AI_Generated 21.05.2025
В Python существует инструмент настолько мощный и в то же время недооценённый, что я часто сравниваю его с тайным оружием в арсенале программиста. Речь идёт о генераторах — одной из самых элегантных. . .
Чем заменить Swagger в .NET WebAPI
stackOverflow 21.05.2025
Если вы создавали Web API на . NET в последние несколько лет, то наверняка сталкивались с зелёным интерфейсом Swagger UI. Этот инструмент стал практически стандартом для документирования и. . .
Использование Linq2Db в проектах C# .NET
UnmanagedCoder 21.05.2025
Среди множества претендентов на корону "идеального ORM" особое место занимает Linq2Db — микро-ORM, балансирующий между мощью полноценных инструментов и легковесностью ручного написания SQL. Что. . .
Реализация Domain-Driven Design с Java
Javaican 20.05.2025
DDD — это настоящий спасательный круг для проектов со сложной бизнес-логикой. Подход, предложенный Эриком Эвансом, позволяет создавать элегантные решения, которые точно отражают реальную предметную. . .
Возможности и нововведения C# 14
stackOverflow 20.05.2025
Выход версии C# 14, который ожидается вместе с . NET 10, приносит ряд интересных нововведений, действительно упрощающих жизнь разработчиков. Вы уже хотите опробовать эти новшества? Не проблема! Просто. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru