В информатике , А слитое дерево представляет собой тип структуры данных дерева , которая реализует ассоциативный массив на ж битовые целые числа. При работе с набором из n пар ключ-значение он использует пространство O ( n ) и выполняет поиск за время O (log w n ) , что асимптотически быстрее, чем традиционное самобалансирующееся двоичное дерево поиска , а также лучше, чем дерево Ван Эмде Боаса для больших значений w. Эта скорость достигается за счет использования определенных операций с постоянным временем, которые могут быть выполнены с машинным словом . Деревья фьюжн были изобретены в 1990 году Майклом Фредманом и Дэном Уиллардом . [1]
Со времени выхода оригинальной статьи Фредмана и Уилларда 1990 года было сделано несколько успехов. В 1999 году [2] было показано, как реализовать деревья слияния в рамках модели вычислений, в которой все базовые операции алгоритма принадлежат AC 0 , модели сложности схемы, которая допускает операции сложения и побитовые логические операции, но запрещает операции умножения. используется в исходном алгоритме дерева слияния. В 1996 г. была предложена динамическая версия деревьев слияния с использованием хэш-таблиц [3], которая соответствовала ожидаемому времени выполнения O (log w n ) исходной структуры . Другая динамическая версия с использованием экспоненциального дерева была предложена в 2007 году [4], которая дает время выполнения в наихудшем случае O (log w n + log log n ) на операцию. Остается открытым, могут ли деревья динамического слияния достичь O (log w n ) за операцию с высокой вероятностью.
Как это работает
Дерево слияния - это, по сути, B-дерево с коэффициентом ветвления w 1/5 (также возможен любой малый показатель степени), что дает ему высоту O (log w n ) . Чтобы достичь желаемого времени выполнения обновлений и запросов, дерево слияния должно иметь возможность искать узел, содержащий до w 1/5 ключей за постоянное время. Это делается путем сжатия («зарисовки») ключей, так что все они могут уместиться в одно машинное слово, что, в свою очередь, позволяет проводить сравнения параллельно.
Эскиз
Эскиз - это метод, с помощью которого каждый w -битовый ключ в узле, содержащем k ключей, сжимается только до k - 1 бит. Каждый ключ x можно рассматривать как путь в полном двоичном дереве высоты w, начинающийся с корня и заканчивающийся на листе, соответствующем x . Чтобы различать два пути, достаточно взглянуть на их точку ветвления (первый бит, в котором два ключа различаются). Все k путей вместе имеют k - 1 точек ветвления, поэтому для различения любых двух из k ключей требуется не более k - 1 бит .
Важным свойством функции эскиза является то, что она сохраняет порядок клавиш. То есть sketch ( x )
Аппроксимация эскиза
Если местоположения битов скетча b 1 < b 2 <··· < b r , то скетч ключа x w -1 ··· x 1 x 0 является r- битным целым числом.
Используя только стандартные операции со словами, например, в языке программирования C , трудно напрямую вычислить эскиз ключа за постоянное время. Вместо этого биты эскиза могут быть упакованы в диапазон размера не более r 4 , используя побитовое И и умножение. Побитовая операция И служит для очистки ключа от всех битов, не относящихся к эскизу, в то время как умножение сдвигает биты эскиза в небольшой диапазон. Как и в «идеальном» эскизе, в приблизительном эскизе сохраняется порядок клавиш.
Для определения правильной константы умножения требуется некоторая предварительная обработка. Каждый бит эскиза в позиции b i будет сдвинут на b i + m i посредством умножения на m =2 м я . Чтобы приблизительный эскиз работал, должны соблюдаться следующие три свойства:
- b i + m j различны для всех пар ( i , j ). Это гарантирует, что биты скетча не будут повреждены умножением.
- b i + m i - строго возрастающая функция от i . То есть порядок битов эскиза сохраняется.
- ( б г + м г ) - ( б 1 + м 1 ) ≤ г 4 . То есть биты эскиза упакованы в диапазоне размеров не более r 4 .
Индуктивный аргумент показывает, как можно построить m i . Пусть m 1 = w - b 1 . Предположим, что 1 < t ≤ r и что m 1 , m 2 ... m t-1 уже выбраны. Затем выберите наименьшее целое число m t такое, чтобы выполнялись оба свойства (1) и (2). Свойство (1) требует, чтобы m t ≠ b i - b j + m l для всех 1 ≤ i , j ≤ r и 1 ≤ l ≤ t -1. Таким образом, существует менее чем tr 2 ≤ r 3 значений, которых следует избегать m t . Поскольку m t выбрано минимальным, ( b t + m t ) ≤ ( b t -1 + m t -1 ) + r 3 . Отсюда следует свойство (3).
Таким образом, приблизительный эскиз рассчитывается следующим образом:
- Замаскируйте все, кроме фрагментов эскиза, с помощью побитового AND.
- Умножьте ключ на заданную константу m . На самом деле для этой операции требуются два машинных слова, но все же это можно сделать за постоянное время.
- Замаскируйте все, кроме сдвинутых фрагментов эскиза. Теперь они содержатся в непрерывном блоке не более r 4 < w 4/5 бит.
Параллельное сравнение
Целью сжатия, достигаемого с помощью наброска, является сохранение всех ключей в одном w- битном слове. Пусть эскиз узла узла будет битовой строкой
- 1
sketch
( х 1 ) 1sketch
( х 2 ) ... 1sketch
( х k )
Можно предположить, что функция скетча использует ровно b ≤ r 4 бита. Тогда каждый блок использует 1 + b ≤ w 4/5 бит, и, поскольку k ≤ w 1/5 , общее количество битов в эскизе узла не превышает w .
Небольшое обозначение в сторону: для битовой строки s и неотрицательного целого числа m пусть s m обозначает конкатенацию s с самим собой m раз. Если t также является битовой строкой, st обозначает конкатенацию t и s .
Скетч узла позволяет искать ключи для любого b -битного целого числа y . Пусть z = (0 y ) k , которое можно вычислить за постоянное время (умножьте y на константу (0 b 1) k ). Обратите внимание, что 1 sketch
( x i ) - 0 y всегда положительно, но сохраняет свою ведущую единицу тогда и только тогда, когда sketch
( x i ) ≥ y . Таким образом, мы можем вычислить наименьший индекс i такой, что sketch
( x i ) ≥ y, следующим образом:
- Вычтите z из эскиза узла.
- Возьмите поразрядное И разности и константу (10 b ) k . Это очищает все, кроме ведущего бита каждого блока.
- Найдите самый значимый бит результата.
- Вычислить i , используя тот факт, что ведущий бит i -го блока имеет индекс i ( b +1).
Рисование
Для произвольного запроса q параллельное сравнение вычисляет индекс i такой, что
sketch
( х я -1 ) ≤sketch
( д ) ≤sketch
( х я )
К сожалению, функция эскиза в целом не сохраняет порядок вне набора ключей, поэтому не обязательно, чтобы x i -1 ≤ q ≤ x i . Что верно, так это то, что среди всех ключей либо x i -1, либо x i имеет самый длинный общий префикс с q . Это связано с тем, что любой ключ y с более длинным общим префиксом с q также будет иметь больше битов эскиза, общих с q , и, следовательно, sketch
( y ) будет ближе к sketch
( q ), чем любой sketch
( x j ).
Длина самого длинного общего префикса между двумя w -битными целыми числами a и b может быть вычислена за постоянное время, найдя самый старший бит побитового XOR между a и b . Затем это можно использовать, чтобы замаскировать все, кроме самого длинного общего префикса.
Обратите внимание, что p точно определяет, где q ответвляется от набора ключей. Если следующий бит q равен 0, тогда преемник q содержится в поддереве p 1, а если следующий бит q равен 1, то предшественник q содержится в поддереве p 0. Это предполагает следующий алгоритм:
- Используйте параллельное сравнение, чтобы найти такой индекс i , что
sketch
( x i -1 ) ≤sketch
( q ) ≤sketch
( x i ). - Вычислите самый длинный общий префикс p для q и либо x i -1, либо x i (беря более длинный из двух).
- Пусть l -1 - длина самого длинного общего префикса p .
- Если l-й бит q равен 0, пусть e = p 10 w - l . Используйте параллельное сравнение для поиска преемника
sketch
( e ). Это фактический предшественник q . - Если l-й бит q равен 1, пусть e = p 01 w - l . Используйте параллельное сравнение для поиска предшественника
sketch
( e ). Это фактический преемник q .
- Если l-й бит q равен 0, пусть e = p 10 w - l . Используйте параллельное сравнение для поиска преемника
- Как только предшественник или преемник q найден, определяется точное положение q среди набора ключей.
Фьюжн хеширование
Применение деревьев слияния к хеш-таблицам было дано Уиллардом, который описывает структуру данных для хеширования, в которой хеш-таблица внешнего уровня с хеш-цепочкой объединена с деревом слияния, представляющим каждую хеш-цепочку. В хеш-цепочке в хеш-таблице с постоянным коэффициентом загрузки средний размер цепочки постоянен, но, кроме того, с большой вероятностью все цепочки имеют размер O (log n / log log n ) , где n - количество хешированных элементов. . Этот размер цепочки достаточно мал, чтобы дерево слияния могло обрабатывать поиск и обновления в нем за постоянное время для каждой операции. Поэтому время для всех операций в структуре данных с большой вероятностью постоянно. Точнее, с этой структурой данных для каждой обратной квазиполиномиальной вероятности p ( n ) = exp ((log n ) O (1) ) существует константа C такая, что вероятность того, что существует операция, превышающая время C, равна не более p ( n ) . [5]
Рекомендации
- ^ Фредман, ML ; Уиллард, Д.Е. (1990), «Взрыв через теоретический информационный барьер с помощью FUSION TREES», Материалы двадцать второго ежегодного симпозиума ACM по теории вычислений (STOC '90) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 1 -7, DOI : 10,1145 / 100216,100217 , ISBN 0-89791-361-2.
- ^ Андерссон, Арне; Милтерсен, Питер Бро; Thorup, Миккель (1999), "Fusion деревья могут быть реализованы с помощью AC 0 инструкции только" Теоретическая информатика , 215 (1-2): 337-344, DOI : 10.1016 / S0304-3975 (98) 00172-8 , MR 1678804.
- ^ Раман, Раджив (1996), «Приоритетные очереди: маленькие, монотонные и трансдихотомические», Четвертый ежегодный европейский симпозиум по алгоритмам (ESA '96), Барселона, Испания, 25–27 сентября 1996 г. , Lecture Notes in Computer Science, 1136 , Берлин:. Springer-Verlag, стр 121-137, DOI : 10.1007 / 3-540-61680-2_51 , МР 1469229.
- ^ Андерссон, Арне; Торуп, Миккель (2007), «Динамические упорядоченные множества с экспоненциальными деревьями поиска», Журнал ACM , 54 (3): A13, arXiv : cs / 0210006 , doi : 10.1145 / 1236457.1236460 , MR 2314255.
- ^ Уиллард, Дэн Э. (2000), «Исследование вычислительной геометрии, деревьев Ван Эмде Боаса и хеширования с точки зрения дерева слияния», SIAM Journal on Computing , 29 (3): 1030–1049, DOI : 10.1137 / S0097539797322425 , Руководство по ремонту 1740562.
Внешние ссылки
- MIT CS 6.897: Расширенные структуры данных: лекция 4, Fusion Trees , профессор Эрик Демейн (весна 2003 г.)
- MIT CS 6.897: Расширенные структуры данных: лекция 5, Дополнительные деревья слияния; самоорганизующиеся структуры данных, движение вперед, статическая оптимальность , профессор Эрик Демейн (весна 2003 г.)
- MIT CS 6.851: Расширенные структуры данных: лекция 13, примечания к Fusion Tree , профессор Эрик Демейн (весна 2007 г.)
- MIT CS 6.851: Расширенные структуры данных: лекция 12, примечания к Fusion Tree , профессор Эрик Демейн (весна 2012 г.)