Об отпечатках пальцев.
Одна из моих любимых технологий в новом фильтре это "отпечатки пальцев". База данных фильтра заполняется специальным образом обработанными "отпечатками" спэм сообщений. Обрабатывая е-мэйл, фильтр снимает с него отпечатки и сравнивает с тем, что ему уже известно. Если находится соответствие - е-мэйл классифицируется как спэм.
В основе технологии лежат исследования Марка Манасси и др. Подробнее вот здесь. А также, базисная работа. Я позволю себе быстро пробежаться по основам.
Допустим имеются сообщения M1 и M2. Допустим также, что мы их можем уникально определить множеством характеристик (например - слов, содержащихся в каждом сообщении. Без учета комманд HTML, пунктуации, приложений). Назовем эти множества Φ1 и Φ2. Определим сходство между M1 и M2 следующим образом:
(Это соответствует нашему интуитивному M1 и M2 "примерно похожи". Чем ближе пересечение к объединению множеств характеристик - тем более "похожи" сами документы).
Далее. Допустим, что из любого сообщения Мi, мы можем извлечь единственную характеристику φi из множества характеристик Φi, такую что для любых двух Мi, Мj :
Если у нас есть r таких алгоритмов выборки, мы можем применить их к каждому множеству Фi r раз, собрать их в вектора Фir и посчитать количество почленных совпадений между двумя такими векторами. Таким образом получаем:
Т.е. если допустим r = 100, количество совпадений будет в точности равно проценту сходства.
Если вас интересует дальнейшее развитие событий (а здесь я видимо поднял больше вопросов чем дал ответов), можете зайти на ссылки данные сверху. Но зерно всего вышесказанного вот в чем:
Сравнение разных по размеру документов, после обработки, сводится к почленному сравнению двух векторов одинакового, заданного размера, и т. о. число сравнений всегда является константой.
После дальнейшей обработки описанных выше векторов, мы сводим сравнения к нескольким просмотрам хэш-таблицы. Это позволяет фильтру быстро манипулировать огромными базами данных с отпечатками.
