Изменения

=Quotient filter={{Определение|definition ='''Quotient filter''' {{---}} вероятностная структура данных, позволяющая проверить принадлежность элемента множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное(элемент в множестве есть, но структура данных сообщает, что его нет).}}

# бит занятости {{---}} равно равен единице, если ячейка является канонической для некого ключа в фильтре, сохраненого необязательно в этой ячейке. # бит продолжения {{---}} равно равен единице, если ячейка занята, но не первым элементов пробеге.# бит сдвига {{---}} равно равен единице, если пробег сдвинут относительно канонического слота.

1 1 1 : Ячейка содержит элем ент элемент пробега(не первый), сдвинутого относительно канонического слота. Ячейка является канонической, для существующего пробега сдвинутого вправо.

Если бит занятости единица, то нам нужно найти пробег для <tex>Dq</tex>. Так как начало нужного пробега может быть сдвинуто, найдем начало кластера. Идем влево от ячейки <tex>Dq</tex> и ищем первую с битом сдвига равным нулю, эта ячейка и будет началом кластера. Пока мы идем влево от <tex>Dq</tex> будем поддерживать счетчик, который бедет показывать сколько пробегов нам нужно будет пропустить от начала кластера. Каждая ячейка с битом занятости равным единице увеличивает счетчик на <tex>1</tex>. После того как мы нашли начало кластера, пойдем от него в левовлево, каждая ячейка с битом продолжения равным нулю говорит о завершении пробега, когда счетчик станет равным нулю мы найдем нужный нам пробег для <tex>Dq</tex>. Если в этом пробеге содержится <tex>Dr</tex>, то <tex>D</tex> ,вероятно, содержится в множестве, иначе <tex>D</</tex> точно не содержится в множестве.