Реферат: Сжатие данных
служит помехой локально адаптированному поведению алгоритма расширяемого
префикса.
Оба алгоритма, Л- и расширяемого префикса, выполняются по времени прямо
пропорционально размеру выходного файла, и в обоих случаях, выход в наихудшем
варианте имеет длину O(H ), т.о. оба должны выполняться в худшем случае за время
O(H ). Постоянные коэффициенты отличаются, поскольку алгоритм расширяемого
префикса производит меньше работы на бит вывода, но в худшем случае производя на
выходе больше битов. Для 13 файлов, представленных в таблице I, Лалгоритм
выводит в среднем 2К битов в секунду, когда как алгоритм расширяемого префикса -
более 4К битов в секунду, т.о. второй алгоритм всегда намного быстрее. Эти
показатели были получены на рабочей станции М68000, серии 200 9836CU Хьюлет
Паккард, имеющей OC HP-UX. Оба алгоритма были реализованы на Паскале, сходным по
описанию с представленным здесь языком.
АРИФМЕТИЧЕСКИЕ КОДЫ.
Tекст, полученный при сжатии арифметических данных, рассматривается в качестве
дроби, где каждая буква в алфавите связывается с некоторым подинтервалом
открытого справа интервала [0,1). Текст источника можно рассматривать как
буквальное представление дроби, использующей систему исчисления, где каждая
буква в алфавите используется в качестве числа, а интервал значений, связанных с
ней зависит от частоты встречаемости этой буквы. Первая буква сжатого текста
(самая "значащая" цифра) может быть декодирована нахождением буквы, полуинтеpвал
которой включает значение пpедставляющей текст дроби. После определения
очередной буквы исходного текста, дробь пересчитывается для нахождения
следующей. Это осуществляется вычитанием из дроби основы связанной с найденной
буквой подобласти, и делением результата на ширину ее полуинтервала. После
завершения этой операции можно декодировать следующую букву.
В качестве примера арифметического кодирования рассмотрим алфавит из 4-х букв
(A, B, C, D) с вероятностями ( 0.125, 0.125, 0.25, 0.5 ). Интервал [ 0,1) может
быть разделен следующим образом: