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


Содержание

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

  • повторить и обобщить понятие о кодировании текстовой информации.

1. Организационный момент, проверка домашнего задания

2. Ознакомление учащихся с понятие «сжатие информации» на примерах (см. слайды №2 и №3).

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

3. Метод Шеннона-Фано (по презентации Приложение 2, см. слайды №№ 4-9)

Как мы уже видели при решении задач, информацию нельзя сжимать до бесконечности. То есть в какой-то момент должна появиться своего рода граница, при сжатии дальше которой восстановление информации неоднозначно или просто невозможно. То есть хотелось бы, чтобы выбранный нами способ кодирования был оптимальным: с одной стороны, чтобы обеспечивалось максимально возможное сжатие, с другой стороны, чтобы записанная таким образом информация не теряла свою полноту. Одним из методов, обеспечивающих такое оптимальное кодирование отдельных символов является метод Шеннона-Фано.
Суть метода состоит в следующем: пусть дан некоторый алфавит (конечный набор символов, который будет использован для написания текста). Пусть также дано сообщение. Какие-то символы в сообщении обычно встречаются чаще, какие-то – реже. Для часто используемых символов создадим более короткие коды, для реже используемых – длинные (слайд №4 – частота использования букв русского языка).
Для начала, в качестве повторения, оценим (например, по формуле Хартли) сколько бит необходимо отвести для записи кода одного символа, и создадим «обычные» коды равной длины (слайд №5).

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

Далее, разделим таблицу на две части, чтобы сумма долей всех символов в одной была как можно ближе к сумме долей всех символов другой. Пусть коды всех символов из первой части начинаются на 0, коды всех символов из второй – на 1 (слайд №7). Если в какой-то части находится более одного символа, то повторим для нее процесс деления, находя вторую, третью и так далее цифры кода. Как только для всех символов найдены коды – процесс завершен (слайды №8 и №9)
Осталось только подчитать количество бит, которые необходимы для представления сообщения в новом коде (слайд №10).

4. Закрепление пройденного материала, решение задач (слайд №11)

Алгоритмы сжатия и компрессии

Опрос

Новички

Словарные методы

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

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

В результате выходной файл состоит из индексов и рядов слов, поэтому необходимо уметь делать различие между ними. Один возможный способ — это добавление к записываемому в файл образчику еще один дополнительный бит. В принципе, 19-битовый индекс будет достаточен для точного указания слов в словаре объема 2 19 = 524288 элементов. Поэтому, если прочитанное слово найдено в словаре, то можно записать 20-битную ссылку, состоящую из флагового бита (возможно, нулевого), за которым следует 19 битов индекса. Если данное слово не обнаружено в словаре, записывается флаг 1, потом длина слова и, наконец, само это слово.

Пример: Предположим, что слово bet находится в словаре под номером 1025. Тогда оно будет закодировано 20-битовым числом 010000000010000000001. Пусть слово xet не обнаружено в словаре. Тогда в выходной файл будет записана последовательность битов 1|0000011|01111000|01100101|01110100. В этом четырехбайтовом числе 7-битовое поле 0000011 означает, что за ним следуют еще три байта.

Если считать, что размер записывается в виде 7-битового числа и что средний размер слова состоит из 5 букв, то несжатое слово будет в среднем занимать 6 байт (= 48 бит) в выходном файле. Сжатие 48 бит в 20 является замечательным, при условии, что это делается достаточно часто. При этом, возникает вопрос: «Сколько совпадений слов надо обнаруживать в словаре, чтобы иметь общее сжатие?». Пусть вероятность обнаружения слова в словаре равна Р. После чтения и сжатия N слов размер выходного файла будет равен N(20P + 48(1 — Р)) = N(48 — 28Р). Размер входного файла равен (при условии, что слово имеет 5 букв) 40N. Тогда сжатие будет достигаться, если N(48 — 28Р) 0.29. Следовательно, надо иметь 29% или больше успешных нахождений слов в словаре для положительного сжатия.

Пример: Если вероятность обнаружения выше, например, Р = = 0.9, то размер выходного файла будет равен 7V(48 — 28P) = 7V(48 — —25.2Р) = 22.8N. Размер входного файла равен, как и раньше, 40N. Фактор сжатия равен 40/22.8 « 1.75.

До тех пор, пока входной файл содержит английский текст, большинство слов будут обнаружены в полмиллионном словаре. Для других типов данных, разумеется, это не будет выполняться. В файле, содержащем код компьютерной программы будут находиться «слова» типа cout, xor, malloc, которые, возможно, не удастся обнаружить в словаре английского языка. А бинарный файл, если его рассматривать в ASCII кодах, обычно, содержит всякий «мусор», который едва ли удастся обнаружить в этом словаре. В результате произойдет расширение вместо сжатия.

Все это говорит о том, что статический словарь — не самый лучший выбор для общего алгоритма сжатия. Однако в ряде специальных случаев, это будет хорошим методом. Возьмем сеть компьютерных магазинов. Их файлы во множестве будут содержать слова типа nut, bolt, paint. В то же время, слова peanut, lightning, painting будут встречаться реже. Поэтому специальное компрессионное программное обеспечение этой фирмы может использовать очень маленький специализированный словарь, состоящий всего из нескольких сотен слов. Каждый сетевой компьютер будет иметь копию этого словаря, что позволит легко сжимать файлы и пересылать их по сети между магазинами и офисами фирмы.

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

1. Алгоритм использует только операции над последовательностями строк типа поиска и сравнения и не использует арифметические вычисления.

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

Большая честь кля ученого, когда его имя присваивается научному открытию, методу или явлению. Еще более почетно, когда имя присваивается целому научному направлению. Как раз это случилось с Якобом Зивом (Jacob Ziv) и Абрахамом Лемпэлом (Abraham Lempel). В 1970 году эти ученые разработали два первых метода, называемые LZ77 и LZ78, кля словарного сжатия данных. Их замечательные идеи вдохновили многих исследователей, которые стали улучшать, обобщать и комбинировать их с другими методами (например, с RLE или со статистическим методом) кля создания многих широко используемых на практике алгоритмов сжатия без потери информации для компрессии текстов, изображений и звука.

Далее в этой главе описано несколько общих LZ методов компрессии и показано, как они развивались из основополагающих идей Зива и Лемпэла.

Методы сжатия архиваторов

Программы сжатия данных (архиваторы): назначение и особенности использования

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

Архивация имеет четыре основные практические приложения:

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

2. Возможность записи на жесткий диск большего объемаинформации;

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

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

Методы сжатия архиваторов

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

1. Кодирование длин серий.

Последовательная серия одинаковых элементов данных заменяется на два символа: элемент и число его повторений.

Например, строку ААААБББВВГГГГ, человек скорее всего запоминает как 4А3Б2В4Г. На аналогичных, только более развитых принципах, основано действие специальных программ – архиваторов

2. Словарный метод.

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

Основным параметром словарного метода является размер словаря. Чем больше словарь, тем больше эффективность.

3. Энтропийный метод

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

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

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

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

5. Непрерывные блоки или непрерывный режим ( Solid mode — непрерывный режим).

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

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше. 8988 — | 7235 — или читать все.

Сжатие информации: как это делается

Мы каждый день пользуемся различными архиваторами: zip, rar, ace окружают нас повсюду.
Графические и звуковые файлы тоже содержат сжатые данные. Если же нам нужно использовать
сжатие в своей проге, то мы используем различные dll’ки, многие из которых платные.
Шареварность — это не единственное свойство программных компонентов, мешающих их нормальному
использованию. Если, например, сжимать waw или bmp-файл архиватором, то
он будет значительно уступать специальному методу для конкретного типа данных, т.е.
метод должен учитывать особенности конкретного типа данных. Поэтому полезно уметь реализовывать сжатие самостоятельно.
В этой статье я расскажу, как вообще сжимать информацию и рассмотрю один из методов сжатия.

Классификация методов сжатия

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

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

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

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

Отметим один момент, который почему-то неочевиден для некоторых «теоретиков».
Правило кодирования определяется вероятностной структурой данных, а значит, декомпрессор
должен до начала раскодирования уже знать её. Если же мы получаем её из статистики конкретного
сообщения (так оно сжимается лучше), то её придется передать явно или неявно вместе со сжатым
сообщением, и еще неизвестно, будет ли общий размер меньше.

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

H = -Sum(p[i] * log(p[i]))

где Sum — сумма по i, p[i] — вероятность i-го сообщения, log — логарифм по основанию 2.
Энтропия сложного сообщения равна сумме энтропий входящих в него простых сообщений.

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

Этот метод в корне отличается от всех рассмотренных ранее методов. Его главное
преимущество в том, что достигается теоретический предел сжатия. Рассмотрим этот метод подробно. Всё сообщение целиком представляется одним числом по следующему правилу. Число должно
находиться в интервале от 0 до 1. Этот интервал делится на части, пропорциональные вероятностям
значений первого символа. Выбирается часть, соответствующая символу и делится на части по
вероятностям значений второго символа и т.д.

новая_нижняя_граница = нижняя_граница + ширина * S[i]
новая_ширина = ширина * p[i]

где p[i] — вероятность i-го символа, S[i] — сумма вероятностей символов с номерами
меньше i.

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

Проект, прикрепленный к этой статье, компилируется на Visual Studio .NET.
Это реализация арифметического кодирования, сжимающая файлы, рассматривая байты как символы.
Содержимое файла рассматривается как марковский процесс 1-го порядка, т. е. распределение
вероятностей символов зависит от предыдущего символа. Класс CMarkovProcessDef обрабатывает
данные, сохраненные в ресурсе в специальном формате. Эти данные сгенерированы по результатам
обработки большого количества текстов, т. е. текстовые файлы, скорее всего, будут сжиматься
хорошо, а если попытаться сжать какой-нибудь бинарник, то размер «сжатого» файла будет больше
исходного. Для того, чтобы получить метод сжатия для своего типа данных, нужно заменить данные о
вероятностях символов. Кроме того, символ — это не обязательно байт несжатых данных. Например,
если есть столбец таблицы, где значения должны быть уникальными, то каждое значение — это
символ, а после того, как символ встречается, сбрасываем его вероятность в ноль. Нижняя граница и ширина интервала хранятся в целочисленных переменных dwBuf1 и dwBuf2.
Если после обработки очередного символа старшие байты границ окажутся равными
(заметим, что это не то же самое, что если старший байт ширины равен нулю), то
соответствующий байт окончательного результата будет равен этому значению, и его можно
записать в файл. Запишем его и сдвинем буферы на 1 байт. При распаковке кроме переменных, обрабатываемых так же, как при упаковке, нам
понадобится еще одна, где будет информация из файла. Для того, чтобы определить очередной символ, нужно
найти символ с наименьшим номером, такой, что S[n] * dwBuf2 >= dwBuf3, т.е. P[n] >= dwBuf3 / dwBuf2. При работе с целыми числами возникает проблема: мы представляем вероятности (дробные
числа от 0 до 1) целочисленными переменными (0x100000000 * p). Для умножения и деления на них нужны
особые процедуры: при умножении берем старшее 32-битное слово 64-битного результата, а при делении
делим число, умноженное на 2^32. Компилятор не может, умножитв DWORD на DWORD, поместить результат
в 64-битную переменную — это недостаток языка С++. Поэтому пришлось написать специальные процедуры
на ассемблере.

Илон Маск рекомендует:  Общие принципы построения систем защиты от копирования

void CArithmCompressorDlg::OnBnClickedCompress()
<
CFileDialog dlg1(TRUE);
if (dlg1.DoModal() != IDOK) return;
CFileDialog dlg2(FALSE, «compressed», 0, OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT, «*.compressed|*.compressed|All files|*.*||»);
if (dlg2.DoModal() != IDOK) return;

CFile file1(dlg1.GetPathName(), CFile::modeRead);
CFile file2(dlg2.GetPathName(), CFile::modeCreate | CFile::modeWrite);

BYTE b;
ULONGLONG fs = file1.GetLength();

file2.Write(&fs, 8); // Запишем размер исходного файла

// m_mpd — это объект класса CMarkovProcessDef
m_mpd.ResetProcess(); // Сбросим данные о предшествующих символах

// Здесь начинается сжатие
// Начальный интервал — от 0x00000000 до 0xFFFFFFFF
DWORD dwBuf1 = 0; // Нижняя граница
DWORD dwBuf2 = 0xFFFFFFFF; // Ширина
DWORD dww; // Временная переменная

Замените эту функцию на свою реализацию и получите метод сжатия для вашего типа данных.
*/
dwBuf1 += dww;
if (b Если старший байт буфера определен
<
file2.Write(((LPBYTE)&dwBuf1)+3, 1); // Записываем его
dwBuf1 = dwBuf1 И сдвигаем буфер
dwBuf2 = dwBuf2 PushSymbol(b, 0) перемещает внутренний указатель на распределение для следующего символа
*/
m_mpd.PushSymbol(b, 0);
>
file2.Write(((LPBYTE)&dwBuf1)+3, 1); // Записываем последний байт
// Вот и всё
// Закрываем файлы
file1.Close();
file2.Close();
>


void CArithmCompressorDlg::OnBnClickedDecompress()
<
CFileDialog dlg1(TRUE, «compressed», 0, 0, «*.compressed|*.compressed|All files|*.*||»);
if (dlg1.DoModal() != IDOK) return;
CFileDialog dlg2(FALSE);
if (dlg2.DoModal() != IDOK) return;

CFile file1(dlg1.GetPathName(), CFile::modeRead);
CFile file2(dlg2.GetPathName(), CFile::modeCreate | CFile::modeWrite);

if (file1.Read(&fs, 8) != 8) return; // Читаем длину извлекаемого файла

DWORD dwBuf1 = 0, dwBuf2 = 0xFFFFFFFF, dwBuf3, dww;

// Читаем первые 4 байта
// Нужно поместить байты в переменную не в том порядке, в каком они в файле,
// поэтому читаем их по отдельности
for (int j = 3; j >= 0; j—) if (file1.Read(((LPBYTE)&dwBuf3)+j, 1) == 0) ((LPBYTE)&dwBuf3)[j] = 0xFF;

// Поиск методом половинного деления
do
<
m = (l+h)/2;
if (h Вычисляем новый интервал
if (m > 0) dww = MulHigh(m_mpd.GetDistribution(m-1), dwBuf2); else dww = 0;
dwBuf1 += dww;
dwBuf3 -= dww;
if (m Пишем символ
m_mpd.PushSymbol(m, 0);

DWORD CArithmCompressorDlg::MulHigh(DWORD dw1, DWORD dw2)
<
/*
Эта функция возвращает старшее двойное слово
произведения данных двойных слов
*/
DWORD r;
_asm
<
mov eax, dw1;
mul dw2;
mov r, edx;
>
return r;
>

DWORD CArithmCompressorDlg::DivLarge(DWORD hi, DWORD lo, DWORD dw)
<
/*
Эта функция делит 64-битное беззнаковое целое (hi;lo)
на 32-битное
*/
DWORD r;
_asm
<
mov eax, lo;
mov edx, hi;
div dw;
mov r, eax;
>
return r;
>

Модели и алгоритмы контекстно-словарного сжатия текстовых данных : Применительно к системам электронного обучения

Содержимое

Оглавление
ВВЕДЕНИЕ.
ГЛАВА 1. АНАЛИЗ МЕТОДОВ СЖАТИИ ИНФОРМАЦИИ.
1.1. Предварительные замечания
1.2. Модели словарного сжатия.
1.3. Модели контекстного сжатия.
1.3.1. Модели с фиксированным контекстом
1.3.2. Контекстуальносмешанные модели
1.3.3. Вероятность ухода
1.3.4. Исключения.
1.3.5. Алфавиты.
1.4. Другие методы статистического моделирования.
1.4.1. Динамическое сжатие Маркова
1.4.2. Г рамматические модели.
1.4.3. Модели новизны.
1.4.4. Выводы по первой главе.
ГЛАВА 2. КОНТЕКСТНОСЛОВАРНЫЕ МОДЕЛИ СЖАТИЯ
2.1. Предварительные замечания
2.2. Сжатие текстовых файлов
2.3. Структурная модель представления сжатия текстовой информации .
2.4. Постановка задачи приведения к предложенной схеме
структурированного вида.
2.5. Модель сжатия использующий контекстнословарный метод
2.5.1. Модель хранения сжатого текста.
2.5.2. Древовидная модель словаря.
2.5.3. Модель словаря морфем
2.6. Выводы по второй главе.
ГЛАВА 3. АЛГОРИТМЫ КОНТЕКСТНОСЛОВАРНОГО СЖАТИЯ ДАННЫХ НА ОСНОВЕ ПРЕДЛОЖЕННЫХ МОДЕЛЕЙ.
3.1. Предварительные замечания
3.2. Приведение информации к структурированному виду
. 3.3. Преобразование словаря.
3.3.1. Разбиение слова на слоги
3.3.2. Разбиение на составные части слова
3.3.3. Древовидное представление структуры словаря.
3.4. Оценка построение структуры словаря от способа разложения слов.
3.5. Кодирование текста с использованием полученного словаря
3.5.1. Построение кодов переменной длины.
3.5.2. Применение кодирования контекстных индексов арифметического
кодирования
3.6. Оценка эффективности полученных кодов алгоритма кодирования с
помощью словаря
3.6.1. Стоимость кодирования текста
3.6.2. Оценка объема необходимой памяти
3.7. Управление распределением памяти.
3.8. Выводы по третьей главе
ГЛАВА 4. ПРОГРАММНЫЙ КОМПЛЕКС КОНТЕКСТНОСЛОВАРНОГО СЖАТИЯ ТЕКСТОВЫХ ДАННЫХ V I
4.1. Основные требования к техническому облику программного
комплекса V i .
4.2. Область применения программного комплекса
4.3. Проблемы существующих систем.
4.4. Задачи разработки программного комплекса.
4.5. Этапы разработки программного комплекса
4.6. Реализация блока сжатия файлов.
4.6.1. Реализация блока .
4.6.2. Реализация блока .
4.7. Сравнительная оценка эффективности.
4.7.1. Тестовые данные
4.7.2. Методика сравнения.
4.7.3. Результаты сравнения
4.8. Пример преобразования и кодирования слов.
4.9. Выводы по четвертой главе
ПРИЛОЖЕНИЕ 1
Листинг V.
ПРИЛОЖЕНИЕ 2.
Акт внедрения
Иллюстрации
Рис. 1 Модель сжатия реляционным словарем
Рис. 2 Модель сжатия динамическим словарем.
Рис. 3 Модель контекстного сжатия
Рис. 4 Операция клонирования в .
Рис. 5. Начальная модель ДМС с одним состоянием
Рис. 6. Более сложная начальная модель.
Рис. 7. Вероятностная грамматика для круглых скобок
Рис. 8 Структурная модель представления сжатия текстовой информации
Рис. 9 Модель сжатия контекстнословарного метода
Рис. Сравнение представления словарей.
Рис. Улучшенная модель представления словаря
Рис. . Модель сжатия текстового файла
Рис. Модель представления текста в естественных языках
Рис. Модель представления словаря после разбиения слов на слоги.
Рис. Модель программного комплекса V i .
Рис. Реализация блока сжатия текстового файла.
Рис. Реализация распаковки тестового файла
Рис. Результаты сравнения программ сжатия для тестового набора файлов.
Рис. График сравнения коэффициента сжатия от языковых особенностей
Введение
Актуальность

Доставим любую диссертацию от 2002 г. Для заказа напишите нам интересующую Вас тему и год защиты на почту: dissertation.com.ua@gmail.com

Поздравляем Вас с праздником весны.

Желаем чтобы в каждой ситуации вы чувствовали себя женщиной!

Желаем всем здоровья , счастья , творческих успехов!

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

Аннотация научной статьи по автоматике и вычислительной технике, автор научной работы — Поддубный Александр Петрович, Холуев Максим Александрович, Галактионов Николай Сергеевич

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

Похожие темы научных работ по автоматике и вычислительной технике , автор научной работы — Поддубный Александр Петрович, Холуев Максим Александрович, Галактионов Николай Сергеевич,

Текст научной работы на тему «Использование файла в качестве избыточного словаря для препроцессинга данных на основе словарных методов сжатия»

А. П. Поддубный, М. А. Холуев, Н. С. Галактионов

ИСПОЛЬЗОВАНИЕ ФАЙЛА В КАЧЕСТВЕ ИЗБЫТОЧНОГО СЛОВАРЯ ДЛЯ ПРЕПРОЦЕССИНГА ДАННЫХ НА ОСНОВЕ СЛОВАРНЫХ МЕТОДОВ СЖАТИЯ

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

Ключевые слова: архивация данных, сжатие без потерь, словарный метод.

Abstract. In article methods of dictionary compression of the data, their characteristics and feature of realization. Article contains classification of dictionary methods of compression of the data. Article also contains algorithm of compression of the data which assumes using file as the dictionary of surplus for compression of the data. Article also contains the table of properties of methods witch works with a preprocessor, which works on the basis of the given algorithm.

Keywords: archiving of the data, impression lost-free, dictionary method.

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

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

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

1. Использование словаря в словарных методах сжатия

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

К основным методам препроцессинга относят:

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

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

Выделяют несколько стратегий построения словаря:

— статическая, т.е. словарь строится заранее и полностью известен как препроцессору, так и постпроцессору;

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

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

При сжатии текстов в качестве блоков обычно используются [1]:

— последовательности из двух символов (биграфы);

— пары букв, фонетически эквивалентных одному звуку;

— пары букв «согласная — гласная» или «гласная — согласная»;

— последовательности из п символов (п-графы).

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

— последовательности, чаще всего встречающиеся в сжимаемом тексте или в текстах определенного класса;

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

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

Стратегия «Словарь п-графов» получила наибольшее распространение в современных архиваторах. Идея заключается в использовании статического словаря, состоящего из последовательностей символов длиной от двух до небольшого числа п (обычно 4-5). В большинстве случаев размер словаря равен примерно 100 таким фразам. К достоинствам данного типа словаря можно отнести:

— обеспечение существенного прироста степени сжатия текстов;

Небольшой размер словаря обусловлен двумя причинами:

— это упрощает кодирование блоков данных словаря;

— дальнейшее увеличение размера словаря улучшает сжатие лишь незначительно (справедливо для BWT и в меньшей степени для Ь2) либо даже вредит в большинстве случаев (справедливо для РРМ).

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

2. Использование избыточного словаря для препроцессинга данных

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

Рис. 1. Стандартная схема кодирования данных

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

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

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

Идея разработанного алгоритма заключается в том, что сжатие осуществляется посредством дополнительного файла, который и будет являться избыточным словарем для первого. В общем виде необходимы два однотипных файла. Первый файл (сжимаемые данные) с именем /Ие1 и второй файл (служебный), названый ёШюпагуШе. При этом /г1е1 при препроцессинге делится на N равных частей объемом S байт (рис. 2).

При каждом шаге работы программы сравнение идет только с одним блоком файла/г!е1. Файл ЛШопагуШе при этом сканируется полностью (рис. 3).

При нахождении совпадения внутри блока совпавший участок меняется на служебный блок (рис. 4). Из рис. 4 видно, что замена может производиться только при S i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

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

Свойства методов при работе с препроцессором

Параметр Метод Однородные данные (текст) Однородные данные (исходные тексты программ) Неоднородные данные Данные с малой избыточностью (предварительно сжатые файлы)

Степень сжатия РРМ Высокая Высокая Высокая Средняя

BWT Близкая к РРМ Близкая к РРМ — —

ьг77 Средняя Высокая Близкая к РРМ —

Скорость кодирования BWT Средняя Низкая Средняя Низкая

РРМ — Если не использовать моделирование — средняя Низкая —

ьг77 Средняя, а при малом словаре -высокая Низкая, при малом словаре -средняя Средняя Средняя

Скорость декодиро- вания ьг77 Примерно в 10 раз выше скорости кодирования; разница еще больше на избыточных данных

РРМ Обычно на 5-10 % медленнее кодирования

BWT В 2-4 раза выше скорости кодирования

Окончание табл. 1

Требуемый объем памяти при сжатии BWT Постоянен при сжатии данных любого типа

РРМ Варьируется в широких пределах в зависимости от сложности моделирования и порядка модели; вырастает для неоднородных данных; в зависимости от структуры хранения контекстной информации может увеличиваться для малоизбыточных данных

ьг77 Пропорционален размеру словаря

Требуемый объем памяти при разжатии ьг77 Минимален


РРМ Максимальный; если процесс моделирования симметричен, то примерно равен расходу памяти при сжатии

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

Рис. 5. Синтезированная схема для архивации данных

Особенность данной схемы заключается в том, что кодер на первом этапе выполняет роль «препрепроцессора» и позволяет получить данные, «удобные для сжатия» для препроцессора. Данная схема будет эффективно работать, если использовать преобразование BWT на первом этапе. Эффективность достигается за счет того, что после преобразования BWT данные будут упорядочены и позволят повысить степень сжатия, однако это может привести к значительным потерям во времени. В качестве оконечного кодера можно использовать как РРМ, так и Ь277 в зависимости от типа сжимаемых данных. Так как разработанный алгоритм взаимодействует с двумя файлами, то для большей результативности сжатия стадию «препрепроцессинга» должны пройти оба файла (рис. 6).

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

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

Даная система будет иметь преимущество при создании больших видеотек и в Интернете.

Рис. 6. Синтезированная схема архивации для двух файлов Заключение

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

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

1. Ватолин, Д. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. — М. : Диалог-МИФИ, 2003. — 384 с.

2. Кадач, А. В. Эффективные алгоритмы неискажающего сжатия текстовой информации : дис. . канд. физ.-мат. наук / Кадач А. В. ; Ин-т систем информатики им. А. П. Ершова. — М., 1997. — 187 с.

Поддубный Александр Петрович аспирант, Российский государственный университет инновационных технологий и предпринимательства

Poddubny Alexander Petrovich Postgraduate student, Russian State University of innovative technologies and entrepreneurship

Холуев Максим Александрович инженер, ОАО «НПП «Рубин»; аспирант, Российский государственный университет инновационных технологий и предпринимательства

Галактионов Николай Сергеевич инженер, ОАО «НПП «Рубин»; аспирант, Российский государственный университет инновационных технологий и предпринимательства

Kholuev Maxim Alexandrovich Engineer, research and production enterprise “Rubin”; postgraduate student, Russian State University of innovative technologies and entrepreneurship

Galaktionov Nikolay Sergeevich

Engineer, research and production enterprise “Rubin”; postgraduate student, Russian State University of innovative technologies and entrepreneurship

УДК 004.82 : 004.4’2 Поддубный, А. П.

Использование файла в качестве избыточного словаря для препро-цессинга данных на основе словарных методов сжатия I А. П. Поддубный, М. А. Холуев, Н. С. Галактионов II Известия высших учебных заведений. Поволжский регион. Технические науки. — 2010. — № 4 (16). — С. 47-54.

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

Wikimedia Foundation . 2010 .

Смотреть что такое «Методы сжатия с использованием словаря» в других словарях:

Метод сжатия с использованием словаря — Метод сжатия с использованием словаря разбиение данных на слова и замена их на индексы в словаре. Этот метод является наиболее распространенным подходом для сжатия данных в настоящее время. Является естественным обобщением RLE. В наиболее… … Википедия

LZ77 — и LZ78 алгоритмы сжатия без потерь, опубликованные в статьях Абрахама Лемпеля (англ.) и Якоба Зива (англ.) в 1977 и 1978 годах. Эти алгоритмы наиболее известные варианты в семействе LZ*, которое включает в себя также LZW, LZSS,… … Википедия

Алгоритм Лемпеля — Алгоритм Лемпеля Зива Велча (Lempel Ziv Welch, LZW) это универсальный алгоритм сжатия данных без потерь, созданный Абрахамом Лемпелем (англ. Abraham Lempel), Якобом Зивом (англ. Jacob Ziv) и Терри Велчем… … Википедия

ROLZ — (от англ. Reduced Offset LZ алгоритм Лемпела Зива с сокращёнными смещениями) словарный алгоритм сжатия данных, близкий к LZ77, но использующий некоторые контекстные приёмы для уменьшения числа активных смещений. Само понятие ROLZ… … Википедия

LZMA — (англ. Lempel Ziv Markov chain Algorithm) алгоритм сжатия данных, разрабатываемый с 2001 года. Используется в архиваторе 7 Zip для создания сжатых архивов в формате 7z. Алгоритм основан на схеме сжатия данных по словарю, сходной с… … Википедия

LZO — это алгоритм сжатия данных, разработанный для достижения максимальной скорости распаковки. LZO это аббревиатура от фамилий разработчиков: Lempel Ziv Oberhumer (Лемпель Зив Оберхеймер). Это алгоритм сжатия без потерь и его базовая реализация … Википедия

LZJB — LZJB алгоритм сжатия данных без потерь, изобретенный Джефом Бонвиком (Jeff Bonwick) для сжатия аварийных дампов программ и данных в ZFS. Этот алгоритм включает множество исправлений к алгоритму LZRW1, являющимся членом семейства алгоритмов… … Википедия

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

Синтез речи — Синтез речи в широком смысле восстановление формы речевого сигнала по его параметрам[1]; в узком смысле формирование речевого сигнала по печатному тексту. Синтезом речи прежде всего называется все, что связано с… … Википедия

Бинарное изображение — Пример бинарного изображения, записанного байтами, где 1 бит представляет 1 пиксель (двоичный, шестнадцатеричный, графический виды) 11111110 01111110 11100011 11000011 00011000 11110011 11111110 00011000 11011011 11000011 00011000 11001111… … Википедия

Двоичное изображение — Пример бинарного изображения, записанного байтами, где 1 бит представляет 1 пиксел (двоичный, шестнадцатеричный, графический виды) 11111110 01111110 11000011 11000011 00011000 11110011 11111110 00011000 11011011 11000011 00011000 11001111… … Википедия

Метод контекстного моделирования (CM)

сокращение от context modeling — контекстное моделирование.

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

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

PPM

PPM (Prediction by Partial Matching)

предсказание по частичному совпадению.

Это особый подвид контекстного моделирования. Предсказание выполняется на основании определенного количества предыдущих элементов данных. Основным параметром является порядок модели, который задает это количество элементов. Чем больше порядок модели, тем выше степень сжатия, но требуется больше оперативной памяти для хранения данных модели. Если оперативной памяти недостаточно, то такая модель с большим порядком показывает низкие результаты. Метод PPM особенно эффективен для сжатия текстовых данных.

Предварительные преобразования или фильтрация

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

Метод сортировки блока данных (BWT)

сокращение от Burrows Wheeler Transform — по имени авторов.

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

Непрерывные блоки или непрерывный режим (Solid mode)

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

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

Сегментирование

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

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

· Первым в списке это WinRAR. WinRAR – это самый популярный в мире архиватор отечественной разработки. Алгоритм сжатия архиватора WinRAR является лучшим из всех остальных. Качественное сжатие файлов, понятный интерфейс, поддержка всех форматов для архивации. WinRAR полностью поддерживает форматы ZIP и RAR. Так же у него есть возможность создавать самораспаковывающиеся архивы, такие как SFX.

· Второй – это 7-Zip. 7-Zip имеет свойство сжатия файлов в формат 7z (считается, что этот формат сжимает информацию с очень большой степенью, то есть им можно архивировать файлы большого размера: игры, Blu-Ray фильмы и т.п.).

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

.Классификация антивирусных программ

Виды антивирусных программ

Евгений Касперский в 1992 году использовал следующую классификацию антивирусов в зависимости от их принципа действия (определяющего функциональность):

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

· Ревизоры (класс, близкий к IDS) — запоминают состояние файловой системы, что делает в дальнейшем возможным анализ изменений.

· Сторожа (мониторы) — отслеживают потенциально опасные операции, выдавая пользователю соответствующий запрос на разрешение/запрещение операции.

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

Современные антивирусы сочетают все вышесказанные функции.

Антивирусы так же можно разделить на:

· Продукты для домашних пользователей:

· Комбинированные продукты (например, к классическому антивирусу добавлен антиспам, файрвол, антируткит и т. д.);

· Антивирусы на рабочих станциях («endpoint»).

КЛАССИФИКАЦИЯ КОМПЬЮТЕРНЫХ ВИРУСОВ

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

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

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

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

Физическая структура компьютерного вируса достаточно проста. Он состоит из головы и, возможно, хвоста. Под головой вируса понимается его компонента, получающая управление первой. Хвост – это часть вируса, расположенная в тексте зараженной программы отдельно от головы. Вирусы, состоящие из одной головы, называют несегментированными, тогда как вирусы, содержащие голову и хвост, — сегментированными.

Наиболее существенные признаки компьютерных вирусов позволяют провести следующую их классификацию.

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

1 По среде обитания вируса

2 По способу заражения


3 По деструктивным возможностям

4 По особенностям алгоритма работ

По среде обитания вирусы подразделяются на:

* Файловые вирусы — вирусы поражающие исполняемые файлы, написанные в различных форматах. Соответственно в зависимости от формата, в котором написана программа это будут EXE или COM вирусы.

* Загрузочные вирусы — вирусы поражающие загрузочные сектора (Boot сектора) дисков или сектор содержащий системный загрузчик(Master Boot Record) винчестера.

* Сетевые вирусы — вирусы, распространяющиеся в различных компьютерных сетях и системах.

* Макро вирусы — вирусы поражающие файлы Microsoft Office

* Flash — вирусы — вирусы поражающие микросхемы FLASH памяти BIOS.

По способу заражения вирусы делятся на:

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

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

По деструктивным возможностям вирусы подразделяются на:

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

* Неопасные вирусы — вирусы, которые проявляют себя в выводе различных графических, звуковых эффектов и прочих безвредных действий.

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

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

По особенностям алгоритма работы вирусы можно подразделить на:

* Вирусы спутники(companion) — эти вирусы поражают EXE-файлы путем создания COM-файла двойника, и поэтому при запуске программы запустится, сначала COM-файл с вирусом, после выполнения своей работы вирус запустит EXE-файл. При таком способе заражения «инфицированная» программа не изменяется.

* Вирусы «черви» (Worms) — вирусы, которые распространяются в компьютерных сетях. Они проникают в память компьютера из компьютерной сети, вычисляют адреса других компьютеров и пересылают на эти адреса свои копии. Иногда они оставляют временные файлы на компьютере но некоторые могут и не затрагивать ресурсы компьютера за исключением оперативной памяти и разумеется процессора.

* «Паразитические» — все вирусы, которые модифицируют содержимое файлов или секторов на диске. К этой категории относятся все вирусы не являются вирусами-спутниками и вирусами червями.

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

* «Полиморфные» (самошифрующиеся или вирусы-призраки, polymorphic) — вирусы, достаточно трудно обнаруживаемые вирусы, не имеющие сигнатур, т.е. не содержащие ни одного постоянного участка кода. В большинстве случаев два образца одного и того же полиморфного вируса не будут иметь ни одного совпадения. Это достигается шифрованием основного тела вируса и модификациями программы-расшифровщика.

* «Макро-вирусы» — вирусы этого семейства используют возможности макроязыков, встроенных в системы обработки данных (текстовые редакторы, электронные таблицы и т.д.). В настоящее время наиболее распространены макро-вирусы, заражающие текстовые документы редактора Microsoft Word.

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

По режиму функционирования:

* резидентные вирусы (вирусы, которые после активизации постоянно находятся в оперативной памяти компьютера и контролируют доступ к его ресурсам);

* транзитные вирусы (вирусы, которые выполняются только в момент запуска зараженной программы).

По объекту внедрения:

* файловые вирусы (вирусы, заражающие файлы с программами);

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

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

* командные файлы и файлы конфигурации;

* составляемые на макроязыках программирования, или файлы, содержащие макросы (макровирусы — разновидность компьютерных вирусов разработанных на макроязыках, встроенных в такие прикладные пакеты ПО, как Microsoft Office );

* файлы с драйверами устройств;

* файлы с библиотеками исходных, объектных, загрузочных и оверлейных модулей, библиотеками динамической компоновки и т.п.

Загрузочные вирусы подразделяются на вирусы, заражающие:

* системный загрузчик, расположенный в загрузочном секторе и логических дисков;

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

По степени и способу маскировки:

* вирусы, не использующие средств маскировки;

* stealth-вирусы (вирусы, пытающиеся быть невидимыми на основе контроля доступа к зараженным элементам данных);

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

В свою очередь, MtE-вирусы делятся:

* на обычные вирусы-мутанты, в разных копиях которых различаются только зашифрованные тела, а дешифрованные тела вирусов совпадают;

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

Наиболее распространенные типы вирусов характеризуются следующими основными особенностями.

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

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

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

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

Макровирусы распространяются под управлением прикладных программ, что делает их независимыми от операционной системы. Подавляющее число макровирусов функционирует под управлением текстового процессора Microsoft Word. В то же время известны макровирусы, работающие под управлением таких приложений, как Microsoft Excel, Lotus Ami Pro, Lotus 1-2-3, Lotus Notes, в операционных системах фирм Microsoft и Apple.

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

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

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

* искажение информации в файлах либо в таблице размещения файлов (FAT-таблице), которое может привести к разрушению файловой системы в целом;

* имитация сбоев аппаратных средств;

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

* инициирование ошибок в программах пользователей или операционной системе.

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

Что такое компьютерная безопасность?

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

Стандартизация безопасности

Предприятия любой отрасли опираются на положения и правила, установленные утверждающими стандарты организациями, например, AMA (American Medical Association — Американская медицинская ассоциация) или IEEE (Institute of Electrical and Electronics Engineers — Институт инженеров по электротехнике и электронике). Подобные идеалы есть и в информационной безопасности. Многие эксперты по безопасности и разработчики опираются на стандартную модель безопасности — CIA (Confidentiality, Integrity, and Availability — конфиденциальность, целостность и доступность). Эта модель из трёх составляющих является общепризнанной при оценке рисков, связанных с важной информацией, и при утверждении политики безопасности. Ниже модель CIA описана более подробно:

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

Целостность — Изменения информации, приводящие к её потере или искажению, должны быть запрещены. Неавторизованные пользователи не должны иметь возможность изменять или разрушать важную информацию.

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

Шифрова́ние — преобразование информации в целях сокрытия от неавторизованных лиц, с предоставлением, в это же время, авторизованным пользователям доступа к ней. Главным образом, шифрование служит задаче соблюдения конфиденциальности передаваемой информации. Важной особенностью любого алгоритма шифрования является использование ключа, который утверждает выбор конкретного преобразования из совокупности возможных для данного алгоритма.[1][2]

Пользователи являются авторизованными, если они обладают определенным аутентичным ключом. Вся сложность и, собственно, задача шифрования состоит в том, как именно реализован этот процесс.[1]

В целом, шифрование состоит из двух составляющих — зашифрование и расшифрование.

С помощью шифрования обеспечиваются три состояния безопасности информации:[1]

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

· Целостность. — Шифрование используется для предотвращения изменения информации при передаче или хранении.

· Идентифицируемость. — Шифрование используется для аутентификации источника информации и предотвращения отказа отправителя информации от того факта, что данные были отправлены именно им.

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

Илон Маск рекомендует:  Asp методы объектов контейнеров adsi

Существующие методы шифрования можно разделить на две большие группы:[6]

Симметричное шифрование использует один ключ для шифрования и расшифрования.

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

Также шифры могут отличаться структурой шифруемой информации. Они могут либо шифровать сразу весь текст, либо шифровать его по мере поступления. Таким образом существуют:[6]

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


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

Блочный шифр можно превратить в поточный, разбивая входные данные на отдельные блоки и шифруя их по отдельности. Однако, блочные шифры являются более криптоустойчивыми по сравнению с поточными. Кроме того, блочные шифры работают зачастую быстрее и легко реализуемы посредством программного обеспечения. Поточные, же, шифры зачастую реализуются в аппаратном виде(в виде некой шифрующей аппаратуры), так как представление данных и их обработка в поточных шифрах очень близка к обработке данных и их передаче в аппаратуре. Там данные представляются именно потоком, чаще всего.[6][19]

Эти методы решают определенные задачи и обладают как достоинствами, так и недостатками. Конкретный выбор применяемого метода зависит от целей, с которыми информация подвергается шифрованию.

Основная статья: Симметричное шифрование

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

Симметричные, а конкретнее, алфавитные алгоритмы шифрования были одними из первых алгоритмов.[20] Позднее было изобретено асимметричное шифрование, в котором ключи у собеседников разные.[21]

Задача. Есть два собеседника — Алиса и Боб, они хотят обмениваться конфиденциальной информацией.

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

Шифрование и передача сообщения.

Алиса шифрует информацию с использованием полученного ключа .

И передает Бобу полученный шифротекст . То же самое делает Боб, если хочет отправить Алисе сообщение.

Боб(Алиса), с помощью того же ключа , расшифровывает шифротекст .

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

[показать] Симметричные криптосистемы

[править]Асимметричное шифрование (с открытым ключом)

Основная статья: Асимметричное шифрование

В системах с открытым ключом используются два ключа — открытый и закрытый, связанные определенным математическим образом друг с другом. Открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для шифрования сообщения и для проверки ЭЦП. Для расшифровки сообщения и для генерации ЭЦП используется секретный ключ.[22]

Данная схема решает проблему симметричных схем, связанную с начальной передачей ключа другой стороне. Если в симметричных схемах злоумышленник перехватит ключ, то он сможет как «слушать», так и вносить правки в передаваемую информацию. В асимметричных системах другой стороне передается открытый ключ, который позволяет шифровать, но не расшифровывать информацию. Таким образом решается проблема симметричных систем, связанная с синхронизацией ключей.[21]

Первыми исследователями, которые изобрели и раскрыли понятие шифрования с открытым кодом, были Уитфилд Диффи и Мартин Хеллман из Стэнфордского университета, и Ральф Меркле из Калифорнийского университета в Беркли. В 1976 году их работа «Новые направления в современной криптографии» открыла новую область в криптографии, теперь известную как криптография с открытым ключом.

Задача. Есть два собеседника — Алиса и Боб, Алиса хочет передавать Бобу конфиденциальную информацию.

Генерация ключевой пары.

Боб выбирает алгоритм и пару открытый, закрытый ключи — и посылает открытый ключ Алисе по открытому каналу.

Шифрование и передача сообщения.

Алиса шифрует информацию с использованием открытого ключа Боба .

И передает Бобу полученный шифротекст .

Боб, с помощью закрытого ключа , расшифровывает шифротекст .

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

Криптография и стеганография

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

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

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

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

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

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

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

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

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

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

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

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

Экспе́ртная систе́ма (ЭС, англ. expert system) — компьютерная система, способная частично заменить специалиста-эксперта в разрешении проблемной ситуации. Современные ЭС начали разрабатываться исследователями искусственного интеллекта в 1970-х годах, а в 1980-х получили коммерческое подкрепление. Предтечи экспертных систем были предложены в 1832 году С. Н. Корсаковым, создавшим механические устройства, так называемые «интеллектуальные машины», позволявшие находить решения по заданным условиям, например определять наиболее подходящие лекарства по наблюдаемым у пациента симптомам заболевания[1].

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

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

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

Дата добавления: 2020-10-26 ; просмотров: 102 ; ЗАКАЗАТЬ РАБОТУ

Ватолин Дмитрий Сергеевич Методы сжатия изображений

Название Ватолин Дмитрий Сергеевич Методы сжатия изображений
страница 6/25
Дата конвертации 23.04.2013
Размер 2.06 Mb.
Тип Литература

Словарные методы сжатия данных

Идея словарных методов

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

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

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

Уменьшение размера возможно в первую очередь за счет того, что обычно в сжимаемых данных встречается лишь малая толика всех возможных строк длины n, поэтому для представления индекса фразы требуется, как правило, меньшее число битов, чем для представления исходной строки. Например, рассмотрим количество взаимно различных строк длины от 1 до 5 в тексте на русском языке (роман Ф.М. Достоевского «Бесы», обычный неформатированный текст, размер около 1.3 Мбайт):

Длина строки Количество различных строк Использовано комбинаций, % от всех возможных
5 196969 0.0004
4 72882 0.0213
3 17481 0.6949
2 2536 13.7111
1 136 100.0000

Иначе говоря, размер (мощность) алфавита равен 136 символам, но реально используется только 2536/(136·136)·100% ≈ 13.7 % от всех возможных двухсимвольных строк, и т.д.

Далее, если у нас есть заслуживающие доверия гипотезы о частоте использования тех или иных фраз, либо проводился какой-то частотный анализ обрабатываемых данных, то мы можем назначить более вероятным фразам коды меньшей длины. Например, для той же электронной версии романа «Бесы» статистика встречаемости строк длины 5 имеет вид:

N Количество строк длины 5, встретившихся ровно N раз Количество относительно общего числа всех различных строк длины 5, %
1 91227 46.3%
2 30650 15.6%
3 16483 8.4%
4 10391 5.3%
5 7224 3.7%
≥6 40994 20.7%
Всего 196969 100.0%

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

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

Очевидно, что процессы моделирования и кодирования, рассматриваемые в главе «Методы контекстного моделирования», для словарных методов сливаются. Моделирование в явном виде может выполняться уже только для индексов. Заметим, что апологеты идеи универсальных моделирования и кодирования последовательно изучают любой метод, не вписывающийся явно в их модель, и обычно достаточно убедительно доказывают, что для него можно построить аналог в виде статистического метода. Так, например, доказано, что несколько рассматриваемых ниже словарных алгоритмов семейства Зива-Лемпела могут быть воспроизведены в рамках контекстного моделирования ограниченного порядка, либо с помощью моделей состояний [6, 9].

Ниже будут рассмотрены алгоритмы словарного сжатия, относимые к классу методов Зива-Лемпела. В качестве примера словарного алгоритма иного класса укажем [7].

Словарные методы сжатия

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

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

В результате выходной файл содержит индексы и слова, поэтому необходимо уметь делать различие между ними. Возможный способ состоит в добавлении к записываемой последовательности дополнительного бита. Например, 19-битового индекса достаточно, чтоб закодировать 2 19 = 524288 элементов. Поэтому, если прочитанное слово найдено в словаре, можно записать 20-битную ссылку, состоящую из нулевого сигнального бита и индекса. Если же слово не найдено в словаре, записывается сигнальный бит, равный 1, длина слово и, наконец, само слово.

Если считать, что размер записывается в виде 7-битового числа и что средний размер слова равен 5 символам, то несжатое слово будет в среднем занимать 6 байт (48 бит). Сжатие 48 бит до 20 бит является вполне хорошим при условии, что происходит достаточно часто. При этом возникает вопрос: «Сколько слов нужно обнаруживать в словаре для того, чтобы иметь общее сжатие?». Пусть вероятность обнаружения слова в словаре равна P. После чтения и записи N слов размер выходного файла будет равен N(20P+48(P –1). Размер входного файла в среднем будет равен 40N. Тогда сжатие будет достигаться в случае, если N(48 – 28P) 0,29. Следовательно, сжатия можно будет добиться при 29% успешных нахождений слов в словаре.

До тех пор, пока входной файл содержит английский текст, большинство слов будут обнаружены в словаре. Для других типов файлов ситуация изменится. В файле, содержащем текст компьютерной программы, будут встречаться слова типа malloc, cout и т.д., которые, возможно, не будут найдены в словаре. А бинарный файл, если его рассматривать как последовательность ASCII-кодов, обычно содержит разный «мусор», которого точно не будет в словаре. В результате вместо сжатия произойдёт разрастание размера файла.

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

1) алгоритм использует только операции над последовательностями строк типа поиска и сравнения и не использует арифметические вычисления;

2) декодер очень прост, так как от него требуется только проводить поиск слова в словаре.

Один из первых методов словарного сжатия – LZ77, названный по фамилиям разработчиков – А. Лемпела и Я. Зива. Основная идея этого метода состоит в использовании ранее прочитанной части файла в качестве словаря. Кодер создаёт окно для входного файла и двигает его справа налево в виде строки символов, требующих сжатия. Окно разбивается на две части. Левая часть окна называется буфером поиска. Она служит текущим словарём, в ней всегда содержатся символы, которые только что поступили и были закодированы. Правая часть окна называется упреждающим буфером и содержит текст, который будет закодирован. На практике буфер поиска состоит из десятков тысяч байт, а длина упреждающего буфера равна нескольким десяткам символов. Пример скользящего окна (буфер поиска и упреждающий буфер разделены вертикальной чертой):

Кодер просматривает буфер поиска в обратном порядке (справа налево) и ищет в нём первое появление символа e из упреждающего буфера. Он обнаруживает такой символ в начале слова easily. Значит, e находится по смещению 8 от конца буфера поиска. Далее кодер определяет, сколько совпадающих символов следует за найденным символом e. В данном случае совпадение по символам eas имеет длину 3. Кодер продолжает поиск, пытаясь найти более длинные совпадающие последовательности. В нашем случае имеется ещё одна совпадающая последовательность той же длины 3 в слове eastman со смещением 16. Кодер выбирает самую длинную из них, а при совпадении длин – самую удалённую, и готовит метку (16,3, e).

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

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

В общем случае метка в LZ77 имеет три поля: смещение, длина и следующий символ в упреждающем буфере (в нашем случае – e). Метка (16,3, e) записывается в выходной файл, а окно сдвигается на 4 позиции вперёд: три позиции для совпадающей последовательности и одна позиция – для следующего символа:

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

|sir_sid_eastman_easily_teases_sea_sick_seals → (0, 0, s);

s|ir_sid_eastman_easily_teases_sea_sick_seals → (0, 0, i);

si|r_sid_eastman_easily_teases_sea_sick_seals → (0, 0, r).

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

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

Дата добавления: 2015-08-01 ; просмотров: 557 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

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