За прошедшую неделю я успел пообщаться с нашим патентным ведомством, которое сказало мне, что алгоритмы не патентуют, патентуют готовые прототипы. Предложили подогнать мою заявку под "Программу для базы данных для ЭВМ", но я не стал тратить время. Таким образом продолжаю серию постов, кратко рассказывающих как формируется ТОП30.
Содержание уже опубликованных заметок

• пост 4 (про ссылки и фильтры)
• пост 3 (эксперимент)
• пост 2 (про параметры)
• пост 1 (причины закрытия)
• Общая идеология ТОП30

Сегодня я приведу алгоритм первичной сортировки и объясню некоторые моменты. Если Вы читали предыдущие заметки, то должны знать, что алгоритм первичной сортировки нужен только для того, чтобы выбрать порядок в котором записи будут анализироваться на предмет прохождения через фильтры. Собственно сам package первичной сортировки:

Copy Source | Copy HTML

1. -- 3) проставляем максимумы
2. CALL top_setmaxs();
3.  
4. select *,top_doubles(temp.linkto) as dd
5.  from (
6. select
7. d.linkto, d.blogtype,d.blogname,d.title, d.body,d.short,d.comments,d.links,d.when,
8. (
9.     if((select count(*) from top_rawdata where blogname=d.blogname)>20,0,1)*
10.     (
11.         d.visits24/m.visits24 + d.links/m.links +
12.         if(d.blogtype='YaRu',if(d.commenters>d.links,d.commenters-d.links,0),d.commenters)/m.commenters +
13.         if(d.blogtype='YaRu',if(d.comments>d.links,d.comments-d.links,0),d.comments)/m.comments
14.     )
15.     *(select 1-(top_daysinheap(d.blogname)-1)/20 from dual)
16.     *if(isnull(h.atyear),1,1-h.atyear/500)
17. )
18. as value
19. from top_rawdata d
20. inner join top_maxs m on (m.blogtype=d.blogtype and m.community=d.community)
21. left join top_intop t on t.blogname=d.blogname -- убедимся что не в топе!
22. left join top_intheme b on b.blogname=d.blogname -- убедимся что не в бане
23. left join arme_top_users h on h.blogname=d.blogname
24.     where short!=''
25.     and b.themeid is null
26.     and t.when is null
27.     and baned='0'
28.     and (((d.visits24>0 or d.blogtype!='BlogsMail') and (d.links>0 or d.blogtype='Livejournal') and d.commenters>0)) -- краевое условие снизу
29.     and d.when>DATE_SUB(NOW(),interval 3 day) -- бесполезно, но пусть будет
30.     and m.count > 10 -- больше 10 постов в группе, иначе нет выбора.
31.     and ((d.visits24/m.visits24)/ (d.links/m.links +
32.         if(d.blogtype='YaRu',if(d.commenters>d.links,d.commenters-d.links,0),d.commenters)/m.commenters +
33.         if(d.blogtype='YaRu',if(d.comments>d.links,d.comments-d.links,0),d.comments)/m.comments) < 3)
34. ) temp
35. order by temp.value desc limit 20;
36.  

Вначале (на строчке 2) считаются максимумы (+1 чтобы не было нулей) для текущего состояния ТОПа, сгруппировано по типу платформы и по личный блог или сообщество. Далее на строчках 9-17 считается value, которая и характеризует сравнение проекций на единичный вектор. Почему суммы, а не квадратуры, как это должно было быть, если бы я чисто сравнивал проекции - доказывается просто. Сравнение знакопостоянных функций равносильно сравнению интегралов от производных по одинаковому промежутку времени. Далее, так как я беру параметры за все время существования записи, то в начальный момент значение подъинтегральной функций равно нулю и остается сравнить лишь значение производной от суммы квадратов в текущий момент времени. Естественно на двойку я сокращаю и остается линейная сумма. Такой переход сильно сокращает вычисления.

Далее, как вы видите для блогов с YaRu введено понижение коэффициентов - это вызвано тем, что внутренняя ссылка является также комментарием. Более того, берется не чистое число комментариев, а число комментариев минус число комментаторов, чтобы базисные вектора были наиболее независимыми.

Следующий момент - строчка 15 - функция top_daysinheap - считает количество дней, в течении которых записи этого блогера попадали в рассмотрение. Чем чаще попадает, тем меньше у него шансов попасть в ТОП. Аналогично для строчки 16 - смотрятся все ТОПы блогера за год, чем их больше тем позднее мы будем анализировать записи блогера. Если автор был в ТОПе 500 раз за год, то у него уже нет шансов попасть в ТОП в этом году.

Переходим к условию Where. Видим, что для попадания в рассмотрение вашей записи нужно

• иметь текст какой-то (строчка 24)
• не затрагивать активную тему дня (строчка 25)
• не быть в уже в ТОПе (строчка 26)
• не быть забаненным автоматически (например, если нет русских слов, строчка 27)
• нулевой фильтр представлен в строчке 28 - пока без ссылок могут в топ попадать лишь записи ЖЖ, это так как есть нехватка хороших записей вцелом и так как мало записей имеет ссылки до того как попадают в ТОП, если не являются накрутками или трансляциями.
• запись должна быть сделана за последние 3 дня. (выходные 2 дня, а многие читают и комментят блоги только с работы, (строчка 29))
• записей с этой блогплатформы должно быть более 10, чтобы я был уверен, что беру лучшее из нескольких, а не единственную запись, которая и дает максимум.(строчка 30) Вероятно отсутствие такого ограничения и позволяло lleo постоянно попадать в ТОП даже не имея комментариев, так как у него уникальная блогплатформа не имеющая аналогов. Сейчас я отношу его к общей группе StandAlone блогам.
• посещения (переходы с Яндекса) не должны вносить наибольший вклад в значение (строчка 31). Чтобы ТОП и темы дня не влияли на ТОП.
• И чуть не забыл (строчка 9) - если более 20 постов за короткий промежуток времени, то тоже исключаем из рассмотрения

Вот пока и все. Другой формулы первичной сортировки не вывести, разве что коэффициенты подкрутить, но опять же ввержу окажутся теже записи, соответствующие экстремальным векторам в четырехмерном пространстве.

И в заключение, наиболее распространенная ошибка в том, чтобы составив алгоритм тут же смотреть какие записи он дает в первых 30. Надо помнить, что все у нас растянуто во времени и хороших записей в рассмотрении в конкретный момент бывает не сразу 30, а 5-10, которые фильтры и вычленяют на следующих этапах. А со временем индексирования записи добавляются в кучу, что позволяет нормально сформировать топ30.
Отвечаю на вопросы в блоге на flashr.ya.ru.