In this work-in-progress paper, we propose the algorithm for creation of a tree structure of the Slovak sentence. The tree structure of a sentence represents the relationships and dependencies between words in a sentence. The root of the tree is predicate. Finding the right sentence structure helps to understand its meaning better. In Slovak language, words have different forms, and there are various ways how to compose sentences. We found that the algorithm properly works for simple sentences with one predicate and subject and sentences connected with one conjunction.
The natural language processing in the Slovak language is a very actual and fruitful area of research interest. It is the most challenging issue to arise in recent years. The Slovak language belongs to a group of a flexible language and has complex rules for word inflection as there are many possible word forms, classification of contexts. One part of natural language processing is understanding the structure of sentences. This work-in-progress paper proposes the algorithm for creation of a tree structure of the Slovak sentence. Algorithm is not base 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: "Lucia cˇíta vel’mi peknú knihu." 1 is shown in Figure 1.
Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
1Lucy is reading very beautiful book.
The natural language processing in the Slovak
language is a very actual and fruitful area of
research interest. It is the most challenging issue
to arise in recent years. However, we can find
several tools, dictionaries and conferences in this
area of research. For example, Paper Online
Natural Language Processing of the Slovak
Language presents the web site for NLP tools
such as lemmatization, correction, finding
part-ofspeech of words in the sentence and others [
Slovak and Czech language have similar
grammatical rules and structure of sentences.
Therefore tools and algorithms for natural
language processing of the Czech language can
also be inspiration for algorithms for the Slovak
Language. There are three main universities
in the Czech republic that deals with natural
language processing. One is Masaryk University
in Brno and the other is Charles University in
Prague. Masaryk university created tools for
adding diacritics into texts, topics detection,
named entity recognition, morphological analyzer
"Majka" and other [
Grammatical rules define the structure of a sentence. A sentence member is a basic unit of a sentence. It is part of a sentence, which is in some relation to the other parts. Main sentence members are subject and predicate.
Subject is part of the sentence, which describes who or what is doing something. It could be noun, adjective, pronoun or numeral. Subject should be in the first case. In Slovak sentences, subject could be expressed or unexpressed. Unexpressed subject means that subject is not in this sentence. For example, in the sentence "Nakupujeme", which means We are shopping, is only verb and no subject. Verb "Nakupujeme" is in plural and in first person form, it is noticeable in Slovak language that subject is "we". Predicate expresses an action or situation of the subject. It could be verb or auxiliary verb plus noun, adjective or numeral. In Figure 1., subject is "Lucia" and predicate is "cˇíta".
Other sentence members are an object, attribute and adverbial. Object specifies predicate and shows object. It could be noun or pronoun and it should not be in the first case. Adverbial gives more information about time, place, manner or cause. Adverbial could be adverb or noun. Attribute modifies subject and it is adjective, pronoun or numeral. There are two types of attribute. One type has to have the same grammatical categories as subject and the other type has at least one of the grammatical categories different from subject. In Figure 1., object is "knihu" and attribute is "peknú". In the sentence "Deti prišli vecˇer."3, adverbial is "vecˇer". Every sentence member except for predicate can be in a sentence more than one time. Conjunction or commas connect same sentence members. These sentence members create a relation between them. The word which depends on the other word in relation is called dependent and another word is superior.
The Slovak language distinguishes three types
of sentence: simple, compound and fundament
sentence. Simple sentence has only one predicate.
Compound sentence has two or more predicates.
Part of compound sentence are connected by
conjunction or commas. The third type has
no subject, only verb or noun. Verb in these
sentences usually describes general action, for
example "Prší" 4 [
Tvaroslovník is a database of all forms of Slovak words. It was created at the University of Pavol Jozef Šafárik. The database contains a lot of Slovak words, their form and other information about these words. 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. 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, 3 Children came in the evening. 4It is raining. categories: grammatical categories, there are different for every part-of-speech.
The algorithm for finding a tree structure of a sentence has Slovak text as input. In the first step, an input is split into sentences by using a dot as a separator. Sentences are put into list of sentences. Then algorithm iterates over list of sentences. It finds all forms and characteristics for each word in a sentence by using Tvaroslovník. In the next step, the algorithm finds out how many of a predicates sentence has. If there is more than one predicate, the algorithm separates sentence into smaller parts. Separation is done according to conjunction or coma. The next steps are same as steps for sentences with one predicate. However, the algorithm uses these smaller parts instead of a whole sentence. After identifying the type of sentence, algorithms checks how many of same sentence members are in a sentence. If there is more than one, the algorithm takes this part of a sentence and creates a relation between each member and comma or conjunction, which is connecting these members. These relations are added to the list of possible relations of sentence. After that, the algorithm takes tuples of words, which are standing next to each other and tries to choose the possible relationship between those words. The algorithm has defined 29 types of relations between words. Except for the definition of part-of-speech and grammatical categories, every relation has its priority defined by empirical experience. All types of relations and their priorities are presented in Table 2.
For each tuple algorithm iterates over all form of words of tuple and try to find suitable word forms according to possible types of relations. After choosing the type of relation for each tuple, relations are put in the list of possible relations and sorted according to priority from the highest to the smallest. If there is more than one possible relation, algorithm put into list of possible relations all relations. Next, the algorithm selects the relation with the highest 5 book categories gender: feminine; number: singular; case: nominative gender: feminine; number: singular; case: genitive gender: feminine; number: singular; case: dative gender: feminine; number: singular; case: accusative gender: feminine; number: singular; case: locative gender: feminine; number: singular; case: instrumental gender: feminine; number: plural; case: nominative gender: feminine; number: plural; case: genitive gender: feminine; number: plural; case: dative gender: feminine; number: plural; case: accusative gender: feminine; number: plural; case: locative gender: feminine; number: plural; case: instrumental priority at the list. Selected relation is added to the list of final relations. This list helps built the tree. After that, the tuples are removed from the list of possible relations, and the dependent word is removed from a sentence. Every relation, which has the same dependent word and other superior word as selected relation, is removed from the list of possibilities. Then words next to the removed word are candidates for a new relation, therefore algorithm checks if they can form relation. If there is some type of relation, this new relation is added to the list of possible relations, and then the list is sorted according to priority again. If there are two relation with same dependent and superior word form, but they have different type of relation as selected relation, algorithm creates copy of list of possible relation. Algorithm creates from copied list other possible tree structure with different types of relations. The process is repeated again until there is only one word in a sentence.The last step is to build a tree structure from the list of final relations. Algorithm for finding tree structure is implemented in Java programming language and data are stored in Java Collections classes List and Map. If there is some ambiguity in relation, algorithm finds all possible tree structure of sentences
The example below illustrates the work of the algorithm. Input is the sentence "Lucia cˇíta vel’mi peknú knihu." 6 First, the algorithm creates 6Lucy is reading very beautiful book. a list of words from a sentence and finds all possible forms from Tvaroslovník and puts it to the map. In our example, the algorithm generates the following map:
Lucia: [idWord: 128848, idForm: 1, form: Lucia, part-of-speech: noun, categories: gender: feminine; number: singular; case: nominative] cˇíta: [idWord: 8679, idForm: 6, form:cˇíta, part-of-speech: verb, categories: person: third; number: singular; time: present] vel’mi: [idWord: 102690, idForm: 0,form: vel’mi, part-of-speech: adverb, categories: None] peknú: [idWord: 56578, idForm: 17, form: peknú, part-of-speech: adjective, categories: gender: feminine; number: singular; case: accusative] knihu: [idWord: 27834, idForm: 4, form: knihu, part-of-speech: noun, categories: gender: feminine; number: singular; case: accusative] After that, the map of possible relations is created with their priorities and it is sorted according to priority: First iteration Relation with priority 9 is chosen. This relation is added to the list of final relations and removed from the list of possible relations. The algorithm is going through the list of possible relations and removes every relation with dependent word vel’mi. Dependent word is removed from a sentence, and the algorithm checks if a new relation is created. After removal, there is a new possible relation between words cˇíta and peknú with priority 2. This new relation is added to the list of possible relations, and the list is sorted again. After the first iteration, there is the sentence "Lucia cˇíta peknú knihu."7.The list of final relations is: dependent: vel’mi and superior: peknú, priority: 9 And the list of possible relations is: cˇíta, Second iteration Relation with priority 4 is selected. This relation is added to the list of final relations and removed from the list of possible relations. the algorithm is going through the list of possible relations and removes every relation with dependent word peknú. Dependent word is removed from sentence, and the algorithm checks if a new relation is created. There is a new possible relation between words cˇíta and knihu with priority 2. This new relation is added to the list of possible relations, and list is sorted again. After second iteration, the sentence is "Lucia cˇíta knihu."8. The list of final relations is: Third iteration Relation with priority 2 is selected. This relation is added to the list of final relation and removed from the list of possible relations. The algorithm is going through the list of possible relations and removed every relation with dependent word knihu. Dependent word is removed from sentence and it checks if a new relation is created. However, there is no possibility to create a new relation. After third iteration, the sentence is "Lucia cˇíta.".9 The list of final relations is: 8Lucy is reading book. 9Lucy is reading. Fourth iteration Relation with priority 1 is chosen. This relation is added to the list of final relations and removed from the list of possible relations. Dependent word is removed from the sentence. Only last word remains in the sentence and the list of possible relations is empty, therefore the fourth iteration is the last one and all needed relations are in the list of final relations. The list of final relations is:
In the last step, a tree structure is built from the list of final relations. Figure 2. illustrates the gradual construction of a tree structure. (a),(b),(c) show a partial tree of a sentence after iterations, and (d) gives an output of a whole sentence after the fourth iteration. 4
In this paper, we have proposed the algorithm for creating a tree structure of the Slovak sentence. We have presented the running of our algorithm on an example of Slovak sentence "Lucia cˇíta vel’mi peknú knihu". However, the Slovak language has various orders of words and combinations of sentence members. The algorithm also finds a tree structure of sentences: example "Lenka simple sentence, for nakupuje oblecˇenie."10 10Lenka is buying clothes. (a) First iteration.
(b) Second iteration. (c) Third iteration.
(d) Fourth iteration. simple sentence without subject, for example "Krácˇame do školy."11 simple sentence with same sentence member, for example "Milý a pekný Martin kupuje kvety Lucke."12 compound sentence with two predicates, for example "Deti sa hrajú na ihrisku a rodicˇia sa rozprávajú."13 compound sentence with two predicates and same sentence member, for example "Pekný a upravený dom stojí na kraji ulice a bývajú v nˇ om dvaja l’udia."14 We aim to improve the presented algorithm in our future research. Particularly, our objective is to analyze the following special types of sentences: fundament sentence, for example "Prší." 15 11We are going to school. 12Nice and handsome Martin buys flowers for Lucy. 13Children are playing on a playground and parents talk. 14A beautiful and tidy house stands on the side of the street and two people are living in it.
15It is raining. simple sentence with a complex predicate, for example "Mal by som už íst’." 16 compound sentence with more predicates, for example "Na záhrade máme cˇervené tulipány, ktoré nám darovala stará mama a vedl’a tulipánov je záhon ruží." 17 The testing of the algorithm for the various types of Slovak sentences and the visualization of the outputs in the user friendly environment are the main objectives of our future research.