Введение 4
1. Постановка задачи 7
2. Обзор 8
2.1. Базовые определения из теории формальных языков . . 8
2.2. Базовые определения из теории графов 11
2.3. Задачи поиска путей с контекстно-свободными ограничениями 12
2.4. Обобщенный LL алгоритм 12
2.5. Алгоритм выполнения контекстно-свободных запросов, базирующийся на GLL 14
3. Реализация алгоритма 16
3.1. Мотивация 16
3.2. Особенности реализации 17
3.3. Архитектура 18
4. Экспериментальное исследование 21
4.1. Оборудование 21
4.2. Экспериментальные данные 21
4.3. Постановка экспериментов 27
4.4. Результаты экспериментов 28
Заключение 36
Список литературы 37
Представление данных в виде помеченных графов находит широкое применение во многих научных областях [17], таких как анализ социальных сетей [2], биоинформатика[16], статический анализ кода [7] и т.д. Одним из основных преимуществ данной модели над реляционной моделью является более быстрое получение информации об отношениях между объектами, ведь взаимосвязи между узлами не вычисляются во время выполнения запроса, а хранятся в самой модели.
При работе с такими данными зачастую возникают запросы навигации и поиска путей между вершинами. Одним из способов выражения такого рода запросов является определение формальных грамматик над алфавитом меток ребер графа [3]. Путь в графе удовлетворяет ограничениям, задаваемым данной формальной грамматикой, если ему принадлежит слово, получаемое конкатенацией меток на ребрах данного пути. Наибольшее практическое применение находят регулярные грамматики, несколько менее популярными являются контекстно-свободные свободные грамматики. Однако, с точки зрения приложений к языкам программирования и компиляции наиболее важными являются именно контекстно-свободные грамматики. Таким образом встает вопрос о необходимости разработки и реализации алгоритмов поиска путей с контекстно-свободными ограничениям (англ. «Context-Free Path Querying», кратко CFPQ).
Несмотря на то, что проблема выполнения контестно-свободных запросов широко изучена и существует целый ряд алгоритмов, ее решающих [1,4,10, 13], тем не менее одной из наиболее остро стоящих проблем является низкая производительность существующих алгоритмов [6], поэтому актуальной задачей является разработка и реализация новых алгоритмов, решающих данную проблему.
Одним из недавно разработанных методов решения данной задачи является алгоритм, использующий матричное представление для получения информации о достижимостях в графе. Данный алгоритм был предложен Азимовым Р.Ш. в [5] и основан на матричных операциях. В его работе было показано, что данный алгоритм демонстрирует достаточно хорошую производительность. Кроме того, основанный на матрицах CFPQ-алгоритм в дальнейшем стал основой для первой полноценной поддержки контекстно-свободных запросов в результате расширения графовой базы данных RedisGraph [14].
Матричное представление не единственный возможный способ решения такого рода задач. Более того, результаты исследований показали, что базовые алгоритма распознавания строк по заданной грамматике могут быть естественным путем обобщены на входные данные в виде графа [8]. Например, существуют описания того, как проблема поиска путей с контекстно-свободными ограничениями может быть решена с помощью использования обобщенного LL-парсера [12, 9] или обобщенного LR-парсера [18, 20]. Более того, такой подход позволяет получать информацию не только о достижимостях в графе, но и о самих путях [11].
Так, в рамках предыдущих работ [22] была получена реализация алгоритма для выполнения контекстно-свободных запросов в графовой базе данных Neo4j. Данный алгоритм является адаптацией классического алгоритма синтаксического анализа Generlized LL для выполнения контекстно-свободных запросов на графах. Важно отметить, что полученный алгоритм поддерживает весь класс контекстно-свободных языков. Модифицированный GLL, так же как и оригинальный алгоритм, возвращает информацию не только о достижимостях между вершинами, но и информацию для построения самих путей. Несмотря на то, что проведенное экспериментальное исследование показало практическую эффективность полученного решения при работе с контекстно-свободными грамматиками, тем не менее данная реализация не позволяет напрямую работать наиболее распространенным на сегодняшний день способом задания ограничений — с регулярными выражениями. Для их обработки сначала необходимо преобразование грамматики, что ведет к увеличению количества продукций в ней и, как следствие, ухудшению производительности алгоритма GLL. Обойти данную проблему может помочь выражение грамматик в виде рекурсивных автоматов, которые одинаково оптимально поддерживают как регулярные, так и контекстно-свободные грамматики.
Таким образом, целью данной работы является предоставление реализации GLL алгоритма, основанного на рекурсивном автомате, для обработки входных данных в виде графа как для решения задачи достижимости, так и для поиска путей. Далее планируется проведение экспериментального исследования с целью выявления значимого повышения эффективности по сравнению с альтернативными решениями.
1 Постановка задачи
Целью данной работы является реализация и экспериментальное исследование производительности GLL-парсера, основанного на рекурсивном автомате.
Для достижения данной цели были поставлены следующие задачи.
• Реализация классического алгоритма GLL.
• Модификация алгоритма GLL для поддержки представления грамматики в виде рекурсивного автомата.
• Расширение модифицированного алгоритма GLL на входные данные в виде графа.
• Проведение экспериментального исследования и сравнение с существующими решениями.
В ходе работы были достигнуты следующие результаты.
• Реализован классический GLL алгоритм.
• Алгоритм GLL был модификацирован для поддержки представления грамматики в виде рекурсивного автомата.
• Реализовано расширение модификацированного GLL алгоритма на входные данные в виде графа.
• Проведено экспериментальное исследование, по результатам которого можно сделать выводы о том, что полученная модификация алгоритма GLL работает существенно эффективнее классического алгоритма GLL.
Можно выделить несколько дальнейших возможных направлений работы.
• Проведение экспериментального исследования на более широком наборе реальных данных. Примером таких данных являются графы MemoryAliases [21]
• Интеграция с одной из графовых баз данных. Примером такой базы является графовая база данных Neo4j.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
