GSoC : Libvarnam can now stem

Very productive ten days. Libvarnam is finally stemming the words. I might not be so wrong in stating that the project is almost half complete. I’ve come up with a multi-pass stemming algorithm (although no flow-chart drawing was required – maybe I’ll draw one for clarity later) that has the *potential* to stem with a reasonable accuracy. Since the algorithm is intended to serve as a platform for many Indian languages, proper documentation is quite important. As a first step, I’ve made a separate github repository putting together the thought process that went into designing the algorithm. The first draft of the algorithm is in the file “03algorithm” here. Please note that the files 01classification and 02implementation are not updated –  those are just things I jotted down.

A rather quick explanation :

The varnam stemmer removes suffixes from malayalam words to obtain the base word. For example,
വേദനാജനകമായ : വേദനാജനകം

The algorithm does this by using a set of rules, called stem rules. The stem rule that was used in the above example is :

“മായ” => “ം”

These rules can be classified into 3 : level 1, level2, and level3. Level1 contains the shortest rules, and the most basic ones. Level2 contains the most common rules and are often 2 syllables or more long. Level3 contains the longest suffixes, like “യിരിക്കുന്നു” => “”. (More on levels at “01classification” here). For now, the classification into levels is rather a convenience than a necessity. I decided that one long list of stem rules is ugly and dividing them into 3 would be nicer. So there you go.

These stem rules reside in a database.


1. Compile the scheme file and insert values into stemrules table
2. buffer = empty_string_bufer
3. Do not stem if size of word is less than 10 bytes. (Min_stem_size)
4. While (termination_condition() is not met)
4.1 Get last letter of the word and insert it at the beginning of the buffer
4.2 if buffer is in level1
4.2.1 apply stemrule from level1, word is modified
4.2.2 if(independent_existence)
4.2.2.1 learn word
4.2.3 clear buffer
4.3 else if buffer is in level2
4.3.1 apply stemrule from level2, word is modified
4.3.2 if(independent_existence)
4.3.2.1 learn word
4.3.3 clear buffer

4.4 else if buffer is in level3
4.4.1 apply stemrule from level3, word is modified
4.4.2 if(independent_existence)
4.4.2.1 learn word
4.4.3 clear buffer


5. Learn the stemmed word

TERMINATION CONDITION
1. Return true if :
a) The word ends with ം.
b) If the word ends with a consonant and there is no added swara eg : പരീക്ഷ (pareeksha)
c) If the buffer contains the rest of the word (or whole of it).

There is something wrong with code indentation in wordpress. Click on the screen shot to see the neatly indented version on sublime text editor.

The algorithm
The algorithm

For example, consider the stemming of the word എന്നിവിടങ്ങളിൽ. Initially, the buffer is empty.

1. Shift word ending to buffer. Buffer now contains ൽ

2. Buffer contents (ൽ) does not correspond to a stem rule in any level.

3. Shift word ending to buffer, buffer now contains ളിൽ

4. There exists a stem rule in level 2 “ളിൽ” => “ൾ”. Apply this stem rule to the word. Word now becomes എന്നിവിടങ്ങൾ

5. Clear the buffer

6. എന്നിവിടങ്ങൾ is independent. That is, it is a meaningful word. Hence learn it. This step (learning) is not necessary in stemming, but is crucial to improve varnam’s predictions.

7. Shift word ending to buffer. Buffer now contains ൾ. Not part of a stem rule.

8. Shift the next ending to buffer. Buffer now contains ങ്ങൾ. There is a stem rule “ങ്ങൾ” => “ം” in level 2. Apply stem rule, and the word becomes  എന്നിവിടം. (Varnam learns this word too)

9. The algorithm continues by shifting the endings of  എന്നിവിടം. Since the contents of the buffer will not correspond to a stem rule at any point of time, the algorithm eventually terminates.

 

The termination condition needs some refinement. Condition a) and b) is not being used right now. Stemming terminates when there is no more element left in the word to shift to the buffer. This seems to work fine right now, and if it continues to work, I will drop conditions a) and b) altogether.

The accuracy of the stemmer is ultimately determined by how good and accurate the design of stem rules are. This requires a lot of trial and error, and some of the stem rules are in the mlstemmer repository. By careful choice of the stem rules, an accuracy of more than 80% is expected.

 

Preliminary testing

I’ve implemented a stemmer.c program under the examples directory that can read words separated by blank spaces from a text file and stem them. This is the sample input :

വിവിധതരം വധശിക്ഷകളിൽ ഒന്നാണ് കുരിശിലേറ്റിയുള്ള വധശിക്ഷ. ഈ ശിക്ഷാരീതിയിൽ പ്രതിയെ ഒരു മരക്കുരിശിൽ ആണിയടിച്ച് തളയ്ക്കുകയാണ് ചെയ്യുക വേദനാജനകമായ വധശിക്ഷ നടപ്പാക്കണം എന്ന ഉദ്ദേശത്തോടുകൂടി രൂപപ്പെടുത്തിയ പുരാതനമായ ഒരു ശിക്ഷാരീതിയാണിത് സെല്യൂസിഡ് സാമ്രാജ്യം കാർത്തേജ് റോമാ സാമ്രാജ്യം എന്നിവിടങ്ങളിൽ ക്രിസ്തുവിന് മുൻപ് നാലാം ശതകം മുതൽ ക്രിസ്തുവിനു ശേഷം നാലാം ശതകം വരെ കുരിശിലേറ്റൽ താരതമ്യേന കൂടിയ തോതിൽ നടപ്പാക്കപ്പെട്ടിരുന്നു യേശുക്രിസ്തുവിനെ കുരിശിലേറ്റി വധിച്ചുവെന്നാണ് ക്രൈസ്തവ വിശ്വാസം. ക്രിസ്തുവിനോടുള്ള ബഹുമാനത്താൽ കോൺസ്റ്റന്റൈൻ ചക്രവർത്തി എ.ഡി. 337-ൽ ഈ ശിക്ഷാരീതി നിർത്തലാക്കുകയുണ്ടായി ജപ്പാനിലും ഒരു ശിക്ഷാരീതിയായി ഇത് ഉപയോഗത്തിലുണ്ടായിരുന്നു മരണശേഷം മൃതശരീരങ്ങൾ മറ്റുള്ളവർക്കുള്ള ഒരു താക്കീത് എന്ന നിലയ്ക്ക് പ്രദർശിപ്പിക്കപ്പെട്ടിരുന്നു കാഴ്ചക്കാരെ ഹീനമായ കുറ്റങ്ങൾ ചെയ്യുന്നതിൽ നിന്നും തടയുക എന്ന ഉദ്ദേശത്തോടെയാണ് കുരിശിലേറ്റൽ സാധാരണഗതിയിൽ നടത്തിയിരുന്നത്

I’ve removed almost all the punctuation so that they won’t interfere with the stemming. I’ve taken 2 screen shots showing the results. The results are far from perfect, and that is certainly because I haven’t added that many stem rules to the database. Things should improve significantly in the next few days.

 

Stem results page 1
Stem results page 1
Stem results page 2
Stem results page 2

References

I’ve referred two papers for designing this stemmer. The first one, LALITHA uses a longest suffix stripping method and was of little use for varnam. The second one, STHREE, uses a similar algorithm to mine but confines the number of iterations to 3. However, both the papers did not contain any links to stem rules or programs that could be reused. Hence I’d be relying on the SILPA stemmer, the first stemmer in Malayalam, for the invaluable stem rules.

But I would be looking for a more exhaustive set of rules (hopefully) and will have to do quite some Malayalam reading. Apart from the Mathrubhoomi newspaper which will definitely be soaked in curry and tea by the time I could carry it away from the mess hall, Malayalam reading materials are actually hard to come by. But wait, I saw a few SFI magazines on the other guy’s room.  Gathi kettal puli pullum thinnum! :p

GSoC : Malayalam stemmer foundation

Another week, and I’m finally working on what I signed up to do – implement a malayalam stemmer. The algorithm itself is still a haze, and I will be sitting down and drawing flowcharts soon. Despite being harassed by university practical exams, I managed to squeeze in enough time to lay down a basic framework. Varnam now has the *potential* to stem.

Something wonderful happened during my last conversation with my mentor. The scheme file, which looked like an ordinary text file full of rules to convert manglish (a blend of Malayalam and English) into malayalam, turned out to be a ruby file. I’m telling you, this is a ruby program! Its actually called the scheme file. The titles “consonants” and “vowels” and the like are actually function calls. Ruby does not need paranthesis to call a function. Beautiful.

Yes, I learned a bit of ruby to add the functionality I needed. I added a few stem rules to the scheme file which gets added to an sqlite3 table when I compile the scheme file. I learned how to call c functions from ruby using FFI and also added a “–stem” option to the list of arguments accepted by varnamc.

varnamc --symbol ml --stem പരീക്ഷയാ

gives the following output:

പരീക്ഷയ്

Doesn’t make much sense, I know. But under the hoods, varnam checked if there is a stem rule for the ending “ാ” in the database and seeing that there is, substituted the ending of the supplied word with the ending specified in the stem rule (“്”). The above stemrule doesn’t serve any purpose, and will be conveniently removed after I draft the algorithm.

Now I have to write tests for all the functions I wrote. I wonder how much of the codebase I broke already.

It’s black and its listening!

I’ve been longing for this day (/night) for almost an year now! I’ve finally, finally, got some data from an electret mic and finally got it into a beaglebone black. If you really want to understand the depth of this achievement, please go through what I’ve been doing for the past few months:

 

http://electronics.stackexchange.com/questions/111458/reading-sound-with-beaglebone-black

http://electronics.stackexchange.com/questions/111969/understanding-a-circuit-diagram

http://electronics.stackexchange.com/questions/106204/connect-electret-mics-to-computer

http://electronics.stackexchange.com/questions/77160/microphone-time-delay-estimation

http://dsp.stackexchange.com/questions/11399/signal-processing-using-panda-board

http://dsp.stackexchange.com/questions/11561/sound-card-for-recording-audio

http://dsp.stackexchange.com/questions/11472/audio-interface-or-external-sound-card

 

That’s a lot of questions. And I got a lot of answers. Though I’m no where near completing the actual project, at least getting it started is a relief. I’ve tried making my own amplifier, tried an audioboard from hrc, tried another opamp IC for amplifier, and finally hit upon this :

Click to access hbmic.pdf

The previous amplifiers I made might have been working fine – I just might not have read the values properly. Anyways, its working now and that’s all I care about.

Ain't she a (black) beauty?
Ain’t she a (black) beauty?

 

Components : Everything that was in the previous link containing the circuit diagram. I did not have 10 uF capacitors so I used 22 uF instead.

Beaglebone black : The INR 4200 beast. This board is being sold out faster than it is being produced. Lucky we could order one!

The process is pretty straightforward now that it works. The beaglebone black has a set of analog pins that can read analog inputs. I connect the mic (which produces voltage variations in the range of 20mv) to a preamplifier (built using the circuit diagram in the link and 741 opamp) and the output of the preamp (in range of 1 v) is given to the analog input of the BBB. When the sound hits the electret mic, it produces a voltage that is proportional to the amplitude of the sound. This is the signal we then amplify and finally measure.

Is this enough to do some signal processing and thus continue the project? Now that requires more experimenting and is a matter for another post.

I made the mistake of not connecting the ground of beaglebone black to the ground rail in the breadboard and cursed many perfectly working amplifier circuit because it BBB did not read.

Now we have to read this value using beaglebone.

First, enable the input output pins :

echo cape-bone-iio > /sys/devices/bone_capemgr.*/slots
If that step went well, you should not see any messages.

Then I wrote a small python script to read the analog pin 1 continously :


import os
import time

while 1:
os.system("cat /sys/devices/ocp.2/helper.14/AIN1")
time.sleep(0.1)

Replace AIN1 with your analog pin (for eg: AIN2 or AIN3) and the value in time.sleep with your desira
ble delay between reads. Saved it as test.py and python test.py does the job.

BBB reading values. Only positive values can be read. I should have given a DC bias.
BBB reading values (look hard. They’re there). Only positive values can be read. I should have given a DC bias.

The beaglebone black can read only voltages till 1.8 volts on its analog pins. Also, it can only read DC. That is why there are a lot of 0s in my screenshot – that’s where the negative voltages should go. The solution is to give a DC bias to the analog signal. Say we give 1v bias. Then the readings would be around 1V and will go below 1v when a negative peak occurs.

GSoC : Unit tests, Merges and Travis

Its been two weeks since community bonding got over and I’ve been making slow but steady progress. A couple of new bugs has surfaced and I will be fixing them before moving on to my main task.

Also, varnam project has been moved to github owing to gitorious being too unstable/unreliable.

I walked (crawled would be more appropriate) into some new territory the past week :

1. Unit tests : Every software project need unit tests. Unit tests make sure that all the tiny little parts (units) of the software function the way they are supposed to function and that you did not accidentally break anything with your new commit. I had heard of them, but I never thought I’d have to do them in c. Varnam uses check for unit testing. I wrote a patch that checks for the validity of the suggestions file libvarnam receives and wrote a test case for it. I learned to do stat calls to a path, rather than using fopen() to check if the file exists. Being the beginner I am, I did break something because the test fails at 70%. Should look into it.

2. Merging : I finally understood what merging is in git, though a bit painfully. Somehow I couldn’t digest the fact that git could simply “merge” all the changes that I made and all the changes (possibly overlapping) that some one else made into something that works. The other guy could have completely removed the stuff I’ve been working on from his commit! I just found out that doing so results in conflicts, and git won’t merge the branches until the conflicts are resolved. Bloody mess. Thankfully, there are wonderful tools like meld that makes resolving conflicts a lot less painful. Besides, the conflicts I had was of a less “violent” nature. So there I go, making my very first (meaningful) merge and a pull request

3. Travis : Just when I thought that the day is done, Travis CI reported that the build failed. Travis? Travis is a continous integrations tool integrated into github. This means, every time I push into a repository, Travis builds (does cmake . , and make) the project after merging my pull request and then runs the test cases to see if anything is broken. And yes, I had broken quite a few things. My new patch completely fails a few assertions.

****************I called it a day and went to sleep*****************

I spent almost the entire day debugging and the tests continued to fail. Apparently some files that should have been generated are simply not there. I created a quick hack, and put together a new pull request. At least the tests are proceeding better now. Travis still fails. Perhaps my mentor can help me with that.

The pull request : https://github.com/varnamproject/libvarnam/pull/47

GSoC : Community bonding

The community bonding period of this year’s google summer of code is nearing an end. Its been a rather busy week, and I had to juggle time between exam preps and GsoC. I cannot say that I have made much progress. However, an IRC meeting with the mentor turned out to be very fruitful. It was about setting up the right development environment, and I did learn a lot!

1. ctags/etags : I was complaining how hard it is to find function definitions in the libvarnam codebase. There are a lot of header files. That’s when I heard about ctags. I had to install the ctags package from the ubuntu repositories, and configure it to catalogue the libvarnam folder. Then I got myself the sublime text editor and installed the plugin for ctags. Now all I have to do is press ctrl+t+t when I encounter a function call and sublime will open the the definition of that function in a separate tab! Productivity multiplied – ten fold!

Another convenient way (though not as convenient) would be to use grep -iR. The -iR argument makes grep list the files from which the pattern matches were found.

2. Nemiver : I have used the gnu debugger (gdb) in my lab before. The programs I wrote then were rather small and I could live without a debugger. But mentor says no. Nemiver is a rather neat front end to gdb and I don’t have to look up line numbers to insert break points anymore – I click on the line instead. Also, nemiver makes the print command in gdb quite obsolete. Nemiver shows the values of all the variables in the scope as a list.

3. Sample project : My first task. In order to get myself familiar with libvarnam and learn some debugging in the process, the mentor asked me to write a sample project. My sample program, found here, would convert all the string literals in a python program into their corresponding Malayalam equivalent. Simple and buggy. But I did learn how to make nemiver branch into the libvarnam API and do some transliteration.

Now that I’m getting a few days gap before the last exam, I must fix a bug or two. I hope I’ll be able to start working on the stemming algorithm starting May 20th.

Google Summer of Code!

I’m excited to announce that I’ve been selected to this year’s google summer of code. My mentoring organization is SMC – Swathantra Malayalam Computing and I will be working on the varnam project.

Varnam means ‘colors’. Varnam is a transliterator for indic languages. My task is to improve the learning capability of varnam by coming up with a stemmer algorithm for indic languages. A stemmer algorithm returns a base word when it is supplied a complex word. In english, supplying ‘retirement’ to the porter stemmer algorithm will trim it down to ‘retire’ and subsequently return ‘retir’. I have to do the same thing with malayalam words. The trick is to design the whole thing in such a way that stemming support for other languages can be easily added. The stemming rules will differ from language to language. Though I will be laying down the rules for malayalam, I should provide room for someone else if she decides to add support for another language. In short, my algorithm should be designed to read a ‘rule file’.

The varnam project can be found here. Why use varnam when you have, say, google input tools? For one, google input tools work only in windows. Two, I’m not sure if you can use it in your own programs. I guess not. Three, it is not open source which means google won’t let you take a peek inside. Four, varnam can render the whole linux shell in malayalam if need be (and if you are willing to put in the effort)! To be frank, seeing small round malayalam alphabets on my desktop konsole was quite unexpected!

I’m so grateful to SMC for letting me work on this and even more grateful to google for the upcoming paycheck ;). SMC requires us to keep the blog updated on a weekly basis, so I guess everyone will be hearing an awful lot from me 😀

Getting machines to listen

I’ve been wanting to do this sound localization project for almost an year now. Its simple – have a few microphones ready, yell at it, and display the direction of sound on a screen. And being the electronics newbie I am, I had spent a considerable amount of time wondering how to connect an electret mic to my board/computer.

However, the last few days have been extremely productive and now I understand what exactly goes on when you yell at your laptop mic.

The Task : Record something using the built in mics (or any mic), store it in RAW format, access it using a python program. Understand sound.

The tool : Ladies and Gentlemen, meet ALSA – Advanced Linux Sound Architecture
Another tool : pyaudioalsa. Helps us do the necessary stuff without resorting to the C API.

You already have ALSA if you are using any of the major Gnu/linux distributions. First get pyalsaaudio and install it on your computer.

The pyalsaaudio page have some nice examples as to how to record sound. Go through it. By default, your recordings are in RAW PCM format. PCM stands for pulse code modulation. The output of your recording is actually a set of values that denote the amplitude of the input sound at various points in time. Just go through and try running the examples that come with pyaudioalsa source – record.py and playback.py.

Your recording is saved as a PCM RAW file. Try opening it in a text editor and you will see junk values.

But where are the amplitude values?

Exactly. Before that, we will try playing it back. Of course you can do it using the example program playback.py. But there’s another way. Try this on the terminal :

aplay -r 44100 -f S16_LE -c 1

That command will make ALSA play back the recording for you. 44100 is the sampling rate of the recording. How did we know that? Look inside record.py and you will see that the recording was sampled at 44.1KHz. S16_LE denotes that there are 16 bits per sample in our recording stored in little endian format? Now how did we know that?. Again, check record.py. The ‘-c 1’ tells ALSA that our recording is mono.

So that’s how you playback raw PCM files.

But what if you want to do some signal processing? What if you want to draw one of those spectrums or waveforms and other seemingly complicated stuff? Then you will need to extract the data from the RAW PCM. It sounds complicated, I know. Have no fear, python (and numpy) is here:

import numpy
data = numpy.memmap("test.pcm", dtype='h', mode='r')
print "VALUES:",data

Finally, something human readable!
Why don’t we draw a graph?
import numpy, pylab
data = numpy.memmap("test.pcm", dtype='h', mode='r')
print data
pylab.plot(data)
pylab.show()

Note : I’m very grateful to this guy for showing me how to do this.

So what do we have here? We have successfully made use of the RAW PCM data. So? There are many algorithms in Scipy and numpy that can do amazing things with that data – cross correlation,fft,convolution. Thank God (and Guido Van Rossum) for python!

Coloring the canvas – the processing way

I thought it was time somebody started painting on the canvas. Its been a couple of months since I wrote this program and it was lying in a corner of my hard disk all along. Realized kevinkoder.tk is pretty low on contents and decided to add it to the site.

http://www.kevinkoder.tk/paint7.htm

And the source code can be viewed by pressing ctrl+u (in chrome). But I must warn you though – I’ve put absolutely zero effort into making the code readable. I’m pretty sure even I can’t make sense of it right now. I was in a hurry to do something with processing and thought “Hey, lets make a paint program”. The development came to an abrupt stand still when i tried to implement the ‘fill bucket’ tool using the flood fill algorithm – the damn thing simply refused to work the way I wanted it to.

Anyways, the program proves beyond all doubt that a lot of amazing things are simply doable with processing.

And I had to choose not to include a lot of additional libraries that might have made it a lot easier to develop the program (like a java library that can add additional drawing layers) because 3rd party processing java libraries are incompatible with processing.js , ie, they wont work when you convert the processing code into javascript.

A few handy ‘features’ were added to compensate for the ultimate pathetic-ness of the program. More info can be found in the documentation.

And the documentation : http://www.kevinkoder.tk/paint_doc.htm

.

Fading menu

Remember me ranting about that free domain name? Well I’ve put it to some good use. Here’s the link to my very first sketch to be hosted on the world wide web :

http://www.kevinkoder.tk/test.htm

Just a few sentences thrown all over the canvas and playing hide and seek in the snow. Nothing much really.  Oh, and here’s the link to the source :

http://www.kevinkoder.tk/data_menu/fading_menu.pde

If you have a slow connection please wait a bit. The music is around 250 kb. Also, text looks a bit drab because I couldn’t get the fonts to work properly with processing.js

And the link to processing tutorial is inside the canvas. Happy hunting 😉

Into the web

I’ve always thought that developing for the web was easy and boring – thanks to my computer teacher who taught me html in 8th grade. However, I used to feel a sense of accomplishment when I saw my marquee going across my web page – and change direction when it hits the edge. And soon enough i came to understand that real programming was a world apart from creating simple web pages in html. And I began to look down on web development as something that is less ‘glorious’ than developing desktop applications.

6 years later, I’m the only programmer in the house who can’t put together a (decent)web site.

I tried learning the Django web framework, all the while hoping that Django is that magical thing that will allow me to write games for the web. It wasn’t, or at least I didn’t have enough enthusiasm to get to the part where Django might turn a little interesting. And I even tried to put together some web pages with some javascript and they looked terrible – and my accounts at various free web hosts started expiring because I never log in. And I really wanted to build one of those cool websites with all those mouse-over effects. That’s when I heard about CSS. Then I hardened up and made up my mind that scripting was not what ‘real’ programmers would be doing and that creating web pages and associated programming was so simple that I shouldn’t be focusing on that – unless I wanted to be a part of the common rabble. This is the single most programming-oriented nasty mindset I’ve ever had till date.

Trying to amend my path, and right my wrongs, I again attempt to climb the web-development mountain. This time I have a rather amusing friend to take along with me – html5. Until recently I thought html5 was the good old html with some extra tags. But boy, the <canvas> tag changed all that. The <canvas> tag in html5 basically lets you draw 2d graphics on to the web page using a scripting language such as javascript. And no, I didn’t know any javascript. But in a fortunate coincidence, I stumbled upon (nothing to do with the stumbleupon site though) a java script library for the processing API around java. what? Let me elaborate :

Back when I was still a school boy my dad’s friend introduced me to this wonderful API called processing. Its built on java and it lets you create colorful graphical applications in no time. Compared to the drab console programming (c++) I was learning at school, processing was a very welcome distraction. I was hooked. It was simple, fast, and so much fun that I soon created the classic pong game in processing. Then the wretched entrance exams got in between and I let processing fade away into some teeny tiny corner of my memory.

processing homepage

Here are some examples : http://www.openprocessing.org/

 

And when I found the javascript library for processing, I had hit my jackpot. Because the library, called processing.js, converts all my processing code into javascipt. That means I can write my pong game in processing (which is really java) and then convert it into javascipt using the processing.js library, and then display it in the canvas.

http://processingjs.org/

Now this is a big deal because implementing your applet as javascipt in the canvas does away with the java plugin and the awful loading time. Also, you can write great programs in no time with the processing API and better yet, you can show it off in a WEBSITE!!!!!So I guess practically that makes me a web developer as well! Watch out watch out here I come 😉 . Until next time.