В области сжатия данных, код Шеннона, названный в честь его создателя, Клода Шеннона, — это алгоритм сжатия данных без потерь с помощью построения префиксных кодов на основе набора символов и их вероятностей (расчётное или измеренное). Он является субоптимальным в том смысле, что не позволяет достичь минимально возможных кодовых длин как в кодировании Хаффмана, и никогда не будет лучше, но иногда равным с кодом Шеннона-Фано.
Этот метод был первым в своём роде, эта методика была использована для доказательства теоремы Шеннона о помехоустойчивом кодировании в 1948 в его статье «Математическая Теория связи»[1].
В кодировании Шеннона символы располагаются в порядке от наиболее вероятных к наименее вероятным. Им присваиваются коды, путём взятия первых <math>l_i = \left\lceil -\log_2 p_i \right\rceil </math> цифр из двоичного разложения кумулятивной вероятности <math> \sum\limits_{k=1}^{i-1} p_k</math> . Здесь <math>\left\lceil x \right\rceil</math> обозначает функцию потолок, которая округляет <math>x</math> до ближайшего целого значения, большего либо равного <math>x</math>.
Пример
В данной таблице представлен пример кодирования методом Шеннона. Можно сразу заметить по итоговым кодам, что он является менее оптимальным, чем метод Фано-Шеннона.
Первым шагом будет подсчёт вероятностей каждого символа. Затем считается число <math>l</math> для каждой вероятности. Например, для a2 оно равно трём (<math>2^{-3} \leq 0,18 \leq 2^{-2}</math> — минимальная степень двойки −3, следовательно <math>l</math> равно трём). После этого считается сумма вероятностей от 0 до i-1 и переводится в двоичную форму. Потом дробная часть усекается слева до <math>l_i</math> числа знаков.
ai
|
p(ai)
|
li
|
Сумма 0 до i-1
|
Сумма по p(ai) bin
|
Итоговый код
|
a1
|
0.36
|
2
|
0.0
|
0.0000
|
00
|
a2
|
0.18
|
3
|
0.36
|
0.0101
|
010
|
a3
|
0.18
|
3
|
0.54
|
0.1000
|
100
|
a4
|
0.12
|
4
|
0.72
|
0.1011
|
1011
|
a5
|
0.09
|
4
|
0.84
|
0.1101
|
1101
|
a6
|
0.07
|
4
|
0.93
|
0.1110
|
1110
|
Ссылки
Шаблон:Примечания
Шаблон:Math-stub
Шаблон:Методы сжатия
Партнерские ресурсы |
---|
Криптовалюты |
|
---|
Магазины |
|
---|
Хостинг |
|
---|
Разное |
- Викиум - Онлайн-тренажер для мозга
- Like Центр - Центр поддержки и развития предпринимательства.
- Gamersbay - лучший магазин по бустингу для World of Warcraft.
- Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память.
- Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России.
- Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме.
- Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео.
- Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет
- SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона.
- «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется.
- StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.
- Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено.
- StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.
|
---|