23.09.2017, 06:54 [+3 UTC]
в нашей команде: 2 126 чел. | участники онлайн: 1 (рекорд: 21)

:: РЕГИСТРАЦИЯ

:: консультации

:: задать вопрос

:: все разделы

:: правила

:: новости

:: участники

:: доска почёта

:: форум

:: блоги

:: поиск

:: статистика

:: наш журнал

:: наши встречи

:: наша галерея

:: отзывы о нас

:: поддержка

:: руководство

Версия системы:
7.41 (25.02.2017)

Общие новости:
23.02.2017, 09:51

Форум:
21.09.2017, 12:28

Последний вопрос:
22.09.2017, 19:10

Последний ответ:
22.09.2017, 18:06

Последняя рассылка:
22.09.2017, 21:45

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
26.01.2011, 09:42 »
xenitron
Огромное Вам спасибо за проделанную работу. [вопрос № 182000, ответ № 265598]
27.09.2015, 20:57 »
Рыленков Геннадий Петрович
Методическая, квалифицированная помощь Академика Владимира Алексеева помогла решить довольно сложный вопрос по новой операционной системе Wndows 10. Спасибо.

РАЗДЕЛ • Информатика

Консультации и решение задач по информатике.

[администратор рассылки: Андреенков Владимир (Профессор)]

Лучшие эксперты в этом разделе

Зенченко Константин Николаевич
Статус: Модератор
Рейтинг: 250
Лысков Игорь Витальевич
Статус: Старший модератор
Рейтинг: 239
CradleA
Статус: Профессионал
Рейтинг: 35

Перейти к консультации №:
 

Консультация онлайн # 191100
Раздел: • Информатика
Автор вопроса: asdf1234 (Посетитель)
Отправлена: 07.06.2017, 13:07
Поступило ответов: 1

Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
4. Синтезировать коды Шеннона-Фено и Хаффмена для указанной ниже группы символов:
Символы Вероятности
Z1 0.05
Z2 0.13
Z3 0.20
Z4 0.15
Z5 0.22
Z6 0.07
Z7 0.08
Z8 0.10


Вопрос перенесен из раздела • Математика
--------

• Отредактировал: Гордиенко Андрей Владимирович (Модератор)
• Дата редактирования: 07.06.2017, 14:04

Состояние: Консультация закрыта

Здравствуйте, asdf1234!

Алгоритм Шеннона-Фано работает следующим образом:

1. Упорядочиваем символы по невозрастанию вероятностей.
2. Делим последовательность символов на две группы с примерно равной суммой вероятностей. Для первой группы добавляем справа в код 1, для второй - 0.
3. Повторяем предыдущий шаг для каждой из групп, пока не получим группу из единственного символа.

В данном случае это будет выглядеть так:

СимволыВероятности
Z50.22
Z30.20
Z40.15
Z20.13
Z80.10
Z70.08
Z60.07
Z10.05

Это исходная таблица. Разбиваем её на две группы так, чтобы сумма вероятностей в каждой была по возможности близка к 0.5 и присваиваем первой код 1, а второй - код 0:
СимволыВероятностиКод
Z5,Z3,Z40.22+0.20+0.15=0.571
Z2,Z8,Z7,Z6,Z10.13+0.10+0.08+0.07+0.05=0.430

Теперь разбиваем первую группу на две с суммой вероятностей близкой к 0.57/2=0.285 и присваиваем им коды 11 и 10, а вторую - на две с суммой вероятностей близкой к 0.43/2=0.215 и присваиваем им коды 01 и 00:
СимволыВероятностиКод
Z50.2211
Z3,Z40.20+0.15=0.3510
Z2,Z80.13+0.10=0.2301
Z7,Z6,Z10.08+0.07+0.05=0.2000

Первая из четырёх получившихся групп содержит только один символ и дальше не разбивается. Остальные разбиваются надвое аналогичным образом:
СимволыВероятностиКод
Z50.2211
Z30.20101
Z40.15100
Z20.13011
Z80.10010
Z70.08001
Z6,Z10.07+0.05=0.12000

Теперь все группы содержат по одному символу, только последняя - два. Её разбиваем надвое:
СимволыВероятностиКод
Z50.2211
Z30.20101
Z40.15100
Z20.13011
Z80.10010
Z70.08001
Z60.070001
Z10.050000

и на этом построение кода Шеннона-Фано закончено.

Алгоритм Хаффмана работает следующим образом:

1. Упорядочиваем символы по невозрастанию вероятностей.
2. Два символа с наименьшими вероятностями заменяем группой с суммарной вероятностью. Для первого символа группы добавляем слева в код 0, для второго - 1, для остальных символов не добавляем ничего.
3. Повторяем, пока не получим группу, объединяющую все символы.

В данном случае это будет выглядеть так:

СимволыВероятности
Z50.22
Z30.20
Z40.15
Z20.13
Z80.10
Z70.08
Z60.07
Z10.05

Объединяем два последних символа (Z6 и Z1) в одну группу и присваиваем им коды 0 и 1. Остальным символам коды не присваиваем:
СимволыВероятностиКоды
Z50.22
Z30.20
Z40.15
Z20.13
Z80.10
Z70.08
Z6,Z10.07+0.05=0.120,1

Упорядочиваем получившуюся таблицу по убыванию вероятностей:
СимволыВероятностиКоды
Z50.22
Z30.20
Z40.15
Z20.13
Z6,Z10.120,1
Z80.10
Z70.08


и объединяем символы Z8 и Z7, присваивая новой группе коды 0 и 1 (остальные символы по-прежнему не имеют кодов):
СимволыВероятностиКоды
Z50.22
Z30.20
Z40.15
Z20.13
Z6,Z10.120,1
Z8,Z7,0.10+0.08=0.180,1

Упорядочиваем получившуюся таблицу по убыванию вероятностей:
СимволыВероятностиКоды
Z50.22
Z30.20
Z8,Z70.180,1
Z40.15
Z20.13
Z6,Z10.120,1

и объединяем два последних символа (Z2 и Z6,Z1) в одну группу, присвоив им коды 0 и 10,11:
СимволыВероятностиКоды
Z50.22
Z30.20
Z8,Z70.180,1
Z40.15
Z2,Z6,Z10.13+0.12=0.250,10,11

Упорядочиваем получившуюся таблицу по убыванию вероятностей:
СимволыВероятностиКоды
Z2,Z6,Z10.250,10,11
Z50.22
Z30.20
Z8,Z70.180,1
Z40.15

и объединяем символы Z8,Z7 и Z4, присваивая новой группе коды 00,01 и 1:
СимволыВероятностиКоды
Z2,Z6,Z10.250,10,11
Z50.22
Z30.20
Z8,Z7,Z40.18+0.15=0.3300,01,1

Упорядочиваем получившуюся таблицу по убыванию вероятностей:
СимволыВероятностиКоды
Z8,Z7,Z40.3300,01,1
Z2,Z6,Z10.250,10,11
Z50.22
Z30.20

и объединяем два последних символа (Z5 и Z3) в одну группу, присвоив им коды 0 и 1:
СимволыВероятностиКоды
Z8,Z7,Z40.3300,01,1
Z2,Z6,Z10.250,10,11
Z5,Z30.22+0.20=0.420,1

Упорядочиваем получившуюся таблицу по убыванию вероятностей:
СимволыВероятностиКоды
Z5,Z30.420,1
Z8,Z7,Z40.3300,01,1
Z2,Z6,Z10.250,10,11

и объединяем символы Z8,Z7,Z4 и Z2,Z6,Z1, присваивая новой группе коды 000,001,01 и 10,110,111:
СимволыВероятностиКоды
Z5,Z30.420,1
Z8,Z7,Z4,Z2,Z6,Z10.33+0.25=0.58000,001,01,10,110,111

Упорядочиваем получившуюся таблицу по убыванию вероятностей:
СимволыВероятностиКоды
Z8,Z7,Z4,Z2,Z6,Z10.58000,001,01,10,110,111
Z5,Z30.420,1

Поскольку осталось только две группы символов, добавляем слева к кодам первой 0, а к кодам второй - 1 и снова разделяем группы на отдельные символы:
СимволыКоды
Z80000
Z70001
Z4001
Z2010
Z60110
Z10111
Z510
Z311

На этом построение кода Хаффмана закончено.


Консультировал: Коцюрбенко Алексей aka Жерар (Мастер-Эксперт)
Дата отправки: 08.06.2017, 05:55

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Мини-форум консультации № 191100

Гордиенко Андрей Владимирович
Модератор

ID: 17387

# 1

= общий = | 07.06.2017, 14:04 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
Экспертам раздела:

Обратите, пожалуйста, внимание на данную консультацию, перенесённую из другого раздела.

=====
Facta loquuntur.

Гордиенко Андрей Владимирович
Модератор

ID: 17387

# 2

= общий = | 07.06.2017, 21:40 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
asdf1234:

Посмотрите решение аналогичной задачи здесь.

=====
Facta loquuntur.

 

Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.13974 сек.

© 2001-2017, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.41 от 25.02.2017
Бесплатные консультации онлайн