Алгоритм поиска связанных элементов на основе общих тегов - PullRequest
Новая
       24

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

11 голосов
/ 12 октября 2009

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

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

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

Ответы [ 5 ]

8 голосов
/ 12 октября 2009

Это может быть так же плохо, как 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 голосов
/ 12 октября 2009

У меня не было времени на оптимизацию предложения 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
1 голос
/ 13 октября 2009 
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
1 голос
/ 13 октября 2009

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

Таблица тегируемых объектов:

Taggable

id, stuff

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

Tag

id, tagName

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

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 против себя (для идентификатора запрашиваемого вопроса; 1 в приведенном выше sql) и подсчитает результаты для оценки.

1 голос
/ 13 октября 2009

Предполагается, что таблица 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
...