Регистрация Спросить otvet5GPT
ЛюБИмИЦа55
06.06.2021 02:47
Информатика
Есть ответ 👍

Провести кодирование строки "to be or not to be? " кодом хаффмана и определить избыточность кода. текст в ковычках, там получается 19 символов, никак не могу построить правильное дерево, чтобы закодировать.

184
338
Посмотреть ответы 2

Ответы на вопрос:

tanyaosipova01
tanyaosipova01
4,6(66 оценок)
Подсчитываются  вероятности  появления  символов  первичного  алфавита  в  исходном  тексте  (если  они  незаданы  заранее)символы  первичного  алфавита  m1  выписывают  в  порядке  убывания  вероятностей.последние  n0  символов  объединяют  в  новый  символ,  вероятность  которого  равна  суммарной  вероятностиэтих  символов,  удаляют  эти  символы  и  вставляют  новый  символ  в  список  остальных  на  соответствующееместо  (по  вероятности).  n0  вычисляется  из  системы: , где  a  —  целое  число,  m1  и  m2  —  мощность  первичного  и  вторичного  алфавита  соответственно.последние  m2  символов  снова  объединяют  в  один  и  вставляют  его  в  соответствующей  позиции,предварительно  удалив  символы,  вошедшие  в  объединение.предыдущий  шаг  повторяют  до  тех  пор,  пока  сумма  всех  m2  символов  не  станет  равной  1. этот  процесс  можно  представить  как  построение  дерева,  корень  которого  —  символ  с  вероятностью  1,получившийся  при  объединении  символов  из  последнего  шага,  его  m2  потомков  —  символы  из  предыдущегошага  и  т.  д. каждые  m2  элементов,  стоящих  на  одном  уровне,  нумеруются  от  0  до  m2-1.  коды  получаются  из  путей  (отпервого  потомка  корня  и  до  листка).  при  декодировании  можно  использовать  то  же  самое  дерево,считывается  по  одной  цифре  и  делается  шаг  по  дереву,  пока  не  достигается  лист  —  тогда  выводится  символ,стоящий  в  листе  и  производится  возврат  в  корень. построение  дерева  хаффмана бинарное  дерево,  соответствующее  коду  хаффмана,  называют  деревом  хаффмана.   построения  кода  хаффмана  равносильна    построения  соответствующего  ему  дерева. общая  схема  построения  дерева  хаффмана: составим  список  кодируемых  символов  (при  этом  будем  рассматривать  каждый  символ  как  одноэлементноебинарное  дерево,  вес  которого  равен  весу  символа).из  списка  выберем  2  узла  с  наименьшим  весом  (под  весом  можно  понимать  частоту  использования  символа—  чем  чаще  используется,  тем  больше  весит).сформируем  новый  узел  и  присоединим  к  нему,  в  качестве  дочерних,  два  узла  выбранных  из  списка.  приэтом  вес  сформированного  узла  положим  равным  сумме  весов  дочерних  узлов.добавим  сформированный  узел  к  списку.если  в  списке  больше  одного  узла,  то  повторить  2-5. пример  реализации пример  реализации  алгоритма  хаффмана  на  языке // скомпилируйте и введите java huffmantest class tree { public tree child0; // потомки "0" и "1" public tree child1; public boolean leaf; // признак листового дерева public int character; // входной символ public int weight; // вес этого символа public tree() {} public tree(int character, int weight, boolean leaf) { this.leaf = leaf; this.character = character; this.weight = weight; } /* обход дерева с генерацией кодов 1. "распечатать" листовое дерево и записать код хаффмана в массив 2. рекурсивно обойти левое поддерево (с генерированием кода). 3. рекурсивно обойти правое поддерево. */ public void traverse(string code, huffman h) { if (leaf) { system.out.println((char)character +" "+ weight +" "+ code); h.code[character] = code; } if ( child0 ! = null) child0.traverse(code + "0", h); if ( child1 ! = null) child1.traverse(code + "1", h); } } class huffman { public static final int alphabetsize = 256; tree[] tree = new tree[alphabetsize]; // рабочий массив деревьев int weights[] = new int[alphabetsize]; //
222812
222812
4,6(82 оценок)
Выполняем все действия: 72+21-75=18

Реши свою проблему, спроси otvet5GPT

  • Быстро
    Мгновенный ответ на твой вопрос
  • Точно
    Бот обладает знаниями во всех сферах
  • Бесплатно
    Задай вопрос и получи ответ бесплатно

Популярно: Информатика

Caktus Image

Есть вопросы?

  • Как otvet5GPT работает?

    otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.

  • Сколько это стоит?

    Проект находиться на стадии тестирования и все услуги бесплатны.

  • Могу ли я использовать otvet5GPT в школе?

    Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!

  • В чем отличия от ChatGPT?

    otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.

Подпишись на наш телеграмм канал

GTP TOP NEWS