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


Содержание

Обратимые и необратимые методы сжатия. Привести примеры методов сжатия

Читайте также:

  1. I. Методы формирования сознания, методы убеждения
  2. I. Стили руководства. Методы принятия управленческих решений. Управленческая решетка Блейка — Моутона.
  3. I. Структурные методы
  4. II ПОСМЕРТНЫЕ МЕТОДЫ
  5. III) Методы управления 1 страница
  6. III) Методы управления 2 страница
  7. III) Методы управления 3 страница
  8. III. Внедрение и освоение новой техники, технологии эксплуатации и ремонта, эффективных и безопасных методов организации производства и труда.
  9. IV. Методы изображения действительности.
  10. IV. Методы изображения действительности.
  11. IV. Современные методы усиления фундаментов.
  12. O Понятия, методы и области применения

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

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

• .JPG для графических данных;

• .МPG для видеоданных;

• .МРЗ для звуковых данных.

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

• .GIF, .TIF, .PCX и многие другие для графических данных;

• .АVI для видеоданных;

• .ZIP, .ARJ, RAR, .LZH, ,LH, .CAB и многие другие для любых типов данных.

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

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

Например, для последовательности: 0; 0; 0; 127; 127; 0; 255; 255; 255: 255 (всего 10 байтов) образуется следующий вектор:

Значение Коэффициент повтора

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

0; 3; 127; 2; 0; 1; 255; 4 (всего 8 байтов). В данном примере коэф­фициент сжатия равен 8/10 (80 %).

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

Дата добавления: 2015-04-24 ; Просмотров: 1746 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

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

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

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

Можно выделить следующие основные свойства и фундаментальные качества естественного языка [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].

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

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

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

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

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

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

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

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

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

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

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

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

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

Рецензенты:

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

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

Сжатие данных в примерах

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

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

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


Что понимается под сжатием данных? Если говорить кратко, то сжатие устраняет из данных избыточность; в терминах же теории информации сжатие увеличивает энтропию сжатого текста. Однако оба этих утверждения по существу по существу верны в силу определения самих понятий. Избыточность может быть выражена в самых разных формах. Одним типом является последовательности повторяющихся битов ( 11111111 ). Вторым – последовательности повторяющихся байтов ( XXXXXXXX ). Однако чаще избыточность проявляется в более крупном масштабе и выражается либо закономерностями в наборе данных, взятом как единое целое, либо последовательностями различной длины, имеющими общие признаки. По существу, цель сжатия данных заключается в поиске алгоритмических преобразований представлений данных, которые позволят получить более компактные представления «типовых» наборов данных. Это описание может показаться несколько туманным, но мы постараемся раскрыть его суть на практических примерах.

Сжатие без потерь и с потерями

Фактически существуют два в корне различающихся подхода к сжатию данных: сжатие с потерями и без потерь. Эта статья, в основном, посвящена методам сжатия без потерь, но для начала полезно изучить различия. Сжатие без потерь предусматривает преобразование представления набора данных таким образом, чтобы затем можно было в точности воспроизвести первоначальный набор данных путем обратного преобразования (распаковки). Сжатие с потерями – это представление, которое позволяет воспроизводить нечто «очень похожее» на первоначальный набор данных. Преимущество использования методов сжатия с потерями заключается в том, что они зачастую позволяют получать намного более компактные представления данных по сравнению с методами сжатия без потерь. Чаще всего методы сжатия с потерями применяются для обработки изображений, звуковых файлов и видео. Сжатие с потерями в этих областях может оказаться уместным благодаря тому, что человек воспринимает битовую комбинацию цифрового изображения/звука не с «побитовой» точностью, а скорее оценивает музыку или изображение в целом.

Илон Маск рекомендует:  Элементы нечеткой логикиh3ce

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

Пример набора данных

В данной статье будет использоваться специально подготовленное гипотетическое представление данных. Приведем простой для понимания пример. В городе Гринфилд (штат Массачусетс, США) используются префиксы телефонных номеров 772- , 773- и 774- . (К сведению читателей за пределами США: в США местные телефонные номера являются семизначными и традиционно представляются в виде ###-####; префиксы назначаются в соответствии с географическим местоположением). Также предположим, что из всех трех префиксов чаще всего используется первый. Частями суффикса могут быть любые другие цифры с приблизительно равной вероятностью. Набор интересующих нас данных находится в «списке всех телефонных номеров, которые в настоящее время находятся в активном пользовании». Можно попробовать подобрать причину, почему это могло бы быть интересным с точки зрения программирования, но в данном случае это не важно.

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

Таблица 1. Многоколоночный отчет

Сжатие пустых мест

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

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

Сжатие пустых мест крайне «дешево» с точки зрения реализации. Вопрос состоит лишь в считывании потока данных и исключении из выходного потока нескольких конкретных значений. Во многих случаях этап «распаковки» вообще не предусматривается. Однако даже если бы мы захотели воссоздать что-то близкое к оригиналу потока данных, это потребовало бы лишь небольшого объема ресурсов ЦП или памяти. Восстановленные данные не обязательно будут совпадать с исходными данными; это зависит от того, какие правила и ограничения содержались в оригинале. Страница HTML, напечатанная человеком в текстовом редакторе, вероятно, будет содержать пробелы, расставленные согласно определенным правилам. Это же относится и к автоматизированным инструментальным средствам, которые часто создают «обоснованные» отступы и интервалы в коде HTML. В случае с жестким форматом отчета, представленным в нашем примере, не существует никаких причин, по которым первоначальное представление не могло бы быть воссоздано каким-либо «форматирующим распаковщиком».

Групповое кодирование

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

Если в обрабатываемом формате данных преобладают повторяющиеся байты, то может быть уместным и эффективным использование алгоритма, в котором один или несколько байтов указывают количество повторений, а затем следует повторяемый символ. Однако если имеются строки символов единичной длины, для их кодирования потребуются два (или более) байта. Другими словами, для одного символа ASCII «X» входного потока мог бы потребоваться выходной битовый поток 00000001 01011000 . С другой стороны, для кодирования ста следующих друг за другом символов «X» использовалось бы то же самое количество битов: 01100100 01011000 , что весьма эффективно.

В различных вариантах RLE часто применяется избирательное использование байтов для указания числа повторений, в то время как остальные байты просто представляют сами себя. Для этого должно быть зарезервировано как минимум одно однобайтовое значение, которое в случае необходимости может удаляться из выходных данных. Например, в нашем образце отчета по телефонным номерам известно, что вся информация во входном потоке состоит из простых символов ASCII. В частности, у всех таких символов первый бит ASCII-значения равен 0. Мы могли бы использовать этот первый бит ASCII для указания на то, что байт указывает число повторений, а не обычный символ. Следующие семь битов байта итератора могли бы использоваться для указания числа повторений, а в следующем байте мог бы содержаться повторяющийся символ. Так, например, мы могли бы представить строку «YXXXXXXXX» следующим образом:

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

Кодирование по методу Хаффмана

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

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

Таблица 2. Результаты кодирования по методу Хаффмана

Исходный набор символов (состоящий из чисел) может быть легко закодирован (без сжатия) в виде 4-х битных последовательностей (полубайтов). Приведенное кодирование по методу Хаффмана будет использовать до 5 битов для символов в наихудшем случае, что очевидно хуже кодирования с помощью полубайтов. Однако в лучшем случае потребуется всего 1 бит; при этом известно, что именно лучший случай будет использоваться чаще всего (так как именно этот символ чаще всего встречается в данных). Таким образом, мы могли бы закодировать конкретный телефонный номер следующим образом:

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

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

Сжатие по алгоритму Лемпеля-Зива

Вероятно, самым значимым методом сжатия без потерь является алгоритм Лемпеля-Зива. В этой статье речь пойдет о варианте LZ78, но LZ77 и другие варианты работают схожим образом. Идея, заложенная в алгоритме LZ78, заключается в кодировании потоковой последовательности байтов с использованием некоторой динамической таблицы. В начале сжатия битового потока таблица LZ заполняется фактическим набором символов, наряду с несколькими пустыми слотами. В алгоритме применяются таблицы разных размеров, но в данном примере с телефонными номерами (со сжатием пустых мест) используется таблица из 32 элементов (этого достаточно для данного примера, но может оказаться мало для других типов данных). Вначале мы заполняем первые десять слотов символами используемого алфавита (цифрами). По мере поступления новых байтов сначала выводится значение из таблицы, соответствующее самой длинной подходящей последовательности, а затем в следующий доступный слот записывается последовательность длиной N+1. В наихудшем случае мы используем 5 битов вместо 4 для отдельного символа, однако в большинстве случаев мы сможем обойтись 5 битами на несколько символов. Рассмотрим пример работы этого алгоритма (слот таблицы указан в квадратных скобках):

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

Приведенных операций должно быть достаточно для демонстрации работы модели. Хотя никакого заметного сжатия пока не достигнуто, уже видно, что мы повторно использовали слоты 11 и 16, закодировав по два символа одним выходным символом. Кроме того, мы уже накопили крайне полезную последовательность байтов 772 в слоте 18, которая впоследствии неоднократно будет встречаться в потоке.

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

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

Правильная постановка задачи

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

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

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

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

Посвящается памяти Клода Шеннона (Claude Shannon).

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

Классификация стратегий моделирования

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

  • статическое;
  • полуадаптивное;
  • адаптивное (динамическое);
  • блочно-адаптивное.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Урок 7
Моделирование в среде текстового процессора

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

Словесные модели

Одним из видов знаковых моделей являются словесные модели — это описание мысленной модели на естественном языке.

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

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

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

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

Рассмотрим поэтапно суть использования словесных моделей.

ПОСТАНОВКА ЗАДАЧИ


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

ЦЕЛИ МОДЕЛИРОВАНИЯ

РАЗРАБОТКА МОДЕЛИ

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

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

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

Компьютерный эксперимент со знаковой моделью включает следующие стадии работы:

ЗАДАЧА 2.1. Словесный портрет

I этап. Постановка задачи

ОПИСАНИЕ ЗАДАЧИ

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

ЦЕЛЬ МОДЕЛИРОВАНИЯ

Набрать и расположить на странице текст. Сохранить текст.

ФОРМАЛИЗАЦИЯ ЗАДАЧИ

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

II этап. Разработка модели

ИНФОРМАЦИОННАЯ МОДЕЛЬ

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

КОМПЬЮТЕРНАЯ МОДЕЛЬ

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

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

1. Создать документ в прикладной среде текстового процессора.

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

3. Набрать текст, используя основные правила набора текста:

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

4. Проверить орфографию.

5. Расставить переносы при помощи команды Расстановка переносов.

6. Сохранить текст под некоторым именем.

III этап. Компьютерный эксперимент

ПЛАН ЭКСПЕРИМЕНТА

1. Провести тестирование модели как компьютерного документа.

2. Провести тестирование смыслового содержания модели.

ПРОВЕДЕНИЕ ИССЛЕДОВАНИЯ

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

2. Для проверки смыслового содержания текста зачитайте его своим одноклассникам. Спросите их мнение.

IV этап. Анализ результатов

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

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Прочитайте литературные портреты. Как называется произведение и кто автор? Какой герой описан? Составьте и оформите компьютерную словесную модель.

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

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

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

ЗАДАЧА 2.3. Поздравительная открытка

I этап. Постановка задачи

ОПИСАНИЕ ЗАДАЧИ

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

ЦЕЛЬ МОДЕЛИРОВАНИЯ

Красиво оформить поздравление.

ФОРМАЛИЗАЦИЯ ЗАДАЧИ

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

II этап. Разработка модели

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

1. Создать новый документ в среде текстового процессора.

2. Установить параметры страницы.

3. Установить обрамление страницы.

4. Установить 2 колонки.

5. Вставить рисунок из коллекции рисунков.

6. Установить выравнивание по центру строки.

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

8. Вставить объект WordArt в качестве заголовка.

9. Набрать текст и подпись.

10. Подобрать параметры текста опытным путем.

III этап. Компьютерный эксперимент

1. Пошаговый просмотр.

2. Просмотр документа.

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

IV этап. Анализ результатов

♦ Если вид объекта не соответствует замыслу, изменить значения параметров объекта.

♦ Если вид документа не соответствует замыслу, откорректировать модель.

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

ЗАДАЧА 2.4. Научный текст

I этап. Постановка задачи


ОПИСАНИЕ ЗАДАЧИ

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

Оформите как научный текст фрагмент материала из учебника по физике или математике.

ЦЕЛЬ МОДЕЛИРОВАНИЯ

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

ФОРМАЛИЗАЦИЯ ЗАДАЧИ

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

II этап. Разработка модели

ИНФОРМАЦИОННАЯ МОДЕЛЬ

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

КОМПЬЮТЕРНАЯ МОДЕЛЬ

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

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

III — IV этапы. Компьютерный эксперимент и анализ результатов

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

Понятен ли текст?

Какие приемы оформления способствуют лучшему пониманию?

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

2.5. Наградной диплом.

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

РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ

1. Рассмотрите примеры дипломов, предлагаемые, например, в среде Word.

2. Используйте обрамление страницы.

3. Для создания красивых полос используйте символы шрифта Wingdings английской раскладки клавиатуры En.

2.6. Объявление.

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

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

Составьте эскиз объявления на выбранную тему.

РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ

Для указания в объявлении контактного телефона используйте инструментарий встроенной векторной графики.

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

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

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 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-файлы представлены только в архивах.
Рекомендуем скачать работу.

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

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

Вопрос:

Какие из ныне существующих, на 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.

Методы максимального неискажающего сжатия Текст научной статьи по специальности « Автоматика. Вычислительная техника»

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


В статье приводится обзор методов сжатия с точки зрения достижения наибольшей степени сжатия «типичных» даншх. Особое внимание уделено контекстному моделированию (КМ) и методам, использующим PPM (Prediction by Partial Match — предсказание по частичному совпадению), которые достигают наибольшей известной степени сжатия. Рассмотрены наиболее существенные недостатки КМ. Предложены три возможных пути повышения эффективности КМ: ассоциативное КМ, использование удаленных контекстов и двустороннее КМ.

Похожие темы научных работ по автоматике и вычислительной технике , автор научной работы — Богатов Роман Николаевич,

Текст научной работы на тему «Методы максимального неискажающего сжатия»

0 ж S s i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

— объем оперативной памяти, необходимой для разжатия.

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

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

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

При многопроходном сжатии производится пред1 варительный анализ всего объема данных с целью выявления их внутренней структуры, осуществления возможной декомпозиции, выбора модели для сжатия и настройки параметров модели. На последнем проходе на основе собранной статистики осуществляется сжатие данных с предварительным кодированием информации, необходимой для осуществления разжатия. Однопроходные методы сжатия не используют предварительного анализа всего объема данных. Сжатие осуществляется из априорного предположения о природе данных, и на основе уже обработанной части подстраиваются параметры модели (производится адаптация).В1981 годуй. Й. РиссанениГ. Г. Лангдон предложили называть такой подход универсальным кодированием и выделять в нем две функциональные составляющие, моделирование и кодирование, осуществляемые последовательно для сжатия каждого сообщения источника [ 1 ]. Модель, в конечном счете, является способом оценки вероятностей возможных значений следующего ожидаемого сообщения источника. Задачей кодера является, используя полученные от модели вероятности, построить для очередного сообщения сжатый код, максимально приближенный по числу бит к энтропии этого сообщения. После кодирования модель производит необходимую адаптацию, оценивает вероятности возможных значений следующего» сообщения, новое сообщение вместе с априорными оценками модели передается кодеру и кодируется, после чего цикл повторяется для каждого кодируемого сообщения. Такая последовательность обновления модели позволяет осуществить аналогичные действия при разжатии: на основании текущих оценок модели декодер производит восстановление значения сжатого сообщения, модель адаптируется и подготавливает декодер для принятия следующего сообщения. Только небольшая часть современных методов сжатия, обеспечивающих высокую степень сжатия типичных данных, не использует явного моделирования как функционально отделимого элемента, К ним относятся, в частности, методы, использующие ВШТ (см. далее в статье).

Илон Маск рекомендует:  Азы jQuery

Для достижения максимальной степени сжатия требуется построение модели, адекватной источнику входных данных. Выбор способа кодирования промоделированных данных влияет на степень сжатия в меньшей степени. Так, например, в связке со словарным моделированием для повышения быстродействия часто используется равномерное кодирование (схемы 1X77, ЬгББ и др.). Разница в степени

сжатия по сравнению с методами, использующими оптимизированное кодирование (ЬХН, ЬгРв, 12С и др.), является гораздо меньшей величиной, чем в случае использования различных типов моделирования и одного метода кодирования [2,3].

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

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

■^Большинство методов КМ являются стохастическими, оценивающими вероятности значений следующего элемента данных на основе статистики по обработанной части и текущего контекста. Исключение составляют методы, использующие преобразование Барроуза-Уиллера (BWT, сокр. от англ. Burrows-Wheeler Transform), которое избавляет данные от контекстной избыточности с помощью сортировки. Среди стохастических методов могут быть выделены использующие явное взвешивание оценок текущих (активных) контекстов (взвешивание контекстного дерева или CWTöt англ. Context Tree Weighting, динамическое Марковское сжатие или DMC от англ. Dynamic Markov Compression и др.) и методы, использующие неявное взвешивание с помощью техники предсказания по частичному совпадению (РРМ, сокр. от англ. Prediction by Partial Match), обеспечивающие наибольшую известную степень сжатия типичных данных и получившие наибольшее распространение.

Суть классического РРМ, предложенного в 1984г. Дж. Г. Клэари (Cleary) и И. X. Уиттеном (Witten) [4), заключается в следующем. Пусть последними символами источника были. sk_3sk2sk, и имеется М контекстных моделей, предсказывающих значение следующего символа sk на основе статистики, накопленной по контекстам разной длины. Контекстная модель порядка т содержит словарь контекстов (цепочек символов) длины т, встречавшихся ранее более одного раза, и для каждого контекста — счетчики символов, которые ранее встречались следующими за ним. Для данного случая я!-тая модель обеспечит статистику по цепочкам вида sk_m. sk_2sk fx, встречавшимся ранее, отличающимися значением х. Кроме М контекстных моделей используются две условных модели нулевого и минус первого порядка. Модель нулевого порядка предсказывает значение sk на основе накопленных частот встретившихся символов; модель минус первого порядка полагает все возможные значения sk равновероятными.

Для оценки значения sk выбирается одна из М + 2 моделей, обладающая статистикой по текущему контексту, и предпринимается попытка закодировать sk на основе ее распределения вероятностей. В классическом варианте модели просматриваются, начиная со старших порядков. Если выбранная модель не может закодировать sk (такое значение в данном контексте не ожидалось), то кодируется код ухода, означающий необходимость использования другой модели. Если все М контекстных моделей и модель нулевого порядка выдадут код ухода, s, кодируется равномерным кодом в модели минус первого порядка.

Оценка вероятности ухода (ОВУ) является одной из ключевых проблем сжатия с использованием РРМ. Большинство известных методов априорной ОВУ (методы А, В [4], С, D [5], Р, X, ХС [3]) используют только три величины: С — частоту появления данного контекста ранее; S — кол-во различных символов, появлявшихся ранее после данного контекста и S»1 — кол-во различных символов, появлявшихся ранее после данного контекста только / раз. Большую точность дают адаптивные методы ОВУ, использующие повторную оценку ухода (SEE, сокр. от англ. Secondary Es-

cape Estimation), основанную на текущей статистике уходов. Адаптивные методы Z [6] Ч. Блума (Bloom) с вариациями,SEE-dl hSEE- i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

— специальная обработка кода конца строки (EOL removing; ЕОЕотангл. End Of Line);

— грамматический и лексический разбор (LIPT и StarNT [13], Lexical Attraction [14]).

Другой полезной дополнительной техникой является использование разреженных контекстов (sparse contexts), которые представляют собой последовательности сообщений, чередующихся с пустыми позициями в различных комбинациях, например, имеющих вид sm □ sm_2. s6 □ □ s3 □ s.1sv где m — длинна контекста; s. — фиксированные значения сообщений; символом □ отмечены свободные позиции. Разреженный контекст считается наступившим при совпадении всех фиксированных значений сообщений с сообщениями источника в тех же позициях. Статистика по разреженному контексту является суммарной статистикой по обыкновенным контекстам, попадающим подданный шаблон. Разреженные контексты используются в большинстве современных архиваторов, основанных на КМ, и позволяют «перешагивать» через сообщения-исключения, нарушающие текущие контекстные зависимости (например, коды EOL).

Однако древовидно-контекстные Марковские модели, лежащие в основе всех существующих методов стохастического КМ, имеют два существенных ограничения:

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

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

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

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

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

Обратимые и необратимые методы сжатия. Привести примеры методов сжатия

Читайте также:

  1. I. Методы формирования сознания, методы убеждения
  2. I. Стили руководства. Методы принятия управленческих решений. Управленческая решетка Блейка — Моутона.
  3. I. Структурные методы
  4. II ПОСМЕРТНЫЕ МЕТОДЫ
  5. III) Методы управления 1 страница
  6. III) Методы управления 2 страница
  7. III) Методы управления 3 страница
  8. III. Внедрение и освоение новой техники, технологии эксплуатации и ремонта, эффективных и безопасных методов организации производства и труда.
  9. IV. Методы изображения действительности.
  10. IV. Методы изображения действительности.
  11. IV. Современные методы усиления фундаментов.
  12. O Понятия, методы и области применения

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

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

• .JPG для графических данных;

• .МPG для видеоданных;

• .МРЗ для звуковых данных.

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

• .GIF, .TIF, .PCX и многие другие для графических данных;

• .АVI для видеоданных;

• .ZIP, .ARJ, RAR, .LZH, ,LH, .CAB и многие другие для любых типов данных.

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

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

Например, для последовательности: 0; 0; 0; 127; 127; 0; 255; 255; 255: 255 (всего 10 байтов) образуется следующий вектор:

Значение Коэффициент повтора

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

0; 3; 127; 2; 0; 1; 255; 4 (всего 8 байтов). В данном примере коэф­фициент сжатия равен 8/10 (80 %).

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

Дата добавления: 2015-04-24 ; Просмотров: 1747 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

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

Опрос

Новички

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

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

Пожалуй, наиболее простой способ оценки реализуется с помощью по­луадаптивного моделирования и заключается в предварительном подсчете безусловной частоты появления символов в сжимаемом блоке. Полученное распределение вероятностей используется для статистического кодирования всех символов блока. Если, например, такую модель применить для сжатия текста на русском языке, то в среднем на кодирование каждого символа бу­дет потрачено примерно 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