Метод Шеннона-Фано

Метод оптимального кодирования Шеннона-Фано позволяет минимизировать избыточность кода. Под кодированием понимается процесс отображения одного набора знаков в другой: представление символов одного (исходного) алфавита в виде символов другого (кодового) алфавита. никакое кодовое слово не должно быть началом никакого другого кодового слова. Код, полученный методом Шеннона-Фано, удовлетворяет условию Фано или принципу префиксности: никакое кодовое слово не должно быть началом никакого другого кодового слова.

[@nahodkiWB309]

Спасибо за понятное объяснение!

[@romantsarev1145]

Вера, рад что Вам понравилось.

[@infup]

Отличное объяснение! Спасибо.

[@romantsarev1145]

Спасибо

[@Artem-u5e9c]

Спасибо большое. Очень понятное объяснение.

[@romantsarev1145]

Пожалуйста

[@Sasha-bm1df]

Очень доходчиво. Спасибо !

[@romantsarev1145]

Пожалуйста.

[@den-ned]

Спасибо. Скоро начну изучать программирование, пока не знаю пригодится ли мне эта тема, но посмотреть было интересно.

[@romantsarev1145]

Ну, как, пригодилось?

[@den-ned]

@@romantsarev1145 Нет, программирование стало менее актуальным с тех пор, и с осени прошлого года перестал его изучать и занялся другой деятельностью, вполне успешно)

[@НікітаПронов]

Здравствуйте, замечательный разбор, а не подскажете как делятся группы например при вероятностях 0.4 0.2 0.4? В какую группу относим второй элемент, к первому или к последнему? Просто разность вероятности 2ух групп в таком случае одинакова

[@romantsarev1145]

Здравствуйте! На Ваше усмотрение.

[@Bezon4ik]

Спасибо, помог

[@romantsarev1145]

Пожалуйста

[@ЧеловекБезСлезинки]

Спасибо за хорошее объяснение, но есть вопрос. Чем Шеррон-Фано отличается от Хаффмана? Просто записано буквально одинаково.

[@romantsarev1145]

В метода Хаффмана мы всегда выбираем минимальные вероятности (сначала среди вероятностей отдельных символов, потом уже и сумм вероятностей). При этом, сортировать предварительно вообще не обязательно. В методе же Ш-A это обязательное условие. Например, этим отличается. В большинстве случаев длина последовательности, сжатой по методу Шеннона - Фано, равна длине сжатой последовательности с использованием кодирования Хаффмана. Однако на некоторых последовательностях могут сформироваться неоптимальные коды Шеннона - Фано, поэтому более эффективным считается сжатие методом Хаффмана (с) Википедия: ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A8%D0%B5%D0%BD%D0%BD%D0%BE%D0%BD%D0%B0_%E2%80%94_%D0%A4%D0%B0%D0%BD%D0%BE

[@oxygensss4390]

Тему понял, но я не знаю зачем это и где пригодится. Объясните пожалуйста

[@perfpg8691]

В моем институте в ближайшее время мы будем писать архиватор на си, с помощью этого метода

[@raydenshow9952]

Спасибо вам большое за объеснение

[@romantsarev1145]

Пожалуйста

[@markysermak6546]

ничего не понятно, но очень интересно

[@romantsarev1145]

Твой комментарий порадовал меня

[@psbd758]

Благодарочку кидаю

[@Вадим-ъ2р8э]

Здравствуйте Роман могли бы мне помочь с решением похожей задачи?

[@romantsarev1145]

Полагаю, что уже не актуально. Что-то не заметил Вашего комментария в свое время. Лучше было на биржу фриланса обратиться. Там бы точно помогли.

[@qwiy5955]

в конце не понял, как добиваются однозначности декодирования?

[@romantsarev1145]

Ни одно кодовое слово не является началом другого кодового слова. То есть, нет ситуации, когда один символ закодирован, например, как 11, а другой - 110, и непонятно при считывании второй единицы (при декодировании) это уже первый символ закончился или второй еще идет. Это называется выполнением принципа префиксности или соблюдением условия Фано.

[@РинатИдрисов-ч8ъ]

такой вопрос : я получил кодовые значения для каждого символа но я не могу понять надо считывать длину кодовой комбинации ? Просто мне надо использовать формулу для уменьшения средней длины кодовой комбинации.

[@romantsarev1145]

Метод Шеннона-Фано дает оптимальный код. Код тем оптимальнее, чем средняя длина кодового слова ближе к минимально возможной. Так что, если Вы хотите узнать насколько код оптимален, то нужно посчитать одно и второе.

[@РинатИдрисов-ч8ъ]

@@romantsarev1145 Спасибо большое за ответ !

[@priest_of_art]

А доказательство эффективности где?

[@romantsarev1145]

Нету. Не ставил такой цели

[@levkornev1013]

Не совсем понятно как двоичный код может обеспечить префиксность если количество элементов больше 8

[@romantsarev1145]

Принцип префиксности - ни одно кодовое слово не может быть началом другого кодового слова. Одно должно выполняться всегда и не зависит ни от системы счисления, ни от числа элементов.

[@levkornev1013]

@@romantsarev1145 тогда не понимаю, как в двоичном коде можно соблюсти этот принцип невзирая на количество кодируемых символов... (на сколько я понял, префиксность проявляется при записи двоичного кода в ряд без разделения)

[@romantsarev1145]

@@levkornev1013 Вы поняли верно. Принцип префиксности позволяет ОДНОЗНАЧНО декодировать символы закодированного сообщения, которые идут сплошняком. Но мне не понятно, что Вам не понятно. Возможно повторный просмотр видео снимет возникшие вопросы. Если нет, задайте их более развернуто.

[@levkornev1013]

@@romantsarev1145 спасибо за ответ, разобрал пример и понял что трактуется однозначно

[@mihrankhachatryan3693]

Вот почему не можно в универе так объяснить?????????

[@romantsarev1145]

Отчего же?! Именно так в Сибирском федеральном университете и преподаю.

[@almazmukushev5993]

У кого есть готовый код на джаве. Шеннона фано??? Или Хаффмана?

[@nanashi106]

Есть на с++

[@almazmukushev5993]

@@nanashi106 можешь скинуть

[@almazmukushev5993]

@@nanashi106 А код Хэмминга есть?

[@nanashi106]

@@almazmukushev5993 Нет, только Шеннона-фано и Хаффмана

[@zhanabaizhuzupov3031]

@@nanashi106 можете ли мне отпр

[@stivensti2031]

автору западло пример привести?

[@romantsarev1145]

Приятно, что на зоне нас тоже смотрят. Для невнимательных: пример начинается на 0:30 и заканчивается на 3:40. И уже потом описание метода в общем виде.