Эффективная реализация фильтра Блума в C?

Этот вопрос задан ранее, но в тот момент ответа не было, поэтому я решил снова спросить его.

Мне нужна эффективная реализация фильтра Bloom в C (а не С++). Если такой вещи нет, я бы не пропустил ее, если бы получил хорошую ссылку, чтобы она не занимала слишком много времени.

Я хочу использовать эту структуру данных для вставок и тестов в соотношении (1: 20k), поэтому в первую очередь это требует интенсивного тестирования. Тестируемые данные - это 64-битные целые числа.

Ответы

Ответ 1

У меня есть отдельная простая библиотека C, которая может быть полезной: https://github.com/jvirkki/libbloom

Ответ 2

Не делать слишком много саморекламы, но я написал плагин для Geany editor/IDE, который отфильтровывает повторяющиеся текстовые строки, он использует фильтр Bloom.

Реализация находится на C, и вы можете найти ее прямо здесь, на GitHub. Это GPL v3, поэтому в зависимости от ваших точных потребностей вы можете или не сможете его использовать.

Некоторые заметки о моей реализации:

  • Он предназначен для фильтрации строк и не абстрагирует тип ключа. Это означает, что вам придется изменить обработку ключей в соответствии с вашими потребностями.
  • Он поддерживает нехарактерную семантику, вы можете фактически использовать ее для абсолютно не вероятностного тестирования existance, если хотите (см. указатель функции BloomContains callback, используемый bloom_filter_new()). Просто передайте NULL, чтобы получить "чистый" фильтр.
  • Функция хеш-функции MurmurHash2 от Остина Эпплби. Я оценил более современный MurmurHash3, но с версией 2 было легче работать.
  • Чтобы соответствовать системе eco Geany, этот код использует GLib.

Он не был сильно настроен на производительность, но должен быть в порядке. Я был бы признателен за любые отзывы, которые могут возникнуть после тестирования, конечно!