Введение 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
Купить

Представление данных в виде помеченных графов находит широкое применение во многих научных областях, таких как анализ соци­альных сетей, биоинформатика, статический анализ кода и т.д. Одним из основных преимуществ данной модели над реляционной моделью является более быстрое получение информации об отношени­ях между объектами, ведь взаимосвязи между узлами не вычисляются во время выполнения запроса, а хранятся в самой модели.
При работе с такими данными зачастую возникают запросы нави­гации и поиска путей между вершинами. Одним из способов выраже­ния такого рода запросов является определение формальных грамма­тик над алфавитом меток ребер графа. Путь в графе удолетворя- ет ограничениям, задаваемым данной формальной грамматикой, если ему принадлежит слово, получаемое конкатенацией меток на ребрах данного пути. Наибольшее практическое применение находят регуляр­ные грамматики, несколько менее популярными являются контекстно­свободные свободные грамматики. Однако, с точки зрения приложений к языкам программирования и компиляции наиболее важными являют­ся именно контекстно-свободные грамматики. Таким образом встает во­прос о необходимости разработки и реализации алгоритмов поиска пу­тей с контекстно-свободными ограничениям (англ. «Context-Free Path Querying», кратко CFPQ).
Несмотря на то, что проблема выполнения контестно-свободных за­просов широко изучена и существует целый ряд алгоритмов, ее решаю­щих , тем не менее одной из наиболее остро стоящих проблем является низкая производительность существующих алгоритмов, по­этому актуальной задачей является разработка и реализация новых ал­горитмов, решающих данную проблему.
Одним из недавно разработанных методов решения данной зада­чи является алгоритм, использующий матричное представление для получения информации о достижимостях в графе. Данный алгоритм был предложен Азимовым Р.Ш. и основан на матричных операци­ях. В его работе было показанно, что данный алгоритм демонстриру­ет достаточно хорошую производительность. Кроме того, основанный на матрицах CFPQ-алгоритм в дальнейшем стал основой для первой полноценной поддержки контекстно-свободных запросов в результате расширения графовой базы данных RedisGraph.
Матричное представление не единственный возможный способ ре­шения такого рода задач. Более того, результаты исследований пока­зали, что базовые алгоритма распознавания строк по заданной грам­матике могут быть ествественным путем обобщены на входные данные в виде граф. Например, существуют описания того, как пробле­ма поиска путей с контекстно-свободными ограничениями может быть решена с помощью использования обобщенного LL-парсера или обобщенного LR-парсера. Более того, такой подход позволяет получать информацию не только о достижимостях в графе, но и о са­мих путях .
Так, в рамках предыдущих работ была получена реализация алгоритма для выполнения контекстно-свободных запросов в графовой базе данных Neo4j. Данный алгоритм является адаптацией классиче­ского алгоритма синтаксического анализа Generlized LL для выполне­ния контекстно-свободных запросов на графах. Важно отметить, что полученный алгоритм поддерживает весь класс контекстно-свободных языков. Модифицированный GLL, так же как и оригинальный алго­ритм, возвращает информацию не только о достижимостях между вер­шинами, но и информацию для построения самих путей. Несмотря на то, что проведенное экспериментальное исследование показало практи­ческую эффективность полученного решения при работе с контекстно­свободными грамматиками, тем не менее данная реализация не позво­ляет напрямую работать наиболее распространненым на сегодняший день способом задания ограничений — с регулярными выражениями. Для их обработки сначала необходимо преобразование грамматики, что ведет к увеличению количества продукций в ней и, как следствие, ухуд­шению производительности алгоритма GLL. Обойти данную проблему может помочь выражение грамматик в виде реккурсивных автоматов, которые одинаково оптимально поддерживают как регулярные, так и контекстно-свободные грамматики.
Таким образом, целью данной работы является предоставление ре­ализации GLL алгоритма, основанного на рекурсивном автомате, для обработки входных данных в виде графа как для решения задачи до­стижимости, так и для поиска путей. Далее планируется проведение экспериментального исследования с целью выявления значимого повы­шения эффективности по сравнению с альтернативными решениями.
Купить