О сервисе WebGround

Ваша тема


Новости сайта

Литература

обложка книгиИнтернетика. Навигация в сложных сетях: модели и алгоритмы
Большакова Е.И., Клышинский Э.С., Ландэ Д.В., Носков А.А., Пескова О.В., Ягунова Е.В. Автоматическая обработка текстов на естественном языке и компьютерная лингвистикаАвтоматическая обработка текстов на естественном языке и компьютерная лингвистика (pdf)
Ягунова Е.В., Макарова О.Е., Антонова А.Ю., Соловьев А.Н. Разные методы компрессии в исследовании понимания новостного текстаРазные методы компрессии в исследовании понимания новостного текста (pdf)
Крылова И.В, Пивоварова Л.М., Савина А.В., Ягунова Е.В. Исследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистовИсследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистов (pdf)
Ягунова Е.В. Исследование перцептивной устойчивости фонем как элементов речевой цепиИсследование перцептивной устойчивости фонем как элементов речевой цепи (pdf)
Ягунова Е.В. Вариативность структуры нарратива и разнообразие стратегий пониманияВариативность структуры нарратива и разнообразие стратегий понимания (pdf)
Ягунова Е.В., Пивоварова Л.М. Экспериментально-вычислительные исследования художественной прозы Н.В. ГоголяЭкспериментально-вычислительные исследования художественной прозы Н.В. Гоголя (pdf)
Ягунова Е.В. Вариативность стратегий восприятия звучащего текстаВариативность стратегий восприятия звучащего текста (pdf)
Ягунова Е.В. Спонтанный нарратив у детей и у взрослыхСпонтанный нарратив у детей и у взрослых (pdf)
Ягунова Е.В. Исследование избыточности русского звучащего текстаИсследование избыточности русского звучащего текста (pdf)
Ягунова Е.В. Фонетические признаки опорных сегментов и восприятие русского текстаФонетические признаки опорных сегментов и восприятие русского текста (pdf)
Ягунова Е.В. Коммуникативная и смысловая структура текста и его восприятиеКоммуникативная и смысловая структура текста и его восприятие (pdf)
Ягунова Е.В. Где скрывается смысл бессмысленного текста?Где скрывается смысл бессмысленного текста? (pdf)
Ягунова Е.В. Эксперимент в психолингвистике: Конспекты лекций и методические рекомендацииЭксперимент в психолингвистике: Конспекты лекций и методические рекомендации (pdf)
Ягунова Е.В. Теория речевой коммуникацииТеория речевой коммуникации (pdf)
Антонова А.Ю., Клышинский Э.С., Ягунова Е.В. Определение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемостиОпределение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемости (pdf)
Ягунова Е.В. Эксперимент и вычисления в анализе ключевых слов художественного текстаЭксперимент и вычисления в анализе ключевых слов художественного текста (pdf)
Ягунова Е.В. Ключевые слова в исследовании текстов Н.В. ГоголяКлючевые слова в исследовании текстов Н.В. Гоголя (pdf)
Пивоварова Л.М., Ягунова Е.В. Информационная структура научного текста. Текст в контексте коллекцииИнформационная структура научного текста. Текст в контексте коллекции (pdf)
Савина А.Н., Ягунова Е.В. Исследование коллокаций с помощью экспериментов с информантамиИсследование коллокаций с помощью экспериментов с информантами (pdf)
Ягунова Е.В., Пивоварова Л.М. От коллокаций к конструкциямОт коллокаций к конструкциям (pdf)
Пивоварова Л.М., Ягунова Е.В. Извлечение и классификация терминологических коллокаций на материале лингвистических научных текстовИзвлечение и классификация терминологических коллокаций на материале лингвистических научных текстов (pdf)
Julia Kiseleva. Grouping Web Users based on Query LogGrouping Web Users based on Query Log (pdf)
Julia_Kiseleva_Unsupervised_Query_Segmentation_Using_Click_Data_and_Dictionaries_Information.pdfUnsupervised Query Segmentation Using Click Data and Dictionaries Information (pdf)
Четыре лекции о методе
Начала предметного анализа методов (на примере метода Ф.Бэкона)
Вариативность стратегий восприятия звучащего текста
Извлечение и классификация коллокаций на материале научных текстов. Предварительные наблюдения
Природа коллокаций в русском языке. Опыт автоматического извлечения и классификации на материале новостных текстов
Войтишек А. Повторы. Лирические рефреныПовторы. Лирические рефрены (pdf)
Войтишек А. Новое. Лирические рефреныНовое. Лирические рефрены (pdf)
Войтишек А. Всё об одном и том жеВсё об одном и том же. 500 лирических рефренов к 50-летию (pdf)
Войтишек А. Тысяча-часть-1Тысяча-часть-1 (pdf)
Войтишек А. Тысяча-часть-2Тысяча-часть-2 (pdf)
Войтишек А. АлфавитАлфавит (pdf)

11.2. Абстрактные фракталы

 

Рассмотрим принципы формирования нескольких абстрактных фрактальных объектов, которые обладают  выраженными свойствами самоподобия.

Построение фрактального множества, снежинки Хельге фон Коха (H. Von Koch) (рис. 62),  начинается с правильного треугольника, длина стороны которого равна 1. Сторона треугольника считается базовым звеном. Далее, на любом шаге итерации каждое звено заменяется на образующий элемент – ломаную, которая состоит по краям исходного звена из отрезков длиной 1/3 от длины этого звена, между которыми размещаются две стороны правильного треугольника со стороной также в 1/3 длины звена. Все  отрезки  - стороны полученной ломаной считаются базовыми звеньями для следующей итерации. Кривая, получаемая в результате n-ой итерации при любом конечном n, называется предфракталом, и лишь при n, стремящимся к бесконечности, кривая Коха становится фракталом. Полученное в результате итерационного процесса фрактальное множество представляет собой линию бесконечной длины, которая ограничивает конечную площадь. Действительно, при каждом шаге число сторон результирующего многоугольника увеличивается в 4 раза, а длина каждой стороны уменьшается только в 3 раза, т.е. длина многоугольника на  n-ой  итерации равна  и стремится к бесконечности с ростом .

        

 

Рис. 62. Первые 5 поколений снежинки Коха

 

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

 

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

.

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

Очевидно, фрактальная размерность салфетки Серпинского составляет:

.

Рис. 63. Первые шаги алгоритма построения салфетки Серпинского

 

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

 

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

Алгоритм построения множества Мандельброта (рис. 64) основан на итеративном вычислении по формуле:

где  и C - комплексные переменные.

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

ris64

Рис. 64.  Множество Мандельброта

 

В 80-х годах прошлого столетия  появился метод "Систем Итерационных Функций" (Iterated Functions System - IFS), представляющий собой простое средство получения фрактальных структур. IFS представляет собой систему функций, которые отображают одно многомерное множество на другое. Наиболее простая реализация IFS представляет собой афинные преобразования плоскости:

        

где  - предыдущие значения координат,  - новые значения,   и- коэффициенты.

         В качестве примера использования IFS для построения фрактальных структур, можно привести  "дракона" Хартера-Хейтуея, сформированного с помощью Java-апплета, приведенного в Интернет по адресу http://www.fractals.nsu.ru/fractals.chat.ru/ifs2.htm (рис. 65). Использование IFS для сжатия обычных изображений, например, фотографии основаны на выявлении локального самоподобия (в отличие от фракталов, где наблюдается глобальное самоподобие).

В 80-х годах М. Барнсли (M. Barnsley ) и А. Слоан (A. Sloane) предложили идею  сжатия и хранения графической информации, основанную на соображениях теории  фракталов и динамических систем. На основе этой идеи был создан алгоритм фрактального сжатия информации, который позволяет  сжимать некоторые образцы графической информации в 500-1000 раз. При этом каждое изображение кодируется несколькими простыми афинными преобразованиями.   

 

dr01

dr06

dr12

а)

б)

в)


 Рис. 65. "Дракон" Хартера-Хейтуея: а) – второй  шаг итерации;

б) – шестой шаг; в) – двенадцатый шаг

        

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

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