In this paper we present a rule-based stemming algorithm for the Uzbek language. Uzbek is an agglutinative language, so many words are formed by adding suffixes, and the number of suffixes is also large. For this reason, it is difficult to find a stem of words. The methodology is proposed for doing the stemming of the Uzbek words with an affix stripping approach whereas not including any database of the normal word forms of the Uzbek language. Word affixes are classified into fifteen classes and designed as finite state machines (FSMs) for each class according to morphological rules. We created fifteen FSMs and linked them together to create the Basic FSM. A lexicon of affixes in XML format was created and a stemming application for Uzbek words has been developed Stemming is defined as the conflation of all variations of specific words to a single form called the root or stem. Stemming algorithms for some languages have been published and applied in the building of information retrieval systems, among which for English is the well-known Porter's algorithm [1,2]. According to the stemming principle, stemming algorithms can be divided into four categories, that are rule-based (truncating, affix removal) method, dictionary look-up (table lookup) method, statistical method, and mixed-method [3].
2022 Copyright for this paper by its authors. stem of the word [6]. For instance, a single word “O‘qi/ma/gan/lar/dan/mi/siz?” (Are you from those who did not read?), which in fact is a question, can be parsed as following: o‘qi to read o‘qi/ma don’t read o‘qi/ma/gan he/she di not read o‘qi/ma/gan/lar they did not read o‘qi/ma/gan/lar/dan from those who did not read o‘qi/ma/gan/lar/dan/mi/siz are you from those who did not read
An affix in Uzbek can have multiple allomorphs in order to provide sound harmony (as the phonological rules) in the word to which it is affixed. For example, the Declension suffix with generic representation –Ga has three allomorphs: –ga, –ka, –qa. The abbreviations used to show suffixes in a generic way are shown below: G: g, k, q Y: a, y K: k, g Q: k, g, g’, q T: t, d A: a,o (): the letter between parentheses can be omitted
All affixes are stored in the Suffixes.xml file. The structure of the XML file is as follows: <?xml version='1.0' encoding='UTF-8'?> <suffixes> <item fsm_id="" suff_id="" group="" pos="" class=""> <suffix allomorph="false"> <name>...</name> <exception_cut>...</exception_cut> <exception_pass>...</exception_pass> </suffix> <definition>...</definition> <old_pos>...</old_pos> <new_pos>...</new_pos> </item> </suffixes>
Here, the <suffixes> ... </suffixes> tag is the root tag, <item>...</item> teg for affixes, there are fsm_id(for FSM id in Table 1), suff_id(for affixes id in each FSM Suffixes table), group="" category="" class="" type="" ( for to express the internal division of affixes in Table 2 within word classes) attributes in <item>...</item>. The <exception_cut> </exception_cut> and <exception_pass> </exception_pass> tags are used for exceptions. The <old_pos> </old_pos> and <new_pos> </new_pos> tags indicate the state before and after the affixes under consideration in the context of open word classes. If the allomorph attribute of the <suffixes> ... </suffixes> tag is true, all allomorphs of the affixes are entered as: <suffix allomorph="true"> <allomorph> <name>...</name> <exception_cut>...</exception_cut> <exception_pass>...</exception_pass> </allomorph> <allomorph> <name>...</name> <exception_cut>...</exception_cut> <exception_pass>...</exception_pass> </allomorph> </suffix>
Declension suffixes are added in Uzbek after open word classes such as noun, adjective, pronoun, numeral and past participle. First, we learn the sequence of affixes, then we build the FSM from left to right [6,10,11,12,13].
In Figure 1, a numerical value is indicated a state. In the following stages, the states will be expressed with these numbers: 0 – ending state, 1 – initial state. The character “ε” means the empty transitions between the states. The final state is represented by 2 circles.
In the next step, the affixes in Figure 1 are numbered. In the next steps, the sequence number in Table 2 is used instead of the affixes.
In Figure 2, the right to left NFA is shown, in which the FSM position from left to right in reverse order is constructed from right to left.
Let us look at some examples of how the following Declension suffixes are made from left to right
finite automata (Figure 1): qishlog‘ (
The large number of gaps in the FSM from left to right and the depth of the FSM complicate the construction of the FSM from right to left.
Table 3 illustrates the transition from NFA to DFA. In DFA, there is only one way out of each entry and exit. There will be no empty transaction at DFA.
If we define the input state of the DFA as A, it includes the input state of the NFA 0 and the states 1,2,4,5,6,7,8 that can pass through the 0-statement empty transition. Entry in DFA A state includes all {0,1,2,4,5,6,7,8} initial cases in NFA. We analyze the new states formed as a result of trimming the suffixes of each state, after the initial case. For example, if the initial state of a word in state A is defined by the suffixes "1-5"(1 - (i)m, 2 - (i)ng, 3 - (s)i, 4 - (i)miz, 5 - (i)ngiz) in Table 2, it will cut the suffix defined on the right side of the word and move the word to the next state B.
When depicting the FSM from right to left, the state contains the final state of the NFA - 1, while from right to left the state of the FSM is the final state and is represented by 2 circular circles. In this case, the FSM ends in the state if no other suffix is found after the word that cut the suffix and the incoming state is the final state.
If we analyze the word “yaxshiroqlaridan” (from things/people which are better). The word initially passes in Figure 3, through Declension Suffixes FSM from right to left, and in this FSM, 10(dan) suffix of the word are cut and go from A to C state, then FSM cut the 3((s)i) suffix and it move from C to B state: “yaxshiroqlaridan”( A– 10 → C ) → “yaxshiroqlari”( C – 3 →B). It stops here because no suffixes after B state are found and B state is the final state. The resulting “yaxshiroqlar”(things/people which are better) word is passed to the next Noun&Adjective Suffixes FSM in Figure 5. In this FSM, the suffix 11(lar) is cut and moves from state A to state B, then cut the suffix 8 (roq) and move from B to C state: “yaxshiroqlar”( A – 11 → B) → “yaxshiroq” ( B – 8 → C) → “yaxshi” (good). The result is the stem of the word.
Most suffixes in Uzbek belong to the category of nouns[14]. Figure 6 depicts the left to right Noun Derivational Suffixes. In Uzbek, Derivational suffixes belonging to several different word groups can be added to the same base. In order to reduce errors in Figure 6, other word group suffixes that are added to the base before Noun Suffixes are also given without spaces.
The main FSM has entry from 2 FSMs: Particle and Derivational [Adv]. If adverb affixes are added to the stem, inflectional ones are not added. A sequence of connections of FSMs is given in the main FSM. Each word should be in the entry part of the main FSM. Words are passed from one FSM to another. There are 3 outputs in the main FSM: Prefixes, Pronouns, and Numbers. There are 9 paths in the main FSM. The word is passed through all the ways whichever way many affixes are stripped, we take the word in this way as a stem. Depending on the way in which the stem is found, it is possible to tell which word classes it belongs to.
Currently, the issue of creating an Uzbek stemmer has not been resolved due to insufficient NLP resources for the Uzbek language. Therefore, it is developed for Uzbek by using the rule-based structure of the language. In Uzbek sentences, words are usually concatenated with lots of suffixes, that is the reason an information retrieval system needs a quick performing stemming algorithm. In systems that work with root detection, it is recommended not to use a dictionary to increase application speed. Therefore, this study does not use any word databases. The considered method in this study can be the basis for the development of an Uzbek stemming algorithm and according to the approaches (algorithm) the python library developed that is easy to install and use in NLP applications. The software and instructions can be reached from the address [15]. This will be applied to develop a software in information retrieval system for Uzbek documents. 4. References