CORSIS

Here is a cleaned-up performance test for several different implementations of levenshtein I have blogged about recently. This test was emailed to me by Ahmed Ghoneim, who has also kindly agreed to its publication on my blog. I am very grateful to him for his excellent contribution. I have slightly altered his file to do away with the unnecessary local variables in my C2C# port of the GNULevenshtein method. I would like to hear from you which methods perform best on your machine. Please drop a comment ^_^! LevenshteinAlgorithmPerformanceTest.cs code only Packages code, data and sample binary in zip and self-executable zip formats Please note that the GNULevenshtein method was found to be buggy! Here is the new replacement method .

While reading some interesting stuff about minimum edit distances in preparation for today's lecture ( ECL/ICL ), which is just about 45 minutes ahead in time as I'm writing this, I had the chance to test 5 different implementations of the Levenshtein minimum edit distance algorithm. Here is a screenshot first: I'll get into details later but let me announce the winner! And the winner is ... gLDp! gLDp is a funny display name for a levenshtein implementation from a C project. original implementation in C: levenshtein.c my C# port: libcorsis code C vs CIL vs C# Now I want to get mercilessly picky with my own port and today's C# compilers. The ternary conditional expressions in my port (lines: #516 , #524 , #533 ) are there to circumvent the following restriction: // valid C int x = 0; int y = 0; int z = 0; z += x == y; x, y and z are initialized 0 and in the final line z gets incremented by 1. This is valid code in C but causes a compile-time error in C#: C# does no...

A quick update on API refactorings! Here is a snapshot of what the code examined in the last post would look like with refactorings and improvements I have made so far: Before: the code examined in the last post After: For segmenting streams into, say, words for example, one could also use something like SED on GNU/Linux, some regular expressions implementation of a programming language or whatever. So why am I such an otaku ? Why not just go with the given the naive and easy way? Well, I am a performance and control freak and CIL is great fun and I feel 'pleasure' writing assembly code for a VM but most importantly, Benihime, 紅姫 makes the perfect training ground for learning language and compiler design. Prior to getting into deep hack mode on Benihime, 紅姫, I had no idea about the differences between 'expressions', 'statements', 'branches' or 'stacks'. Implementing complex boolean expressions in conditional statements like if((c && pm) ...

An interesting design concern has brought the development of my new segmenter compiler to a temporary standstill for tonight: parallelization . I was trying to refactor and improve the design of my new segmenter compiler Benihime, 紅姫. (It is named after Urahara's sword from the Japanese anime Bleach . Benihime means crimson princess , what is more suitable to call a state-of-the-art segmenter. ^o^ theheee~~) One of my major concerns with the new implementation was decoupling the flow control logic from the segmenter builder and the flow direction. This is essential for being able to reuse the same logic to compile two segmenters that run in opposite directions for example. Let me illustrate the problem with the help of a file I happened to submit as a practice for our introduction to computational linguistics course just 5 days ago: // /home/sert/Projects/hw1/hw1/Main.cs created with MonoDevelop // // project created on 10/21/2007 at 3:19 AM using System; using System.IO; using...

I am busy with my studies and cannot spend much time on development for the time being. All little what I do is test some ideas and the design of the class library. One of the tests I conducted was to see how much of a performance gain my single-file frequency listing routines might achieve on multi-core processors with multi-threading. So I decided to write some methods that help split a 140MB file into segments which can be processed on individual threads and added together once all threads return. You can see the code here . Below is the result: creating a frequency list for a 140~MB-large file utilizing four threads on a quad-core machine can be 83% faster than single-threading the same operation: You should expect to see this discovery taken into account in the next release. Another major change I'm planning for the next release is making the Segmenter, Clusterer and FrequencyList classes generic so that ' print ' as verb can be analyzed as a separate entity from ...

I've been trying to integrate reflection emit into Tenka Text recently and that's how far I have come in code: Builder.cs . You can use reflection emit to compile and build types at runtime. A pretty amazing way of using this technology is having an abstract class whose implementation you provide at runtime. Tenka Text is going to use reflection emit to provide custom segmentation. Using reflection emit instead of going for a simpler approach has numerous distinguishing advantages. I quote my friend Mike Scott from the documentation of his WordSmith Tools 4 here: [...] you may wish to allow certain additional characters within a word. For example, in English, the apostrophe in father's is best included as a valid character as it will allow processing to deal with the whole word instead of cutting it off short. (If you change language to French you might not want apostrophes to be counted as acceptable mid-word characters.) Examples: ' (only apostrophes allowed in the mi...

A new pre-alpha binary release is now available for download ! It features the performance of the new frequency list classes and a new statistics view in its WordLister tool. Go download the demo version of the commercially available WordSmith Tools 4 and compare to realize the power of open-source C#!

TT5 -> TT8 performance difference I conducted a performance test on one of the remotely accesible computers of the University of Heidelberg. (2 physical/4 logical cpus and 2 GB Ram) The test was performed by creating a frequency list based on the helsinki corpus (9.793 KB, single text file) and then sorting it. As you can see below, my optimization efforts seem to have paid off well. WordSmith Tools 4.0.0.374 took about 13 seconds to create and sort a word list into: Alphabetical order Frequency order Alphabetical order between types with the same frequency value TT5 (svn revision 17, binary release: 2006-11-25) required 2,51 seconds to create and 10,07 seconds to sort the list into: Alphabetical order Frequency order TT8 (svn revision 66) needed 1,10~ seconds to create and 2,40~ seconds to sort the list into: Alphabetical order Frequency order Alphabetical order between types with the same frequency value * Performance Comparison Table WS4 0.0.374 TT5 SVN17 TT8 SVN62 TT8.1 S...

To do a quick test on performance improvement, I redid some parts of my counter and switched to the new high performance hashset collection from the Orcas January CTP. I used the helsinki corpus (9.793 KB, single text file) and conducted a single-word frequency list operation (create and sort). And here are the results: TT5 SVN17 TT7 SVN47 Performance Improvement Create 2,17 1,84 1,17x Sort 12,42 2,28 5,44x Display 0,80~ 0,80~ - Total 15,39~ 4,92~ 3,12x For your information, WordSmith Tools 4 (4.0.0.374) takes about 23 seconds to perform the same operation.

I tested performances of several set implementations. A set is an unordered collection of unique elements. Time required to create a set of unique words with different implementations (Corpus Size: 278,675 tokens of 21,828 types): a cheap set implementation which derives from the BCL generic list collection and imposes Contains(T item) checks on each add / insert operation [ SVN ] 21,20~ seconds a set implementation which is a reflected / disassembled partial copy of the BCL generic list collection and performs manually inlined Contains checks on each add / insert operation 20,70~ seconds System.Collections.Specialized.StringCollection : if (!set.Contains(word)) set.Add(word); 18.96~ seconds HashSet from Orcas October CTP 0,17~ seconds ^_^ just who can beat this? I immediately decided to switch to the new generic HashSet from the BCL guys. Tenka.Text will greatly benefit from this development especially when sorting word-frequency dictionaries* on their frequencies. (* Your ...