Хеширование (29 апреля 2016)

  1. Случайные графы. Забавные факты.
    1. В графе из n/3 рёбер с большой вероятностью нет циклов
    2. В графе из 5n рёбер каково размера компоненты связности?
    3. В графе из n рёбер каково размера компоненты связности?
  2. Суффиксные деревья, окончание
    1. Лемма: суффиксная ссылка вершины − вершина
    2. Лемма: время работы O(n) (длина пути suf[v] не более чем на 1 меньше, чем у v)
    3. Построение: куда ведёт суфф ссылка вершины?
    4. Пример построения на строке "ababbaabbc".
    5. Алгоритм Маккрейта
− Перерыв −
  1. Универсальное семество хеш функций (M → m)
    1. Определение через |H|/m и 1/m. Эквивалентность.
    2. Плохое хеширования: x → x mod m
    3. Пример хорошего хеширования: x → ((ax + b) mod p) mod m. Hp,m = {(a, b)} − универсальное семейство хеш-функций.
    4. Хеш-таблица: детерминированная версия, рандомизированая версия
    5. Хеш-таблица на списках: среднее число коллизий (m = n, m = n2), средняя длина списка.
  2. Совершенное хеширование
    1. Пример: младший бит числа
    2. У нас уже есть рандомизированное O(1): хеш-таблица. Теперь нужно детерминированное O(1).
    3. Двухуровневая схема (внешняя таблица имеет размер m=n, внутренняя для i-й корзины имеет размер ki2). Сколько памяти нужно? O(nlogn) бит.
    4. Схема со случайным графом [Czech'92] (x → ребро (h1(x),h2(x)), если получили ацикличный граф, можем расставить числа). Сколько памяти нужно? O(nlogn) бит.
  3. Хеширование кукушки [Pagh,Rodler'01]
  4. Фильтр Блюма
    1. Структура: есть k хеш-функций, и m бит. Элемент x есть в множестве, если все биты h1(x),...hk(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.6185m/n