Хеширование и архиваторы (18 ноября 2024)

1. Универсальное семество хеш функций (M → m)
   1. Определение через 1/m.
   2. Плохое хеширования: x → x mod m. Почему плохое?
   3. Пример хорошего хеширования: x → ((ax + b) mod p) mod m. H_p,m = {(a, b)} − универсальное семейство хеш-функций.
   4. Хеш-таблица: детерминированная версия, рандомизированная версия
   5. Хеш-таблица на списках: среднее число коллизий (m = n, m = n²), средняя длина списка.
   
   
2. Фильтр Блюма
   1. Структура: есть k хеш-функций, и m бит. Элемент x есть в множестве, если все биты h₁(x),...,h_k(x) стоят.
   2. Вероятность одного бита: (1 - 1/m)^kn ≈ e^-kn/m
   3. Вероятность ложного срабатывания: (1 - e^-kn/m)^k. При фиксированных (n,m) получаем оптимальное k = ln2 * (m/n). Pr = 2^-k = 0.6185^m/n
   4. Сравнение с хеш-таблицей: пусть для каждого x считаем 16-битный хеш, тогда даже для открытой адресации нужно 16*1.5*n = 24n бит. Взяв m/n=24, получаем ошибку <10^-6.
   
   
3. Совершенное хеширование
   1. Постановка задачи: даны x₁, x₂, ... x_k, придумать f: f(x_i) различны и попадают в диапазон.
   2. Пример: младший бит числа, m[2^k mod 67] = k для всех k=0..63
   3. У нас уже есть рандомизированное O(1): хеш-таблица. Теперь нужно детерминированное O(1).
   4. Двухуровневая схема (внешняя таблица имеет размер m=n, внутренняя для i-й корзины имеет размер k_i²). Сколько памяти нужно? O(nlogn) бит.

1. Сжатие данных
   1. Постановка задачи: придумать обратимую f для битовых строк (строк над алфавитом?)
   2. Не существует идеального архиватора: 2^k > ∑ 2ⁱ
   3. Существует не сильно портящий архиавтор: s → 0s или 1f(s)
   4. Что уже знаем? 7-битное кодирование. Хаффман.
   
   
2. Хаффман: реализация
   1. Декодирования: бесконечный спуск по бору.
   2. Хранение словаря частотами: k*logN бит.
   3. Хранение словаря бором: z*(2+logk) бит (z − кол-во символов с ненулевой частотой)
   
   
3. Арифметическое кодирование
   1. Проблемы Хаффмана: k=3, равные частоты ; k=2, сильно неравные частоты.
   2. Заметим, что 3⁵ = 243 ⇒ за 8 бит можно сохранить 5 символов при k=3.
   3. Идея: делить отрезок рекурсивно на части, кидать точку, куда попали, тот и символ.
   4. Kraft-McMillan inequality: ∑ 2^-len_i ≤ 1
   5. Gibbs' inequality: Оптимальные коды: len_i = -log₂p_i. Теоретическая оценка: ∑ -p_i*log₂p_i.
   
   
4. Словарное кодирование
   1. Пример с английскими словами и новым алфавитом
   2. LZW. Нет оверхеда на хранение словаря. Пример: ababc.
   
   
5. BWT.
   1. Определение: последний столбец массива циклических сдвигов
   2. Примеры: harryharry → hhyyaarrrr | harry,oh,harry,harry → hyyhhho,y,,aaarrrrrr
   3. Что хорошего мы тут видим? Цепочки одинаковых символов.
   4. Время: O(n) прямое, O(n) обратное (изучим на практике).
   
   
6. RLE. Принцип кодирования. Пример: BMP. Аккуратное битовое хранение.
   1. Время: один проход, максимально быстро.
   
   
7. MTF. Принцип кодирования. Пример: 999000559 → 900100302.
   1. Время: O(nk) прямое, O(nk) обратное (изучим на практике). Оба на практике улучшим до O(nlogk).
   
   
8. Соединяем: BWT + MTF + RLE + Арифметическое кодирование
   
9. Как сжимать лучше? Предсказание текста. Суффиксный автомат и вероятностые модели над исходным алфавитом и метаалфавитом.

1. Бонус. Случайные графы. Забавные факты.
   1. В графе из n/3 рёбер с большой вероятностью нет циклов
   2. В графе из n, 3n, 5n, 7n рёбер каково размера компоненты связности? (4/5n, n-sqrt(n), n-O(1), n)
   3. В графе без циклов из n/2, n/3 рёбер какой диаметр дерева? (sqrt(n), logn)
   
   
2. Бонус. Схема со случайным графом [Czech'92]
   1. x → ребро (h₁(x),h₂(x)). x → i = (f[h₁(x)] + f[h₂(x)]) mod n, все i различны
   2. Если получили ацикличный граф, можем расставить числа. Сколько памяти нужно? O(nlogn) бит.
   3. С какой вероятностью получим случайный граф? Какое выбрать n? (6m)
   
   
3. Бонус. Хеширование кукушки [Pagh,Rodler'01]
   1. Схема: для каждого x есть две ячейки h₁(x) и h₂(x). Если хоть одна свободна, иначе выталкиваем того, кто лежит в h₁(x), туда кладём x... если циклимся, перестариваем всё.
   2. Время работы: add за O(1) в среднем, find и del за O(1) в худшем
   3. Сравнение: в обычной цепочечной хеш-таблице add за O(1) в худшем, find и del за O(1) в среднем