Sunday, May 8, 2016

NLP for Uzbek language

    Natural language processing is an essential tool for text mining in data analysis field. In this post, I want to share my approach in developing stemmer for Uzbek language.
     Uzbek language is spoken by 27 million people around the world and there are a lot of textual materials in internet in uzbek language and it is growing.
As I was doing my weekend project "FlipUz" (which is news aggregator for Uzbek news sites) I stumbled on a problem of automatic tagging news into different categories. As this requires a good NLP library, I was not able to find one for Uzbek language.
That is how I got a motive to develop a stemmer for Uzbek language.
      In short, Stemming is an algorithm to remove meaningless suffixes at the end, thus showing the core part of the word. For example: rabbits -> rabbit.
As Uzbek language is similar to Turkish, I was curious if there is stemmer for Turkish. And I found this: Turkish Stemmer with Snowball. Their key approach was to use Finite state machine.
This was an interesting approach. I liked the simplicity of it. The only thing that i had to do was to model the suffixes transformations in state machine.
As the stemmer can be applied for all kind of words, in the first step, the Nouns was the target.
Therefore, I created the state machine for nouns:
While drawing this diagram, I referenced the Uzbek language phonetics and word formation rules from the Uzbek language book. The book was very helpful. Though, I still did not use much of it yet.

I used python language, for its easiness and richness of external libraries.
Here is the source code:
from fysom import Fysom
def stem(word):
    fsm = Fysom(initial='start',
                    events=[
                    ('dir', 'start', 'b'),
                    ('dirda', 'start', 'b'),
                    ('ku', 'start', 'b'),
                    ('mi', 'start', 'b'),
                    ('mikan', 'start', 'b'),
                    ('siz', 'start', 'b'),
                    ('day', 'start', 'b'),
                    ('dek', 'start', 'b'),
                    ('niki', 'start', 'b'),
                    ('dagi', 'start', 'b'),
                    ('mas', 'start', 'd'),
                    ('ning', 'start', 'f'),
                    ('lar', 'start', 'g'),
                    ('lar', 'e', 'g'),
                    ('dan', 'd', 'e'),
                    ('da', 'd', 'e'),
                    ('ga', 'd', 'e'),
                    ('ni', 'd', 'e'),
                    ('dan', 'start', 'e'),
                    ('da', 'start', 'e'),
                    ('ga', 'start', 'e'),
                    ('ni', 'start', 'e'),
                    ('lar', 'f', 'g'),
                    ('miz', 'start', 'h'),
                    ('ngiz', 'start', 'h'),
                    ('m', 'start', 'h'),
                    ('si', 'start', 'h'),
                    ('i', 'start', 'h'),
                    ('ng', 'start', 'h'),
                    ('miz', 'f', 'h'),
                    ('ngiz', 'f', 'h'),
                    ('m', 'f', 'h'),
                    ('si', 'f', 'h'),
                    ('i', 'f', 'h'),
                    ('ng', 'f', 'h'),
                    ('miz', 'e', 'h'),
                    ('ngiz', 'e', 'h'),
                    ('m', 'e', 'h'),
                    ('si', 'e', 'h'),
                    ('i', 'e', 'h'),
                    ('ng', 'e', 'h'),
                    ('lar', 'h', 'g'),
                    ('dagi', 'g', 'start')
                    ]
                );
    i = len(word) - 1
    j = len(word)
    while(True):
        if (i<=0):
            break
        v = word[i:j]
        #print v
        res = fsm.can(v)
        if (res):
            if (v == 'i' and fsm.can(word[i-1:j])):
                i = i - 1
                continue
            fsm.trigger(v)
            if (fsm.current == 'h'):
                if (word[i-1:i]=='i'):
                    i = i - 1 #skip i
                    if (word[i-1:i]=='n' ):
                            # ning qushimchasi
                        fsm.current = 'start'
                        continue
            elif (fsm.current == 'b'):
                fsm.current = 'start'
            j = i
            # print fsm.current
        i =  i - 1
    return word[:j]
It is available in github also.
We are collaborating with Uzbek developers friends to develop full-featured NLP library for Uzbek language.
The next step is to apply stemming for Verbs.
Let me know if you have some ideas on this. thanks.

Test outputs:

print stem('mahallamizdagilardanmisiz')
mahalla