Xpoint
   [напомнить пароль]

Использование меток для категоризации контента

Андрей Новиков[досье]

Я решил всё-таки оформить свои мысли касательно данной проблемы. Отчасти потому, что эти идеи я в будущем хочу применить на Xpoint. Времени у меня мало, поэтому буду писать потихоньку.

Оглавление

Вступление

Описываемые мной подходы были изначально внедрены и опробованы в моей домашней галерее. Дальнейшее развитие этод метод получил на сайте Xpoint. На данный момент это категоризация документов базы знаний, а именно Алфавитный указатель.

Все примеры в данной статье написаны на языке Perl, но для тех, кто с ним незнаком, максимально откомментированны. Структура таблиц и другие неявные данные, используемые в примерах статьи описаны в cправочных материалах.

Текущий подход - дерево категорий

...ждем-с...

Что такое метка

Метка — это некое однозначное определение какого-либо из ортогональных свойств описываемого объекта. Ортогональность здесь играет большую роль, т.к. позволяет более качественно искать объекты по меткам. Ортогональность в данном случае — это отсутствие меток, группирующих понятия нескольких других меток. Например, если есть метки "красный", "зеленый", "синий", то метка "имеет цвет" — это плохо. Требование ортогональности вытекает из общего смысла меток — максимально четко, или другими словами, однозначно описать каждое из интересующих нас свойств объекта. С ортогональностью связана одна из проблем, на которых мы остановимся позже.

Выборка объектов по меткам

Основа концепции проста и сводится к следующему: выбирая одну или несколько меток, мы сужаем область поисков, накладывая кретерии выборки объектов. В отличие от рубрикатора, путь по которому предопределен его организатором, с метками мы пожем получать любую произвольную выборку. На этом начинается скупая теория и начинается суровая практика. А на практике мы сталкиваемся с вопросами удобства и простоты использования интерфейса, гибкости построения выборок, производительности системы.

Простейший вариант выборки по одной метке мы рассматривать не будем, как абсолютно несерьезный и непрактичный. Золотой (на данный момент) серединой является вариант выборки с перемножением множеств меток. Т.е. мы выбираем объекты, имеющие все указанные нами метки. Наиболее сложным, абсолютно гибким и нигде мной еще не встречавшимся вариантом является возмоность произвольной комбинации меток через И, НЕ и ИЛИ. Т.е., говоря псевдо-языком, возможность выборки объектов, которые, (красные ИЛИ зеленые) И (волосатые ИЛИ шершавые) И НЕ пластмассовые.

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

Привязка меток к объекту

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

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

Тут будет подробно раскрыт подход, используемый на Xpoint, когда он выродится во что-то достойное описания.

Управление метками объектов

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

Существует два основных подхода к управлению метками, как самостоятельными сущностями:

  1. Создание и удаление меток с помощью независимого интерфейса.
  2. Автоматическое создание и удаление меток в момент их привязки к объектам.

Каждый подход имеет право на жизнь и выбирается в зависимости от конкретной задачи и предпочтений автора реализации. Я предпочитаю второй подход.

В то время, как первый подход весьма тривиален, остановимся подробнее на втором.

Автоматическое добавление меток

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

# $labels - строка с метками, разделенными запятой или точкой с запятой
# $DBC - всевдо-класс работы с СУБД

my @labels; # массив меток
my %found;  # временный хэш найденных меток

# выбираем ID для каждой метки
foreach my $label (split(/\s*[,;]\s*/, $labels))
{
    # убираем дубликаты
    exists $found{$label} and next;
    $found{$label} = 1;

    # выбираем ID существующей в базе метки по её имени
    my $lName = $DBC->quote($label);
    $label = $DBC->getValue("SELECT id FROM label WHERE name = $lName");

    # создаем новые, если их нет
    unless ($label)
    {
        # добавляем в базу новую метку
        $DBC->execute("INSERT INTO label(name) VALUES($lName)");
        # получаем ID добавленной метки
        $label = $DBC->getLastInsertID();
    }

    # добавляем ID метки в массив
    push(@labels, $label);
}
%found = undef;

Теперь, когда все метки существуют в базе, а у нас есть список их ID, можно осуществить непосредственную их привязку к объектам:

# $objectId - ID описываемого объекта

# получаем список текущих привязанных к объекту меток
my %old = $DBC->getMap("SELECT label, 1 FROM label WHERE object_id = $objectId");

# сравниваем текущий список с новым, чтобы получить список изменений
my @insert = ();
for my $label (@labels) 
{
    unless (exists($old{$label}))
    {
        push(@insert, $label);
    }
    else
    {
        delete($old{$label});
    }
}
my @remove = keys %old;

# добавляем в таблицу связей новые метки
if (@insert)
{
    $DBC->execute("INSERT INTO object_label(object_id, label) VALUES ".join(",", map {"($objectId, $_)" } @insert));
}

# удаляем более неиспользующиеся метки
if (@remove)
{
    $DBC->execute("DELETE FROM object_label WHERE object_id=$objectId AND label IN (".join(',',@remove).")");
}

Автоматическое удаление меток

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

Сначала (перед внесением изменений в таблицу связей (перед комментарием "добавляем в таблицу связей новые метки") вставляем выбор подлежащих удалению меток:

# формируем список подлежащих полному удалению меток
my %dlstats = ();
# запоминаем статистику по использованию удаленных меток
if (@remove)
{
    $dlstats = $DBC->getMap("SELECT label, count(object_id) FROM object_label WHERE label IN (".join(', ', @remove).") GROUP BY label");
}

А в самый конец кода привязки меток добавляем удаление самих меток (чтобы перед удалением быть уверенными, что все связи успешно обновлены):

# смотрим, есть ли метки, которые были привязаны только к нашему объекту, и удаляем их
foreach my $label (keys(%dlstats))
{
    if ($dlstats{$label} == 1)
    {
        $DBC->execute("DELETE FROM label WHERE id = $label");
    }
}

Проблемы

...ждем-с...

  • кластеризация меток
  • опечатки, синонимы
  • смена понятий

...

Чужой опыт

В последнее время не я один проповедую такой подход для категоризации объектов. Из известных мне сервисов хочу отметить следующие:

  1. GMail — знаменитая почта Гугла полностью отказалась от привычного древовидного рубрикатора в пользу меток.
  2. del.icio.us — использует метки для категоризации архива ссылок пользователей сервиса.
  3. Flickr — сервис публикации фотографий использует метки, как один из вариантов категоризации контента.
  4. utx — система для категоризации и социальной организации записей в Живом Журнале (Livejournal.com).
  5. OpenNet Project — информационный ресурс для ИТ-специалистов использует метки для категоризации и поиска материалов. Примечателен тем, что метки привязаны к классическому рубрикатору, что облегчает навигацию новым посетителям. Это как раз то, к чему стремится Xpoint.

Если вам есть, чем дополнить этот список, пишите в комментарии.

Ссылки по теме

...ждем-с...

Справочные материалы

Используемая структура базы данных

-- таблица меток
CREATE TABLE label (
  id integer unsigned NOT NULL,
  name varchar(250) NOT NULL,
  PRIMARY KEY (id)
);

-- таблица связей меток с объектами
CREATE TABLE object_label (
  object_id integer unsigned NOT NULL,
  label integer unsigned NOT NULL,
  PRIMARY KEY (object_id, label),
  UNIQUE KEY label_object_id (label, object_id)
);
Powered by POEM™ Engine Copyright © 2002-2005