Вероятность неверной идентификации строки в фильтре Блума - DataScientist
0 голосов
/ 12 октября 2019

Я пытаюсь задать вопрос, связанный с фильтрами Блума:

Наш фильтр Блума использует $3$ различных независимых хеш-функций $H_1, H_2, H_3$, каждая из которых принимает любую строку в качестве входных данных и возвращает индекс вбитовый массив длиной $n$. Каждый индекс одинаково вероятен для каждой хеш-функции.

Чтобы добавить строку в набор, передайте ее каждой из $3$ хеш-функций, чтобы получить $3$ позиций массива. Установите биты во всех этих положениях на $1$. Например, изначально все значения в битовом массиве равны нулю. В этом примере $n = 10$:

Index: 0 1 2 3 4 5 6 7 8 9
Value: 0 0 0 0 0 0 0 0 0 0

После добавления строки «слово», где $H_1($ «слово» $)=4$, $H_2($ «слово» $)=7$ и $H_3($ «слово"$)=8$:

Index: 0 1 2 3 4 5 6 7 8 9
Value: 0 0 0 0 1 0 0 1 1 0

Биты никогда не переключаются обратно на $0$. Рассмотрим фильтр Блума с $n=9000$ корзинами. Вы добавили в фильтр $m=1000$ строк.

a) Какова вероятность того, что в первом сегменте есть хэшированные строки $0$?

b) Чтобы проверить, является ли строкав наборе передайте его каждой из $3$ хеш-функций, чтобы получить $3$ позиций массива. Если какой-либо из битов в этих позициях равен $0$, элемент отсутствует в наборе. Если все биты в этих позициях равны $1$, строка может быть в наборе;но возможно, что эти биты равны $1$, потому что некоторые другие строки хэшируются с такими же значениями. Можно предположить, что значение одного сегмента не зависит от значения всех остальных.

Какова вероятность того, что строка, которая ранее не была добавлена ​​в набор, будет ошибочно идентифицирована, как в наборе. То есть какова вероятность того, что биты во всех его позициях хеширования уже равны $1$?

Для первой части вероятность того, что определенная строка не хешируется на $H_1$ в первую очередьведро $\frac{8999}{9000}$. Вероятность того, что эта строка не хэшируется ни одной из $3$ функций, составляет $\big(\frac{8999}{9000}\big)^3$. Вероятность того, что ни одна из строк не будет хэширована какой-либо из функций хеширования в первый сегмент, тогда равна $\big(\frac{8999}{9000}\big)^{3000}$.

Для второй части мы должны найти вероятность того, что $3$ определенных сегментов (скажем, ведра №. $p,q,r$) уже имеют хешированную строку. Это

$$P(p=1,q=1,r=1)=1-P((p=0)\cup(q=0)\cup(r=0))$$

Объединение может быть рассчитано как (обозначая события $p=0, q=0, r=0$ как $p_0, q_0, r_0$ соответственно)

$$P(p_0\cup q_0\cup r_0)=\\P(p_0)+P(q_0)+P(r_0)-P(p_0,q_0)-P(q_0,r_0)-P(r_0,p_0)+P(p_0,q_0,r_0)$$

$P(p_0),P(q_0),P(r_0)$ будет таким же, как ответ на первый вопрос. $P(p_0,q_0)$ будет (используя ту же логику, что и в части а) $\big(\frac{8998}{9000}\big)^{3000}$. $P(p_0,q_0,r_0)$ будет $\big(\frac{8997}{9000}\big)^{3000}$. Включив все эти значения, мы получим ответ.

Я не слишком уверен ни в одной из этих частей. Правильны ли ответы, а вышеприведенный подход верен? Есть ли более эффективный / лучший / альтернативный способ решения вопроса?

...