Содержание к диссертации
Введение
Глава 1. Анализ теоретических и экспериментальных основ моделирования алгоритмов сжатия 12
1.1. Задачи, для решения которых используется сжатие данных 12
1.2. Анализ избыточности источников сообщений 19
1.3. Теорегаческие подходы к сжатию источников информации. Моделирование и основные методы 25
1.4. Анализ и обоснование критериев оценки эффективности алгоритмов сжатия Теоретические подходы к сжатию 52 источников информации
1.5. Определение требований к критериям оценки АС , 54
1.6. Пример получения зависимости Td(Kc) 57
1.7. Модель разбиения пространства объектов по вектору признаков 62
Выводы по первой главе 68
Глава 2 Оценка эффективности и классификация алгоритмов обратимого сжатия 69
2.1. Обоснование новых критериев и классификация алгоритмов сжатия на основе файловых признаков 69
2.2. Классификация алгоритмов сжатия по временным критериям 94
2.3. Оценка.сложности вектора признаков АС 102
2.4. Анализ результатов классификации 110
Выводы по второй главе - 111
Глава 3. Моделирование алгоритма сжатия на основе выделения граничной точки 113
3.1. Постановка общей задачи сжатия табличных данных 113
3.2. Оценка аппаратных затрат на реализацию сжатой таблицы 116
3.3. Метод сжатия на основе выделения граничной точки 117
3.4. Анализ функции F(x) - 118
3.5. Нахождение граничной точки 120
3.6. Избыточность множеств X, Y и формирование S и X 122
3.7. Формирование множеств О и Y 129
3.8. Нахождение граничных точек 132
3.9. Определение нагрузки на разрядный вход регистра результата. Периодичность узловых значений 139
3.10. Графическая интерпретация метода 141
3.11. Выбор функциональной системы генератора функции F(x) 145
Выводы по третьей главе 152
Глава 4. Анализ результатов исследования и практические рекомендации 153
4.1. Применение таблиц замены для разработки алгоритма обратимого сжатия данных 153
4.2. Оценка эффективности нового алгоритма сжатия 161
4.3. Уточнение функций классификаций 161
Выводы по четвертой главе 163
Заключение 165
Библиографический список использованной литературы 166
Приложения 178
- Теорегаческие подходы к сжатию источников информации. Моделирование и основные методы
- Классификация алгоритмов сжатия по временным критериям
- Метод сжатия на основе выделения граничной точки
- Применение таблиц замены для разработки алгоритма обратимого сжатия данных
Теорегаческие подходы к сжатию источников информации. Моделирование и основные методы
Существуют два основных способа проведения сжатия: статистический и словарный. Лучшие статистические методы
Одним из наиболее важных достижений в теории сжатия за последнее десятилетие явилась впервые высказанная в М идея разделения процесса сжатия на две части: на кодер, непо средственно производящий сжатый поток битов, и на моделирующее устройство (simulator), поставляющее ему информацию. Эти две раздельные части названы кодированием и моделированием. Моделирование присваивает вероятности символам, а кодирование переводит эти вероятности в последовательность битов.
Задачей моделирования является оценка вероятности для каждого символа. Из этих вероятностей может быть вычислена энтропия. Очень важно отметить, что энтропия есть свойство модели. Наилучшая средняя длина кода достигается моделями, в которых оценки вероятности как можно более точны. Точ-ность оценок зависит от широты использования контекстуальных знаний.
Модель по существу есть набор вероятностей распределения, по одному на каждый контекст, на основании которого символ может быть закодирован. Контексты называются классами условий, т.к. они определяют оценки вероятности. Нетривиальная модель может содержать тысячи классов условий.
В порядке функционального соответствия, декодер должен иметь доступ к той же модели, что и кодер. Длл достижения этого есть три способа моделирования: статичное, полуадаптированное и адаптированное.
Статичное моделирование использует для всех текстов одну и ту же модель. Она задается при запуске кодера, воз-можно на основании образцов типа ожидаемого текста Такая же копия модели хранится вместе с декодером. Недостаток состоит в том, что схема будет давать неограниченно плохое сжатие всякий раз, когда кодируемый текст не вписывается в выбранную модель, поэтому статичное моделирование используют только тогда когда важны в первую очередь скорость и простота реализации.
Полуадаптированное моделирование решает эту проблему, используя для каждого текста свою модель, которая строится еще до самого сжатия на основании результатов предва-рительного просмотра текста (или его образца). Перед тем, как окончено формирование сжатого текста, модель должна быть передана декодеру. Несмотря на дополнительные затраты по передаче модели эта стратегия в общем случае окупается благодаря лучшему соответствию модели тексту
Адаптированное моделирование уходит от связанных с этой передачей расходов. Первоначально и кодер, и декодер присваивают себе некоторую пустую модель, как ссли бы символы все были равновероятными. Кодер использует эту модель для сжатия очередного символа, а декодер - для его восстановления. Затем они оба изменяют свои модели одинаковым образом (например, аккумулируя вероятность рассматривае-мого символа). Следующий символ кодируется и достается на основании новой модели, а затем снова изменяв модель. Кодирование продолжается аналогичным декодированию образом, которое поддерживает идентичную модель за счет приме-нения такого же алгоритма ее изменения обеспеченным отсутствием ошибок во время кодирования. Используемая модель, которую к тому же не нужно передавать явно, будет хорошо соответствовать сжатому тексту.
Адаптированные модели представляют собой эффективную технику и обеспечивают сжатие, по крайней мере, не худшее производимого неадаптированными схемами. Оно может быть значительно лучше, чем у плохо соответствующих тек-стам статичных моделей М. Адаптиировнные модели втличии от полуадаптированных, не производят их предварительного просмотра являясь поэтому лучше сжимающими Таким образом, описываемые алгоритмы моделей при кодировании и декодировании будут выполнятся одинаково Модель никогда не передается явно поэтому сбой происходит только в случае нехватки под не е памяти. /
Важно, чтобы значения вероятностей, присваемых моделью не были бы равны О, т.к. если символы кодируются (-logp) битами, то при близости вероятности к О, длина кода стремится к бесконечности. Нулевая вероятность имеет место, если в образце текста символ не встретился ни разу - частая ситуация для адаптированных моделей на начальной стадии сжатия, Она известна как проблема нулевой вероятности, которую можно решить несколькими способами. Один подход состоит в том, чтобы добавлять 1 к счетчику каждого символа іт.ші. Альтернативные подходы в основном основаны на идее выделенил одного счетчика для всех новых (с нулевой частотой) символов! для последующего использования его значения между ними №т/ Срранени, етии хтрратеий ммжет тытт ьайденн в mm Оно показывает что ни один метод не имеет впечатляющего преимущества над другими хотя метод выбранный в ет хорошие oZne характеристики
Классификация алгоритмов сжатия по временным критериям
Ежегодно в информационных системах каждой предметной области возрастают объемы хранимой и передаваемой информации, все острее встает задача по экономному расходованию ресурсов ЭВМ информационных систем, компактного представления данных на различных магнитных носителях, что, несомненно, вызывает потребность в поиске путей сокращения временных затрат на получение (извлечение) информации из сжатых представлений. Ясно, что для решения подоб-ных задач необходимы АС, характеризующиеся высокими значениями коэффициентов сжатия и наименьшим - временем восстановления (сжатия) информации. Времени» параметры АС играют важную роль в вопросах распознавания образов (например, в системах распознавания летательных объектов «свой-чужой»), решение которых, определенным образом, может влиять на степень боевой готовности средств ПВО страны, Поэтому необходимы критерии оценки эффективности АС, позволяющие выделить среди большого множества алгоритмов наиболее оптимальные по временным параметрам.
Проведенные исследования в рамках настоящей работы позволили установить, что существующие критерии оценки временных затрат на процесс сжатия информации (время сжатия и время восстановления) не позволяют оценить преимущества и недостатки имеющихся алгоритмов обратимого сжатия. Причем анализ научных источников показал что взаимосвязь между коэффициентом сжатия и временными показателями ра-нее не рассматривалась. Мало того, налицо имеется противоречие: с одной стороны, возможно построение регрессионных моделей взаимосвязи указанных критериев, т.к имеется корреляционная связь между коэффициентом сжатия и временем сжатия; с другой стороны получаемая модель не может быть адекватной и использована на практике в вопросах прогнозирования так как она строится на базе неоднородной выборки алгоритмов обратимого сжатия Таким образом необходимо решать адачу разбиения исходной выборки АС на однородные причем признаковклассификации должен быть один из временных параметров
Проведенные в ходе исследования эксперименты показали, что АС не могут быть разбиты (классифицированы) на однородные классы по существующим временным параметрам, т.к у последних наблюдается корреляционная связь с коэффициентом сжатия, что, в свою очередь, вызывает уменьшение значений межгрупповой дисперсии, приводит к сближению кластеров, к и?, «слиянию» (см. приложение 2). Таким образом, необходим поиск таких критериев, которые позволили бы классифицировать существующие АС по временным при знакам, а затем в каждом полученном классе алгоритмов обратимого сжатия установить наличие связи между коэффициентом сжати» и временными показателями и определить вид ее модели.
С целью доказательства справедливости получеггиых результатов классификации алгоритмов сжатия (см. п. 1Л.) по файловым признакам необходимо провести контрольные эксперименты. В связи с этим предлагается провести дополни тельную классификацию по набору других временных признаков, которые часто используются при решении научно-практических задач.
Поиск необходимых признаков включил в себя несколько этапов исследования рассматриваемого вопроса. Рассмотрим каждый из них. Этап L Создание исходной матрицы АС,
На данном этапе формировалась матрица из существую-щих алгоритмов обратимого сжатия (см. приложение 3). В ка-честве признаков были определены следующие параметры: / -коэффициент сжатия; Тс- время сжатия (компрессии) исходного файла, с; Td- время восстановления (декомпрессии), с; . Ус- объем (размер) исходного файла после сжатия, байт. Этап 2. Увеличение размерности исходной матрицы, Исходная матрица была дополнена новыми временными признаками, связанными со значениями Тс и Td, для определения которых применялись следующие приемы: Примечание. Признаки Ц...Т6 были определены с целью получения временных критериев оценки относительного времени протекания процессов сжатия и восстановления, независящих от конфигурации ЭВМ (например, от модели процессора зависит тактовая частота, которая влияет на временные параметры при небольших объемах исходного файла). Для оценивания временных параметров АС были определены так:ке следующие признаки: где $с- относительная скорость процесса сжатия, байт/с; -относительная скорость процесса декомпрессии, байт/с; АV- изменение размера исходного файла (AF = Vinp-Vc), байт; Vinp- размер исходного файла до сжатия, байт; &cd относительная скорость процесса сжатия-декомпрессии, байт/с. Этап 3. Изучение свойств признаков и их выбор. На этом этапе проводилась классификация методом кластерного анализа (методом к- средних) с целью получения средних значений признаков для каждого кластера (см. рис. 15).
Метод сжатия на основе выделения граничной точки
Кратко охарактеризуем перечисленные выше задачи. 1. Определение правила сжатия. На множестве исходных данных необходимо построиТЬ такое фактормножество, в котором было ёы наименьшее количество классов эквивалентно-сти, покрывающих все исходные данные, причем для упрощения переадресовки количество элементов в классах эквивалентности должно быть кратным целой степени двойки. Построение фактормножества опирается на равномерное и не-равномерное разбиения исходного множества данных, на результаты исследования свойств данных внутри разбиений, на оптимизацию количества разбиений, на возможность уменьшения длины слов внутри разбиений. Основным требованием к построению фактормножества является меньшая сложность формы представления сжатой таблицы по сравнению со сложностью исходной таблицы.
2. Определение правила перекодировки. Здесь на множе-стве имен-аргументов создается фактормножество, соответствующее фактормножеству, полученному на исходном множестве табличных данных. Далее требуется решать задачу логического преобразования группы имен-аргументов, относящихся к классу эквивалентности соответствующих табличных данных с целью получения имени группы. Основной трудностью является определение имени группы для случаев: 1) когда ко-личество элементов в классах эквивалентности нечетное. Главная цель задачи переадресовки - достижение минималь-ной сложности описания закона функционирования схемы переадресовки
3. Определение правила поиска. Важными этапами этой задачи является организация размещения сжатой таблицы в памяти и поиск данных по именам, получаемым после переадресовки. Задача размещения и поиска данных здесь связывается с разработкой моделей памяти, основанных на равномерном и неравномерных разбиениях пространства адресов. Основное требование - уменьшение времени получения данных из сжатой таблицы.
4. Определение вида операции восстановления. Необходимо найти такую операцию w, которая обеспечивала бы минимальное время восстановления данного и небольшую точ-ность воспроизведения данных и имела бы наименьшую сложность по сравнению с другими операциями. Решение этой задачи базируется на Р1следовании свойств зависимости y = f(x), реализуемой с помощью таблшш.
В 1,4 были рассмотрены различные подходы к сжатию таблиц; с точки зрения поиска данных в сжатых таблицах разобьем эти подходы на два класса: 1) класс, в котором поиск основан на переадресовке; 2) класс, в котором проводится по-иск с восстановлением. Для методов первого класса оставший-ся после сжатия массив данных переадресуется; для этих целей вводится специальная схема, которая по заданному адресу отыскивает соответствующее ему табличное данное. Для вто-рого класса методов сначала по исходному адресу осуществляется поиск в сжатых таблицах, и только после этого выполняется восстановление исходного данного. Здесь под восстановлением понимается процесс аппаратного вычисления искомого данного посредством использования некоторой математической операции над табличными данными, выбираемыми по заданному адресу Поиск с восстановчением может вносить погрешность в получаемый результат/
Для методов обоих классов нужно вводить дополнительные схемы, причем аппаратные затраты на эти схемы могут быть сравнимы с получаемой экономией памяти.
В самом общем случае объем оборудования на хранение (V#), поиск и восстапоБление {W on) данных МожнО выразить как причем аппаратные затраты на память Логут определяться количеством слов (ячеек памяти) или бит; аппаратные затраты на дополнительное оборудование можно оценивать другой универсальной мерой - количеством вентилей. В связи с этим необходимо найти меру оценки аппаоатных затрат такую, чтобы один параметр можно было выразить посредством другого т.е. найти соответствие между количеством вентилей и количеством бит. Иначе говоря, нужно ввести коэффициент пересчета {Кп), с помощью которого биты можно нересчитать в вентили и обратно. Так как ПСТ состоит в основном из модулей памяти, то измерения в бит являются преобладающими, Введетше коэффициеита пересчета К„) вентилей в бит позволяет ПРОВОДИТЬ косвенную опенку дополнительного обооудо мивбитВсв и тем что объем составZZl ntlw для систем памяти с ра личной организац меняйся в дальнейшем будем затрат для этих систем раздельно
Предлагаемый метод представляет интерес по ряду сле дующих причин: 1) учет симметрии узловых значений мно жеств адресов и табличных значений относительно некоторой граничной точки дает возможность существенного изменения избыточности, т.е. проведения сжатия данных; 2) воспроизведение функциональной зависимости производится путем суперпозиции двух функций за минимально возможное время; 3) метод в основном охватывает класс функций F(x) = a/(bx+c), которые широко применяются при моделировании сигналов в радиотехнических системах; 4) исследование сжатия таблиць, функции Чх дает дополнительные знания о величинеизбыточности в этой таблице, что позволяет осуществлять ее сравнение с величиной избыточности, выявляемой и устраняемой другими методами сжатия; 5) используется комбинирование равномерного и неравномерного разбиений входного кода.
Применение таблиц замены для разработки алгоритма обратимого сжатия данных
Сначала, из W4 можно определить, что частоты символов s\, 52 53 О 1 в правых столбцам будут равны 2 2 I2 3 соответ-ственно, из которых подсчитываете, тип (І, I,О,2,3)). В за-ключении, из us, не данной здесь, декодер определяет, какие символы заполняют семь пустых позиций. (Из типа (1,1,0,2,3) декодер определяет порядок кодирования М5.) Определим понятия кода источника без потерь, кода ие-рархического источника без потерь, кода последовательного источника с целью сравнения их в дальнейшем. Коды источника без потерь. Введем некоторые обозначения. Если п - положительное целое число, то у/п - {єп, 6п) -код источника /7-го порядка без потерь есть пара, в которой: 1) єп - взаимно однозначное отображение из Лп на префиксное подмножество {0,1} ; 2) #„=„- - обратное отображение е„. Представляя код (є„, 8п) источника «-го порядка без потерь, отображение єп назовем-кодером, отображение 6п - деко-дером Последовательность w-(W «-\ 2 ) в котоРОЙ ш„ -код источника «-ого порядка без потерь "для каждого « в дальнейшем будем называть алгоритмом обратимого сжатия данных, Если i{/=(y/n:n=1,2,...) есть алгоритм сжатия данных и х - непустая строка в А\ то пусть L(y/, х)- длина кодового сслва, которым тгкодер х кодирует X. Коды иерархического источника без потерь. Определено ранее, что таблица тєТсап имеет наименьшую сложность, если не одно из пяти правил сокращения № нн ерименимм о г. Пусть п будет положительным числом {п 2). Для каждой строки данных хєА" пусть тх будет такая таблица замены (тхєТсап) уменьшающая любую сложность, что тх- х. Тогда, мы можем определить отображение є» на Ап как следующее: Результирующая пара (єп, пх) кодера-декодера определяет код у/п источника п-го порядка без потерь. Множество всЄХ у/п, формируемое ЭТИМ СПОСОбом будет ОТМечатЬСЯ Г„(иее). Дескриптор «иер» указывает на принадлежность каждого кода источника без потерь (код иерархической структуры) множеству Fn- Элементами Уп („ep) будут и-элементные коды иерархического источника и-порядка без потерь. Более того, алгоритм обратимого сжатия данных w-( wn n-\ 2 ) будет назы-ваться иерархическим алгоритмом обратимого сжатия, если у„е!Рп(„ер) Для каждого п 2. Для того, чтобы разработать код („, єп- ), принадлежащий множеству „(иир), необходимо только выбрать таблицу замены {тх:хєАп}, удовлетворяющую равенство Щ). Каждая тх может быть сформирована, начиная с произвольной (исходной) таблицы, представляющей строку данных х, которую применением пяти правил сокращения пре образуют в таблицу наименьшей сложности /Ш/. Таблица наи меньшей сложности формируется за конечное число шагов со кращений. Например, если начать с исходной таблицы замены, состоящей из одного единственного ряда (so, х), то начальное значение функции сложности эквивалентно (2/?-1), следова тельно в этом случае необходимо (2п-2) шагов сокращений чтобы достигнуть таблицы наименьшей сложности. , Коды последовательного источника без потерь.
Одна из целей данной работы - сравнить производительность кодов иерархического источника и-го порядка без потерь с производительностью кодов последовательного источника w-огo порядка при длине данных п— оо. Пусть подмножество Ua А будет полным префиксным множеством и для каждой бесконечной последовательности (Хь Х2,...) символов из А существует такое и, что (Х], 2,..., х„)EU. Определим код последовательного источника без потерь набором из пяти элементов (пятимерный кортеж) (N,U,t(p,a ), в котором: 1) N- положительное целое число; 2) [/={/,-:/=1,2,..., N}, где каждое Ut - конечное полное префиксное подмножество из А ; 3) Є {ЄІ:І=\,2,.,., N\, где каждое , - точное отображение U, на префиксное подмножество {0,1} ; 4) р - отображение из множества {(/,w):/e{1,2,..., N} UeUi) на множество {1,2,...,7V} ; 5) я - элемент из А. Давая пятимерный кортеж {N,U,e, p,a), удовлетворяющий 1)...5), код источника /7-го порядка без потерь порожден для каждого п \. Фиксируем п и описываем код (є„, ,""), порождаемый источником «-го порядка без потерь. Этого достаточно, чтобы определить порядок работы кодера є. В завершении, фиксируем хєА". Пусть Сбудет такой бес конечной последовательностью {хьх2,х3)), что x = (xhx2,x3,....xn) и Xj = a для ясех х я. Тогдд можно огенерировать последовательность строк (щ,иъ...) и такую последовательность положительных целых чисел (іі,Ь»)» что имеет место выполнение следующих условий: 1) последовательность имеет место тогда, когда (щ,и2,...) конкатенированы в указанном порядке; Пусть у будет таким положительным целым, что х является префиксом из (uhu2,..Mj). Тогда JC кодируется в кодовое слово Определенный код (є„. Єп1) источника без потерь будем называть кодом источника и-го порядка без потерь, порожденным пятеркой (N U є Ф а ) Пусть s - положительное целое Кол w источника и-го порядка без потерь будет называться
Похожие диссертации на Анализ, классификация и моделирование алгоритмов сжатия
