81
правка
Изменения
Нет описания правки
Предположим, что <tex>n</tex> чисел должны быть сортированы, и в каждом <tex>logm</tex> бит. Мы рассматриваем, что в каждом числе есть <tex>h</tex> сегментов, в каждом из которых <tex>log(m/h)</tex> бит. Теперь мы применяем хэширование ко всем сегментам и получаем <tex>2hlogn</tex> бит хэшированных значений для каждого числа. После сортировки на хэшированных значениях для всех начальных чисел начальная задача по сортировке <tex>n</tex> чисел по <tex>m</tex> бит в каждом стала задачей по сортировке <tex>n</tex> чисел по <tex>log(m/h)</tex> бит в каждом.
Так же, рассмотрим проблему последующего разделения. Пусть <tex>a_{1}</tex>, <tex>a_{2}</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>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>logm</tex>бит в несколько задач на разделение с числами в <tex>log(m/h)</tex> бит.
