?

Log in

No account? Create an account

Компьютерная лингвистика

Новостная лента www.solarix.ru

Previous Entry Share Next Entry
Синтаксическое дерево на HTML 5 canvas
kelijah
Это третья попытка сделать отрисовку синтаксических деревьев средствами HTML.

Первая версия использовала символы псевдографики └├ и т.д.

Вторая версия использовала CSS и набор элементарных изображений линий.

Теперь новая попытка на основе механизма canvas, появившегося в HTML 5.

Что хочется получить

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

2. Желательно, чтобы алгоритм отрисовки легко реализовывался средствами PHP и C#, чтобы работать на веб-сервере. Реализация через сторонние библиотеки, для подключения которых нужны привелегии, танцы с бубном и так далее, нежелательна. Только стандартные средства.

3. Каждый узел (вершина) может быть не просто словом, а прямоугольным блоком с разнообразной информацией о слове с дополнительным оформлением, упрощающим визуальное восприятие.

4. Узлы должны быть кликабельны, это позволит раскрывать пользователю дополнительную информацию для каждого слова, например - грамматические признаки, использованные правила перевода и так далее. Кликабельность понимается по аналогии с гиперссылками - после клика в пределах узла либо сервер, либо клиент должны получить управление и возможность обработать клик с информацией, какое слово стоит за узлом. В рамках HTML есть, наверное, только 2 подходящих механизма. Про гиперссылки, вводимые в текст тегом <a>, все понятно. Есть и другой стандартный механизм - карты изображений, но для них нужна дополнительная обработка на стороне веб-сервера, что не всегда удобно.

5. Должен быть способ рисовать ребра с разными стилями для разных типов синтаксических отношений.

JavaScript библиотеки

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

Немного погуглив, быстро наткнулся на пост в stackoverflow с перечнем библиотек:

http://stackoverflow.com/questions/7034/graph-visualization-code-in-javascript

Из этого списка я попробовал несколько вещей, а именно

arbor.js (и кстати статья на хабре)

Graph JavaScript framework, version 0.0.1

JavaScript InfoVis Toolkit Среди демок можно найти "space tree", которая вроде бы почти идеально соответствует требованиям задачи. Но поковырявшись некоторое время, я не смог добиться от либы нужно поведения.

JS Graph It Основная фишка, взявшая за живое - возможность таскать узлы графа мышкой. Практически получается редактор для подготовки к печати. Сам скрипт там простой, то есть его можно и подпилить под себя.

Есть еще очень крутая либа Rafael.


Генерация изображения на стороне веб-сервера

Очень хороший способ, позволяющий написать генератор PNG-изображения на C# через GDI+ или что-то типа этого. Браузеру отдается ссылка на сгенерированный файл. Клики пользователя отрабатываем через описание областей тегами
<map>...<area shape="...">.... Веб-сервер получает информацию о кликах на изображении и может соответствующим образом подготовить для веб-браузера новый контент как реакцию на клик.

Вся логика в этом случае остается на сервере. Хотя получается очень много возни с сохранением контекста для графов, отрисованных в изображения-карты.

Для пользователя неудобство в том, что кликабельность никак не подчеркивается визуально. Курсор при наведении на узлы не меняется и т.д.

SVG

Хороший способ. Сейчас вроде бы все браузеры имеют поддержку этого векторного формата "из коробки". Можно добавлять гиперссылки. То есть на сервере генерируем векторное изображение для графа и отсылаем его в теле веб-страницы. Удобно и просто.

Минус - нужны дополнительные усилия для вычисления экранных позиций узлов. Каждый узел может быть целым div'вом с многострочным текстом с разным оформлением. Без информации о шрифтах, которыми все это будет отрисовываться, высчитать границы блоков и позиции невозможно. Нужны вычисления по месту на клиенте, то есть javascript.

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

Но в итоге я решил сделать еще проще, оставив вопрос размещения узлов полностью на движок браузера, заодно пощупав вживую возможности нового стандарта HTML на самом нижнем, так сказать, уровне.

HTML 5 Canvas

"Холсты" дают возможность рисования прямо на клиенте, в браузере, средствами javascript, без привлечения каких-либо плагинов, флеша, сильверлайта и прочего.

Простая документация, позволяющая очень быстро войти в курс дела и начать рисовать - у Мозиллы

Текущая версия FireFox уже имеет все необходимое на борту - можно экспериментировать. Safari вроде бы тоже. IE 8 участвовать отказался, возможно версия 9 все-таки имеет поддержку canvas, но я не проверял.

Вот так все выглядит сейчас в FF:

синтаксическое дерево средствами HTML 5


Расчет layout'а полностью отдан на откуп движка браузера. Каждый узел это на самом деле div, в котором может быть хоть таблица с множеством дополнительной описательной мелочевки, и заботиться о расчете размеров нет необходимости.

Ключевое слово - табличная верстка. Так как синтаксический граф однозначно делится на уровни иерархии, то рекурсивный алгоритм обхода дерева элементарно преобразует дерево в набор вложенных <table>.

Прямоугольная область каждого узла имеет свой уникальный id. Поэтому javascript код может пройтись по узлам и определить их экранные координаты и протяженность. Я привык к jQuery, поэтому определение позиций и размеров сделал через нее. В итоге C#-код на сервере генерирует html-код с деревом и javascript-код для прорисовки ребер, и все это отправляет пользователю для исполнения в веб-браузере.

Наконец, отрисовка ребер. Вот тут нам и нужна canvas. Мы помещаем canvas позади div'а с деревом, задавая им соответствуюзщие z-order. Зная экранные координаты узлов, которые нам сообщил браузер, мы просто отрисовываем линии на холсте, и вуаля.

Новую отрисовку можно будет посмотреть на сайте онлайн-словаря http://178.64.252.139:8080/Morphology.aspx завтра или послезавтра.

Что надо улучшить

Для каждого узла будем писать также часть речи. Более детальную морфологическую информацию можно раскрывать в popup-диалогах, которые сейчас появляются при клике на узлах.

Стиль рисования ребер будем задавать в зависимости от типа ребра (см. sol_GetLeafLinkType). То есть цвет и пунктир как минимум.

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