[devel] bloom filters

[Alexey Tourbin <at@altlinux.ru>]

[-- Attachment #1.1: Type: text/plain, Size: 2497 bytes --]

On Sun, Sep 18, 2005 at 02:02:51PM +0400, Alexey Tourbin wrote:
> Эффективный reverse lookup без полной таблицы можно реализовать на
> основе bloom filters.  Я только пока не знаю, в какую сторону ошибка
> будет.  Сейчас попробую сделать.

bloom filter -- это специальный бинарный хеш, который позволяет
проверить принадлежность элемента к множеству, не имея при этом (на
стадии проверки) самого множества элементов.  Множество элементов
нужно только на стадии создания хеша.

Существует вероятность ошибки типа "false positive" -- произвольный
элемент определяется как принадлежащий к множеству, однако же этот
элемент не был предъявлен на стадии создания хеша (не входил в множество
элементов).  При расходе памяти 2 байта на элемент вероятность false
positive статистически меньше 1%.  То есть в ряде случаев bloom filters
позволяют минимум на порядок сократить время проверки/расходы памяти,
если сама ошибка такого рода допустима.

Ошибки "false negative" (то есть определение элементов, изначально
принадлежащих множеству, как не принадлежащих этому множеству)
не существует.

Bloom filter используется, например, в spellchecker'ах, когда нужно
захешировать все "правильные" слова.  Произвольное неправильное слово
может с очень небольшой вероятность определиться как правильное.

Подробнее об алгоритме и обо всём остальном -- по ссылкам в гугле.

Теперь о реализациях.  Нормальной реализации нету.  Есть перловый модуль
Bloom::Filter, но он "не тянет" большое число элементов (несколько тысяч
тянет нормально, но нужно порядка миллиона).  К тому же там сделано
безграмотно по части математики.  C/C++ реализацию я искал, но не нашёл.
Поэтому я написал свою упрощенную реализацию.  Работает это так:

$ gcc -o bloom bloom.c -Wall -lm -lssl
$ wc -l /usr/share/dict/words
45427 /usr/share/dict/words
$ ./bloom -n 50000 /usr/share/dict/words >words.bf
$ ls -sH1 /usr/share/dict/words words.bf
400 /usr/share/dict/words
 60 words.bf
$ head /usr/share/dict/words
ALGOL
ANSI
ARCO
ARPA
ARPANET
ASCII
Aarhus
Aaron
Ababa
Abba
$ ./bloom -e ALGOL words.bf; echo $?
0
$ ./bloom -e ANSI words.bf; echo $?
0
$ ./bloom -e ALGOLANSI words.bf; echo $?
1
$ ./bloom -e ANSIALGOL words.bf; echo $?
1
$

Я завтра его наверное ещё напильником и упакую.  Ошибки я пока не искал;
главное, что работает. :)

То есть к чему это всё: 350-метровый дамп ELF-символов -- это ещё не
конец света.  На самом деле всё пакуется из расчета 2 байта на символ.

[-- Attachment #1.2: bloom.c --]
[-- Type: text/plain, Size: 2946 bytes --]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <openssl/sha.h>
#include <getopt.h>

typedef struct BloomFilter {
	size_t n;	/* capacity */
	double p;	/* false positive rate */
	size_t m;	/* number of bits in vector */
	size_t k;	/* number of hash functions */
	char v[1];
} BF;

BF *BF_new(size_t n, double p)
{
	BF *bf;
	size_t m, k, nb;
	assert(n > 0 && p > 0 && p < 1);
	m = n * log(p) / log(0.6185);
	k = log(p) / log(0.5);
	assert(m > 0 && k > 0);
	nb = sizeof(BF) + m / 8;
	bf = malloc(nb);
	assert(bf);
	memset(bf, 0, nb);
	bf->n = n; bf->p = p;
	bf->m = m; bf->k = k;
	return bf;
}

BF *BF_load(FILE *fp)
{
	size_t n;
	BF *bf = malloc(sizeof(BF));
	assert(bf);
	n = fread(bf, sizeof(BF), 1, fp);
	assert(n == 1);
	assert(bf->n > 0 && bf->p > 0 && bf->p < 1);
	assert(bf->m > 0 && bf->k > 0);
	bf = realloc(bf, sizeof(BF) + bf->m / 8);
	assert(bf);
	rewind(fp);
	n = fread(bf, sizeof(BF) + bf->m / 8, 1, fp);
	assert(n == 1);
	return bf;
}

void BF_save(BF *bf, FILE *fp)
{
	size_t nb = sizeof(BF) + bf->m / 8;
	size_t n = fwrite(bf, nb, 1, fp);
	assert(n == 1);
}

void BF_set(BF *bf, size_t n)
{
	assert(bf->m >= n);
	bf->v[n / 8] |= (1 << (n % 8));
}

int BF_isset(BF *bf, size_t n)
{
	assert(bf->m >= n);
	return bf->v[n / 8] & (1 << (n % 8));
}

static
size_t rehash(const char digest[], int i)
{
	size_t hash = digest[(i + 1) % 20]
		+ (digest[(i + 2) % 20] << 8)
		+ (digest[(i + 3) % 20] << 16)
		+ (digest[(i + 4) % 20] << 24);
	hash ^= digest[(i + 6) % 20]
		+ (digest[(i + 7) % 20] << 8)
		+ (digest[(i + 8) % 20] << 16)
		+ (digest[(i + 9) % 20] << 24);
	return hash;
}

void BF_add(BF *bf, const char *str, size_t len)
{
	char digest[20]; int i;
	SHA1(str, len, digest);
	for (i = 0; i < bf->k; i++) {
		size_t hash = rehash(digest, i);
		BF_set(bf, hash % bf->m);
	}
}

int BF_exists(BF *bf, const char *str, size_t len)
{
	char digest[20]; int i;
	SHA1(str, len, digest);
	for (i = 0; i < bf->k; i++) {
		size_t hash = rehash(digest, i);
		int set = BF_isset(bf, hash % bf->m);
		if (!set) return 0;
	}
	return 1;
}

int main(int argc, char *argv[])
{
	size_t n = 1024;
	double p = 0.01;
	char *e = NULL;
	int c;
	while ((c = getopt(argc, argv, "n:p:e:")) != -1) {
		switch (c) {
		case 'n':
			n = strtoul(optarg, NULL, 10);
			break;
		case 'p':
			p = atof(optarg);
			break;
		case 'e':
			e = optarg;
			break;
		default:
			exit(2);
		}
	}
	if (optind + 1 != argc) {
		fprintf(stderr, "arg count\n");
		exit(2);
	}
	if (e) {
		int exists;
		FILE *fp = fopen(argv[optind], "r");
		assert(fp);
		BF *bf = BF_load(fp);
		exists = BF_exists(bf, e, strlen(e));
		exit(!exists);
	} else {
		char line[1024];
		BF *bf = BF_new(n, p);
		FILE *fp = fopen(argv[optind], "r");
		assert(fp);
		while (fgets(line, sizeof(line), fp)) {
			int len = strlen(line);
			if (line[len - 1] == '\n')
				len--;
			BF_add(bf, line, len);
		}
		BF_save(bf, stdout);
	}
	return 0;
}

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]