Использование графа, как основы для создания рубрикатора

    Определения


    В этой статье я опишу способы создания, и использования рубрикаторов, в основе которых лежит структура графа.
    Рубрикатор, категоризатор, каталог категорий, предметный указатель, индекс. Для удобства будем считать, что все эти термины описывают примерно одно и то же. А там, где будут существенные отличия, мы будем явно на них указывать.
    Информационный элемент – чаще всего файл, но в общем случае любая информация представленная как единое целое.

    Введение


    Рубрикаторы используются для решения самых разнообразных задач:
    • Для ускорения поиска и облегчения навигации по большим массивам информации.
    • Для пометки (тегирования) информации с целью организации выборок по определенным рубрикам
    • Для сортировки информации по:
      областям знаний (физика, математика, биология)
      способам использования (Книги — читать, музыка — слушать, фильмы — смотреть)
      принадлежности (папки мои и общие документы)
      важности (папки inbox и spam) и т.п.


    Как правило, классические рубрикаторы основаны на древовидной структуре. Основное достоинство такой организации рубрикатора – это простота и распространенность. В каждой книге есть оглавление – это пример классической структуры в виде дерева. В книге есть разделы, которые в свою очередь делятся на части, главы и так далее. Глубина рубрикатора при этом хорошо отображает сложность структуры книги. Но книга, в классическом понимании это поток информации со свойством «Forward Only». Т.е. оглавление позволяет легко найти конкретное место в книге, а далее мы открываем книгу и последовательно читаем страница за страницей.
    Сложности начинаются тогда, когда в качестве книги выступает справочник, и когда при помощи рубрикатора делается попытка организовать выборочный доступ к контенту вида команд «SELECT * FROM BOOK WHERE TOPIC = ‘Something Interesting’».
    image
    Рис. 1Предметный указатель

    Результатом таких попыток становится – предметный указатель. Это, очень удобный вид указателя. По нему мы можем легко и просто найти в тексте книги разделы, в которых встречается интересная нам тема. Но вот как раз тут и кроется одно из неудобств этого вида рубрикатора – невозможно сразу сгруппировать результаты, разбросанные по всей книге.
    Пример: «Имитация материальной поверхности» встречается на 4 страницах. Эти страницы идут не подряд. То есть, можно предположить, что, все эти страницы относятся к разным рубрикам. Но для того, чтобы найти название соответствующей рубрики требуется проделать отдельную работу: перелистать книгу на нужную страницу и прочитать название рубрики в колонтитуле, если он есть.

    Построение рубрикатора в виде графа (не дерева)


    Начнем с небольшого теоретического отступления: «Дерево является связанным графом, не содержащим циклы»
    Из этого определения следует, что классический рубрикатор, построенный в виде дерева, является «урезанной» версией полноценного рубрикатора, основанного на неориентированном графе.

    Пример построения рубрикатора в виде графа


    Для построения примера рубрикатора на основе графа возьмем близкую многим новосёлам область – строительства ремонта.

    Корневой узел

    Несмотря на то, что в графе не существует ярко выраженного «корня», для создания рубрикатора, в основе которого будет лежать граф – мы нарисуем/назначим один из узлов корневым. В примере – это будет узел «всё».
    «Всё» — это одна из вершин графа, которая имеет специальное предназначение. Эта вершина представляет собой корневой узел дерева рубрикатора. (Так как любое дерево можно представить графом, то такая интерпретация особого назначения вполне допустима).
    image

    Необходимость наличия корневого узла рубрикатора обусловлена «привычностью» его наличия. Этот узел добавляет удобства при использовании рубрикатора человеком. Любой разговор, любое описание строения рубрикатора всегда начинается с выбора основных разделов. Так же, наличие этого узла позволяет реализовать такую удобную функцию как «хлебные крошки».

    Связи

    Связи – это самое ценное, что может предложить рубрикатор, составленный по принципу графа. В отличие от классического древовидного рубрикатора граф позволяет легко задать связи, наличие которых необходимо для полноты описания предметной области, но которые невозможно задать в рамках древовидной структуры.
    Рассмотрим организацию связей в рубрикаторе-графе на примере более подробно.
    image
    Рис. 2 Циклы в рубрикаторе-графе

    На Рис. 2 (выше) изображено подмножество рубрикатора, взятого со строительного портала stroika.ru
    На примере выделена рубрика с названием «Клей паркетный». Если проследить путь, по которому можно добраться до этого раздела, то можно отметить, что узел «Клей паркетный» достижим из узла «всё» через две различные ветки рубрикатора. Узел «Клей паркетный» в равной мере относится как к разделу «Клей» так и к разделу «Паркет». Причем задание такого отношения является естественным для рубрикатора, основанного на графе.
    При желании данную схему можно расширить, задав для каждой дуги графа приоритет (вес). И тогда можно будет указать что «Клей паркетный» это больше клей, нежели паркет. Например, так:
    image
    Рис. 3 Приоритет связей

    Возможность создавать в рубрикаторе циклы является очень важной при работе с категориями, которые:
    • нельзя четко, на 100%. отнести к какой-то одной основной рубрике.
    • имеют особенный смысл только при нахождении в пограничной области. Как раз, пример с клеем для паркета. Без паркета этот вид клея не имеет никакой ценности. Ценность паркетного клея именно в его применимости к паркету.
    • являются ортогональными существующей структуре рубрикатора. Например, разделение товары и услуги аренды. Автокран можно как продать, так взять в аренду.
    • Конкретный компьютерный вирус может быть отнесен к Email-Worm, к P2P-Worm и к Trojan Mailfinder, если он одновременно и распространяется по электронной почте, и является червём, да еще и собирает адреса email.


    Приведем примеры, когда наличие множественных связей существенно упрощает рубрицирование:
    • Клей паркетный (Это и клей и для паркета)
    • Макро-Вирус блокер (Это и макровирус и блокер)
    • Аренда автокрана (Это и аренда автотехники и автокран)
    • Благотворительный концерт (И концерты и благотворительность)
    • Цвет светло-зелёный металлик (И оттенки зеленого и металлики)

    Вершины графа. Промежуточные рубрики

    Граф-рубрикатор состоит из корневого узла «Всё», рёбер графа обозначающих подчинённость одной рубрики другой, вершин (промежуточных рубрик) и листьев (просто рубрик).
    Для создания строго описанного рубрикатора требуется обязательно ответить на вопрос о физическом смысле вершин графа. Т.е. на вопрос о том, как будет трактоваться принадлежность определенной информации в вершине графа. Возможно, в некоторых случаях, будет проще вообще отказаться от использования вершин графа (не листьев!) в качестве рубрик, чем определять смысл отнесения рубрики к вершине графа.
    Рассмотрим этот вопрос более детально на примере:
    image
    Рис. 4 Отнесение информации к листу и вершине графа

    Информационный элемент «письмо» отнесен к рубрике «Клей паркетный». Здесь имеет место отнесение информации к листу графа. И это однозначное соответствие, которое прямо говорит нам о том, что в письме речь идет о паркетном клее. Вариант прямого, однозначного соответствия рубрике является наиболее простым и распространенным.
    Более сложный вариант – элемент «Информационная статья» отнесен к рубрике «Клей». Здесь могут появиться разночтения.
    Например, отнесение к рубрике «Клей» может означать, что статья носит чисто информационный характер и описывает такое вещество, как клей, в общем. Возможно, даже без упоминания таких деталей как «Клей обойный», «Клей резиновый» и «Клей паркетный».
    Другой вариант – когда в статье будет описан не один конкретный «Клей паркетный» а еще и «клей резиновый». В таком случае, отнесение элемента «информационное письмо» к какой либо одной рубрике (листу графа) не будет полностью корректным.
    Итого, при использовании любого древовидного рубрикатора надо обязательно определиться, будут ли вершины графа (промежуточные рубрики) использоваться для пометки информации, или же они будут использоваться только для облегчения составления и навигации по рубрикатору безотносительно рубрицируемых информационных элементов.
    В случае, когда принято решение использовать в качестве рубрик не только листья, но и вершины графа, то стоит подумать о множественной рубрикации информации.

    Листья. Конечные рубрики

    Листья графа – это вершины графа, которые соединены с другими элементами графа только одним ребром. Применительно к графу-рубрикатору это конечные рубрики. Т.е. рубрики, которые не делятся на подрубрики.
    Листья графа-рубрикатора могут содержать дополнительную информацию, которая может помочь в выборе именно этого раздела рубрикатора. В качестве такой информации могут выступать наборы ключевых слов.
    Одним из интересных вариантов использования вершин и листьев графа-рубрикатора может быть вариант, когда и вершины и листья по сути сами являются ключевыми словами. В таком случае в качестве рубрик могут использоваться вершины графа, а листья будут играть роль ключевых слов. Этот вариант построения рубрикатора и алгоритм автоматического рубрицирования будет рассмотрен в следующей статье.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 16

      +5
      На практике приходится работать со множеством уже существующих классификаторов(рубрикаторов), и актуализируется задача синхронизации и определения соответствия, между классификаторами имеющими различную структуру, глубину вложенности а порой даже и различные верхние уровни.

      Не решив этих задач — контент для «свежего» классификатора придётся писать самому, что ведёт накладные расходы на содержание дорогого журналистского отдела. Так как это не всегда возможно, то оптимальным будет предоставление контента самими пользователями, но размещаться в «контентной пустыне», чистом рубрикаторе, никто не захочет, поэтому придётся добыть где-то стартовый контент. И даже если вы договоритесь с партнёрами, всё равно встанет задача синхронизации классификаторов.

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

      Идеальный рубрикатор — это утопия, если вы работаете в издательстве журнала лет 7 — вы это и сами понимаете.
        0
        Я тоже выбрал эту модель для построения рубрикатора.
        Единственное отличие — у меня еще существуют поясняющие теги к каждой рубрике (и к вершинам и к листьям)
          0
          интересная мысль, но отличаются ли у вас листья от описаний?
            0
            Например, лист называется Галантерейные товары, а в тегах у него: Сумки, Кошельки и т.д.

            Соответственно в поиске набираем Сумки, получаем лист Галантерейные товары и все компании, попадающие под эту сферу.
              +1
              Как я понимаю, в терминах данной статьи, ваши Галантерейные товары это и есть узел, у которого будут «описывающие» его листьяСумки, Кошельки и т.д.
                0
                Видимо это специализированный набор «листьев», хранящийся в отдельной таблице.

                В данной статье каждый лист одновременно является возможным узлом, у комментатора же «листья» не являются узлами.
          +1
          а подскажите как хранить такие графы в базе? есть ли готовые алгоритмы, типа nestedsets для деревьев?
            +1
            как список ребер, где в полях будут указаны вершины, которые соединяет ребро
              0
              а вершины — это id записей
                0
                *рубрик (простите за 3 комментария подряд)
              0
              смотря в какой базе, в Cache, например, очень легко хранить графы и деревья — ибо она древовидная БД — никаких алгоритмов не требуется.
              В реляционной базе придётся немного извратиться. Вот пример «изврата» habrahabr.ru/blogs/sql/43955/ немного не в тему но всё же.
                0
                в реляционной см. выше, никакого изврата. Извращаться будет приложение, которое будет подключаться к БД, чтобы забрать данные. Хотя там тоже все просто
                  0
                  одно дело просто — а другое — естественно, и хранение графа в древовидной БД естественнее чем в реляционной
                    0
                    это да, но не всегда есть возможность использовать древовидную БД
                0
                В базе всё просто: две таблицы. Сущности и связи.
                Причем сущности могут существовать отдельно от связей. Это чтобы можно было отдельно добавлять понятия. Например встретили какой то новый термин — добавали, просто чтобы не забыть про него. А уж потом привязали к соответствующим узлам и отдельно их структурировать. Лист превращается в узел простым добавлением связи. Для удобства показа и обработки там конечно хранится флажок, но это уже мелкая оптимизация.

                Only users with full accounts can post comments. Log in, please.