Объяснение алгоритма "Граф эскиза"

Question

Может кто-нибудь объяснить, как работает алгоритм Sketch Count? Например, я до сих пор не могу понять, как используются хеши. Мне трудно понять эту статью .

Answer 1

Этот алгоритм потоковой передачи создает следующую структуру.

1. Найдите алгоритм рандомизированной потоковой передачи, выход которого (в качестве случайной переменной) имеет желаемое ожидание, но обычно высокую дисперсию (то есть шум).

2. Чтобы уменьшить дисперсию / шум, запустите много независимых копий параллельно и объедините их выходные данные.

Обычно 1 более интересен, чем 2. Этот алгоритм 2 на самом деле несколько нестандартен, но я собираюсь поговорить только о 1.

Предположим, мы обрабатываем ввод

a b c a b a .

С тремя счетчиками нет необходимости хешировать.

a: 3, b: 2, c: 1

Предположим, однако, что у нас есть только один. Есть восемь возможных функций h : {a, b, c} -> {+1, -1}. Вот таблица результатов.

 h  |
abc |  X = counter
----+--------------
+++ | +3 +2 +1 =  6
++- | +3 +2 -1 =  4
+-- | +3 -2 -1 =  0
+-+ | +3 -2 +1 =  2
--+ | -3 -2 +1 = -4
--- | -3 -2 -1 = -6
-+- | -3 +2 -1 = -2
-++ | -3 +2 +1 =  0

Теперь мы можем рассчитать ожидания

            (6 + 4 + 0 + 2) - (-4 + -6 + -2 + 0)
E[h(a) X] = ------------------------------------ = 24/8 = 3
                             8

            (6 + 4 + -2 + 0) - (0 + 2 + -4 + -6)
E[h(b) X] = ------------------------------------ = 16/8 = 2
                             8

            (6 + 2 + -4 + 0) - (4 + 0 + -6 + -2)
E[h(c) X] = ------------------------------------ =  8/8 = 1 .
                             8

Что здесь происходит? Например, для a мы можем разложить X = Y + Z, где Y - это изменение суммы для a с, а Z - это сумма для не a с. По линейности ожидания имеем

E[h(a) X] = E[h(a) Y] + E[h(a) Z] .

E[h(a) Y] - это сумма со слагаемым для каждого вхождения a, то есть h(a)^2 = 1, поэтому E[h(a) Y] - это число вхождений a. Другой термин E[h(a) Z] равен нулю; даже если задано h(a), хэш-значения друг друга с равной вероятностью будут равны плюс или минус единица и, следовательно, дают нулевое ожидание.

На самом деле хеш-функция не обязательно должна быть равномерно случайной, и это хорошая вещь: не было бы способа ее сохранить. Достаточно, чтобы хеш-функция была попарно независимой (любые два конкретных хеш-значения независимы). Для нашего простого примера достаточно случайного выбора следующих четырех функций.

abc

+++
+--
-+-
--+

Я оставлю вам новые расчеты.

Answer 2

Подсчет количества - это вероятностная структура данных , которая позволяет вам ответить на следующий вопрос:

Чтение потока элементов a1, a2, a3, ..., an, где может быть много повторяющихся элементов, вв любое время он даст вам ответ на следующий вопрос: сколько элементов ai вы уже видели.

---

Вы можете точно получить точное значение в каждый раз, просто поддерживая хэш, гдеключи - это ai, а значения - это количество элементов, которые вы уже видели.Это быстрый O(1) add, O(1) check, и он даст вам точный счет.Единственная проблема в том, что он занимает O(n) пробел, где n - количество отдельных элементов (имейте в виду, что размер каждого элемента имеет большую разницу, потому что он занимает way more space to store this big string as a key, чем просто this.

---

Итак, чем вам поможет эскизный подсчет? Как и во всех вероятностных структурах данных, вы жертвуете определенностью для пространства. Набросок подсчета позволяет выбрать 2 параметра: точность результатов ε и вероятность неверной оценки δ.

Для этого вы выбираете семейство d попарно независимых хеш-функций . Эти сложные слова означают, что они не сталкиваются часто (фактически, если оба хэша отображают значения в пространство [0, m],вероятность столкновения составляет приблизительно 1/m^2). Каждая из этих хеш-функций отображает значения в пространство [0, w]. Таким образом, вы создаете матрицу d * w.

Теперь, когда вы читаете элемент, вы вычисляете каждыйd хэшей этого элемента и обновите соответствующие значения в эскизе. Эта часть такая же для эскиза Countи отсчет-мин.

Insomniac хорошо объяснил идею (вычисление ожидаемого значения) для отсчета отсчета, поэтому я просто расскажу об этом с помощью count-мин все еще проще.Вы просто вычисляете d хешей значения, которое хотите получить, и возвращаете наименьшее из них.Удивительно, но это дает надежную гарантию точности и вероятности, которую вы можете найти здесь .

Увеличение диапазона хеш-функций, повышение точности результатов, увеличение количества хеш-функций уменьшает вероятность неверной оценки: ε = e / w и δ = 1 / e ^ d.Еще одна интересная вещь - это то, что значение всегда завышено (если вы нашли значение, оно, скорее всего, больше реального значения, но, конечно, не меньше).

Answer 3

На самом деле хеш-функция не обязательно должна быть равномерно случайной, и это хорошая вещь: не было бы способа ее сохранить. Достаточно, чтобы хеш-функция была попарно независимой (любые два конкретных хеш-значения независимы). Для нашего простого примера достаточно случайного выбора следующих четырех функций.