Программный комплекс и эффективные методы организации и индексации больших массивов текстов

• Автор: Веретенников, Александр Борисович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Екатеринбург
• Количество страниц: 150 с. : ил.

Введение

1 Формальные модели и обзор существующих структур данных и алгоритмов

1.1. Формальная модель текста.

1.2. Формальная модель текста с учетом морфологии

1.3. Формальная модель базы данных поисковой системы .

1.4. Формальная модель программного комплекса поисковой системы

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

1.6. Модель внешней памяти.

1.7. Вдеревья.

1.7.1. Вдерово при фиксированном размере элементов . .

1.7.2. Поиск элемента в Вдсреве

1.7.3. Вставка элемента в Вдерево
1.7.4. Вдерево при произвольном размере элементов . .
1.7.5. Вдеревья при заполнении узлов на
1.7.6. Кэширование .
1.8. Инвертированные файлы.
1.8.1. Идея инвертированных файлов
1.8.2. Внешняя сортировка слиянием
1.8.3. Создание инвертированного файла.
1.9. Суффиксные массивы.
1 i Вдеревья
1
1 x
2 Деревья
2.1. Базовая идея дерева
2.2. Структура дерева. описание основного алгоритма создания индекса.
2.2.1. Компоненты дерева
2.2.2. Организация данных для эффективного чтения .
2.2.3. Эффективное заполнение блоков
2.2.4. Поиск словоформы и извлечение информации о ней
2.2.5. Кэширование для слов, входящих в словарь морфологического анализатора
2.2.6. Кэширование для слов, не входящих в словарь морфологического анализатора
2.2.7. Общая структура системы индексирования и поиска .
2.2.8. Создание индекса
2.3. Теоретическое обоснование производительности.
2.4. Замечания
2.5. Поиск .
2.6. Кодирование позиций слов.
2.7. Обработка наиболее часто встречающихся слов
2.7.1. Алгоритм поиска
2.8. Репозитарий
2.9. Вдерево с использованием тернарных деревьев.
2.9.1. Тернарные деревья.
2.9.2. Поиск в дереве
2.9.3. Удаление .
2.9.4. Разделение
3 Программный комплекс и результаты экспериментов
3.1. Система индексирования и поиска на базе СЬВдерева . .
3.1.1. Структура списка документов.
3.1.2. Описание возможностей разработанной системы .
3.1.3. Создание индекса
3.1.4. Конфигурационный файл индекса
3.1.5. Поиск
3.1.6. Журнал индекса
3.1.7. Настройки библиотеки
3.1.8. Модуль поддержки форматов.
3.1.9. Внутреннее устройство библиотеки
3.2. Результаты экспериментов.
3.2.1. Исследование производительности базовой структуры
3.2.2. Сравнение с инвертированными файлами .
3.2.3. Сравнение с существующими разработками
3.2.4. Сравнение эффективности СЬВдерева в битных
и битных архитектурах
3.2.5. Эксперименты поиска
4 Вспомогательные компоненты
4.1. Оптимизация выделения динамической памяти
4.2. i Литература
Введение


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