Моделирование при сжатии текстовых данных дальhейшие исследоваhия


Содержание

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

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

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

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

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

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

Глава 1. Анализ теоретических и экспериментальных основ моделирования алгоритмов сжатия 12

1.1. Задачи, для решения которых используется сжатие данных 12

1.2. Анализ избыточности источников сообщений 19

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

1.4. Анализ и обоснование критериев оценки эффективности алгоритмов сжатия Теоретические подходы к сжатию 52 источников информации

1.5. Определение требований к критериям оценки АС , 54

1.6. Пример получения зависимости Td(Kc) 57

1.7. Модель разбиения пространства объектов по вектору признаков 62

Выводы по первой главе 68

Глава 2 Оценка эффективности и классификация алгоритмов обратимого сжатия 69

2.1. Обоснование новых критериев и классификация алгоритмов сжатия на основе файловых признаков 69

2.2. Классификация алгоритмов сжатия по временным критериям 94

2.3. Оценка.сложности вектора признаков АС 102

2.4. Анализ результатов классификации 110

Выводы по второй главе — 111

Глава 3. Моделирование алгоритма сжатия на основе выделения граничной точки 113

3.1. Постановка общей задачи сжатия табличных данных 113

3.2. Оценка аппаратных затрат на реализацию сжатой таблицы 116

3.3. Метод сжатия на основе выделения граничной точки 117

3.4. Анализ функции F(x) — 118

3.5. Нахождение граничной точки 120

3.6. Избыточность множеств X, Y и формирование S и X 122

3.7. Формирование множеств О и Y 129

3.8. Нахождение граничных точек 132

3.9. Определение нагрузки на разрядный вход регистра результата. Периодичность узловых значений 139

3.10. Графическая интерпретация метода 141

3.11. Выбор функциональной системы генератора функции F(x) 145

Выводы по третьей главе 152

Глава 4. Анализ результатов исследования и практические рекомендации 153

4.1. Применение таблиц замены для разработки алгоритма обратимого сжатия данных 153

4.2. Оценка эффективности нового алгоритма сжатия 161

4.3. Уточнение функций классификаций 161

Выводы по четвертой главе 163

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

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

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

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

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

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

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

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

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

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

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

Важно, чтобы значения вероятностей, присваемых моделью не были бы равны О, т.к. если символы кодируются (-logp) битами, то при близости вероятности к О, длина кода стремится к бесконечности. Нулевая вероятность имеет место, если в образце текста символ не встретился ни разу — частая ситуация для адаптированных моделей на начальной стадии сжатия, Она известна как проблема нулевой вероятности, которую можно решить несколькими способами. Один подход состоит в том, чтобы добавлять 1 к счетчику каждого символа іт.ші. Альтернативные подходы в основном основаны на идее выделенил одного счетчика для всех новых (с нулевой частотой) символов! для последующего использования его значения между ними №т/ Срранени, етии хтрратеий ммжет тытт ьайденн в mm Оно показывает что ни один метод не имеет впечатляющего преимущества над другими хотя метод выбранный в ет хорошие oZne характеристики

Классификация алгоритмов сжатия по временным критериям

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

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

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

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

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

На данном этапе формировалась матрица из существую-щих алгоритмов обратимого сжатия (см. приложение 3). В ка-честве признаков были определены следующие параметры: / -коэффициент сжатия; Тс- время сжатия (компрессии) исходного файла, с; Td- время восстановления (декомпрессии), с; . Ус- объем (размер) исходного файла после сжатия, байт. Этап 2. Увеличение размерности исходной матрицы, Исходная матрица была дополнена новыми временными признаками, связанными со значениями Тс и Td, для определения которых применялись следующие приемы: Примечание. Признаки Ц. Т6 были определены с целью получения временных критериев оценки относительного времени протекания процессов сжатия и восстановления, независящих от конфигурации ЭВМ (например, от модели процессора зависит тактовая частота, которая влияет на временные параметры при небольших объемах исходного файла). Для оценивания временных параметров АС были определены так:ке следующие признаки: где $с- относительная скорость процесса сжатия, байт/с; -относительная скорость процесса декомпрессии, байт/с; АV- изменение размера исходного файла (AF = Vinp-Vc), байт; Vinp- размер исходного файла до сжатия, байт; &cd относительная скорость процесса сжатия-декомпрессии, байт/с. Этап 3. Изучение свойств признаков и их выбор. На этом этапе проводилась классификация методом кластерного анализа (методом к- средних) с целью получения средних значений признаков для каждого кластера (см. рис. 15).

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

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

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

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

4. Определение вида операции восстановления. Необходимо найти такую операцию w, которая обеспечивала бы минимальное время восстановления данного и небольшую точ-ность воспроизведения данных и имела бы наименьшую сложность по сравнению с другими операциями. Решение этой задачи базируется на Р1следовании свойств зависимости y = f(x), реализуемой с помощью таблшш.

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

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

Предлагаемый метод представляет интерес по ряду сле дующих причин: 1) учет симметрии узловых значений мно жеств адресов и табличных значений относительно некоторой граничной точки дает возможность существенного изменения избыточности, т.е. проведения сжатия данных; 2) воспроизведение функциональной зависимости производится путем суперпозиции двух функций за минимально возможное время; 3) метод в основном охватывает класс функций F(x) = a/(bx+c), которые широко применяются при моделировании сигналов в радиотехнических системах; 4) исследование сжатия таблиць, функции Чх дает дополнительные знания о величинеизбыточности в этой таблице, что позволяет осуществлять ее сравнение с величиной избыточности, выявляемой и устраняемой другими методами сжатия; 5) используется комбинирование равномерного и неравномерного разбиений входного кода.

Применение таблиц замены для разработки алгоритма обратимого сжатия данных

Сначала, из W4 можно определить, что частоты символов s\, 52 53 О 1 в правых столбцам будут равны 2 2 I2 3 соответ-ственно, из которых подсчитываете, тип (І, I,О,2,3)). В за-ключении, из us, не данной здесь, декодер определяет, какие символы заполняют семь пустых позиций. (Из типа (1,1,0,2,3) декодер определяет порядок кодирования М5.) Определим понятия кода источника без потерь, кода ие-рархического источника без потерь, кода последовательного источника с целью сравнения их в дальнейшем. Коды источника без потерь. Введем некоторые обозначения. Если п — положительное целое число, то у/п — <єп, 6п) -код источника /7-го порядка без потерь есть пара, в которой: 1) єп - взаимно однозначное отображение из Лп на префиксное подмножество <0,1>; 2) #„=„- — обратное отображение е„. Представляя код (є„, 8п) источника «-го порядка без потерь, отображение єп назовем-кодером, отображение 6п — деко-дером Последовательность w-(W «-\ 2 ) в котоРОЙ ш„ -код источника «-ого порядка без потерь «для каждого « в дальнейшем будем называть алгоритмом обратимого сжатия данных, Если i, удовлетворяющую равенство Щ). Каждая тх может быть сформирована, начиная с произвольной (исходной) таблицы, представляющей строку данных х, которую применением пяти правил сокращения пре образуют в таблицу наименьшей сложности /Ш/. Таблица наи меньшей сложности формируется за конечное число шагов со кращений. Например, если начать с исходной таблицы замены, состоящей из одного единственного ряда (so, х), то начальное значение функции сложности эквивалентно (2/?-1), следова тельно в этом случае необходимо (2п-2) шагов сокращений чтобы достигнуть таблицы наименьшей сложности. , Коды последовательного источника без потерь.

«ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ АНАЛИЗА И МОДЕЛИРОВАНИЯ ТЕКСТОВЫХ ДАННЫХ Монография Воронеж Издательство «Научная книга» УДК . »

Л.С. Ломакина, А.С. Cуркова

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

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

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

Издательство «Научная книга»

Рецензенты:

Турлапов В.Е. д-р. техн. наук (Нижегородский государственный

университет им. Н.И. Лобачевского)

д-р физ.-мат. наук (Институт прикладной физики РАН)

Л 74 Ломакина, Л.С. Информационные технологии анализа и моделирования текстовых структур: Монография / Л.С. Ломакина, А.С. Суркова. – Воронеж: Издательство «Научная книга», 2015. – 208 c.

ISBN 978-5-98222-863-5 В книге излагаются актуальные проблемы построения моделей текстовых данных и создания на их основе систем обработки и анализа текстов с учетом структурных особенностей текстов. Основные задачи анализа текстовых данных кластеризация, классификация,

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

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

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

Рис. 47. Табл. 27. Библиогр.: 131 назв.

УДК 004.912 ББК 32.81 Л 74 © Ломакина Л.С., Суркова А.С., 2015 ISBN 978-5-98222-863-5

СОДЕРЖАНИЕ

Часть I. Методологические аспекты анализа и моделирования текстовых данных

1. Основные задачи анализа и обработки текстовых данных. 8

2. Основные принципы анализа текстовых данных

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

2.2. Принцип нечеткой логики

2.3. Принцип обучающихся систем

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

Часть II. Теоретические аспекты анализа и обработки текстовых данных

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

4.1. Основные понятия и определения

4.2. Структурно-статистический подход

4.3. Информационный подход

4.4. Использование N-грамм

4.5. Использование моделей сжатия

5. Основные аспекты нечеткой логики

5.1. Основные понятия и определения

5.2. Модели нечеткой кластеризации

6. Основные аспекты обучающихся систем

6.1. Модель процесса обучения

6.2. Алгоритмический подход к построению обучающихся систем 122

6.3. Задачи классификации в обучающихся системах

6.4. Основные понятия и определения нейросетевых технологий. 133 Часть III. Практические аспекты анализа и обработки текстовых данных

7. Алгоритмическое и программное обеспечение анализа и обработки текстов

7.1. Алгоритмы на основе структурно-иерархического представления текста

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

7.3. Нечеткие алгоритмы в задачах анализа и обработки текстов. 151

7.4. Алгоритмы с использованием нейросетевых технологий. 163

7.5. Алгоритмы с использованием деревьев принятия решений. 166

8. Практическая реализация алгоритмов решения основных задач 171

8.1. Примеры кластеризации текстовых данных

8.2. Примеры классификации текстовых данных

8.3. Примеры идентификации текстовых данных

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

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

Область, занимающаяся проблемами обработки все увеличивающегося объема текстовой информации, получила название Text Mining. На русский этот термин можно перевести как Интеллектуальный анализ текстов аналогично уже устоявшемуся понятию Data Mining – интеллектуальный анализ данных. Предметную область Text Mining как согласованную совокупность задач можно описать следующим образом. К числу традиционных проблем можно отнести задачи определения авторства, автоматического извлечения ключевых слов, аннотирования и реферирования, кластеризации и классификации по тематическим категориям и т.д. К недавно возникшим задачам относятся проблема анализа текстов в глобальной сети для обеспечения безопасности и выявления потенциально опасных или нежелательных сообщений, а также задачи, связанные с многоязыковыми текстами и проблемой «переводного» плагиата и заимствования.

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

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

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

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

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

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

В третьей части в разделе «Алгоритмическое и программное обеспечение анализа и обработки текстов» приведены конкретные алгоритмы анализа текстовых данных, основанные на системном представлении текстов. Рассмотрены базовые нечеткие методы кластеризации, такие как fuzzy c-means (FCM), Kernel Fuzzy Clustering и др. и предложенные модификации алгоритмов классификации и кластеризации на основе нечетких отношений. Также в данном разделе описаны алгоритмы решения основных задач анализа текстов на основе нейронных сетей, деревьев принятия решений и подхода Random forest.

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

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

Библиографический список Андреев А.М., Березкин Д.В., Морозов В.В., Симаков К.В. Метод кластеризации документов текстовых коллекций и синтеза аннотаций кластеров // Труды 10-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции»

– RCDL’2008, Дубна, Россия, 2008. с 220-229 Арапов М.В. Квантитативная лингвистика. – М.: Наука, 1988. – 184 с.

Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Методы и 3.

модели анализа данных: OLAP и Data Mining. – СПб.: БХВ-Петербург, 2004. – 336 с.

Белозерова Н.Н. Можно ли поверить дискурс фракталом? //Язык и литература, 2002, №16. – Тюмень, изд-во ТюмГУ, 2002.

Белоногов Г.Г., Кузнецов Б.А. Языковые средства автоматизированных 5.

информационных систем. М., 1983. Мельников Г.П. Системный подход в лингвистике. // Системные исследования. Ежегодник. – М.: Наука, 1972.

Вапник В.Н., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). М., Наука. 1974. 416 с.

Верещагин Н.К., Успенский В.А., Шень А. Колмогоровская сложность и 7.

алгоритмическая случайность. – М.: МЦНМО, 2013.

Воронцов К.В. Машинное обучение (курс лекций). Режим доступа:

Гальперин И.Р. Текст как объект лингвистического исследования – М.:

Наука, 1981. – 140 с.

Гладких А.В. Синтаксические структуры естественного языка в автоматизированных системах сообщений. – М.: Наука, 1985.

Городецкий Б.Ю. Компьютерная лингвистика: моделирование языкового 11.

общения //Новое в зарубежной лингвистике. Вып. 24. — М., 1989.

Дмитриев А.С. Хаос, фракталы и информация //Наука и жизнь, 2001, №5 12.

Дюран Б., Одел П. Кластерный анализ. М., Статистика, 1977. – 128 с.

Егорушкин А. У каждого свой язык. //Компьютера – 2002, №21.

Еремеев А.П. Построение решающих функций на базе тернарной логики 15.

в системах принятия решений в условиях неопределенности // Изв. РАН.

Теория и системы управления. 1997. N 5. — с. 138-143 Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир. – 1976. – 164 с.

Заде Л.А. Размытые множества и их применение в распознавании образов 17.

и кластер-анализе // Классификация и кластер. М.: Мир, 1980., с. 208-247 Колмогоров А.Н. Три подхода к определению понятия «Количество информации» // Новое в жизни, науке, технике. Сер. “Математика, кибернетика”. 1991, №1, стр. 24-29 Костышин А.С. О применимости некоторых формальных методов для исследования полных строений текстов. //Материалы конференции КВАЛИСЕМ-2000 – Новосибирск, изд-во Новосибир. гос. пед. ун-та., 2000.

Кофман А. Введение в теорию нечетких множеств. – М., Радо и связь, 20.

Ландэ Д.В., Снарский А.А., Безсуднов И.В. Интернетика. Навигация в 21.

сложных сетях: модели и алгоритмы. – M.: Либроком, 2009. – 264 с.

Леоненков А.В. Нечеткое моделирование в среде Matlab и fuzzyTECH. – 22.

С.Пб.: BHV-Санкт-Петербург, 2003. – 736 с.

Леонтьева Н.Н. Динамика единиц в семантических структурах. //Труды 23.

Международного семинара Диалог-2002 по компьютерной лингвистике и ее приложениям. Том 1. Теоретические проблемы. – М., 2002.

Лингвистический энциклопедический словарь. – М.: 1990.

Ломакин Д.В., Панкратова А.З., Суркова А.С. Золотая пропорция как инвариант структуры текста. // Журнал «Вестник Нижегородского университета им. Н.И. Лобачевского», 2011, №4, с. 196-199.

Ломакина Л.С., Мордвинов А.В., Суркова А.С. Построение и исследование 26.

модели текста для его классификации по предметным категориям. // Системы управления и информационные технологии, 2011, №1(43), с. 16-20.

Ломакина Л.С., Родионов В.Б., Суркова А.С. Иерархическая кластеризация текстовых документов. // Системы управления и информационные технологии, 2012, № 2(48), с. 39-44.

Ломакина Л.С., Суркова А.С. Автоматизированные информационнопоисковые системы. Задачи. Принципы. Методология: учеб. пособие / Л.С. Ломакина, А.С. Суркова; Нижегор. гос. техн. ун-т им. Р.Е. Алексеева. – Н. Новгород, 2011. – 109 с.

Ломакина Л.С., Суркова А.С., Буденков С.С. Кластеризация текстовых 29.

данных на основе нечеткой логики // Системы управления и информационные технологии, №1(55), 2014. – С. 73-77.

Мартыненко Г.Я. Основы стилеметрии. – Л.: Изд-во ЛГУ, 1988. – 176 с.

Мельничук А. С. Понятие системы и структуры языка. // Вопросы языкознания, 1970, №1. С. 27 Мельчук И.А. Русский язык в модели «Смысл Текст». Москва-Вена, 32.

Минский М. Фреймы для представления знаний. — М.: Энергия. 1979.

Москальская О.И. Грамматика текста. М.: Наука, 1981.

Москальчук Г.Г. Структура текста как синергетический процесс. М.:

УРСС, 2003. Москальчук Г.Г. Структурная организация и самоорганизация текста. – Барнаул, 1998.

Мурзин Л.Н., Штерн А.С. Текст и его восприятие – Свердловск, 1991.

Нариньяни А.С. Автоматическое понимание текста — новая перспектива // 37.

Труды международного семинара Диалог-97 по компьютерной лингвистике и ее приложениям. — Москва, 1997, с. 203-208.

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

//Вычислительная лингвистика. М.: Наука, 1976.

Нечеткие множества в моделях управления и искусственного интеллекта 39.

/ Под ред. Д.А.Поспелова. – М., Наука, 1986. 312 с.

Нечеткие множества и теория возможностей. Последние достижения / 40.

Под ред. Р.Р.Ягера. – М.: Радио и связь, 1986.– 408 с.

Орлов Ю.К. Обобщенный закон Ципфа-Мандельброта и частотные 41.

структуры информационных единиц различных уровней.

//Вычислительная лингвистика. М.: Наука, 1976.

Поликарпов А.А. Циклические процессы в становлении лексической системы языка: моделирование и эксперимент – М., 2001.

Пономаренко И.Н. Фрактал в структуре художественного текста 43.

//Русский язык: исторические судьбы и современность. II Международный конгресс русистов-исследователей. – М., 2004.

Прангишвили И.В. Системный подход и общесистемные закономерности.

– М.: СИНТЕГ, 2000, 528с.

Прикладная статистика: Классификации и снижение размерности: Справ.

изд. / Под ред. С. А. Айвазяна. — М.: Финансы и статистика, 1989. — 607 с.

Романов А.С. Методика идентификации автора текста на основе аппарата 46.

опорных векторов // Доклады ТУСУРа. – 2009. – № 1 (19), ч. 2. – С. 36–42 Руспини Э.Г. Последние достижения в нечетком кластер-анализе // Нечеткие множества и теория возможностей: Последние достижения / Под ред. Р.Р. Ягера; — М: Радио и связь, 1986.— с. 114-132.

Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. — М.: Горячая линия — Телеком, 2006.

Рыжов А.П. Элементы теории нечетких множеств и измерения нечеткости. М., Диалог-МГУ, 1998.

Сайт, посвященный литературоведческой атрибуции: http://corneillemoliere.com/.

Сафронова Ю.Б. Некоторые системно-количественные характеристики 51.

лексико-семантических парадигм разных видов. //Уч. зап. ТГУ. Вып. 745.

Скороходько Э.Ф. Семантические сети и автоматическая обработка текста. Киев, Наукова думка, 1983. – 218 с.

Сметанин Ю. Г., Ульянов М. В. Мера символьного разнообразия: подход 53.

комбинаторики слов к определению обобщенных характеристик временных рядов // Бизнес-информатика №3 (29) 2014. с. 40–48.

Сметанин Ю.Г., Ульянов М.В. Мера символьного разнообразия – характеристика временных рядов. // Materials of the III International Scientific Conference «Information-Management Systems and Technologies». Odessa.

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

//Системные исследования. Ежегодник. — М.: Наука, 1991. с.124-141.

Солганик Г.Я. Стилистика текста. – М., 1997.

Солнцев В.М. Язык как системно-структурное образование. М.: Наука, 57.

Суркова А.С. Идентификация текстов на основе информационных портретов // Вестник Нижегородского университета им. Н.И. Лобачевского, 2014, № 3 (1), с. 145–149 Суркова А.С., Родионов В.Б. Алгоритм разбиения неструктурированного 59.

множества текстовых объектов // Научно-технический вестник Поволжья.– Казань, 2013г. — №5. – с.298-300 Турыгина Л.А. Моделирование языковых структур средствами вычислительной техники – М., 1988

Уфимцев Р. Тексты как фракталы. Режим доступа:

Хмелев Д.В. Классификация и разметка текстов с использованием методов сжатия данных. Краткое введение:

Хьетсо Г. и др. Кто написал «Тихий Дон»? (Проблема авторства «Тихого 63.

Дона») – М., 1989 Цыпкин Я.З. Основы теории обучающихся систем, М., Наука, 1970, 252 с.

Шевелёв О.Г. Методы автоматической классификации текстов на естественном языке: Учебное пособие. – Томск: ТМЛ-Пресс, 2007. 144 с.

Шеннон К. Э. Математическая теория связи // Работы по теории информации и кибернетике/ Пер. С. Карпова. – М.: ИИЛ, 1963. – 830 с.

Шрейдер Ю.А., Шаров А.А. Системы и модели – М.: Радио и связь, 1982.

Штовба С.Д. Введение в теорию нечетких множеств и нечеткую логику.

Шульгин В.И. Основы теории цифровой связи. Харьков, ХАИ, 2008, 184 с.

70. Advances in Fuzzy Clustering and its Applications. Editor(s): J. Valente de Oliveira, W. Pedrycz. John Wiley & Sons, Ltd. 2007. 434 р.

71. Alrabaee S., Saleem N., Preda S., Wang L., Debbabi M. OBA2: An Onion approach to Binary code Authorship Attribution // Digital Investigation, 2014, №11, P. S94–S103

72. Bennett C.H., Gacs P., Li M., Vitanyi P.M.B., Zurek W. Information Distance // IEEE Transactions on Information Theory, 44:4(1998), pp. 1407-1423

73. Berry M. W., Kogan J. Text Mining. Applications and Theory. – Wiley, 2010.

74. Bezdek J.C. [et al.]. Fuzzy models and algorithms for pattern recognition and image processing. Springer Science + Business Media, Inc. 2005. 776 р.

75. Bloom C. New techniques in context modeling and arithmetic encoding // IEEE DCC, Los Alamitos CA, March 1996, March, p. 426.

76. Bolshakov I.A., Gelbukh A. Computational linguistics: models, resources, applications, Mexico, 2004, 186 pp.

77. Bolshoy A., Volkovich Z., Kirzhner V., Barzily Z. Genome Clustering: From Linguistic Models to Classification of Genetic Texts. Springer, 2010. 206 p.

78. Brocardo M.L., Traore I., Saad S., Woungang I. Authorship Verification for Short Messages using Stylometry // Proceedings of the IEEE International Conference on Computer, Information and Telecommunication Systems (CITS 2013), 2013, pp. 1-6.

79. Cavnar W.B. N-Gram-Based Text Filtering For TREC-2 // Proceedings of the Second Text Retrieval Conference (TREC-2). – NIST, Gaithersburg, Maryland. – 1993, pp. 171-180

80. Cavnar W.B., Trenkle J.M. N-Gram-Based Text Categorization // Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval. – Las Vegas. – 1994. P. 161–175

81. Cavnar W.B., Vayda A.J. N-gram-based matching for multi-field database access in postal applications // Proceedings of the 1993 Symposium On Document Analysis and Information Retrieval. University of Neveda. – Las Vegas.

82. Chen Hs., Chau M. Web Mining: Machine learning for Web Applications // Annual Review of Information Science and Technology, 2004, vol. № 38, pp.289-329

83. Cilibrasi R., Vitanyi P.M.B. Clustering by compression // IEEE Trans. Inf.

Theory, 2005. Vol. 51, no. 4, 1523–1545.

84. Clarke B., Fokoue E., Zhang H.H. Principles and Theory for Data Mining and Machine Learning. Springer Science, LLC, 2009, 781 p.

85. Cooley R., Mobasher B., Srivastava J. Web mining: information and pattern discovery on the World Wide Web // Proceedings of the 9th ZEEE International Conference on Tools with Artificial Intelligence, 1997, 558-567.

86. D’Urso P. Fuzzy Clustering of Fuzzy Data // Advances in Fuzzy Clustering and its Applications (eds. J. V. de Oliveira, W. Pedrycz). 2007. — pp. 155-192

87. Doyle J., Keselj V. Automatic Categorization of Author Gender via N-Gram Analysis // Proceedings of The 6th Symposium on Natural Language Processing, SNLP’2005. http://web.cs.dal.ca/

88. Dua S., Du X. Data Mining and Machine Learning in Cybersecurity. New York, 2011. 224 p.

89. Etzioni O. The world-wide web: Quagmire or gold mine? // Communications of the ACM, 1996, № 39(11), p.65-68

90. Feldman R., Sanger J. The text mining handbook. Advanced Approaches in Analyzing Unstructured Data. – Cambridge University Press. 2007. 410 p.

91. Goldberg D.E. Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley. 1989

92. Granovetter M. The Strength of Weak Ties // American Journal of Sociology, 1973, Vol. 78, No. 6., pp 1360—1380

93. Gries S.Th., Newman J., Shaoul C. N-grams and the clustering of registers.

//Empirical Language Research Journal, 2011, №5.1.

94. Hathaway, R.J. and Bezdek, J.C. Switching regression models and fuzzy clustering // IEEE Transactions on Pattern Analysis and Machine Intelligence.

1993, 1 (3): pp.195–204.

95. Hoppner F., Klawonn F., Kruse R., Runkler Th. Fuzzy Cluster Analysis:

Methods for Classification, Data Analysis, and Image Recognition. New York, John Wiley & Sons, 1999.

96. Juola P. Authorship Attribution // Foundations and Trends in Information Retrieval. Vol. 1, No. 3 (2006) 233–334

97. Kimbrell R.E. Searching for Text? Send and N-gram! // Byte, May 1998. –

98. Klein D., Manning Ch.D. A generative constituent-context model for improved grammar induction. // Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, 2002, pp. 128-135.

99. Kontostathis A., Edwards L., Leatherman A. Text mining and cybercrime // Text Mining. Applications and Theory. Ed. by Berry M. W., Kogan J. – Wiley,

100. Kosala R., Blockeel H. Web Mining Research: A Survey. ACM SIGKDD,

2000. Vol. 2, Issue 1, pp.1-15

101. Krsul I, Spafford EH. Authorship analysis: identifying the author of a program// Proc. 8th National Information Systems Security Conference, 1995, P. 514–524.

102. Lance G.N., Williams W.T. A general theory of classificatory sorting strategies. // Computer J., 1967, V.9, №4, P. 373-380.

103. Langdon G.G. and Rissanen J.J. 1981. Compression of black-white images with arithmetic coding. IEEE Trans.Commun.COM-29, 6(Jun.),858-867

104. Li M., Chen X., Li X., Ma B., Vitanyi P.M.B. The similarity metric // IEEE Trans. Inform. Th., 50:12(2004), 3250- 3264

105. Lomakina L.S., Rodionov V.B., Surkova A.S. Hierarchical Clustering of Text Documents // Automation and Remote Control, 2014, Vol. 72, No. 9, pp. 345Manning Ch.D., Raghavan P., Schutze H. Introduction to Information Retrieval. Cambridge University Press. 2008. 504 с.

107. Manning Ch.D., Schutze H. Foundations of statistical natural language processing. MIT Press., Cambridge. 1999. 680 с.

108. Miyamoto S., Ichihashi H., Honda K. Algorithms for Fuzzy Clustering. Methods in c-Means Clustering with Applications. Springer-Verlag Berlin Heidelberg. 2008. 247 р.

109. O’Connor B., Bamman D., Smith N.A. Computational Text Analysis for Social Science: Model Assumptions and Complexity // Second Workshop on Computational Social Science and the Wisdom of Crowds (NIPS 2011).

110. Parpinelli, R.S., Lopes, H.S. and Freitas, A.A. An Ant Colony Algorithm for Classification Rule Discovery // Data Mining: a Heuristic Approach, Idea Group, 2002. pp. 191-208

111. Rendon E., Abundez I., Arizmendi A., Quiroz E. Internal versus External cluster validation indexes // International journal of computers and communications. 2011, Issue 1, Vol. 5. pp.27-34

112. Rijsbergen C. J. Information retrieval. 1979, 153 p.

113. Rissanen J.J., Langdon G.G. Universal modeling and coding // IEEE Trans.

Inf. Theory IT-27. 1981. №1, pp. 12-23.

114. Rosenblum N., Zhu X., Miller B.P. Who wrote this code? Identifying the authors of program binaries // Proceedings of the 16th European conference on

Режим доступа:


Research in computer security, 2011.

115. Salton G. Automatic text processing. Addison-Wesley Publishing Company.

116. Salton G., Wong A., Yang C.S. A vector space model for automatic indexing // Communications of The ACM — CACM, 1975, vol. 18, no. 11, pp. 613-620.

117. Sanderson, C., Guenter, S. Short text authorship attribution via sequence kernels, Markov chains and author unmasking: An investigation // Proceedings of the International Conference on Empirical Methods in Natural Language Engineering, 2006, pp. 482–491

118. Sato-Ilic M., Jain L.C. Innovations in Fuzzy Clustering. Theory and Applications. Springer, 2006. 152 р.

119. Schwartz R., Tsur O., Rappoport A., Koppel M. Authorship Attribution of Micro-Messages // Conference on Empirical Methods in Natural Language Processing (EMNLP), 2013, P. 1880-1891

120. Sebastiani F. Machine Learning in Automated Text Categorization // ACM Computing Serveys, 2002. Vol. 34. – №1. P. 1–47

121. Shannon, C.E.: A mathematical theory of communication. Bell System Technical J. 27, 379–423 (1948), русский перевод: Шеннон К. Э. Математическая теория связи // Работы по теории информации и кибернетике / Пер. С. Карпова. — М.: ИИЛ, 1963. — 830 с.

122. Stamatatos. E. A Survey of Modern Authorship Attribution Methods // Journal of the American Society for Information Science and Technology, 2009. № 60(3). P.538–556.

123. Stanko S., Lu D., Hsu I. Whose Book is it Anyway? Using Machine Learning to Identify the Author of Unknown Texts // Machine Learning Final Projects,

124. Surkova A.S., Domnin A.A., Bulatov I.V., Tsarev A.A. Neural networks and decision trees algorithms – the base of automated text classification and clustering // American Journal of Control Systems and Information Technology.

125. Vapnik V.N. Statistical Learning Theory. John Wiley & Sons, Ltd. 1998. 736 р.

126. Vinh N.X., Epps J., Bailey J. Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance // The Journal of Machine Learning Research. 2010, Vol. 11, pp. 2837-2854

127. Xie X L, Beni G. A validity validity measure for fuzzy clustering // IEEE Trans. PAMI, 1991, vol. 13(8), pp. 841-847.

128. Yang Y. An evaluation of statistical approaches to text categorization. // Journal of Information Retrieval, 1999, №1. P. 67-88.

129. Zadeh L.A. Similarity relations and fuzzy orderings // Information Sciences, 1971, vol. 3, no. 2, pp. 177-200.

130. Ziv J., Lempel A. A Universal Algorithm for Sequential Data Compression // IEEE Transactions on Information Theory, 1977, 23(3), pp. 337–343

131. Ziv J., Lempel A. Compression of Individual Sequences via Variable-Rate Coding // IEEE Transactions on Information Theory. 1978, 24 (5), 530–536.

«Значение В.Г. Шевченко для развития физики высоких энергий в Московском университете В 1967 г. в Институте физики высоких энергий в Протвино был запущен ускоритель У-70 на энергию протонов 70 ГэВ, который в течение пяти лет был крупнейшим в мире. У советских физиков появилась современная база для исследований по физике высоких энергий. На это откликнулся и Московский университет. Лаборатория высоких энергий была создана в НИИЯФ МГУ в конце 1968 г. с целью развития в Московском университете. »

«А. В. ХАЛАПСИС ПОСТНЕКЛАССИЧЕСКАЯ МЕТАФИЗИКА ИСТОРИИ МОНОГРАФИЯ Днепропетровск «Инновация» УДК 130.3 ББК 87.6 + 87.21 Х 17 Рекомендована к печати Ученым советом Днепропетровского национального университета (протокол № 10 от 29 мая 2008 г.) Рецензенты: доктор философских наук Окороков В. Б. доктор философских наук Шабанова Ю. А. Халапсис А. В. Х 17 Постнеклассическая метафизика истории: Монография. – Днепропетровск: Изд-во «Инновация», 2008. – 278 с. ISBN 978–966–8676–31–4 В монографии. »

«Разбиения поверхностей на многоугольники и задачи, пришедшие из физики, химии и биологии В. М. Бухштабер МИАН имени В. А. Стеклова, МГУ имени М. В. Ломоносова, ИППИ имени А. А. Харкевича XV Летняя школа Современная математика Ратмино, 23 июля 2015 г. Лекция 1 1/43 В. М. Бухштабер Разбиения поверхностей на многоугольники. Регулярные разбиения Разбиение поверхности на многоугольники называется регулярным, если в каждой вершине сходится только три ребра, а два многоугольника пересекаются только по. »

«Интернет-журнал «НАУКОВЕДЕНИЕ» Институт Государственного управления, права и инновационных технологий (ИГУПИТ) Выпуск 2, март – апрель 2014 Опубликовать статью в журнале http://publ.naukovedenie.ru Связаться с редакцией: publishing@naukovedenie.ru УДК 330.43: 343.9.01 Кучерова Светлана Викторовна ФГБОУ ВПО Владивостокский государственный университет экономики и сервиса Россия, Владивосток1 Доцент кафедры математики и моделирования Кандидат физико-математических наук E-Mail. »

«Ученые записки Таврического национального университета имени В.И. Вернадского Серия «Физико-математические науки». Том 25 (64). 2012 г. № 1. С. 231-238 УДК 378.12 (092)(035) ВЕЛИКОЛЕПНЫЙ ОРГАНИЗАТОР И ВОСПИТАТЕЛЬ ( К 100-летию со дня рождения Рубена Григорьевича Бадальяна ) (1912-1982) Шостка В.И. Таврический национальный университет имени В.И. Вернадского, Симферополь, Украина E-mail: vshostka@yandex.ru В статье рассказывается о первом декане физического факультета Таврического национального. »

«АНАЛИЗ СТРУКТУРЫ ЗАНЯТОСТИ НАСЕЛЕНИЯ Низамиев Абдурашит Гумарович д-р геогр. наук, проф., РГСУ, филиал в городе Ош, Кыргызская Республика, г. Ош Кенешбаева Зуура Маматовна канд. экон. наук, РГСУ, филиал в городе Ош, Кыргызская Республика, г. Ош E-mail: kenzuura@rambler.ru Максутов Айдарбек Рысбаевич канд. физико-матем. наук, РГСУ, филиал в городе Ош, Кыргызская Республика, г. Ош E-mail: maks0505@mail.ru Алайчиев Эрнисбек Каныбекович канд. геогр. наук, доцент, РГСУ, филиал в городе Ош. »

«Российская Академия Естествознания Издательский дом Академии Естествознания ПРИМЕНЕНИЕ ИННОВАЦИЙ ПРИ РАЗРАБОТКЕ РАДИОТЕХНИЧЕСКИХ СИСТЕМ Коллективная монография Под общей редакцией доктора физико-математических наук, доцента М.Ю. Звездиной Рекомендовано УМО РАЕ по классическому университетскому и техническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлениям: 11.03.01 – «Радиотехника»; 11.03.02 – «Инфокоммуникационные технологии и системы. »

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

«Минобрнауки России ФБФГБОУ ВПО “Уральский государственный горный университет” Положение о структурном подразделении 4.2.3. Управление документацией СМКПСП 304.14 Положение о Бизнес-школе Бизнес-центре Екатеринбург 1. Общие положения 1.1. Положение о Бизнес-школе Бизнес-центре факультета геологии и геофизики ФГБОУ ВПО «Уральский государственный горный университет» определяет основные задачи, функции (права, обязанности), связанные с удовлетворением потребностей граждан в образовательных услугах. »

«Секция 2. Ограждающие конструкции зданий, энергои ресурсосбережение УДК. 728.3: 699.86 ТЕПЛОТЕХНИЧЕСКИЕ ОСОБЕННОСТИ НАРУЖНЫХ СТЕН МАЛОЭТАЖНЫХ ЗДАНИЙ Стерлягов А.Н., Низовцев М.И. Институт теплофизики СО РАН, г. Новосибирск С 20 мая 2011 г. постановлением Госстроя России приняты и введены в действие СП 55.13330.2011 «Дома жилые одноквартирные. Актуализированная редакция СНиП 31-02-2001» [1]. Настоящие нормы разработаны в связи с возрастающим объмом строительства и развитием рынка одноквартирных. »

«История и достижения кафедры физики СВЧ (А. А. Звягинцев) Начало XX века ознаменовалось появлением нового научного направления в физике – радиофизики. Ее бурное развитие началось с решения важных прикладных задач – задач радиолокации. Возникла и необходимость создания центра по подготовке высококвалифицированных специалистов в этой области. И не случайно выбор пал на Харьковский государственный университет им. А. М. Горького, имевший богатые традиции в области физики. Основателем харьковской. »

«Цели освоения модуля (дисциплины) 1. Цели освоения дисциплины «Основы геофизики»: формирование у обучающихся общего представления о происхождении и эволюции Земли, закономерностях физических процессов и явлений, физических полях и возможном их воздействии на биосферу. Полученные знания соответствуют целям направления ООП 022000 Экология и природопользование:подготовка выпускников к проектно-производственной деятельности в области оценки воздействия естественных и техногенных геофизических полей. »

«1 БЮЛЛЕТЕНЬ НОВЫХ ПОСТУПЛЕНИЙ 1-15 АПРЕЛЯ 2015г. В настоящий «Бюллетень» включены книги, поступившие в отделы Фундаментальной библиотеки с 1 по 15 апреля 2015 г. Бюллетень составлен на основе записей Электронного каталога. Материал расположен в систематическом порядке по отраслям знания, внутри разделов – в алфавите авторов и заглавий. Записи включают полное библиографическое описание изданий, шифр книги и место хранения издания в сокращенном виде (список сокращений приводится в Бюллетене). »

«ПОТЕНЦИАЛ СОВРЕМЕННОЙ НАУКИ, №8, НОЯБРЬ, 2015 ISSN 2312-1939 щим. Эти условия выполнены в H3S, и именно это соединение развивается из H2S при высоком давлении. Ученые в настоящее время ищут материалы с еще более высокими переходными температурами. Повышение давления, действующее на сероводород, выше 1,5 мегабара в этом случае не полезно. Это было рассчитано не только физиками теоретиками, но теперь также подтверждается в экспериментах, выполненных на практике. При еще более высоких. »

«КРАТКИЕ СООБЩЕНИЯ Самарская Лука: проблемы региональной и глобальной экологии. 2010. – Т. 19, № 2. – С. 151-156. УДК 01+09.2 В.И. ПРОКАЕВ В КУЙБЫШЕВЕ И КУЙБЫШЕВСКОЙ ОБЛАСТИ © 2010 А.А. Головлёв* Самарский государственный экономический университет, г. Самара (Россия) Поступила 10 ноября 2009 г. Рассматривается куйбышевский период биографии В.И. Прокаева Ключевые слова: В.И. Прокаев, биография, Куйбышевский плановый институт. Golovlyov A.A. V.I. PROKAEV IN THE KUIBYSHEV AND KUIBYSHEV REGION The. »

2020 www.os.x-pdf.ru — «Бесплатная электронная библиотека — Научные публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.

Методы сжатия

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

  1. II.Численные методы решения нормальных краевых задач для уравнений параболического типа. №13
  2. V. Основные методы проектирования ИС
  3. Административно-правовые методы управления
  4. Административные методы мотивации
  5. Административные методы мотивации
  6. Адсорбционные и хемосорбционные методы очистки отходящих газов
  7. Анализ» и «синтез» как общенаучные методы познания, их роль и особенности
  8. Антивирусные методы и программные средства.
  9. Аудиторская выборка. Виды и методы выборки
  10. Бесконтактные методы оценки
  11. Биологические методы борьбы с вредителями
  12. БИОЛОГИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯ ОБЪЕКТОВ СУДЕБНОЙ ЭКСПЕРТИЗЫ

Современные архиваторы

Специальные программы

Лекция 6

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

Илон Маск рекомендует:  Загрузка и выполнение javascript файлов после загрузки страницы

Сжатие данных используется очень широко. Можно сказать, почти везде. Например, документы PDF, как правило, содержат сжатую информацию. Довольно много исполняемых файлов EXE сжаты специальными упаковщиками. Всевозможные мультимедийные файлы (GIF, JPG, MP3, MPG) являются своеобразными архивами.

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

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

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

Кодирование длин серий (RLE — сокращение от run-length encoding — кодирование длин серий)

Очень простой метод. Последовательная серия одинаковых элементов данных заменяется на два символа: элемент и число его повторений. Широко используется как дополнительный, так и промежуточный метод. В качестве самостоятельного метода применяется, например, в графическом формате BMP.

Словарный метод (LZ — сокращение от Lempel Ziv — имена авторов)

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

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

Энтропийный метод (Huffman — кодирование Хаффмена, Arithmetic coding — арифметическое кодирование)

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

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

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

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

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

PPM (PPM — Prediction by Partial Matching — предсказание по частичному совпадению)

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

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

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

Метод сортировки блока данных (BWT — сокращение от Burrows Wheeler Transform — по имени авторов)

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

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

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

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

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

| следующая лекция ==>
Формат PDF | Антивирусы

Дата добавления: 2014-01-06 ; Просмотров: 1584 ; Нарушение авторских прав? ;

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

Всё о сжатии данных, изображений и видео

Сравнения кодеков

Проекты

Разделы

Сайт подключен к Orphus. Если вы заметили опечатку, выделите слово и нажмите Ctrl+Enter. Спасибо!

Моделирование для сжатия текстов


(Modeling for Text Compression)


T. Bell, I.H. Witten, J.G. Cleary


(разделы 1-2)


(разделы 3-6)


Содержание

Введение

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

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

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

Кодирование

1. Контекстуальные метода моделирования

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

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

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

1.4 Исключения

1.5 Алфавиты

1.6 Практические контекстно-ограниченные модели

1.7 Реализация

2. ДРУГИЕ МЕТОДЫ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАHИЯ

2.1 Модели состояний

2.1.1 Динамическое сжатие Маркова

2.2 Грамматические модели

2.3 Модели новизны

2.4 Модели для сжатия изображений

3. СЛОВАРHЫЕ МЕТОДЫ

3.1 Стратегия разбора

3.2 Статичные словарные кодировщики

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

3.4 Адаптированные словарное кодирование: метод Зива-Лемпела

3.4.1 LZ77
3.4.2 LZR
3.4.3 LZSS
3.4.4 LZB
3.4.5 LZH
3.4.6 LZ78
3.4.7 LZW
3.4.8 LZC
3.4.9 LZT
3.4.10 LZMW
3.4.11 LZJ
3.4.12 LZFG
3.4.13 Структуры данных для метода Зива-Лемпела

4. ВОПРОСЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ

4.1 Ограничения по памяти

4.2 Подсчет

5. СРАВHЕHИЕ

5.1 Хаpактеpистики сжатия

5.2 Требования скорости и памяти

6. ДАЛЬHЕЙШИЕ ИССЛЕДОВАHИЯ

Авторские примечания

Словарь к переводу

Литература

Об авторах, выходные данные

3. СЛОВАРHЫЕ МЕТОДЫ

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

Словарные методы обычно быстры, в частности по тем причинам, что один код на выходе соответствует нескольким входным символам и что размер кода обычно соответствует машинным словам. Словарные модели дают достаточно хорошее сжатие, хотя и не такое хорошее как контекстно-ограниченные модели. Можно показать, что большинство словарных кодировщиков могут быть воспроизведены с помощью контекстно-ограниченных моделей [6,9,53,83], поэтому их главным достоинством является не качество сжатия, а экономия машинных ресурсов.

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

3.1 Стратегия разбора

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

К сожалению тщательный разбор не обязательно будет оптимальным. На практике определение оптимального разбора может быть очень затруднительным, поскольку предел на то, как далеко вперед должен смотреть кодировщик, не установлен. Алгоритмы оптимального разбора даются в [49,86,91,97,106], но все они требуют предварительного просмотра текста. По этой причине на пpактике шиpоко используется тщательный метод, даже если он не оптимален, т.к. пpоводит однопроходное кодирование с ограниченной задержкой.

Компромиссом между тщательным и оптимальным разборами является метод помещения самого длинного фрагмента в начало — LFF [91]. Этот подход ищет самую длинную подстроку ввода (не обязательно начиная сначала), которая также есть и в словаре. Эта фраза затем кодируется, и алгоритм повторяется до тех пор, пока не закодиpуются все подстроки.

Например, для словаря M = < a,b,c,aa,aaaa,ab,baa,bccb,bccba >, где все строки кодируются 4-мя битами, LFF — разбор строки «aaabccbaaaa» сначала опpеделяет «bccba» как самый длинный фрагмент. Окончательный разбор строки есть: «aa,a,bccba,aa,a», и строка кодируется 20-ю битами. Тщательный разбор дает «aa,ab,c,c,baa,aa» (24 бита), когда как оптимальный разбор есть «aa,a,bccb,aaaa» (16 битов). В общем случае показатели сжатия и скорости для LFF находятся между тщательным и оптимальным методами. Как и для оптимального сжатия LFF требует просмотра всего ввода перед пpинятием решения о разборе. Теоретическое сравнение техник разбора можено посмотpеть в [34,49,97].

Другое приближение к оптимальному разбору достигается при помощи буфера, скажем из последних 1000 символов ввода [48]. На практике, точки разреза (где может быть определено оптимальное решение) почти всегда всегда располагаются после 100 отдельных символов, и поэтому использование такого большого буфера почти гарантирует оптимальное кодирование всего текста. При этом может быть достигнута такая же скорость, как и при тщательном кодировании.

Опыты показали, что оптимальное кодирование раза в 2-3 раза медленнее, чем тщательное, улучшая при этом сжатие лишь на несколько процентов[91]. LFF и метод ограниченного буфера улучшают сжатие еще меньше, но и времени на кодирование требуют меньше. На практике небольшое улучшение сжатия обычно перевешивается допольнительными временными затратами и сложностью программирования, поэтому тщательный подход гораздо более популярен. Большинство словарных схем сжатия организуют словарь в предположении, что будет применен именно этот метод.

3.2 Статичные словарные кодировщики

Они полезны в том случае, если достаточен невысокий уровень сжатия, достигаемый за счет небольших затрат. Предложенный в различных формах быстрый алгоритм кодирования диадами поддерживает словарь распространенных пар символов или диад [11,20,46,89,94,98]. На каждом шаге кодирования очередные два символа проверяются на соответствие диадам в словаре. Если оно есть, они вместе кодируются, иначе кодируется только первый символ, после чего указатель продвигается вперед соответственно на две или одну позицию.

Диадные коды достраиваются к существующим кодам символов. Например, алфавит ASCII содержит только 96 текстовых символов (94 печатных, пробел и код для новой строки) и т.о. часто размещается в 8 битах. Оставшиеся 160 кодов доступны для представления диад. Их может быть и больше, если не все из 96 символов используются. Это дает словарь из 256 элементов (96 символов и 160 диад). Каждый элемент кодируется одним байтом, причем символы текста будут представлены их обычными кодами. Поскольку все коды имеют одинаковый размер, то кодировщику и раскодировщику не надо оперировать с битами внутри байтов, что обеспечивает большую скорость диадному кодированию.

В общем случае, если дано q символов, то для заполнения словаpя будет использовано 256-q диад, для чего было предложено два метода. Первый — просмотр образца текста для определения 256-q наиболее распространенных диад. Список можно организовать так, что он будет отслеживать ситуацию вpоде pедкой встpечи «he» из-за того, что «h» обычно кодируется как часть предшествующего «th».

Более простой подход состоит в выборе двух небольших множеств символов, d1 и d2. Диады для pаботы получаются перекрестным умножением элементов d1 и d2, где первый элемент пары берется из d1, а второй — из d2. Словарь будет полным, если |d1|*|d2| = 256-q. Обычно и d1, и d2 содержат часто встречающиеся символы, дающие множество типа: Другая часто используемая возможность основана на идее pаспpостpаненности паpы гласная-согласная и создает множество d1 = < a,e,i,o,u,y,_ >[98].

Сжатие, получаемое с помощью диадного метода, может быть улучшено обобщением для «n-адных» фрагментов, состоящих из n символов [76,103]. Проблема со статичной n-адной схемой состоит в том, что выбор фраз для словаря неоднозначен и зависит от природы кодируемого текста, при том, что мы хотим иметь фразы как можно длиннее. Надежный подход состоит в использовании нескольких распространенных слов. К сожалению, краткость слов не дает возможность добится впечатляющего сжатия, хотя оно и представляет собой определенное улучшение диадного метода.

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

Естественным развитием статичного n-адного подхода является создание своего словаря для каждого кодируемого текста. Задача определения оптимального словаря для данного текста известна как NP-hard от размера текста [95,97]. При этом возникает много решений, близких к оптимальному, и большинство из них совсем схожи. Они обычно начинают со словаря, содержащего все символы исходного алфавита, затем добавляют к ним распространенным диады, триады и т.д., пока не заполнится весь словарь. Варианты этого подхода были предложены в [62,64, 86,90,106,109,116].

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

3.4 Адаптированные словарное кодирование: метод Зива-Лемпела

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

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

Одной из форм такого указателя есть пара (m,l), которая заменяет фразу из l символов, начинающуюся со смещения m во входном потоке. Например, указатель (7,2) адресует 7-ой и 8-ой символы исходной строки. Используя это обозначение, строка «abbaabbbabab» будет закодирована как «abba(1,3)(3,2)(8,3)». Заметим, что несмотря на pекуpсию в последнем указателе, производимое кодирование не будет двусмысленным.

Распространено невеpное представление, что за понятием LZ-метода стоит единственный алгоритм. Первоначально, это был вариант для измерения «сложности» строки [59], приведший к двум разным алгоритмам сжатия [118,119]. Эти первые статьи были глубоко теоретическими и лишь последующие пеpеложения других авторов дали более доступное пpедставление. Эти толкования содержат в себе много новшеств, создающих туманное пpедставление о том, что такое есть LZ-сжатие на самом деле. Из-за большого числа вариантов этого метода лучшее описание можно осуществить только через его растущую семью, где каждый член отражает свое решение разработчика. Эти версии отличаются друг от друга в двух главных факторах: есть ли предел обратного хода указателя, и на какие подстроки из этого множества он может ссылаться. Продвижение указателя в ранее просмотренную часть текста может быть неограниченным (расширяющееся окно) или ограничено окном постоянного размера из N предшествующих символов, где N обычно составляет несколько тысяч. Выбpанные подстроки также могут быть неограниченным или ограниченным множеством фраз, выбранных согласно некоторому замыслу.

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

Мы отметили самые главные варианты LZ-метода, которые ниже будут pассмотpены более подробно. Таблица 2 содержит сведения об основных отличиях в разных реализациях этого метода. Все они произошли от одного из двух разных подходов.

Таблица 2. Основные варианты LZ-схемы.

Имя Авторы Отличия
LZ77 Ziv and Lempel [1977] Указатели и символы чередуются. Указатели адресуют подстроку среди предыдущих N символов.
LZR Roden et al. [1981] Указатели и символы чередуются. Указатели адресуют подстроку среди всех предыдущих символов.
LZSS Bell [1986] Указатели и символы различаются флажком-битом. Указатели адресуют подстроку среди предыдущих N символов.
LZB Bell [1987] Аналогично LZSS, но для указателей применяется разное кодирование.
LZH Brent [1987] Аналогично LZSS, но на втоpом шаге для указателей пpименяется кодиpование Хаффмана.
LZ78 Ziv and Lempel [1978] Указатели и символы чередуются. Указатели адресуют ранее разобранную подстроку.
LZW Welch [1984] Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку. Указатели имеют фиксированную длину.
LZC Thomas et al. [1985] Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку.
LZT Tischer [1987] Аналогично LZC, но фразы помещаются в LRU-список.
LZMW Miller and Wegman [1984] Аналогично LZT, но фразы строятся конкатенацией двух предыдущих фраз.
LZJ Jakobsson [1985] Вывод содержит только указатели. Указатели адресуют подстроку среди всех предыдущих символов.
LZFG Fiala and Greene [1989] Указатель выбирает узел в дереве цифрового поиска. Строки в дереве берутся из скользящего окна.

описанных Зивом и Лемпелом [118,119], и помеченных соответственно как LZ77 и LZ78. Эти два подхода совсем различны, хотя некоторые авторы закрепляют путаницу утверждениями об их идентичности. Теpмин «LZ-схемы» происходят от имен их изобретателей. Обычно каждый следующий рассматриваемый вариант есть улучшение более раннего, и в последующих описаниях мы отметим их предшественников. Более подробное изучение этого типа кодирования можно найти в [96].

3.4.1 LZ77

Это была первая опубликованная версия LZ-метода [118]. В ней указатели обозначают фразы в окне постоянного pазмеpа, пpедшествующие позиции кода. Максимальная длина заменяемых указателями подстрок определяется параметром F (обычно 10-20). Эти ограничения позволяют LZ77 использовать «скользящее окно» из N символов. Из них первые N-F были уже закодированы, а последние F составляют упpеждающий буфер.

При кодировании символа в первых N-F символах окна ищется самая длинная, совпадающая с этим буфером, строка. Она может частично перекрывать буфер, но не может быть самим буфером.

Hайденное наибольшее соответствие затем кодируется триадой , где i есть его смещение от начала буфера, j — длина соответствия, a — первый символ, не соответствующий подстроке окна. Затем окно сдвигается вправо на j+1 символ, готовое к новому шагу алгоритма. Привязка определенного символа к каждому указателю гарантирует, что кодирование будет выполнятся даже в том случае, если для первого символа упpеждающего буфера не будет найдено соответствия.

Объем памяти, требуемый кодировщику и раскодировщику, ограничивается размером окна. Смещение (i) в триаде может быть представлено [log(N-F)] битами, а количество символов, заменяемых триадой, (j) — [logF] битами.

Раскодирование осуществляется очень просто и быстро. При этом поддерживается тот же порядок работы с окном, что и при кодировании, но в отличие от поиска одинаковых строк, он, наоборот, копирует их из окна в соответствии с очередной триадой. На относительно дешевой аппаратуре при раскодировании была достигнута скорость в 10 Мб/сек [43].

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

Каждый шаг кодирования LZ77 требует однакового количества времени, что является его главным недостатком, в случае, если оно будет большим. Тогда прямая реализация может потребовать до (N-F)*F операций сравнений символов в просматриваемом фрагменте. Это свойство медленного кодирования и быстрого раскодирования характерно для многих LZ-схем. Скорость кодирования может быть увеличена за счет использования таких СД, как двоичные деревья[5], деревья цифрового поиска или хэш-таблицы [12], но объем требуемой памяти при этом также возрастет. Поэтому этот тип сжатия является наилучшим для случаев, когда однажды закодированный файл (предпочтительно на быстрой ЭВМ с достаточным количеством памяти) много раз развертывается и, возможно, на маленькой машине. Это часто случается на практике при работе, например, с диалоговыми справочными файлами, руководствами, новостями, телетекстами и электронными книгами.

3.4.2 LZR

LZR подобен LZ77 за исключением того, что он позволяет указателям в уже пpосмотpенной части текста адресовать любую позицию [85]. Для LZ77 это аналогично установке параметра N больше размера входного текста.

Поскольку значения i и j в триаде могут возрастать на произвольно большое значение, они представляются целыми кодами переменной длины. Этот метод использован Элиасом [23] и помечен как C(w’). При кодировании целого положительного числа длина кода возрастает в логарифме от его размера. Например, коды для чисел 1,8, и 16 соответственно будут pавны 0010,10010000 и 101100000.

Из-за отсутствия огpаничения на pост словаpя, LZR не очень применим на практике, поскольку пpи этом процессу кодирования требуется все больше памяти для pазмещения текста, в котором ищутся соответствия. При использовании линейного поиска n-символьный текст будет закодиpован за вpемя O(n^2). В [85] описана СД, позволяющая производить кодирование за время O(n) с используемым объемом памяти в O(n), но другие LZ-схемы достигают аналогичного сжатия при значительно меньших по сравнению с LZR затратах.

3.4.3 LZSS

Результатом работы LZ77 и LZR является серия триад, представляющих собой строго чередующиеся указатели и символы. Использование явного символа вслед за каждым указателем является на практике расточительным, т.к. часто его можно сделать частью следующего указателя. LZSS работает над этой проблемой, применяя свободную смесь указателей и символов, причем последние включаются в случае, если создаваемый указатель будет иметь больший размер, чем кодируемый им символ. Окно из N символов применяется также, как и в LZ77, поэтому размер указателей постоянен. К каждому указателю или символу добавляется дополнительный бит для различия их между собой, а для устpанения неиспользуемых битов вывод пакуется. LZSS в общих чертах описан в [97], а более подробно — в [5].

3.4.4 LZB

Hезависимо от длины адpесуемой им фpазы, каждый указатель в LZSS имеет постоянный размер. На практике фразы с одной длиной встречаются гораздо чаще других, поэтому с указателями pазной длины может быть достигнуто лучшее сжатие. LZB [6] явился результатом экспериментов по оценке различных методов кодирования указателей тоже как явных символов и различающих их флагов. Метод дает гораздо лучшее чем LZSS сжатие и имеет дополнительное достоинство в меньшей чувствительности к выбору параметров.

Первой составляющей указателя есть позиция начала фразы от начала окна. LZB работает относительно этой компоненты. Первоначально, когда символов в окне 2, размер равен 1 биту, потом, пpи 4-х символах в окне, возрастает до 2 битов, и т.д., пока окно не станет содержать N символов. Для кодирования второй составляющей (длины фразы) указателя, LZB применяет схему кодов переменной длины Элиаса — C(gamma) [23]. Поскольку этот код может представлять фразу любой длины, то никаких ограничений на нее не накладывается.

3.4.5 LZH

Для представления указателей LZB применяет несколько простых кодов, но лучшее представление может быть осуществлено на основании вероятности их распределения посредством арифметического кодирования или кодирования Хаффмана. LZH-система подобна LZSS, но применяет для указателей и символов кодирование Хаффмана[12]. Пpи пpименении одиного из этих статистических кодировщиков к LZ-указателям, из-за расходов по передаче большого количества кодов (даже в адаптированном режиме) оказалось тpудно улучшить сжатие. Кроме того, итоговой схеме не хватает быстроты и простоты LZ-метода.

3.4.6 LZ78

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

Например, строка «aaabbabaabaaabab», как показано на pисунке 6, делится на 7 фраз. Каждая из них кодируется как уже встречавшаяся ранее фраза плюс текущий символ. Например, последние три символа кодируются как фраза номер 4 («ba»), за которой следует символ «b». Фраза номер 0 — пустая строка.

Input: a aa b ba baa baaa bab
Phrase number: 1 2 3 4 5 6 7
Output: (0,a) (1,a) (0,b) (3,a) (4,a) (5,a) (4,b)

Рисунок 6. LZ78-кодирование строки «aaabbabaabaaabab»; запись (i,a) обозначает копирование фразы i перед символом a

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

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

Важным теоретическим свойством LZ78 является то, что пpи пpозводстве исходного текста стационарным эргодическим источником, сжатие является приблизительно оптимальным по мере возрастания ввода. Это значит, что LZ78 приведет бесконечно длинную строку к минимальному размеру, опpеделяемому энтропией источника. Лишь немногие методы сжатия обладают этим свойством. Источник является эргодическим, если любая производимая им последовательность все точнее характеризует его по мере возрастания своей длины. Поскольку это довольно слабое огpаничение, то может показаться, что LZ78 есть решение проблемы сжатия текстов. Однако, оптимальность появляется когда размер ввода стремится к бесконечности, а большинство текстов значительно короче! Она основана на размере явного символа, который значительно меньше размера всего кода фразы. Т.к. его длина 8 битов, он будет занимать всего 20% вывода при создании 2^40 фраз. Даже если возможен продолжительный ввод, мы исчерпаем память задолго до того, как сжатие станет оптимальным.

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

3.4.7 LZW

Переход от LZ78 к LZW параллелен переходу от LZ77 к LZSS. Включение явного символа в вывод после каждой фразы часто является расточительным. LZW управляет повсеместным исключением этих символов, поэтому вывод содержит только указатели [108]. Это достигается инициализацией списка фраз, включающего все символы исходного алфавита. Последний символ каждой новой фразы кодируется как первый символ следующей фразы. Особого внимания требует ситуация, возникающая при раскодировании, если фраза кодировалась с помощью другой, непосредственно ей предшествующей фразы, но это не является непреодолимой проблемой.

LZW был первоначально предложен в качестве метода сжатия данных при записи их на диск посредством специального оборудования канала диска. Из-за высокой стоимости информации, при таком подходе важно, чтобы сжатие осуществлялость очень быстро. Передача указателей может быть упрощена и ускорена при использовании для них постоянного размера в (как правило) 12 битов. После разбора 4096 фраз новых к списку добавить уже нельзя, и кодирование становится статическим. Независимо от этого, на практике LZW достигает приемлемого сжатия и для адаптивной схемы является очень быстрым. Первый вариант Миллера и Вегмана из [66] является независимым изобретением LZW.

3.4.8 LZC

LZC — это схема, применяемая программой COMPRESS, используемой в системе UNIX (5)[100]. Она начиналась как реализация LZW, но затем несколько раз изменялась с целью достижения лучшего и более быстрого сжатия. Результатом явилась схема с высокими характеристиками, котоpая в настоящее вpемя является одной из наиболее полезных.

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

3.4.9 LZT

LZT [101] основан на LZC. Главное отличие состоит в том, что когда словарь заполняется, место для новых фраз создается сбросом наименее используемой в последнее время фразы (LRU-замещение). Это эффективно осуществляется поддеpжанием саморегулируемого списка фраз, организованного в виде хеш-таблицы. Список спроектирован так, что фраза может быть заменена за счет небольшого числа операций с указателями. Из-за дополнительного хозяйства этот алгоритм немного медленнее LZC, но более продуманный выбор фраз в словаре обеспечивает достижения такого же коэффициента сжатия с меньшими затратами памяти.

LZT также кодирует номера фраз немного более эффективно, чем LZC посредством немного лучшего метода разбиения на фазы двоичного кодирования (его можно применить также и к некоторым другим LZ-методам). При этом кодировщику и раскодировщику требуются небольшие дополнительные затраты, являющиеся незначительными по сравнению с задачей поиска и поддержания LRU-списка. Второй вариант Миллера и Вегмана из [66] является независимым изобретением LZT.

3.4.10 LZMW

Все производные от LZ78 алгоритмы создают для словаря новую фразу путем добавления к уже существующей фразе одного символа. Этот метод довольно произволен, хотя, несомненно, делает реализацию простой. LZMW [66] использует другой подход для формирования записей словаря. Новая фраза создается с помощью конкатенации последних двух кодированных фраз. Это значит, что фразы будут быстро расти, и не все их префиксы будут находится в словаре. Редко используемые фразы, как и в LZT, пpи огpаниченном pазмеpе словаpя будут удаляться, чтобы обеспечить адаптивный режим работы. Вообще, стратегия быстрого конструирования фразы LZMW достигает лучшего сжатия, по сpавнению с наращиванием фразы на один символ за раз, но для обеспечения эффективной реализации необходима продуманная СД.

3.4.11 LZJ

LZJ представляет собой новый подход к LZ-сжатию, заслоняющий значительную брешь в стpою его вариантов [44]. Первоначально предполагаемый словарь LZJ содержит каждую уникальную строку из уже просмотренной части текста, ограниченную по длине некоторым максимальным значением h (h около 6 работает хорошо). Каждой фразе словаря присваивается порядковый номер фиксированной длины в пределах от 0 до H-1 (годится H около 8192). Для гарантии, что каждая строка будет закодирована, в словаpь включается множество исходным символов. Когда словарь полон, он сокращается удалением строки, появлявшейся во входе только один раз.

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

3.4.12 LZFG

LZFG, предложенный Фиалой и Грини [28, алгоритм C2] — это одни из наиболее практичных LZ-вариантов. Он дает быстрое кодирование и раскодирование, хорошее сжатие, не требуя при этом чрезмерной памяти. Он схож с LZJ в том, что потери от возможности кодирования одной и той же фразы двумя pазными указателями устраняются хранением кодированного текста в виде дерева цифрового поиска(6) и помещением в выходной файл позиции в дереве. Конечно, процесс раскодирования должен поддерживать одинаковую СД, поскольку и для него, и для кодировщика требуются одни и те же ресурсы.

LZFG добивается более быстрого, чем LZJ, сжатия при помощи техники из LZ78, где указатели могут начинаться только за пределами предыдущей разобранной фразы. Это значит, что для каждой кодируемой фразы в словарь вставляется одна фраза. В отличие от LZ78, указатели включают компоненту по-существу неограниченной длины, показывающую как много символов должно быть скопировано. Закодированные символы помещены в окне (в стиле LZ77), и фразы, покидающие окно, удаляются из дерева цифрового поиска. Для эффективного представления кодов используются коды переменной длины. Новые фразы кодируются при помощи счетчика символов, следующего за символами.

3.4.13 Структуры данных для метода Зива-Лемпела

Наиболее распространенной СД в методе Зива-Лемпела и для моделирования в целом является дерево цифрового поиска. Такая СД и ее вариации обсуждаются в [51]. Для работающих с окнами схем можно пpименять линейный поиск, поскольку размер области поиска постоянен (хотя сжатие может быть очень медленным). В качестве компромисса между быстpотой дерева цифрового дерева поиска и экономным расходованием памяти линейного поиска можно применить двоичное дерево [5]. Для этой цели также можно использовать хеширование [12]. Подобное применение хеширования можно обнаружить в [110]. Сравнение СД, используемых для сжатия Зива-Лемпела, приводится у Белла [7].

Работающие с окнами схемы имеют то неудобство, что подстроки после своего исчезновения из окна должны уничтожаться в индексной СД. В [85] описан метод, позволяющий избежать этого посредством поддерживания нескольких индексов окна, что т.о. позволяет осуществлять поиск в СД, где уничтожение затруднительно. Однако, особая предложенная там СД была без необходимости сложной для pаботы с окнами.

Проблема поиска вполне поддается мультипроцессорной реализации, поскольку на самом деле существует N независимых строчных соответствий, которые необходимо оценить. В [34] описана параллельная реализация сжатия Зива-Лемпела.

4. ВОПРОСЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ

4.1 Ограничения по памяти

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

Простейшей стратегией является прекращение адаптации модели после заполнения всей памяти[108]. Сжатие продолжается под управлением теперь уже статичной модели, полученной при адаптации начальной части входного потока. Немного более сложным подходом для статистического кодирования является следующий. Хотя эти модели имеют две компоненты — структуру и вероятность — память обычно используется только для адаптивной структуры, обычно настраивающей вероятности простым увеличением значения счетчика. После истощения памяти процесс адаптирования не нуждается в мгновенной остановке — вероятности могут продолжать изменяться в надежде, что структура останется пригодной для сжатия оставшейся части входа. Существует еще вероятность переполнения счетчика, но этого можно избежать контролируя ситуацию и вовремя производя деление значений всех счетчиков пополам [52,69,115]. Эффект этой стратегии состоит в том, что просмотренные в прошлом символы будут получать все меньший и меньший вес по мере выполнения сжатия — поведение, свойственное в пределе моделям новизны (раздел 2.3).

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

Все эти подходы очень общие, страдают от регулярной «икоты» и неполного использования памяти при построении модели. Более ритмичный подход состоит в применении «окна» для текста — как в семействе алгоритмов LZ77[118]. Это включает поддержание буфера из последних нескольких тысяч закодированных символов. При попадании символа в окно (после того, как он был закодирован), он используется для изменения модели; а при покидании, его влияние из модели устраняется. Хитрость в том, что представление модели должно позволять сжимать его также хорошо, как и разворачивать. Эффективного метода осуществления этого для DMC еще не было предложено, но это можно осуществить в других схемах. Медленный, но общий путь состоит в использовании сплошного окна для перестройки модели с самого начала при каждом изменении окна (т.е. при кодировании очеpедного символа). Ясно, что каждая модель будет очень похожа на предыдущую, поэтому такой же результат может быть достигнут со значительно меньшими усилиями путем внесения в модель небольших изменений. Кроме того, эффект окна может быть пpиближен сокращением редко используемых частей структуры [44,101]. Кнут [52] в своем адаптивном кодировании Хаффмана использовал окно.

4.2 Подсчет

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

Если n есть максимальное количество наблюдений, то счетчикам требуется log n битов памяти. Однако, можно применять меньшие регистры, если при угрозе переполнения делить значения счетчиков пополам. Понижение точности частот наносит небольшой ущерб, поскольку возникновение небольших ошибок в их предсказании почти не оказывает влияния на среднюю длину кода. На самом деле, масштабирование счетчиков часто улучшает сжатие, поскольку дает более старым счетчикам меньший вес, чем текущим, а последние статистики часто являются лучшей основой для предсказания следующего символа, чем более ранние. Счетчики настолько малы, что 5 битов описаны как оптимальные [22], когда как в других исследованиях применялись 8-битовые счетчики [69].

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

Моррис в [70] предложил технику, при которой счетчики, достигшие значения n, помещаются в log(log(n)) битовый регистр. Принцип состоит в хранении логарифма счетчика и увеличении счетчика с вероятностью 2^-c, где c есть текущее значение регистра. Этот вероятностный подход гарантирует увеличение значения счетчика так часто, как следует, т.е. в среднем. Для анализа этой техники смотри Флажолета [29].

5. СРАВHЕHИЕ

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

5.1 Хаpактеpистики сжатия

Таблица 3 представляет сравниваемые методы сжатия. DIGM — простое кодирование с применением диад, основанное на работе Шнайдермана и Ханта[94] и интересное главным образом своей скоростью. LZB в среднем дает лучшее сжатие среди семейства алгоритмов LZ77, а LZFG — среди LZ78. HUFF — это адаптированный кодировщик Хаффмана применяющий модель 0-го порядка. Остальные методы адаптивно создают вероятностные модели, применяемые в сочетании с арифметическим кодиpованием. DAFC применяет модель, переключаемую между 0-м и 1-м порядками. ADSM использует контекст 1-го порядка с рядом кодируемых символов. PPMC [69] основан на методе, предложенном Клири и Уиттеном [16], применяющим более длинные контексты, и является одним из лучших контекстно-ограниченных методов моделирования. WORD — это контекстно-ограниченная модель, в которой вместо символов используются слова. DMC строит модели с ограниченным числом состояний [19], а MTF есть метод новизны, применяющий стратегию move-to-front [67], котоpый является усовершенствованием метода, предложенного Бентли и другими [10]. Почти все методы имеют параметры, обычно воздействующие на скорость работы и требуемые объемы памяти. Мы выбрали значения, которые дают хорошее сжатие без необязательно больших запросах ресурсов ЭВМ.

Таблица 3. Экспериментельно оцениваемые схемы сжатия.

Схема Авторы Заданные параметры
DIGM Snyderman and Hunt [1970] — Без параметров.
LZB Bell [1987] N = 8192 Количество символов в окне.
p = 4 Минимальная длина соответствия.
LZFG Fiala and Greene [1989] M = 4096 Максимальное число фраз в словаре.
HUFF Gallager [1978] — Без параметров.
DAFC Langdon and Rissanen [1987] Contexts = 32 Количество контекстов в модели 1-го порядка.
Threshold =50 Количество появлений символа, прежде, чем он станет контекстом.
ADSM Abramson [1989] — Без параметров.
PPMC Moffat [1988b] m = 3 Максимальный размер контекста. Неограниченная память.
WORD Moffat [1987] — Без параметров.
DMC Cormack and Horspool [1987] t = 1 Предпосылка изменений на текущем пути для клонирования.
T = 8 Предпосылка изменений на остальных путях для клонирования.
MTF Moffat [1987] size = 2500 Количество слов в списке.

Рисунок 7 характеризует образцы текстов, которые обрабатывались вышеуказанными методами. Они включают книги, статьи, черно-белые изобpажения и прочие виды файлов, распространенные в системах ЭВМ. Таблица 4 содержит полученные результаты, выраженные в битах на символ. Лучшее для каждого файла сжатие от- мечено звездочкой.

Text Type Format Content Size Sample
bib bibliography UNIX «refer» format, ASCII 725 references for books and papers on Computer Science 111.261 characters %A Witten, I.H.; %D 1985; %T Elements of computer typography; %J IJMMS; %V 23
book1 fiction book Unformatted ASCII Thomas Hardy: «Far from the Madding Crowd» 768.771 characters a caged canary — all probably from the window of the house just vacated. There was also a cat in a willow basket, from the partly-opened lid of which she gazed with half-closed eyes, and affectionately-surveyed the small birds around.
book2 non-fiction book UNIX «troff» format, ASCII Witten: «Principles of computer speech» 610.856 characters Figure 1.1 shows a calculator that speaks. .FC «Figure 1.1» Whenever a key is pressed the device confirms the action by saing the key’s name. The result of any computation is also spoken aloud.
geo geophysical data 32 bit numbers Seismic data 102.400 characters d3c2 0034 12c3 00c1 3742 007c 1e43 00c3 2543 0071 1543 007f 12c2 0088 eec2 0038 e5c2 00f0 4442 00b8 1b43 00a2 2143 00a2 1143 0039 84c2 0018 12c3 00c1 3fc2 00fc 1143 000a 1843 0032 e142 0050 36c2 004c 10c3 00ed 15c3 0008 10c3 00bb 3941 0040 1143 0081 ad42 0060 e2c2 001c 1fc3 0097 17c3 00d0 2642 001c 1943 00b9 1f43 003a f042 0020 a3c2 00d0 12c3 00be 69c2 00b4 cf42 0058 1843 0020 f442 0080 98c2 0084
news electronic news USENET batch file A variety of topics 377.109 characters In article thon@uts.amdahl.com (Ronald S. Karr) writes:
>Some Introduction:
>However, we have conflicting ideas concerning what to do with sender
>addresses in headers.
We do, now, support the idea that a pure !-path >coming it can be left as a !-path, with the current hostname prepended
obj1 object code Executable file for VAX Compilation of «progp» 21.504 characters 0b3e 0000 efdd 2c2a 0000 8fdd 4353 0000 addd d0f0 518e a1d0 500c 50dd 03fb 51ef 0007 dd00 f0ad 8ed0 d051 0ca1 dd50 9850 7e0a bef4 0904 02fb c7ef 0014 1100 ba09 9003 b150 d604 04a1 efde 235a 0000 f0ad addd d0f0 518e a1d0 500c 50dd 01dd 0bdd 8fdd 4357 0000 04fb d5ef 000a 7000 c5ef 002b 7e00 8bdd 4363 0000 addd d0f0 518e a1d0 500c 50dd 04fb e7ef 0006 6e00 9def 002b 5000 5067 9def 002b 5200 5270 dd7e
obj2 object code Executable file for Apple Macintosh «Knowledge Support System» program 246.814 characters 0004 019c 0572 410a 7474 6972 7562 6574 0073 0000 0000 00aa 0046 00ba 8882 5706 6e69 6f64 0077 0000 0000 00aa 0091 00ba 06ff 4c03 676f 00c0 0000 0000 01aa 0004 01ba 06ef 0000 0000 0000 00c3 0050 00d3 0687 4e03 7765 00c0 0000 0000 00c3 0091 01d3 90e0 0000 0000 0015 0021 000a 01f0 00f6 0001 0000 0000 0000 0400 004f 0000 e800 0c00 0000 0000 0500 9f01 1900 e501 0204 4b4f 0000 0000 1e00 9f01 3200 e501
paper1 technical paper UNIX «troff» format, ASCII Witten,Neal and Cleary:»Arithmetic coding for data compression» 53.161 characters Such a \fIfixed\fR model is communicated in advance to both encoder and decoder, after which it is used for many messages.
.pp
Alternatively, the probabilities the model assigns may change as each symbol is transmitted, based on the symbol frequencies seen \fIso far\fR in this
paper2 technical paper UNIX «troff» format, ASCII Witten: «Computer (In)security» 82.199 characters Programs can be written which spread bugs like an epidemic. They hide in binary code, effectively undetectable (because nobody ever examins binaries). They can remain dormant for months or years, perhaps quietly and imperceptibly infiltrating their way into the very depths of a system, then suddenly pounce,
pic black and white facsimile picture 1728×2376 bit map 200 pixels per inch CCITT facsimile test, picture 5 (page of textbook) 513.216 characters
progc program Source code in «C», ASCII Unix utility «compress» version 4.0 39.611 characters
progl program Source code in LISP, ASCII System software 71.646 characters
progp program Source code in Pascal, ASCII Program to evaluate compression performance of PPM 49.379 characters
trans transcript of terminal session «EMACS» editor controlling terminal with ASCII code Mainly screen editing, browsing and using mail 93.695 characters

Рисунок 7. Описание образцов текстов, использованных в экспериментах

Таблица 4. Результаты опытов по сжатию ( биты на символ )

Текст Размер DIGM LZB LZFG HUFF DAFC ADSM PPMC WORD DMC MTF
bib 111261 6.42 3.17 2.90 5.24 3.84 3.87 *2.11 2.19 2.28 3.12
book1 768771 5.52 3.86 3.62 4.56 3.68 3.80 *2.48 2.70 2.51 2.97
book2 610856 5.61 3.28 3.05 4.83 3.92 3.95 2.26 2.51 *2.25 2.66
geo 102400 7.84 6.17 5.70 5.70 *4.64 5.47 4.78 5.06 4.77 5.80
news 377109 6.03 3.55 3.44 5.23 4.35 4.35 *2.65 3.08 2.89 3.29
obj1 21504 7.92 4.26 4.03 6.06 5.16 5.00 *3.76 4.50 4.56 5.30
obj2 246814 6.41 3.14 2.96 6.30 5.77 4.41 *2.69 4.34 3.06 4.40
paper1 53161 5.80 3.22 3.03 5.04 4.20 4.09 *2.48 2.58 2.90 3.12
paper2 82199 5.50 3.43 3.16 4.65 3.85 3.84 2.45 *2.39 2.68 2.86
pic 513216 8.00 1.01 *0.87 1.66 0.90 1.03 1.09 0.89 0.94 1.09
progc 39611 6.25 3.08 2.89 5.26 4.43 4.20 *2.49 2.71 2.98 3.17
progl 71646 6.30 2.11 1.97 4.81 3.61 3.67 *1.90 1.90 2.17 2.31
progp 49379 6.10 2.08 1.90 4.92 3.85 3.73 *1.84 1.92 2.22 2.34
trans 93695 6.78 2.12 *1.76 5.58 4.11 3.88 1.77 1.91 2.11 2.87
В среднем 224402 6.46 3.18 2.95 4.99 4.02 3.95 *2.48 2.76 2.74 3.24

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

5.2 Требования скорости и памяти

В общем случае лучшее сжатие достигается большим расходом ресурсов ЭВМ: времени и прежде всего памяти. Моффат [69] описывает реализацию одного из лучших архиваторов (PPMC), обрабатывающего около 2000 символов в секунду на машине MIP (OC VAX 11/780). DMC выполняется немного медленнее, так как работает с битами. Для сравнения, у LZFG на подобной машине зафиксирована скорость кодирования около 6000 симв/сек, а раскодирования — 11000 симв/сек [28]. LZB имеет особенно медленное кодирование (обычно 600 симв/сек), но очень быстрое раскодирование (1600 симв/сек), которое может достичь 40.000.000 симв/сек при использовании архитектуры RISC [43].

Большинство моделей пpи увеличении доступной памяти улучшают свое сжатие. Пpи использовании лучшей СД скоpость их pаботы повысится. Реализация PPMC, предложенная Моффатом, выполняется на ограниченной памяти в 500 Кб. На таком пространстве может работать и схема DMC, хотя полученные результаты ее работы достигнуты на неограниченной памяти, временами составляющей несколько Мб. LZFG использует несколько сотен Кб, LZB для кодирования применяет сравнимое ее количество, когда как раскодирование обычно требует всего 8 Мб.

Илон Маск рекомендует:  Функции dos int 20h завершить программу

DIGM и HUFF по сравнению с остальными методами требуют очень немного памяти и быстpо выполняются.

6. ДАЛЬHЕЙШИЕ ИССЛЕДОВАHИЯ

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

Сейчас лучшие схемы достигают сжатия в 2.3 — 2.5 битов/символ для английского текста. Показатель иногда может быть немного улучшен за счет использования больших объемов памяти, но сообщений о преодолении рубежа в 2 бита/символ еще не было. Обычные люди достигали результата в 1.3 бита/символ при предсказании символов в английском тексте [21]. Хотя обычно это принимается за нижнюю границу, но теоретических причин верить, что хорошо тренированные люди или системы ЭВМ не достигнут большего, не существует. В любом случае, несомненно, существует много возможностей для улучшения алгоритмов сжатия.

Одним направлением для исследований является подгонка схем сжатия к отечественным языкам. Сегодняшние системы работают полностью на лексическом уровне. Использование больших словарей с синтаксической и семантической информацией может позволить машинам получить преимущество от имеющейся в тексте высокоуpовневой связности. Однако, необходимо иметь в виду, что очень большое количество слов обычного английского текста в обычном английском словаpе может быть не найдено. Например, Уолкер и Эмслер[107] проверили 8 миллионов слов из New York Times News Service для Webster’s Seventh New Collegiate Dictionary[65] и обнаружили, что в словаpе отсутствовало почти 2/3 (64%) слов (они подсчитали, что около 1/4 из них — грамматические формы слов, еще 1/4 — собственные существительные, 1/6 — слова, написанные через дефис, 1/12 — напечатаны с орфографическими ошибками, а оставшуюся четверть составляют возникшие уже после выпуска словаря неологизмы). Большинство словарей не содеpжат имен людей, названий мест, институтов, торговых марок и т.д., хотя они составляют основную часть почти всех документов. Поэтому, специальные алгоритмы сжатия, взятые в рассчете на лингвистическую информацию более высокого уровня, будут несомненно зависеть от системной сферы. Вероятно, что поиски методов улучшения характеристик сжатия в данном направлении будут объединяться с исследованиями в области контекстуального анализа по таким проблемам как извлечение ключевых слов и автоматическое абстрагирование.

Второй подход диаметрально противоположен описанному выше наукоемкому направлению, и состоит в поддержании полной адаптивности системы и поиске улучшений в имеющихся алгоритмах. Необходимы лучшие пути организации контекстов и словарей. Например, еще не обнаружен пригодный метод постстроения моделей состояний; показанный метод DMC — лишь форма контекстно-ограниченной модели[8]. Тонкости роста этих СД вероятно значительно влияют на сжатие, но, несмотря на статью Уильямса [110], этот вопрос еще не был исследован систематично. Дpугой стоящей темой для исследований являются методы выделения кодов уходов в частично соответствующих контекстуальных моделях. В итоге, пpеобpазование систем, определяемых состояниями, таких как скрытые модели Маркова[77], может вдохнуть новую жизнь в модели состояний сжатия текстов. Например, алгоритм Баума-Уэлча определения скрытых моделей Маркова [4] в последнее время был вновь открыт в области распознавания речи [60]. Он может быть успешно применен для сжатия текстов, равно как и для техники глобальной оптимизации, такой как моделирование обжига[25]. Недостаток этих методов состоит в их значительных временных затратах, что позволяет сейчас эксплуатировать довольно небольшие модели с десятками и сотнями, а не тысячами и более состояний.

Поиски более быстрых алгоритмов, сильно влияющих на развитие методов сжатия текстов, будут несомненно продолжены в будущем. Постоянный компромисс между стоимостями памяти и вычислений будет стимулировать дальнейшую работу над более сложными СД, требующими больших объемов памяти, но ускоряющих доступ к хранимой информации. Применение архитектуры RISC, например в [43], разными путями воздействует на баланс между хранением и выполнением. Будет развиваться аппаратура, например, исследователи экспериментируют с арифметическим кодированием на микросхеме, когда как Гонзалес-Смит и Сторер [34] разработали для сжатия Зива-Лемпела параллельные алгоритмы поиска. В общем, увеличение вариантов аппаратных реализаций будет стимулировать и разнообразить исследования по улучшению использующих их алгоритмов.

Последняя область на будущее — это разработка и реализация новых систем, включающих сжатие текстов. Существует идея объединения в единую систему ряда распространенных пpогpамм pазных областей применения, включая текст-процессор MaxWrite(7)[117], цифровой факсимильный аппаpат [42], сетевую почту и новости (например, UNIX «net-news») и архивацию файлов (например, программы ARC и PKARC для IBM PC(8), которые часто применяются для pаспpеделяемого ПО из электронных бюллютеней). Для увеличения скорости и сокращения стоимости большинство этих систем используют удивительно простые методы сжатия. Все они представляют собой потенциальные сферы применения для более сложных методов моделирования.

Люди часто размышляют над объединением адаптированного сжатия с дисковым контроллером для сокращения использования диска. Это поднимает интересные системные проблемы, частично в сглаживании взрывного характера вывода большинства алгоритмов сжатия, но в основном в согласовывании случайного характера доступа к дисковым блокам с требованиями адаптации к разным стилям данных. Сжатие имеет значительные преимущества для конечного движения — некоторые высокоскоростные модемы (например, Racal-Vadic’s Scotsman) и конечные эмуляторы (например, [3]) уже имеют адаптивные алгоритмы. В будущем полностью цифровые телефонные сети радикально изменят характер конечного движения и, вообще, сферу локальных сетей. Эффективность сжатия трудно оценить, но эти усовершенствования определенно будут давать преимущество в скорости реализации.

Еще одной сферой применения является шифрование и защита данных [113]. Сжатие придает хранимым и передаваемым сообщениям некоторую степень секретности. Во-первых, оно защищает их от случайного наблюдателя. Во-вторых, посредством удаления избыточности оно не дает возможности криптоаналитику установить присущий естественному языку статистичекий порядок. В-третьих, что самое важное, модель действует как очень большой ключ, без которого расшифровка невозможна. Применение адаптивной модели означает, что ключ зависит от всего текста, переданного системе кодирования/раскодирования во время ее инициализации. Также в качестве ключа может быть использован некоторый префикс сжатых данных, опpеделяющий модель для дальнейшего pаскодиpования[47].

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

Авторские примечания

(1) — Везде в этой статье основание логарифма есть 2, а единица информации — бит.
(2) — Вероятность может быть менее 100% в случае иностранных слов, таких как «Coq au vin» или «Iraq.».
(3) — Понятие введено Моффатом в [69] для техники, использованной в [16].
(4) — Эта перемена инициалов в аббревиатуре является увековеченной нами исторической ошибкой.
(5) — UNIX — торговая марка AT&T Bell Laboratories.
(6) — На самом деле это дерево Patricia [51,71].
(7) — MacWrite — зарегестрированная торговая марка Apple Computer,Inc.
(8) — IBM — зарегестрированная торговая марка International Business Machines.

Словарь к переводу

ADSM = adaptive dependency source model.
Arithmetic coding — арифметическое кодирование.
Bits per character (bit/char) — биты на символ — единица измерения степени сжатия.
Blending strategy — смешанная стратегия.
Code space — кодовое пространство.
Compression ratio — характеристика степени сжатия.
Conditioning classes — классы условий.
Cross-product — перекрестное умножение 4 .
Cumulative probability — накапливаемая вероятность.
DAFC = A doubly-adaptive file compression algorithm.
Dictionary coding — словарное кодирование.
Digram coding — кодирование диадами.
Entropy — энтропия.
Escape probability — вероятность ухода.
File — файл, обозначение сжимаемых данных.
Finite-context modeling — контекстно-ограниченное моделирование.
Finite-context probabilistic model — вероятностные модели с конечным числом состояний.
FSM = finite-state machine — конечный автомат.
Greedy parsing — тщательный разбор 3 .
Hyphenated words — слова, разделенные дефисом.
Input — ввод, обозначение сжимаемых данных.
Lazy exclusion — ленивое исключение.
Lookahead buffer — упpеждающий (пpосмотpенный) впеpед буфер.
LFF = Longest Fragment First — метод помещения в начало самого длинного фрагмента.
Noiseless compression — сжатие без помех (обpатимое).
Order-o fixed-context model — контекстно-зависимая модель степени o.
Parsing — разбор текста на фразы.
PPMA = prediction by partial match, method A 5 .
Proper nouns — имена собственные.
Recency models — модели новизны.
Run-length coding — кодиpование длин тиpажей 6 .
Skew count — ассиметричный счет.
Source — источник, производящий (содержащий) данные для сжатия.
Source coding — синоним процесса сжатия.
Statistical coding — статистическое кодирование.
String — строка, обозначение сжимаемых данных.
Text — текст, обозначение сжимаемых данных.
Trie = digital search tree — дерево цифрового поиска.
Update exclusion — обновляемое исключение.
Vowel-consonant pairs — пары «гласная-согласная».
Zero frequency problem — проблема нулевой частоты.
Ziv-Lempel compression — сжатие Зива-Лемпела.

Литература

  1. Abramson D.M. 1989. An adaptive dependency source model for data compression. Commun.ACM 32,1(Jan.),77-83.
  2. Angluin D.,and Smith C.H. 1983. Inductive inference:Theory and methods. Comput.Surv. 15, 3(Sept.),237-269.
  3. Auslander M., Harrison W., Miller V., and Wegman M. 1985. PCTERM: A terminal emulator using compression. In Proceedings of the IEEE Globecom’85. IEEE Press, pp.860-862.
  4. Baum L.E., Petrie T.,Soules G. and Weiss N. 1970. A maximization technique occuring in the statistical analysis of probabilistic functions of Markov chains. Ann. Math. Stat.41, 164-171.
  5. Bell T.C. 1986. Better OPM/L test compression. IEEE Trans. Commun. COM-34. 12(Dec.),1176-1182.
  6. Bell T.C. 1987. A unifying theory and improvements for existing approaches to text compression. Ph.D. dissertation, Dept. of Computer Science, Univ. of Canterbury, New Zealand.
  7. Bell T.C. 1989. Longest match string searching for Ziv-Lempel compression. Res. Rept.6/89, Dept. of Computer Science, Univ. of Canterbury, New Zealand.
  8. Bell T.C. and Moffat A.M. 1989. A note on the DMC data compression scheme. Computer J. 32,1(Feb.), 16-20.
  9. Bell T.C. and Witten I.H. 1987. Greedy macro text compression. Res. Rept.87/285/33. Department of Computers Science, University of Calgary.
  10. Bentley J.L.,Sleator D.D., Tarjan R.E. and Wei V.K. 1986. A locally adaptive data compression scheme. Commun. 29, 4(Apr.), 320-330. Shows how recency effectscan be incorporated explicitly into a text compression system.
  11. Bookstein A. and Fouty G. 1976. A mathematical model for estimating the effectivness of bigram coding. Inf. Process. Manage.12.
  12. Brent R.P. 1987. A linear algorithm for data compression. Aust. Comput. J. 19,2,64-68.
  13. Cameron R.D. 1986. Source encoding using syntactic information source model. LCCR Tech. Rept. 86-7, Simon Fraser University.
  14. Cleary J.G. 1980. An associative and impressible computer. Ph.D. dissertation. Univ. of Canterbury, Christchurch, New Zealand.
  15. Cleary J.G. and Witten I.H. 1984a. A comparison of enumerative and adaptive codes. IEEE Trans. Inf. Theory, IT-30, 2(Mar.),306-315. Demonstrates under quite general conditions that adaptive coding outperforms the method of calculating and transmitting an exact model of the message first.
  16. Cleary J.G. and Witten I.H. 1984b. Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. COM-32, 4(Apr.),396-402. Presents an adaptive modeling method that reduces a large sample of mixed-case English text to around 2.2 bits/character when arithmetically coded.
  17. Cooper D. and Lynch M.F. 1982. Text compression using variable-to-fixed-length encoding. J. Am. Soc. Inf. Sci. (Jan.), 18-31.
  18. Cormack G.V. and Horspool R.N. 1984. Algorithms for adaptive Huffman codes. Inf.Process.Lett. 18,3(Mar.), 159-166. Describes how adaptive Huffman coding can be implemented efficiently.
  19. Cormack G.V. and Horspool R.N. 1987. Data compression using dynamic Markov modelling. Comput. J. 30,6(Dec.), 541-550. Presents an adaptive state-modelling technique that, in conjunction with arithmetic coding, produces results competitive with those of[18].
  20. Cortesi D. 1982. An effective text-compression algorithm. Byte 7,1(Jan.),397-403.
  21. Cover T.M. and King R.C. 1978. A convergent dambling estimate of the entropy of English. IEEE Trans. Inf. Theory IT-24, 4(Jul.),413-421.
  22. Darragh J.J., Witten I.H. and Cleary J.G. 1983. Adaptive text compression to enhance a modem. Res.Rept.83/132/21.Computer Science Dept.,Univ.of Calgary.
  23. Elias P. 1975. Universal codeword sets and representations of the integers. IEEE Trans.Inf.Theory IT-21,2(Mar.),194-203.
  24. Elias P. 1987. Interval and recency rank source coding: Two on-line adaptive variable-length schemes. IEEE Trans.Inf.Theory IT-33, 1(Jan.),3-10.

  25. El Gamal A.A., Hemachandra L.A., Shperling I. and Wei V.K. 1987. Using simulated annealing to design good codes. IEEE Trans.Inf.Theory,IT-33,1,116-123.
  26. Evans T.G. 1971. Grammatical inference techniques in pattern analysis. In Software Engineering, J. Tou. Ed.Academic Press, New York, pp.183-202.
  27. Faller N. 1973. An adaptive system for data compression. Record of the 7th Asilomar Conference on Circuits, Systems and Computers. Naval Postgraduate School, Monterey, CA, pp.593-597.
  28. Fiala E.R. and Greene D.H. 1989. Data compression with finite windows. Commun.ACM 32,4(Apr.),490-505.
  29. Flajolet P. 1985. Approximate counting: A detailed analysis. Bit 25,113-134.
  30. Gaines B.R. 1976. Behavior/structure transformations under uncertainty. Int.J.Man-Mach.Stud. 8, 337-365.
  31. Gaines B.R. 1977. System >

Об авторах, выходные данные

Tim Bell reseived a B.Sc. (First >Ian H. Witten is Professor of Computer Science at the University of Calgary, Canada. In the past he has worked on numerous aspects of man-machine systems, particularly speech synthesis and documentation graphics. His current research interests include prediction and modeling, machine learning, and office information systems. He has published around 80 papers and three books: Communication with Microcomputers (Academic Press,1980), Principles of Computer Speech (Academic Press,1982), and Talking with Computer (Prentice Hall,1986).

John G.Cleary is Associate Professor of Computer Science at the University of Calgary, Canada. He received his Ph.D. in electrical engineering from the University of Canterbury, New Zealand. Prior to moving to Canada in 1982 he spent six years working on commercial software systems. His current research include adaptive systems, parralel algorithms and hardware particularly for high quality graphics, logic programming and its application to distributed simulation using virtual time techniques. Drs. Bell, Cleary, and Witten have recently collaborated on a book entitled Text Compression (Prentice Hall, in press).

Сноски:
3 Очевидно, что такой разбор никакой не «тщательный», а именно «жадный» (greedy parsing).
4 “Cross-product” – это векторное произведение по-русски.
5 Интересно, что, похоже, сами авторы PPM не могут разобраться, как же расшифровывается эта аббревиатура. В статьях с их участием встречается как “prediction by partial matching”, так и “prediction by partial match”. В первой статье 1984 года используется именно “. matching”.
6 «Тираж» – это уж совсем жестоко. Часто говорят «кодирование длин серий».
наверх

Сайт подключен к Orphus. Если вы заметили опечатку, выделите слово и нажмите Ctrl+Enter. Спасибо!

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

«Текстовая задача — описание некоторой ситуации на естественном языке, с требованием дать количественную характеристику какого-либо компонента этой ситуации, установить наличие или отсутствие некоторого отношения между её компонентами и определить вид этого отношения» — по утверждению Л.П. Стойловой [13, с.147].

Автор дает характеристику задаче так: «Любая текстовая задача состоит из двух частей — условия и требования (вопроса). В условии соблюдаются сведения об объектах и некоторые числовые данные объекта, об известных и неизвестных значениях между ними. Требования задачи — это указание того, что нужно найти. Оно выражено предложением в повелительной или вопросительной форме [13, с.158].

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

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

Н.Б.Истомина, разрабатывая методику обучения младших школьников решению задач, указывает: «Работа по формированию умения решать текстовые задачи начинается с первых дней обучения в школе. Первые шаги при решении простых задач не вызывают у учащихся затруднений. Но самостоятельное решение составных задач оказывается не по силам многим, и от класса к классу эти учащиеся испытывают всё большие трудности. Причина возникающих затруднений состоит в том, что у учащихся не сформировано в значительной степени умение анализировать текст задачи, правильно выделять известное и неизвестное, устанавливать взаимосвязь между ними, которая является основой выбора действия для решения текстовой задачи» [6, с.103].

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

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

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

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

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

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

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

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

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

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

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

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

  • 1) все математические понятия, используемые при решении задач, должны изучаться с помощью моделей;
  • 2) должна вестись работа по усвоению знаково-символического языка, на котором строится модель (при этом ученик должен осознавать значение каждого элемента модели, осуществляя переход от реальности (от предметной модели к графической модели, и наоборот) [14, с.15].

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

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

Математическая модель — это описание какого-либо реального процесса на математическом языке [4, с.118].

В процессе решения задачи чётко выделяются три этапа математического моделирования:

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

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

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

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

Рисунок начинают применять уже в 1 классе. Во-первых, рисование — любимый вид деятельности малышей, во-вторых, приём хорош для развития моторики рук, в-третьих, рисование является развивающим упражнением [16, с. 79].

С краткой записью начинают работать в конце 1-го класса, т.к. ученики уже способны записать текст. Удачным может быть введение краткой записи параллельно с рисунком.

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

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

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

Рассмотрим методику работы с некоторыми моделями с помощью метода беседы.

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

Например: Когда с полки сняли 2 книги, там осталось 4. Сколько книг лежало на полке сначала?

Учитель: Сколько книг осталось на полке?

Учитель: Изобразим это с помощью прямоугольников.

Учитель: Раньше книг было больше или меньше? Почему?

Ученики: Больше. Здесь нет книг, которые сняли с полки.

Учитель: Знаем ли мы, сколько книг было сначала? Нет. Покажем это скобкой или дугой и вопросительным знаком.

Учитель: Почему книг стало меньше?

Ученики: С полки сняли две книги.

Учитель: Изобразим две книги внизу, под скобкой.

Учитель: Как узнать, сколько всего книг было на полке?

Ученики: Нужно сложить книги, которые остались на полке, и те, которые сняли.

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

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

Наиболее удачно можно применять таблицы при решении задач на тройку пропорциональных величин: цена — количество — стоимость; расход на 1 шт.- количество штук — общий расход; масса — количество — общая масса; скорость — время — расстояние; и т.д.

Например: Из двух городов, расстояние между которыми равно 1200 км, одновременно вышли навстречу друг другу два поезда. Один из них проходит это расстояние за 20 часов, а другой — за 30 часов. Через сколько часов поезда встретятся?»

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

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

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

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

  • 1)60 + 40 = 100 (км/ч)
  • 2) 1200: 100 = 12 (ч)

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

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

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

Схема — это чертёж, на котором все взаимосвязи и взаимоотношения величин передаются приблизительно, без соблюдения масштаба,

Например: Из двух кусков ткани сшили 18 одинаковых занавесок. В первом куске было 30 метров, во втором — 24 метра. Сколько занавесок сшили из каждого куска?

Обычно условие записывают в таблицу:

Расход на одно платье

Однако по этой модели рассуждение у детей вызывает затруднение. Детям трудно увидеть, что нужно знать для определения расхода ткани на одну занавеску. Учитель … рекомендует использовать такую схему [, с.].

Понимание процесса, рассматриваемого в задаче, облегчается тем, что на схеме один и тот же отрезок изображает и сумму длин двух кусков ткани — (30 + 24) в метрах, и 18 занавесок, которые из нее сшили.

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

Например: Когда шланг длинной 5 метров удлинили на несколько метров, то получился шланг длиной 8 метров. На сколько метров удлинили шланг?

Рассмотрим поэтапную работу в беседе с учащимися.

Учитель: Какой длины был сначала шланг?

Ученики: 5 метров.

Учитель: Какой длины вычерчиваем первый отрезок?

Учитель: Что произошло со шлангом?

Ученики: Увеличился на несколько метров.

Учитель: Как изменится отрезок?

Ученики: Увеличится на несколько сантиметров.

Учитель: Какой длины стал шланг?

Ученики: 8 метров.

Учитель: Какой длины станет наш отрезок?

Ученики: 8 сантиметров.

Учитель: Отметим на чертеже, на сколько увеличился наш отрезок.

Учитель: Что нужно узнать в задаче? Как на нашей модели отмечено искомое?

Далее выбирается арифметическое действие.

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

Например: У Васи 2 машинки, а у Коли в 3 раза больше, чем у Васи. Сколько машинок у Коли?

Чертёж имеет такой вид:

Затем выбирается арифметическое действие для решения: 2 Ч 3 = 6 (м.).

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

Выводы по 1 главе

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

  • 1. Можно смело утверждать, что задачи, решаемые школьниками в младших классах, занимают одно из важнейших мест в их обучении.
  • 2. Текстовая задача — это математическая задача, которая по своей структуре имеет условие и вопрос. Она представляет собой словесную модель ситуации, явления, события, процесса и т. п. Как в любой модели, в текстовой задаче описывается не все событие или явление, а лишь его количественные и функциональные характеристики.
  • 3. Учитель начальных классов должен сформировать навык у учащихся решения задач. Этого требует программа. А для качественного решения этой проблемы необходимо применять наиболее эффективную методику работы — методы и приемы организации учебной деятельности.
  • 4. Моделирование можно рассматривать как особую деятельность по построению (выбору или конструированию) моделей для определенных целей.
  • 5. Математическая модель — это описание какого-либо реального процесса на математическом языке.
  • 6. Для учебных моделей характерны следующие особенности, которые проявляются, в том числе в моделях графических:
    • — наглядность данных моделей;
    • — возможность сохранять информацию для дальнейшего изучения преобразования;
    • — организация внутренней психической деятельности учеников;
    • — указание способов организации действий учащихся;
    • — открытие нового знания, скрытого при поверхностном анализе объекта исследования.
  • 7. Существуют различные виды моделей: словесные — высказывательная форма (утверждения, требования),
  • — вспомогательные — схематизированные (вещественные, графические), знаковые,
  • — математические (арифметический метод, алгебраический метод).

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

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

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

Секция: Педагогика

XII Студенческая международная научно-практическая конференция «Гуманитарные науки. Студенческий научный форум»

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

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

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

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

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

Основными этапами моделирования являются [1]: 1. Постановка задачи. На данном этапе определяется цель моделирования, а также проводится анализ исследуемого объекта. 2. Построение модели и ее апробация. 3. Анализ адекватности модели (проверка соответствия полученных результатов поставленным целям).

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

Задача. У Маши в вазе стоит 7 тюльпанов, а у ее подруги Юли на 2 тюльпана меньше. Сколько всего тюльпанов у девочек?

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

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

  • Объекты: тюльпаны.
  • Утверждения: 1) У Маши 7 тюльпанов. 2) У ее подруги Юли на 2 тюльпана меньше.
  • Требования: 1) Сколько тюльпанов у Юли? 2) Сколько всего тюльпанов у девочек?

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

К графическим моделям относятся:

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

Рисунок 1. Графическая модель: рисунок

— условный рисунок. На условном рисунке школьники изображают объекты, о которых идет речь в задаче, с помощью обозначений, символов, знаков, например: квадратов, треугольников, кружочков и др. (рис. 2);

Рисунок 2. Графическая модель: условный рисунок

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

Рисунок 3. Графическая модель: чертеж

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

Рисунок 4. Графическая модель: схема

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

Рисунок 5. Краткая запись задачи

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

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

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

7 + (7 – 2) = 12 (т.) – всего тюльпанов у девочек;

или запись по действиям:

1) 7 — 2 = 5 (т.) — тюльпанов у Юли;

2) 7 + 5 = 12 (т.) — всего тюльпанов у девочек.

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

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

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

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

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

Соглашение об использовании материалов сайта

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

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

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

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

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

курсовая работа [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

Реферат: Методы и алгоритмы построения элементов систем статистического моделирования

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

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

2. Моделирование случайных величин и процессов

3. Основные понятия марковских процессов

4. Математический аппарат дискретных марковских цепей

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

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

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

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

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

Различают две области применения метода статистического моделирования:

— для изучения стохастических систем;

— для решения детерминированных задач.

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

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

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

Понятие “статистическое моделирование” тесно связано с по­нятием “метод Монте-Карло” и почти ему тождественно.

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

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

· генерирование N реализации случайной величины с требуемой функцией распределения;

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

· статистическая обработка реализации.

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

Конструктивно задаются случайная величина, равномерно распределенная в интервале (0,1), (0,l), далее производится ото­бражение и получается новая случайная величина с распределением, определяемым решаемой задачей, в общем случае может быть довольно сложным.

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

В результате можно выделить следующие этапы (рис. 4.1):

— подготовка исходных данных (блок 1),

— генерирование равномерно распределенных случайных чисел (блок 2),

— преобразования для получения заданного закона распределения (блок 3);

— выполнение дополнительных преобразований в соответствии с проблем ной областью (блок 4);

— статистическая обработка (блок 5).

Рис. 4.1. Технологический процесс в Монте-Карло системах

— ПИД — подготовка исходных данных,

— ГРРСЧ — генерирование равномерно распределенных случайных чисел;

— ГПЗ — генерирование произвольного (заданного) закона распре­деления;

— ДПр — дополнительные преобразования;

— СО — статистическая обработка.

Имитационные системы имеют следующие функциональные блоки:

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

— имитации правил переработки входной информации исследуемой системы;

— накопления информации в результате моделирования;

— анализа накопленной информации;

— управления имитирующей системы.

Традиционный подход использует все классы задач, что и в методе Монте-Карло. Рассмотрим подробнее аналитический подход задания экзогенных переменных (первый случай). Они являются вы­ходными другой подсистемы макросистемы и сами представляют собой макромодель. В рассматриваемом случае характеристики за­даны аналитически.

Информационно технологическая блок-схема представлена на рис. 4.2.

Рис. 4.2. Технологический процесс имитационной системы

ГСП — генерирование случайных (входных) процессов;

ИС — имитационная система.

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

Во втором и третьем блоках производится генерирование слу­чайных чисел с равномерным распределением x, и экзогенных слу­чайных процессов z.

Блок 4 имитирует работу исследуемой системы, результаты его работы накапливаются для последующей статистической обра­ботки. В последнем, пятом, блоке осуществляется статистическая обработка.

При моделировании систем на ЭВМ программная имитация случайных воздействий любой сложности сводится к генерированию некоторых стандартных (базовых) процессов и к их последующему функциональному преобразованию. В качестве базового может быть принят любой удобный в случае моделирования конкретной системы S процесс (например, пуассоновский поток при моделировании Q-схемы). Однако при дискретном моделировании базовым процессом является последовательность чисел , представляю­щих собой реализации независимых, равномерно распределенных на интервале (0,1) случайных величин или – в статистических терминах- повторную выборку из равномерно распределен­ной на (0,1) генеральной совокупности значений величины x.

Непрерывная случайная величина x имеет равномерное распределение в интервале (а,b), если ее функция плотности (рис. 4.3,а) и распределение (рис. 4.3,6) соответственно примут вид:

Название: Методы и алгоритмы построения элементов систем статистического моделирования
Раздел: Рефераты по математике
Тип: реферат Добавлен 03:56:06 23 марта 2008 Похожие работы
Просмотров: 2212 Комментариев: 15 Оценило: 4 человек Средний балл: 4.8 Оценка: неизвестно Скачать

Рис. 4.3. Равномерное распределение случайной величины

2. Моделирование случайных величин и процессов

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

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

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

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

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

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

Моделирование случайных процессов строится на основе базовых распределений случайных величин.

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

3. Основные понятия марковских процессов

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

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

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

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

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

Такими примерами СФ являются: колебания напряжения в электрической цепи, скорость движения автомобиля на участке дороги с ограничением скорости, шероховатость поверхности детали на определенном участке и т.д.

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

Нетрудно заметить, что если обозначить состояние и изобразить зависимость , то такая зависимость и будет случайной функцией.

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

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

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

Рис. 1. Схема процесса без последействия

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

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

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

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

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

Марковский СП называется однородным, если переходные вероятности остаются постоянными в ходе процесса.

Цепь Маркова считается заданной, если заданы два условия.

1. Имеется совокупность переходных вероятностей в виде матрицы:

2. Имеется вектор начальных вероятностей

описывающий начальное состояние системы.

Матрица (2) называется переходной матрицей (матрицей перехода). Элементами матрицы являются вероятности перехода из i-го в j-е состояние за один шаг процесса. Переходная матрица (2) обладает следующими свойствами:

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

Рис. 2. Ориентированный взвешенный граф

Вершины графа обозначают состояние , а дуги- переходные вероятности.

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

1. Невозвратное множество (рис. 3).

Рис. 3. Невозвратное множество


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

2. Возвратное множество (рис. 4).

Рис. 4. Возвратное множество

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

3. Эргодическое множество (рис. 5).

Рис. 5. Эргодическое множество

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

4. Поглощающее множество (рис. 6)

Рис. 6. Поглощающее множество

При попадании системы в это множество процесс заканчивается.

Кроме описанной выше классификации множеств различают состояния системы:

а) существенное состояние (рис.7): возможны переходы из в и обратно.

Рис. 7. Существенное состояние

б) несущественное состояние (рис. 8): возможен переход из в , но невозможен обратный.

Рис. 8. Несущественное состояние

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

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

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

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

Рис. 9. Классификация марковских процессов

4. Математический аппарат дискретных марковских цепей

В дальнейшем рассматриваются простые однородные марковские цепи с дискретным временем. Основным математическим соотношением для ДМЦ является уравнение, с помощью которого определяется состояние системы на любом ее k-м шаге. Это уравнение имеет вид:

и называется уравнением Колмогорова-Чепмена .

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

Дальнейшие математические соотношения зависят от конкретного вида марковской цепи.

4.1. Поглощающие марковские цепи

Как указывалось выше, у поглощающих ДМЦ имеется множество, состоящее из одного или нескольких поглощающих состояний.

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

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

Такая форма позволяет представить матрицу (6) в каноническом виде:

где — единичная матрица;

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

— матрица, описывающая внутренние переходы в системе в невозвратном множестве состояний.

На основании канонической формы (6а) получена матрица, называемая фундаментальной:

В матрице (7) символ (-1) означает операцию обращения, то есть

После соответствующих преобразований матрица (7) примет вид:

Каждый элемент матрицы (7а) соответствует среднему числу раз попадания системы в то или иное состояние до остановки процесса (поглощения).

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

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

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

В данном случае

Проделаем необходимые вычисления:

В данном случае компоненты вектора означают, что если процесс начинается с состояния , то общее среднее число шагов процесса до поглощения будет равно 3,34 и, соответственно, если процесс начинается с состояния , то — 2,26.

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

Так, если задать в нашем примере время пребывания в состоянии , а в состоянии — , то общее время до поглощения будет равно:

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

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

М — фундаментальная матрица с размерностью S;

R — блок фундаментальной матрицы с размерностью r.

Рассмотрим конкретный пример системы с четырьмя состояниями , два из которых- — поглощающие, а два — — невозвратные (рис.10):

Рис. 8.10. Система с четырьмя состояниями

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

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

Фундаментальная матрица после вычислений примет вид:

Тогда, согласно формуле (9), матрица вероятностей поглощения вычисляется так:

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

Таким образом, если процесс начался в , то вероятность попадания его в равна , а в — . Отметим одно интересное обстоятельство: несмотря на то, что, казалось бы, левое поглощающее состояние (“левая яма”) находится рядом с , но вероятность попадания в нее почти в два раза меньше, чем в “удаленную яму” — . Этот интересный факт подмечен в теории ДМЦ, и объясняется он тем, что , то есть процесс имеет как бы “правый уклон”. Рассмотренная выше модель называется в теории ДМЦ моделью случайного блуждания. Такими моделями часто объясняются многие физические и технические явления и даже поведение игроков во время различных игр.

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

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

— диагональная матрица, т.е. матрица, полученная из М путем оставления в ней лишь диагональных элементов и замены остальных элементов нулями. Например, приведенная выше матрица (7а) будет иметь вид:

В свою очередь, матрица М представляет собой матрицу, полученную из М путем возведения в квадрат каждого ее элемента, то есть для (7а) будем иметь:

Аналогичным образом определяема и дисперсия для общего количества раз пребывания в том или ином состоянии . Обозначим ее :

4.2. Эргодические цепи

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

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

1. Степени при стремятся к стохастической матрице .

2. Каждая строка матрицы представляет один и тот же вероятностный вектор

все компоненты которого положительны.

Вектор (12) в теории ДМЦ занимает особое место из-за наличия многих приложений и называется вектором предельных или финальных вероятностей (иногда — стационарным вектором). Финальные вероятности определяют с помощью векторно-матричного уравнения

которое в развернутом виде будет выглядеть так:

К уравнениям (8.13а) можно дополнительно добавить условие нормировки:

Тогда любое из уравнений в (8.14) можно исключить.

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

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

— фундаментальная матрица (15);

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

D — диагональная матрица с диагональными элементами, ;

Е — матрица, все элементы которой равны единице.

Матрица дисперсий времени первого достижения имеет несколько более сложный вид:

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

4.3. Управляемые марковские цепи

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

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

— конечное множество решений (альтернатив) , где — номер состояния системы;

— матрицы переходов соответствующие тому или иному принятому k-му решению;

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

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

Таким образом, процесс функционирования системы, описываемой УЦМ, выглядит следующим образом:

— если система находится в состоянии и принимается решение , то она получает доход ;

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

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

Стратегией p называется последовательность решений:

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

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

Оптимальной будет такая стратегия, которая максимизирует полный ожидаемый доход для всех i и n. В теории УМЦ разработаны два метода определения оптимальных стратегий: рекуррентный и итерационный .

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

— полный ожидаемый доход;

шагов, если система находится в состоянии i;

— непосредственно ожидаемый доход, т.е. доход на одном шаге, если процесс начался с i-го состояния;

— величина полного ожидаемого дохода за n прошедших шагов, если процесс начинался с j-го состояния (i¹j).

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

Конкретное применение метода будет рассмотрено далее на примере.

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

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

Представим графически линейную зависимость суммарного дохода от числа шагов (рис. 11).

Для наглядности график (см. рис. 11) изображен для УМЦ с двумя состояниями и . На графике прямая показывает зависимость суммарного дохода, если система “стартовала” из состояния . Соответственно, прямая изображает ту же зависимость для состояния . Обе прямые могут быть описаны линейными уравнениями :

g — угловой коэффициент прямой ;

— доход в i-том состоянии в конце процесса.

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

Рис. 11. Зависимость суммарного дохода от числа шагов

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

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

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

Обработка и анализ результатов моделирования

При выборе методов обработки существенную роль играют три особенности машинного эксперимента с моделью системы [34,35]:

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

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

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

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

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

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

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

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

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

— несмещенности, то есть равенства математического ожидания оценке самой вероятностной характеристике:

Учитывая, что случайные величины независимы, находим, что

откуда следует, что оценка математического ожидания является несмещенной, а дисперсии – смещенной.

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

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

— состоятельности оценки, то есть ее сходимости по вероятности при к оцениваемому параметру:

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

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

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

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

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

Так как данная оценка является несмещенной и состоятельной,

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

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

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

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

Выборочные авто и взаимокорреляционные функции и определяются в соответствии с выражениями

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

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

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

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

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

Выбор типа теоретического распределения проводится по гистограммам , выведенным на печать или на экран монитора.

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

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

где — количество значений случайной величины , попавших в -й подынтервал;

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

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

N — объем выборки значений случайной величины при машинном эксперименте.

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

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

— значение случайной величины ;

— число степеней свободы. Функции распределения табулированы.

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

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

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

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

Т а б л и ц а 17.1

Число запросов Число одночасовых интервалов с соответствующим числом запросов Относительная частота
0,619
0,279
0,078
0,018
0,004
0,002
Объем выборки 509 1,000

Известно, что распределение Пуассона выражается формулой

где = — вероятность наступления k событий;

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

На основании данных табл. 17.1 определим оценки математического ожидания и дисперсии:

где — как и ранее, полный объем выборки,

— число групп (интервалов) выборки;

— значение -й группы.

Вычисления сведем в таблицу 17.2

Т а б л и ц а 17.2

и окончательно получим

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

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

Для получения значения ожидаемой частоты для каждого подынтервала умножаем соответствующую величину на 509. Следующий шаг – определение критического значения величины для выбранного доверительного уровня 0,95 и числа степеней свободы 4 – 1 – 1 = 2 из таблицы критических величин, приведенных в справочнике. Находим, что табличное значение = 5,99, что больше расчетной величины =5,10. Таким образом, гипотеза принимается.

Т а б л и ц а 17.3

k P(k )
0,571 1,98
0,319 2,47
0,089 0,56
0,017
0,003 0,09
0,001
1,000 5,10

Последние три группы значений в нашем расчете были объединены с тем, чтобы получить значение частоты не менее 5 в каждой группе; вместо исходных 6 групп мы получили 4.

Критерий согласия Колмогорова — Смирнова. Основан на выборе в качестве меры расхождения величины .

Из теоремы Колмогорова следует, что при имеет функцию распределения

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

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

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

По имеющимся результатам вычисляют эмпирические функции распределения и и определяют

Затем при заданном уровне значимости находят допустимое отклонение

где и — объемы сравниваемых выборок.

Теперь проводится сравнение значений и ; если > , то нулевая гипотеза о тождественности законов распределения и с доверительной вероятностью отвергается.

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

Т а б л и ц а 17.4

Число запросов Наблюдаемая частота Наблюдаемая вероятность Теоретическая вероятность Интегральная вероятность II Интегральная вероятность III Абсолютная разность
0,619 0,571 0,619 0,571 0,048
0,279 0,319 0,898 0,890 0,008
0,078 0,089 0,976 0,979 0,003
0,018 0,017 0,994 0,996 0,002
0,004 0,003 0,998 0,999 0,001
0,002 0,001 1,000 1,000 0,000

Наибольшая абсолютная разность 0,048 получается в группе, соответствующей нулевому числу запросов. Именно эту разность надо сравнить с критическим значением, найденным из таблиц и равным при N и

Так как полученная нами наибольшая разность 0,048 не превышает критического значения, то и в этом случае принимается решение о том, что экспериментальное распределение подчиняется закону Пуассона.

Сравнение рассмотренных критериев, направленных на решение однородных задач, приводит к заключению о том, что критерий предпочтителен для больших выборок (более 100), в то время как критерий Колмогорова – Смирнова предпочтителен при .

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

где и – объемы выборок для оценки и соответственно;

и – оценки дисперсий соответствующих выборок.

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

Чувствительность критерия к «нормальной распределенности» величин и невелика. Он применим, если их распределения не имеют несколько вершин и не слишком ассиметричны.

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

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

Алгоритм применения критерия Фишера следующий:

— вычисляется выборочное отношение ;

— определяется число степеней свободы и , где и — объемы выборок для оценок и соответственно;

— при выбранном уровне значимости для величины и величин и по таблице F-распределения находятся значения и ;

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

В MATLABе для подбора вида закона распределения в максимальной степени соответствующего полученной гистограмме следует последовательно ввести три команды: n=hist(y,m), bar(n./length(y)) и disttool. Первая делит диапазон значений наблюдаемой переменной y на m равных интервалов и записывает в матрицу n число элементов, попавших в каждый из них. Вторая – вычисляет относительную частоту попадания в каждый интервал и выводит графическое представление полученной гистограммы. Третья – открывает диалоговое окно, обеспечивающее выбор и настройку параметров стандартных распределений (рис. 17.1), содержащее следующие элементы:

— поле вывода графика закона распределения (cdf-интегрального, pdf-дифференциального), в котором отображается визир предназначенный для точного определения координат;

— раскрывающийся список для выбора вида закона распределения (19 вариантов);

— раскрывающийся список для выбора плотности вероятностей или функции распределения;

— ползунки для изменения значений параметров распределения;

— поля ввода/отображения координат точек графика и параметров распределения.

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

Следующий этап обработки экспериментально полученной информации – проверка статистических гипотез. Проверка гипотезы о том, что наблюдаемая величина распределена по нормальному закону с известным СКО и математическим ожиданием равным M, осуществляется с помощью функции ztest, которая может принять одно из двух возможных значений: – если гипотезу следует принять и 1 – гипотезу следует отвергнуть. В качестве дополнительной информации функция ztest формирует величину SIG, которая отражает степень достоверности нулевой гипотезы — чем меньше SIG, тем больше доверия . Аналогичную задачу позволяет решить и функция ttest, которая в качестве дополнительной информации выдает значение условной вероятности того, что используемый статистический критерий примет некоторое значение в предположении, что нулевая гипотеза верна. Величина этой условной вероятности в зарубежной литературе по статистике называется p-value (р-значение). Если p-value оказывается меньше уровня значимости, то нулевая гипотеза отвергается. В качестве примера рассмотрим задачу об определении среднего числа покупателей некоей торговой точки в час пик в четную и нечетную недели. В результате натурного эксперимента были получены следующие результаты по подсчету количества покупателей, посетивших магазин в рабочие дни недели (включая субботу) с 17 до 18 часов соответственно, на четной и нечетной неделях: chet = [26,30,25,29,20,28]; nechet = [24,28,30,25,32,26]. Необходимо проверить гипотезу о том, что среднее количество покупателей остается неизменным независимо от номера недели. Вычислим среднее число покупателей на четной неделе: chislo = mean (chet). Величину chislo используем при обращении к функции ttest, при этом уровень значимости по умолчанию равен 0,05: [H, SIG] = ttest(nechet, chislo). В результате работы функции получим: H = 0, SIG = 0.3964. Это означает, что принятую гипотезу следует принять, однако степень ее достоверности средняя.

Выборки chet и nechet можно представить графически с помощью функции boxplot(y), параметр у в которой представляет собой матрицу со столбцами, содержащими значения исследуемых выборок. Для получения такой графической интерпретации в командном окне MATLAB следует ввести следующую последовательность команд.

chet = chet’ – транспонирование вектора chet;

nechet = nechet’ – транспонирование вектора nechet;

y = [chet, nechet] – объединение вектор-столбцов в матрицу;

boxplot(y) – получение графической интерпретации и вывод картинки на экран. Для рассматриваемого примера получим график, приведенный на рис. 17.2.

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

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

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

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

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

Рассмотрим их последовательно.

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

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

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

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

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

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

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

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

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

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

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

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

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

Мерой ошибки регрессионной модели служит среднеквадратическое отклонение

Для нормально распределенных процессов приблизительно 67 % точек находится в пределах одного отклонения от линии регрессии и 95 % точек – в пределах , как показано на правой части рисунка. Для проверки точности оценок и регрессионной модели могут быть использованы критерии Фишера (F-распределение) и Стьюдента (t-распределение). Аналогично могут быть определены коэффициенты уравнения регрессии и для случая нелинейной аппроксимации.

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

1,0 2,5 1,0 2,5
2,5 2,0 6,25 5,0
3,0 3,0 9,0 9,0
4,5 2,5 20,25 11,25
5,0 4,0 20,0
16 61,5 47,75

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

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

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

Оценка коэффициента корреляции, очевидно, будет иметь вид

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

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

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

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

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

Из-за влияния числа реализаций при моделировании на оценку коэффициента корреляции необходимо убедиться в том, что действительно отражает наличие статистически значимой корреляционной зависимости между исследуемыми переменными модели Мм. Это можно сделать проверкой гипотезы : = 0. Если гипотеза при анализе отвергается, то корреляционную зависимость признают статистически значимой. Очевидно, что выборочное распределение введенного в рассмотрение коэффициента при = 0 является гауссовским с нулевым средним и дисперсией Следовательно, область принятия гипотезы определяется неравенством

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

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

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

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

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

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

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

Моделирование данных (стр. 1 из 2)

2.4.1. Case-метод Баркера

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

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

Нотация ERD была впервые введена П. Ченом (Chen) и получила дальнейшее развитие в работах Баркера [8]. Метод Баркера будет излагаться на примере моделирования деятельности компании по торговле автомобилями. Ниже приведены выдержки из интервью, проведенного с персоналом компании.

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

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

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

Первый шаг моделирования — извлечение информации из интервью и выделение сущностей.

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

Рис. 2.18. Графическое изображение сущности

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

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

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

Следующим шагом моделирования является идентификация связей.

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

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

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

  • продавец может получить вознаграждение за 1 или более контрактов;
  • контракт должен быть инициирован ровно одним продавцом.

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

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

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

Последним шагом моделирования является идентификация атрибутов.

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

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

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

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

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

С учетом имеющейся информации дополним построенную ранее диаграмму (рисунок 2.25).

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

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

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

Рис. 2.26. Подтипы и супертипы

Рис. 2.27. Взаимно исключающие связи

Рекурсивная связь: сущность может быть связана сама с собой (рисунок 2.28).

Неперемещаемые (non-transferrable) связи: экземпляр сущности не может быть перенесен из одного экземпляра связи в другой (рисунок 2.29).

Рис. 2.28. Рекурсивная связь

Рис. 2.29. Неперемещаемая связь

Методология IDEF1

Метод IDEF1, разработанный Т.Рэмей (T.Ramey), также основан на подходе П.Чена и позволяет построить модель данных, эквивалентную реляционной модели в третьей нормальной форме. В настоящее время на основе совершенствования методологии IDEF1 создана ее новая версия — методология IDEF1X. IDEF1X разработана с учетом таких требований, как простота изучения и возможность автоматизации. IDEF1X-диаграммы используются рядом распространенных CASE-средств (в частности, ERwin, Design/IDEF).

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

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