Содержание к диссертации
Введение
Глава 1 Направления решения задачи анализа данных 9
1.1. Классификация аналитических систем 9
1.2. Реализации интерактивного анализа данных (OLAP) 16
1.3. Алгоритмы агрегирования куба 21
1.4. Алгоритмы поиска частых наборов и ассоциативных правил 32
1.5. Эффективный просмотр ассоциативных правил 49
1.6. План работы и полученные результаты 50
Глава 2 Алгоритмы перестроек префиксного дерева для реализации интерактивного анализа данных, агрегирования куба и поиска частых наборов 52
2.1. Формальная постановка задач 52
2.2. Структура данных - префиксное дерево 59
2.3. Алгоритм выполнения запросов OLAP .> 66
2.4. Алгоритм агрегирования куба с помощью перестроек префиксного дерева .73
2.5. Алгоритм поиска частых наборов с помощью перестроек префиксного дерева 77
Глава 3 Организация просмотра ассоциативных правил 80
3.1. Меры правил 80
3.2. Алгоритмы поиска интересных ассоциативных правил 90
3.3. Внешний вид отчёта о просматриваемых правилах 91
3.4. Алгоритм интерактивного просмотра правил в виде сводной таблицы 92
Глава 4 Теоретический анализ алгоритмов 94
4.1. Задача о среднем числе разных элементов 94
4.2. Сложность задач 107
4.3. Объём префиксного дерева 109
4.4. Время построения префиксного дерева 111
4.5. Время подъёма уровня префиксного дерева 113
4.6. Время работы алгоритма интерактивного анализа данных 114
4.7. Время работы алгоритма агрегирования куба 118
4.8. Время работы алгоритмов поиска частых наборов 122
Глава 5 Экспериментальный анализ алгоритмов 127
5.1. Алгоритмы интерактивного анализа данных 127
5.2. Алгоритмы агрегирования куба 132
5.3. Алгоритмы поиска частых наборов 136
5.4. Меры интереса правил 141
Заключение 144
Список использованных источников
- Реализации интерактивного анализа данных (OLAP)
- Структура данных - префиксное дерево
- Алгоритмы поиска интересных ассоциативных правил
- Время построения префиксного дерева
Введение к работе
Актуальность темы.
Построение систем анализа данных является важным направлением развития информационных технологий. В последнее время в связи с ростом числа накопленных данных в организациях и необходимостью принятия обоснованных управленческих решений интерес к этому направлению растёт. С помощью систем анализа данных могут быть решены следующие задачи: сбор всех необходимых для анализа данных в одном месте с согласованием форматов и удалением ошибок, интерактивный просмотр этих данных аналитиком, автоматическое извлечение закономерностей из данных. Всё это позволяет в каждый момент времени иметь полную информацию об организации и эффективно принимать управляющие решения.
В литературе активно исследуются три основных технологии систем анализа данных: хранилища данных, оперативная аналитическая обработка данных (Online Analytical Processing, или сокращённо OLAP), интеллектуальный анализ данных (Data Mining).
Основным требованием к системам OLAP является скорость выполнения запросов, так как анализ должен проходить в интерактивном режиме. Предложенные в литературе алгоритмы OLAP основаны на дисковых структурах данных или структурах данных в оперативной памяти. Дисковые структуры данных являются медленными или вынуждены хранить практически полностью агрегированные кубы для достижения скорости, что приводит к большим расходам памяти. Структуры в оперативной памяти могут обрабатывать лишь небольшие объёмы данных. Предложенный в диссертации алгоритм перестроек префиксного дерева существенно уменьшает требования к объёму данных по сравнению с другими алгоритмами в оперативной памяти, вместе с тем сохраняя высокую скорость работы.
Если объёмы данных очень велики, то предагрегация может значительно ускорить выполнение запросов. Также агрегирование может применяться для
5 ответа на запросы пользователя с одновременным требованием просмотра многих агрегатных данных (например, при отображении сводной таблицы). Первые алгоритмы агрегирования куба основываются на существенном использовании диска и являются достаточно медленными. Алгоритмы MemoryCube и BUC компактно используют оперативную память для проведения вычислений, но их планы выполнения являются неоптимальными. Предложенный в диссертации алгоритм перестроек префиксного дерева предлагает более быстрое выполнение по сравнению с заявленными алгоритмами при тех же объёмах обрабатываемых данных.
Одним из наиболее популярных направлений интеллектуального анализа данных является поиск правил в данных. В большинстве алгоритмов поиска правил первым и наиболее трудоёмким шагом является поиск частых наборов. Предложенный в диссертации алгоритм перестроек префиксного дерева обладает минимальными требованиями к памяти среди остальных алгоритмов и может обрабатывать большие объёмы данных без выхода на диск, что позволяет ускорить вычисления.
Проблема просмотра найденных ассоциативных правил является актуальной из-за большого количества обычно получаемых правил. В литературе были предложены две основных группы методов: отсечение по мерам интереса и синтаксические ограничения. Среди мер интереса в основном рассматривались меры, не учитывающие состава левой части правила. В работе предложен ряд мер, учитывающих состав левой части правила. В области синтаксических ограничений предполагалось, что пользователь задаёт их заранее, а затем просматривает все полученные правила. Недостатком является долгое ожидание результата. В диссертации предложен интерактивный просмотр ассоциативных правил в виде сводной таблицы.
Цели работы.
Основными целями диссертационной работы являются:
1. Разработка эффективных алгоритмов реализации интерактивного анализа
данных, автоматического поиска частых наборов и правил в данных,
основанных на использовании префиксного дерева.
Разработка алгоритмов удобного просмотра извлечённых правил.
Анализ разработанных алгоритмов.
Методы исследования.
В работе использовались методы теории структур данных и баз данных, комбинаторики, теории графов, теории вероятностей и математической статистики, алгебры, теории множеств. Экспериментальный анализ проводился с помощью компьютерного моделирования.
Научная новизна полученных результатов.
Предложена математическая модель в виде префиксного дерева для хранения данных при интерактивном анализе данных и поиске закономерностей. Разработаны алгоритмы выполнения запросов интерактивного анализа данных, вычисления всех агрегатных данных, поиска частых наборов с помощью перестроек префиксного дерева. Получены теоретические оценки эффективности разработанных алгоритмов в лучшем, худшем и среднем случаях. Введено несколько мер ценности ассоциативных правил, учитывающих их специфику, и разработан алгоритм поиска ассоциативных правил с учётом этих мер. Предложен способ интерактивного просмотра ассоциативных правил на сводной таблице и разработан алгоритм выполнения соответствующих запросов с помощью перестроек префиксного дерева.
Практическая значимость исследования.
Реализации разработанных алгоритмов могут быть использованы для проведения эффективного анализа данных в любых учреждениях, где имеются базы данных и есть накопленные данные.
Разработанный алгоритм интерактивного анализа данных внедрён в автоматизированной информационной системе "Консул ЗУ" в МИД РФ.
7 Апробация работы.
Основные результаты работы докладывались, обсуждались и получили одобрение специалистов на следующих конференциях:
XLVIII и XLIX научных конференциях Московского физико-технического института (государственного университета), (Долгопрудный, 2005,2006)
XIII международной научной конференции студентов, аспирантов и молодых учёных "Ломоносов", (Москва, МГУ, 2006),
а также на научных семинарах кафедры управляющих и информационных систем МФТИ и 3500 отделения ГосНИИ авиационных систем в 2002-2006 гг.
Публикации.
Основные положения работы отражены в публикациях [1-6]. Краткое содержание работы.
В главе 1 проводится обзор основных направлений решения задачи анализа данных. Рассмотрено положение систем анализа данных среди информационных систем и их классификация по способу хранения данных, способу анализа данных и степени участия человека в анализе данных. Поставлены основные задачи диссертации: реализация ответов на запросы интерактивного анализа данных (OLAP), агрегирование куба, поиск частых наборов и ассоциативных правил, эффективный просмотр ассоциативных правил. Для каждой задачи проведён обзор существующих подходов к решению.
В главе 2 рассматриваются алгоритмы решения задач на основе перестроек префиксного дерева. Введены формальные определения анализируемых данных и постановки задач ответов на запросы интерактивного анализа данных, агрегирования куба, поиска частых наборов. Дано определение префиксного дерева, процедуры заполнения и пополнения по заданной базе данных, алгоритм перестройки уровней дерева. Описаны алгоритмы ответов на запросы интерактивного анализа данных, агрегирования куба, поиска частых наборов, основанные на перестройках префиксного дерева.
В главе 3 рассматриваются подходы к обеспечению эффективного просмотра ассоциативных правил. Основная проблема заключается в большом количестве получаемых правил. Два основных подхода к решению этой проблемы: отсечение правил по мерам интереса и с помощью синтаксических ограничений. Рассмотрена классификация мер правил. Введены меры интереса, учитывающие состав левой части правила. Для них разработан алгоритм поиска интересных правил для заданного порога интереса. Рассмотрены основные способы отображения правил. Предложен способ интерактивного просмотра правил в виде сводной таблицы и соответствующий алгоритм выполнения запросов и отображения, основанный на перестройках префиксного дерева.
В главе 4 проводится теоретический анализ разработанных алгоритмов. Решена вспомогательная задача о среднем числе разных значений и среднем числе разных частых значений при заданном пороге частоты в выборке из конечного множества. На основе этой задачи получены оценки сложности решаемых задач, включая объём исходных данных, запрашиваемых данных, частых наборов. Подсчитаны объём префиксного дерева, время построения по базе данных, время подъёма уровня в лучшем, худшем и среднем случаях. Вычислено время работы для алгоритмов агрегирования куба и поиска частых наборов.
В главе 5 проводится экспериментальный анализ разработанных алгоритмов для выполнения запросов интерактивного анализа данных, агрегирования куба и поиска частых наборов. При выполнении запросов интерактивного анализа данных производится сравнение с алгоритмом, основанным на хранении в виде таблицы и ответов на запросы с помощью сортировок. Сравнение производится по времени заполнения, объёму занимаемой памяти и скорости ответов на запросы. При агрегировании куба производится сравнение с алгоритмом MemoryCube. При поиске частых наборов производится сравнение четырёх предложенных алгоритмов с алгоритмами Apriori и FP-Growth.
В заключении приведены основные результаты работы.
Реализации интерактивного анализа данных (OLAP)
Различные подходы к реализации программ OLAP обсуждаются в [7, 11, 14, 15, 23, 24, 26-29, 31, 34, 37, 46, 60, 61, 65, 71, 73, 74, 76, 79, 85, 86, 90, 92, 101]. Два наиболее популярных метода - это реляционный OLAP (ROLAP) и многомерный OLAP (MOLAP). Кроме того, существует множество индексных структур, которые могут применяться как для ускорения программ ROLAP, так и самостоятельно. Частичная материализация агрегатных данных используется для ускорения выполнения запросов. Хранение данных во время работы программы может осуществляться на диске или в оперативной памяти. Рассмотрим вышеперечисленные варианты подробнее. ROLAP.
Данные хранятся в виде набора таблиц в реляционной базе данных. Сформулированные пользователем запросы к данным переводятся на язык SQL и передаются базе данных. Полученные результаты отображаются в виде сводной таблицы.
Таблицы базы данных для приложений OLAP обычно строятся в виде схемы звезда. Она содержит таблицу фактов, содержащую коды измерений и значения показателей, и по одной таблице измерений для каждого измерения, содержащих конкретные значения данного измерения.
Выполнение запросов к базе данных содержит две основных части: 1. Выбор строк таблицы фактов, удовлетворяющих ограничениям по измерениям. 2. Агрегация значений показателя по выбранным отображаемым измерениям.
Выбор строк, удовлетворяющих ограничениям, может быть ускорен при использовании индексов. Агрегация может быть ускорена за счёт предварительного вычисления и хранения всех или части агрегатных данных.
MOLAP.
Данные хранятся в виде многомерного массива. Он реализуется в виде массива ячеек, хранящих значения показателя. Информация об измерениях закодирована в сдвигах массива. В приложениях OLAP массив является сильно разреженным, что приводит к неоправданным затратам памяти. Поэтому массив хранится в сжатом виде в виде множества пар (сдвиг, значение). Сжатый массив занимает меньше места, чем таблица, так как не нужно хранить значения измерений.
Выполнение запросов осуществляется сканированием всех ячеек сжатого массива и агрегированием ячеек, удовлетворяющих ограничениям, в результирующий массив. При наличии ограничений число сканируемых ячеек массива может быть уменьшено при сегментации массива, то есть разбиении на подмассивы. Каждый подмассив имеет столько же размерностей, как и основной массив. Если какой-либо подмассив не может содержать ячеек, удовлетворяющих ограничениям, то его ячейки не сканируются.
Индексы.
Индексные структуры могут применяться к отдельным столбцам таблицы фактов для быстрой выборки значений конкретного измерения или заменять таблицу фактов, индексируя все измерения. Рассмотрим основные индексы.
1. Многомерный массив.
Является наиболее естественным индексом для многомерной модели OLAP в случае плотного куба. Но кубы в приложениях OLAP являются в основном сильно разреженными, поэтому польза от индексирования многомерными массивами пропадает. Они могут применяться локально, если какой-то подкуб является плотным.
2. Инвертированные списки и битовые индексы.
Исходная таблица фактов хранится в виде множества строк, содержащих значения показателя и ссылки на значения измерений. На ту же самую таблицу можно взглянуть под другим углом, со стороны столбцов. В этом случае для каждого значения каждого измерения будет храниться список номеров таблицы фактов, содержащих данное значение данного измерения. Значения показателя хранятся в таблице. Обработка запросов с ограничениями производится следующим образом. Все списки ограничивающих значений всех измерений пересекаются, в результате чего получается список номеров таблицы фактов, удовлетворяющих ограничениям. Агрегация производится только по ним.
Битовые индексы являются способом реализации инвертированных списков. Каждый такой список представляется в виде битовой строки. Длина строки равна числу строк таблицы фактов. Значение в позиции битовой строки равно 1, если соответствующая строка таблицы фактов содержит данное значение измерения, и О в противном случае.
Структура данных - префиксное дерево
Запрос для полного куба и для отчёта с промежуточными итогами состоит из следующих частей. Вначале задаются отображаемые измерения. Они будут составлять результирующий куб или отчёт с промежуточными итогами. Затем задаются ограничения для каждого измерения в виде подмножеств значений. Для сводной таблицы множество отображаемых измерений делится на две части: отображаемые по строкам и отображаемые по столбцам измерения.
Результатом выполнения запросов являются куб, отчёт с промежуточными итогами или сводная таблица соответственно. Их измерения соответствуют заданным в запросе ограничивающим подмножествам для каждого измерения. Значения показателя - это агрегированные по всем неотображаемым измерениям с учётом ограничений значения показателя исходного куба данных. Определение. Пусть I - конечное множество элементов. База транзакций - это множество D={ttcl,t 0}.
База транзакций представляет собой набор транзакций, каждая из которых представляет собой подмножество элементов. База транзакций соответствует базе данных, в которой каждому элементу соответствует бинарный атрибут, а каждой транзакции - строка. Значение атрибута для строки равно 1, если элемент содержится в транзакции, и нулю в противном случае.
Определение. Ассоциативное правило для базы транзакций - это импликация вида X = Y, где X с I, Y с I и X n Y = 0. Ассоциативное правило для таблицы - это импликация вида Х= У,где X={dl,...,drdleDil,...,dreDir},Y6Dir4-l,{il,...,iH-l}c{l,...,m}. X называется условием правила, a Y - следствием. Ассоциативное правило представляет собой связь между элементами в базе транзакций или значениями измерений в базе данных. Оно показывает, что из наличия в строке элементов левой части правила следует наличие элемента правой части. В диссертации решаются следующие задачи. Задача 1. Ответы на запросы интерактивного анализа данных. Заданы база данных DB, запрос Q. Получить отчёт с промежуточными итогами, сводную таблицу или куб, соответствующие запросу. Задача 2. Агрегирование куба. Задана база DB. Получить все значения агрегированного куба С . Задача 3. Поиск частых наборов. Заданы база данных DB и порог частоты s. Получить все значения агрегированного куба С , большие или равные s.
Структура данных - префиксное дерево
Префиксное дерево содержит агрегатную информацию для одного или более атрибутов по набору записей таблицы.
Определение. Префиксное дерево - это ориентированное дерево, для которого 1. Каждый узел содержит метку и число. 2. Метка корня - null. 3. Метки дочерних узлов любого узла различны. 4. Показатели внутренних узлов и корня - сумма показателей дочерних вершин. 5. Все листья располагаются на одном уровне.
Пусть исходный набор данных задан в виде таблицы R со столбцами Db ..., Dm, М. Здесь Db ..., Dm - конечные множества элементов, называемые измерениями, М - множество чисел, натуральных или действительных, называемое показателем.
Префиксное дерево для R - это префиксное дерево, для которого 1. Высота дерева т+1. 2. Метки на каждом уровне - это элементы одного измерения. 3. Существует взаимно однозначное соответствие между уникальными записями таблицы и объединением меток на путях дерева от корня к листьям. 4. Показатели в листьях - это суммарные значения для каждой уникальной записи исходной таблицы.
Алгоритмы поиска интересных ассоциативных правил
В общем случае алгоритм вычисления интересных правил на основе порогов для поддержки, доверия и интереса, работает следующим образом. Производится вычисление всех правил, удовлетворяющих порогам поддержки и доверия. Для каждого такого правила вычисляется мера интереса и сравнивается с порогом. Для некоторых мер интереса этот алгоритм может быть улучшен.
Для эффективного извлечения правил с учётом меры Superlnterest разработан следующий специальный алгоритм, основанный на использовании свойства антимонотонности меры.
Вход. База данных или транзакций, пороги поддержки, доверия и интереса. Выход. Множество правил с соответствующими значениями поддержки, доверия и интереса, удовлетворяющими заданным порогам. Алгоритм.
1. Находим все частые наборы при заданном пороге поддержки одним из алгоритмов поиска частых наборов.
2. Извлекаем все правила из наборов и вычисляем их доверия. При сохранении правила группируются по одинаковым правым частям.
3. Для каждой группы правил с одинаковой правой частью выполняем
3.1. Строим префиксное дерево левых частей с узлами состава: доверие, поддержка, интерес, максимальное доверие. В вершину заносим доверие Р(Ь), максимальное доверие Р(Ь) и интерес 1.
3.2. Обходим префиксное дерево в ширину. Для каждого узла ищем родителей (узлы с исключением одного элемента) и считаем по ним максимальное доверие. Присваиваем значение интереса частному своего доверия к максимальному доверию. Присваиваем своё максимальное доверие максимуму максимального доверия родителей и своего доверия.
3.3. Обходим дерево и распечатываем правила с интересом, большим порога интереса, и доверием, большим порога доверия.
3.4. Очищаем дерево.
В работе предлагается способ просмотра ассоциативных правил, основанный на синтаксических ограничениях.
Для отображения ассоциативных правил может использоваться сводная таблица, при помощи которой просматривались ответы на запросы OLAP. По строкам таблицы располагаются условия правил, по столбцам - следствия, а в ячейках - соответствующие значения поддержки и доверия. Правила выбираются с помощью задания отображаемых по строкам и столбцам измерений и ограничений на их значения. При этом возможно обеспечить интерактивный анализ правил. Пользователь выбирает несколько измерений, отображаемых по строкам. Они будут отображать условия правил. Пользователь выбирает одно измерение для отображения по столбцам. Оно будет отображать следствия правил, В ячейках таблицы отображаются поддержка и доверие соответствующих правил. Отображаемые по строкам измерения могут просматриваться с промежуточными итогами, что позволяет просматривать изменение точности по сравнению с правилами-предками.
Просмотр ассоциативных правил в виде сводной таблицы обладает следующими преимуществами: 1. Просмотр осуществляется в интерактивном режиме. 2. Возможность формирования запросов пользователем на основе интуитивного интерфейса. 3. Возможность просмотра всех правил независимо от порогов поддержки или доверия без потери производительности.
Для обеспечения интерактивного просмотра правил в виде сводной таблицы разработан следующий алгоритм, основанный на перестройках префиксного дерева. Алгоритм выполнения запроса. Вход: префиксное дерево, запрос. Выход: сводная таблица с правилами. Алгоритм. 1. Отобразить названия отображаемых строковых и столбцовых измерений или значения всего при отсутствии отображаемых измерений по строкам или столбцам. 2, Привести префиксное дерево к порядку измерений, когда вначале идут измерения левых частей в заданном порядке, затем измерения правых частей в заданном порядке. 3. Перенумеровать значения левых измерений, удовлетворяющие ограничениям и порогу частоты. 4. Перенести измерения правых частей вверх дерева с сохранением порядка. 5. Отобразить удовлетворяющие ограничениям значения измерений правых частей по столбцам, а соответствующие им доверия правил с нулевой левой частью в нижней строке. 6. Перенумеровать значения правых измерений, удовлетворяющие ограничениям. 7. Для каждого измерения левой части в порядке следования в запросе выполнить: 7.1. Перенести измерение поверх измерений правых частей. 7.2. Отобразить доверия правил с левыми частями, соответствующими уже перенесённым вверх измерениям левых частей. 8. Отобразить в правом столбце значения частот, соответствующие частым значениям левых измерений.
Время построения префиксного дерева
Время построения префиксного дерева будет рассмотрено для двух вариантов алгоритма заполнения: последовательная вставка записей и вставка записей из отсортированной таблицы. Теорема. Пусть 1. m - число измерений, п - число записей, рь...,рт - число разных значений измерений 1,...,т. 2. Префиксное дерево строится в порядке измерений (1,...,ш) с помощью последовательной вставки записей.
Тогда 1. Количество добавлений узлов равно Nnodes. 2. Количество операций сложения равно (m+l)n-NnodeS 3. Количество операций сравнения равно O(mn) при использовании хеш-таблиц для хранения узлов, 0((pi+...+pm)n) при использовании списков. Здесь Nnodcs - число узлов префиксного дерева. Доказательство.
1. Каждый узел добавляется ровно один раз, поэтому количество добавлений узлов равно Nn0des.
2. При добавлении элемента новой строки есть две возможности. В первом случае такого узла ещё нет в префиксном дереве, поэтому создаётся новый узел с частотой этой строки. Во втором случае такой узел уже есть, и тогда нужно провести суммирование частоты строки и частоты узла. При добавлении каждой строки производится добавление для корня и для всех измерений, то есть всего (m+l)n добавлений. Из них NnodCS раз производится добавление узла, а в остальных случаях суммирование, поэтому число суммирований равно (m+l)n-Nnodes.
3. При вставке каждой записи в префиксное дерево для элемента каждого измерения этой записи производится поиск элемента среди дочерних узлов узла с элементом предыдущего измерения. Всего производится по п операций поиска для каждого измерения, а всего mn операций поиска. В случае использования хеш-таблиц каждая операция поиска требует 0(1) сравнений, то есть всего получается O(mn) сравнений. В случае использования списков операция поиска для измерения і требует 0(рі) сравнений, то есть всего получается 0((pi+...+pm)n) сравнений. Теорема. Пусть 1. m - число измерений, п - число записей, pi,...,pm - число разных значений измерений 1,...,т. 2. Префиксное дерево строится в порядке измерений (1,...,т) из отсортированной в том же порядке измерений таблицы. Тогда 1. Количество добавлений узлов равно Nnodes. 2. Количество операций сложения равно п-1. 3. Количество операций сравнения равно mn. Здесь Nnodes - число узлов префиксного дерева. Доказательство. 1. Каждый узел добавляется ровно один раз, поэтому количество добавлений узлов равно Nnodcs. 2. Количество сложений для уровня m равно n-Nnodes_m, Для остальных уровней і (i=0,...,m-l) равно NnodeS_i+i-NnodcsJ, где Nnodcsj - число узлов префиксного дерева на уровне і. Это следует из того, что вставка элемента на уровень і производится не для всех записей, а только для всех разных дочерних узлов этого элемента в дереве. Общее число сложений равно m-\ m Ц nodes_i + l nodes 0 + m nodes_ 1=0 m-\ m \ = 2-і"nodes і +1 2-і nodes i + m nodes i=0 /=0 m m-\ = 2-i nodes і 2-і"nodes i + m "nodes n (=1 i=0 = "nodes _m nodes _ 0 + n "nodes _m n Nn0des_o=l так как на этом уровне располагается только один корень.
3. Для каждой вставляемой записи осуществляется по одному сравнению для элемента каждого измерения с последним текущим элементом, чтобы решить, добавлять ли узел или проводить суммирование. Всего получается mn сравнений.
Теорема. Пусть 1. m - число измерений, п - число записей, pi,...,pm - число разных значений измерений 1,...,ш. 2. Префиксное дерево построено в порядке измерений (1,...,т). 3. Осуществляется подъём уровня і, іє {2,...,т}. Тогда 1. Число созданий узлов равно nb. 2. Число удалений узлов равно па. 3. Число сложений равно nab-nb. 4. Число сравнений равно O(nab) при использовании хеш-таблиц или списков для хранения узлов. Здесь па - число узлов префиксного дерева на уровне і-1 до подъёма уровня і, nb - число узлов префиксного дерева на уровне і-l после подъёма уровня і, nab - число узлов префиксного дерева на уровне і. Доказательство. 1. Алгоритм создаёт новые узлы для всех разных значений поднимаемого измерения на уровне і-l, число которых равно nb. 2. Алгоритм удаляет все старые узлы на уровне і-l, число которых равно па. 3. В процессе подъёма уровня обрабатывается nab узлов уровня і. Для каждого узла либо создаётся новый узел на уровне і-l, либо производится увеличение частоты ранее созданного узла с помощью сложения. Поэтому число сложений равно nab-nb. 4. Обозначим пО - число узлов на уровне і-2. В процессе подъёма уровня і операция выполняется отдельно для каждого узла] уровня і-2. Каждая такая задача сводится к слиянию na(j) множеств из общего числа nab(j) элементов. В случае использования хеш-таблиц слияние осуществляется за 0(nab(j)) сравнений. В случае использования упорядоченных списков слияние осуществляется за O(nab(j)logna(j)). Значение na(j) ограничено сверху числом элементов измерения і-l, то есть logna(j) logpi_b что является в большинстве случаев малой константой. Поэтому можно и в случае списков считать число сравнений равным O(nabQ). Просуммировав число сравнений по всем узлам j, получим, что общее число сравнений равно O(nab).
