Реферат: Сжатие данных
массива могут содержать от 9 до 10 битов ( 2 байта на большинстве машин)(3).
Неизменные запросы памяти у алгоритма расширяемого префикса составляют
приблизительно 9.7К битов (2К байтов на большинстве машин). Подобный подход к
хранению массивов в Л-алгоритме требует около 57К битов (10К байтов на
большинстве машин ).
Другие широко применяемые алгоритмы сжатия требуют еще большего пространства,
например, Уэлч советует для реализации метода Зива-Лемпела использовать
хеш-таблицу из 4096 элементов по 20 битов каждый, что в итоге составляет уже82К
битов ( 12К байтов на большинстве машин ). Широко используемая команда сжатия в
системе ЮНИКС Беркли применяет код Зива-Лемпела, основанный на таблице в 64К
элементов по крайней мере в 24 бита каждый, что в итоге дает 1572К битов ( 196К
байтов на большинстве машин ).
В таблице I показано как Л-алгоритм Уиттера и алгоритм расширяющегося префикса
характеризуются на множестве разнообразных тестовых данных. Во всех случаях был
применен алфавит из 256 отдельных символов, расширенный дополнительным знаком
конца файла. Для всех файлов, результат работы Л-алгоритма находится в пределах
5% от H и обычно составляет 2% от H . Результат работы алгоритма расширяющегося
префикса никогда не превышает H больше, чем на 20%, а иногда бывает много меньше
H .
Тестовые данные включают программу на Си (файл 1), две программы на Паскале
(файлы 2 и 3) и произвольный текстовый файл (файл 4). Все текстовые файлы
используют множество символов кода ASCII с табуляцией, заменяющей группы из 8
пробелов в начале, и все пробелы в конце строк. Для всех этих файлов Лалгоритм
достигает результатов, составляющих примерно 60% от размеров исходного текста, а
алгоритм расширения - 70%. Это самый худший случай сжатия, наблюдаемый при
сравнении алгоритмов.
Два объектых файла М68000 были сжаты ( файлы 5 и 6 ) также хорошо, как и файлы
вывода TEX в формате .DVI ( файл 7 ). Они имеют меньшую избыточность, чем
текстовые файлы, и поэтому ни один метод сжатия не может сократить их размер