Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
bikovbiv
3 / 3 / 0
Регистрация: 21.02.2016
Сообщений: 73
1

Кодирование Фано-Шеннона

27.11.2017, 19:14. Просмотров 961. Ответов 12
Метки нет (Все метки)

Добрый день. Есть недочет в коде, цель закодировать и декодировать строку алгоритмом Фано-Шеннона. Проблема в том, что если кодировать строку, состоящую из одного символа (a или aaaaaaaaaa), то результат не выводится, так же при декодировании любой строки при ее выводе добавляются лишние символы, поэтому строу приходится выводить посимвольно. Можете ли подсказать, как исправить косяки, исправить надо что-то в функциях encode и decode файла Codetree.cpp код прилагаю.

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
char* encode(const CodeTree* tree, const char* message)
{
    char* code = new char[MAX_CODE_LEN];
    int len = strlen(message);
    /*const CodeTree* v = tree;
    if (is_leaf(v))
    {
        for (int i = 0; i < len; i++)
        code[i] = '0';
        return code;
    }*/
    const CodeTree** symbols_map = new const CodeTree*[UCHAR_MAX];
    for (int i = 0; i < UCHAR_MAX; ++i) 
    {
        symbols_map[i] = nullptr;
    }
    fill_symbols_map(tree, symbols_map);
    int index = 0;
    char path[UCHAR_MAX];
    for (int i = 0; i < len; ++i)
    {
        const CodeTree* node = symbols_map[message[i] - CHAR_MIN];
        int j = 0;
            while (!is_root(node))
            {
                if (node->parent->left == node)
                    path[j++] = '0';
                else
                    path[j++] = '1';
                node = node->parent;
            }
        while (j > 0) code[index++] = path[--j];
    }
    code[index] = 0;
    delete[] symbols_map;
    return code;
}
 
char* decode(const CodeTree* tree, const char* code, const int _len)
{
    char* message = new char[MAX_CODE_LEN];
    int index = 0;
    int len = strlen(code);
    const CodeTree* v = tree;
    for (int i = 0; i < len; ++i) 
    {
        if (code[i] == '0')
            v = v->left;
        else
            v = v->right;
        if (is_leaf(v)) {
            message[index++] = v->s.c;
            v = tree;
        }
    }
    return message;
}
0
Вложения
Тип файла: rar fannoshannon.rar (2.4 Кб, 10 просмотров)
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.11.2017, 19:14
Ответы с готовыми решениями:

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

Алгоритм Шеннона-Фано
Приветствую всех в этой теме. Создаю архиватор по методу Шеннона-Фано. И...

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

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

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

12
nmcf
6401 / 5663 / 2580
Регистрация: 14.04.2014
Сообщений: 23,965
27.11.2017, 20:00 2
Конец строки message надо явно устанавливать как в 34.
1
bikovbiv
3 / 3 / 0
Регистрация: 21.02.2016
Сообщений: 73
27.11.2017, 21:55  [ТС] 3
спасибо, сейчас попробую

Добавлено через 3 минуты
проблема с выводом декодированной строки исчезла, осталась проблема с кодированием строки из одинаковых символов

Добавлено через 5 минут
получается, если строка состоит из одинаковых символов, то кодовое дерево состоит только из корня, я проверяю на tree->right == NULL && tree->left==NULL, если так, то всю строку заполняю нулями (этот код в encode закоммичен). при этом выполнении программы в этом случае срабатывает исключение, что я не так делаю?
0
nmcf
6401 / 5663 / 2580
Регистрация: 14.04.2014
Сообщений: 23,965
27.11.2017, 22:27 4
И там конец строки надо устанавливать.
1
bikovbiv
3 / 3 / 0
Регистрация: 21.02.2016
Сообщений: 73
27.11.2017, 23:22  [ТС] 5
да, я это уже сделал
C++
1
2
3
4
5
6
7
if (is_leaf(v))
    {
    for (int i = 0; i < len; i++)
       code[i] = '0';
    code[len] = 0;
    return code;
    }
Выскакивает сообщение: Вызвано необработанное исключение: нарушение доступа для чтения.
node было nullptr.
в коде
C++
1
2
3
4
bool is_leaf(const CodeTree* node)
{
    return ((node->left == nullptr) && (node->right == nullptr));
}
0
nmcf
6401 / 5663 / 2580
Регистрация: 14.04.2014
Сообщений: 23,965
27.11.2017, 23:55 6
Ну тогда, разумеется, будет исключение. Дерево не построено, что ли?
1
bikovbiv
3 / 3 / 0
Регистрация: 21.02.2016
Сообщений: 73
28.11.2017, 00:15  [ТС] 7
В случае, если ввожу строку из одинаковых элементов дерево будет состоять только из одного корня
0
bikovbiv
3 / 3 / 0
Регистрация: 21.02.2016
Сообщений: 73
28.11.2017, 00:19  [ТС] 8
на скринпе слева дерево, построенное для строки из различных элементов, справа - для строки из одинаковых эл-тов (один корень = 13)
0
Миниатюры
Кодирование Фано-Шеннона  
bikovbiv
3 / 3 / 0
Регистрация: 21.02.2016
Сообщений: 73
28.11.2017, 00:22  [ТС] 9
само дерево строится в первой функции fannoshannon
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
static int middle(const Symbol* symbols, int l, int sum, int& lsum, int& rsum);
 
CodeTree* fanno_shannon(const Symbol* symbols, int l, int r, int sum)
{
    if (l >= r) return nullptr;
    if (r - l == 1) return make_leaf(symbols[l]);
    int lsum, rsum;
    int m = middle(symbols, l, sum, lsum, rsum);
    CodeTree* ltree = fanno_shannon(symbols, l, m + 1, lsum);
    CodeTree* rtree = fanno_shannon(symbols, m + 1, r, rsum);
    CodeTree* node = make_node(sum, ltree, rtree);
    ltree->parent = node;
    rtree->parent = node;
    return node;
}
CodeTree* fanno_shannon(const Symbol* symbols, int len)
{
    int sum = 0;
    for (int i = 0; i < len; ++i)
        sum += symbols[i].weight;
    return fanno_shannon(symbols, 0, len, sum);
}
CodeTree* fanno_shannon(const char* message)
{
    Symbol symbols[UCHAR_MAX];
    for (int i = 0; i < UCHAR_MAX; ++i) {
        symbols[i].c = i + CHAR_MIN;
        symbols[i].weight = 0;
    }
    int size = strlen(message);
    for (int i = 0; i < size; ++i)
        symbols[message[i] - CHAR_MIN].weight++;
    std::sort(symbols, symbols + UCHAR_MAX, symbol_greater);
    int len = 0;
    while (symbols[len].weight > 0 && len < UCHAR_MAX) len++;
    return fanno_shannon(symbols, len);
}
int middle(const Symbol* symbols, int l, int sum, int& lsum, int& rsum)
{
    int m = l;
    lsum = symbols[m].weight;
    rsum = sum - lsum;
    int delta = lsum - rsum;
    while (delta + symbols[m + 1].weight < 0) {
        m++;
        lsum += symbols[m].weight;
        rsum -= symbols[m].weight;
        delta = lsum - rsum;
    }
    return m;
}
0
nmcf
6401 / 5663 / 2580
Регистрация: 14.04.2014
Сообщений: 23,965
28.11.2017, 10:36 10
Если там возникает ошибка, то в tree нет корректного указателя.
0
bikovbiv
3 / 3 / 0
Регистрация: 21.02.2016
Сообщений: 73
28.11.2017, 12:33  [ТС] 11
То есть не правильно создается дерево?
C++
1
2
3
4
5
6
7
8
9
CodeTree* make_leaf(const Symbol& s)
{
    return new CodeTree{ s, nullptr, nullptr, nullptr };
}
CodeTree* make_node(int weight, CodeTree* left, CodeTree* right)
{
    Symbol s{ 0, weight };
    return new CodeTree{ s, nullptr, left, right };
}
Не могу понять, что нужно исправить
0
nmcf
6401 / 5663 / 2580
Регистрация: 14.04.2014
Сообщений: 23,965
28.11.2017, 14:44 12
Лучший ответ Сообщение было отмечено bikovbiv как решение

Решение

decode() не правильная. У тебя сначала переход на следующий элемент (которого может не быть), а затем проверка is_leaf().
1
bikovbiv
3 / 3 / 0
Регистрация: 21.02.2016
Сообщений: 73
28.11.2017, 17:33  [ТС] 13
Большое спасибо, все получилось
0
28.11.2017, 17:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.11.2017, 17:33

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

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

Метод архивации Шеннона-Фано
Не подскажите,может есть у кого исходник кода архивации(сжатия и...


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

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

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