Скачать UCFS - скачать исходный код UCFS

UCFS

Другой исходный код

1.0.0

Скачать

UCFS

Строить Тест

О
Использование
- Из источников
- Использование JAR
- Пример формата CFG
- Пример формата RSM
Производительность
- Графики
- Грамматика
- Результаты
- Больше результатов

Примечание: проект под тяжелой разработкой!

О

UCFS- это Nuversal C Ontext- Free S Olver: инструмент для решения проблем, связанных с контекстным и обычным языковым пересечением. Примеры таких проблем:

Диапазон
Запрос пути без контекста (CFPQ)
Достигаемость без контекста языка (CFL-R)

Использование

Интерфейс командной строки

 Usage: kotgll options_list
Options: 
    --input -> Input format (always required) { Value should be one of [string, graph] }
    --grammar -> Grammar format (always required) { Value should be one of [cfg, rsm] }
    --sppf [ON] -> Sppf mode { Value should be one of [on, off] }
    --inputPath -> Path to input txt file (always required) { String }
    --grammarPath -> Path to grammar txt file (always required) { String }
    --outputPath -> Path to output txt file (always required) { String }
    --help, -h -> Usage info

Из источников

Шаг 1. Репозиторий клона

git clone https://github.com/FormalLanguageConstrainedPathQuerying/kotgll.git

или

git clone [email protected]:FormalLanguageConstrainedPathQuerying/kotgll.git

или

gh repo clone FormalLanguageConstrainedPathQuerying/kotgll

Шаг 2. Перейдите в папку

cd kotgll

Шаг 3. Запустите команду справки

gradle run --args="--help"

Вы увидите сообщение «Список параметров».

Пример

 gradle run --args="--input graph --grammar rsm --sppf off --inputPath src/test/resources/cli/TestGraphReadWriteCSV/dyck.csv --grammarPath src/test/resources/cli/TestRSMReadWriteTXT/dyck.txt --outputPath ./result.txt"

Использование JAR

Шаг 1. Загрузите последнюю банку

 curl -L -O https://github.com/FormalLanguageConstrainedPathQuerying/kotgll/releases/download/v1.0.0/kotgll-1.0.0.jar

Шаг 2. Запустить банку с Java

 java -jar kotgll-1.0.0.jar --input graph --grammar rsm --sppf off --inputPath src/test/resources/cli/TestGraphReadWriteCSV/dyck.csv --grammarPath src/test/resources/cli/TestRSMReadWriteTXT/dyck.txt --outputPath ./result.txt

Пример формата CFG

 StartNonterminal("S")
Nonterminal("S") -> Terminal("subClassOf_r") Nonterminal("S") Terminal("subClassOf")
Nonterminal("S") -> Terminal("subClassOf_r") Terminal("subClassOf")
Nonterminal("S") -> Terminal("type_r") Nonterminal("S") Terminal("type")
Nonterminal("S") -> Terminal("type_r") Terminal("type")

Пример формата RSM

 StartState(id=0,nonterminal=Nonterminal("S"),isStart=true,isFinal=false)
State(id=0,nonterminal=Nonterminal("S"),isStart=true,isFinal=false)
State(id=1,nonterminal=Nonterminal("S"),isStart=false,isFinal=false)
State(id=4,nonterminal=Nonterminal("S"),isStart=false,isFinal=false)
State(id=3,nonterminal=Nonterminal("S"),isStart=false,isFinal=true)
State(id=2,nonterminal=Nonterminal("S"),isStart=false,isFinal=false)
State(id=6,nonterminal=Nonterminal("S"),isStart=false,isFinal=true)
State(id=5,nonterminal=Nonterminal("S"),isStart=false,isFinal=false)
TerminalEdge(tail=0,head=1,terminal=Terminal("subClassOf_r"))
TerminalEdge(tail=0,head=4,terminal=Terminal("type_r"))
TerminalEdge(tail=1,head=3,terminal=Terminal("subClassOf"))
NonterminalEdge(tail=1,head=2,nonterminal=Nonterminal("S"))
TerminalEdge(tail=4,head=6,terminal=Terminal("type"))
NonterminalEdge(tail=4,head=5,nonterminal=Nonterminal("S"))
TerminalEdge(tail=2,head=3,terminal=Terminal("subClassOf"))
TerminalEdge(tail=5,head=6,terminal=Terminal("type"))

Производительность

Алгоритм GLL был изменен для поддержки ввода графика. Предложенная модификация была оценена на нескольких реальных графиках для сценария поиска всех пар охвата.

Конфигурация машины : ПК с Ubuntu 20.04, Intel Core I7-6700 3,40 ГГц ЦП, ОЗУ DDR4 64 ГБ.

Конфигурация среды :

Java Hotspot (TM) 64-битная виртуальная машина сервера (Build 15.0.2+7-27, смешанный режим, общий доступ).
Конфигурация кучи JVM: 55 ГБ как XMS и XMX.

Графики

Графические данные выбраны из набора данных CFPQ_DATA.

Подробное описание графиков указано ниже.

Графики анализа RDF

Название графика	\| V \|	\| E \|	#subclassof	#тип	#broadertransitive
Фермент	48 815	86 543	8 163	14 989	8 156
Экрасс	239 111	360 248	90 962	72 517	0
Иерархия	45 007	490 109	490 109	0	0
Идти	582 929	1 437 437	94 514	226 481	0
Геоспекты	450 609	2 201 532	0	89 065	20 867
Таксономия	5 728 398	14 922 125	2 112 637	2 508 635	0

Грамматика

Все запросы, используемые в оценке, являются вариантами запроса одного поколения. Обратное отношение x и соответствующий край обозначается как x_r .

Грамматики, используемые для графиков RDF :

G ₁

 S -> subClassOf_r S subClassOf | subClassOf_r subClassOf 
     | type_r S type | type_r type

Представление грамматики без контекста G ₁ в репозитории можно найти здесь.

Представление грамматики без контекста G ₁ в качестве рекурсивного автомата в репозитории можно найти здесь.

Результаты

Результаты оценки запросов о достижении All Pars на графиках, связанных с анализом RDF, перечислены ниже.

В каждом ряду лучшее среднее время за считанные секунды выделяется жирным шрифтом .

График	CFG	RSM	Gll4graph
Фермент	0,107	0,044	0,22
Экрасс	0,94	0,43	1.5
Иерархия	4.1	3.0	3.6
Идти	3.2	1.86	5,55
Геоспекты	0,97	0,34	2.89
Таксономия	31.2	14.8	45,4