Отсутствие домена в базе будет самым худшим случаем в смысле алгоритмической сложности и к тому же самым частным :) Поэтому в таких системах часто в качестве первого уровня проверки реализуют фильтры Блума, которые позволяют очень быстро узнать, что домена нет в базе. Рекомендую.
Саму базу я бы хранил просто в памяти в виде хэш-таблицы. Не вполне ясно, откуда взялась задача из оригинального поста :) Весь парсинг в таких системах делают оффлайново и заранее. -- Alex Kapranoff. 2010/2/9 Kaltashkin Eugene <[email protected]>: > 09.02.2010 16:08, Denis Evdokimov пишет: >> >> Не точно выразился, >> 1. есть ли возможность поменять формат данных >> 2. можно ли получить небольшой кусочек реальных данных >> > > Берём файл со списком доменов. > mercury:/usr/local/squid/scripts$ grep 'ac\.th' files/malwaredomains.txt > assess.vet.cmu.ac.th:malware > bu.ac.th:malware > cw.ubru.ac.th:rfi > thailocal.sru.ac.th:gumblar > econ1.nida.ac.th:RFI > > Цель задачи: минимизировать поиск по базе доменов(хешей доменов). > домен может быть 25 уровня, а то и 100. Но это неважно, нужно знать в каком > уровне домена может находиться текущий проверяемый > домен и какая категория ему присвоится. > Я выделяю домен второго уровня и использую его как справочный ключ с > информацией о уровнях на которых могут находиться > определенные типы доменов. > В нашем случае это "ac.th". Для наглядности я оставил буквенные значения > доменов вместо хешей(поиск по хешам быстрее, чем перебор доменов по уровням) > Чтобы не было путаницы я считаю количество точек внутри имени домена, так > проще и быстрее и разруливается одним регеспом. > таким образом домен, ac.th это первый уровень, aa.ac.th это второй уровень, > bb.aa.ac.th это третий уровень и т.д. > в ключевом хеше мне нужно сохранить в каком-то виде информацию о вышестоящих > уровнях которые у меня есть и на которых присутствует какая-то > категория. Храним мы не домены, а ХЕШИ(чтобы не было путаницы) > > Скажем есть домен: > porno.ru - porno - 1 уровень > css.porno.ru - pics - 2 уровень > elena.berkova.img.porno.ru - porno - 4 уровень > img.porno.ru - pics - 2 уровень > > На запрос berkova.img.porno.ru я должен вернуть какую-то категорию для > блокировки. > Видим что url третьего уровня, значит анализ будет urlов ниже третьего > уровня. > url третьего уровня у нас нет, поэтому анализируемый url обрезается до > второго уровня и проверяется (img.porno.ru) > Ему вернётся категория "pics". если бы категория для "img.porno.ru" не была > определена, то категория стала бы "porno", > т.к. рекурсия включается только в том случае если на запрос для url уровня > выше первого не вернулся ответ. > Если мы запросим paris.hilton.img.porno.ru, то ответ будет pics. при этом > будет анализ всех уровней кроме третьего(его нет), т.е. сначала 4й, потом > сразу 2й. > Если в ключевом домене нет перечисления уровней, но присвоена категория, > значит все поддомены любых уровней попадают > в эту категорию. > > Ну и вот результат по начальному примеру(уже автоматизированный поиск) > > ac.th 4=1,3=114,2=1 > assess.vet.cmu.ac.th 1 > bu.ac.th 1 > cw.ubru.ac.th 114 > econ1.nida.ac.th 114 > thailocal.sru.ac.th 100 > > 1,114 и 100 это номера категорий malware,rfi и gumblar соответственно во > внутренней базе имён. > 4,3,2 это номера уровней на которых были найдены категории. > Понимаю, что сумбурно, но для меня самого эта схема была тяжела для > понимания первое время. > За счёт того, что запросов много, то рекурсия разделения домена на части и > получения списка уровней > должна быть очень быстрой, отсюда и пост пошёл. > > > > -- > Moscow.pm mailing list > [email protected] | http://moscow.pm.org > -- Moscow.pm mailing list [email protected] | http://moscow.pm.org
