Введение
Глава 1. Использование взаимно независимых разрядных преобразований на основе вертикальной обработки данных при выполнении операций сравнения для информационного поиска 36
1.1. Описание метода вертикальной обработки 36
1.2. Вертикальное сложение двоичных чисел в знакоразрядном коде 47
1.3. Взаимно независимая обработка разрядов для сравнения чисел 55
1.4. Поразрядно-параллельный способ сравнения слов строкового типа 61
1.5. Поиск по маске подстроки в строке на основе взаимно независимой обработки разрядов при выполнении сравнений 67
1.5.1. Поиск подстроки в строке с минимальной временной сложностью 69
1.6. Способы выделения старшего ненулевого разряда 72
1.6.1. Выделение старшего ненулевого разряда на основе сортировки подсчетом по матрице сравнений 73
1.6.2. Выделение старшего ненулевого разряда на основе логических операций 76
1.6.3. Минимизация временной сложности выделения старшего ненулевого разряда по аналогии с нормализацией двоичной мантиссы 78
1.7. Сравнение предложенного метода с известными аналогами 83
1.8. Выводы 85
Глава 2. Детерминированное построение декартова дерева с логарифмической временной сложностью для ускорения обработки данных 87
2.1. Предварительное описание декартова дерева 87
2.2. Построение декартова дерева с применением устойчивой адресной сортировки 88
2.3. Характеристика существующих комплексов реляционных структур данных 94
2.4. Сопоставление параллельного построения декартова дерева с построением в реляционной структуре данных Oracle Database 103
2.5. Сравнение временной сложности предложенного построения декартова дерева с известными алгоритмами 110
2.6. Выводы 113
Глава 3. Методы минимизации временной сложности построения двоичного дерева на основе устойчивой адресной сортировки 115
3.1. Построение двоичного дерева с логарифмическим числом шагов 115
3.1.1. Извлечение структурных закономерностей из произвольного расположения входных данных на основе сортировки 123
3.1.2. Последовательное построение двоичного дерева 126
3.2. Минимизация временной сложности построения двоичного дерева с применением взаимной независимости разрядных преобразований при сравнении элементов 128
3.3. Сравнение выполнения базовых операций с известными методами 130
3.4. Сравнение временной сложности построения двоичного дерева с известными алгоритмами 136
3.4.1. Сравнение предложенного построения двоичного дерева с известными алгоритмами 137
3.4.2. Сравнение оценок временной сложности максимально параллельного построения двоичного дерева с известными алгоритмами 143
3.4.3. Сравнение оценок временной сложности последовательного построения двоичного дерева с известными алгоритмами 145
3.5. Оценки ускорения с учетом взаимной независимости разрядных преобразований при выполнении операций сравнения 148
3.6. Выводы 152
Заключение 154
Список литературы 158
Приложения 173
