DjangoBB LoFi version

anton_krupin

Апрель 9, 2021 12:22:33

Добрый день!
Столкнулся с задачей по реализации фильтра Блума.

Реализуйте классический фильтр Блюма для строк на основе битового массива (не массива из байтов или булевых значений).
Для тестового примера можно использовать и обычное 32-разрядное целое число: принимаем размер фильтра m=32. Примем количество значений для фильтра n=10, и получим примерное количество хэш-функций k=2.
Не используйте в вашем решении никакие стандартные библиотеки для работы с битовыми массивами.

Основная проблема в том, что я не понимаю, как создать сам битовый массив (без использования сторонних библиотек типа bitarray)

Буду благодарен за помощь.

PEHDOM

Апрель 9, 2021 14:06:16

anton_krupin
Основная проблема в том, что я не понимаю, как создать сам битовый массив (без использования сторонних библиотек типа bitarray)

помотреть как это сделано у других:
https://github.com/hiway/python-bloom-filter/blob/master/src/bloom_filter/bloom_filter.py
там есть , например:
class Array_backend(object):
“”“Backend storage for our ”array of bits“ using a python array of integers”“”

py.user.next

Апрель 9, 2021 23:50:53

anton_krupin
Основная проблема в том, что я не понимаю, как создать сам битовый массив

Битовый массив создаётся в целом числе. Целое число представляет из себя массив битов.

  
>>> array = 0
>>> array
0
>>> array |= 1
>>> array
1
>>> array |= 2
>>> array
3
>>> bin(array)
'0b11'
>>> '{:010b}'.format(array)
'0000000011'
>>> array |= 4
>>> '{:010b}'.format(array)
'0000000111'
>>> array
7
>>> array |= 8
>>> '{:010b}'.format(array)
'0000001111'
>>> array
15
>>> array |= 16
>>> '{:010b}'.format(array)
'0000011111'
>>> array
31
>>>

Так как в питоне используется длинная арифметика для целых чисел, то массив может быть любого размера, хоть 1000000 битов.