Изменения

Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере <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}O0^{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> контейнеров. Считаем, что время, потраченное на один контейнер — константа.