Синтетические алгоритмы

Алгоритм RLE

В основу положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой, в которой указывается код данных и коэффициент повтора.

Например, для последовательности:

0; 0; 0; 125;125; 0; 248; 248; 248; 248 (всего 10 байтов)

1 2 3 4 5 6 7 8 9 10

Выявляются: значение и коэффициент повтора.

0 3

125 2

0 1

248 4

Новый вектор данных имеет вид:

0; 3; 125; 2; 0; 1; 248; 4 (всего 8 байтов)

Коэффициент сжатия 8/10*100%=80%.

Алгоритм отличается простотой, высокой скоростью работы, но обеспечивает недостаточное сжатие.

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

Этот метод может дать заметный выигрыш на некоторых типах файлов баз данных. Имеющих таблицы с фиксированной длиной полей.

Для текстовых данных методы RLE неэффективны.

Алгоритм KWE

В основу положен принцип кодирования лексических единиц исходного документа группами байтов фиксированной длины.

Лексическая единица – последовательность символов, справа и слева ограниченная пробелами или символами конца абзаца.

Лексической единицей может быть слово.

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

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

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

Эффективность метода зависит от длины документа.

Из-за необходимости прикладывать к архиву словарь слов, длина кратких документов не только не уменьшается, но даже возрастает.

Алгоритм наиболее эффективен для англоязычных текстовых документов и файлов баз данных.

Алгоритм Хафмана

В основе алгоритма лежит кодирование не байтами, а битовыми группами.

Принцип кодирования:

· Перед началом кодирования производится частотный анализ кода документа с целью выявления частоты повтора каждого из встречающихся символов.

· Чем чаще встречается тот или иной символ, тем меньшим количеством битов он кодируется.

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

Соответственно, чем реже встречается символ, тем длиннее его кодовая битовая последовательность. Например:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

Используя 16 бит, можно закодировать до 256 различных символов. К сжатому архиву необходимо прикладывать таблицу соответствия, поэтому для файлов малых размеров алгоритм Хафмана малоэффективен.

Эффективность алгоритма зависит и от заданной предельной длины кода (размера словаря). Наиболее эффективными оказываются архивы с размером словаря от 512 до 1024 единиц.

Все рассмотренные алгоритмы в «чистом виде» на практике не применяются, т.к. эффект каждого из них сильно зависит от начальных условий.

Синтетические алгоритмы

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

Общим принципом в работе «синтетических» алгоритмов является предварительный просмотр и анализ исходных данных для индивидуальной настройки алгоритма на особенности обрабатываемого материала.

18.3 Программные средства сжатия данных

Для сжатия данных в файлах существуют специальные программы, называемые архиваторами. Эти программы сжимают файлы, значительно уменьшая их размер.

«Классическими» форматами сжатия данных, являются форматы *.ZIP, *.ARJ, *.RAR.

Операционная система	Формат сжатия	Средство архивации	Средство разархивации
MS-DOS	.ZIP	PKZIP.EXE	PKUNZIP.EXE
.ARJ	ARJ.EXE
.RAR	RAR.EXE	UNRAR.EXE
Windows	.RAR	WinRAR
.ZIP	WinZip
.ARJ	WinArj

Современные программные средства для создания и обслуживания архивов отличаются большим объёмом функциональных возможностей, многие из которых выходят за рамки простого сжатия данных и эффективно дополняют стандартные средства операционной системы. В этом смысле современные средства архивации данных называют диспетчерами архивов.