Введение
ГЛАВА 1. Обзор достижений в областях конструирования дескрипторов трехмерных объектов и скоростного приближенного поиска по шаблону в строках 12
1.1 Информационные объекты и дескрипторы 12
1.2 Обзор некоторых дескрипторов трехмерных объектов 17
1.3 Краткий обзор роли дескрипторов в некоторых фундаментальных техниках распознавания образов 21
1.3.1 Статистическая классификация (statistical classification) 21
1.3.2 Синтаксический (структурный) подход 22
1.3.3 Нейронные сети 23
1.3.4 РАМ-алгоритм 24
1.4 Расстояние редактирования и ограничения неэмпирических методов приближенного поиска, основанных на расчете расстояния редактирования 27
1.5 Эмпирики семейства BLAST 32
1.6 Метод block-distance («блочного расстояния») 35
1.7 Анализ распределений -граммов 39
1.8 Выводы 40
ГЛАВА 2. q-грамм статистичесике подходы в конструировании дескрипторов и приближенном поиске в строках 42
2.1.1 Дескриптор DQG, отражающий распределение /7-мерных -граммов 43
2.1.2 Дескриптор QSN, отражающий распределение совместных появлений пар «-мерных -граммов 47
2.2.1 Алгоритм q-AS (q-gram Approximate Searching/ q-грамм приближенный поиск) 52
2.2.2 Модели строк и искажений в строках, используемые при выборе параметров алгоритма q-AS 58
2.2.3 q-Subword complexity (сложность по подстрокам длины q) случайных строк 66
2.2.4 Упрощенный алгоритм выбора параметров Алгоритма q-AS 70
2.2.5 Особенности и перспективы Алгоритма q-AS 72
2.2.6 Выводы 73
ГЛАВА 3. Экспериментальные исследования 16
3.1.1 Качественные эксперименты по применению дескрипторов DQG и QSN в задачах кластеризации данных 76
3.1.2 DQG-дескриптор для 3D объектов 82
3.1.3 Сравнительный benchmark-тест PSB-2004 84
3.1.4 Количественные эксперименты по применению дескриптора DQG в задачах классификации 3D объектов 87
3.2.1 Экспериментальное исследование методов выбора параметров для Алгоритма q-AS 88
3.2.2 Эксперименты по применению Алгоритма q-AS 91
3.2.3 Сравнение Алгоритма q-AS с эмпирической системой приближенного поиска BLAST 92
3.3 Выводы 94
Заключение 97
Список литературы 102
