после кодирования методом rle получилась следующая последовательность
Содержание урока
Задачи
Задачи
1. С помощью алгоритма RLE закодируйте сообщение «ВААААВАААРРРРРРРРРР».
2. После кодирования методом RLE получилась следующая последовательность байтов (первый байт — управляющий):
10000011 10101010 00000010 10101111 11111111 10000101 10101010
Сколько байтов будет содержать данная последовательность после распаковки?
3. После кодирования методом RLE получилась следующая последовательность байтов (первый байт — управляющий):
00000011 10101010 00000010 10101111 10001111 11111111
Сколько байтов будет содержать данная последовательность после распаковки?
4. Раскодируйте сообщение, которое закодировано с помощью приведённого в тексте кода Шеннона-Фано:
5. Постройте дерево, соответствующее коду А — 0, Б — 1, В — 00, Г — 01, Д — 10, Е — 11. Является ли этот код префиксным? Как это определить, посмотрев на дерево?
*6. Постройте дерево Хаффмана для фразы «МАМА МЫЛА ЛАМУ». Найдите коды всех входящих в нее символов и закодируйте сообщение. Чему равен коэффициент сжатия в сравнении с равномерным кодом минимальной длины? С однобайтной кодировкой?
Следующая страница 
§3. Сжатие данных
Cкачать материалы урока
Презентация на тему «Метод RLE-кодирования» (11 класс)
Новые аудиокурсы повышения квалификации для педагогов
Слушайте учебный материал в удобное для Вас время в любом месте
откроется в новом окне
Выдаем Удостоверение установленного образца:
Описание презентации по отдельным слайдам:
Пример задания: Упаковка информации методом RLE-кодирования состоит в следующем. Упакованная последовательность содержит управляющие байты, за каждым управляющим байтом следует один или несколько байтов данных. Если старший бит управляющего байта равен 1, то следующий за управляющим байт данных при распаковке нужно повторить столько раз, сколько записано в оставшихся 7 битах управляющего байта. Если же старший бит управляющего байта равен 0, то надо взять несколько следующих байтов данных без изменения. Сколько именно – записано в оставшихся 7 битах управляющего байта. Например, управляющий байт 10000111 говорит о том, что следующий за ним байт надо повторить 7 раз, а управляющий байт 00000100 – о том, что следующие за ним 4 байта надо взять без изменений. После кодирования методом RLE получилась следующая последовательность байтов (первый байт – управляющий): 10000011 10101010 00000010 10101111 11111111 10000101 10101010. Сколько байт будет содержать данная последовательность после распаковки? Впишите в бланк только число.
Решение: обратите внимание, что в этой задаче НЕ нужно распаковывать последовательность, а нужно просто определить ее длину проанализируем первый управляющий байт, 10000011; он начинается с 1 – это команда на повторение следующего символа; количество повторений записано в семи младших битах: 112 = 3 раза; значит, раскодирование первых двух байт дает 3 символа следующий управляющий байт – третий, 00000010; его старший бит 0 говорит о том, что следующие 102 = 2 символа повторяются 1 раз; получаем еще 2 символа следующий управляющий байт – шестой, 10000101; он говорит о том, что следующий за ним символ нужно повторить 1012 =5 раз; получаем еще 5 символов полная длина распакованной последовательности равна 3 + 2 + 5 = 10 символов вот итог нашего анализа: Управляю-щий байты 1-3 Управляю-щий байт 4 байт 5 Управляю-щий байты 6-10 10000011 10101010 00000010 10101111 11111111 10000101 10101010
Упаковка информации методом RLE-кодирования состоит в следующем. Упакованная последовательность содержит управляющие байты, за каждым управляющим байтом следует один или несколько байтов данных. Если старший бит управляющего байта равен 1, то следующий за управляющим байт данных при распаковке нужно повторить столько раз, сколько записано в оставшихся 7 битах управляющего байта. Если же старший бит управляющего байта равен 0, то надо взять несколько следующих байтов данных без изменения. Сколько именно – записано в оставшихся 7 битах управляющего байта. Например, управляющий байт 10000111 говорит о том, что следующий за ним байт надо повторить 7 раз, а управляющий байт 00000100 – о том, что следующие за ним 4 байта надо взять без изменений. После кодирования методом RLE получилась следующая последовательность байтов (первый байт – управляющий): 00000011 10101010 00000010 10101111 10001111 11111111. Сколько байт будет содержать данная последовательность после распаковки? Впишите в бланк только число.
Содержание урока
Задачи
Задачи
1. С помощью алгоритма RLE закодируйте сообщение «ВААААВАААРРРРРРРРРР».
2. После кодирования методом RLE получилась следующая последовательность байтов (первый байт — управляющий):
10000011 10101010 00000010 10101111 11111111 10000101 10101010
Сколько байтов будет содержать данная последовательность после распаковки?
3. После кодирования методом RLE получилась следующая последовательность байтов (первый байт — управляющий):
00000011 10101010 00000010 10101111 10001111 11111111
Сколько байтов будет содержать данная последовательность после распаковки?
4. Раскодируйте сообщение, которое закодировано с помощью приведённого в тексте кода Шеннона-Фано:
5. Постройте дерево, соответствующее коду А — 0, Б — 1, В — 00, Г — 01, Д — 10, Е — 11. Является ли этот код префиксным? Как это определить, посмотрев на дерево?
*6. Постройте дерево Хаффмана для фразы «МАМА МЫЛА ЛАМУ». Найдите коды всех входящих в нее символов и закодируйте сообщение. Чему равен коэффициент сжатия в сравнении с равномерным кодом минимальной длины? С однобайтной кодировкой?
Следующая страница §3. Сжатие данных
Cкачать материалы урока
Тема: Анализ алгоритма построения последовательности
Главная > Решение
| Информация о документе | |
| Дата добавления: | |
| Размер: | |
| Доступные форматы для скачивания: |
Тема: Анализ алгоритма построения последовательности.
в некоторых задачах (на RLE-кодирование, см. далее) нужно знать, что такое бит и байт, что байт равен 8 бит, что такое старший бит, как переводить числа из двоичной системы в десятичную
в классических задачах (на символьные цепочки) каких-либо особых знаний из курса информатики, кроме умения логически мыслить, не требуется
Пример задания:
Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ
Запишите семь символов подряд, стоящие в восьмой строке со 126-го по 132-е место (считая слева направо).
используя приведенное правило, можно построить следующие строки:
(5) E DCBAABAACBAABAADCBAABAACBAABAA
(6) F E DCBAABAACBAABAADCBAABAACBAABAA E DCBAABAACBAABAADCBAA
BAACBAABAA
мы быстро убедимся, что следующие строки получаются достаточно длинные, и легко запутаться, отсчитывая символы с номерами 126-132 в восьмой строке
попробуем найти закономерности, позволяющие решить задачу без выписывания 8-ой строки;
восьмая строка строится так: восьмая буква латинского алфавита (H) и затем – два раза седьмая строка (сверху написаны номера символов)
символы 126-132 находятся на границе двух цепочек, повторяющих 7-ую строку; заметим, что в соответствии с заданным алгоритмом можно легко определить первые символы в 7-ой строке (GFEDC) и последние символы (AABAA)
далее сразу находим, что интересующая нас часть 8-ой строки имеет вид
таким образом, правильный ответ – BAAGFED.
Возможные ловушки и проблемы :
можно, конечно, попробовать выписать заданную строку и выделить нужные символы, но этот подход очень трудоемкий и чреват случайными ошибками
чаще всего заданная цепочка находится на границе, где соединяются две части строки (например, в этом задании – на границе двух последовательностей, совпадающих с 7-ой строкой)
в задачах этого типа часто встречается игра на последовательностях вида
полезно помнить формулу, которая «сворачивает» сумму степеней двойки:
Еще пример задания:
Упаковка информации методом RLE-кодирования состоит в следующем. Упакованная последовательность содержит управляющие байты, за каждым управляющим байтом следует один или несколько байтов данных. Если старший бит управляющего байта равен 1, то следующий за управляющим байт данных при распаковке нужно повторить столько раз, сколько записано в оставшихся 7 битах управляющего байта. Если же старший бит управляющего байта равен 0, то надо взять несколько следующих байтов данных без изменения. Сколько именно – записано в оставшихся 7 битах управляющего байта. Например, управляющий байт 10000111 говорит о том, что следующий за ним байт надо повторить 7 раз, а управляющий байт 00000100 – о том, что следующие за ним 4 байта надо взять без изменений.
После кодирования методом RLE получилась следующая последовательность байтов (первый байт – управляющий):
10000011 10101010 00000010 10101111 11111111 10000101 10101010.
Сколько байт будет содержать данная последовательность после распаковки? Впишите в бланк только число.
обратите внимание, что в этой задаче НЕ нужно распаковывать последовательность, а нужно просто определить ее длину
проанализируем первый управляющий байт, 1 0000011 ; он начинается с 1 – это команда на повторение следующего символа; количество повторений записано в семи младших битах: 11 2 = 3 раза; значит, раскодирование первых двух байт дает 3 символа
следующий управляющий байт – третий, 0 0000010 ; его старший бит 0 говорит о том, что следующие 10 2 = 2 символа повторяются 1 раз; получаем еще 2 символа
следующий управляющий байт – шестой, 1 0000101 ; он говорит о том, что следующий за ним символ нужно повторить 101 2 =5 раз; получаем еще 5 символов
полная длина распакованной последовательности равна 3 + 2 + 5 = 10 символов
Тема: Анализ алгоритма построения последовательности
Тема: Анализ алгоритма построения последовательности.
· в некоторых задачах (на RLE-кодирование, см. далее) нужно знать, что такое бит и байт, что байт равен 8 бит, что такое старший бит, как переводить числа из двоичной системы в десятичную
· в классических задачах (на символьные цепочки) каких-либо особых знаний из курса информатики, кроме умения логически мыслить, не требуется
Пример задания:
Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу:
Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ
Запишите семь символов подряд, стоящие в восьмой строке со 126-го по 132-е место (считая слева направо).
1) используя приведенное правило, можно построить следующие строки:
(6) FEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAADCBAA BAACBAABAA
2) мы быстро убедимся, что следующие строки получаются достаточно длинные, и легко запутаться, отсчитывая символы с номерами 126-132 в восьмой строке
3) попробуем найти закономерности, позволяющие решить задачу без выписывания 8-ой строки;
4) прежде всего, заметим, что длины первых строк 1, 3, 7, 15, … – это числа вида 2i-1, где i – номер строки; таким образом, длина 7-ой строки – 127, а длина восьмой – 255 символов
5) восьмая строка строится так: восьмая буква латинского алфавита (H) и затем – два раза седьмая строка (сверху написаны номера символов)
6) символы 126-132 находятся на границе двух цепочек, повторяющих 7-ую строку; заметим, что в соответствии с заданным алгоритмом можно легко определить первые символы в 7-ой строке (GFEDC) и последние символы (AABAA)
7) далее сразу находим, что интересующая нас часть 8-ой строки имеет вид
8) таким образом, правильный ответ – BAAGFED.
Возможные ловушки и проблемы:
· можно, конечно, попробовать выписать заданную строку и выделить нужные символы, но этот подход очень трудоемкий и чреват случайными ошибками
· чаще всего заданная цепочка находится на границе, где соединяются две части строки (например, в этом задании – на границе двух последовательностей, совпадающих с 7-ой строкой)
· в задачах этого типа часто встречается игра на последовательностях вида
полезно помнить формулу, которая «сворачивает» сумму степеней двойки:
(для доказательства используйте тот факт, что двоичное число, состоящее только из единиц, имеет вид 2n-1)
Еще пример задания:
Упаковка информации методом RLE-кодирования состоит в следующем. Упакованная последовательность содержит управляющие байты, за каждым управляющим байтом следует один или несколько байтов данных. Если старший бит управляющего байта равен 1, то следующий за управляющим байт данных при распаковке нужно повторить столько раз, сколько записано в оставшихся 7 битах управляющего байта. Если же старший бит управляющего байта равен 0, то надо взять несколько следующих байтов данных без изменения. Сколько именно – записано в оставшихся 7 битах управляющего байта. Например, управляющий байт говорит о том, что следующий за ним байт надо повторить 7 раз, а управляющий байт – о том, что следующие за ним 4 байта надо взять без изменений.
После кодирования методом RLE получилась следующая последовательность байтов (первый байт – управляющий):
Сколько байт будет содержать данная последовательность после распаковки? Впишите в бланк только число.
1) обратите внимание, что в этой задаче НЕ нужно распаковывать последовательность, а нужно просто определить ее длину
2) проанализируем первый управляющий байт, ; он начинается с 1 – это команда на повторение следующего символа; количество повторений записано в семи младших битах: 112 = 3 раза; значит, раскодирование первых двух байт дает 3 символа
3) следующий управляющий байт – третий, ; его старший бит 0 говорит о том, что следующие 102 = 2 символа повторяются 1 раз; получаем еще 2 символа
4) следующий управляющий байт – шестой, ; он говорит о том, что следующий за ним символ нужно повторить 1012 =5 раз; получаем еще 5 символов
5) полная длина распакованной последовательности равна 3 + 2 + 5 = 10 символов