UCFS

UCFS

• À propos
• Usage
  • Des sources
  • Utilisation de pot
  • Exemple de format CFG
  • Exemple de format RSM
• Performance
  • Graphiques
  • Grammaire
  • Résultats
  • Plus de résultats

Remarque: Projet sous un développement lourd!

À propos

UCFS est un uc nuversal C onText- f Ree S olver: un outil pour résoudre les problèmes liés à l'intersection linguistique sans contexte et régulière. Exemples de tels problèmes:

• Analyse
• Interrogation de chemin sans contexte (CFPQ)
• Attachabilité du langage sans contexte (CFL-R)

Usage

Interface de ligne de commande

 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

Des sources

Étape 1. Référentiel de clones

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

ou

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

ou

gh repo clone FormalLanguageConstrainedPathQuerying/kotgll

Étape 2. Allez dans le dossier

cd kotgll

Étape 3. Exécutez la commande d'aide

gradle run --args="--help"

Vous verrez le message "Liste des options".

Exemple

 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"

Utilisation de pot

Étape 1. Téléchargez le dernier pot

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

Étape 2. Exécutez un pot avec 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

Exemple de format 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")

Exemple de format 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"))

Performance

L'algorithme GLL a été modifié pour prendre en charge l'entrée du graphique. La modification proposée a été évaluée sur plusieurs graphiques réels pour le scénario de recherche de toutes les paires d'accès à l'accessibilité.

Configuration de la machine : PC avec Ubuntu 20.04, Intel Core i7-6700 3,40 GHz CPU, DDR4 64 Go RAM.

Configuration de l'environnement :

• Machine virtuelle de serveur 64 bits Java Hotspot (TM) (Build 15.0.2 + 7-27, mode mixte, partage).
• Configuration du tas JVM: 55 Go XMS et XMX.

Graphiques

Les données du graphique sont sélectionnées dans le jeu de données CFPQ_DATA.

Une description détaillée des graphiques est ci-dessous.

Graphiques d'analyse RDF

Nom graphique	| V |	| E |	#subclassof	#taper	#broadertransitive
Enzyme	48 815	86 543	8 163	14 989	8 156
Éclasse	239 111	360 248	90 962	72 517	0
Go hiérarchie	45 007	490 109	490 109	0	0
Aller	582 929	1 437 437	94 514	226 481	0
Géospécies	450 609	2 201 532	0	89 065	20 867
Taxonomie	5 728 398	14 922 125	2 112 637	2 508 635	0

Grammaire

Toutes les requêtes utilisées dans l'évaluation sont des variantes de la requête de même génération. L'inverse d'une relation x et le bord respectif est désigné x_r .

Grammaires utilisées pour les graphiques RDF :

G ₁

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

La représentation de la grammaire sans contexte G ₁ dans le référentiel peut être trouvée ici.

La représentation de la grammaire sans contexte G ₁ en tant qu'automate récursive dans le référentiel peut être trouvée ici.

Résultats

Les résultats de l'évaluation des requêtes d'accès à toutes les paires sur les graphiques liés à l'analyse RDF sont répertoriés ci-dessous.

Dans chaque rangée, le meilleur temps méchant en secondes est mis en évidence en gras .

Graphique	CFG	RSM	Gll4graph
Enzyme	0.107	0,044	0,22
Éclasse	0,94	0,43	1.5
Go hiérarchie	4.1	3.0	3.6
Aller	3.2	1.86	5.55
Géospécies	0,97	0,34	2.89
Taxonomie	31.2	14.8	45.4

Plus de résultats

Plus de résultats, mais sous forme brute, peuvent être trouvés dans le référentiel kotgll_benchmarks