Изменения

Перейти к: навигация, поиск

Сортировка Хана

221 байт убрано, 16:24, 21 июня 2012
Нет описания правки
'''Сортировка Хана (Yijie Han)''' {{---}} сложный алгоритм сортировки целых чисел со сложностью <tex>O(n \log\log n)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.
Данная статья писалась на основе брошюры Хана, посвященной этой сортировке. Изложение материала в данной статье идет примерно в том же порядке, в каком она предоставлена в работе Хана.
== Алгоритм ==
Алгоритм: Пусть целое число <tex>b \ge 0</tex> и пусть <tex>U = \{0, \ldots, 2^b - 1\}</tex>. Класс <tex>H_{b,s}</tex> хеш функций из <tex>U</tex> в <tex>\{0, \ldots, 2^s - 1\}</tex> определен как <tex>H_{b,s} = \{h_{a} \mid 0 < a < 2^b, a \equiv 1 (\bmod 2)\}</tex> и для всех <tex>x</tex> из <tex>U: h_{a}(x) = (ax</tex> <tex>\bmod</tex> <tex>2^b)</tex> <tex>div</tex> <tex>2^{b - s}</tex>.
Данный алгоритм базируется на <ib>лемме №1</ib>
Следует отметить, что несмотря на размер таблицы <tex>O(n^2)</tex>, потребность в памяти не превышает <tex>O(n)</tex> потому, что хеширование используется только для уменьшения количества бит в числе.
 
==Signature sorting==
В данной сортировке используется следующий алгоритм:
 
 
Предположим, что <tex>n</tex> чисел должны быть сортированы, и в каждом <tex>\log m</tex> бит. Рассматривается, что в каждом числе есть <tex>h</tex> сегментов, в каждом из которых <tex>\log (m/h)</tex> бит. Теперь применяем хеширование ко всем сегментам и получаем <tex>2h \log n</tex> бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке <tex>n</tex> чисел по <tex>m</tex> бит в каждом стала задачей по сортировке <tex>n</tex> чисел по <tex> \log (m/h)</tex> бит в каждом.
 
 
Так же, рассмотрим проблему последующего разделения. Пусть <tex>a_{1}</tex>, <tex>a_{2}</tex>, <tex>\ldots</tex>, <tex>a_{p}</tex> {{---}} <tex>p</tex> чисел и <tex>S</tex> {{---}} множество чисeл. Необходимо разделить <tex>S</tex> в <tex>p + 1</tex> наборов таких, что: <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < {<tex>a_{2}</tex>} < <tex>\ldots</tex> < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Т.к. используется signature sorting, до того как делать вышеописанное разделение, необходимо поделить биты в <tex>a_{i}</tex> на <tex>h</tex> сегментов и возьмем некоторые из них. Так же делим биты для каждого числа из <tex>S</tex> и оставим только один в каждом числе. По существу для каждого <tex>a_{i}</tex> берутся все <tex>h</tex> сегментов. Если соответствующие сегменты <tex>a_{i}</tex> и <tex>a_{j}</tex> совпадают, то нам понадобится только один. Сегменты, которые берутся для числа в <tex>S</tex>, {{---}} сегмент, который выделяется из <tex>a_{i}</tex>. Таким образом преобразуется начальная задачу о разделении <tex>n</tex> чисел в <tex>\log m</tex> бит в несколько задач на разделение с числами в <tex>\log (m/h)</tex> бит.
 
 
Пример:
 
<tex>a_{1}</tex> = 3, <tex>a_{2}</tex> = 5, <tex>a_{3}</tex> = 7, <tex>a_{4}</tex> = 10, S = <tex>\{1, 4, 6, 8, 9, 13, 14\}</tex>.
 
Делим числа на 2 сегмента. Для <tex>a_{1}</tex> получим верхний сегмент 0, нижний 3; <tex>a_{2}</tex> верхний 1, нижний 1; <tex>a_{3}</tex> верхний 1, нижний 3; <tex>a_{4}</tex> верхний 2, нижний 2. Для элементов из S получим: для 1: нижний 1 т.к. он выделяется из нижнего сегмента <tex>a_{1}</tex>; для 4 нижний 0; для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты 8, 9, 10 формируют 4 новые задачи на разделение.
==Сортировка n целых чисел в sqrt(n) наборов==
Постановка задачи и решение некоторых проблем:
 
Рассмотрим проблему сортировки <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> в <tex>\sqrt{n}</tex> наборов как во второй лемме. Предполагая, что в каждом контейнере <tex>k \log\log n \log m</tex> бит и хранит число в <tex>\log m</tex> бит. Поэтому неконсервативное преимущество <tex>k \log \log n</tex>. Так же предполагаем, что <tex>\log m \ge \log n \log\log n</tex>. Иначе можно использовать radix sort для сортировки за время <tex>O(n \log\log n)</tex> и линейную память. Делим <tex>\log m</tex> бит, используемых для представления каждого числа, в <tex>\log n</tex> блоков. Таким образом каждый блок содержит как минимум <tex>\log\log n</tex> бит. <tex>i</tex>-ый блок содержит с <tex>i \log m/ \log n</tex>-ого по <tex>((i + 1) \log m/ \log n - 1)</tex>-ый биты. Биты считаются с наименьшего бита начиная с нуля. Теперь у нас имеется <tex>2 \log n</tex>-уровневый алгоритм, который работает следующим образом:
 
На каждой стадии работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее м.ч.) потому, что каждое м.ч. теперь содержит только <tex>\log m/ \log n</tex> бит. Каждое число представлено и соотносится с м.ч., над которым работаем в данный момент. Положим, что нулевая стадия работает с самыми большим блоком (блок номер <tex>\log n - 1</tex>). Предполагаем, что биты этих м.ч. упакованы в <tex>n/ \log n</tex> контейнеров с <tex>\log n</tex> м.ч. упакованных в один контейнер. Пренебрегая временем, потраченным на на эту упаковку, считается, что она бесплатна. По третьей лемме находим медиану этих <tex>n</tex> м.ч. за время и память <tex>O(n/ \log n)</tex>. Пусть <tex>a</tex> это найденная медиана. Тогда <tex>n</tex> м.ч. могут быть разделены на не более чем три группы: <tex>S_{1}</tex>, <tex>S_{2}</tex> и <tex>S_{3}</tex>. <tex>S_{1}</tex> содержит м.ч. которые меньше <tex>a</tex>, <tex>S_{2}</tex> содержит м.ч. равные <tex>a</tex>, <tex>S_{3}</tex> содержит м.ч. большие <tex>a</tex>. Так же мощность <tex>S_{1}</tex> и <tex>S_{3} </tex>\le <tex>n/2</tex>. Мощность <tex>S_{2}</tex> может быть любой. Пусть <tex>S'_{2}</tex> это набор чисел, у которых наибольший блок находится в <tex>S_{2}</tex>. Тогда убираем <tex>\log m/ \log n</tex> бит (наибольший блок) из каждого числа из <tex>S'_{2}</tex> из дальнейшего рассмотрения. Таким образом после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения. Так как в каждом числе только <tex>\log n</tex> блоков, для каждого числа потребуется не более <tex>\log n</tex> стадий чтобы поместить его в набор половинного размера. За <tex>2 \log n</tex> стадий все числа будут отсортированы. Так как на каждой стадии работаем с <tex>n/ \log n</tex> контейнерами, то игнорируя время, необходимое на упаковку м.ч. в контейнеры и помещение м.ч. в нужный набор, затрачивается <tex>O(n)</tex> времени из-за <tex>2 \log n</tex> стадий.
 
Сложная часть алгоритма заключается в том, как поместить маленькие числа в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <tex>n</tex> чисел уже поделены в <tex>e</tex> наборов. Используем <tex>\log e</tex> битов чтобы сделать марки для каждого набора. Теперь хотелось бы использовать лемму шесть. Полный размер маркера для каждого контейнера должен быть <tex>\log n/2</tex>, и маркер использует <tex>\log e</tex> бит, количество маркеров <tex>g</tex> в каждом контейнере должно быть не более <tex>\log n/(2\log e)</tex>. В дальнейшем т.к. <tex>g = \log n/(2 \log e)</tex> м.ч. должны влезать в контейнер. Каждый контейнер содержит <tex>k \log\log n \log n</tex> блоков, каждое м.ч. может содержать <tex>O(k \log n/g) = O(k \log e)</tex> блоков. Заметим, что используем неконсервативное преимущество в <tex>\log\log n</tex> для использования леммы шесть. Поэтому предполагается, что <tex>\log n/(2 \log e)</tex> м.ч. в каждом из которых <tex>k \log e</tex> блоков битов числа упакованный в один контейнер. Для каждого м.ч. используется маркер из <tex>\log e</tex> бит, который показывает к какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в контейнеры как и м.ч. Так как каждый контейнер для маркеров содержит <tex>\log n/(2 \log e)</tex> маркеров, то для каждого контейнера требуется <tex>(\log n)/2</tex> бит. Таким образом лемма шесть может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <tex>O((n \log e)/ \log n)</tex> контейнеров то время необходимое для помещения м.ч. в их наборы потребуется <tex>O((n \log e)/ \log n)</tex> времени.
 
Стоит отметить, что процесс помещения нестабилен, т.к. основан на алгоритме из леммы шесть.
 
При таком помещении сразу возникает следующая проблемой.
 
Рассмотрим число <tex>a</tex>, которое является <tex>i</tex>-ым в наборе <tex>S</tex>. Рассмотрим блок <tex>a</tex> (назовем его <tex>a'</tex>), который является <tex>i</tex>-ым м.ч. в <tex>S</tex>. Когда используется вышеописанный метод перемещения нескольких следующих блоков <tex>a</tex> (назовем это <tex>a''</tex>) в <tex>S</tex>, <tex>a''</tex> просто перемещен на позицию в наборе <tex>S</tex>, но не обязательно на позицию <tex>i</tex> (где расположен <tex>a'</tex>). Если значение блока <tex>a'</tex> одинаково для всех чисел в <tex>S</tex>, то это не создаст проблемы потому, что блок одинаков вне зависимости от того в какое место в <tex>S</tex> помещен <tex>a''</tex>. Иначе у нас возникает проблема дальнейшей сортировки. Поэтому поступаем следующим образом: На каждой стадии числа в одном наборе работают на общем блоке, который назовем "текущий блок набора". Блоки, которые предшествуют текущему блоку содержат важные биты и идентичны для всех чисел в наборе. Когда помещаем больше бит в набор, помещаются последующие блоки вместе с текущим блоком в набор. Так вот, в вышеописанном процессе помещения предполагается, что самый значимый блок среди <tex>k \log e</tex> блоков это текущий блок. Таким образом после того, как помещены эти <tex>k \log e</tex> блоков в набор, удаляется изначальный текущий блок, потому, что известно, что эти <tex>k \log e</tex> блоков перемещены в правильный набор и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных <tex>k \log e</tex> блоках.
 
Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. Леммы четыре, пять и шесть расчитанны на не очень маленькие наборы. Но поскольку сортируется набор из <tex>n</tex> элементов в наборы размера <tex>\sqrt{n}</tex>, то проблем не должно быть.
 
Собственно алгоритм:
 
end.
 
==Собственно сортировка с использованием O(nloglogn) времени и памяти==
Для сортировки <tex>n</tex> целых чисел в диапазоне от {<tex>0, 1, \ldots, m - 1</tex>} предполагается, что используем контейнер длины <tex>O(\log (m + n))</tex> в нашем консервативном алгоритме. Далее всегда считается, что все числа упакованы в контейнеры одинаковой длины.
 
Берем <tex>1/e = 5</tex> для экспоненциального поискового дереве Андерссона. Поэтому у корня будет <tex>n^{1/5}</tex> детей и каждое ЭП-дерево в каждом ребенке будет иметь <tex>n^{4/5}</tex> листьев. В отличии от оригинального дерева, вставляется не один элемент за раз, а <tex>d^2</tex>, где <tex>d</tex> {{---}} количество детей узла дерева, где числа должны спуститься вниз. Алгоритм полностью опускает все <tex>d^2</tex> чисел на один уровень. В корне опускаются <tex>n^{2/5}</tex> чисел на следующий уровень. После того, как опустились все числа на следующий уровень и они успешно разделились на <tex>t_{1} = n^{1/5}</tex> наборов <tex>S_{1}, S_{2}, \ldots, S_{t_{1}}</tex>, в каждом из которых <tex>n^{4/5}</tex> чисел и <tex>S_{i} < S_{j}, i < j</tex>. Затем, берутся <tex>n^{(4/5)(2/5)}</tex> чисел из <tex>S_{i}</tex> и за раз и опускаются на следующий уровень ЭП-дерева. Это повторяется, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на <tex>t_{2} = n^{1/5}n^{4/25} = n^{9/25}</tex> наборов <tex>T_{1}, T_{2}, \ldots, T_{t_{2}}</tex> в каждом из которых <tex>n^{16/25}</tex> чисел, аналогичным наборам <tex>S_{i}</tex>. Теперь числа опускаются дальше в ЭП-дереве.
 
Нетрудно заметить, что ребалансирока занимает <tex>O(n \log\log n)</tex> времени с <tex>O(n)</tex> временем на уровень. Аналогично стандартному ЭП-дереву Андерссона.
 
Нам следует нумеровать уровни ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз на уровне <tex>s</tex>. Имеется <tex>t = n^{1 - (4/5)^s}</tex> наборов по <tex>n^{(4/5)^s}</tex> чисел в каждом. Так как каждый узел на данном уровне имеет <tex>p = n^{(1/5)(4/5)^s}</tex> детей, то на <tex>s + 1</tex> уровень опускаются <tex>q = n^{(2/5)(4/5)^s}</tex> чисел для каждого набора или всего <tex>qt \ge n^{2/5}</tex> чисел для всех наборов за один раз.
 
Спуск вниз можно рассматривать как сортировку <tex>q</tex> чисел в каждом наборе вместе с <tex>p</tex> числами <tex>a_{1}, a_{2}, \ldots, a_{p}</tex> из ЭП-дерева, так, что эти <tex>q</tex> чисел разделены в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}, \ldots, S_{p}</tex> таких, что <tex>S_{0} < </tex>{<tex>a_{1}</tex>} < <tex>\ldots</tex> < {<tex>a_{p}</tex>}<tex> < S_{p}</tex>
 
Так как не надо полностью сортировать <tex>q</tex> чисел и <tex>q = p^2</tex>, то есть возможность использовать лемму 2 для сортировки. Для этого необходимо неконсервативное преимущество, которое получается ниже. Для этого используется линейная техника многократного деления (multi-dividing technique), чтобы добиться этого.
 
Для этого воспользуемся signature sorting. Адаптируем этот алгоритм для нас. Предположим у нас есть набор <tex>T</tex> из <tex>p</tex> чисел, которые уже отсортированы как <tex>a_{1}, a_{2}, \ldots, a_{p}</tex>, и хотется использовать числа в <tex>T</tex> для разделения <tex>S</tex> из <tex>q</tex> чисел <tex>b_{1}, b_{2}, \ldots, b_{q}</tex> в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}, \ldots, S_{p}</tex> что <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < <tex>\ldots</tex> < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Назовем это разделением <tex>q</tex> чисел <tex>p</tex> числами. Пусть <tex>h = \log n/(c \log p)</tex> для константы <tex>c > 1</tex>. <tex>h/ \log\log n \log p</tex> битные числа могут быть хранены в одном контейнере, так что одно слово хранит <tex>(\log n)/(c \log\log n)</tex> бит. Сначала рассматриваем биты в каждом <tex>a_{i}</tex> и каждом <tex>b_{i}</tex> как сегменты одинаковой длины <tex>h/ \log\log n</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки, хешируются числа в этих контейнерах (<tex>a_{i}</tex>-ом и <tex>b_{i}</tex>-ом), чтобы получить <tex>h/ \log\log n</tex> хешированных значений в одном контейнере. Чтобы получить значения сразу, при вычислении хеш значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хеш значения считаются за константное время. Затем, посчитав значения, два контейнера объединяются в один. Пусть <tex>a'_{i}</tex> хеш контейнер для <tex>a_{i}</tex>, аналогично <tex>b'_{i}</tex>. В сумме хеш значения имеют <tex>(2 \log n)/(c \log\log n)</tex> бит. Хотя эти значения разделены на сегменты по <tex>h/ \log\log n</tex> бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Сначала упаковываются все сегменты в <tex>(2 \log n)/(c \log\log n)</tex> бит. Потом рассматриваются каждый хеш контейнер как число и сортируются эти хеш контейнеры за линейное время (сортировка рассмотрена чуть позже). После этой сортировки биты в <tex>a_{i}</tex> и <tex>b_{i}</tex> разрезаны на <tex>\log\log n/h</tex>. Таким образом получилось дополнительное мультипликативное преимущество в <tex>h/ \log\log n</tex> (additional multiplicative advantage).
 
После того, как повторится вышеописанный процесс <tex>g</tex> раз, получится неконсервативное преимущество в <tex>(h/ \log\log n)^g</tex> раз, в то время, как потрачено только <tex>O(gqt)</tex> времени, так как каждое многократное деление делятся за линейное время <tex>O(qt)</tex>.
 
Хеш функция, которая используется, находится следующим образом. Будут хешироватся сегменты, которые <tex>\log\log n/h</tex>-ые, <tex>(\log\log n/h)^2</tex>-ые, <tex>\ldots</tex> от всего числа. Для сегментов вида <tex>(\log\log n/h)^t</tex>, получаем нарезанием всех <tex>p</tex> чисел на <tex>(\log\log n/h)^t</tex> сегментов. Рассматривая каждый сегмент как число, получится <tex>p(\log\log n/h)^t</tex> чисел. Затем получаем одну хеш функцию для этих чисел. Так как <tex>t < \log n</tex> то, получится не более <tex>\log n</tex> хеш функций.
 
Рассмотрим сортировку за линейное время о которой было упомянуто ранее. Предполагается, что хешированные значения для каждого контейнера упаковались в <tex>(2 \log n)/(c \log\log n)</tex> бит. Есть <tex>t</tex> наборов в каждом из которых <tex>q + p</tex> хешированных контейнеров по <tex>(2 \log n)/(c \log\log n)</tex> бит в каждом. Эти числа должны быть отсортированы в каждом наборе. Комбинируя все хеш контейнеры в один pool, сортируем следующим образом.
 
Таким образом заполняются все наборы за линейное время.
 
Как уже говорилось ранее после <tex>g</tex> сокращений бит получаем неконсервативное преимущество в <tex>(h/ \log\log n)^g</tex>. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на лемму два для завершения разделения <tex>q</tex> чисел с помощью <tex>p</tex> чисел на наборы. Заметим, что по природе битового сокращения, начальная задача разделения для каждого набора перешла в <tex>w</tex> подзадачи разделения на <tex>w</tex> поднаборы для какого-то числа <tex>w</tex>.
 
Теперь для каждого набора собираются все его поднаборы в подзадачах в один набор. Затем используя лемму два, делается разделение. Так как получено неконсервативное преимущество в <tex>(h/ \log\log n)^g</tex> и работа происходит на уровнях не ниже чем <tex>2 \log\log\log n</tex>, то алгоритм занимает <tex>O(qt \log\log n/(g(\log h - \log\log\log n) - \log\log\log n)) = O(\log\log n)</tex> времени.
 
Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере <tex>\log m \ge \log\log\log n</tex>, потому, что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть <tex>h/ \log\log n</tex> хешированных значений (сегментов) в себе на уровне <tex>\log h</tex> в ЭП-дереве. Полное число хешированных бит в контейнере <tex>(2 \log n)(c \log\log n)</tex> бит. Хотя хешированны биты в контейнере выглядят как <tex>0^{i}t_{1}0^{i}t_{2} \ldots t_{h/ \log\log n}</tex>, где <tex>t_{k}</tex>-ые это хешированные биты, а нули это просто нули. Сначала упаковываем <tex>\log\log n</tex> контейнеров в один и получаем <tex>w_{1} = 0^{j}t_{1, 1}t_{2, 1} \ldots t_{\log\log n, 1}0^{j}t_{1, 2} \ldots t_{\log\log n, h/ \log\log n}</tex> где <tex>t_{i, k}</tex>: <tex>k = 1, 2, \ldots, h/ \log\log n</tex> из <tex>i</tex>-ого контейнера. Ипользуем <tex>O(\log\log n)</tex> шагов, чтобы упаковать <tex>w_{1}</tex> в <tex>w_{2} = 0^{jh/ \log\log n}t_{1, 1}t_{2, 1} \ldots t_{\log\log n, 1}t_{1, 2}t_{2, 2} \ldots t_{1, h/ \log\log n}t_{2, h/ \log\log n} \ldots t_{\log\log n, h/ \log\log n}</tex>. Теперь упакованные хеш биты занимают <tex>2 \log n/c</tex> бит. Используем <tex>O(\log\log n)</tex> времени чтобы распаковать <tex>w_{2}</tex> в <tex>\log\log n</tex> контейнеров <tex>w_{3, k} = 0^{jh/ \log\log n}0^{r}t_{k, 1}O^{r}t_{k, 2} \ldots t_{k, h/ \log\log n} k = 1, 2, \ldots, \log\log n</tex>. Затем используя <tex>O(\log\log n)</tex> времени упаковываем эти <tex>\log\log n</tex> контейнеров в один <tex>w_{4} = 0^{r}t_{1, 1}0^{r}t_{1, 2} \ldots t_{1, h/ \log\log n}0^{r}t_{2, 1} \ldots t_{\log\log n, h/ \log\log n}</tex>. Затем используя <tex>O(\log\log n)</tex> шагов упаковать <tex>w_{4}</tex> в <tex>w_{5} = 0^{s}t_{1, 1}t_{1, 2} \ldots t_{1, h/ \log\log n}t_{2, 1}t_{2, 2} \ldots t_{\log\log n, h/ \log\log n}</tex>. В итоге используем <tex>O(\log\log n)</tex> времени для упаковки <tex>\log\log n</tex> контейнеров. Считаем что время потраченное на одно слово {{---}} константа.
 
==Signature sorting==
В данной сортировке используется следующий алгоритм:
 
 
Предположим, что <tex>n</tex> чисел должны быть сортированы, и в каждом <tex>\log m</tex> бит. Рассматривается, что в каждом числе есть <tex>h</tex> сегментов, в каждом из которых <tex>\log (m/h)</tex> бит. Теперь применяем хеширование ко всем сегментам и получаем <tex>2h \log n</tex> бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке <tex>n</tex> чисел по <tex>m</tex> бит в каждом стала задачей по сортировке <tex>n</tex> чисел по <tex> \log (m/h)</tex> бит в каждом.
 
 
Так же, рассмотрим проблему последующего разделения. Пусть <tex>a_{1}</tex>, <tex>a_{2}</tex>, <tex>\ldots</tex>, <tex>a_{p}</tex> {{---}} <tex>p</tex> чисел и <tex>S</tex> {{---}} множество чисeл. Необходимо разделить <tex>S</tex> в <tex>p + 1</tex> наборов таких, что: <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < {<tex>a_{2}</tex>} < <tex>\ldots</tex> < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Т.к. используется signature sorting, до того как делать вышеописанное разделение, необходимо поделить биты в <tex>a_{i}</tex> на <tex>h</tex> сегментов и возьмем некоторые из них. Так же делим биты для каждого числа из <tex>S</tex> и оставим только один в каждом числе. По существу для каждого <tex>a_{i}</tex> берутся все <tex>h</tex> сегментов. Если соответствующие сегменты <tex>a_{i}</tex> и <tex>a_{j}</tex> совпадают, то нам понадобится только один. Сегменты, которые берутся для числа в <tex>S</tex>, {{---}} сегмент, который выделяется из <tex>a_{i}</tex>. Таким образом преобразуется начальная задачу о разделении <tex>n</tex> чисел в <tex>\log m</tex> бит в несколько задач на разделение с числами в <tex>\log (m/h)</tex> бит.
 
 
Пример:
Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере <tex>\log m \ge \log\log\log n</tex>, потому, что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть <tex>h/ \log\log n</tex> хешированных значений (сегментов) в себе на уровне <tex>\log h</tex> в ЭП-дереве. Полное число хешированных бит в контейнере <tex>(2 \log n)(c \log\log n)</tex> бит. Хотя хешированны биты в контейнере выглядят как <tex>0^{i}t_a_{1}0^{i}t_{2} \ldots t_{h/ \log\log n}</tex>= 3, где <tex>t_a_{k2}</tex>-ые это хешированные биты, а нули это просто нули. Сначала упаковываем <tex>\log\log n</tex> контейнеров в один и получаем <tex>w_{1} = 0^{j}t_{15, 1}t_{2, 1} \ldots t_{\log\log n, 1}0^{j}t_{1, 2} \ldots t_{\log\log n, h/ \log\log n}</tex> где <tex>t_a_{i, k3}</tex>: <tex>k = 1, 2, \ldots, h/ \log\log n</tex> из <tex>i</tex>-ого контейнера. Ипользуем <tex>O(\log\log n)</tex> шагов7, чтобы упаковать <tex>w_a_{14}</tex> в = 10, S = <tex>w_{2} = 0^{jh/ \log\log n}t_{1, 1}t_{24, 1} \ldots t_{\log\log n6, 1}t_{18, 2}t_{29, 2} \ldots t_{1, h/ \log\log n}t_{2, h/ \log\log n} \ldots t_{\log\log n13, h/ 14\log\log n}</tex>. Теперь упакованные хеш биты занимают <tex> Делим числа на 2 \log n/c</tex> битсегмента. Используем Для <tex>O(\log\log n)a_{1}</tex> времени чтобы распаковать получим верхний сегмент 0, нижний 3; <tex>w_a_{2}</tex> в верхний 1, нижний 1; <tex>\log\log n</tex> контейнеров <tex>w_a_{3, k} = 0^{jh/ \log\log n}0^{r}t_{k, 1}O^{r}t_{k, 2} \ldots t_{k, h/ \log\log n} k = 1, 2, \ldots, \log\log n</tex>. Затем используя верхний 1, нижний 3; <tex>O(\log\log n)a_{4}</tex> времени упаковываем эти <tex>\log\log n</tex> контейнеров в один <tex>w_{4} = 0^{r}t_{1, 1}0^{r}t_{1верхний 2, нижний 2} \ldots t_{. Для элементов из S получим: для 1, h/ \log\log n}0^{r}t_{2, : нижний 1} \ldots t_{\log\log n, h/ \log\log n}</tex>т.к. Затем используя <tex>O(\log\log n)он выделяется из нижнего сегмента </tex> шагов упаковать <tex>w_a_{41}</tex> в <tex>w_{5} = ; для 4 нижний 0; для 8 нижний 0^{s}t_{; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1}t_{1и 3, нижние сегменты 4, 5, 2} \ldots t_{16, h/ \log\log n}t_{27, 1}t_{2нижние сегменты 8, 2} \ldots t_{\log\log n9, h/ \log\log n}</tex>. В итоге используем <tex>O(\log\log n)</tex> времени для упаковки <tex>\log\log n</tex> контейнеров. Считаем что время потраченное 10 формируют 4 новые задачи на одно слово {{---}} константаразделение.
==Лемма №1==
Даны целые числа <tex>b</tex> <tex>\ge</tex> <tex>s</tex> <tex>\ge</tex> 0 и <tex>T</tex> является подмножеством <tex>\{0, \ldots, 2^b - 1\}</tex>, содержащим <tex>n</tex> элементов, и <tex>t</tex> <tex>\ge</tex> <tex>2^{-s + 1}</tex>С<tex>^k_{n}</tex>. Функция <tex>h_{a}</tex> принадлежащая <tex>H_{b,s}</tex> может быть выбрана за время <tex>O(bn^2)</tex> так, что количество коллизий <tex>coll(h_{a}, T) <tex>\le</tex> t</tex>
==Лемма №2==
Анонимный участник

Навигация