Программирование — работа в Москве

Язык программирования: C++ Домашнее задание Для решения этой задачи вам предстоит реализовать Фильтр Блума, который работает со строковыми объектами. Он поддерживает: Добавление строки в множество. Тест принадлежности строки к множеству объектов. Помимо этого вам требуется добавить поддержку расчета доли ложно-положительных срабатываний, то есть значения, которое показывает отношение количества тестов принадлежности, которые дали ложно-положительный результат, к общему числу поступивших тестов принадлежности. Реализуемый Вами класс BloomFilter должен содержать следующие методы и конструкторы: Конструктор, параметризуемый числом хеш-функций фильтра и числом ячеек фильтра. Деструктор. Метод add, который вставляет информацию о строке, с использованием хэш-функций, в множество. Принимает на вход значение строкового типа. Метод verify, который проверяет, существует ли строка в Фильтре Блума. Принимает на вход значение типа std::string, возвращает значение типа bool. В случае, если Фильтр Блума показывает, что строка в нём находится, но при этом она не добавлялась - необходимо инкрементировать счетчик ложно-положительных значений на единицу. Метод getFPRate, который возвращает отношение количества ложно-положительных срабатываний к сумме всех запросов к функции verify. Тип возвращаемого значения - double. Константный метод numberOfHashFunctions, который возвращает количество хеш-функций для данного фильтра. Константный метод numberOfBits, который возвращает количество ячеек в данном фильтре. Поскольку фильтр содержит информацию о количестве k k используемых хеш-функций, применяется следующий вариант получения k k хеш-функций: Используется объект стандартной библиотеки std::hash, а при подсчете хеша для n-ого хешера, где n > 0, добавляется некоторое подобие «соли», в качестве которой выступает номер хеш-функции, приведенный к строке и добавленный в конец исходной строки. Таким образом, например, вычисление 4 4 хеш-функций от строки «abcd» будет выглядеть следующим образом: hash0(«abcd») = std::hash{}(«abcd»); hash1(«abcd») = std::hash{}(«abcd1»); hash2(«abcd») = std::hash{}(«abcd2»); hash3(«abcd») = std::hash{}(«abcd3»); Примечания Вы должны прислать код, содержащий определение вашего класса. Для удобства рекомендуется использовать публичный интерфейс из данного примера: ссылка. Ввиду того, что требуется рассчитывать долю ложно-положительных срабатываний, необходимо организовать хранение «действительных» копий строк, информация о которых была добавлена в фильтр. Вам предстоит самостоятельно выбрать способ хранения строк, с которыми вы работаете. Разрешено использование только собственных структур. От выбора оптимального способа хранения строк будет зависеть оценка. Например, может быть выбрана одна из возможных реализаций префиксного дерева