Определения
В этой статье я опишу способы создания, и использования рубрикаторов, в основе которых лежит структура графа.
Рубрикатор, категоризатор, каталог категорий, предметный указатель, индекс. Для удобства будем считать, что все эти термины описывают примерно одно и то же. А там, где будут существенные отличия, мы будем явно на них указывать.
Информационный элемент – чаще всего файл, но в общем случае любая информация представленная как единое целое.
Введение
Рубрикаторы используются для решения самых разнообразных задач:
- Для ускорения поиска и облегчения навигации по большим массивам информации.
- Для пометки (тегирования) информации с целью организации выборок по определенным рубрикам
- Для сортировки информации по:
областям знаний (физика, математика, биология)
способам использования (Книги — читать, музыка — слушать, фильмы — смотреть)
принадлежности (папки мои и общие документы)
важности (папки inbox и spam) и т.п.
Как правило, классические рубрикаторы основаны на древовидной структуре. Основное достоинство такой организации рубрикатора – это простота и распространенность. В каждой книге есть оглавление – это пример классической структуры в виде дерева. В книге есть разделы, которые в свою очередь делятся на части, главы и так далее. Глубина рубрикатора при этом хорошо отображает сложность структуры книги. Но книга, в классическом понимании это поток информации со свойством «Forward Only». Т.е. оглавление позволяет легко найти конкретное место в книге, а далее мы открываем книгу и последовательно читаем страница за страницей.
Сложности начинаются тогда, когда в качестве книги выступает справочник, и когда при помощи рубрикатора делается попытка организовать выборочный доступ к контенту вида команд «SELECT * FROM BOOK WHERE TOPIC = ‘Something Interesting’».
Рис. 1Предметный указатель
Результатом таких попыток становится – предметный указатель. Это, очень удобный вид указателя. По нему мы можем легко и просто найти в тексте книги разделы, в которых встречается интересная нам тема. Но вот как раз тут и кроется одно из неудобств этого вида рубрикатора – невозможно сразу сгруппировать результаты, разбросанные по всей книге.
Пример: «Имитация материальной поверхности» встречается на 4 страницах. Эти страницы идут не подряд. То есть, можно предположить, что, все эти страницы относятся к разным рубрикам. Но для того, чтобы найти название соответствующей рубрики требуется проделать отдельную работу: перелистать книгу на нужную страницу и прочитать название рубрики в колонтитуле, если он есть.
Построение рубрикатора в виде графа (не дерева)
Начнем с небольшого теоретического отступления: «Дерево является связанным графом, не содержащим циклы»
Из этого определения следует, что классический рубрикатор, построенный в виде дерева, является «урезанной» версией полноценного рубрикатора, основанного на неориентированном графе.
Пример построения рубрикатора в виде графа
Для построения примера рубрикатора на основе графа возьмем близкую многим новосёлам область – строительства ремонта.
Корневой узел
Несмотря на то, что в графе не существует ярко выраженного «корня», для создания рубрикатора, в основе которого будет лежать граф – мы нарисуем/назначим один из узлов корневым. В примере – это будет узел «всё».
«Всё» — это одна из вершин графа, которая имеет специальное предназначение. Эта вершина представляет собой корневой узел дерева рубрикатора. (Так как любое дерево можно представить графом, то такая интерпретация особого назначения вполне допустима).
Необходимость наличия корневого узла рубрикатора обусловлена «привычностью» его наличия. Этот узел добавляет удобства при использовании рубрикатора человеком. Любой разговор, любое описание строения рубрикатора всегда начинается с выбора основных разделов. Так же, наличие этого узла позволяет реализовать такую удобную функцию как «хлебные крошки».
Связи
Связи – это самое ценное, что может предложить рубрикатор, составленный по принципу графа. В отличие от классического древовидного рубрикатора граф позволяет легко задать связи, наличие которых необходимо для полноты описания предметной области, но которые невозможно задать в рамках древовидной структуры.
Рассмотрим организацию связей в рубрикаторе-графе на примере более подробно.
Рис. 2 Циклы в рубрикаторе-графе
На Рис. 2 (выше) изображено подмножество рубрикатора, взятого со строительного портала stroika.ru
На примере выделена рубрика с названием «Клей паркетный». Если проследить путь, по которому можно добраться до этого раздела, то можно отметить, что узел «Клей паркетный» достижим из узла «всё» через две различные ветки рубрикатора. Узел «Клей паркетный» в равной мере относится как к разделу «Клей» так и к разделу «Паркет». Причем задание такого отношения является естественным для рубрикатора, основанного на графе.
При желании данную схему можно расширить, задав для каждой дуги графа приоритет (вес). И тогда можно будет указать что «Клей паркетный» это больше клей, нежели паркет. Например, так:
Рис. 3 Приоритет связей
Возможность создавать в рубрикаторе циклы является очень важной при работе с категориями, которые:
- нельзя четко, на 100%. отнести к какой-то одной основной рубрике.
- имеют особенный смысл только при нахождении в пограничной области. Как раз, пример с клеем для паркета. Без паркета этот вид клея не имеет никакой ценности. Ценность паркетного клея именно в его применимости к паркету.
- являются ортогональными существующей структуре рубрикатора. Например, разделение товары и услуги аренды. Автокран можно как продать, так взять в аренду.
- Конкретный компьютерный вирус может быть отнесен к Email-Worm, к P2P-Worm и к Trojan Mailfinder, если он одновременно и распространяется по электронной почте, и является червём, да еще и собирает адреса email.
Приведем примеры, когда наличие множественных связей существенно упрощает рубрицирование:
- Клей паркетный (Это и клей и для паркета)
- Макро-Вирус блокер (Это и макровирус и блокер)
- Аренда автокрана (Это и аренда автотехники и автокран)
- Благотворительный концерт (И концерты и благотворительность)
- Цвет светло-зелёный металлик (И оттенки зеленого и металлики)
Вершины графа. Промежуточные рубрики
Граф-рубрикатор состоит из корневого узла «Всё», рёбер графа обозначающих подчинённость одной рубрики другой, вершин (промежуточных рубрик) и листьев (просто рубрик).
Для создания строго описанного рубрикатора требуется обязательно ответить на вопрос о физическом смысле вершин графа. Т.е. на вопрос о том, как будет трактоваться принадлежность определенной информации в вершине графа. Возможно, в некоторых случаях, будет проще вообще отказаться от использования вершин графа (не листьев!) в качестве рубрик, чем определять смысл отнесения рубрики к вершине графа.
Рассмотрим этот вопрос более детально на примере:
Рис. 4 Отнесение информации к листу и вершине графа
Информационный элемент «письмо» отнесен к рубрике «Клей паркетный». Здесь имеет место отнесение информации к листу графа. И это однозначное соответствие, которое прямо говорит нам о том, что в письме речь идет о паркетном клее. Вариант прямого, однозначного соответствия рубрике является наиболее простым и распространенным.
Более сложный вариант – элемент «Информационная статья» отнесен к рубрике «Клей». Здесь могут появиться разночтения.
Например, отнесение к рубрике «Клей» может означать, что статья носит чисто информационный характер и описывает такое вещество, как клей, в общем. Возможно, даже без упоминания таких деталей как «Клей обойный», «Клей резиновый» и «Клей паркетный».
Другой вариант – когда в статье будет описан не один конкретный «Клей паркетный» а еще и «клей резиновый». В таком случае, отнесение элемента «информационное письмо» к какой либо одной рубрике (листу графа) не будет полностью корректным.
Итого, при использовании любого древовидного рубрикатора надо обязательно определиться, будут ли вершины графа (промежуточные рубрики) использоваться для пометки информации, или же они будут использоваться только для облегчения составления и навигации по рубрикатору безотносительно рубрицируемых информационных элементов.
В случае, когда принято решение использовать в качестве рубрик не только листья, но и вершины графа, то стоит подумать о множественной рубрикации информации.
Листья. Конечные рубрики
Листья графа – это вершины графа, которые соединены с другими элементами графа только одним ребром. Применительно к графу-рубрикатору это конечные рубрики. Т.е. рубрики, которые не делятся на подрубрики.
Листья графа-рубрикатора могут содержать дополнительную информацию, которая может помочь в выборе именно этого раздела рубрикатора. В качестве такой информации могут выступать наборы ключевых слов.
Одним из интересных вариантов использования вершин и листьев графа-рубрикатора может быть вариант, когда и вершины и листья по сути сами являются ключевыми словами. В таком случае в качестве рубрик могут использоваться вершины графа, а листья будут играть роль ключевых слов. Этот вариант построения рубрикатора и алгоритм автоматического рубрицирования будет рассмотрен в следующей статье.
