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 байта на символ.