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

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

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

1. Информация и информационные процессы

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

1. 
   Алгоритм RLE

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

BBBBBBACCCABBBBBB

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

Ответ:

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

.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

Ответ:

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

   Сжатая последовательность	Несжатая последовательность	Коэффициент сжатия

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

   Несжатая последовательность	Сжатая последовательность	Коэффициент сжатия
   		2
   		4
   		5

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

   Несжатая последовательность	«Сжатая» последовательность	Коэффициент сжатия

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

   Файл	Размер без сжатия	Размер после сжатия	Коэффициент сжатия
   grad_vert.bmp
   grad_horz.bmp
   grad_diag.jpg

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

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

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

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

	Шеннон и Фано	Хаффман
Длина основного кода
Длина кодовой таблицы (дерева)
Коэффициент сжатия (по основным кодам)
Коэффициент сжатия (с учетом дерева кодов)

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

Ответ:

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

Ответ:

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

Ответ:

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

	RLE	Шеннон и Фано	Хаффман
Размер сжатого файла
Коэффициент сжатия

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

Ответ:

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

Ответ:

5. 
   Примените несколько раз повторное сжатие этого файла с помощью алгоритма Хаффмана (новые файлы получат имена 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

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

Ответ:

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

	Размер файла	Предельный коэффициент сжатия
a.txt
a.txt.shf
a.txt.shf2
a.txt.shf3
a.txt.shf4
a.txt.shf5
a.txt.shf6

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

Ответ:

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

	Размер файла	Предельный коэффициент сжатия
RLE
Хаффман
Шеннон и Фано
ZIP
RAR
7Z

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

Ответ:

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

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

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

Ответ:

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

Имя архива	Описание	Объем до сжатия, Кб	Объем после сжатия, Кб
tolstoy.7z	обычный архив	5379
tolstoy.exe	SFX-архив	5379

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

7. 
   Переместите рисунки в отдельный каталог Pictures, а звуковые файлы – в каталог Sounds.
   
8. 
   Упакуйте рисунки и звуки в архив Media с паролем media123.
   
9. 
   Упакуйте все остальные файлы и папки в архив Data (без пароля).
   
10. 
    Удалите все файлы, кроме архивов Media и Data, и покажите работу учителю.
    

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

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

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

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

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

Для 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
Объем файла, Кбайт

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

График:

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

Ответ:

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

Ответ:

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

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

Качество	1	2	3	4	5	6	7	8	9	10
Объем файла, Кбайт

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

Битрейт, Кбит/с	8	16	32	48	64	96	128
Объем файла, Кбайт

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

График:

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

Ответ:

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

Ответ:

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

http://kpolyakov.spb.ru