Моделі і алгоритми стиску даних в інформаційних системах

Abstract

Дисертація присвячена питанням розроблення засобів стиску даних в інформаційних системах. Запропоновані математичні моделі стали основою методу локальних зсувів для стиску інформа-ційних масивів. Розроблений метод локальних зсувів для стиску масивів двійкових даних дозволяє виділити надмірність статистичного і структурного роду і застосувати для її усунення відповідні методи кодування. Розроблені алгоритми кодування значно спрощують алгоритм стиску і відпо-відно підвищують його швидкодію. Синтезована структурна і функціональна схеми системи стиску можуть бути використані для апаратної реалізації розроблених алгоритмів. Це дає можливість їх використання в інформаційних системах реального часу. При цитуванні документа, використовуйте посилання http://essuir.sumdu.edu.ua/handle/123456789/3449

Диссертация посвящена разработке новых моделей, методов и алгоритмов сжатия данных в информационных системах. Результаты анализа современного состояния и тенденций развития информационных систем показали актуальность проблемы сжатия данных. Это позволяет значительно разгрузить каналы связи, системы обработки и хранения данных за счет исключения избыточных сообщений, что эквивалентно повышению пропускных способностей информационных систем или увеличению емкости запоминающих устройств. В работе обоснована целесообразность применения комбина-торных методов сжатия в АСУ, особенно для задач, когда неизвестны вероятностные характери-стики источника информации. Показано, что сжатие данных комбинаторными методами дает теоретически лучший результат, чем статистическими методами, оперирующими вероятностными свойствами источника информации. Предложен метод локальных сдвигов для сжатия массивов двоичных данных. Метод позволяет выделить из сжимаемых данных избыточность статистического и структурного рода и применить для ее устранения соответствующие методы кодирования. Метод использует бернуллиевскую мо-дель для описания исходных сообщений. Чтобы повысить адекватность описания данных моделью, возможно применение декорреляции как этапа предварительной обработки. Для сжатия использу-ется разложение бернуллиевского источника информации на два взаимосвязанных, раздельное кодирование которых позволяет устранить структурную и вероятностную избыточность исходных сообщений. Кроме того, раздельное кодирование источников информации дает возможность ис-пользовать модель для систем с защитой данных от несанкционированного доступа. Основной эффект сжатия достигается при кодировании комбинаторного источника информации, для описа-ния которого используется разработанная модель относительной адресации, позволяющая адек-ватно описывать последовательности в виде, удобном для их оптимального кодирования. Данная модель позволяет перейти от равновероятной комбинаторной модели источника двоичных после-довательностей к вероятностному источнику относительных адресов символов с детерминиро-ванным распределением вероятностей генерируемых значений. Это дает возможность эффективно применять алгоритмы ОНК для кодирования комбинаторного источника без ограничения на мощность его алфавита. Применение декорреляции является одним из методов предварительной обработки данных, позволяющих устранить или существенно ослабить взаимосвязи между эле-ментами сжимаемого массива. Она позволяет существенно повысить эффективность сжатия дан-ных на основе разработанных моделей. Разработанный алгоритм кодирования вероятностного источника относительных адресов не требует вычисления вероятностей значений кодируемых значений. Это значительно упрощает алгоритм сжатия и соответственно повышает его быстродействие. Алгоритм разработан на основе модификации известных методов ОНК и с учетом характерной для метода локальных сдвигов функциональной зависимости для вероятностей относительных адресов. В алгоритме используется комбинаторное разложение кодируемых адресов на классы эквивалентности. Генерируемый код является неравномерным, префиксным и оптимальным с точки зрения информационной нагрузки на каждый символ. Разработаны программы сжатия графических данных и двоичных последовательностей на основе метода локальных сдвигов. Использование этих программ позволило произвести экспери-ментальную оценку эффективности сжатия предложенным в работе методом. Разработанный пакет программ применяется в учебных целях в Сумском государственном университете по дисциплинам “Методы и средства сжатия данных в информационных системах”, “Системы передачи данных” для исследования методов обработки изображений, сжатия графических и нетипизированных данных. Проведенный анализ эффективности сжатия данных на основе разработанных моделей источников информационных массивов и алгоритмов их кодирования методом локальных сдвигов показал, что метод позволяет производить сжатие как типизированных, так и нетипизированных данных лучше, чем известные на сегодняшний день методы. Применение разработанных методов кодирования в сочетании с алгоритмом декорреляции позволило превзойти по степени сжатия специализированные алгоритмы, разработанные для сжатия графических данных. Синтезированы структурная и функциональная схемы системы сжатия, которые могут быть использованы для аппаратной реализации разработанных алгоритмов. Рассмотренные структурные и функциональные блоки можно построить с использованием ПЛИС. Кроме того, сами структуры кодирующих устройств обладают достаточной простотой и наглядностью. Надежность и быстро-действие таких устройств будут существенно выше, чем реализованной программной модели. Это дает возможность предполагать, что они могут быть использованы в информационных системах, работающих в реальном режиме времени. Результаты диссертационной работы в виде метода локальных сдвигов для сжатия данных с программной реализацией использованы в Научно-производственном коллективном предприятии “Преобразователь” (г. Сумы) в информационных каналах автоматизированной системы учета электроэнергии для промышленных предприятий. Благодаря использованию метода локальных сдвигов обеспечено хранение большего объема оперативных данных без изменения объема запоминающих устройств. При цитировании документа, используйте ссылку http://essuir.sumdu.edu.ua/handle/123456789/3449

The dissertation is devoted to questions of development of means of compression given in information systems. The offered mathematical models have formed the basis for a method of local shifts for com-pression of information files. The developed method of local shifts for compression of files of the binary data allows to allocate redundancy of a statistical and structural sort and to apply to its elimination the appropriate methods of coding. The developed algorithms of coding considerably simplify algorithm of compression and, accordingly, raises its speed. The synthesized structural and functional circuits of system of compression can be used for hardware realization of the developed algorithms. It enables their uses in information systems of real time. When you are citing the document, use the following link http://essuir.sumdu.edu.ua/handle/123456789/3449