Название очень блефует, титульная партия - мяу хахахахахаха. Хорошо, вернемся к теме, когда мы делаем сканирование данных, если мы гарантируем дедупликацию, давайте поговорим с вами сегодня об использовании фильтра Блума для дедупликации.
Прежде всего, что такое фильтр Блума, давайте все же заглянем в энциклопедию Baidu.
- Фильтр Блума был предложен Блумом в 1970 году. На самом деле это длинный двоичный вектор и ряд функций случайного отображения. Фильтры Блума можно использовать для определения того, находится ли элемент в коллекции. Его преимущество в том, что эффективность использования пространства и время запроса намного лучше, чем у общего алгоритма, а недостаток в том, что он имеет определенную частоту ложных распознаваний и его трудно удалить.
Глупо, на самом деле, я только что начал напрямую. На самом деле двоичный вектор в верхней части представляет собой массив битов (например, массив битов длиной 2 ^ 32 в REDIS, размер которого составляет 512 МБ), а ряд функций случайного отображения на самом деле представляет собой несколько хеш-функций. Итак, сначала и все придут на Хэш.
хэш-функция
Хеш-функция обычно также называется хэш-функцией, то есть вход любой длины может быть преобразован в выходное число фиксированной длины с помощью хеш-алгоритма, а выходным результатом является хэш-значение. Общие хэш-функции включают md5, sha1, sha256 и т. д. Хеш-функции также можно понимать как метод шифрования, но хеш-функции необратимы, то есть вы не можете получить хеш-значение из выходного поля и обратить значение входного поля. . . . (Поскольку он использует очень мощные научные расчеты, он необратим.) Затем поговорим о нескольких характеристиках хеширования.
- Неограниченный входной домен, ограниченный выходной домен(То есть, если вы поместите приветственное слово в поле ввода и небольшой фильм 10G, выходное поле выводит вывод фиксированной длины. Даже если в поле ввода есть разница только в один символ, полученные хэш-значения очень разные и нестандартные)
- Один и тот же ввод должен привести к одному и тому же результату(Это не означает, что вы используете одну и ту же хеш-функцию для воспроизведения одного и того же небольшого фильма 10G дважды, и полученное хеш-значение будет одинаковым)
- Различные входные данные могут также получить один и тот же результат, явление, известное как хеш-коллизия.(Поскольку поле ввода бесконечна, а выходное поле ограничено, оно неизбежно приведет к тому, что введите два разных значения, которые вы вводите, но выходное поле получает то же значение HASH)
- Каждый результат выходной области равномерно распределяется по всей выходной области, что также становится дискретностью хеш-функции.(Полезность хеш-функции обычно отражается в ее дискретности. Чем более равномерно распределены выходные результаты, тем лучше дискретность.)
Есть много применений для хеш-функций, например
Посмотрите на это, когда вы загружаете League of Legends, как вы можете быть уверены, что ваша полная загрузка прошла успешно?
В это время официал закинет файл в хеш-функцию (md5) для шифрования, получит хэш-значение, как показано на рисунке выше, а затем, когда загрузка будет завершена, зашифрует загруженный вами файл той же хэш-функцией, Если полученное значение совпадает с официальным значением, вы, должно быть, уже полностью загрузили файл. Обычно для такого рода проверки файлов используются хеш-функции.
Так что вы должны понять меня, когда я говорю это (шепотом bb....)
В порядке! Теперь, когда мы все знаем, так что в следующей теме поговорим о фильтре Блума (мяу от этого беспардонного вопроса и ответа ха-ха-ха-ха-ха-ха~)
Фильтр Блума
Во-первых, давайте поговорим о процессе работы фильтра Блума.
- Сначала хэшируйте данные с помощью k хеш-функций, чтобы получить k хеш-значений (h1, h2, ...hk)
- Определите длину битового массива, предположим, m, возьмите k хеш-значений по модулю m соответственно, чтобы получить k значений (v1, v2....vk). Убедитесь, что каждое значение находится в пределах длины битового массива. [ 0,м-1]
- Если вам нужно сохранить, в размерном массиве используйте значения k, полученные по модулю на предыдущем шаге, в качестве значения индекса, и найдите значение, соответствующее индексам k, и измените его на 1.
- Если вам нужно запросить, существуют ли данные, проверьте, все ли значения, соответствующие индексам k, равны 1. Если все равны 1, это означает, что они существуют, в противном случае они не существуют.
Я предполагаю, что должна быть какая-то сила, чтобы содрать после того, как вы прочитали, представьте, что вы положили лист бумаги в битовый массив
Затем, предполагая, что данные еще не были добавлены, вы передали 4 хеш-функции и получили 4 значения по модулю (эти 4 значения должны быть в пределах диапазона длин этого битового массива, потому что выполняется операция по модулю), эти 4 значения находятся в определенных позициях этого документа, затемните эти 4 позиции
Поэтому, когда вы добавите много данных, на этой белой бумаге будет много маленьких черных точек (я больше не буду ее рисовать, это некрасиво и надоело...)
Как судить о дублировании Если позиция, соответствующая значению, полученному путем множественных хеш-вычислений и по модулю, на этом листе бумаги вся черная, то этот фрагмент данных считается дублированным. Пока есть позиция, которая является белой, то она не будет повторяться, продолжайте добавлять и затемняйте позицию, которая является белой, а позиция, которая уже является черной, игнорируется.
Поэтому, чтобы судить о повторении данных, нужно только проверить, все ли соответствующие позиции индексов в битовом массиве равны 1, и если они все равны 1, то повторить, и эти данные можно отбросить.
Я думаю, вы все это понимаете... эммммм, понимаете вы это или нет, я продолжу!
Когда мы используем фильтр Блума для дедупликации, должна быть частота ошибок (из-за характеристик коллизии хэшей), но это может гарантировать, что дублирующиеся данные могут быть оценены! (Это означает, что существует очень маленькая вероятность того, что когда ваши данные не будут повторяться, я скажу, что вы повторяетесь! Вам не разрешат добавлять данные! Будьте уверены!!!)
А у фильтра Блума есть еще одна особенность, то есть он обращает внимание только на количество данных, а не считает размер одной выборки данных (это определяется свойством хеша 1, поле ввода не ограничено, а поле вывода ограничено), поэтому фильтр Блума особенно эффективен для массивной дедупликации больших данных и больших выборок.
这个时候就会发现这个失误率和位数组的长度m、和哈希函数的个数k息息相关。这个时候如何设计布隆过滤器呢？ Не переживай!已经有科学家帮我们研究出了公式，我们只需要根据自己样本数量和预计失误率计算出你需要的东西啦！就是这么得劲！
По количеству выборочных данных n и частоте ошибок p можно рассчитать m (длину битового массива).
Рассчитать количество k хеш-функций в соответствии с m и n
Рассчитайте фактическую частоту ошибок через значения m, k и n
Длина полученного массива и количество функций округляются в большую сторону, например, если рассчитанное k равно 8,23, то сразу берется 9 хеш-функций, поэтому процент ошибок будет ниже ожидаемого.
Итак, фильтр Блума может дедуплицировать большой объем данных с очень небольшими затратами, и это все!
Чедан так сильно вытащил, но код на ха!
Код (Питон)
Битовый массив, здесь я буду напрямую использовать бит, предоставленный в Redis, во-первых, мне нужно несколько разных хеш-функций (это можно найти в MIT)
#
#**************************************************************************
#* *
#* General Purpose Hash Function Algorithms Library *
#* *
#* Author: Arash Partow - 2002 *
#* URL: http://www.partow.net *
#* URL: http://www.partow.net/programming/hashfunctions/index.html *
#* *
#* Copyright notice: *
#* Free use of the General Purpose Hash Function Algorithms Library is *
#* permitted under the guidelines and in accordance with the MIT License. *
#* http://www.opensource.org/licenses/MIT *
#* *
#**************************************************************************
def rs_hash(key):
a = 378551
b = 63689
hash_value = 0
for i in range(len(key)):
hash_value = hash_value * a + ord(key[i])
a = a * b
return hash_value
def js_hash(key):
hash_value = 1315423911
for i in range(len(key)):
hash_value ^= ((hash_value << 5) + ord(key[i]) + (hash_value >> 2))
return hash_value
def pjw_hash(key):
bits_in_unsigned_int = 4 * 8
three_quarters = (bits_in_unsigned_int * 3) / 4
one_eighth = bits_in_unsigned_int / 8
high_bits = 0xFFFFFFFF << int(bits_in_unsigned_int - one_eighth)
hash_value = 0
test = 0
for i in range(len(key)):
hash_value = (hash_value << int(one_eighth)) + ord(key[i])
test = hash_value & high_bits
if test != 0:
hash_value = ((hash_value ^ (test >> int(three_quarters))) & (~high_bits))
return hash_value & 0x7FFFFFFF
def elf_hash(key):
hash_value = 0
for i in range(len(key)):
hash_value = (hash_value << 4) + ord(key[i])
x = hash_value & 0xF0000000
if x != 0:
hash_value ^= (x >> 24)
hash_value &= ~x
return hash_value
def bkdr_hash(key):
seed = 131 # 31 131 1313 13131 131313 etc..
hash_value = 0
for i in range(len(key)):
hash_value = (hash_value * seed) + ord(key[i])
return hash_value
def sdbm_hash(key):
hash_value = 0
for i in range(len(key)):
hash_value = ord(key[i]) + (hash_value << 6) + (hash_value << 16) - hash_value;
return hash_value
def djb_hash(key):
hash_value = 5381
for i in range(len(key)):
hash_value = ((hash_value << 5) + hash_value) + ord(key[i])
return hash_value
def dek_hash(key):
hash_value = len(key);
for i in range(len(key)):
hash_value = ((hash_value << 5) ^ (hash_value >> 27)) ^ ord(key[i])
return hash_value
def bp_hash(key):
hash_value = 0
for i in range(len(key)):
hash_value = hash_value << 7 ^ ord(key[i])
return hash_value
def fnv_hash(key):
fnv_prime = 0x811C9DC5
hash_value = 0
for i in range(len(key)):
hash_value *= fnv_prime
hash_value ^= ord(key[i])
return hash_value
def ap_hash(key):
hash_value = 0xAAAAAAAA
for i in range(len(key)):
if (i & 1) == 0:
hash_value ^= ((hash_value << 7) ^ ord(key[i]) * (hash_value >> 3))
else:
hash_value ^= (~((hash_value << 11) + ord(key[i]) ^ (hash_value >> 5)))
return hash_value
Далее идет реализация цветения
from BloomFilter.GeneralHashFunctions import *
import redis
import pickle
import base64
class BloomFilterRedis(object):
# 哈希函数列表
hash_list = [rs_hash, js_hash, pjw_hash, elf_hash, bkdr_hash, sdbm_hash, djb_hash, dek_hash]
def __init__(self, key, host='127.0.0.1', port=6379):
self.key = key
self.redis = redis.StrictRedis(host=host, port=port, charset='utf-8')
def random_generator(self, hash_value):
'''
将hash函数得出的函数值映射到[0, 2^32-1]区间内
'''
return hash_value % (1 << 32)
def do_filter(self, item, save=True):
"""
过滤，判断是否存在
:param item:
:return:
"""
flag = True # 默认存在
for hash in self.hash_list:
# 计算哈希值
hash_value = hash(item)
# 获取映射到位数组的下标值
index_value = self.random_generator(hash_value)
# 判断指定位置标记是否为 0
if self.redis.getbit(self.key, index_value) == 0:
# 如果不存在需要保存，则写入
if save:
self.redis.setbit(self.key, index_value, 1)
flag = False
return flag
class Stu(object):
def __init__(self, name, age):
self.name = name
self.age = age
if __name__ == '__main__':
bloom = BloomFilterRedis("bloom_obj")
# 对对象进行去重，必须实现序列化
data = pickle.dumps(Stu("xiaohong", 18))
data1 = base64.b64encode(data).decode()
ret = bloom.do_filter(data1)
print(ret)
data = pickle.dumps(Stu("xiaohong", 18))
data1 = base64.b64encode(data).decode()
ret = bloom.do_filter(data1)
print(ret)
bloom = BloomFilterRedis("bloom_url")
ret = bloom.do_filter("http://www.baidu.com")
print(ret)
ret = bloom.do_filter("http://www.baidu.com")
print(ret)
Ну, код строки и выше, чтобы поприветствовать вас в небольшой партнер собрать взгляды ха-ха-ха-ха-ха-ха, то здесь сегодня, позвольте мне уйти! ! !