Анализ и разработка индекса для поиска последовательностей элементов произвольного типа по их фрагментам в реляционных базах данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Чернов, Андрей Фёдорович

• Чернов, Андрей Фёдорович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Чернов, Андрей Фёдорович

ОГЛАВЛЕНИЕ

Список сокращений

ВВЕДЕНИЕ

ГЛАВА 1. Постановка задач исследования. Анализ способов индексации данных. Выбор структур и алгоритмов

1.1 Постановка решаемых прикладных задач

1.1.1 Задача поиска по фрагменту в числовых массивах

1.1.2 Задача текстового поиска по подстроке

1.2 Анализ способов индексации данных и выбор типа индекса для последовательностей элементов

1.2.1 Индексы на основе битовых карт

1.2.2 НазИ-индексы

1.2.3 Индексы на основе В-деревьев

1.2.4 Индексы на основе В+-деревьев

1.2.5 Индексы на основе суффиксных структур данных

1.2.6 Индексы на основе Я-деревьев

1.2.7 Индексы на основе БШ-деревьев

1.2.8 Выбор структуры индекса для индексации последовательностей

1.3 Постановка задач дальнейшего исследования

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

ГЛАВА 2. Разработка модификации структуры ЬШ-деревьев и эффективных алгоритмов поиска с ней

2.1 Асимптотический анализ алгоритмов работы с ШЗ-деревом

2.1.1 Анализ сложности поиска фрагмента в последовательностях по

КО-дереву для среднего случая

2.2 Анализ причин «ложных попаданий» при поиске по ШЗ-дереву

2.3 Математическая оценка количества «ложных попаданий» при поиске

по БШ-дереву

2.3.1 Вычисление количества комбинаций последовательностей с повторяющимися элементами

2.3.2 Оценка количества «ложных попаданий» при поиске по КО-

дереву

2.4 Модификация структуры Ш>дерева для минимизации «ложных попаданий»

2.4.1 Этап 1: добавление в индекс информации о количестве одинаковых элементов в последовательностях

2.4.2 Этап 2: добавление в индекс признаков повторения элементов подряд в последовательностях

2.4.3 Этап 3: использование разбиения последовательностей для учета порядка расположения элементов

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

ГЛАВА 3. Выбор параметров алгоритмов построения и использования ЬШ-деревьев. Экспериментальная проверка эффективности

3.1 Экспериментальная проверка эффективности поиска с

использованием модифицированных КО-деревьев

3.1.1 Используемые средства для проверки эффективности

3.1.2 Оценка количества «ложных попаданий» при поиске на

случайных данных

3.1.3 Результаты экспериментальной проверки эффективности поиска

3.1.4 Оценка зависимости эффективности поиска от размера БД

3.2 Доработка алгоритма построения ИГ)-дерева для эффективности разбиения последовательностей на фреймы

3.2.1 Разработка алгоритма анализа данных для формирования актуальных разделителей фреймов для содержимого БД

3.2.2 Экспериментальная проверка корректности формирования актуальных разделителей фреймов

3.2.3 Экспериментальная проверка эффективности поиска с использованием доработанного алгоритма построения RD-дерева

3.3 Оценка степени применимости выполненной модификации RD-деревьев к различным искомым данным

3.4 Оценка влияния выполненной модификации RD-деревьев на время построения индекса

3.4.1 Оценка зависимости времени построения от размера БД

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

ГЛАВА 4. Применение полученных результатов для практических задач

4.1 Применение модифицированных RD-деревьев для поиска по

фрагменту в числовых массивах

4.2 Применение модифицированных RD-деревьев для текстового поиска

по подстроке

4.2.1 Применение модифицированных RD-деревьев полнотекстового поиска с использованием хеширования слов

4.3 Реализация индекса на основе модифицированных RD-деревьев для СУБД PostgreSQL

4.3.1 Выбор встроенного в СУБД индекса для его модификации

4.3.2 Доработка операторов сравнения числовых массивов для учета порядка элементов

4.3.3 Модификация структуры индекса и алгоритмов работы с ним

4.3.4 Использование сигнатур переменной длины в узлах RD-дерева

4.3.5 Анализ экспериментальных результатов

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

ЗАКЛЮЧЕНИЕ

146

СПИСОК ЛИТЕРАТУРЫ

Приложение А (обязательное) Алгоритм поиска фрагмента в последовательностях по RD-дереву

Приложение Б (справочное) Алгоритм программы для определения степени применимости модификаций RD-дерева

Приложение В (справочное) Реализация определения вхождения числовых массивов друг в друга, учитывающая порядок элементов

156

Список сокращений

ипс Информационно-поисковая система

мд Метод доступа (к данным)

СУБД Система управления базой данных

БД База данных

ПО Программное обеспечение

GIST Обобщенное поисковое дерево (General Information Search Tree)

Введение диссертации (часть автореферата) на тему «Анализ и разработка индекса для поиска последовательностей элементов произвольного типа по их фрагментам в реляционных базах данных»

ВВЕДЕНИЕ

Актуальность работы. В современном мире огромную роль играют информационно-поисковые системы (ИПС). Информационные технологии проникают во все сферы человеческой деятельности. На сегодняшний день невозможно себе представить отсутствие электронного хранения информации с поддержкой соответствующих способов ее эффективного поиска. На темы, связанные с поиском информации, ее отбором из огромных объемов данных, пишется большое количество научных трудов [14,16,21,32], появляются новые способы поиска, постоянно совершенствуются существующие алгоритмы [50]. К настоящему времени в многочисленных ИПС накоплены колоссальные объемы информации, и ни на минуту не замедляются темпы их роста. Все это приводит к постоянному росту нагрузки и, как следствие, к росту требований к поисковым системам, что подчеркивает актуальность и значимость исследований в области информационного поиска.

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

Для стандартных типов данных (числа, даты и т.п.) к настоящему времени разработано много эффективных МД, реализованных в современных системах управления базами данных (СУБД). Кроме того, хорошо проработан и реализован в большом количестве ИПС текстовый поиск - словарный поиск, полнотекстовый поиск [18], поиск по различным шаблонам [16] и т.д. Однако для этих и других типов данных, которые также важны и востребованы на практике, в области информационного поиска еще остается немало проблем и актуальных вопросов.

Для многих типов данных, помимо поиска на точное равенство, развиваются возможности нечеткого поиска [53], приближенного поиска по сходству [32] и др.

Вопросам проектирования структур данных и алгоритмов информационного поиска посвящены работы Д. Хеллерстейна, А. Гуттмана, Р. Финкеля, М. Никола и других. Из отечественных публикаций можно выделить работы О. С. Бартунова, Т. Г. Сигаева, И. А. Андрианова, П. Г. Айткулова, Л. М. Бойцова и других. Особенно значимыми для данной диссертации явились работы Д. Хеллерстейна, О. С. Бартунова и Т. Г. Сигаева в области использования различных структур данных для информационного поиска.

Практически все современные МД к данным объединяет то, что для данных строятся специальные вспомогательные поисковые структуры - индексы, использование которых позволяет существенно сократить время поиска информации. Например: битовые карты, В-деревья и их модификации, Я-деревья и их модификации, суффиксные структуры данных и др.

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

• При поиске числовых массивов по их фрагменту, как правило, не учитывается порядок следования элементов (например, Ш>деревья в СУБД PostgreSQL [19,65]),

• Для обеспечения поиска строк по подстроке, как правило, требуется большое количество памяти под индекс, многократно превышающее размер самих данных (например, суффиксные структуры [14,16], которые, к тому же, требуют серьезного перестроения даже при небольших изменениях данных),

• Не существует единого индексного МД, применяемого для последовательностей элементов любого типа.

Проблема обработки последовательностей притягивает повышенное внимание в сообществе объектно-ориентированных базах данных (БД), а также

это свойственно и для приложений, использующих традиционные реляционные базы данных [59].

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

Исследование, выполненное в настоящей работе, направлено на выбор наиболее подходящего существующего индексного МД к последовательностям элементов и на реализацию на его основе эффективного поиска по фрагменту. В качестве практических задач, которые решены на основе выполненных теоретических разработок, рассматривается поиск по фрагменту в числовых массивах, отражающих хронологию каких-либо событий, а также текстовый поиск по подстроке. Возможны и другие применения разработанных структур и алгоритмов. Результаты исследования применены при разработке нового индекса для свободно распространяемой СУБД PostgreSQL [65] и внедрены в реальные прикладные системы.

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

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

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

3. Разработка программных реализаций модифицированной структуры индекса.

4. Получение экспериментальных данных, сравнение с известными аналогами.

5. Внедрение результатов работы в деятельность конкретных организаций.

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

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

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

Научная новизна работы заключается в следующем:

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

результате чего достигнуто существенное ускорение поиска последовательностей

«

по фрагменту.

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

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

Практическую значимость имеют следующие полученные в диссертации результаты:

1. Разработанный индекс для СУБД PostgreSQL, основанный на модифицированном М>дереве, применяемый для ускорения поиска числовых последовательностей по фрагменту и представляющий собой программный модуль для расширения СУБД.

2. Методика для ускорения и упрощения формулирования сложных, но достаточно востребованных, поисковых запросов, использующая сознательную денормализацию БД и поиск фрагментов в числовых массивах, тем самым обеспечивающая актуальность применения модифицированных ЯО-деревьев для ускорения поиска числовых массивов.

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

На защиту выносятся следующие основные результаты и положения:

1. Модификация ЯО-деревьев, предложенных Дж. Хеллерстейном, и поисковые алгоритмы, использующие ее для существенного ускорения поиска последовательностей по фрагменту.

2. Алгоритм формирования актуальных для содержимого БД параметров построения ЬШ-дерева, используемый при анализе данных на начальном этапе построения индекса и приводящий к дополнительному ускорению поиска, а также обеспечивающий одинаковую высокую эффективность, не зависимую от содержимого БД.

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

Апробация работы: Основные результаты работы докладывались и получили положительную оценку на следующих конференциях и семинарах: седьмая всероссийская научно-техническая конференция «Вузовская наука региону» (Вологда, ВоГТУ, 2009 г.), всероссийская научная конференция

«Молодые исследователи - регионам» (Вологда, ВоГТУ, 2009, 2010, 2011 гг.), III ежегодные смотры-сессии аспирантов и молодых ученых по отраслям наук (Вологда, ВоГТУ, 2009 г.), IV ежегодные смотры-сессии аспирантов и молодых ученых по отраслям наук (Вологда, ВоГТУ, 2010 г), седьмая международная научно-техническая конференция «Автоматизация и энергосбережение машиностроительного и металлургического производств, технология и надежность машин, приборов и оборудования» (Вологда, ВоГТУ, 2012), научный семинар вологодского регионального отделения Научного совета РАН по методологии искусственного интеллекта (Вологда, ВГПУ, 2013 г.), международная научно-практическая конференция «Вопросы образования и науки в XXI веке» (Тамбов, ИГЖ, 2013 г.), международная научно-практическая конференция «Современное общество, образование и наука» (Тамбов, ИПК, 2013 г.).

Кроме того, материалы работы использованы в Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы: «Разработка методов формализации и верификации распределенных информационно-поисковых систем на основе сервис-ориентированной архитектуры».

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

Реализация и внедрение результатов. Теоретические и практические результаты работы внедрены в программные продукты компании R-Style Softlab (ЗАО «Эр-Стайл Софтлаб»). В частности в подсистеме «Кредитование» интегрированной банковской системы (ИБС) RS-Bank была реализована возможность эффективного поиска по фрагменту в числовых массивах, отражающих хронологию выполнения операций. В числовых массивах хранились идентификаторы операций, выполненных по кредитному договору. Таким

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

Кроме того, в подсистеме «Расчетный банк» ИБС Я8-Вапк была реализована возможность эффективного поиска банковских документов и клиентов банка по подстроке, что позволило значительно повысить производительность системной операции проверки клиентов на причастность к террорестическим организациям.

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

Публикации результатов исследования. Основное содержание диссертационной работы опубликовано в 13 научных работах [1-13], среди которых 3 публикации в ведущих рецензируемых изданиях, рекомендованных ВАК, 1 монография и 9 докладов в материалах международных, национальных и региональных конференций.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения, списка сокращений, библиографического списка и 3 приложений. Работа содержит 156 страниц машинописного текста, включая 49 рисунков и 8 таблиц. Библиографический список включает 65 наименований.

ГЛАВА 1. Постановка задач исследования. Анализ способов индексации данных. Выбор структур и алгоритмов

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

Определение 1.1 Последовательность элементов — набор каких-либо элементов, в котором учитывается порядок следования элементов друг за другом.

1.1 Постановка решаемых прикладных задач

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

1.1.1 Задача поиска по фрагменту в числовых массивах

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

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

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

Достаточно часто индексы могут быть неприменимы либо недостаточно эффективны по причине нормализации хранимой в БД информации. Нормализация данных впервые была представлена в 1970 году и к настоящему времени очень хорошо и широко документирована [35,41,54]. Нормализация данных — это методика для формирования набора таблиц, которые представляют реальные бизнес-записи в базе данных, что полностью избавляет от дублирования данных в условиях высокой стоимости ресурсов хранения [39]. Разработка нормализации данных была выполнена под влиянием действовавших в то время мощных побудительных причин - дисковое пространство было дефицитным и дорогостоящим [39]. В результате общепринятым подходом стало преобразование бизнес-записей в нормализованное представление для компьютеров (и обратно) [39]. Фактически в сформированном наборе таблиц дублируются лишь значения ключей, связывающих таблицы, а основные элементы данных хранятся ровно один раз. В результате нормализации данных одна бизнес-запись может быть представлена посредством десятков или даже сотен таблиц [39]. Нормализованная схема базы данных - неестественное представление бизнес-записей, очень трудное для понимания бизнес-пользователями и неэффективное для формулировки и обработки аналитических бизнес-запросов. [39]

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

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

выполнено десятки и сотни операций (выдача кредита, погашение, вынос на просрочку и др.). Необходимо ускорить поиск кредитных договоров в запросах типа: «найти все договоры, по которым после выдачи кредита было не менее двух погашений подряд». На рисунке 1.1 приведена схема хранения данных, соответствующая третьей нормальной форме [35,41], которая в настоящее время является стандартом де-факто при проектировании БД.

кредитные„договоры

, идент_договора INTEGER

назв_договора VARCHAR(IOO)

операции_по_договорам

идент_договора INTEGER пор_номер_операции INTEGER идент_операции NTEGER

операции

идент_операции INTEGER

назв_операции VARCHAR(IOO)

Рисунок 1.1- Нормализованная схема БД

В данном случае таблица «операции_по_договорам» является синтетической (не естественной), полученной в результате нормализации данных. В таблице 1.1 приведен пример содержимого данной таблицы БД.

Таблица 1.1- Пример содержимого таблицы БД «операции по договорам»

идент_договора пор_номер_операции идент_операции

1 1 1 (выдача) —

1 2 2 (погашение) —

1 3 3 (вынос на просрочку) —

2 1 1 (выдача) —

2 2 2 (погашение) —

2 3 2 (погашение) —

В данном случае требуемый поисковый запрос «найти все договоры, по которым после выдачи кредита было не менее двух погашений подряд» на языке SQL [61] формулируется сравнительно сложно (см. рисунок 1.2). Современные СУБД не позволяют эффективно выполнить такой поиск даже с использованием

индексов. Приходится использовать такие неэффективные по быстродействию SQL-операторы, как IN, EXISTS, а также вложенные запросы. В результате такой поисковый запрос выполняется медленно.

SELECT назБ_договора FROM кредитные_догоБоры

WHERE идант договора IN (SELECT DISTINCT идент_договора FROM операдии_по_догоБорам опер вневш WHERE иден.т_операции = 1

ÄND EXISTS {SEbECT * FROM операции_по_догоБорам опер_внутр

WHERE опер_Бнутр.идект_договора = опер_Бнешн.идент_договора ÄND опер_вмутр.пор_комер_операции = опер_Бнешн.пор_номер_операции + 1 äND опер_внутр.идент_операщо1 = 2) ÄND EXISTS (SELECT * FROM операцш_по_договораи опер_внутр

WHERE 0лер_Бнутр.идент_д0Г0Бара — опер_Бнешн.идент_договора

JiND опер_Бнутр.пор_камер_операции = опер_внешн. пор_номер_опера1?«и + 2

äND опер_внутр .идент_операц£«к = 2) ) ;

Рисунок 1.2 - Пример поискового запроса к нормализованным данным

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

Поэтому в последнее время для удобства/возможности выполнять различные поисковые запросы, используя индексные структуры, все чаще прибегают к изменению логической структуры БД - сознательной денормализации [39,40]. Денормализация заключается в хранении бизнес-записей без их декомпозиции на несколько таблиц, что позволяет:

• во-первых, формулировать поисковые запросы более лаконично (например, на языке SQL [61]), что приводит к ускорению их выполнения,

• во-вторых, эффективно использовать индексы, что также приводит к ускорению поиска.

Возвращаясь к примеру с кредитными договорами в коммерческом банке, в результате денормализации можно удалить синтетическую таблицу «операции_по_договорам» из схемы БД (рисунок 1.3).

кредитные_договоры

операции

идент^оговора. INTEGER назв^договора. VARCHAR(100) выпопненные_опер: tNTEGERf]

Щ, идент_операции: INTEGER

назв_операции: VARCHAR(100)

Рисунок 1.3 - Денормализованная схема БД

Таким образом, хронологическая последовательность операций, выполненных по каждому договору, хранится в самой таблице «кредитные_договоры» в виде числового массива «выполненные_опер». В этих числовых последовательностях достаточно просто выполнить поиск по фрагменту. На рисунке 1.4 приведена формулировка требуемого поискового запроса «найти все договоры, по которым после выдачи кредита было не менее двух погашений подряд» на языке SQL (используется специальный оператор @>, означающий поиск по фрагменту).

SELECT назв_договора FROM кредш?ные_д о говоры WHERE выполненные_опер @> * {1,2,2}';

Рисунок 1.4 — Пример поискового запроса к денормализованным данным

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

Аналогичные поисковые задачи востребованы и в других предметных областях, например:

• информационные системы учебных заведений,

• системы сбора статистики,

• и т.п.

1.1.2 Задача текстового поиска по подстроке

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

Поиск подстроки является, пожалуй, наиболее распространенным и востребованным среди множества других задач поиска текстовой информации, таких как точный поиск введенной строки, поиск смысловой информации внутри проиндексированных текстов, задачи нечеткого поиска [53,64] и многих других.

Текстовые данные занимают огромную часть накопленной на данный момент информации: персональные данные людей, содержимое web-сайтов, различная справочная информация, техническая документация и пр. Поэтому необходимость быстрого поиска текстовой информации сложно переоценить. В результате по этой теме написано много научных трудов [14,16,21,32] и разработано много способов поиска. Однако существенная часть имеющихся на данный момент подходов обладают определенными недостатками при индексации текста для поиска подстроки.

Современные СУБД поддерживают целый ряд способов поиска подстроки: использование регулярных выражений [46,57], специальных функций и операторов и др. Примеры SQL-запросов согласно стандарту [61] выглядят следующим образом:

• select * from texttable where textfld like '%substring%';

• select * from texttable where substring(textfld from 5 for 9) like 'substring';

А, например, в диалекте языка SQL, который используется в свободно распространяемой СУБД PostgreSQL, имеется оператор «~» [65]. Пример SQL-запроса на поиск подстроки с его использованием выглядит следующим образом:

• select * from texttable where textfld ~ '.*substring.*';

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

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

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

Полнотекстовый поиск

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

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

Примером таких индексов, ориентированных на слова естественного языка, а не символьные последовательности, может служить модуль tsearch2 для СУБД PostgreSQL [18]. Таким образом, разработанный индекс на основе R-деревьев, применительно к полнотекстовому поиску, может быть успешно применен в модуле tsearch2 к PostgreSQL, а также для решения широкого круга других прикладных задач.

Список литературы диссертационного исследования кандидат наук Чернов, Андрей Фёдорович, 2014 год

СПИСОК ЛИТЕРАТУРЫ

1. Чернов, А.Ф. Ускорение поиска в индексах на основе R-деревьев // Программные продукты и системы, 2012. №2 (98), С. 46 - 50.

2. Чернов, А.Ф., Андрианов И.А. Оптимизация разбиения данных в индексах на основе R-деревьев // Системы управления и информационные технологии, 2011. №4 (46), С. 18 - 22.

3. Чернов, А.Ф. Модификация индексов на основе R-деревьев для ускорения поиска // Информационные системы и технологии, 2011. №6 (68), С. 10 - 18.

4. Андрианов, И.А. Индексирование и поиск в последовательностях для больших баз данных: монография / И.А. Андрианов, А.Ф. Чернов. - Вологда, ВоГУ, 2013. -165 с.

5. Чернов, А.Ф. Сравнение обобщенных методов доступа к данным на основе GIST и GIN индексов / А.Ф. Чернов // Вузовская наука региону: материалы седьмой Всерос. науч.-техн. конф. В 2-х т., г. Вологда, 27 февраля 2009 г. -Вологда, 2009.-Т. 1. - С. 103 - 105.

6. Чернов, А.Ф. Ускорение поиска пространственных данных с использованием индексов на основе R-деревьев / А.Ф. Чернов // Молодые исследователи -регионам: материалы Всерос. науч. конф. студентов и аспирантов. В 2-х т., г. Вологда, 16-18 апреля 2009 г. - Вологда, 2009. - Т. 1. - С. 110 - 111.

7. Чернов, А.Ф. Использование сигнатур переменной длины в индексах на основе R-деревьев / А.Ф. Чернов // материалы III ежегод. смотров-сессий аспирантов и молодых ученых по отраслям наук: в 2-х т., г. Вологда, 18-19 ноября 2009 г. -Вологда, 2009. - Т. 2.: Экономические науки. - С. 264 - 268.

8. Чернов, А.Ф. Модификация сигнатур в индексах на основе R-деревьев / А.Ф. Чернов // Молодые исследователи - регионам: материалы Всерос. науч. конф. В 2-хт, г. Вологда, 22-23 апреля 2010 г. - Вологда, 2010.-Т. 1.-С. 149- 151.

9. Чернов, А.Ф. Ускорение поиска в индексах на основе R-деревьев с помощью разбиения индексируемых данных / А.Ф. Чернов // материалы IV ежегод. смотров-сессий аспирантов и молодых ученых по отраслям наук: Технические

науки. Экономические науки., г. Вологда, 15-16 декабря 2010 г. - Вологда, 2010. -С. 79 - 84.

10. Чернов, А.Ф. Оптимизация использования разбиения данных для ускорения поиска в индексах на основе R-деревьев / А.Ф. Чернов // Молодые исследователи - регионам: материалы Всерос. науч. конф. В 2-х т., г. Вологда, 21-22 апреля 2011 г.-Вологда, 2011.-Т. 1.-С. 109-111.

11. Чернов, А.Ф. Математический анализ эффективности поиска с использованием индексов на основе R-деревьев / А.Ф. Чернов // Автоматизация и энергосбережение машиностроительного и металлургического производств, технология и надежность машин, приборов и оборудования: материалы седьмой Междунар. науч.-техн. конф., г. Вологда, 13-15 марта 2012 г. - Вологда, 2012. - С. 352- 355.

12. Чернов, А.Ф. Доработка разбиения данных в индексах на основе R-деревьев для достижения универсальности / А.Ф. Чернов // Вопросы образования и науки в XXI веке: материалы Междунар. науч.-практ. конф. В 11ч., г. Тамбов, 29 апреля 2013 г.-Тамбов, 2013.-Ч. 11. - С. 116 - 119.

13. Чернов, А.Ф. Оптимизация размера сигнатур GIST индекса в СУБД PostgreSQL / А.Ф. Чернов // Современное общество, образование и наука: материалы Междунар. науч.-практ. конф. В 5 ч., г. Тамбов, 31 июля 2013 г. -Тамбов, 2013. - Ч. 4. - С. 140 - 142.

14. Айткулов П.Г. Исследование и разработка методов и алгоритмов обработки символьных массивов в базах данных / П.Г. Айткулов; дис. ... канд. техн. наук. -Москва: Институт проблем управления им. В. А. Трапезникова РАН, 2010. - 97 с.

15. Андерсон, Дж. Дискретная математика и комбинаторика / Дж. Андерсон; пер. с англ. - М.: Изд-во «Вильяме», 2004. - 960 с.

16. Андрианов И.А. Анализ и разработка способов индексирования текстов на основе обобщенных и неплотных суффиксных деревьев / И.А. Андрианов; дис. ... канд. техн. наук. - СПб.: Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина), 2005. -138 с.

17. Бартунов, О. С. Специализированные типы данных для цифровых библиотек / О. С. Бартунов // http://www.sai.msu.su/~megera/postgres/talks/RCDL2007.oleg.pdf

18. Бартунов, О.С., Сигаев Т.Г. Tsearch2 - full text extension for PostgreSQL / O.C. Бартунов, Т.Г. Сигаев // http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/

19. Бартунов, О.С., Сигаев, Т.Г. Научная сеть: алгоритмы и структуры данных / О.С. Бартунов, Т.Г. Сигаев // http://www.sai.msu.su/~megera/postgres/gist/doc/algo.shtml

20. Бартунов, О.С., Сигаев, Т.Г. Написание расширений для PostgreSQL с использованием GiST / О.С. Бартунов, Т.Г. Сигаев //

http ://www. sai.msu. su/~megera/postgres/talks/gist_tutorial.html

21. Бойцов JI.M. Синтез системы автоматической коррекции, индексации и поиска текстовой информации / Л.М. Бойцов; дис. ... канд. техн. наук. - М.: Московская академия рынка труда и информационных технологий, 2003. - 144 с.

22. Гречкосий, Г. Индексы. Теоретические основы. / Г. Гречкосий // http://www.sql.ru/articles/mssql/03013101 indexes. shtml#4

23. Еманов, Д. Firebird: методы доступа к данным / Д. Еманов // http://www.ibase.rU/devinfo/dataaccesspaths.htm#root

24. Кантор, И. Б, Б+ и Б++ деревья / И. Кантор // http://algolist.ncstu.ru/ds/s_btr.php

25. Кантор, И Хеш-таблицы / И. Кантор // http://algolist.manual.ru/ds/s_has.php

26. Каратаев, Е. Битмап индекс (bitmap index) / Е. Каратаев // http://karataev.nm.ru/ind/bitmap.html

27. Каратаев, Е. Хеш-индекс / Е. Каратаев // http://karataev.nm.ru/ind/hash.html

28. Ключаев, A.A., Матьяш, В.А., Щекин, C.B. Структуры и алгоритмы обработки данных: учебное пособие / A.A. Ключаев, В.А. Матьяш, C.B. Щекин - СПб.: СПбГУАП, 2003.- 172 с.

29. Кнут, Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы / Д. Кнут; пер. с англ. - М.: Изд-во "Вильяме", 2000. - 720 с.

30. Кнут, Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы / Д. Кнут; пер. с англ. - М.: Изд-во "Вильяме", 2000. - 500 с.

31. Кнут, Д. Искусство программирования для ЭВМ. Т.З. Сортировка и поиск / Д. Кнут; пер. с англ. - М.: Изд-во "Вильяме", 2000. - 832 с.

32. Колесов Д.А. Приближенный поиск в базах данных на основе метрических деревьев / Д.А. Колесов; дис. ... канд. техн. наук. - Казань: Казанский государственный технический университет им. А. Н. Туполева, 2006. — 142 с.

33. Колмогоров, А.Н., Журбенко, И.Г., Прохоров, A.B. Введение в теорию вероятностей. 2-е изд. / А.Н. Колмогоров, И.Г. Журбенко, A.B. Прохоров - М.: Физматлит, 1995. - 176 с.

34. Кормен, Т. Алгоритмы: построение и анализ. 3-е изд. / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн; пер. с англ. - М.: Изд-во "Вильяме", 2013. - 1328 с.

35. Крёнке Д. Теория и практика построения баз данных. 8-е изд. / Д. Крёнке -СПб.: Питер, 2003. - 800 с.

36. Кузнецов, С.Д. Методы сортировки и поиска / С.Д. Кузнецов // http://citfomm.ru/programming/theory/sorting/sortingl.shtml

37. Льюис, Д. Понимание индексов на основе битовых карт / Д. Льюис // http://www.s-networks.ru/index-674.htm

38. Льюис, Д. Разбираемся с индексами на основе битовых карт / Д. Льюис // http ://citforum.ru/database/oracle/bitmap_index/

39. Малайка, С., Никола М. Пересмотр взглядов на нормализацию данных: Часть

1. История бизнес-записей / С. Малайка, М. Никола // https://www.ibm.com/developerworks/ru/library/dm-l 112normalization/

40. Малайка, С., Никола М. Пересмотр взглядов на нормализацию данных: Часть

2. Бизнес-записи в 21 веке / С. Малайка, М. Никола // https://www.ibm.com/developerworks/ru/library/dm-120 lnormalizationpart2/

41. Райордан, Р. Основы реляционных баз данных / Р. Райордан; Пер. с англ. - М.: Издательско-торговый дом «Русская Редакция», 2001. - 384 с.

42. Седжвик, Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск. Часть 1-4 / Р. Седжвик: пер. с англ. - К.: Издательство «ДиаСофт», 2002 - 688.

43. Скворцов, А.В. Глобальные алгоритмы построения R-деревьев / А.В. Скворцов - Томск: Томский государственный университет, 1999. - 17 с.

44. Страуструп, Б. Язык программирования С++. Специальное издание. / Бьерн Страуструп; пер. с англ. - СПб.: Невский диалект; Бином, 2004. - 1104 с.

45. Уорсли, Дж. PostgreSQL. Для профессионалов (+CD-ROM) / Дж. Уорсли, Дж. Дрейк; Пер с англ. - СПб.: Питер, 2003. - 496 с.

46. Фридл, Дж. Регулярные выражения. 2-е изд. / Дж. Фридл. - СПб.: Питер, 2003. - 464 с.

47. Холл, М. Комбинаторика / М. Холл; пер. с англ. С.А. Широковой - М.: Изд-во «Мир», 1970. - 424 с.

48. Хусаинов, Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си / Б.С. Хусаинов - М: "Финансы и статистика", 2004. - 464 с.

49. Antognini, С. Bloom Filters / С. Antognini // Trivadis AG, Ziirich, Switzerland. -2008.

50. Arge, L. The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree / L. Arge, M. De Berg, H. Haverkort, K. Yi // ACM Transactions on Algorithms Vol. 4.-2008. - P. 165-194.

51. Bloom, Burton H. Space/time trade-offs in hash coding allowable errors / Burton H. Bloom // Communications of the ACM Vol. 13. - 1970. - P. 422-426.

52. Blumer, A. Complete inverted files for efficient text retrieval and analysis / A. Blumer, J. Blumer, D. Haussler, R. McConnell, D. Ehrenfeucht // J. ACM. - 1987. - P. 578-595.

53. Boytsov, L. Indexing methods for approximate dictionary searching: Comparative analysis / L. Boytsov // ACM Journal on Experimental Algorithmics Vol. 16. - 2011. -91 p.

54. Date, C. J. An Introduction to Database Systems, 8th Edition. / C.J. Date // Addison-Wesley Longman, ISBN 0-321-19784-4. - 1999.

55. Finkel, Raphael A. Quad Trees: A Data Structure for Retrieval on Composite Keys / Raphael A. Finkel, Jon Louis Bentley // Acta Informatica Vol. 4. - 1974. - P. 1-9.

56. Garcia, Y.J. A greedy algorithm for bulk loading R-trees. / Y.J. Garcia, M.A. Lopez, S.T. Leutenegger // Proc. 6th ACM Symposium on Advances in GIS. - 1998. - P. 163164.

57. Gennick, J. Oracle regular expressions pocket reference / J. Gennick, P. Linsley // O'Reilly.-2003.-64 p.

58. Guttman, A. R-trees: A Dynamic Index Structure For Spatial Searching / A. Guttman // Proc. ACM SIGMOD Int. Conf. on Management of Data. - 1984. - P. 47-57.

59. Hellerstein, Joseph M. Generalized search trees for database systems / Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer // Morgan Kaufmann Publishers Inc. Morgan Kaufmann Series In Data Management Systems. Readings in database systems (3rd ed.).- 1998.-P. 101-112.

60. Hellerstein, Joseph M. The RD-tree: an index structure for sets / Joseph M. Hellerstein // University of Wisconsin at Madison. Technical Report №1252. -1994.

61. ISO/IEC 9075-1:2008. Information technology - Database languages - SQL - Part 1: Framework (SQL/Framework), 2008.

62. Kamel, I. Hilbert R-tree: An Improved R-tree using Fractals /1. Kamel, C. Faloutsos // Proc. 20th ACM Int. Conf. on Very Large Data Bases. - 1994. - P. 500-509.

63. Maab, M. Suffix Trees and their Applications / M. Maab // Technische Universität München. - 1999.

64. Manning, C., Schutze, H. Foundations of Statistical Natural Language Processing / C. Manning, H. Schutze // MIT Press. - 1999.

65. PostgreSQL documentation // http://www.postgresql.org/docs/

Приложение А (обязательное)

Алгоритм поиска фрагмента в последовательностях по М)-дереву

Алгоритм поиска приведен на рисунке А. 1.

Рисунок А. 1 - Алгоритм поиска фрагмента в последовательностях по КО-дереву