Вывод меток сайта деревом.
Вывод меток сайта деревом.
5 февраля 2011 г.
Sadovnik
Просмотров: 186
RSS
Программирование
php, вывод меток, таксономия, фолксономияРазбивку постов на сайте можно осуществлять используя категории и метки. Эти два подхода имеют свои плюсы и минусы.
При помощи категорий можно создавать четкую иерархию страниц: т. н. Таксономия. Однако, необходимо ломать голову над категоризацией. К тому же, перегруженность иерархии вызовет у пользователя проблемы с нахождением нужной информации. Еще один минус категорий - они плохо подходят для совместной классификации информации, ибо каждый видит классификацию по-своему.
Альтернативой категориям есть метки: т. н. Фолксономия (англ. folksonomy, от folk — народный + taxonomy — таксономия). Метки можно присваивать спонтанно и они отлично подходят для совместной классификации информации.
При достаточно большом количестве меток облако меток становится не очень
приглядное. Категории же сохраняют строгий порядок.
Как же совместить достоинства меток и категорий, придав меткам вид древовидной структуры как у категорий.
Наверняка, можно выделить более важные метки и менее важные, от них зависимые. Как же это сделать? Попытаюсь придумать алгоритм для реализации на php.
Имеем массив меток
$tags = array(tag1, tag2, tagn);
Имеем записи p1 ... pm.
Можно построить матрицу попадания метки в запись
P(i,j) = 1, если метка i принадлежит посту j.
P(i,j) = 0, иначе.
Далее, вычисляем мощность каждой метки mi - кол-во постов, в которые попадает метка.
Вычисляем матрицу связности меток
A(i,j) = у скольких постов метки i и j присутствуют одновременно.
Можно также ввести понятие "зависимоть меток" и вычислить матрицу зависимости меток.
C(i,j) = 1, если метки i и j зависимы.
C(i,j) = 0, если метки i и j не зависимы.
Причем зависимость меток и связность могут быть не тождественными понятиями.
Зависимость меток можно определять например так:
Метки считаются зависимы если их связность больше x, где x может быть как 0 (тогда зависимость и связность тождества) так и больше.
C(i,j) = 1, если A(i,j)>=x
C(i,j) = 0, иначе.
Еще один способ - учитывать мощность меток, например
C(i,j) = 1, если A(i,j)>=x*mi*mj
Способ вычисления зависимости/независимости меток будет влиять на вид дерева меток.
Если предварительно отсортировать множество меток по убыванию мощности, то самой мощной будет самая первая метка. Тогда самая мощная найдется так:
a_tag = $tags[0];
function get_tags_group($tags , $C1)
где, $C1 - вычисленная каким-либо образом матрица зависимости меток
function get_a_tags_array($tags , $C2)
где, $C2 - вычисленная каким-либо образом матрица зависимости меток
function get_tags_way($tags , $tag)
Путь меток данной метки - это все метки, которые в узлах, через которые мы проходим к метке и все дочерние метки.
Это нам понадобится при дополнении дерева.
Логично будет выглядеть попадание метки одновременно в разные ветки дерева. Для этого дополним дерево меток.
Для каждой метки определим множество с ней связанных и множество меток, входящих в путь метки.
Исключим из множества связанных меток все метки, которые уже вошли в путь и дополним узел ветками из оставшихся.
Реализацию этого алгоритма оставлю на потом.
При помощи категорий можно создавать четкую иерархию страниц: т. н. Таксономия. Однако, необходимо ломать голову над категоризацией. К тому же, перегруженность иерархии вызовет у пользователя проблемы с нахождением нужной информации. Еще один минус категорий - они плохо подходят для совместной классификации информации, ибо каждый видит классификацию по-своему.
Альтернативой категориям есть метки: т. н. Фолксономия (англ. folksonomy, от folk — народный + taxonomy — таксономия). Метки можно присваивать спонтанно и они отлично подходят для совместной классификации информации.
При достаточно большом количестве меток облако меток становится не очень
приглядное. Категории же сохраняют строгий порядок.
Как же совместить достоинства меток и категорий, придав меткам вид древовидной структуры как у категорий.
Наверняка, можно выделить более важные метки и менее важные, от них зависимые. Как же это сделать? Попытаюсь придумать алгоритм для реализации на php.
Как мы можем формализовать имеющиеся данные.
Имеем массив меток
$tags = array(tag1, tag2, tagn);
Имеем записи p1 ... pm.
Можно построить матрицу попадания метки в запись
P(i,j) = 1, если метка i принадлежит посту j.
P(i,j) = 0, иначе.
Далее, вычисляем мощность каждой метки mi - кол-во постов, в которые попадает метка.
Вычисляем матрицу связности меток
A(i,j) = у скольких постов метки i и j присутствуют одновременно.
Можно также ввести понятие "зависимоть меток" и вычислить матрицу зависимости меток.
C(i,j) = 1, если метки i и j зависимы.
C(i,j) = 0, если метки i и j не зависимы.
Причем зависимость меток и связность могут быть не тождественными понятиями.
Зависимость меток можно определять например так:
Метки считаются зависимы если их связность больше x, где x может быть как 0 (тогда зависимость и связность тождества) так и больше.
C(i,j) = 1, если A(i,j)>=x
C(i,j) = 0, иначе.
Еще один способ - учитывать мощность меток, например
C(i,j) = 1, если A(i,j)>=x*mi*mj
Способ вычисления зависимости/независимости меток будет влиять на вид дерева меток.
Какие функции над множеством меток мы можем определить.
1. Найти в множестве меток $tags самую мощную.
Если предварительно отсортировать множество меток по убыванию мощности, то самой мощной будет самая первая метка. Тогда самая мощная найдется так:
a_tag = $tags[0];
2. Разбить множество меток на подмножества независимых меток.
function get_tags_group($tags , $C1)
где, $C1 - вычисленная каким-либо образом матрица зависимости меток
3. Выделить из множества меток подмножество зависимых от метки A-tag меток.
function get_a_tags_array($tags , $C2)
где, $C2 - вычисленная каким-либо образом матрица зависимости меток
4. Определить множество меток, входящих в путь метки $tag.
function get_tags_way($tags , $tag)
Путь меток данной метки - это все метки, которые в узлах, через которые мы проходим к метке и все дочерние метки.
Это нам понадобится при дополнении дерева.
Рекуррентная функция построения дерева меток.
- function get_tag_tree($tags , &$C1 , &$C2) // использовать матрицу зависимости мы будем в двух случаях // для каждого можно свой вариант ее вычисления{ if (!$tags) return false; if (count($tags)==1) return array($tags[0]=>false); $tags_tree = array(); // дерево на текущей итерации пусто $groups = get_tag_group($tags, $C1); // попытаемся разбить на группы if ($groups) // если это получилось { foreach ($groups as $group) // для каждой группы строим дерево меток { $current_tree = get_tag_tree($group , $C1 , $C2); if ($current_tree) $tags_tree = $current_tree; } } else // разбить на группы независимых неполучилось // может разбивать на группы нужно пробовать несколько раз // используя разные способы вычисления матрицы зависимости меток // но это не сейчас { // выберем самую мощную метку $a_tag = array_shift($tags); $tags2 = get_a_tag_array($tags, &$C2) // строим множество зависимых от a_tag меток $tags_tree[$a_tag] = $tags2; // получили одну ветку поддерева на этой итерации $tags3 = array_diff($tags , $tags2) // продолжим работу с оставшимися метками $current_tree = get_tag_tree($tags3 , $C1 , $C2); // построим дерево для оставшихся if ($current_tree) $tags_tree = array_merge($tags_tree , $current_tree); } return $tags_tree;}
Дополнение дерева меток.
Логично будет выглядеть попадание метки одновременно в разные ветки дерева. Для этого дополним дерево меток.
Для каждой метки определим множество с ней связанных и множество меток, входящих в путь метки.
Исключим из множества связанных меток все метки, которые уже вошли в путь и дополним узел ветками из оставшихся.
Реализацию этого алгоритма оставлю на потом.
Оставьте комментарий!