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

• Автор: Мирошниченко, Любовь Александровна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Новосибирск
• Количество страниц: 222 с.

Содержание
Введение

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

1.1. Элементарные структурообразующие единицы текста

1.2. Методы сегментирования символьных последовательностей

1.2.1. Морфологический анализ текста без пробелов

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

1.2.3. Иерархическое представление последовательностей

с помощью порождающих грамматик.

1.2.4. Выявление моментов изменения свойств последовательности

1.3. Методы фрагментирования символьных последовательностей .

1.3.1. Статистические частотные методы фрагментирования .
1.3.2. Позиционные методы фрагментирования
1.3.3. Суперсинтаксические методы фрагментирования.
1.3.4. Методы фрагментирования, основанные на сопоставлении эволюционно иили функционально близких текстов
1.3.5. Поиск локальных аномалий в режиме скользящего окна
1.3.6. Агрегирование алфавита как способ выявления локальных структурных закономерностей .
1.3.7. Задание структурных элементов в виде образцов.
Выводы по первой главе .
Глава 2. Методы выделения структурных единиц на основе сложностных разложений текста
2.1. Различные модификации меры сложности ЛемпеляЗива .
2.1.1. Понятие повтора и его использование в сложностных разложениях
2.1.2. Векторная мера сложности
2.1.3. Мера сложности с пошаговой оптимизацией по ограниченному набору подстановок
2.1.4. Мера сложности с пошаговой оптимизацией по полному набору подстановок мера С .
2.2. Алгоритмы вычисления сложности символьной последовательности .
2.2.1. Алгоритм вычисления сложности при фиксированной подстановке
2.2.2. Алгоритм вычисления меры С .
2.3. Сложностные профили символьных последовательностей.
2.4. Случай нескольких последовательностей .
2.5. Некоторые свойства сложностных разложений .
2.6. Примеры применения сложностного анализа
к биологическим текстам .
2.6.1. Выявление блочной структуры и эволюционных
перестроек в промоторах.
2.6.2. Выявление взаимосвязей в Бфланкирующих районах
генов гормона роста.
2.6.3. Анализ полных геномов
2.6.4. Сравнительный анализ последовательностей дисков
политенных хромосом
Выводы по второй главе
Глава 3. Анализ серий в агрегированном алфавите .
3.1. Агрегирование алфавита .
3.2. Серийные характеристики
3.3. Использование серийных характеристик для анализа генетических текстов
3.3.1. Выявление аномалий в агрегированных ДНКпоследовательностях .
3.3.2. Анализ точечных мутаций .
3.3.3. Выявление регулярностей в локализации аминокислот
3.3.4. Кластеризуемость элементов в ДНКиоследовательностях совместный учет разных агрегирований
3.4. Сравнительный анализ серийных характеристик
3.5. Анализ взаимного расположения серий
Выводы по третьей главе .
Глава 4. Использование позиционной информации для
выделения структурных единиц и оценивания
их значимости .
4.1. Статистики для выявления неравномерностей позиционного распределения .
4.2. Схема анализа позиционного распределения заданной цепочки
по длине текста.
4.3. Описание экспериментов. Интерпретации результатов
4.3.1. Исходные данные .
4.3.2. Описание экспериментов.
4.3.3. Интерпретация результатов .
4.4. Примеры позиционных аномалий. Их взаимосвязь.
4.5. Пример практического использования позиционных аномалий .
4.6. Обсуждение результатов
Выводы по четвертой главе.
Глава 5. Представление структурных единиц в виде образцов и алгоритмы их поиска в тексте.
5.1. Постановка задачи поиска по частичноспецифицированному запросу
5.2. Алгоритмы поиска по групповому частично специфицированному запросу
5.2.1. Поиск группы константных образцов с помощью
алгоритма АхоКорасик
5.2.2. Поиск по групповому частично специфицированному запросу Алгоритм 1
5.2.3. Поиск по групповому частично специфицированному запросу Алгоритм 2
5.2.4. Апробация алгоритмов 1 и 2
5.3. Использование недетерминированных конечных автоматов
для поиска по групповому запросу
5.3.1. Поиск образца, содержащего неопределенные позиции .
5.3.2. Алгоритм 3 Поиск по группе образцов с элементами типа X
5.3.3. Алгоритм 4 Поиск по группе образцов с элементами типа X
5.3.4. Алгоритм 5 Поиск по групповому частично специфицированному запросу общий случай
5.4. Выявление совпадений, вложений и пересечений
среди образцов запроса.
5.4.1. Описание алгоритма выявления взаимосвязанных образцов
5.4.2. Апробация алгоритма.
5.5. Поиск образцов, содержащих переменные
5.5.1. Формулировка задачи.
5.5.2. Адаптивный алгоритм поиска образцов с одной переменной
в константном окружении.
Выводы по пятой главе .
Заключение
Список использованных источников


Все описываемые ниже методы структурирования слитных без разделителей символьных последовательностей и текстов на естественном языке можно рассматривать как своего рода фильтрующие процедуры, выделяющие из всего множества повторов некоторую их часть, удовлетворяющую определенным ограничениям статистического, синтаксического или семантического характера. Следуя лингвистической терминологии , эти методы можно условно разделить на две группы. Элементы разбиения можно трактовать как структурные единицы. Вторую группу составляют методы фрагментирования, осуществляющие выбор наиболее значимых элементов фрагментов текста. Различаются эти методы способами формализации понятия значимости или информативности. В работе описана попытка автоматического вычленения морфем элементарных смысловых единиц языка из слитного текста с устраненными разделителями между словами и знаками препинания. Предполагается, что письменность исследуемого языка фонематическая, т. В основе подхода лежит представление о морфемах как об устойчивых в некотором смысле отрезках текста. Первое из этих свойств названо внутренней устойчивостью ЗДпе, второе внешней устойчивостью x. Если и Г левая и правая части некоторой цепочки i в разбиении текста, то прогнозирование оставшейся части цепочки по уже появившейся оценивается величиной при расширении вправо или пг при расширении влево, где частота вхождения цепочки а в текст. Эти величины можно рассматривать в качестве оценок соответствующих условных вероятностей. При сильном прогнозировании они стремятся к 1, при слабом к нулю. Для других вариантов разбиения цепочки человек на 2 части степень прогнозируемости будет не столь высокой. Внешняя устойчивость позволяет выделить цепочки, которые можно считать неделимыми в том смысле, в котором неделима комбинация букв и в английском языке. В то же время это условие отсекает все однократно встречающиеся цепочки, поскольку все их расширения имеют ту же частоту. Предложена приближенная последовательная процедура оптимизации, на каждом шаге которой список формируемых морфем увеличивается на единицу. Для однобуквенных цепочек i полагается равной нлю. В качестве достоинства подхода отмечена его универсальность возможность применения к текстам на неизвестном языке. Близкие в идейном плане подходы были развиты для выявления структурных единиц в ДНК и аминокислотных последовательностях , а также в знаменных песнопениях 3, 4, однако там не ставилось целыо получение полного разбиения текста, т. Это оправдано, поскольку методика носит статистический характер и начинает давать сбои на низкочастотных структурных единицах. В основе подхода лежит понятие сложности конечной символьной последовательности, введенное Лемпелем и Зивом в г. Его можно рассматривать как пример конструктивной реализации идей А. Н. Колмогорова по оцениванию сложности объектов, высказанных в . Количественной мерой сложности при этом выступает длина наикратчайшего описания объекта. Лем пел ь и Зив предложили измерять сложность последовательности числом шагов порождающего ее процесса. Допустимыми операциями при этом являются генерация символа и копирование готового фрагмента из предыстории т. Первая операция, как минимум, необходима для синтеза элементов алфавита. Ее применение увеличивает длину последовательности на 1. Вторая операция использует уже имеющиеся заготовки для максимально возможного удлинения последовательности. На каждом шаге процесса каждая из операций используется по разу. Я5 г 5г 1 г2 5г 1 5гт 1 Я, 1. Ам шаге, а т тя5 число шагов процесса. Из всевозможных схем порождения 5 выбирается минимальная по числу шагов. Минимальность числа шагов обеспечивается выбором для копирования на каждом шаге максимально длинного прототипа из предыстории. Представление сегментацию 5 в виде 1. Чтобы в нем не было повторяющихся компонентов, на каждом шаге максимальный прототип удлиняется еще на один элемент генерация символа. У у 1, 1. А указатель копирования номер позиции, с которой начинается копирование на км шаге к полагается равным 0, если в позиции г1 1 стоит ранее не встречавшийся символ. Пример 1. Пусть Е Л, , 5 АВ В АВ ААВ В ААВ АВ В А. Сьг1 тпт5.