Главная страница

Информация и информационные процессы Практические работы Алгоритм rle


Скачать 188 Kb.
НазваниеИнформация и информационные процессы Практические работы Алгоритм rle
Дата30.09.2022
Размер188 Kb.
Формат файлаdoc
Имя файлаpractice11-1.doc
ТипДокументы
#707647


И
01.10.2022
нформатика, 11 класс К.Ю. Поляков, Е.А. Ере
мин
  1. Информация и информационные процессы

Практические работы


      1. Алгоритм RLE


  1. Используя алгоритм RLE, закодируйте последовательность символов

BBBBBBACCCABBBBBB

Запишите результат в виде шестнадцатеричных кодов (каждый символ кодируется в виде байта, который представлен двумя шестнадцатеричными цифрами ). Проверьте полученный результат с помощью программы RLE.

Ответ:

  1. Раскодируйте последовательность, упакованную с помощью алгоритма RLE (приводятся шестнадцатеричные коды): 01 4D 8E 41 01 4D 8E 4116. Для определения символов по их шестнадцатеричным кодом используйте таблицу ASCII. В приведённой таблице в первом столбце записана первая цифра шестнадцатеричного кода символа, а в первой строке – вторая. Например, символ «&» имеет шестнадцатеричный код 2616.

 

.0

.1

.2

.3

.4

.5

.6

.7

.8

.9

.A

.B

.C

.D

.E

.F

0.

NUL

SOH

STX

ETX

EOT

ENQ

ACK

BEL

BS

TAB

LF

VT

FF

CR

SO

SI

1.

DLE

DC1

DC2

DC3

DC4

NAK

SYN

ETB

CAN

EM

SUB

ESC

FS

GS

RS

US

2.

 

 !

"

#

$

 %

&

'

(

)

*

+

,



.

/

3.

0

1

2

3

4

5

6

7

8

9

 :

 ;

<

=

>

 ?

4.

@

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

5.

P

Q

R

S

T

U

V

W

X

Y

Z

[

\

]

^

_

6.

`

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

7.

p

q

r

s

t

u

v

w

x

y

z

{

|

}



DEL

Ответ:

  1. Определите количество байтов в исходной и распакованной последовательности (см. предыдущее задание) и вычислите коэффициент сжатия:

    Сжатая последовательность

    Несжатая последовательность

    Коэффициент сжатия










  2. Проверьте результат, полученный в предыдущем пункте, с помощью программы RLE. Предложите два способа проверки.

  3. Постройте последовательности, которые сжимаются алгоритмом RLE ровно в 2 раза, в 4 раза, в 5 раз. Проверьте свои ответы с помощью программы RLE.

    Несжатая последовательность

    Сжатая последовательность

    Коэффициент сжатия







    2







    4







    5

  4. Придумайте три последовательности, которые невозможно сжать с помощью алгоритма RLE:

    Несжатая последовательность

    «Сжатая» последовательность

    Коэффициент сжатия




























  5. Используя программу RLE, примените RLE-сжатие к следующим файлам и найдите для каждого из них коэффициент сжатия:

    Файл

    Размер без сжатия

    Размер после сжатия

    Коэффициент сжатия

    grad_vert.bmp










    grad_horz.bmp










    grad_diag.jpg










  6. Объясните результаты, полученные в предыдущем пункте:

    • почему не удается сжать рисунки в формате JPEG?

Ответ:

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

Ответ:

  1. Оцените максимально достижимый коэффициент сжатия с помощью рассмотренного в учебнике варианта RLE-алгоритма. В каком случае его удастся достичь?

Ответ:

  1. Оцените коэффициент сжатия с помощью RLE-алгоритма в худшем случае. Опишите этот худший случай.

Ответ:


      1. Сравнение алгоритмов сжатия


При выполнении этой работы используются программы RLE (алгоритм сжатия RLE) и Huffman (кодирование Хаффмана и Шеннона-Фано).

  1. Запустите программу Huffman.exe и закодируйте строку «ЕНОТ НЕ ТОНЕТ», используя методы Шеннона-Фано и Хаффмана. Запишите результаты в таблицу:




Шеннон и Фано

Хаффман

Длина основного кода







Длина кодовой таблицы (дерева)







Коэффициент сжатия (по основным кодам)







Коэффициент сжатия (с учетом дерева кодов)







Сделайте выводы.

Ответ:

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

Ответ:

  1. Используя кнопку Анализ файла в программе Huffman, определите предельный теоретический коэффициент сжатия для файла a.txt1 при побайтном кодировании.

Ответ:

  1. С помощью программ RLE и Huffman выполните сжатие файла a.txt разными способами. Запишите результаты в таблицу:




RLE

Шеннон и Фано

Хаффман

Размер сжатого файла










Коэффициент сжатия










Объясните результат, полученный с помощью алгоритма RLE.

Ответ:

  1. Используя кнопку Анализ файла в программе Huffman, определите предельный теоретический коэффициент сжатия для файла a.txt.huf при побайтном кодировании. Объясните результат.

Ответ:

  1. Примените несколько раз повторное сжатие этого файла с помощью алгоритма Хаффмана (новые файлы получат имена a.txt.huf2, a.txt.huf3 и т.д.) и заполните таблицу, каждый раз выполняя анализ полученного файла.




Размер файла

Предельный коэффициент сжатия

a.txt







a.txt.huf







a.txt.huf2







a.txt.huf3







a.txt.huf4







a.txt.huf5







a.txt.huf6







Объясните, почему с некоторого момента при повторном сжатии файла его размер увеличивается.

Ответ:

  1. Выполните те же действия, используя метод Шеннона-Фано.




Размер файла

Предельный коэффициент сжатия

a.txt







a.txt.shf







a.txt.shf2







a.txt.shf3







a.txt.shf4







a.txt.shf5







a.txt.shf6







Объясните, почему с некоторого момента при повторном сжатии файла его размер увеличивается.

Ответ:

  1. Сравните результаты сжатия этого файла с помощью алгоритма RLE, лучшие результаты, полученные методами Шеннона-Фано и Хаффмана, а также результат сжатия этого файла каким-нибудь архиватором.




Размер файла

Предельный коэффициент сжатия

RLE







Хаффман







Шеннон и Фано







ZIP







RAR







7Z







Объясните результаты и сделайте выводы.

Ответ:


      1. Использование архиватора


  1. Изучите возможности архиватора, который установлен на вашем компьютере (Ark, 7-Zip, WinRAR или др.).

  2. Откройте каталог, указанный учителем. Он должен содержать все файлы, которые используются далее.

  3. Распакуйте архив secret.zip, который упакован с паролем secretLatin. В подкаталогах, получившихся после распаковки, вы должны найти 3 файла, содержащие части высказывания на латинском языке, которое означает «договоры следует выполнять».

  4. Создайте новый текстовый файл latin.txt и запишите в него это высказывание на латыни. После этого удалите архив secret.zip.

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

Имя файла

Описание

Объем до

сжатия, Кб

Объем после сжатия, Кб

Коэффициент сжатия

random.dat

случайные данные

391







morning.zip

сжатый файл

244







sunset.jpg

рисунок в формате JPEG

730







prog.exe

программа для Windows

163







signal.mp3

звук в формате MP3

137







forest.wav

звук в формате WAV

609







ladoga.bmp

рисунок в формате BMP

9217







tolstoy.txt

текст

5379







Сделайте выводы о том, какие файлы обычно сжимаются лучше, а какие – хуже:

Ответ:

  1. Если ваш архиватор позволяет создавать самораспаковывающиеся архивы, сравните размеры обычного архива и SFX-архива для файла tolstoy.txt:

Имя архива

Описание

Объем до

сжатия, Кб

Объем после сжатия, Кб

tolstoy.7z

обычный архив

5379




tolstoy.exe

SFX-архив

5379




Объясните, почему размеры двух архивов получились разные. После этого удалите оба созданных архива.

  1. Переместите рисунки в отдельный каталог Pictures, а звуковые файлы – в каталог Sounds.

  2. Упакуйте рисунки и звуки в архив Media с паролем media123.

  3. Упакуйте все остальные файлы и папки в архив Data (без пароля).

  4. Удалите все файлы, кроме архивов Media и Data, и покажите работу учителю.



      1. Сжатие с потерями


  1. Скопируйте в свою папку файл valaam.bmp.

  2. Используя растровый графический редактор (GIMP, Photoshop), сохраните несколько копий этого рисунка с разным качеством, от 0% до 100%.

В редакторе GIMP нужно выбрать пункт меню Файл – Экспортировать, ввести имя файла с расширением JPG (например, для файла с качеством 50% можно использовать имя valaam50.jpg) и в появившемся окне установить нужное качество:

В редакторе Photoshop нужно выбрать пункт меню Файл – Сохранить как…, далее в окне сохранения файла выбрать формат JPEG, ввести имя файла с расширением JPG (например, для файла с качеством 50% можно использовать имя valaam50.jpg) и в появившемся окне установить нужное качество (от 0 до 12):

  1. В табличном процессоре заполните таблицу

Для GIMP:

Качество, %

0

10

20

30

40

50

60

70

80

90

100

Объем файла, Кбайт


































Для Photoshop:

Качество, %

0

1

2

3

4

5

6

7

8

9

10

11

12

Объем файла, Кбайт








































С помощью табличного процессора постройте график по этим данным.

График:

Сделайте выводы.

Ответ:

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

Ответ:

  1. Скопируйте в свою папку звуковой файл bears.mp3.

  2. Используя звуковой редактор (например, Audacity), сохраните несколько копий этого звукового файла с разным качеством. Для формата Ogg Vorbis используйте качество от 0 до 10, для формата MP3 – битрейт от 8 до 128 Кбит/с.

  3. В табличном процессоре заполните таблицу

Для формата Ogg Vorbis:

Качество

1

2

3

4

5

6

7

8

9

10

Объем файла, Кбайт































Для формата MP3:

Битрейт, Кбит/с

8

16

32

48

64

96

128

Объем файла, Кбайт






















Постройте график по этим данным.

График:

Объясните, почему получилась именно такая зависимость.

Ответ:

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

Ответ:

1 Этот файл имеет объем 1 Мбайт и состоит из одних символов «А».

http://kpolyakov.spb.ru



написать администратору сайта