Introduction

Natural language processing is part of artificial intelligence and linguistics, focusing on understanding human language by computers. There are different tasks in natural language processing:

• Automatic summarization provides summaries or detailed information of text of a known type.

• Co-reference resolution refers to a sentence or more extensive set of text determining which word refers to the same object.

• Discourse analysis refers to the task of identifying the discourse structure of a text.

• Machine translation refers to automatic translation of text from one human language to another.

• Morphological segmentation refers to separate words into individual morphemes and identifies the class of the morphemes.

• Named entity recognition describes a stream of text and determines which text items relate to proper names.

• Optical character recognition gives an image representing printed text, which helps determine the corresponding or related text.

• Part of speech tagging describes a sentence, determines the part of speech for each word.

Some of the tasks can be used as a subtask for more complex assignments [1].

Semantic and syntactic parsing is also part of natural language processing, aiming to provide internal relations between words. There are two approaches for finding the structure of sentence: constituent parsing and dependency parsing. Constituent parsing provides a constituent tree where nodes are phrases. The goal is to find these phrases and their relations. The approaches of constituent parsing include the chart-based and the transition-based models. Both have statistical and neural models. Dependency parsing is using bilexicalized dependency grammar, which contains all semantic and syntactic dependencies. Dependency parsing models are divided into two groups: graphbased models and transition-based models, both of which have their own statistical or neural network approaches [2]. This work-in-progress paper proposes the improvement of algorithm for creation of a tree structure of the Slovak sentence [19]. This algorithm is not based on statistical data from the corpus, but takes raw data from Tvaroslovník. It is a database of all forms of Slovak words. The tree structure of a sentence can represent the relationships and dependencies between words in a sentence. The root of the tree is a predicate. The tree structure for Slovak sentence: Hodina dnes za£ala malým kvízom.1 is shown in Figure 1.

State of Art

Institute of Formal and Applied Linguistic at Charles University in Prague has created the Prague Dependency Corpus, which is an excellent contribution to natural language processing. Several tools have been developed to find out a sentence structure or work on other natural language processing tasks based on this corpus or Universal Dependency Treebank. For example [3]:

• Netgraph -this is a graphically oriented client-server application for searching in an annotated corpus.

• TrEd -an editor used to search for a syntactically annotated sentence structure.

• Morfo -a system for morphological analysis of the Czech language.

kvízom malým za£ala dnes Hodina • MorfoDita -a free tool for morphological analysis of natural language texts.

• Moses -a statistical machine translation system that automatically allows training translation models for any language pair.

• UDPipe -a trainable channel for tokenization, labeling, lemmatization, and relationship analysis. Institute developed two version of UDPipe [4], [5].

The Natural Language Processing Centre at Masaryk University in Brno is mainly engaged in research into the processing of the Czech, English, and Slovak languages. They deal with morphological, syntactic, and semantic analysis and the creation of corpora and dictionaries. The institute has created several tools that work with morphological, syntactic, and semantic analysis. Examples include [6]:

• Majka -morphological analyzer for Slovak, Czech, Polish, Swedish, German language.

• The Sketch engine -a tool used to search for information from text corpora.

• CZ accent -a tool for adding accents to text.

• Synt and SET -parsers used to determine the structure.

• Visual Browser -Java software that visualizes data into RDT format.

Institute of Theoretical and Computational Linguistics at

Charles University develops computational tools for automatic language processing, for example, syntactic annotation of Czech corpora or grammar-based treebank of Czech language.

[7]. Similar to the Czech language, there are several tools, dictionaries, and conferences in natural language processing research in Slovak languages. Language Institute of L'udovít Štúr offers a wide selection of dictionaries. These include a [8], [9], [10] and much more [11]. It also provides the Slovak National Corpus. It is an electronic database, mainly containing Slovak texts from 1955 from different styles, genres, thematic areas, region and other. Language Institute of L'udovít Štúr developed tools for searching words in Slovak National Corpus and working with them.

For example, DEVELOPER visualizes an occurrence of one or two words in the corpus. DIAKRITIK corrects the diacritics, and KOLOKAT visualizes distances between two terms in the corpus [12]. Every two years, the institute organizes a conference SLOVKO on natural language processing [13]. In 2017, D. Zeman presented an article Slovak Dependency Treebanks in Universal Dependencies about converting the syntactically annotated part of the Slovak National Corpus into the annotation scheme known as Universal Dependencies. Universal Dependencies is an international standard and also the largest database of freely available dependency treebank [14]. Database of Slovak words and their forms Tvaroslovník was created at Pavol Jozef Šafárik University at Košice [15], [16]. Master thesis [17] deals with the creation of an algorithm for finding the structure of the sentence.

Dictionaries

It is necessary to have more information about words to create a sentence structure. Therefore we are using the dictionary Tvaroslovník and Valency dictionary for our algorithm of syntactic analysis.

Tvaroslovník

Tvaroslovník is a database of all forms of all Slovak words from [8] and [9]. Every row contains information about form of the word, its part-of-speech and grammatical categories of the word. Data in Tvaroslovník was collected from the dictionary of Slovak language. Database contains approximately 220,000 words and 24,000,000 records of words and all their forms. All data and information are saved in one table. There is a list of columns:

• idWord -unique identification number for word,

• idForm -unique identification number of word's form,

• form -a form of a word,

• part-of-speech,

• categories -grammatical categories, there are different for every part-of-speech. Table 1 shows an example of records for the word hodina 2 .

Valency dictionary

Valency dictionary contains two types of the most common covalence between words. First is covalence between verb and preposition or verb and the most common case of the following term. Covalence between noun and preposition is the second type of valency dictionary. To built the valency dictionary, we took noun and verbs from Tvaroslovník and covalencies with prepositions and cases were automatically created from examples in Krátky slovník slovenského jazyka [18]. Dictionary cointans columns:

• idWord -unique identification number for word from Tvaroslovník,

• preposition -preposition which follow after noun or verb,

• case -case of word after noun or verb.

Table 2 illustrates examples from dictionary of covalence.

Tree structure of sentence

We presented the main idea of the algorithm for finding the tree structure in the article [19]. For the algorithm, we expanded the table of relations and added cases of Slovak sentences, which we describe in the subsection Special cases of sentences. Table 3 illustrates the new relationship table, and algorithm 1 describes the pseudocode for the main idea of the tree finding algorithm.

Special cases of sentences

Slovak is a flexible language and has many peculiarities that we took into account when creating the method.

• Multiple sentence member: The first is multiple sentence members. We find out whether there is a conjunction or a comma in the sentence during searching for initial possible relations. If so, we look at the word before and after the conjunction if it is the same part of speech and has the same grammatical categories. After fulfilling the condition, we add a relation between conjunction and the words to the possible relations. The conjunction then takes over the grammatical categories of the words it connects. For example, in sentence Noviny a £asopisy pí²u o celebritách. 3 words noviny and £asopisy are same sentence member, therefore there are relations noviny and a with priority 12 and £asopisy and a with priority 12 in the list of possible relations. Word a participates as noun in nominative case. Algorithm 1: Pseudocode for finding tree structure algorithm • Multiple verbs in sentence: Occurrence of several verbs in a sentence is another specification of the sentence. Before we start looking for possible relationships in a sentence, we determine if this is not the case. After determining verbs, we search whether a conjunction or a comma is in the sentence between them. Finding a comma or conjunction classifies a sentence as a sentence. Therefore, we divide the sentence according to the conjunction or comma into subsections with which we work as separate sentences. We connect these sentences with the relationships between the conjunction or comma and the roots of subsentences in the resulting output. Figure 2 shows us example of sentence structure for sentence Mama £íta noviny a otec pí²e správu. 4 In a sentence containing more verbs without conjunction or comma between them, we assume that there is a compound verb relation. Therefore, we combine the found verbs with the relation and add them to the list of possible relations. Figure 3 shows us example of such sentence structure for sentence Ráno za£alo pr²a´.5

• Same form of word: Some words have the same form in several cases, so it is sometimes difficult to determine which relationship they can form. We find all possible relations for the word. In the method where we gradually iterate over the list of possible relations and remove relations with the same dependent word as the currently selected relation, we locate a relation with the same dependent and superior word but with a different priority. We create another list of final and possible relations assigning a relation with a different priority. The method then outputs two trees. Figure 4 illustrates the two possible outputs for sentence Diev£a upieklo mame perníkové srdce.6

• Different part-of-speech for same form: Expect a word having the same form in multiple cases may also have the same form for multiple parts of speech. For example, the word to is a pronoun and particle. We created a list that contains the most commonly used part of speech for these words. If we set the method to find only the most relevant sentence structures, we use only the most often used part of speech for a form. • compound sentences: Te²í sa z jeho krásy a uºíva si pokojný relax. 9 ,

• sentences with multiple sentence member:

Uprostred hlu£ného a ubehaného meste£ka leºí krásny zelený park. 10 ,

• sentences with compound predicate: V mestskej £asti si môºu náv²tevníci uºiḱ úpalisko. 11 .

middle of the forest. 9 She enjoys its beauty and enjoys peaceful relaxation. 10 In the middle of a noisy and deserted town lies a beautiful green park.

11 Visitors can enjoy the swimming pool in the city.

We created this dataset manually. To each sentence, we added the required tree structure. As a result, we received 85 identical tree structures. The difficulties for finding incorrect structure were:

• Digital number in a sentence. For example, Hrad vznikol pravdepodobne v druhej polovici 13. storo£ia. 12• Changing the position of words in a nominal predicate. For example, Vhodná je paralela z £ias môjho starého otca. 13In our future work we want to focus on: