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

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

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

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


c bloom-filter
person Aman Deep Gautam    schedule 13.06.2012    source источник
comment
Это вероятностно. Если вам нужен точный ответ, используйте Union Find Disjoint Set. Ищите это на topcoder, для этого должно быть какое-то руководство.   -  person nhahtdh    schedule 13.06.2012
comment
Если вы пишете на C, это не та вещь, для которой вам нужна общая библиотека. Это должно быть менее 100 строк кода, и на его написание должно уйти меньше времени, чем на интеграцию сторонней библиотеки. Просто прочитайте ваше любимое описание алгоритма в Википедии или аналогичном.   -  person R.. GitHub STOP HELPING ICE    schedule 13.06.2012
comment
@R написание займет меньше времени, насколько я знаю, но эффективное написание, чтобы оно хорошо масштабировалось, является проблемой. Я должен проверить принадлежность данных в порядке 10 ^ 7 и сделать этот запрос быстрее, чем запрос count (*) в результате эквивалентного соединения. Я не могу позволить себе потерять даже мс в своей реализации   -  person Aman Deep Gautam    schedule 13.06.2012
comment
Эффективность заключается как в любой хэш-функции, которую вы выберете (быстро, но с низкой вероятностью коллизий), так и в эффективности представления фильтра (например, растрового изображения, если вы не используете подсчитывающий фильтр); кроме этого, не так много оптимизации, которую можно сделать.   -  person tbert    schedule 13.06.2012
comment
можете ли вы сказать мне, где я могу прочитать о хеш-функциях, подходящих для этой цели?   -  person Aman Deep Gautam    schedule 13.06.2012
comment
@AmanDeepGautam да: Google; Честно говоря, у меня нет более авторитетного ответа, чем этот, хотя быстрым и грязным ответом будет передача указателя на хэш-функцию Дженкинса (http://http://www.burtleburtle.net)./bob/hash/doobs.html) и использовать его в качестве индекса для маркировки фильтра; однако это только одномерный фильтр Блума, и вы могли бы добиться большего успеха с другими подходами, ИМО   -  person tbert    schedule 13.06.2012
comment
@AmanDeepGautamer, должен был сказать, что вы должны передать указатель на макрос Jenkins mix(), а не на полноценную хеш-функцию...   -  person tbert    schedule 13.06.2012
comment
большое спасибо. когда я напишу один, я обязательно опубликую его здесь.   -  person Aman Deep Gautam    schedule 13.06.2012

Ответы (5)


arrow_upward
16
arrow_downward

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

person Jyri J. Virkki    schedule 13.02.2013

arrow_upward
4
arrow_downward

Чтобы не заниматься саморекламой, я написал плагин для редактора/IDE Geany, который отфильтровывает дубликаты. текстовые строки, он использует фильтр Блума.

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

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

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

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

person unwind    schedule 13.06.2012
comment
Эй, спасибо, это действительно может быть очень полезно. Я попробую и расскажу вам об этом. - person Aman Deep Gautam; 13.06.2012
comment
можете ли вы предложить другие библиотеки для высокой производительности, кроме glib - person Aman Deep Gautam; 14.06.2012
comment
можете ли вы предложить какой-либо конкретный мотив использования библиотеки glib, кроме того, что она делает код переносимым. - person Aman Deep Gautam; 15.06.2012
comment
@AmanDeepGautam Ну, стандартное обоснование библиотеки, конечно, применимо: кто-то уже решил кучу проблем, поэтому мне не нужно изобретать велосипед. Кроме того, код взят из плагина для IDE, основанного на GTK+/GLib, поэтому было бы странно не использовать GLib. - person unwind; 04.02.2013

arrow_upward
2
arrow_downward

У Chromium есть один на C++

ссылка на github

person eqzx    schedule 13.06.2012
comment
Чувак, им действительно нужно включить авторские права Боба Дженкинса на использование его (общественного достояния) хеш-функции... - person tbert; 13.06.2012

arrow_upward
0
arrow_downward

Я знаю, что это старый вопрос, но для справки вот некоторые результаты поиска github.

Простой поиск на github для «bloomfilter» дает массу результатов (для C):

https://github.com/search?q=extension%3Ac+bloomfilter&type=Code&ref=searchresults

Это только для ССЫЛКИ.

person Optimized Coder    schedule 02.06.2013

arrow_upward
0
arrow_downward

В этом проекте доступны несколько реализаций фильтра Блума и альтернативные алгоритмы: https://github.com/FastFilter/fastfilter_cpp

Охвачены обычный фильтр Блума, заблокированный фильтр Блума, фильтр с кукушкой, кодированный набор Голомба и другие. Это C++, но основные алгоритмы легко переносятся на C.

person Thomas Mueller    schedule 14.11.2018