[devel] Re: bloom filters

[Alexey Tourbin]

On Mon, Sep 19, 2005 at 12:18:34AM +0400, Alexey Tourbin wrote:
> Bloom filter используется, например, в spellchecker'ах, когда нужно
> захешировать все "правильные" слова.  Произвольное неправильное слово
> может с очень небольшой вероятность определиться как правильное.

Возвращаюсь к нашим баранам.  Есть список символов def "с адресом" --
эти символы провайдятся, и есть список символов ref "без адреса" --
которые, стало быть, кто-то должен провайдить.

$ awk -F'\t' '{print$NF}' def |sort -u >defsym
$ awk -F'\t' '{print$NF}' ref |sort -u >refsym
$ head defsym
A
A20Proc16
AAAAddAVPToMessage
AAABuildMsgBuffer
AAACloneAVP
AAAConvertAVPToString
AAACreateAVP
AAAFindMatchingAVP
AAAFreeAVP
AAAFreeMessage
$ wc -l defsym refsym
 1592688 defsym
 174130 refsym
 1766818 total
$

Ассиметрия в природе.  Провайдится гораздо больше, чем требуется.
Теперь попробуем воткнуть сюда фильтр Блума.

$ bloom -n 1592688 defsym >defsym.bf
$ ls -s1 defsym defsym.bf
56872 defsym
 1864 defsym.bf
$

Вот!  Меньше минимум на порядок, во всех отношениях.
Пробуем проверить malloc:

$ bloom -e malloc defsym.bf; echo $?
0
$ bloom -e Malloc defsym.bf; echo $?
1
$

Ну.  Работает.  Как и следовало ожидать.  То есть превентивная мера,
которую можно применить для проверки *всех* ELF'ов, а не только
публичных библиотек, состоит в том, что обнаруженные undefined symbols
из вывода `ldd -r' нужно попробовать отыскать в общем "отстойнике".
Если их там нет, то пакет нужно *точно* давить.  Кстати, false positive
в данном случае означает, что по ошибке можно пропустить пакет, который
следовало бы задавить, потому что символ в отстойники будет "найден"
(это в некотором смысле лучше, чем задавить пакет невинный).  Если
добавить в bloom.c элемент случайности, то сбой проверки будет одиночным
явлением.  (Вообще, по поводу сбоев: вероятность сбоев нужно оценивать
комплексно; например, учитывать вероятность выхода из строя сборочных
серверов, которая, кажется, выше статистического 1 процента.)
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Тип     : application/pgp-signature
Размер  : 189 байтов
Описание: =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Url     : <http://lists.altlinux.org/pipermail/devel/attachments/20050919/5ba6942d/attachment-0001.bin>