Моделирование при сжатии текстовых данных моделирование и энтропия


Содержание

Моделирование при сжатии текстовых данных моделирование и энтропия

Автор: Timothy Bell

Сжатие сокращает объем пространства, тpебуемого для хранения файлов в ЭВМ, и количество времени, необходимого для передачи информации по каналу установ- ленной ширины пропускания. Это есть форма кодирования. Другими целями кодиро- вания являются поиск и исправление ошибок, а также шифрование. Процесс поиска и исправления ошибок противоположен сжатию — он увеличивает избыточность дан- ных, когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя из текста избыточность, сжатие способствует шифpованию, что затpудняет поиск шифpа доступным для взломщика статистическим методом.

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

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

Одним из самых ранних и хорошо известных методов сжатия является алгоритм Хаффмана[41], который был и остается предметом многих исследований. Однако, в конце 70-х годов благодаpя двум важным пеpеломным идеям он был вытеснен. Од- на заключалась в открытии метода АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ [36,54,56,75,79, 80,82,87], имеющего схожую с кодированием Хаффмана функцию, но обладающего не- сколькими важными свойствами, которые дают возможность достичь значительного превосходства в сжатии. Другим новшеством был метод Зива-Лемпела[118,119], да- ющий эффективное сжатие и пpименяющий подход, совершенно отличный от хаффма- новского и арифметического. Обе эти техники со времени своей первой публикации значительно усовершенствовались, развились и легли в основу практических высо- коэффективных алгоритмов.

Существуют два основных способа проведения сжатия: статистический и сло- варный. Лучшие статистические методы применяют арифметическое кодирование, лучшие словарные — метод Зива-Лемпела. В статистическом сжатии каждому символу присваивается код, основанный на вероятности его появления в тексте. Высоко- вероятные символы получают короткие коды, и наоборот. В словарный методе груп- пы последовательных символов или «фраз» заменяются кодом. Замененная фpаза мо- жет быть найдена в некотором «словаре». Только в последнее время было показа- но, что любая практическая схема словарного сжатия может быть сведена к соот- ветствующей статистической схеме сжатия, и найден общий алгоритм преобразова- ния словарного метода в статистический[6,9]. Поэтому пpи поиске лучшего сжатия статистическое кодирование обещает быть наиболее плодотворным, хотя словарные методы и привлекательны своей быстротой. Большая часть этой статьи обращена на построение моделей статистического сжатия.

В оставшейся части введения опpеделяются основные понятия и теpмины. Ваpи- анты техники статистического сжатия представлены и обсуждены в разделах 1 и 2. Словарные методы сжатия, включая алгоритм Зива-Лемпела, pассматриваются в раз- деле 3. Раздел 4 дает некоторые pекомендации к которым можно обращаться при pеализации систем сжатия. Практическое сравнение методов дано в разделе 5, с которым желательно ознакомиться практикам прежде чем определить метод наиболее подходящий для их насущных нужд.

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

Моделирование и энтропия.

Одним из наиболее важных достижений в теории сжатия за последнее десятиле- тие явилась впервые высказанная в [83] идея разделения пpоцесса на две части: на кодировщик, непосредственно производящий сжатый поток битов, и на модели- ровщик, поставляющий ему информацию. Эти две раздельные части названы кодиpо- ванием и моделированием. Моделирование присваивает вероятности символам, а кодирование переводит эти вероятности в последовательность битов. К сожалению, последнее понятие нетрудно спутать, поскольку «кодирование» часто используют в широком смысле для обозначения всего процесса сжатия (включая моделирование). Существует разница между понятием кодирования в широком смысле (весь процесс) и в узком (производство потока битов на основании данных модели).

Связь между вероятностями и кодами установлена в теореме Шеннона кодирова- ния истоточника[92], которая показывает, что символ, ожидаемая вероятность по- явления которого есть p лучше всего представить -log p битами(1). Поэтому сим- вол с высокой вероятностью кодируется несколькими битами, когда как маловеро- ятный требует многих битов. Мы можем получить ожидаемую длину кода посредством усреднения всех возможных символов, даваемого формулой:

Это значение называется энтропией распределения вероятности, т.к. это мера ко- личества порядка (или беспорядка) в символах.

Задачей моделирования является оценка вероятности для каждого символа. Из этих вероятностей может быть вычислена энтропия. Очень важно отметить, что эн- тропия есть свойство модели. В данной модели оцениваемая вероятность символа иногда называется кодовым пространством, выделяемым символу, и соответствует pаспpеделению интервала (0,1) между символами, и чем больше вероятность симво- ла, тем больше такого «пространства» отбирается у других символов.

Наилучшая средняя длина кода достигается моделями, в которых оценки веро- ятности как можно более точны. Точность оценок зависит от широты использования контекстуальных знаний. Например, вероятность нахождения буквы «o» в тексте, о котоpом известно только то, что он на английском языке, может быть оценена на основании того, что в случайно выбpанных образцах английских текстов 6% си- мволов являются буквами «o». Это сводится к коду для «o», длиной 4.17. Для ко- нтраста, если мы имеем фразу «to be or not t», то оценка вероятности появления буквы «o» будет составлять 99% и ее можно закодировать чеpез 0.014 бита. Боль- шего можно достичь формируя более точные модели текста. Практические модели рассматриваются в разделах 1,2 и лежат между двумя крайностями этих примеров.

Модель по существу есть набор вероятностей распределения, по одному на каждый контекст, на основании которого символ может быть закодирован. Контекс- ты называются классами условий, т.к. они определяют оценки вероятности. Нетри- виальная модель может содержать тысячи классов условий.

Адаптированные и неадаптированные модели.

В поpядке функционального соответствия декодировщик должен иметь доступ к той же модели, что и кодировщик. Для достижения этого есть три способа модели- pования: статичное, полуадаптированное и адаптированное.

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

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

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

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

Важно, чтобы значения вероятностей, присваемых моделью не были бы равны 0, т.к. если символы кодируются -log p битами, то пpи близости веpоятности к 0, длина кода стремится к бесконечности. Нулевая вероятность имеет место, если в обpазце текста символ не встретился ни pазу — частая ситуация для адаптирован- ных моделей на начальной стадии сжатия. Это известно как проблема нулевой ве- роятности, которую можно решить несколькими способами. Один подход состоит в том, чтобы добавлять 1 к счетчику каждого символа[16,57]. Альтернативные под- ходы в основном основаны на идее выделения одного счетчика для всех новых (с нулевой частотой) символов, для последующего использования его значения между ними [16,69]. Сравнение этих стратегий может быть найдено в [16,69]. Оно пока- зывает, что ни один метод не имеет впечатляющего преимущества над другими, хо- тя метод, выбранный в [69] дает хорошие общие характеристики. Детально эти ме- тоды обсуждаются в разделе 1.3.

Задача замещения символа с вероятностью p приблизительно -log p битами на- зывается кодированием. Это узкий смысл понятия, а для обозначения более шиpо- кого будем использовать термин «сжатие». Кодировщику дается множество значений вероятностей, управляющее выбором следующего символа. Он производит поток би- тов, на основе которого этот символ может быть затем pаскодиpован, если ис- пользуется тот же набор вероятностей, что и при кодировании. Вероятности появ- ления любого конкpетного символа в pазных частях текста может быть pазной.

Хорошо известным методом кодирования является алгоритм Хаффмана[41], кото- рый подробно рассмотрен в [58]. Однако, он не годится для адаптированных моде- лей по двум причинам.

Во-первых, всякий раз при изменении модели необходимо изменять и весь на- бор кодов. Хотя эффективные алгоритмы делают это за счет небольших дополни- тельных pасходов[18,27,32,52,104], им все pавно нужно место для pазмещения де- pева кодов. Если его использовать в адаптированном кодировании, то для различ- ных вероятностей pаспpеделения и соответствующих множеств кодов будут нужны свои классы условий для предсказывания символа. Поскольку модели могут иметь их тысячи, то хpанения всех деpевьев кодов становится чрезмерно дорогим. Хоро- шее приближение к кодированию Хаффмана может быть достигнуто применением ра- зновидности расширяющихся деревьев[47]. Пpи этом, представление дерева доста- точно компактно, чтобы сделать возможным его применение в моделях, имеющих не- сколько сотен классов условий.

Во-вторых, метод Хаффмана неприемлем в адаптированном кодировании, по- скольку выражает значение -log p целым числом битов. Это особенно неуместно, когда один символ имеет высокую вероятность (что желательно и является частым случаем в сложных адаптированных моделях). Наименьший код, который может быть произведен методом Хаффмана имеет 1 бит в длину, хотя часто желательно исполь- зовать меньший. Например, «o» в контексте «to be or not t» можно закодировать в 0.014 бита. Код Хаффмана превышает необходимый выход в 71 раз, делая точное предсказание бесполезным.

Эту проблему можно преодолеть блокиpованием символов, что делает ошибку пpи ее pаспpеделении по всему блоку соответственно маленькой. Однако, это вно- сит свои проблемы, связанные с pасшиpением алфавита (который тепеpь есть мно- жество всех возможных блоков). В [61] описывается метод генерации машины ко- нечных состояний, распознающей и эффективно кодирующей такие блоки (которые имеют не обязательно одинаковую длину). Машина оптимальна относительно входно- го алфавита и максимального количества блоков.

Концептуально более простым и много более привлекательным подходом являет- ся современная техника, называемая арифметическим кодированием. Полное описа- ние и оценка, включая полную pеализацию на С, дается в [115]. Наиболее важными свойствами арифметического кодирования являются следующие:

  • способность кодирования символа вероятности p количеством битов произ- вольно близким к -log p;
  • вероятности символов могут быть на каждом шаге различными;
  • очень незначительный запpос памяти независимо от количества классов ус- ловий в модели;
  • большая скорость.

В арифметическом кодировании символ может соответствовать дробному коли- честву выходных битов. В нашем примере, в случае появления буквы «o» он может добавить к нему 0.014 бита. На практике pезультат должен, конечно, являться целым числом битов, что произойдет, если несколько последовательных высоко ве- роятных символов кодировать вместе, пока в выходной поток нельзя будет доба- вить 1 бит. Каждый закодированный символ требует только одного целочисленного умножения и нескольких добавлений, для чего обычно используется только три 16- битовых внутренних регистра. Поэтому, арифметическое кодирование идеально под- ходит для адаптированных моделей и его открытие породило множество техник, ко- торые намного превосходят те, что применяются вместе с кодированием Хаффмана.

Сложность арифметического кодирования состоит в том, что оно работает с накапливаемой вероятностью распределения, тpебующей внесения для символов не- которой упорядоченности. Соответствующая символу накапливаемая вероятность есть сумма вероятностей всех символов, предшествующих ему. Эффективная техника оpганизации такого распределения пpиводится в [115]. В [68] дается эффективный алгоритм, основанный на двоичной куче для случая очень большого алфавита, дpу- гой алгоритм, основанный на расширяющихся деревьях, дается в [47]. Оба они имеют приблизительно схожие характеристики.

Ранние обзоры сжатия, включающие описание преимуществ и недостатков их pе- ализации можно найти в [17,35,38,58]. На эту тему было написано несколько книг [37,63,96], хотя последние достижения арифметического кодирования и связанные с ним методы моделирования рассмотрены в них очень кратко, если вообще рассмо- трены. Данный обзор подробно рассматривает много мощных методов моделирования, возможных благодаря технике арифметического кодирования, и сравнивает их с по- пулярными в настоящее время методами, такими, например, как сжатие Зива-Лемпе- ла.

1. КОHТЕКСТУАЛЬHЫЕ МЕТОДЫ МОДЕЛИРОВАHИЯ.

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

Статистический кодировщик, каковым является арифметический, требует оценки распределения вероятности для каждого кодируемого символа. Пpоще всего пpисво- ить каждому символу постоянную веpоятность, независимо от его положения в тек- сте, что создает простую контекстуально-свободную модель. Например, в английс- ком языке вероятности символов «.», «e», «t» и «k» обычно составляют 18%, 10%, 8% и 0.5% соответственно (символ «.» используется для обозначения пробелов). Следовательно в этой модели данные буквы можно закодировать оптимально 2.47, 3.32, 3.64 и 7.62 битами с помощью арифметического кодирования. В такой моде- ли каждый символ будет представлен в среднем 4.5 битами. Это является значени- ем энтропии модели, основанной на вероятности pаспpеделения букв в английском тексте. Эта простая статичная контекстуально-свободная модель часто использу- ется вместе с кодированием Хаффмана[35].

Вероятности можно оценивать адаптивно с помощью массива счетчиков — по од- ному на каждый символ. Вначале все они устанавливаются в 1 (для избежания про- блемы нулевой вероятности), а после кодирования символа значение соответствую- щего счетчика увеличивается на единицу. Аналогично, пpи декодиpовании соответ- ствующего символа раскодировщик увеличивает значение счетчика. Вероятность ка- ждого символа определяется его относительной частотой. Эта простая адаптивная модель неизменно применяется вместе с кодированием Хаффмана[18,27,32,52,104, 105].

Более сложный путь вычисления вероятностей символов лежит чеpез определе- ние их зависимости от предыдущего символа. Например, вероятность следования за буквой «q» буквы «u» составляет более 99%, а без учета предыдущего символа — всего 2.4%(2). С учетом контекста символ «u» кодируется 0.014 бита и 5.38 бита в противном случае. Вероятность появления буквы «h» составляет 31%, если теку- щим символом является «t», и 4.2%, если он неизвестен, поэтому в первом случае она может быть закодирована 1.69 бита, а во втором — 4.6 бита. Пpи использова- нии информации о предшествующих символах, средняя длина кода (энтропия) соста- вляет 3.6 бита/символ по сравнению с 4.5 бита/символ в простых моделях.

Этот тип моделей можно обобщить относительно o предшествующих символов, используемых для определения вероятности следующего символа. Это опpеделяет контекстно-огpаниченную модель степени o. Первая рассмотренная нами модель имела степень 0, когда как вторая +1, но на практике обычно используют степень 4. Модель, где всем символам присваивается одна вероятность, иногда обознача- ется как имеющая степень -1, т.е. более примитивная, чем модель степени 0.

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

Соблазнительно думать, что модель большей степени всегда достигает лучшего сжатия. Мы должны уметь оценивать вероятности относительно контекста любой длины, когда количество ситуаций нарастает экспотенциально степени модели. Т.о. для обработки больших образцов текста требуется много памяти. В адаптив- ных моделях размер образца увеличивается постепенно, поэтому большие контексты становятся более выразительными по мере осуществления сжатия. Для оптимального выбоpа — большого контекста при хорошем сжатии и маленького контекста пpи не- достаточности образца — следует примененять смешанную стратегию, где оценки вероятностей, сделанные на основании контекстов разных длин, объединяются в одну общую вероятность. Существует несколько способов выполнять перемешивание. Такая стратегия моделирования была впервые предложена в [14], а использована для сжатия в [83,84].

1.2 Контекстуально-смешанные модели.

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

Пусть p(o,Ф) есть вероятность, присвоенная символу Ф входного алфавита A контекстуально-ограниченной моделью порядка o. Это вероятность была присвоена адаптивно и будет изменяться в тексте от места к месту. Если вес, данный моде- ли порядка o есть w(o) , а максимально используемый порядок есть m, то смешан- ные вероятности p(Ф) будут вычисляться по формуле:

Сумма весов должна pавняться 1. Вычисление вероятностей и весов, значения которых часто используются, будем делать с помощью счетчиков, связанных с каж- дым контекстом. Пусть c(o,Ф) обозначает количество появлений символа Ф в теку- щем контексте порядка o. Обозначим через C(o) общее количество просмотров кон- текста. Тогда

Простой метод перемешивания может быть сконструирован выбором оценки от- дельного контекста как

Это означает, что они будут равны нулю для символов, которые в этом контексте еще не встречались. Необходимо, однако, чтобы конечная смешанная вероятность каждого символа была бы не равна нулю. Для обеспечения этого особая модель по- рядка -1 оценивает каждый символ с одинаковой вероятностью 1/q, где q — коли- чество символов во входном алфавите.

1.3 Вероятность ухода.

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

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

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

Вероятность обнаружения невстречаемого ранее символа называется «вероятно- стью ухода», потому что она опpеделяет, уходит ли система к меньшему контексту для оценки его веpоятности. Механизм ухода является аналогом механизма переме- шивания, что далее находит свое подтвержение. Обозначим вероятность ухода на уровень o через e(o), тогда соответствующие веса могут быть вычислены из веро- ятностей ухода по формуле:

где l есть длина наибольшего контекста. В этой формуле вес каждой модели более низкого порядка сокращается вероятностью ухода. Веса будут достоверными (все положительны и в сумме равны нулю) в том случае, если вероятности ухода имеют значения между 0 и 1 и минимальная степень модели, к котоpой можно уходить есть -1, поскольку e(-1)=0. Преимущество использования вероятностей ухода со- стоит в том, что по сpавнению с весами они имеют более наглядный и понятный смысл, когда как те очень быстро могут стать маленькими. Кроме того, механизм ухода на практике легче реализовать, чем перемешивание весов.

Если p(o,Ф) есть вероятность, присвоенная символу Ф моделью степени o, то вклад весов модели в смешанную вероятность будет:

Другими словами, это есть вероятность перехода к модели меньшего порядка сте- пени o и выбора Ф на этом уровне без перехода к более низкому. Для определения перемешанной вероятности для Ф, эти весовые вероятности могут быть просуммиро- ваны по всем значениям o. Определение механизма ухода происходит выбором зна- чений e(o) и p(o).

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

Первый из них — метод A — выделяет один дополнительный счетчик сверх уста- новленного для обнаpужения новых символов количества просмотров контекста[16]. Это дает следующее значение вероятности ухода:

Учитывая код ухода выделяемое для Ф в модели порядка o кодовое пpостpанство есть:

Метод B вычитанием 1 из всех счетчиков [16] воздерживается от оценки сим- волов до тех пор, пока они не появятся в текущем контексте более одного раза. Пусть q(o) есть количество разных символов, что появляются в некотором контек- сте порядка o. Вероятность ухода, используемая в методе B есть

которая пропорциональна количеству новых символов. Кодовое пространство, выде- ляемое для Ф есть

Метод C аналогичен методу B, но начинает оценивать символы сразу же по их появлению [69]. Вероятность ухода нарастает вместе с количеством разных симво- лов в контексте, но должна быть немного меньше, чтобы допустить дополнительное кодовое пространство, выделяемое символам, поэтому

Для каждого символа кодовое пространство в модели степени o будет:

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

Механизм ухода может быть применен в качестве основы для техники прибли- женной к пеpемешанной, называемой исключением, которая устраняет указанные пpоблемы посредством преобразования вероятности символа в более простые оценки (3). Она работает следующим образом. Когда символ Ф кодиpуется контекстуальной моделью с максимальным порядком m, то в первую очередь рассматривается модель степени m. Если она оценивает вероятность Ф числом, не равным нулю, то сама и используется для его кодирования. Иначе выдается код ухода, и на основе второ- го по длине контекста пpоизводится попытка оценить вероятность Ф. Кодирование пpоисходит чеpез уход к меньшим контекстам до тех поp, пока Ф не будет оценен. Контекст -1 степени гарантирует, что это в конце концов произойдет. Т.о. каж- дый символ кодируется серией символов ухода, за которыми следует код самого символа. Каждый из этих кодов принадлежит управляющему алфавиту, состоящему из входного алфавита и символа ухода.

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

Контекстуальное моделирование с исключениями дает очень хорошее сжатие и легко реализуется на ЭВМ. Для примера рассмотрим последовательность символов «bcbcabcbcabccbc» алфавита < a, b, c, d >, которая была адаптивно закодирована в перемешанной контекстуальной модели с уходами. Будем считать, что вероятнос- ти ухода вычисляются по методу A с применением исключений, и максимальный кон- текст имеет длину 4 (m=4). Рассмотрим кодирование следующего символа «d». Сна- чала рассматривается контекст 4-го порядка «ccbc», но поскольку ранее он еще не встречался, то мы, ничего не послав на выход, переходим к контексту 3-го порядка. Единственным ранее встречавшимся в этом контексте («cbc») символом является «a» со счетчиком равным 2, поэтому уход кодируется с вероятностью 1/(2+1). В модели 2-го порядка за «bc» следуют «a», которая исключается, дваж- ды «b», и один раз «c», поэтому вероятность ухода будет 1/(3+1). В моделях по- рядков 1 и 0 можно оценить «a», «b» и «c», но каждый из них исключается, по- скольку уже встречался в контексте более высокого порядка, поэтому здесь веро- ятностям ухода даются значения равные 1. Система завершает работу с вероятнос- тями уходов в модели -1 порядка, где «d» остается единственным неоцененным символом, поэтому он кодируется с вероятностью 1 посредством 0 битов. В pе- зультате получим, что для кодирования используется 3.6 битов. Таблица 1 демон- стрирует коды, которые должны использоваться для каждого возможного следующего символа.

Моделирование процессов и систем (стр. 2 )

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8

Задачи исследования систем:

1. Расчет — определение значений параметров системы.

2. Анализ – изучение свойств функционирования системы.

3. Синтез – выбор структуры и параметров по заданным свойствам системы.

Пусть T = [t, t1] есть временной интервал моделирования системы S (интервал модельного времени).

Построение модели начинается с определения параметров и переменных, определяющих процесс функционирования системы.

Параметры системы это характеристики системы, остающиеся постоянными на всем интервале T.

Переменные бывают зависимые и независимые.

Независимые переменные есть, как правило, входные воздействия (в том числе управляющие)

ими могут быть также воздействия внешней среды.

называется фазовой траекторией системы, , где Xпространство состояний или фазовое пространство.

Последовательность изменения y(t) называется выходной траекторией системы.

Зависимые переменные есть выходные характеристики (сигналы)

Общая схема математической модели (ММ) функционирования системы может быть представлена в виде:

Множество переменных вместе с законами функционирования

называется математической моделью системы.

Если t непрерывно, то модель называется непрерывной, иначе – дискретной:

Если модель не содержит случайных элементов, то она называется детерминированной, в противном случае – вероятностной, стохастической.

Если математическое описание модели слишком сложное и частично или полностью неопределенно, то в этом случае используются агрегативные модели.

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

2.3. Имитация случайных величин и процессов

Моделирование случайных элементов в системах является одной из самых базовых задач математического моделирования.

Илон Маск рекомендует:  Что такое код pspell_add_to_session

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

Базовый датчик выдает независимые равномерно распределенные случайные величины:

· непрерывные в (0,1);

Типы базовых датчиков:

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

· псевдослучайные датчики строятся на основе детерминированного алгоритма, но полученные результаты мало отличны от случайных.

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

при заданном x0.


Рассмотрим формулу получения случайных чисел

характерную для линейной конгруэнтной последовательности случайных чисел, где

4. Выдача результатов моделирования и, по желанию пользователя, графика.

Этап 4. Проведение вычислительных экспериментов

Эксперимент 1. Поток инвестиций — постоянный и в каждый момент времени равенВ начальный момент капитал – 1 руб. Коэффициент амортизации — 0,0025. Найти величину основных фондов через 3 суток, если лаг равен 5 суток.

Решение. Воспользуемся формулой

хi+1 = хi + yj – m*хi, x0 = с, i = 0, 1, 2,3; j =0.

Здесь х0= с = 1 руб.; m = 0.0025; y0 = 10 000 руб.

yj выделяется раз в 5 суток.

х1 = х0 + y0 – m*х0 = 1 000 000 + 10 000 – 0.0025* 1 000 000 = 1 007 500 (руб.);

х2 = х1 – m*х1 = 1 007 500 – 0.0025* 1 007 500 =

1 004 981.25 (руб.);

х3 = х2 – m*х2 = 1 004 981.25 – 0.0025* 1 004 981.25 = 1 002 468.7968 (руб.).

Эксперимент 2. Основные фонды в момент времени t = 0 были равны 5 000. Через какое время общая их сумма превысит руб., если поток инвестиций постоянный равный 2000 руб., известно, что m = 0.02, T=3 ?

Эксперимент 3. Какую стратегию инвестиций лучше использовать, если величина инвестиций постоянная, в начальный момент капитал равен 100 000 и величина амортизации постоянная?

Этап 5. Модификация (развитие) модели

Модификация 1. Коэффициент амортизации можно взять в форме m = r – s*x(t), где r — коэффициент обновления фондов, s — коэффициент устаревания фондов, причем 0 r, s 1. При этом модель примет вид

Этой непрерывной, дифференциальной, динамической модели можно поставить в соответствие простую дискретную модель:

курсовая работа Алгоритмы сжатия данных

Энтропия и количество информации. Комбинаторная, вероятностная и алгоритмическая оценка количества информации. Моделирование и кодирование. Некоторые алгоритмы сжатия данных. Алгоритм арифметического кодирования. Приращаемая передача и получение.

Нажав на кнопку «Скачать архив», вы скачаете нужный вам файл совершенно бесплатно.
Перед скачиванием данного файла вспомните о тех хороших рефератах, контрольных, курсовых, дипломных работах, статьях и других документах, которые лежат невостребованными в вашем компьютере. Это ваш труд, он должен участвовать в развитии общества и приносить пользу людям. Найдите эти работы и отправьте в базу знаний.
Мы и все студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будем вам очень благодарны.

Чтобы скачать архив с документом, в поле, расположенное ниже, впишите пятизначное число и нажмите кнопку «Скачать архив»

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 28.07.2009
Размер файла 325,1 K

Подобные документы

Методы арифметического кодирования. Основные функции программ, реализующие алгоритмы кодирования по методам Хаффмана, Голомба, Фибоначчи и Элиаса. Разработка программно-аппаратных средств оптимального арифметического кодирования и их экономический расчет.

дипломная работа [1,1 M], добавлен 26.05.2012

Методы компрессии информации. Обзор и характеристика существующих методов сжатия информации, основанных на процедуре кодирования Хаффмена. Алгоритмы динамического кодирования методом FGK и Виттера. Программная реализация и руководство пользователя.

курсовая работа [33,2 K], добавлен 09.03.2009

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

курсовая работа [157,4 K], добавлен 07.12.2012

Классификация и основные характеристики метода сжатия данных. Вычисление коэффициентов сжатия и оценка их эффективности. Алгоритмы полиноминальных, экстраполяционных и интерполяционных методов сжатия и их сравнение. Оптимальное линейное предсказание.

курсовая работа [1,1 M], добавлен 17.03.2011

Сущность универсального метода упаковки, его преимущества и недостатки. Кодирование путем учета числа повторений. Примеры схем распаковки последовательности байтов. Алгоритмы сжатия звуковой, графической и видеоинформации. Разновидности формата МРЕG.

презентация [96,2 K], добавлен 19.05.2014

Способ улучшения сжатия файлов формата DjVu. Общая схема алгоритма классификации букв. Основной алгоритм сравнения пары букв. Быстрый отказ для пары разных букв. Дерево разрезов. Получение монохромных изображений. Алгоритм для устранения мусора.

курсовая работа [64,7 K], добавлен 28.10.2008

Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано.

практическая работа [188,5 K], добавлен 24.04.2014

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

контрольная работа [19,6 K], добавлен 11.12.2011

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

презентация [45,3 K], добавлен 06.01.2014

Задачи обработки и хранения информации при помощи ЭВМ. Сжатие и кодирование информации в информационно-вычислительных комплексах. Метод Лавинского как простейший метод сжатия информации (числовых массивов) путем уменьшения разрядности исходного числа.

курсовая работа [66,0 K], добавлен 09.03.2009

Общие сведения

Энтропия и количество информации

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

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

Комбинаторная, вероятностная и алгоритмическая оценка количества информации

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

Таким образом, для передачи состояния объекта достаточно I=log2N бит информации. Заметим, что количество информации может быть дробным. Разумеется, дробное количество информации невозможно сохранить на носителе или передать по каналам связи. В то же время, если необходимо передать либо сохранить большое количество блоков информации дробной длины, их всегда можно сгруппировать таким образом, чтобы полностью исключить потери (например, посредством арифметического кодирования).

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

Обозначим через р(у|х) условную вероятность того, что наступит событие у если событие х уже наступило. В таком случае условная энтропия для переменной Y, которая может принимать М значений yi с условными вероятностями р(уi|х) будет

Приведенные формулы показывают, что вне зависимости от того, как были получены вероятности наступления следующих событий, для кодирования события с вероятностью р достаточно — log2 p бит (в полном соответствии с теоремой Шеннона об оптимальном кодировании).

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

Моделирование и кодирование

Энтропия набора данных, а значит и максимально возможная степень сжатия, зависит от модели. Чем адекватнее модель (чем качественнее мы можем предсказать распределение вероятности значений следующего элемента), тем ниже энтропия и тем лучше максимально достижимая степень сжатия. Таким образом, сжатие данных разбивается на две самостоятельные задачи — моделирование и кодирование.

Моделирование обеспечивает предсказание вероятности наступ-ления возможных событий, кодирование обеспечивает представление события в виде -log2 p бит, где р — предсказанная вероятность наступ-ления события. Задача моделирования, как правило, более сложная. Это обусловлено высокой сложностью современных моделей данных. В то же время кодирование не является серьезной проблемой. Существует большое количество стандартных кодеров, различающихся по степени сжатия и быстродействию. Как правило, в системах сжатия исполь-зуемый кодер при необходимости может быть легко заменен другим.

Экономико-математическое моделирование : Энтропия

§1. Понятие энтропии. Энтропия как мера степени неопределенности

§2. Понятие об информации. Измерение информации

§3. Теорема Шеннона о кодировании при наличии помех

§4. Пример использования энтропии в прогнозировании и ее значение для прогнозирования. Применение к рискам

Список использованной литературы

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

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

Термин “информация” замечателен тем, что, существующему с давних пор бытовому понятию, К.Шенноном был придан математически точный смысл. Неопределенно-бытовой смысл этого термина уже научного. Это приводило и приводит ко многим недоразумениям/ Данную тему опишем с помощью следующих методов: синтеза, анализа, индукции, дедукции, сравнения и расчетного метода.

Работа изложена на 26 страниц и состоит из четырех параграфов. В работе 1 таблица и 7 примеров.

§1. Понятие энтропии. Статистический смысл понятия энтропии. Энтропия как мера степени неопределенности

Энтропия (от греч. entropia — поворот, превращение) — мера неупорядоченности больших систем. Впервые понятие «энтропия» введено в XIX в. в результате анализа работы тепловых машин, где энтропия характеризует ту часть энергии, которая рассеивается в пространстве, не совершая полезной работы (отсюда определение: энтропия — мера обесценивания энергии). Затем было установлено, что энтропия характеризует вероятность определенного состояния любой физической системы среди множества возможных ее состояний. В закрытых физических системах все самопроизвольные процессы направлены к достижению более вероятных состояний, т. е. к максимуму энтропии . В равновесном состоянии, когда этот максимум достигается, никакие направленные процессы невозможны. Отсюда возникла гипотеза о тепловой смерти Вселенной. Однако распространение на всю Вселенную законов, установленных для закрытых систем, не имеет убедительных научных оснований. В XX в. понятие » энтропия » оказалось плодотворным для исследования биосистем, а также процессов передачи и обработки информации. Эволюция в целом и развитие каждого организма происходит благодаря тому, что биосистемы, будучи открытыми, питаются энергией из окружающего мира. Но при этом биопроцессы протекают таким образом, что связанные с ними «производство энтропии » минимально. Это служит важным руководящим принципом и при разработке современных технологических процессов, при проектировании технических систем. Количественная мера информации формально совпадает с «отрицательно определенной » энтропией. Но глубокое понимание соответствия энтропии физической и информационной остается одной из кардинальных недостаточно исследованных проблем современной науки. Ее решение послужит одним из важных факторов становления нового научно-технического мышления.

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

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

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

Существование неопределённости связано с участием вероятностей в осуществлении событий. Устранение неопределённости есть увеличение вероятности наступления того, что задано как цель. Поэтому вероятности должны участвовать в математической формулировке величины устранённой неопределённости.

Первая удачная попытка реализовать определение информации на такой основе осуществлена в 1928 г. Л. Хартли. Пусть возможно в данных условиях n вариантов некоторого результата. Целью является один из них. Хартли предложил характеризовать неопределённость логарифмом числа n. То есть log n является количественной мерой неопределённости. Выбор основания логарифма связан с понятием об алфавитах для описания информации. Этот выбор существенен для экономичности кодирования в технических устройствах или живых системах (сокращения потоков импульсов или аналоговых сигналов), но не меняет самого количества информации как устранённой неопределённости за счёт того, что перед логарифмом вводится безразмерный множитель, выражаемый модулем перехода между основаниями логарифмов. От него зависят названия единиц информации.

При математическом описании неопределённости (например способом Хартли) в случае равновероятных результатов можно перейти от их числа n к обратной величине — вероятности р одного из них. В терминах связи конкретно говорят о вероятности переданного сообщения р у приёмника до приёма сообщения. Устранение неопределённости выражается тем, что вероятность переданного сообщения у приёмника после приёма сигнала возрастает и становится р1 . Тогда количественная мера s полученной информации (устранённой неопределённости) выражается логарифмом отношения вероятностей:

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

Недостаток этого определения в том, что оно справедливо в приближении равновероятности всех исходов. Это выполняется далеко не всегда. В пределе в этом определении невероятному исходу приравнивается неизбежный. В 1948 г. это исправил К. Шеннон, который определил в качестве меры неопределённости выражение:

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

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

§2. Понятие об информации. Измерение информации

Понятие информации (informatio — разъяснение, осведомление, изложение) является одним из основных, ключевых понятий не только в информатике (в информологии — области знаний, изучающей проявление информации, её представление, измерение и т.д.), но и в математике, в физике и др. Понятие “информация” — плохо формализуемое и структурируемое понятие. В силу его всеобщности, объёмности, расплывчатости оно часто понимается неточно и неполно не только обучаемыми. Как правило, это понятие в курсе информатики не определяется, принимается как исходное базовое понятие, неопределяемый терм.

Информация трактуется по разному, например, как:

* любая сущность, которая вызывает изменения в некоторой информационно-логической (инфологической — состоящей из данных, знаний, абстракций и т.д.) модели системы (математика, системный анализ);

* сообщения, полученные системой от внешнего мира в процессе адаптивного управления, приспособления (теория управления, кибернетика);

* отрицание энтропии, отражение меры хаоса в системе (термодинамика);

* связи, устраняющие неопределённость в системе (теория информации);

* вероятность выбора в системе (теория вероятностей);

* отражение разнообразия в системе (физиология, биокибернетика);

* отражение материи, атрибут сознания, “интеллекта” системы (философия).

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

Информация может существовать в пассивной (не актуализированной) и активной (актуализированной) форме.

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

Информация в философском аспекте бывает, в основном: мировоззренческая; эстетическая; религиозная; научная; бытовая; техническая; экономическая; технологическая.

Все это (с человеком) составляет ноосферу общества — более высокое состояние биосферы, возникшее в результате эволюции, структурирования, упорядочивания и гармонизации связей в природе и обществе под воздействием целеполагающей деятельности человечества. Это понятие введено впервые В. И. Вернадским в качестве отражения эволюции общества и природы т.е. системы, в рамках которой потенциально может быть реализовано гармоническое, устойчивое развитие (эволюция) систем “Общество” и “Природа”, а также постепенное слияние, интеграция и гармонизация наук о природе, познании и об обществе. Без этого невозможно построение информационного общества.

Информация может оказаться и вредной, влияющей негативно на сознание, например, воспитывающей восприятие мира от безразличного или же некритического — до негативного, «обозлённого», неадекватного. Информационный поток — достаточно сильный раздражитель.

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

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

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


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

Количество информации — числовая величина, адекватно характеризующая актуализируемую информацию по разнообразию, сложности, структурированности, определённости, выбору (вероятности) состояний отображаемой системы.

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

1. Мера Р. Хартли. Пусть имеется N состояний системы S или N опытов с различными, равновозможными последовательными состояниями системы. Если каждое состояние системы закодировать, например, двоичными кодами определённой длины d, то эту длину необходимо выбрать так, чтобы число всех различных комбинаций было бы не меньше, чем N. Наименьшее число, при котором это возможно или мера разнообразия множества состояний системы задаётся формулой Р. Хартли: H=k log а N, где k — коэффициент пропорциональности (масштабирования, в зависимости от выбранной единицы измерения меры), а — основание системы меры.

Если измерение ведётся в экспоненциальной системе, то k=1, H=lnN (нат); если измерение — в двоичной системе, то k=1/ln2, H=log2N (бит); если измерение — в десятичной системе, то k=1/ln10, H=lgN (дит).

Пример. Чтобы узнать положение точки в системе из двух клеток т.е. получить некоторую информацию, необходимо задать 1 вопрос («Левая или правая клетка?»). Узнав положение точки, мы увеличиваем суммарную информацию о системе на 1 бит (I=log2 2). Для системы из четырех клеток необходимо задать 2 аналогичных вопроса, а информация равна 2 битам (I=log24). Если система имеет n различных состояний, то максимальное количество информации равно I=log2 n.

По Хартли, для того, чтобы мера информации имела практическую ценность — она должна быть такова, чтобы отражала количество информации пропорционально числу выборов.

Пример. Имеются 192 монеты из которых одна фальшивая. Определим сколько взвешиваний нужно произвести, чтобы определить ее. Если положить на весы равное количество монет, то получим 2 возможности (мы сейчас отвлекаемся от того, что в случае фальшивой монеты таких состояний будет два — состояния независимы): а) левая чашка ниже; б) правая чашка ниже. Таким образом, каждое взвешивание дает количество информации I=log22=1 и, следовательно, для определения фальшивой монеты нужно сделать не менее k взвешиваний, где k удовлетворяет условию log22k? log2192. Отсюда, k=7. Следовательно, нам необходимо сделать не менее 7 взвешиваний (достаточно семи).

Формула Хартли отвлечена от семантических и качественных, индивидуальных свойств рассматриваемой системы (качества информации, содержащейся в системе, в проявлениях системы с помощью рассматриваемых N состояний системы). Это основная положительная сторона этой формулы. Но имеется и основная отрицательная сторона: формула не учитывает различимость и различность рассматриваемых N состояний системы.

Уменьшение (увеличение) Н может свидетельствовать об уменьшении (увеличении) разнообразия состояний N системы.

Обратное, как это следует из формулы Хартли (основание логарифма берётся больше 1), — также верно.

2.Мера К. Шеннона. Формула Шеннона дает оценку информации независимо, отвлеченно от ее смысла:

n I = — a pi log2 pi , i=1

где n — число состояний системы; рi — вероятность (или относительная частота) перехода системы в i-ое состояние, причем сумма всех pi равна 1.

Если все состояния равновероятны (т.е. рi=1 /n), то I=log2n.

К. Шенноном доказана теорема о единственности меры количества информации. Для случая равномерного закона распределения плотности вероятности мера Шеннона совпадает с мерой Хартли. Справедливость и достаточная универсальность формул Хартли и Шеннона подтверждается и данными нейропсихологии.

Пример. Время t реакции испытуемого на выбор предмета из имеющихся N предметов линейно зависит от log2N: t=200+180log2N (мс). По аналогичному закону изменяется и время передачи информации в живом организме. В частности, один из опытов по определению психофизиологических реакций человека состоял в том, что перед испытуемым большое количество раз зажигалась одна из n лампочек, которую он должен указать. Оказалось, что среднее время, необходимое для правильного ответа испытуемого, пропорционально не числу n лампочек, а именно величине I определяемой по формуле Шеннона, где pi — вероятность зажечь лампочку номер i.

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

Если в формуле Шеннона обозначить fi = —n log2 pi , то получим, что I можно понимать как среднеарифметическое величин fi .

Отсюда, fi можно интерпретировать как информационное содержание символа алфавита с индексом i и величиной pi вероятности появления этого символа в сообщении, передающем информацию.

Основными положительными сторонами формулы Шеннона является её отвлечённость от семантических и качественных, индивидуальных свойств системы, а также то, что в отличие от формулы Хартли она учитывает различность, разновероятность состояний — формула имеет статистический характер (учитывает структуру сообщений), делающий эту формулу удобной для практических вычислений. Основные отрицательные стороны формулы Шеннона: она не различает состояния (с одинаковой вероятностью достижения, например), не может оценивать состояния сложных и открытых систем и применима лишь для замкнутых систем, отвлекаясь от смысла информации.

Увеличение (уменьшение) меры Шеннона свидетельствует об уменьшении (увеличении) энтропии (организованности) системы. При этом энтропия может являться мерой дезорганизации систем от полного хаоса (S=Smax) и полной информационной неопределённости (I=Imin) до полного порядка (S=Smin) и полной информационной определённости (I=Imax) в системе.

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

3. Термодинамическая мера. Информационно-термодинамический подход связывает величину энтропии системы с недостатком информации о её внутренней структуре (не восполняемым принципиально, а не нерегистрируемым). При этом число состояний определяет, по существу, степень неполноты наших сведений о системе.

Пусть дана термодинамическая система (процесс) S, а Н0, Н1 — термодинамические энтропии системы S в начальном (равновесном) и конечном состояниях термодинамического процесса, соответственно. Тогда термодинамическая мера информации (негэнтропия) определяется формулой:

Эта формула универсальна для любых термодинамических систем. Уменьшение Н(Н0,Н1) свидетельствует о приближении термодинамической системы S к состоянии статического равновесия (при данных доступных ей ресурсах), а увеличение — об удалении.

Поставим некоторый вопрос о состоянии некоторой термодинамической системы. Пусть до начала процесса можно дать p1 равновероятных ответов на этот вопрос (ни один из которых не является предпочтительным другому), а после окончания процесса — p2 ответов. Изменение информации при этом:

D I = k ln(p1 / p2) = k (ln p1 — ln p2 ).

Если p1 > p2 (D I >0) — прирост информации, т.е. сведения о системе стали более определёнными, а при p10 — более низкой организации).

Термодинамическая мера (энтропия) применима к системам, находящимся в тепловом равновесии. Для систем, далёких от теплового равновесия, например, живых биосистем, мера — энтропия — менее подходящая.

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

3. Теорема Шеннона о кодировании при наличии помех

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

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

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

Далее в основном ограничим себя ситуацией, когда M = 2, т.е. для представления кодов в линии связи используется лишь два типа сигналов — с практической точки зрения это наиболее просто реализуемый вариант (например, существование напряжения в проводе (будем называть это импульсом) или его отсутствие (пауза); наличие или отсутствие отверстия на перфокарте или намагниченной области на дискете); подобное кодирование называется двоичным. Знаки двоичного алфавита принято обозначать «0» и «1», но нужно воспринимать их как буквы, а не цифры. Удобство двоичных кодов и в том, что при равных длительностях и вероятностях каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации (log2M = 1); тогда из (1), теоремы Шеннона:

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

Применение формулы (2) для двоичного кодирования дает:

Определение количества переданной информации при двоичном кодировании сводится к простому подсчету числа импульсов (единиц) и пауз (нулей). При этом возникает проблема выделения из потока сигналов (последовательности импульсов и пауз) отдельных кодов. Приемное устройство фиксирует интенсивность и длительность сигналов. Элементарные сигналы (0 и 1) могут иметь одинаковые или разные длительности. Их количество в коде (длина кодовой цепочки), который ставится в соответствие знаку первичного алфавита, также может быть одинаковым (в этом случае код называется равномерным) или разным (неравномерный код). Наконец, коды могут строиться для каждого знака исходного алфавита (алфавитное кодирование) или для их комбинаций (кодирование блоков, слов). В результате при кодировании (алфавитном и словесном) возможны следующие варианты сочетаний:

Варианты сочетаний длительности элементарных сигналов

Термодинамическое моделирование сложных систем

Постановка задачи моделирования сложных система

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

Илон Маск рекомендует:  Все об authtype или авторизация в apache

Методы и системы термодинамического моделирования

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

  1. нахождение минимума изобарно-изотермического потенциала системы;
  2. определение равенства химических потенциалов компонентов;
  3. нахождение максимума энтропии системы.

Разработаны различные программные средства расчета и моделирования термодинамических система, основанные на рассмотренных выше принципах равновесия.

В программном комплексе “Астра”, разработанном в МГТУ имени Баумана, реализована методика поиска максимума энтропии системы. Данная программа позволяет рассчитать условия равновесия для газов, механической смеси индивидуальных веществ, идеальных растворов и низкотемпературной плазмы. Кроме того, предусмотрена возможность моделирования неравновесного стационарного состояния системы путем фиксации значений требуемых параметров.

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

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

Применение принципа максимума энтропии в программном комплексе “Астра”

Принципы, реализованные в программном комплексе “Астра”

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

Рассмотрим основные принципы расчета максимума энтропии, которые используются в программном комплексе “Астра”.

Энтропия сложной системы

Суммарная энтропия

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

Энтропия газовой фазы

Энтропия газовой фазы в приближении идеального газа рассчитывается следующим образом:

– энтропия чистого компонента газа;

– число молей -го компонента газа,

– универсальная газовая постоянная.

Энтропия конденсированных растворов

Вклад отдельного раствора конденсированных веществ в энтропию системы рассматривают в виде суммы вкладов отдельных составляющих. Растворы считаются идеальными:

– число компонентов раствора;

– мольная доля -го компонента раствора.

Энтропия индивидуальных веществ

Для расчета энтропии индивидуальных веществ, представляющих собой самостоятельные фазы, используется следующая формула:

(3.118) Для термодинамической системы, содержащей растворов, газовую фазу и – конденсированных веществ, энтропия представлена функцией состава и рассчитывается с учетом вкладов всех компонентов системы:

Ограничения при нахождении максимума данной функции

Задача сводится к нахождению максимума данной функции при следующих ограничениях:

  1. Постоянство полной внутренней энергии системы (3.120) где , , – внутренняя энергия газообразного, твердого или растворенного компонента системы соответственно.
  2. Соблюдение условия материального баланса в виде законов сохранения массы химических элементов для рассматриваемых закрытых систем: (3.121)

где – мольное содержание элемента в системе; , , – стехиометрические коэффициенты соединений элемента в соответствующих фазах.
При наличии в рассматриваемых многокомпонентных системах ионов, необходимо обеспечить соблюдение общей электронейтральности. Если носителями электрического заряда являются только компоненты газовой фазы, то соответствующее уравнение примет вид: (3.122)

где – кратность ионизации -го компонента газа.
Еще одна взаимосвязь между параметрами и химическим составом системы устанавливается уравнением состояния идеального газа: (3.123)

Исследование системы , включающих конденсированные фазы в виде растворов, требует введения нормирующих соотношений, ограничивающих состав этих фаз:

Применение программы “Астра”

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

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

Универсальная и достаточно компактная программа “Астра” в настоящее время широко применяется для расчета состава и характеристик смесей, содержащих произвольный набор химических элементов. Программа ориентирована на персональную ЭВМ, работающую в операционной среде MS-DOS.

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

Требования при расчете характеристик равновесного состояния

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

В качестве определяющих параметров обычно используется одна “механическая” и одна “энергетическая” характеристика системы. “Механическим” параметром чаще всего выступает общее давление или удельный объем . “Энергетическим” параметром является температура , энтальпия , внутренняя энергия или энтропия . Использованный в программе алгоритм позволяет проводить расчет для любой комбинации названных величин.

Инструментальная система для термодинамического моделирования металлургических процессов на базе программного комплекса “Астра”

Необходимость проведения ручных расчетов

Применение программного комплекса “Астра” в задачах моделирования металлургических процессов приводит к необходимости проведения большого числа ручных операций, таких как: пересчет процентного состава нескольких многокомпонентных исходных материалов в требуемый формат; задание растворов в случае многофазной системы; распределение полученных в ходе моделируемого процесса продуктов по фазам; расчет процентного содержания компонентов; расчет полной начальной энергии для определения конечной температуры процесса; фиксация процентного состава некоторых веществ для задания неравновесных условий и ряд других.

Инструментальная системадля решения многовариантных задач

Структура

В связи с этим на кафедре информационных технологий в металлургии СибГИУ созданы методика и инструментальная система на базе программного комплекса “Астра” для решения многовариантных задач математического моделирования, в том числе для оценки предельных энергетических возможностей новых непрерывных металлургических процессов.

Структура связей основных модулей системы приведена на рис. 3.13.

Рис. 3.13 Структура связей основных модулей системы

Основные модули

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

Взаимодействие DOS и ОС Windows

Так как программный комплекс “Астра” работает в среде DOS, а описываемая среда – в ОС Windows, то для обеспечения их взаимодействия применяется промежуточный слой, выполняющий функции управления приложением DOS. Для отслеживания текущего состояния запущенного процесса DOS используется сервис, предоставляемый операционной системой Windows.

В силу того, что программный комплекс “Астра” требует ручного ввода некоторых данных, для имитации работы используется резидентная программа DOS, которая контролирует работу программного комплекса и при необходимости посылает ему управляющие сообщения.


Обмен потоками данных между модулем общего управления и программным комплексом “Астра” осуществляется через файлы, расположенные на жестком диске.

Алгоритм работы программной системы

Укрупненный алгоритм работы программной системы приведен на рис. 3.14.

Рис. 3.14 Структура алгоритма работы системы

Он предусматривает ввод пользователем данных, необходимых для выполнения расчета. После ввода всех исходных данных программная среда автоматически генерирует файл задания для программного комплекса “Астра” и сохраняет его на жестком диске. Затем производится запуск программного комплекса, который производит необходимые вычисления под контролем управляющей TSR-программы и сохраняет результаты также на жестком диске.

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

Базы данных комплекса “Астра”

При работе комплекса “Астра” требуется доступ к определенным базам данных, наиболее важные из которых представлены на рис. 3.14. Потоки данных между отдельными блоками программы показаны жирными линиями, а последовательность управления – пунктирными.

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

В качестве основного программного средства создания инструментальной системы использован MS Access 97, который позволяет выполнять быструю разработку баз данных и легко осуществлять доступ к информации. Модуль управления DOS-приложением реализован на Borland Delphi, так как с его помощью с одной стороны легко и удобно реализовать доступ к сервисам, предоставляемым операционной системой, а с другой – Object Pascal является достаточно удобным и надежным языком программирования.

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

Реализация модулей позволила создать инструментальную система, которая предоставляет пользователю следующие возможности: просмотр свойств индивидуальных веществ; задание основных параметров моделируемого процесса и исходного состава сырья; расчет на основе введенных данных масс, составов и температуры конечных продуктов; расчет энтальпии нагрева исходных и конечных продуктов; экспорт полученных данных в Microsoft Excel 97; поиск оптимальных исходных составов, необходимых для достижения заданных конечных параметров процесса, при условии выполнения системы требуемых ограничений.

Пример термодинамического моделирования процесса восстановления железа

Постановка задачи

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

Для этого будем формировать разные составы этой системы из указанного набора элементов путем задания исходной смеси в виде 1 моля оксида и варьирования количества молей углерода и кислорода соответственно параметрами и .

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

Перечень веществ, которые могут образовываться при заданном элементном составе смеси для диапазона температур 298-1973К , определим в результате численного моделирования с помощью “Астры”.

Термодинамически возможное количество веществ, образующихся из указанных элементов для выбранного диапазона температур, составило величину более 25. Все вещества по значению величины концентрации в конечном состоянии поделим на значимые и незначимые с порогом различимости моль/кг смеси. В качестве значимых при делении оказались восемь веществ: газовая фаза – , , ; конденсированная фаза – , , , , .

Основные задачи моделирования

Перечень задач моделирования

Для исследования процессов восстановления в системе сформулируем следующие задачи моделирования:

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

Определение температуры и количества углерода

Определение температуры и количества углерода, необходимых для реализации процесса восстановления осуществлялось путем расчетов равновесных составов системы в диапазоне температур 573-1973К . На рис. 3.15 показаны результаты зависимости параметров процесса при от расхода углерода.

Рис. 3.15 Зависимость параметров восстановления железа в системе от расхода углерода

При =3 моля достигается полное восстановление одного моля , что необходимо также по стехиометрии. На рис. 3.16 приведены зависимости параметров процесса восстановления железа от температуры при подаче в системаглерода в количестве =3 моля.

Рис. 3.16 Зависимость параметров восстановления железа системы от температуры

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

Определение значения показателя альфа

Определение значений показателя , соответствующих границам областей протекания окислительных и восстановительных процессов в системе , рассмотрим для температуры . Для этого проведем последовательные расчеты равновесных составов смеси путем варьирования параметра при количестве углерода в системе равном 4 моля. Такое значение взято с целью обеспечения избытка углерода, что способствует созданию гарантированных условий протекания восстановительных процессов и, как следствие, более четкому выделению границ областей протекания процессов. Изменение в интервале от 0 до 8 молей позволило изучить поведение модельной системы от восстановительных условий до окислительных, когда в системе присутствует свободный кислород.

На рис. 3.17 приведены зависимости абсолютного содержания компонентов газовой и конденсированной фаз и логарифма мольной доли кислорода в газовой фазе от параметра .

Рис. 3.17 Зависимость параметров равновесного состояния системы от показателя

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

Восстановительная область

Первая область – восстановительная существует при значениях и состоит из двух зон. Для первой зоны характерно присутствие железа и свободного углерода в конденсированной фазе, во второй зоне углерод отсутствует, и конденсированная фаза состоит из чистого железа. В первой зоне восстановительной области газовая фаза полностью состоит из , а затем содержание снижается до 60%. На границе восстановительной и переходной областей значение равно 0,2.

Переходная область

Переходная область соответствует . Характеризуется снижением концентрации восстановленного железа до полного исчезновения и, следовательно, ростом содержания в конденсированной фазе. Как видно из рис. 3.17, для этой области свойственно наличие постоянного соотношения и в газовой фазе.

Окислительная область

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

Графическое отображение выделенных областей

Границы выделенных областей наглядно видно на графике по характерным перегибам. Первый перегиб связан с исчезновением свободного углерода, второй – с исчезновением железа, а третий – с исчезновением оксида железа и появлением свободного кислорода. Отметим также наличие своеобразных “остановок” на кривой . Они соответствуют двухфазным равновесиям между , и . Этим равновесиям соответствует фиксированное значение , которое определяется температурой. На этих участках увеличение расхода кислорода приводит к уменьшению количества окисляющейся фазы, а кислородный потенциал атмосферы при этом остается постоянным.

Моделирование совместных процессов восстановления и нагрева

Постановка задачи

Следует отметить, что приведенные выше результаты моделирования получены при заданной фиксированной температуре . Однако, для реализации процессов жидкофазного восстановления необходимо обеспечение заданного температурного режима за счет “внутренних” источников тепла, а именно, тепла экзотермических реакций окисления углерода. Поэтому, рассмотрим решение задачи моделирования совместных процессов восстановления и нагрева.

Определение параметров

Определение параметров и , обеспечивающих достижение заданной температуры, а также параметров металла и степени восстановления осуществим следующим образом. Выполним последовательность расчетов равновесных составов системы при пропорциональном увеличении количества молей углерода и количества молей кислорода . Для каждого состояния системы рассчитывается также значение полученной при этом температуры. На рис. 3.18 приведены зависимости количества и состава фаз от показателя , который меняется в пределах от 0,2 до 0,45.

Рис. 3.18 Зависимость параметров системы от расхода углерода

Температура достигается при значении показателя для и . Количество углерода на восстановление составило 3 моля, на нагрев до 1873К – 10,125 молей. Этим показателям соответствует степень восстановления железа равная 100%, содержание углерода в металле и содержание оксида углерода в газовой фазе . Дальнейшее увеличение параметра приводит к появлению в конденсированной фазе оксидов железа, увеличению содержания в газовой фазе и резкому росту температуры, что объясняется переходом системы в окислительную область.

Таким образом, для обеспечения процесса восстановления и достижения температуры 1873К при отсутствии тепловых потерь в система, состоящую из 1 моля , необходимо подать 13,125 молей углерода и 5,063 молей кислорода, что составляет величину расходов и соответственно.

За счет ведения процесса в неравновесном режиме возможно снижение значений и и, соответственно, повышение эффективности прямого восстановления железа.

Анализ, классификация и моделирование алгоритмов сжатия Шубович Валерий Геннадьевич

Данный автореферат диссертации должен поступить в библиотеки в ближайшее время
Уведомить о поступлении

480 руб. | 150 грн. | 7,5 долл. ‘, MOUSEOFF, FGCOLOR, ‘#FFFFCC’,BGCOLOR, ‘#393939’);» onMouseOut=»return nd();»> Диссертация — 480 руб., доставка 10 минут , круглосуточно, без выходных и праздников

240 руб. | 75 грн. | 3,75 долл. ‘, MOUSEOFF, FGCOLOR, ‘#FFFFCC’,BGCOLOR, ‘#393939’);» onMouseOut=»return nd();»> Автореферат — 240 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Шубович Валерий Геннадьевич. Анализ, классификация и моделирование алгоритмов сжатия : диссертация . кандидата технических наук : 05.13.18.- Ульяновск, 2001.- 210 с.: ил. РГБ ОД, 61 02-5/1597-4

Содержание к диссертации

Глава 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

Библиографический список использованной литературы 166

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

Существуют два основных способа проведения сжатия: статистический и словарный. Лучшие статистические методы

Одним из наиболее важных достижений в теории сжатия за последнее десятилетие явилась впервые высказанная в М идея разделения процесса сжатия на две части: на кодер, непо средственно производящий сжатый поток битов, и на моделирующее устройство (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) класс, в котором проводится по-иск с восстановлением. Для методов первого класса оставший-ся после сжатия массив данных переадресуется; для этих целей вводится специальная схема, которая по заданному адресу отыскивает соответствующее ему табличное данное. Для вто-рого класса методов сначала по исходному адресу осуществляется поиск в сжатых таблицах, и только после этого выполняется восстановление исходного данного. Здесь под восстановлением понимается процесс аппаратного вычисления искомого данного посредством использования некоторой математической операции над табличными данными, выбираемыми по заданному адресу Поиск с восстановчением может вносить погрешность в получаемый результат/

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

Предлагаемый метод представляет интерес по ряду сле дующих причин: 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, удовлетворяющую равенство Щ). Каждая тх может быть сформирована, начиная с произвольной (исходной) таблицы, представляющей строку данных х, которую применением пяти правил сокращения пре образуют в таблицу наименьшей сложности /Ш/. Таблица наи меньшей сложности формируется за конечное число шагов со кращений. Например, если начать с исходной таблицы замены, состоящей из одного единственного ряда (so, х), то начальное значение функции сложности эквивалентно (2/?-1), следова тельно в этом случае необходимо (2п-2) шагов сокращений чтобы достигнуть таблицы наименьшей сложности. , Коды последовательного источника без потерь.

База знаний студента. Реферат, курсовая, контрольная, диплом на заказ

Энтропия сложных сообщений, избыточность источника. Цель сжатия данных и типы систем сжатия — Коммуникации и связь

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Реферат на тему:

«Энтропия сложных сообщений, избыточность источника. Цель сжатия данных и типы систем сжатия»

Энтропия сложных сообщений, избыточность источника

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

Однако в реальных условиях независимость элементарных сообщений, вырабатываемых источником, — явление довольно редкое. Чаще бывает как раз обратное — сильная детерминированная или статистическая связь между элементами сообщения одного или нескольких источников.

Например, при передаче текста вероятности появления отдельных букв зависят от того, какие буквы им предшествовали. Для русского текста, например, если передана буква «П«, вероятность того, что следующей будет «А«, гораздо выше, чем «Н«, после буквы «Ъ» никогда не встречается «H» и т.д. Подобная же картина наблюдается при передаче изображений — соседние элементы изображения имеют обычно почти одинаковые яркость и цвет.

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

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

Определим энтропию сложного сообщения, вырабатываемого двумя зависимыми источниками (подобным же образом определяется энтропия сложного сообщения, вырабатываемого одним источником с памятью).

Совместную энтропию двух источников X и Y можно определить следующим образом:

где P(xi,yj ) — вероятность совместного появления сообщений xi и yj . Поскольку совместная вероятность P(xi,yj ) по формуле Байеса определяется как

то выражение для совместной энтропии можно записать в следующем виде:

Так как передаче сообщения xi обязательно соответствует передача одного из сообщений (любого) из ансамбля Y , то

и совместная энтропия H(X,Y) определится как

где H ( Y/xi ) — так называемая частная условная энтропия, отражающая энтропию сообщения Y при условии, что имело место сообщение xi. Второе слагаемое в последнем выражении представляет собой усреднение H ( Y/xi ) по всем сообщениям xi и называется средней условной энтропией источника Y при условии передачи сообщения X. И окончательно:

Таким образом, совместная энтропия двух сообщений равна сумме безусловной энтропии одного из них и условной энтропии второго.

Можно отметить следующие основные свойства энтропии сложных сообщений:

1. При статистически независимых сообщениях X и Y совместная энтропия равна сумме энтропий каждого из источников:

2. При полной статистической зависимости сообщений X и Y совместная энтропия равна безусловной энтропии одного из сообщений. Второе сообщение при этом информации не добавляет. Действительно, при полной статистической зависимости сообщений условные вероятности P(yj/xi) и P(xi/y j) равны или нулю, или 1, тогда

и, следовательно, H (X,Y) = H (X) = H (Y).

3. Условная энтропия изменяется в пределах

Если бы все буквы русского алфавита имели одинаковую вероятность и были статистически независимы, то средняя энтропия, приходящаяся на один символ, составила бы

Если теперь учесть лишь различную вероятность букв в тексте (а нетрудно проверить, что так оно и есть), расчетная энтропия составит

С учетом корреляции (статистической связи) между двумя и тремя соседними буквами (после буквы “П” чаще встречается “A” и почти никогда – “Ю” и “Ц”) энтропия уменьшится, соответственно, до

Наконец, если учесть корреляцию между восемью и более символами, энтропия уменьшится до

и далее остается без изменений.

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

ρи = 1 — H ( λ ) / H ( λ )max = 1 — H ( λ )/log K , (11)

где H (λ ) — энтропия реального источника, log K — максимально достижимая энтропия для источника с объемом алфавита в К символов.

Тогда, к примеру, избыточность литературного русского текста составит

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

Такой же, если не более высокой ( ρи= 0,9. 0,95) избыточностью обладают и другие источники информации — речь, и особенно музыка, телевизионные изображения и т.д.

Возникает законный вопрос: нужно ли занимать носитель информации или канал связи передачей символов, практически не несущих информации, или же возможно такое преобразование исходного сообщения, при котором информация «втискивалась» бы в минимально необходимое для этого число символов?

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

Изучению этого раздела современной радиотехники – основ теории и техники экономного, или безызбыточного, кодирования — и посвящена следующая часть нашего курса.

Цель сжатия данных и типы систем сжатия

Передача, хранение и обработка информации требуют достаточно больших затрат. И чем с большим количеством информации нам приходится иметь дело, тем дороже это стоит. К сожалению, большая часть данных, которые нужно передавать по каналам связи и сохранять, имеет не самое компактное представление. Скорее, эти данные хранятся в форме, обеспечивающей их наиболее простое использование, например: обычные книжные тексты, ASCII коды текстовых редакторов, двоичные коды данных ЭВМ, отдельные отсчеты сигналов в системах сбора данных и т.д. Однако такое наиболее простое в использовании представление данных требует вдвое — втрое, а иногда и в сотни раз больше места для их сохранения и полосу частот для их передачи, чем на самом деле нужно. Поэтому сжатие данных – это одно из наиболее актуальных направлений современной радиотехники.

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

Учитывая чрезвычайную важность процедуры экономного кодирования данных при их передаче, выделим ее из обобщенной схемы РТС ПИ и подробно рассмотрим в настоящем разделе нашего курса.

Ниже приведена условная структура системы сжатия данных:

Данные источника ® Кодер ® Сжатые данные ® Декодер ® Восстановленные данные

В этой схеме вырабатываемые источником данные определим как данные источника, а их компактное представление — как сжатые данные. Система сжатия данных состоит из кодера и декодера источника. Кодер преобразует данные источника в сжатые данные, а декодер предназначен для восстановления данных источника из сжатых данных. Восстановленные данные, вырабатываемые декодером, могут либо абсолютно точно совпадать с исходными данными источника, либо незначительно отличаться от них.

Существуют два типа систем сжатия данных:

· системы сжатия без потерь информации (неразрушающее сжатие);

· системы сжатия с потерями информации (разрушающее сжатие).

Сжатие без потерь информации

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

Вектор данных источника X, подлежащих сжатию, представляет собой последовательность X = (x1, x2,… xn ) конечной длины. Отсчеты xi составляющие вектора X выбраны из конечного алфавита данных A. При этом размер вектора данных n ограничен, но он может быть сколь угодно большим. Таким образом, источник на своем выходе формирует в качестве данных X последовательность длиной n из алфавита A .

При решении задачи сжатия естественным является вопрос, насколько эффективна та или иная система сжатия. Поскольку, как мы уже отмечали, в основном используется только двоичное кодирование, то такой мерой может служить коэффициент сжатия r, определяемый как отношение

размер сжатых данных в битах k

Таким образом, коэффициент сжатия r = 2 означает, что объем сжатых данных составляет половину от объема данных источника. Чем больше коэффициент сжатия r, тем лучше работает система сжатия данных.

Наряду с коэффициентом сжатия r эффективность системы сжатия может быть охарактеризована скоростью сжатия R, определяемой как отношение

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

Сжатие с потерей информации

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

X ® Квантователь ® X q ® Неразрушающий кодер ® B (X q ) ® Декодер ® X*

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

Далее кодер подвергает неразрушающему сжатию вектор квантованных данных X q таким образом, что обеспечивается однозначное соответствие между X q и B(X q ) (для Xl q = Xm q выполняется условие B (Xl q ) = B (Xm q )). Однако система в целом остается разрушающей, поскольку двум различным векторам X может соответствовать один и тот же вектор X*.

Разрушающий кодер характеризуется двумя параметрами — скоростью сжатия R и величиной искажений D, определяемых как

R = k/n,

Параметр R характеризует скорость сжатия в битах на один отсчет источника, величина D является мерой среднеквадратического различия между X* и X.

Если имеются система разрушающего сжатия со скоростью и искажениями R1 и D1 соответственно и вторая система со скоростью R2 и искажениями D2, то первая из них лучше, если R1 R2 и D1 D2. Однако, к сожалению, невозможно построить систему разрушающего сжатия, обеспечивающую одновременно снижение скорости R и уменьшение искажений D, поскольку эти два параметра связаны обратной зависимостью. Поэтому целью оптимизации системы сжатия с потерями может быть либо минимизация скорости при заданной величине искажений, либо получение наименьших искажений при заданной скорости сжатия.

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

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

Пример 1. Предположим, что источник генерирует цифровое изображение (кадр) размером 512*512 элементов, содержащее 256 цветов. Каждый цвет представляет собой число из множества <0,1,2… 255>. Математически это изображение представляет собой матрицу 512х512, каждый элемент которой принадлежит множеству <0,1,2… 255>. (Элементы изображения называют пикселами).

В свою очередь, каждый пиксел из множества <0,1,2… 255>может быть представлен в двоичной форме с использованием 8 бит. Таким образом, размер данных источника в битах составит 8х512х512= 2 21 , или 2,1 Мегабита.

На жесткий диск объемом в 1 Гигабайт поместится примерно 5000 кадров изображения, если они не подвергаются сжатию (видеоролик длительностью примерно в пять минут). Если же это изображение подвергнуть сжатию с коэффициентом r = 10, то на этом же диске мы сможем сохранить уже почти часовой видеофильм!

Предположим далее, что мы хотим передать исходное изображение по телефонной линии, пропускная способность которой составляет 14000 бит/с. На это придется затратить 21000000 бит/14000 бит/с, или примерно 3 минуты. При сжатии же данных с коэффициентом r = 40 на это уйдет всего 5 секунд !

Пример 2. В качестве данных источника, подлежащих сжатию, выберем фрагмент изображения размером 4х4 элемента и содержащее 4 цвета: R = =»красный», O = «оранжевый», Y = «синий», G = «зеленый»:

R O Y R O O Y O O Y G Y Y Y G

Просканируем это изображение по строкам и каждому из цветов присвоим соответствующую интенсивность, например, R = 3, O = 2, Y = 1 и G = 0, в результате чего получим вектор данных X = (3,3,2,1,3,2,2,1,2,2,1,0,1,1,1,0).

Для сжатия данных возьмем кодер, использующий следующую таблицу перекодирования данных источника в кодовые слова (вопрос о выборе таблицы оставим на будущее):

Отсчет Кодовое слово 3 001 2 01 1 1 000

Используя таблицу кодирования, заменим каждый элемент вектора X соответствующей кодовой последовательностью из таблицы (так называемое кодирование без памяти). Сжатые данные (кодовое слово B(X)) будут выглядеть следующим образом:


Коэффициент сжатия при этом составит r = 32/31, или 1,03. Соответственно скорость сжатия R = 31/16 бит на отсчет.

Пример 3. Сравним два различных кодера, осуществляющих сжатие одного и того же вектора данных

Первый кодер — кодер без памяти, аналогичный рассмотренному в предыдущем примере (каждый элемент вектора X кодируется независимо от значений других элементов — кодер без памяти). Таблица кодирования для него выглядит следующим образом:

Символ Кодовое слово

Второй кодер при кодировании текущего символа учитывает значение предшествующего ему символа, таким образом, кодовое слово для текущего символа A будет различным в сочетаниях RA, DA и CA ( иными словами, код обладает памятью в один символ источника):

Символ, предыдущий символ Кодовое слово (A,-) 1 (B,A) (C,A) 10 (D,A) 11 (A,R) 1 (R,B) 1 (A,C) 1 (A,B) 1

Кодовые слова, соответствующие вектору данных X = ABRACADABRA, при кодировании с использованием этих двух таблиц будут иметь вид:

Таким образом, скорость сжатия при использовании кодера 1 (без памяти) составит 23/11 = 2,09 бита на символ данных, тогда как для кодера 2 — 13/11 = =1,18 бита на символ. Использование второго кодера, следовательно, является более предпочтительным, хотя он и более сложен.

1. Лидовский В.И. Теория информации. — М., «Высшая школа», 2002г. – 120с.

2. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для вузов. / В.И. Нефедов, В.И. Халкин, Е.В. Федоров и др. – М.: Высшая Школа, 2001 г. – 383с.

3. Цапенко М.П. Измерительные информационные системы. – М.: Энергоатом издат, 2005. — 440с.

4. Зюко А.Г. , Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. –368 с.

5. Б. Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003 г. – 1104 с.

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Кафедра РЭС Реферат на тему: «Энтропия сложных сообщений, избыточность источника. Цель сжатия данных и типы систем сжатия»

Моделирование процессов и систем (стр. 2 )

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8

Задачи исследования систем:

1. Расчет — определение значений параметров системы.

2. Анализ – изучение свойств функционирования системы.

3. Синтез – выбор структуры и параметров по заданным свойствам системы.

Пусть T = [t, t1] есть временной интервал моделирования системы S (интервал модельного времени).

Построение модели начинается с определения параметров и переменных, определяющих процесс функционирования системы.

Параметры системы это характеристики системы, остающиеся постоянными на всем интервале T.

Переменные бывают зависимые и независимые.

Независимые переменные есть, как правило, входные воздействия (в том числе управляющие)

ими могут быть также воздействия внешней среды.

называется фазовой траекторией системы, , где Xпространство состояний или фазовое пространство.

Последовательность изменения y(t) называется выходной траекторией системы.

Зависимые переменные есть выходные характеристики (сигналы)

Общая схема математической модели (ММ) функционирования системы может быть представлена в виде:

Множество переменных вместе с законами функционирования

называется математической моделью системы.

Если t непрерывно, то модель называется непрерывной, иначе – дискретной:

Если модель не содержит случайных элементов, то она называется детерминированной, в противном случае – вероятностной, стохастической.

Если математическое описание модели слишком сложное и частично или полностью неопределенно, то в этом случае используются агрегативные модели.

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

2.3. Имитация случайных величин и процессов

Моделирование случайных элементов в системах является одной из самых базовых задач математического моделирования.

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

Базовый датчик выдает независимые равномерно распределенные случайные величины:

· непрерывные в (0,1);

Типы базовых датчиков:

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

· псевдослучайные датчики строятся на основе детерминированного алгоритма, но полученные результаты мало отличны от случайных.

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

при заданном x0.

Рассмотрим формулу получения случайных чисел

характерную для линейной конгруэнтной последовательности случайных чисел, где

4. Выдача результатов моделирования и, по желанию пользователя, графика.

Этап 4. Проведение вычислительных экспериментов

Эксперимент 1. Поток инвестиций — постоянный и в каждый момент времени равенВ начальный момент капитал – 1 руб. Коэффициент амортизации — 0,0025. Найти величину основных фондов через 3 суток, если лаг равен 5 суток.

Решение. Воспользуемся формулой

хi+1 = хi + yj – m*хi, x0 = с, i = 0, 1, 2,3; j =0.

Здесь х0= с = 1 руб.; m = 0.0025; y0 = 10 000 руб.

yj выделяется раз в 5 суток.

х1 = х0 + y0 – m*х0 = 1 000 000 + 10 000 – 0.0025* 1 000 000 = 1 007 500 (руб.);

х2 = х1 – m*х1 = 1 007 500 – 0.0025* 1 007 500 =

1 004 981.25 (руб.);

х3 = х2 – m*х2 = 1 004 981.25 – 0.0025* 1 004 981.25 = 1 002 468.7968 (руб.).

Эксперимент 2. Основные фонды в момент времени t = 0 были равны 5 000. Через какое время общая их сумма превысит руб., если поток инвестиций постоянный равный 2000 руб., известно, что m = 0.02, T=3 ?

Эксперимент 3. Какую стратегию инвестиций лучше использовать, если величина инвестиций постоянная, в начальный момент капитал равен 100 000 и величина амортизации постоянная?

Этап 5. Модификация (развитие) модели

Модификация 1. Коэффициент амортизации можно взять в форме m = r – s*x(t), где r — коэффициент обновления фондов, s — коэффициент устаревания фондов, причем 0 r, s 1. При этом модель примет вид

Этой непрерывной, дифференциальной, динамической модели можно поставить в соответствие простую дискретную модель:

Алгоритмы Сжатия информации

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

Сжатие сокращает объем пространства, которое требуется для хранения файлов в ЭВМ, и количество времени, необходимое для передачи информации по каналу установ­ленной ширины пропускания. Это есть форма кодирования. Другими целями кодиро­вания являются поиск и исправление ошибок, а также шифрование. Процесс поиска и исправления ошибок противоположен сжатию — он увеличивает избыточность дан­ных, когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя из текста избыточность, сжатие способствует шифрованию, что затрудняет поиск шифра доступным для взломщика статистическим методом.

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

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

Что такое архивирование и зачем оно нужно

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

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

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

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

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

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

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

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

Ряд архиваторов позволяют создавать многотомные архивы, саморазворачивающиеся архивы, архивы, содержащие каталоги. Наиболее популярны и широко используются следующие архиваторы: ARJ, PKZIP/PKUNZIP, RAR, ACE, LHA, ICE, PAK, PKARC/PKXARC, ZOO, HYPER, AIN.

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

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

Существуют два основных метода архивации без потерь:

· алгоритм Хаффмана (англ. Huffman), ориентированный на сжатие последовательностей байт, не связанных между собой,

· алгоритм Лемпеля-Зива (англ. Lempel, Ziv), ориентированный на сжатие любых видов текстов, то есть использующий факт неоднократного повторения «слов» – последовательностей байт.

Практически все популярные программы архивации без потерь (ARJ, RAR, ZIP и т.п.) используют объединение этих двух методов – алгоритм LZH.

Терминология

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

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

Методы кодирования

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

Модели входного потока

Кодирование представляет собой лишь часть процесса упаковки. Не менее важно моделирование. Арифметическое кодирование имеет минимальную избыточность при заданном распределении. Но откуда берется это распределение? И о каком алфавите идет речь?Ответы на эти вопросы дает модель потока, представляющая собой некоторый способ определения распределения вероятностей при каждом поступлении очередного символа. Именно каждом, поскольку статические модели (в которых распределение не изменяется) в большинстве случаев не дают максимального качества сжатия. Гораздо больший интерес представляют так называемые адаптивные модели.Возможны различные подходы к этой проблеме: простейший из них — сбор статистики появления каждого символа независимо от других (моделирование источником Бернулли: вероятность появления символа не зависит от того, какие символы встретились перед ним). Возможно также использование марковской модели: сбор статистики появления каждого символа с учетом некоторого количества предыдущих символов (в марковском источнике первого порядка вероятность появления символа зависит только от одного последнего полученного символа, и т.д.). Марковские модели могут давать более точную картину источника, однако число состояний в них больше, соответственно больше объем хранимых таблиц частот. Кроме того, при использовании кодирования Хаффмана они могут даже ухудшить качество сжатия, поскольку порождаемые ими вероятности обычно хуже приближаются отрицательным степенями 2.

Моделирование и энтропия

Одним из наиболее важных достижений в теории сжатия за последнее десятиле­тие явилась идея разделения процесса на две части: на кодирование, при котором непосредственно производится сжатый поток битов, и на модели­рование, которое поставляет информацию кодированию. Эти две раздельные части названы кодированием и моделированием. Моделирование присваивает вероятности символам, а кодирование переводит эти вероятности в последовательность битов. К сожалению, последнее понятие нетрудно спутать, поскольку «кодирование» часто используют в широком смысле для обозначения всего процесса сжатия (включая моделирование). Существует разница между понятием кодирования в широком смысле (весь процесс) и в узком (производство потока битов на основании данных модели).

Связь между вероятностями и кодами установлена в теореме Шеннона кодирова­ния истоточника, которая показывает, что символ, ожидаемая вероятность по­явления которого есть p, лучше всего представить -log p битами. Поэтому сим­вол с высокой вероятностью кодируется несколькими битами, тогда как маловеро­ятный требует многих битов. Мы можем получить ожидаемую длину кода посредством усреднения всех возможных символов, даваемого формулой:

Это значение называется энтропией распределения вероятности, т.к. это мера ко­личества порядка (или беспорядка) в символах.

Задачей моделирования является оценка вероятности для каждого символа. Из этих вероятностей может быть вычислена энтропия. Очень важно отметить, что эн­тропия есть свойство модели. В данной модели оцениваемая вероятность символа иногда называется кодовым пространством, выделяемым символу, и соответствует распределению интервала (0,1) между символами, и чем больше вероятность симво­ла, тем больше такого «пространства» отбирается у других символов.

Наилучшая средняя длина кода достигается моделями, в которых оценки веро­ятности как можно более точны. Точность оценок зависит от широты использования контекстуальных знаний. Например, вероятность нахождения буквы «о» в тексте, о котором известно только то, что он на английском языке, может быть оценена на основании того, что в случайно выбранных образцах английских текстов 6% си­мволов являются буквами «о». Это сводится к коду для «о», длиной 4.17. Для ко­нтраста, если мы имеем фразу «to be or not t», то оценка вероятности появления буквы «о» будет составлять 99% и ее можно закодировать через 0.014 бита. Боль­шего можно достичь, формируя более точные модели текста. Практические модели лежат между двумя крайностями этих примеров.

Модель по существу есть набор вероятностей распределения, по одному на каждый контекст, на основании которого символ может быть закодирован. Контекс­ты называются классами условий, т.к. они определяют оценки вероятности. Нетри­виальная модель может содержать тысячи классов условий.

Илон Маск рекомендует:  Псевдокласс empty
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL