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


Содержание

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

Словарь данных

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

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

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

  • описанием значений потоков и хранилищ, изображенных на DFD;
  • описанием композиции агрегатов данных, движущихся вдоль потоков, т.е. комплексных данных, которые могут расчленяться на элементарные символы (например, АДРЕС ПОКУПАТЕЛЯ содержит ПОЧТОВЫЙ ИНДЕКС, ГОРОД, УЛИЦУ и т.д.);
  • описанием композиции групповых данных в хранилище;
  • специфицированием значений и областей действия элементарных фрагментов информации в потоках данных и хранилищах;
  • описанием деталей отношений между хранилищами.

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

По типу потока в словаре содержится информация, идентифицирующая:

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

Атрибуты потока данных включают:

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

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

Лучшие изречения: При сдаче лабораторной работы, студент делает вид, что все знает; преподаватель делает вид, что верит ему. 9339 — | 7293 — или читать все.

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

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

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

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

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

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

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

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

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

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

Сжатие текстовых сообщений на основе адаптивного контекстно-морфологического моделирования

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

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

HTML-версии работы пока нет.
Cкачать архив работы можно перейдя по ссылке, которая находятся ниже.

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

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

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

Особенности посылки сообщений в Windows и в Win32 API. Обработка состояний простоя. Маршрутизация сообщений в Windows 3.x. Основные циклы обработки сообщений. Применение многопотоковых приложений. Основные возможности редакторов WinWord 97 и Notepad.

лекция [35,9 K], добавлен 24.06.2009

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

курсовая работа [197,1 K], добавлен 20.02.2012

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

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

Текстовый редактор — приложение для обработки текстовой информации. Описание текстовых процессоров как более совершенных текстовых редакторов. Типы текстовых файлов: форматированные, неформатированные. Основные правила редактирования и набора текста.

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

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

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

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

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

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

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

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

контрольная работа [2,3 M], добавлен 07.07.2013

Обзор существующих программ сжатия данных без потерь. Анализ методов сжатия: алгоритмов группы, KWE, Lossless JPEG, кодирование Хаффмана. Обзор составляющих компонентов. Разработка кода программы-архиватора, работающей на основе алгоритма Хаффмена.

курсовая работа [487,3 K], добавлен 14.07.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

Сжатие текстовых данных Текст научной статьи по специальности « Общие и комплексные проблемы естественных и точных наук»

Похожие темы научных работ по общим и комплексным проблемам естественных и точных наук , автор научной работы — Петрянин Д.Л., Юрков Н.К.,

Текст научной работы на тему «Сжатие текстовых данных»

Петрянин Д.Л., Юрков Н.К

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

СЖАТИЕ ТЕКСТОВЫХ ДАННЫХ

Архиватор — программа, осуществляющая сжатие и/или упаковку одного и более файлов в архив или серию архивов, для удобства переноса или хранения, а также распаковку архивов.

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

Архивация все чаще используется при передаче данных через локальные сети или/и сети Интернет, для экономичности трафика и времени передачи.

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

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

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

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

Сжатие текстовых данных обычно происходит намного быстрее, чем остальных типов данных.

Проведем эксперимент: произведем сжатие 4 распространенных текстовых типов данных: TXT, DOCX, DOC и RTF. В каждый из данных файлов будет находиться один и тот же текст (малого объема — 135 слов (1054 знака), без форматирования) . Количество используемых архиваторов: 11 (RAR, 7z, ZIP, ARJ, UC2, GZ, LHA (LZH), TGZ, DST, RK и CAB) . Результаты сжатия по размерам приведены в таблице 1, а по времени сжатия — в таблице 2.

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

Таблица 1 Результаты сжатия по размерам (в байтах)______________________

Файл TXT DOCX DOC RTF

Размер файла 1058 10951 28160 37582

RAR 612 8443 6006 7134

7z 726 8435 5601 7402

zip 841 8623 6311 8349

ARJ 688 8466 6219 8351

UC2 1555 1041 7209 9265

GZ 592 8370 5883 7534

LZH 610 8390 6115 8294

TGZ 841 8632 6359 8592

DST 616 8350 5983 7642

RK 640 9120 5956 7684

CAB 723 8464 5979 8053

Min размер 592 1041 5601 7134

Выбранный архиватор GZ UC2 7z RAR

Таблица 2 Результаты сжатия по времени сжатия (в мс)

Файл TXT DOCX DOC RTF

Размер файла 1058 10951 28160 37582

RAR 78 469 124 93

zip 45 469 31 63

ARJ 46 108 78 46

UC2 297 312 295 282

GZ 31 61 78 124

LZH 31 78 46 46

TGZ 46 62 63 45

DST 79 124 92 141


CAB 93 218 93 110

Min время 31 47 31 45

Выбранный архиватор GZ/LZH 7z zip TGZ

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

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

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

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

Рис. 1 Распределение русских букв по их частоте использования

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

Файлы документов MS WinWord с расширением DOC представляют собой сложные объекты, организованные по правилам структурированного хранилища. Внутри составной файл состоит из следующих элементов:

«хранилища», а на самом деле это просто внутренние каталоги, описывающие состав и расположение других объектов внутри составного файла;

«потоки», а на самом деле это своего рода файлы, массивы структурированной информации, имеющие собственное имя;

«заблокированные данные», а на самом деле это довольно редко встречающиеся неструктурированные массивы двоичной информации, своего рода «посторонние» данные, которые разрешается иметь внутри составного файла, но которые не могут служить OLE-объектами. [3]

Формат DOCX предполагает сжатие, и сам по себе является ZIP-архивом, внутри которого содержатся собственно текстовый документ в виде XML, графика и файлы, определяющие свойства документа и отношения между содержимым контейнера. Сжатие определяет и одно из основных отличий между форматами DOC и DOCX — размер файла в последнем случае несколько меньше. [4]

В RTF для обмена документами используются только представимые символами коды из ASCII-, MAC- и PC-символьного набора. Документы RTF состоят преимущественно из команд управления настройки программы чтения файлов в данном формате. Эти команды можно разделить на управляющие слова и управляющие символы (рис. 2). Конец каждой команды отмечается одним из разделяющих символов (чаще всего — точкой с запятой). [5] Так как файл состоит из данных команд и отсутствует какое-либо

внутреннее сжатие, то документ будет занимать большее физическое пространство (на носителе) .

0x0310 3530 3230 3330 347D 5469 6D65 7320 4Е65

0x0320 7720 526F 6D61 6ЕЗВ 7D0D 0А7В 5С66 6C6F

0x0330 6D69 6E6F 725С 6633 3135 3034 5С66 6269

0x0340 6469 2 05С 6672 6F6D 616Е 5С66 6368 6172

0x0350 7365 7432 3034 5С66 7072 7132 7В5С 2А5С

0x0360 7061 6E6F 7365 2030 3230 3230 3630 3330

0x0370 3530 3430 3530 3230 3330 3 47D 5469 6D65

0x0380 7320 4Е65 7720 526F 6D61 6ЕЗВ 7D7B 5С66

0x0390 6462 6D69 6E6F 725С 6633 3135 3035 5С66

ОхОЗАО 6269 6469 2 05С 6672 6F6D 616Е 5С66 6368

0x03В 0 6172 7365 7432 3034 5С66 7072 7132 7В5С

ОхОЗСО 2А5С 7061 6E6F 7365 2030 3230 3230 3 63 0

0x03D0 3330 3530 3430 3530 3230 3330 347D 5469

ОхОЗЕО 6D65 7320 4Е65 7720 526F 6D61 6ЕЗВ 7D0D

Рис. 2 Фрагмент документа RTF в шестнадцатеричной форме (HEX)

TXT-файл представляет собой последовательность символов в одной из пяти кодировок: ANSI, UTF-8, Unicode, Unicode Big Endian, OEM. Каждый символ из используемого набора символов кодируется в виде одного байта, а иногда в виде последовательности подряд идущих двух, трёх и т.д. байтов.

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

Текстовым файлам противопоставляются двоичные (бинарные) файлы, в которых информация

организована по иным принципам. [б] Поэтому данный документ имеет наименьший размер.

Таким образом, каждый из текстовых типов файлов (TXT, DOCX, DOC и RTF) имеет свою некоторую структуру «шифрования» файла, соответственно размер каждого файла различается, также как и архиватор с наименьшим размером. Поэтому для каждого файла необходимо определять архиватор индивидуально .

1. Батьков, В.О. Анализ проблем современных хранилищ данных / В.О. Батьков // Труды

международного симпозиума Надежность и качество. 2013. Т. 1. С. 259-260.

2. Петрянин, Д.Л. Анализ систем защиты информации в базах данных / Д.Л.Петрянин, Н.В.Горячев, Н.К. Юрков // Труды международного симпозиума Надежность и качество. 2013. Т. 1. С. 115-121.

3. Внутренний формат документов MS WORD — http://uinc.ru/articles/39/

[MS-DOCX]: Word Extensions to the Office Open XML (.docx) File Format —

Лучшие алгоритмы сжатия текста

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

Вопрос:

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

  • текст будет представлять себя наборы символов латиницы, кириллицы, знаков препинания — из ASCII (cp866 или win-1251), возможно еще псевдографика будет
  • те же наборы символов, но представленные в кодировке ru_RU.UTF-8

Пока на слуху, но это уже относительно давно, алгоритм PPMd, PPMz. Есть что-то более совершенное?

2 ответа 2

Лучший ответ на этот вопрос — спросите на форуме encode.ru. Я лично не слежу за этим совсем уж пристально, поэтому навскидку: paq8px, emma, cmix (у каждого есть своя ветка на форуме). Кроме этого, препроцессинг — словарная замена (xml-wrt), трюки Grabowski. Имейте в виду, что тексты должны быть достаточно велики (ну хотя бы сотни килобайт) и скорость сжатия/распаковки может быть в районе нескольких кб/с, а многопоточность невозможна без ухудшения сжатия.

Собственно приведённая вами же ссылка http://mattmahoney.net/dc/text.html даёт достаточно исчерпывающий ответ на ваш вопрос. Все алгоритмы такого уровня получают ветки на форуме encode.ru и тестируются Маттом на тексте английской википедии.

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

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

Алгоритм сжатия текстовых файлов

Рубрика: Технические науки

Дата публикации: 05.11.2020 2020-11-05

Статья просмотрена: 215 раз

Библиографическое описание:

Череданова Е. М., Мамченко Е. А. Алгоритм сжатия текстовых файлов // Молодой ученый. — 2020. — №44. — С. 24-26. — URL https://moluch.ru/archive/178/46279/ (дата обращения: 12.11.2020).

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

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

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

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

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

При отсутствии статистической взаимосвязи между символами методы построения эффективных кодов были даны впервые К.Шенноном и Н.Фано. Код строится следующим образом: символы алфавита сообщений выписываются в порядке убывания вероятностей. Записанная последовательность разделяется на две подгруппы с равными суммарными вероятностями. Всем символам верхней половины в качестве первого знака приписывается 1, а всем нижним — 0. Каждая из полученных групп, в свою очередь, разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одному символу. При каждом разбиении к префиксам кодовых комбинаций символов одной подгруппы дописывается кодовый знак 0, к символам другой -1.

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

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

Задача построения оптимального неравномерного кода (ОНК) основания a для некоррелированных алфавитов исходной дискретной последовательности (сообщения) m, состоящий из m символов, формулируется следующим образом:

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

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

Для того, что бы предложенный ОНК удовлетворял соотношению (1) необходимо выполнение условий:

  1. Если выписать символы в порядке убывания вероятности:

где i>j, то длительность соответствующих кодовых комбинаций должна удовлетворять соотношению:

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

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

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

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

где Аср — средняя длина кодовой комбинации, — вероятность i-го символа алфавита находящегося на k-й позиции в слове, — число кодовых знаков кодовой комбинации i -го символа алфавита на k-ой позиции в слове, n- максимальная длина слова.

Что бы предложенный ОНК, удовлетворял соотношению (5) необходимо выполнение условий:

  1. Для каждой позиции символов в слове k є [1…n] если выписать символы в порядке убывания вероятностей:

где i> j, то длительность соответствующих кодовых комбинаций должна удовлетворять соотношению:

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

Илон Маск рекомендует:  Зачем вам изучать html

Оценка эффективности

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

Возьмем для алфавита текстовых сообщений на русском языке m = 53 (32 буквы, 10 цифр, 11 служебных знаков). Тогда для равномерного распределения частот символов алфавита печатного текста, построенное по данным [2] получим:

– для соответствующего этому распределению частот первого приближения к энтропии:

– информационная емкость сообщения:

– максимально достижимый выигрыш при кодировании

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

= 4,02 дв. ед./симв. и

Заключение


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

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

1. Новик Д. А. Эффективное кодирование. М.-Л. “Энергия”,1965 г., 236

2. Котов А. П. и др., Основы телеграфии, ВКАС, л.,1958

Алгоритмы сжатия данных с использованием внешнего словаря и их реализация

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

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

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

Простейший пример (я его реализовывал в одном своем приложении, вполне полезно и удобно) с использованием алгоритма diff (а точнее bzdiff — это почти то же самое но результат сжимается bz).

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

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

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

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

Внимание вопрос… я делаю очередной велосипед или тут ‘поле не пахано’? Есть ли готовые решения и библиотеки (в идеале opensource, так как возможны слишком узкие ниши применения с соответствующими требованиям к исправлениям, плюс гибкость выбора платформ)?

Вопрос номер два — есть ли те, кому требуется сократить нагрузку на каналы связи (если их мало или они дорогие, например спутниковая связь)?

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

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

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

Можно выделить следующие основные свойства и фундаментальные качества естественного языка [3]:

– принципиальная нечеткость значения языковых выражений;

– динамичность языковой системы;

– образность номинации, основанная на метафоричности;

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

– гибкость в передаче эксплицитной и имплицитной информации;

– разнообразие функций, включающее коммуникативную, когнитивную, планирующую, управляющую, обучающую, эстетическую и другие;

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

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

Системное представление текстовых структур

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

Рис. 1. Иерархическое представление текста

Иерархическая модель может отражать разные параметры текстовой структуры. Одно из представлений – выделение уровней букв, слов и предложений [6]. Структура целого текста определяет не только связи между предложениями, но и связи между словами, а также в некоторой степени связи между элементами слова (буквами и слогами).

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

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

Потоковое представление текстовых структур

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

Текст X можно рассматривать как последовательность (поток) из n элементов x1, x2, . xn некоторого алфавита Q, при этом длина текстовой строки (текста) [7]. Элементом текста xn может быть как одиночный текстовый символ, так и слово, грамматический класс, любая группировка или подстрока символов текста. Схематично потоковое представление текстов изображено на рис. 2.

Рис. 2. Потоковое представление текста для разных элементов

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

Теория сжатия и Колмогоровская сложность

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

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

– избыточность языка и текста.

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

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

Как правило, соседние или близко расположенные элементы изображения близки по цвету и интенсивности, а следующие друг за другом кадры отличаются только некоторыми элементами. Текстовые объекты также необходимо рассматривать с позиций контекстного моделирования (context modeling): с одной стороны, любой текст представляет собой поток данных, с другой – для текстов на естественном языке появление любого элемента во многом зависит от предшествующих элементов.

Основу возможности применения алгоритмов сжатия для оценки близости двух объектов составляет понятие Колмогоровской сложности, которую также иногда называют описательной сложностью. Формальное определение Колмогоровской сложности задается следующим образом: сложностью строки x является длина минимальной бинарной программы, выводящей строку x. Колмогоровская сложность x при заданном y – это длина наикратчайшей бинарной программы, которая, получая на вход y, выводит x (это обозначается ). Колмогоровская сложность x как длина наикратчайшей бинарной программы без входных данных, выводящая x, обозначается , где λ – отсутствие данных на входе. Данная величина является невычислимой, но ее можно аппроксимировать как длину максимально сжатой версии входной строки [2].

Илон Маск рекомендует:  Компоненты pfsgrid net таблица с множеством поддерживаемых функций

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

Теория нечеткости

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

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

● естественная неоднозначность при рассмотрении текстовых объектов;

● принципиальная невозможность учесть все возможные факторы и параметры.

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

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

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

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

Использование нечеткого отношения как бинарной функции, определяющей степень выполнения отношения для каждой пары объектов, позволяет формализовать многие реальные явления и задачи при обработке и анализе текстов. Если рассматривать некоторое множество текстов, то для каждой пары может быть вычислена степень близости, например, на основе понятия Колмогоровской сложности и определения степени сжатия объединенных объектов. Тогда полученную матрицу расстояний можно рассматривать как нечеткое бинарное отношение, заданное на множестве текстовых объектов. На рис. 3 приведен фрагмент таблицы, построенной для художественных текстов русских авторов, элементы которой могут быть интерпретированы как значения нечеткого отношения близости объектов. В работе [5] рассмотрена задача нечеткого разделения пользователей социального сообщества в сети Интернет путем выявления характерных признаков оставленных ими сообщений.

Рис. 3. Пример матрицы близости текстовых объектов

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

Рецензенты:

Баландин Д.В., д.ф.-м.н., профессор, заведующий кафедрой численного и функционального анализа, Нижегородский государственный университет им. Н.И. Лобачевского, г. Нижний Новгород;

Федосенко Ю.С., д.т.н., профессор, заведующий кафедрой «Информатика, системы управления и телекоммуникаций», Волжский государственный университет водного транспорта, г. Нижний Новгород.

СЖАТИЕ ДАННЫХ

СЖАТИЕ ДАННЫХ, в вычислительной технике — методика, позволяющая добиться сокращения объема памяти, занимаемой данными. Для этого прописные буквы представляют меньшим числом бит, чем обычно, а часто употребляемые слова воспроизводят сокращенными обозначениями (алгоритм Хофмана). Длинные последовательности одинаковых знаков заменяют одним знаком и числом, указывающим, сколько раз его повторять — этот метод называют алгоритмом повторяющихся сегментов. При помощи этих способов объем текстовых файлов сокращается более чем на 50%, а оцифрованные изображения — на 90%. Методы сжатия подразделяют на алгоритмы без потери данных и с потерей данных. В первом случае данные при сжатии не теряют своих качеств. Во втором случае достигается более значительное сжатие, но качество данных ухудшается — после возвращения им прежнего объема они несколько отличаются от исходных. Метод сжатия с потерей качества применяется преимущественно для записи изображений, видеокадров и музыки.

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

Опрос

Новички

Контекстное моделирование

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

Пожалуй, наиболее простой способ оценки реализуется с помощью по­луадаптивного моделирования и заключается в предварительном подсчете безусловной частоты появления символов в сжимаемом блоке. Полученное распределение вероятностей используется для статистического кодирования всех символов блока. Если, например, такую модель применить для сжатия текста на русском языке, то в среднем на кодирование каждого символа бу­дет потрачено примерно 4.5 бита. Это значение является средней длиной кодов для модели, базирующейся на использовании безусловного распределения вероятностей букв в тексте. Заметим, что уже в этом простом случае достигается степень сжатия 1.5 по отношению к тривиальному кодированию, когда всем символам назначаются коды одинаковой длины. Действительно, размер алфавита русского текста превышает 64 знака, но меньше 128 знаков (строчные и заглавные буквы, знаки препинания, пробел), что требует 7-битовых кодов.

Анализ распространенных типов данных, — например, тех же текстов на естественных языках, — выявляет сильную зависимость вероятности появ­ления символов от непосредственно им предшествующих. Иначе говоря, большая часть данных, с которыми мы сталкиваемся, порождается источни­ками с памятью. Допустим, нам известно, что сжимаемый блок является текстом на русском языке. Если, например, строка из трех только что обра­ботанных символов равна «_цы» (подчеркиванием здесь и далее обозначает­ся пробел), то текущий символ скорее всего входит в следующую группу: «г» («цыган»), «к» («цыкать»), «п» («цыпочки»), «ц» («цыц»). Или, в случае анализа фазу нескольких слов, если предыдущая строка равна «Вста-вай,_проклятьем_заклейменный,», то продолжением явно будет «весь_мир_». Следовательно, учет зависимости частоты появления символа (в общем случае — блока символов) от предыдущих должен давать более точные оценки и в конечном счете лучшее сжатие. Действительно, в случае посим­вольного кодирования при использовании информации об одном непосред­ственно предшествующем символе достигается средняя длина кодов в 3.6 бита для русских текстов, при учете двух последних — уже порядка 3.2 бита. В первом случае моделируются условные распределения вероятностей сим­волов, зависящие от значения строки из одного непосредственно предшест­вующего символа, во втором — зависящие от строки из двух предшествую­щих символов.

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

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

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

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

Если длина контекста ограничена, то такой подход будем называть кон­текстным моделированием ограниченного порядка (finite-context modeling), при этом под порядком понимается максимальная длина используемых кон­текстов N. Например, при моделировании порядка 3 для последнего симво­ла «о» в последовательности «. молоко. » контекстом максимальной длины 3 является строка «лок». При сжатии этого символа под «текущими контек­стами» могут пониматься «лок», «ок», «к», а также пустая строка «». Все эти контексты длины от N до 0 назовем активными контекстами в том смысле, что при оценке символа может быть использована накопленная для них сть тистика.

Далее вместо «контекст длины о, о N , где q — размер алфавита обрабатываемой последовательности. КМ(0) и КМ(-1) всегда ак­тивны.

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

Часто говорят о «родительских» и «дочерних» контекстах. Для контекста «к» дочерними являются «ок» и «лк», поскольку они образованы сцеплением (конкатенацией) одного символа и контекста «к». Аналогично для контекста «лок» родительским является контекст «ок», а контекстами-предками — «ок», «к», «». Очевидно, что «пустой» контекст «» является предком для всех. Ана­логичные термины применяются для КМ, соответствующих контекстам.

Совокупность КМ образует модель источника данных. Под порядком модели понимается максимальный порядок используемых КМ.

ВИДЫ КОНТЕКСТНОГО МОДЕЛИРОВАНИЯ

Пример обработки строки «абсабвбабс» иллюстрирует сразу две пробле­мы контекстного моделирования:

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

■ как оценивать вероятность символов, имеющих нулевую частоту (на­пример, «г»).

Выше были приведены цифры, в соответствии с которыми при увеличе­нии длины используемого контекста сжатие данных улучшается. К сожале­нию, при кодировании блоков типичной длины — одного или нескольких мегабайтов и меньше — это справедливо только для небольших порядков модели, так как статистика для длинных контекстов медленно накапливает­ся. При этом также следует учитывать, что большинство реальных данных характеризуется неоднородностью, нестабильностью силы и вида статисти­ческих взаимосвязей, поэтому «старая» статистика контекстно-зависимых частот появления символов малополезна или даже вредна. Поэтому модели, строящие оценку только на основании информации КМ максимального по­рядка N, обеспечивают сравнительно низкую точность предсказания. Кроме того, хранение модели большого порядка требует много памяти.

Если в модели используются для оценки только КМ(ЛО, то иногда такой подход называют «чистым» (pure) контекстным моделированием порядка N. Из-за вышеуказанного недостатка «чистые» модели представляют обычно только научный интерес.

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

Рассмотрим модель произвольного порядка N. Если q(si\o) есть вероят­ность, присваиваемая в активной КМ(о) символу j, алфавита сжимаемого потока, то смешанная вероятность q(si) вычисляется в общем случае как

где w(o) — вес оценки КМ(о).

Оценка q(Sj\o) обычно определяется через частоту символа s,- по триви­альной формуле

rnfiJ[si\o) — частота появления символа st в соответствующем контексте по­рядка о; До) — общая частота появления соответствующего контекста поряд­ка о в обработанной последовательности.

Заметим, что правильнее было бы писать не, скажем, Ду/|о), иДз^С^), т. е. «частота появления символа S/ в КМ порядка о с номером До)», по­скольку контекстных моделей порядка о может быть огромное количество. Но при сжатии каждого текущего символа мы рассматриваем только одну КМ для каждого порядка, так как контекст определяется непосредственно примыкающей слева к символу строкой определенной длины. Иначе говоря, для каждого символа мы имеем набор из N+1 активных контекстов длины от N до 0, каждому из которых однозначно соответствует только одна КМ, если она вообще есть. Поэтому здесь и далее используется сокращенная за­пись.

Если вес w(-l) > 0, то это гарантирует успешность кодирования любого символа входного потока, так как наличие КМ(-1) позволяет всегда получать ненулевую оценку вероятности и, соответственно, код конечной длины.

Различают модели с полным смешиванием (fully blended), когда предска­зание определяется статистикой КМ всех используемых порядков, и с час­тичным смешиванием (partially blended) — в противном случае.

Рассмотрим процесс оценки отмеченного на рисунке стрелкой символа

«л», встретившегося в блоке «молочноемолоко». Считаем, что модель рабо­тает на уровне символов.

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