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

Алгоритм RLE

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

Алгоритм KWE

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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