автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Анализ, классификация и моделирование алгоритмов сжатия

Введение.

Глава 1. Анализ теоретических и экспериментальных основ моделирования алгоритмов сжатия.

1.1. Задачи, для решения которых используется сжатие данных.

1./,. Анализ избыточности источников сообщений.

КЗ.Теоретические подходы к сжатию источников информации.

Моделирование и основные методы.

1.4. Анализ и обоснование критериев оценки эффективности алгоритмов сжатия Теоретические подходы к сжатию 52 источников информации.

1.5. Определение требований к критериям оценки АС.

1.6. Пример получения зависимости Td(Kc).

1.7. Модель разбиения пространства объектов по вектору признаков

Выводы по первой главе.

Глава 2. Оценка эффективности и классификация алгоритмов обратимого сжатия.

2.1. Обоснование новых критериев и классификация алгоритмов сжатия на основе файловых признаков.

2.2. Классификация алгоритмов сжатия по временным критериям

2.3. Оценка.сложности вектора признаков АС.

2.4. Анализ результатов классификации.

Выводы по второй главе. III

Глава 3.Моделирование алгоритма сжатия на основе выделения граничной точки.

3.1. Постановка общей задачи сжатия табличных данных.ИЗ

3.2. Оценка аппаратных затрат на реализацию сжатой таблицы.

3.3. Метод сжатия на основе выделения граничной точки.

3.4. Анализ функции F(x).

3.5. Нахождение граничной точки.

3.6. Избыточность множеств X, Y и формирование S и X.

3.7. Формирование множеств О и Y. ^

3.8. Нахождение граничных точек.

3.9. Определение нагрузки на разрядный вход регистра результата.

Периодичность узловых значений

3.10. Графическая интерпретация метода.

3.11. Выбор функциональной системы генератора функции /^(х)

Выводы по третьей главе.

Глава 4. Анализ результатов исследования и практические рекомендации.

4.1. Применение таблиц замены для разработки алгоритма обратимого сжатия данных.

4.2. Оценка эффективности нового алгоритма сжатия.

4.3. Уточнение функций классификаций.

Выводы по четвертой главе.

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

Большие объемы хранимой информации определяют задачи экономного расходования ресурсов ЭВМ, компактного представления данных на различных магнитных носителях, что, несомненно, вызывает потребность в поиске путей сокращения временных затрат на получение (извлечение) информации из сжатых структур. Временные показатели алгоритмов сжатия играют важную роль в системах реального масштаба времени, в рамках которых приходится решать задачи сжатия информации, где протекание процессов сжатия и восстановления исходных данных имею! ограничения по времени (например, в системах распознания летательных объектов «свой-чужой», управления движением самолетов при посадке и т.д).

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

Актуальность темы

Число алгоритмов обратимого сжатия продолжает с каждым годом расти. Здесь следует отметить работы Д.Хаффмана, К.Шеннона, Р.Фано, Б.Фитингофа, Ю.Штарькова, Р.Киричевского, Р.Галлагера, Л.Дэвисона, Т.Ковера, П.Элайеса, А.Лемпела, Д.Зива, Т.Белла, Я.Витенна, Д.Риссанена и др. М. Алгоритмы сжатия самые разнообразные, имеют различные характеристики сжатия. В качестве основной оценки используется классический подход - коэффициент сжатия (отношение исходного объема данных к объему сжатых данных УцСх ® практических целях другие параметры, такие как время сжатия и время восстановления (Гс,7^) указываются не всегда и авторы не придают им большого значения. Однако, на практике и, особенно, в системах реального времени большое значение придается таким параметра м как Тс, fy.

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

Требуется связать параметры коэффициента сжатия (Кс) с Данная необходимость возникает при решении многих технических задач, где за короткие промежутки времени требуется передавать большие объемы информации.

Например, известно что количество научных бортовых приборов, участвующих в эксперименте, а также vr: точность и разрешающая способность растут быстрее, нежели качество космических средств передачи данных. Поэтому актуальность задачи уменьшения объема информации в бортовой информационно-измерительной системе с расширением научных космических исследований все более и более возрастает, а сжатие информации и передача ее на Землю за короткие промежутки времени выдвигаются в ряд первоочередных проблем, требующих решения при организации космического эксперимента. Передача команд управления экспериментом и космическим аппаратом (КА) являются также существенным дополнением к общему объему передаваемой информации, требующей решения задач сжатия за короткие сроки (до попадания КА в "теневую зону").

Необходимость решения задач сжатия возникает и в системах распознавания "свой-чужой". Например, ракеты HARM применялись ВВС США в 1986 году против ливийских средств ПВО в заливе Сидра, а также авиацией союзников во время операции "Буря в пустыне" в 1991 году. Всего за время операции было выпущено 80 ракет по PJ1C ПВО Ирака. Несмотря на высокую эффективность ракеты HARM не могут считаться современным высокоточным оружием поскольку не имеют полноценной системы распознавания "свой-чужой".

В настоящее время разработано свыше 150 алгоритмов обратимого сжатия данных (АСОД), не имеется научно-обоснованной классификации, пригодной для их практического использования. Увеличивается число задач, для решения которых применяются АСОД. Оценка АС ведется по разным критериям, что затрудняет их соотнесение к научно-практическим задачам.

Целесообразно провести классификацию известных алгоритмов и свести их к небольшому количеству групп. Есгп для каждой группы создать свою представительную модель, го с их помощью можно оценивать (моделировать) возможность той или иной группы АС для использования в своей предметной области. В результате будут получены некоторые предварительные оценки по выбору той или иной группы АС.

После выбора представительной группы поиск "уточненного" АС будет упрощен за счет двух или трех проходов по уровням иерархии. Появляется возможность целенаправленного и быстрого поиска (выбора) алгоритма наиболее близкого по эффективности, по решению задачи сжатия в своей предметной области.

Указанная цель не является единственной. Классификация также позволяет решать следующий дополнительный ряд задач: а) получать некоторое множество интегральных критериев оценки АС, например, связать коэффициент сжатия и время сжатия (Кс с Тс или Кс с Т^), что имеет важность для практических задач, таких как распознавание образов в системах реального времени "свой-чужой" в войсках противовоздушной обороны, в навигационных системах, телеметрии и т.д.; б) "отсеивать" множество неэффективных и слабо эффективных алгоритмов сжатия, т. к. последние представляют собой некий "информационный мусор" (на практике их не используют); в) разрабатывать новые алгоритмы сжатия с учетом интегрированных критериев оценки АС и свойств "слабых" и "сильных" алгоритмов; г) разрабатывать тесты (группы тестовых файлов) отбора

АС.

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

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

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

Цель исследования

Целью работы является повышение эффективности создания и использова-ия средств сжатия данных и проектирования на их основе аппаратно-программных систем.

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

Для достижения поставленной цели выделяются две основные задачи.

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

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

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

В общем случае первая задача диссертационной работы может быть представлена следующим образом.

Пусть имеется конечное множество средств сжатия данных 5" ={5], под которыми понимается АС, и имеется конечное множество ресурсов Я = {г\,г2,0«}' которые принадлежат средствам СД

Пусть имеется конечное множество задач Z = 21-,. ¿у} с соответствующими параметрами Д., которые ре.даются с использованием средств СД - £

Требуется поставить в соответствие задаче у которой имеются параметры , средство сжатия данных так, чтобы эффективность решения задачи была не хуже некоторой величины цр е О, где О - множество оценок решений этой задачи с помощью остальных средств сжатия из множества 5, причем эта величина др была бы не хуже других оценок, в смысле некоторого заданного критерия решаемой задачи.

Таким образом, задачу требуется прорешать всеми известными приемами, используя ССД из множества сравнить решения по заданному критерию () и выбрать наилучшее.

В настоящее время насчитывается свыше полутора сотен алгоритмов сжатия данных, обладающих различными возможностями (ресурсами), имеются десятки задач, требующие для своего решения средства СД.

Для выполнения условий этой задачи необходим полный перебор решений всех вариантов. На практике это плохо осуществимо.

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

Вторая задача в общем виде формулируется следующим образом.

Имеется массив табличных данных Му, удовлетворяющий требованиям организации структуры таблицы и формата представления табличных данных. В массиве М-р имеется некоторый объем скрытой избыточности 1%. Требуется выполнить такое разбиение массива Мр, в результате которого удалось бы выявить избыточность и уменьшить ее, т.е.

1% —>■ min при этом обеспечить условие восстановления исходных табличных данных.

Решение обеих задач базируется на операции разбиения массивов: /.ля первой - массива алгоритмов сжатия, для второй - массива исходных данных, поэтому разбиение является общим основным подходом при исследовании и решении вопросов настоящей диссертационный работы.

Составными задачами работы являются:

1. Теоретический анализ современного состояния в области сжатия данных и обоснование основных задач исследований диссертационной работы.

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

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

4. Моделирование процесса классификации алгоритмов обратимого сжатия данных на основе научно-обоснованного набора информативных признаков с целью получения оптимального числа классов АОСД и подтверждение достоверности получаемых результатов.

5. Установление аналитических зависимостей между основными параметрами алгоритмов сжатия: коэффициентом сжатия, временем сжатия и временем восстановления.

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

Научная новизна работы

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

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

3. Разработан и исследован эффективный метод сжатия табличных данных, основанный на выделении граничной точки, для функциональных зависимостей вида у — Ъ/(ах + с), широко применяемых в системах навигации, радиолокации и т.д.

4. Разработан?, и исследована модель табличной системы воспроизведения функциональных зависимостей видд у — Ь/(ах + с) на основе разработанного метода сжатия (п.З), отличающаяся предельно высокой скоростью получения результатов, однородностью структуры, простотой реализации на типовых микросхемах памяти.

Практическая значимость результатов исследований

1. Свойства полученных классов алгоритмов обратимого сжатия данных, выраженные с помощью числовых характеристик основных параметров АС: коэффициента сжатия, времени сжатия, времени восстановления, позволяют соотнести алгоритмы сжатия с научно-практическими задачами, что упрощает процесс поиска необходимого средства сжатия данных. Классификация позволяет распознать свойства новых алгоритмов сжатия и отнести АС к соответствующему классу.

2. Разработанная модель табличной системы воспроизведения функциональной зависимости типа у — Ы(ах + с) может быть применена при построении систем управления в реальном масштабе времени посадкой летательных аппаратов, навигации, обработки радиолокационной информации и других аналогичных систем.

Положения, выносимые на защиту

1. С целью получения наиболее информативных признаков классификации АОСД необходимо выполнение процедур кластерного и факторного анализа признаков, что позволяет существенно сократить временные затраты на формирование признакового пространства.

2. Доказано, что для получения оптимального числа (трех) классов однородных алгоритмов обратимого сжатия данных необходимо проводить их классификацию либо по обоснованному минимальному набору наиболее информативных тестовых файлов {GEO, РОЕМ, FAX}, либо по обоснованному набору временных параметров алгоритмов сжатия

9С, »9^, Кс}.

3. Для выявления и уменьшения скрытой избыточности в табличных данных функциональных зависимостей вида у = Ь/(ах + с) требуется проводить разбиение интервала изменения аргумента в некоторой граничной точке, выделяющей класс избыточных данных.

4. Модель табличной системы, воспроизводящей сжатые табличные данные функциональных зависимостей вида у — Ы(ах + с), построенная на основе неравномерного разбиения и выделения граничной точки, позволяет получать результаты с предельной скоростью, близкой к времени выборки из памяти, строить однородные экономичные табличные системы на базе типовых микросхем.

Личный вклад автора в получение результатов, изложенных в диссертации: обоснование задач диссертации, постановка основных положений третьей главы разработано совместно с профессором A.A. Смагиным. Первая, вторая и четвертая главы, вывод аналитических выражений, проведение расчетов, компьютерное моделирование, анализ результатов выполнены автором самостоятельно.

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

Реализация, апробация, публикации

Результаты исследования использованы в двух научно-исследовательских работах, шифры "АСУ вуза", "Методы", проводимых 1997.2000 годах. Апробация результатов проведена в выступлениях и тезисах на конференциях профессорско-преподавательского состава УФВАТТ (г. Ульяновск, 1999 г., 2000 г.), научных конференциях УЛГУ (г. Ульяновск, 1998 г., 2000 г.), 3-ей Всероссийской научно-технической конференции "Методы и средства измерения физических величин" (г. Нижний Новгород, 1998 г.).

Основные положения диссертации опубликованы в пятнадцати печатных трудах. .

Результаты диссертационной работы используются в учебном процессе Ульяновского государственного университета при чтении курса лекций и проведении практических и лабораторных занятий по дисциплинам "Теория информации" и "Основы сетевых технологий" и Ульяновском филиале Военной академии тыла и транспорта при проведении лекционных и практических занятий с адъюнктами по дисциплине "Математическое моделирование".

Структура и объем диссертации

Диссертационная работа состоит из введения, четырех глав, общих выводов, библиографического списка используемой литературы, включающего 216 работ отечественных и зарубежных авторов, 12 приложений, включающих 33 таблицы, 20 графиков. Работа изложена на 17? листах текста, содержит 22 рисунка и 16 таблиц.

Основные результаты диссертационной работы заключа ются в следующем:

1. Проанализирован класс задач, решаемых с помощью алгоритмов сжатия, исследованы свойства известных алгорит мов сжатия, указано на недостаточность существующих оценок эффс.'ктивности алгоритмов сжатия.2. Разработана методика выделения из множества при знаков АС наиболее информативных, позволяющих уменьшить размерность признакового пространства, что в отличии от су ществующих методик отбора признаков сокращает время от бора и повышает его качество.3. Проведена научно-обоснованная классификация алго ритмов обратимого сжатия данных, определены три основных класса однородных АС, разработана методика отнесения алго ритмов сжатия к одному из классов, что позволяет на практике более качественно различать АС по временным параметрам.4. Выявлены основные закономерности каждого класса алгоритмов и их численные характеристики, установлены связи между основными параметрами - коэффициентом сжатия, вре менем восстановления и временем сжатия, что дает возмож ность каждому классу АС поставить в соответствие класс ре шаемых задач.5. Разработан новый эффективный способ сжатия таблиц функциональных зависимостей вида y = bf{ox+c), основанный на выделении граничной точки интервала изменения аргумен та, позволяющий выделить скрытую избыточность и осущест вить ее сокращение.6. Разработаны модели сжатых табличных структур реа лизации зависимости у = Ь({ах + с), которые отличаются про стотой формирования результата, однородностью структуры и возможностью реализации на типовых элем^ентах памяти. Реа лизация модели сжатой таблицы функции зависимости

у-Ь1{ах-\-с) дает возможность воспроизведения табличных данных с предельно высокой скоростью, равной времени об ращения к памяти, и с заданной точностью получения значе ний функции.7. Создан комплекс программ анализа, классификации, тестирования алгоритмов сжатия данных и моделирования спецпроцессора для вычисления значений функции y = bl{cix-\-c) на сжатых таблицах.