[Moscow.pm] String to Hash

[Alex Kapranoff]

Отсутствие домена в базе будет самым худшим случаем в смысле
алгоритмической сложности и к тому же самым частным :)
Поэтому в таких системах часто в качестве первого уровня проверки
реализуют фильтры Блума, которые позволяют очень быстро узнать, что
домена нет в базе.
Рекомендую.

Саму базу я бы хранил просто в памяти в виде хэш-таблицы.

Не вполне ясно, откуда взялась задача из оригинального поста :) Весь
парсинг в таких системах делают оффлайново и заранее.

-- 
Alex Kapranoff.


2010/2/9 Kaltashkin Eugene <zhecka на gmail.com>:
> 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
> moscow-pm на pm.org | http://moscow.pm.org
>