Алгоритм, который ищет связанные элементы на основе общих тегов

Давайте рассмотрим вопросы StackOverflow. Каждый из них имеет несколько назначенных тэгов. Как построить алгоритм, который найдет связанные вопросы, исходя из того, сколько общих тегов у них (отсортировано по числу общих тегов)?

На данный момент я не могу думать ни о чем лучше, чем просто выбирать все вопросы, которые содержат по крайней мере один общий тег в массиве, а затем перебирать их, назначая количество общих тегов для каждого элемента, а затем сортируя этот массив.

Есть ли более умный способ сделать это? Идеальное решение - это один запрос sql.

Ответ 1

Это может быть так же плохо, как O (n ^ 2), но оно работает:

create table QuestionTags (questionid int, tag int);

select q1.questionid, q2.questionid, count(*) as commontags
from QuestionTags q1 join QuestionTags q2 
where q1.tag = q2.tag and q1.questionid < q2.questionid
group by q1.questionid, q2.questionid order by commontags desc;

Ответ 2

У меня не было времени оптимизировать предложение WHERE IN(), которое медленно, как смерть. Я также не хотел включать индексы или указывать двигатель или сортировки, но это, надеюсь, сделает трюк. Пожалуйста, укажите любые ошибки, поскольку я не проверял этот неряшливый код:

CREATE TABLE question (
    id INT(11) UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
    title VARCHAR(255) NOT NULL,
    question MEDIUMTEXT
);

CREATE TABLE question_rel_tag (
    id INT(11) UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
    question_id INT(11) UNSIGNED NOT NULL,
    tag_id INT(11) UNSIGNED NOT NULL
);

CREATE TABLE tag (
    id INT(11) UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
    name VARCHAR(20) NOT NULL
);

SELECT question.id, question.title, question.question, count(tag.id) AS `count`
FROM question
INNER JOIN question_rel_tag ON (question.id = question_rel_tag.question_id)
INNER JOIN tag ON (question_rel_tag.tag_id = tag.id)
WHERE question.id != YOUR_QUESTION_ID_HERE
AND tag.id IN 
    (SELECT tag.id FROM question
    INNER JOIN question_rel_tag ON (question.id = question_rel_tag.question_id)
    INNER JOIN tag ON (question_rel_tag.tag_id = tag.id)
    WHERE question.id = YOUR_QUESTION_ID_HERE)
GROUP BY tag.id
ORDER BY `count` DESC

Ответ 3

Предполагая таблицу Questions с столбцом первичного ключа Id, таблицу Tags с столбцом первичного ключа Id тоже и таблицу соединений QuestionTags с составным первичным ключом QuestionId и TagId ссылаясь на первичные ключи двух предыдущих таблиц, следующий запрос даст желаемый результат (в SQL Server 2005).

SELECT q1.Id AS Id1, q2.Id AS Id2,
   (SELECT COUNT(*) FROM QuestionTags qt1 INNER JOIN QuestionTags qt2
    ON qt1.QuestionId = q1.Id AND qt2.QuestionId = q2.Id AND qt1.TagId = qt2.TagId) AS TagCount
FROM Questions q1 INNER JOIN Questions q2 ON q1.Id < q2.Id
ORDER BY TagCount DESC

Это может быть улучшено до следующего.

SELECT qt1.QuestionId AS Id1, qt2.QuestionId AS Id2, COUNT(*) AS TagCount
FROM QuestionTags qt1 INNER JOIN QuestionTags qt2
ON qt1.QuestionId < qt2.QuestionId AND qt1.TagId = qt2.TagId
GROUP BY qt1.QuestionId, qt2.QuestionId
ORDER BY TagCount DESC

Ответ 4

Предположим, что у меня есть следующее:

Таблица объектов с меткой:

Taggable

id, stuff

Таблица тегов:

Tag

id, tagName

Таблица соединений с тегами, связанными с тем, что Taggables

TagInfo

taggableId tagId

Тогда:

SELECT COUNT(Taggable_1.id) AS score, Taggable_1.id FROM dbo.Taggable INNER JOIN dbo.TagInfo ON dbo.Taggable.id = dbo.TagInfo.taggableId INNER JOIN dbo.TagInfo TagInfo_1 ON dbo.TagInfo.tagId = TagInfo_1.tagId INNER JOIN dbo.Taggable Taggable_1 ON TagInfo_1.taggableId = Taggable_1.id WHERE (dbo.Taggable.id = 1) AND (Taggable_1.id <> 1) GROUP BY Taggable_1.id

присоединяется к таблице tag-join против самого себя (для запрошенного вопроса id; 1 в приведенном выше sql) и подсчитывает результаты для оценки.

Ответ 5

select *
     , count(t.*) as matched_tag_count
  from questions q
  join tags_to_questions t
    on t.question_id = q.id
   and t.tag_id in (select tag_id
                      from tags_to_questions
                     where question_id = ?)
group
    by q.id
order
    by matched_tag_count desc