Разностный граф

[Former user]

Originally reported on Google Code with ID 277

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

1) версия преподавателя: abc
   версия студента     : abd
   разностный граф     : http://i.imgur.com/pb5szVC.png

2) версия преподавателя: a|b|c
   версия студента     : a|b|d
   разностный граф     : http://i.imgur.com/c0g4u57.png

3) версия преподавателя: (?:abc){1,3}
   версия студента     : (?:abc){0,3}
   разностный граф     : здесь проблема...

При создании изображения для 3-го случая возникла проблема. На предыдущей встрече было
озвучено предложение что-то на подобие этого http://i.imgur.com/13oaoEv.png . Но выяснилось,
что Dot не даёт возможность размечать различные части текста различными цветами в надписи
для подграфа. По крайней мере я так понял после прочтений документации. Есть какие-нибудь
предложения на этот счёт?

Reported by ZluMYO on 2014-04-18 09:48:57

[Former user]

Похоже проблема разными цветами в надписях решилась. В документации найден такой момент,
что HTML теги можно использовать в каких бы то ни было надписях ТОЛЬКО, если выходное
изображение имеет формат SVG. Это именно наш случай, так что нам сильно повезло...

Reported by ZluMYO on 2014-04-18 15:49:24 - Status changed: Accepted

[Oleg Sychev]

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

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

Reported by oasychev on 2014-04-19 20:15:56

[Former user]

По поводу красного цвета из примера №2: может быть такой?  http://i.imgur.com/8jRehcJ.png

3) версия преподавателя: (?:abc){1,3}
   версия студента     : (?:abc){0,3}
   разностный граф     : http://i.imgur.com/D97CT3g.png

4) <простой ассерт>
   версия преподавателя: a\bc
   версия студента     : a\Bc
   разностный граф     : http://i.imgur.com/KeOGotn.png

Reported by ZluMYO on 2014-05-16 12:12:21

[Oleg Sychev]

Можно. Правда в случае большого совпадения фраз (как в 3 и 4) лучше цветом выделить
именно разницу. Это можно сделать либо на уровне анализа дерева (preg-узлов, можно
выделить одинаковые узлы с разными параметрами), либо на уровне анализа строк (через
алгоритм LCS).

Reported by oasychev on 2014-05-17 11:47:37

[Former user]

5) <сложный ассерт - разное содержимое, но направление верное>
   версия преподавателя: (?<=a)b 
   версия студента     : (?<=с)b 
   разностный граф     : http://i.imgur.com/VczafKK.png (внутри ассерта действуют предыдущие
правила)

6) <сложный ассерт - нужное содержимое, но направление ошибочное>
   версия преподавателя: (?=a)b 
   версия студента     : (?<=a)b 
   разностный граф     : http://i.imgur.com/TKJxLwq.png

6) <сложный ассерт - нужное содержимое, но утверждение ошибочное>
   версия преподавателя: (?<=a)b 
   версия студента     : (?<!a)b 
   разностный граф     : http://i.imgur.com/7PpEr9C.png

Reported by ZluMYO on 2014-05-30 11:52:20

[Former user]

7) <комплексный пример>
    версия преподавателя: ^<tag>(.+)</tag>$ 
    версия студента     : <teg>[\w\d\s]*</teg>
    разностный граф     : http://sendimage.me/enlarge/sGkSMe2D

Теперь большое отступление, но важное отступление...

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

Если присмотреться к существующему коду, который реализует объясняющий граф (далее
ОГ). То можно заметить, что классы qtype_preg_explaining_graph_tool_node, qtype_..._link
и qtype_..._subgraph не прямо отображают предметную обсуждаемую предметную область
(ОГ регулярного выражения). Зато эти классы точно представляют кое-что другое - dot-код.
Ведь dot оперирует именно этими понятиями: узел, связь и подграф. Отсюда следует вывод,
что нужны другие программные типы данных, которые адекватно описывали бы ОГ регулярного
выражения.

Как это ни смешно, но нужно сначала выяснить из чего состоит ОГ (оказывается 2 года
до этого прошли в неведении). Поскольку по сути он представляет собой регулярное выражение
(ого!), то нужно и оперировать понятиями регулярных выражений! А именно в терминах
ООП получается "Граф" - это класс содержащий упорядоченный контейнер частей регулярного
выражения, слева на право, как в письменном виде. Естественно для частей регулярного
выражения тоже нужно иметь соотвествующие классы. Наконец, очевидно, что все эти классы
кое-что объединяет - они все могут преобразовать себя в dot-представление!

Получается красивая картина, но на первый взгляд предполагающая, что существующие классы
qtype_preg_explaining_graph_tool_node, qtype_..._link и qtype_..._subgraph нужно выкинуть.
Но на самом деле это не так! Создав небольшой прототип программы на языке Python, где
реализованы новые описанные выше классы (не все и не полностью конечно), я пришёл к
выводу, что самостоятельно генерировать dot-код с их помощью громоздко и неудобно.
Зато довольно легко из них получить модель dot-кода, описываемую имеющимися классами
в Preg.

Итак, имея на руках описанный ваше класс "Граф", мы получаем удобный инструмент для
реализации главной задачи, а именно получение разностного графа. Совершенно очевидно,
что найти разницу между двумя упорядоченными контейнерами (то есть экземплярами класса
"Граф") намного проще, нежели работать ПО СУТИ с моделью dot-кода двух регулярных выражений.
Осталось лишь, говоря математическим языком, определиться с видом некоторого бинарного
оператора A, который из двух "Графов" получил бы их разность.

P.S. В итоге получается, что введение нового уровня абстракции опять спасло мир.
Прототип на Python: https://github.com/zlumyo/egraph

Reported by ZluMYO on 2014-08-16 08:32:10 - Status changed: InProgress

[Oleg Sychev]

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


Ну и самое важное - про алгоритмы общих подграфов смотрели? Думали?

Reported by oasychev on 2014-08-26 11:04:13

[Oleg Sychev]

Не самая приятная новость: проблема максимального общего подграфа (MCS) NP-полная, то
есть решается главным образом вариациями перебора с отсечениями. Эффективных алгоритмов
нет (если придумаете - премия в миллион долларов ваша). По описаниям сводится к проблеме
максимальной клики: http://en.wikipedia.org/wiki/Clique_problem 
Подходы к решению описаны в 
Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M. (1999), "The maximum clique
problem", Handbook of Combinatorial Optimization 4, Kluwer Academic Publishers, pp.
1–74, CiteSeerX: 10.1.1.48.4074 
и 
Gutin, G. (2004), "5.3 Independent sets and cliques", in Gross, J. L.; Yellen, J.,
Handbook of graph theory, Discrete Mathematics & Its Applications, CRC Press, pp. 389–402,
ISBN 978-1-58488-090-5.

Ключевые слова для поиска статей с алгоритмами: maximum common subgraph, labeled, directed
(т.е. граф с метками и направленный что важно). Пример легко находящейся статьи - http://www.emis.de/journals/JGAA/accepted/2007/ConteFoggiaVento2007.11.1.pdf

Reported by oasychev on 2014-08-26 11:21:22

[Former user]

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

Reported by ZluMYO on 2014-08-26 14:09:32

[Oleg Sychev]

Что такое "списочный вид" регекса я даже не знаю - набор конкатенаций? А как быть с
альтернативами и т.д.?

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

Reported by oasychev on 2014-08-26 21:43:33

[Former user]

Почитал литературы на тему поиска общих подграфов. Методов не очень много и делятся
они на точные и приближённые. Точные являются NP-полными и отличаются по сути моделью
перебора (например нахождением клик или методом ветвей и границ).
В процессе ознакомления с материалами по данной теме возникла мысль, что у в нашем
случае идёт речь не о простом граф, а всё таки о дереве. Интуиция подсказывает, что
поскольку деревья это весьма особый тип графов, то наверняка и задача поиска максимальных
поддеревьев (а именно так я понимаю поставленную задачу) должна решаться несколько
по особому (подразумеваю - легче в алгоритмическом плане).
И правда! Если покопаться по теме MCS, где S - subtree вместо subgraph, то можно найти
интересующую информацию. Здесь также есть быстрые, но приближённые, методы, тогда как
точные являются NP-полными. В тоже время точные методы в алгоритмическом плане проще,
чем для графов в целом.
Таким образом, предлагаю взять за основу алгоритм предназначенный для дерева, нежели
для графов в целом.

Reported by ZluMYO on 2014-09-06 20:23:35

[Former user]

Начал думать о реализации алгоритма, и в процессе на бумаге возник вот такой пример:

7) <совпадения с чередованием>
    версия преподавателя: abc
    версия студента     : _a_b_c_
    разностный граф     : http://i.imgur.com/L3rFwYQ.png

Думаю, стоит обсудить обсудить этот пример. Нужно ли в таких случаях, когда совпадения
могут оказаться далеко друг от друга (допустим вместо "_" там бы стояло что-то большое)
собственно считать это совпадениями?

Reported by ZluMYO on 2014-09-07 09:11:20

[Oleg Sychev]

Где это вы видели у нас дерево? У нас DAG - Direct Acyclic Graph (направленный ацикличный
подграф), что еще важно - он с метками в вершинах. Методы предназначенные для деревьев
нам не подходят - разве что вы удалите из графа все вершины после схождения первой
же развилки.....

Reported by oasychev on 2014-09-07 17:55:07

[Former user]

Как это не дерево? Я имею в виду синтаксическое дерево. Находить разницу между регулярными
выражениями на уровне дерева, а затем преобразовать это в граф.

Reported by ZluMYO on 2014-09-08 05:53:07

[Oleg Sychev]

Разницу между выражениями следует искать на уровне графа. Вы не обратили внимание -
на одной из встреч мы пытались построить разностное дерево для регулярных выражений.
Оно получается очень некрасивым и плохо понятным - например в случае возникновения
конкатенации там где был один символ и т.д. Синтаксическое дерево не годится для наглядного
сравнения выражений. И разные деревья могут приводить к похожим графам.

Reported by oasychev on 2014-09-08 11:24:11

[Former user]

В процессе проработки тестовых примеров возник вопрос, учитывать ли (и если да то как)
настройку "is exact matching" при нахождении разницы?

Reported by ZluMYO on 2014-10-02 13:30:04

[Oleg Sychev]

Ну по идее разностный граф нужен для вопроса с написанием регекса, как таковой настройки
там может не быть. Пока ее судьба непонятна, так что можно не заморачиваться если потом
доделать при необходимости...

Reported by oasychev on 2014-10-02 17:16:54

[Former user]

Нашёл очень хорошую статью на английском языке, где представлено описание различных
алгоритмов нахождения MCS. Рассказ ведётся относительно проблемы нахождения подобий
в структурах химических молекул, но это никак не мешает.
http://www.icst.pku.edu.cn/intro/leizou/teaching/2012-autumn/papers/part5/Maximum%20common%20subgraph%20isomorphism%20algorithms%20for%20the%20matching%20of%20chemical%20structures.pdf

Если вкратце, то автор разделяет на 2 большие группы: точные и приближённые.
В группе точных представлены:
- алгоритм основанный на кликах;
- бэктрекинг;
- динамическое программирование (да-да!).
В группе приближённых:
- генетический алгоритм;
- комбинаторная оптимизация;
- хранилище фрагментов (Fragment storage).

Reported by ZluMYO on 2014-10-26 07:04:07

[Oleg Sychev]

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

Reported by oasychev on 2014-11-03 23:59:33

[Former user]

В процессе составления тестов для алгоритма(-ов) поймал себя на мысли, что по сути тесты
берутся просто наобум. Не очень получается их как-то классифицировать, если не считать
по разнообразию различных фич PCRE диалекта. Есть какие-то предложения на этот счёт?

Reported by ZluMYO on 2014-11-11 11:30:14

[Oleg Sychev]

Во-первых, можно классифицировать по структуре базового графа (я бы на каждый вариант
графа делал несколько вариантов разностных).
Во-вторых, по степени сходства сравниваемых графов - от слабо отличающихся до почти
разных.
В третьих, мало и среднеотличающиеся можно классифицировать по видам различий (в последовательностях
- разные; в развилках, в кластерах (повторение и подмаски) и т.д.
В четвертых - отдельную группу стоит посвятить разным, но реально эквивалентным участкам
(альтернатива из одного символа и символьный класс, разные написания симв. классов,
a{2}a? и a{2,3} и т.д. 

Reported by oasychev on 2014-11-11 14:37:38

[Oleg Sychev]

Reported by oasychev on 2015-03-01 22:51:11 - Labels added: Component-Preg