OPTIMIZATION OPTIONS OF WORD FORMS MORPHEMIC ANALYSIS ON THE BASIS OF STATISTICAL KNOWLEDGE
Morphemic analysis of word forms
Word forms are composed of 2 types of morphs – roots and affixes. Some affixes can be found only before roots, some - only after roots and some of the affixes – within roots. Within this framework word form can be represented by a sequence of 3 groups of morphs:
- The prefix group consists of a sequence of affixes, which can be found only before roots (prefixes, the left part of confixes).
- The postfix group consists of a sequence of affixes, which can be found only after roots (suffixes, the right part of confixes).
- The stem group consists of a sequence of stems, and possibly affixes, which can be interchange with stems (infixes, interfixes, etc.)
The morphs set of the prefix group stands for , the morphs set of the stem group – , the morphs set of the postfix group – , wherein – are respectively the number of morphs of the prefix group, the stem group, and the postfix group for a given natural language. Each natural language has its own sets and its own amount of determined by its morphology.
Let us consider the analysis on the example of the prefix group. There may be more than one prefix morph in a word, that is why even after the first successful check, one should move to the next step, preceding the analysis of the rest of the word form, and repeat these steps for as long as the inclusions will no longer be detected. In general, each of the morphs set can be found both at the beginning, at the end and in the middle of the prefix group. Therefore, every step should contain verification of inclusions in the word form each of the morphs set .
The disadvantage of this approach is the necessity of looking over all the elements of set at each step sequentially. And while at the first step the number of verifications is equal to , then amount of verifications at the next steps becomes equal to , where - the number of ways of analysis found at the previous step.
The postfix group has the similar way of analysis; with the only difference that it is more convenient to begin the analysis in the end of the word form and the analysis involves morphs from the set .
The reiterated complete verification of all elements of set slows down work on the analysis of text.
Optimization of the analysis
There are peculiarities in natural languages that can help in acceleration of analysis.
The 1st peculiarity. The probabilities of coming across different morphs in a group differ from each other.
The 2nd peculiarity. The probability of coming across a morph in a word form depends on the location in the group.
The 3rd peculiarity. The probabilities of coming across different combinations of morphs differ from each other.
The 4st peculiarity. The probabilities of coming across different combinations of morphs depends on the location in the group.
Considering these statistics features, it is possible to accelerate the analysis. However, this would require collecting statistics on the specific natural language, upon which primarily perform verification of that morphs and their combinations, which are more common in this place of analysis.
Possible solutions of optimization based on statistics
Solution for the 1st peculiarity. Instead of disordered set of morphs it is possible to use their one-dimensional ordered array, in which a morph with a higher probability of coming across has a lower index, than a morph with a lower probability. Verification of morphs for presence in word form should be performed in ascending order of their index. In this case, the morphs with the greatest probability will be checked first.
Solution for the 2nd peculiarity. It is possible to use two-dimensional ordered array. The 1st row of array includes morphs in order of descending of their probability of coming across at the 1st step. The 2nd row of array includes morphs in order of descending of their probability of coming across at the 2nd step, etc. Each step of analysis has its own corresponding number of the array row. As a result, at each step, the morphs with the highest probability of coming across will be checked first at this step.
Solution for the 3rd peculiarity. One-dimensional ordered array used as the solution for the 1st peculiarity can be supplemented with the combinations of morphs with a higher probability of coming across. The higher probability of coming across the lower index in the array. The verification is performed in order of increasing of element’s index. In this case, the morphs (combinations) with the highest probability will be checked first.
Solution for the 4st peculiarity. Two-dimensional ordered array used as the solution for the 2nd peculiarity can be supplemented with the combinations of morphs with a higher probability of coming across. Morphs and their combinations in each row are sorted in descending order of probability of their coming across. In this case, the morphs (combinations) with the highest probability will be checked first.
These solutions with the corresponding change of analysis algorithms will enable to find ways to the final result much faster. After receiving the result, one can discard the remaining verifications, thereby reducing the time of analysis.
These solutions are a practical approach for use with the prefix and postfix groups, since the number of elements is relatively small and the arrays will not be too cumbersome in them.
The problem of analysis based on statistics
The main problem is existence of homonyms. Homonyms are identical in spelling but different in their meanings, thus the analysis of a homonym should give several results instead of one. Therefore the analysis should not terminate at the first found result; it should pass on, since there is a possibility of finding another option for the analysis and possibly not even one.
The consequence of the requirement to continue the analysis after finding the first option is the necessity for a complete search of all morphs, and combinations thereof. If so, there is no point in their arrangement – they still have to be looked through in any case, therefore, time spent on analysis, will be the same one way or another.
In order to get out of this situation, we shall consider 3 situations:
- The element in its order of appearance has already come across during the set of statistics in this language .
- The element in its order of appearance cannot be come across, since the language morphology does not allow its appearance in the current location (for example, the verb endings cannot be found together, when examining the location, far from the end of the postfix group).
- Other situations, which are not related to par. 1 и 2. Here .
In the 1st situation the searching of elements should be continued, since a common situation has already occurred in a given language.
In the 2nd situation the searching of elements should be ceased and then a shift should be produced.
In the 3rd situation it is not clear whether the searching of elements should be continued a shift should be produced. If continued then there is another question – how many elements of the set from с should be searched before ceasing and moving to another step?
To implement a flexible solution that can carry into effect the ceasing of searching as well as its continuation, an additional numerical parameter is introduced, which will determine the actions in the 3rd situation. Let us call it “the depth of the morphemic analysis”. It will determine number of the ordered set elements which are to be processed after elements with have proceeded. When such elements are not processed (with the exception of cases described below), when , one element is processed, upon which the shift to the following step is produced. Accordingly, when , 2 elements are processed, etc.
It should be noted that when , there may be cases where processing elements with is still necessary. For example, if the analysis is over, but no final alternative was found. In such cases, it is necessary go back to the step at which the analysis was interrupted, and continue with the interrupted point. In order to make it possible, it is necessary to be remembered all the states in which the analysis was interrupted.
It is more sensible to define parameter outside the decomposition algorithm, so that the user could choose the behavior of the analysis. During initial set-up of the model the larger value of is more appropriate, since the statistics has not been collected yet and almost all the elements have . According to continuation, the values of can be gradually reduced, looking for a compromise between performance and accuracy of the analysis.
The proposed optimization options can reduce time on morphemic analysis of word forms. This will require a preliminary collection of statistics on the basis of a language corpus. Moreover, the presence of suffixes and roots’ dictionaries of this language is a necessary condition as well.
Zheltov P.V. Lingvisticheskie processory, formal’nye modeli i metody: teorija i praktika [Linguistic processors, the formal models and methods: theory and practice]. – Cheboksary: Izd-vo Chuvash. un-ta, 2006. – 208 p. [In Russian]
Zheltov P.V. Formal’nye metody v sravnitel’no-sopostavitel’nom jazykoznanii [Formal methods in comparative linguistics]. – Cheboksary: Izd-vo Chuvash. un-ta, 2006. – 252 p. [In Russian]
Zheltov P.V. Lingvisticheskie processory v sistemah iskusstvennogo intellekta [Linguistic processors in systems of artificial intelligence]. – Cheboksary: Izd-vo Chuvash. un-ta, 2007. – 100 p. [In Russian]