1

Тема: По якому алгоритму можна вирахувати пов'язані мітки

Раніше не звертав увагу на мітки на stackoverflow, але зараз, коли зайнявся власним схожим проектом, цікаво стало: може вже є якийсь відомий алгоритм підрахунку пов'язаних міток? І хоча мені цей алгоритм зараз не потрібен, бо в моєму випадку це можна значно простіше зробити, але спортивний інтерес все таки є.

Для прикладу візьмемо мітку JavaScript. На даний момент stackoverflow каже, що питань з цією міткою 809 050 штук, і в правій колонці трохи нижче надає пов'язані мітки: jquery × 283354, html × 143526 ... - це кількість питань на stackoverflow, які йдуть в поєднанні з вже вибраною міткою JavaScript.

Якщо далі вибрати, скажімо, angularjs, то видається інший список пов'язаних міток. І якщо вибирати так само далі потрібні мітки, то кількість варіантів скорочується аж до одиниць.

Все було б просто, якщо б статистику потрібно було вирахувати для невеликої кількості поєднання: пари, трійки, четвірки, чи п'ятірки міток, які згадуються у питаннях одночасно.

Але коли маємо навіть 10 міток, то вирахувати поєднання різних їх варіантів хоча й не дуже складно, але вже не просто. Що вже тоді казати коли на ресурсі тисячі міток. Тут мабуть без спеціального математичного алгоритму не обійтись.

Ніхто не в курсі як це робиться?

2 Востаннє редагувалося VTrim (20.03.2015 10:29:57)

Re: По якому алгоритму можна вирахувати пов'язані мітки

Я б зробив так..
Наприклад є таблиця articles з полем mitka,в це поле записувати мітки через кому html,javascript,php.

При пошуку зробив би вибірку по полю mitka через оператор LIKE = 'javascript'
Під час виводу результатів, через explode(',', $sql['mitka']) створював би масив з міток.
Потім через foreach записував би кожен елемент з поля (створений через explode) в масив $arr,попередньо видаливши запис з javascript через unset().

А після проходу while цикла виводу..
print_r(array_count_values($arr));

Що вивело б новий масив з кількістю кожного елемента

Array ( [html] => 2  [php] => 3)
Де повязаних міток з html - 2, php - 3

Подякували: ktretyak1

3

Re: По якому алгоритму можна вирахувати пов'язані мітки

Я не до кінця розумію завдання, особливо в місці, де з'являються пари й трійки. Можете якось детальніше пояснити?

4

Re: По якому алгоритму можна вирахувати пов'язані мітки

По-перше, навіть якщо припустити, що "спорідненість" міток визначається не модераторами за статистикою, а автоматично, все одно нам потрібні тільки пари - якщо мітки "c++", "stl" та "iostream" часто йдуть групами, то ми все одно цього не бачимо, нам достатньо тільки пар "c++"/"stl", c++"/"iostream" та "stl"/"iostream".
Ну а по-друге, нікому не треба отримувати "живу" статистику, що змінюється щохвилини - співвідношення за добу буде практично таким самим, максимум якась мітка на одну позицію зсунеться. Тому достатньо обчислювати цю статистику пар раз на добу.

Подякували: quez1

5

Re: По якому алгоритму можна вирахувати пов'язані мітки

Це, мабуть, як індексація сторінок пошуковими машинами.

6

Re: По якому алгоритму можна вирахувати пов'язані мітки

Ваш приклад дуже схожий на задачу зв’язності. Почитайте Седжвіка "Фундаметнальні алгоритми на С++", теми 1.2 та 1.3. Там описані кілька алгоритмів розв’язку такої задачі. Можливо, на stackoverflow використовуюється модифікація алгоритму виваженого швидкого об’єднання (weighted quick - union).

7 Востаннє редагувалося ktretyak (20.03.2015 22:19:23)

Re: По якому алгоритму можна вирахувати пов'язані мітки

VTrim написав:

Я б зробив так..
Наприклад є таблиця articles з полем mitka, в це поле записувати мітки через кому html,javascript,php.

При пошуку зробив би вибірку по полю mitka через оператор LIKE = 'javascript'
Під час виводу результатів, через explode(',', $sql['mitka']) створював би масив з міток...

Тю, точно!

Я мабуть не бачив цієї ідеї зразу, бо був впевнений, що треба наперед перерахувати всі варіанти та зберігати їх десь в кеші. В такому б разі, дійсно, потрібно було б знати всі наперед варіанти, і потрібен був би не простий алгоритм їх отримання.

Але ж можна, як і показав VTrim, динамічно це все обраховувати.
Припустимо в нас є денормалізована таблиця all_tags, де зберігаються всього два поля: tag_name - назва мітки, та string_tags - рядкове представлення зчіплених міток типу javascript,angularjs,... (в розрізі одного питання на stackoverflow).

Тепер наш запит хоча й буде трохи затратним в плані ресурсів сервера, бо є like '%...%', але простеньким і правильним

select
  tag_name
  ,count(*) as total_questions
from all_tags
where string_tags like '%javascript%'
  and string_tags like '%angularjs%'
group by
  tag_name
order by
  total_questions desc
limit 100

Капець =)

8 Востаннє редагувалося ktretyak (29.04.2015 20:38:34)

Re: По якому алгоритму можна вирахувати пов'язані мітки

Оскільки в табличці all_tags декілька мільйонів рядків, то пошук типу like '%...%', швидше за все, не використовують.

Простіше в таблиці all_tags замість поля string_tags додати поле question_id - ідентифікатор питання. Після чого побудувати кластерний індекс по полям question_id, tag_name.

Тепер просто під'єднуємо цю таблицю саму до себе з різними вибірками:

select
  other_tags.tag_name
  ,count(*) as total_questions
from all_tags as tag_1
  join all_tags as tag_2
    on tag_1.question_id = tag_2.question_id
  join all_tags as other_tags
    on tag_2.tag_name = other_tags.tag_name
where tag_1.tag_name = 'javascript'
  and tag_2.tag_name = 'angularjs'
group by
  other_tags.tag_name
order by
  total_questions desc
limit 100

9 Востаннє редагувалося ktretyak (24.03.2015 14:48:33)

Re: По якому алгоритму можна вирахувати пов'язані мітки

До речі, очевидно що на московському hashcode.ru до цього не додумались. У них видається загальна кількість питань по певній мітці, замість кількості питань в поточному контексті. Відповідно - відбувається не релевантне сортування до даного контекста.

Слабенько, слабенько...

10

Re: По якому алгоритму можна вирахувати пов'язані мітки

Питання до тих, хто знайомий з аналітичними кубами: задачу з даної теми можна легше вирішити за допомогою кубів, чи ні?

11

Re: По якому алгоритму можна вирахувати пов'язані мітки

Між іншим, кому треба буде реалізовувати інтерфейс з багатьма фільтрами для вибору товарів, то динамічний фільтр можна зробити точно по такому ж самому принципу.

Наприклад, на hotline.ua дуже зручний динамічний фільтр, який після вибору певних опцій показує решту доступних опцій. Тільки замість ID запитання (в попередньому SQL-запиті) треба підставляти ID товару, а замість міток - опції товару.

12

Re: По якому алгоритму можна вирахувати пов'язані мітки

На stackoverflow всього майже 27 млн. міток

Подякували: Chemist-i1