Как стать автором
Обновить

Строим граф ключевых слов

Время на прочтение 2 мин
Количество просмотров 2.5K
В прошлой заметке я поделился результатами своих экспериментов по построению графа ключевых слов. В ней я совершенно не касался «технических аспектов» построения графов. В комментариях меня попросили пролить свет и на техническую составляющую моих экспериментов. По здравому размышлению я решил вынести их в отдельную заметку, поскольку они могут сгодится для построения любого графа средствами набора утилит graphviz.

Итак, что такое граф и какие они бывают я рассказывать не буду — все желающие могут сами прочитать о них в википедии. Я лишь расскажу как можно построить простой неориентированный граф при помощи набора утилит graphviz на примере построения графа ключевых слов.

Для начала как сделана поддержка ключевых слов в медиарепозитории. При проектировании базы данных для ведения учета ключевые слова были созданы две таблицы: собственно таблица ключевых слов (kw) и таблица связи ключевых слов и файлов (file2kw). Благодаря такой организации таблиц можно для каждого файла указать свой произвольный набор ключевых слов.

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

Поэтому для построения карты связанных ключевых слов со словом «анероид» решаются две задачи:
1. Извлечение списка всех файлов, у которых использовалось слово «анероид»
2. Извлечение всех ключевых слов, используемых для описания всех полученных файлов, за исключением слова «анероид».

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

digraph kw{
Рождение->Юность->Зрелость->Старость->Смерть;
Юность->Смерть;
Зрелость->Смерть;
}

Теперь нам остается сделать самую малость: выбрать список всех используемых ключевых слов и по ним построить списки связанных ключевых слов. Для решения этой задачи средствами MySQL одним SQL-запросом обойтись не получается, а вот в PostgreSQL такое вполне возможно. Из-за того, что на сайте используется как раз MySQL мне пришлось написать небольшой PHP-скрипт, который делал все нужные извлечения из базы данных и форматировал их в формате dot-файла для graphviz'а.

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

Для получения PNG-картинки графа по методу fdp из исходного dot-файла в консоли UNIX или Linux-машины нужно набрать следующее:

fdp -Tpng -o media-kw.png media-kw.dot

На выходе мы получим такое (граф ключевых слов по состоянию на 1 сентября 2008 года):
Граф ключевых слов
Теги:
Хабы:
+12
Комментарии 7
Комментарии Комментарии 7

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн
PG Bootcamp 2024
Дата 16 апреля
Время 09:30 – 21:00
Место
Минск Онлайн
EvaConf 2024
Дата 16 апреля
Время 11:00 – 16:00
Место
Москва Онлайн