What I cannot create, I do not understand

This excellent blog post draws parallels between Feynman's observations regarding the Challenger disaster and current trends in Software Engineering. Makes for a rather interesting read and is worth checking out. In particular, I appreciated the bit about unit testing and 'step by step' increases -- things I believe good programmers should constantly strive for in single-author programs... but which may become increasingly difficult/expensive in larger endeavors.

(via Slashdot)

Another Quality Microsoft Product(tm)

IEEE Spectrum has a lengthy profile of the tiny, 11-man division of mighty Microsoft developing a toolkit for robot designers. The blatantly uncritical article glowingly portrays the team as an underdog guaranteed to succeed. I’m shocked that there are still tech-savvy people out there who believe Microsoft to be capable of producing quality products.

Will the machines controlled by MS Robotic Studio crash with Blue Screens or Red Rings?

via AAAI.org News

SourceForge.net Site Maintenance

I just completed a good scrub updating the SourceForge.net project websites for JWords and AutoSummary. I removed most of the unused features, uploaded & organized documentation, and configured the SF.net web hosting service. No new file releases are available (or pending), but the SourceForge.net page and documentation should make JWords & AutoSummary much more accessible and easier to use.

Javadoc source code documentation was uploaded onto SourceForge for both of the projects. Additionally, I created step-by-step instructions for getting each program up and running, which should be easy to follow for even the non-programmer. And finally, I posted more extensive project descriptions to the respective documentation pages.

The updated SourceForge.net project websites can be viewed at:
JWords Java Interface for WordNet
AutoSummary Semantic Analysis Engine

My SourceForge.net developer profile can be found at:
http://sourceforge.net/users/greenbacker/

Frustrating Recursion

I thought I made a mistake once, but I was wrong. For some reason, this happens to me all the time when programming.

I was working on AutoSummary this weekend, adding a contextual framework using hypernym (superordinate) information for individual senses of a given word. In order to do this I needed to create a b-tree data structure. I thought I had set everything up properly, except the tree wouldn't populate past the second level. Weird crashes, etc. I tried everything, checked all of the functions and methods, testing everything I could think of. Nothing.

Tonight, I started checking everything over again, trying some different approaches. I did some digging and determined something was generating a null pointer exception. I checked everything all over again, and again... nothing. After a period of insufferable aggrivation, I discovered by trial and error that the exception was caused by the fact that I had forgotten to initialize the data container (an ArrayList). I was so worried about getting all the "hard stuff" figured out that I had overlooked a beginner's error.

The moral of the story? The simplest answers are often the hardest to find.

Moving Forward

Last night I did some work on the Answer Machine, and today I'm working on adding topic detection to AutoSummary.

Check out the entry in the Answer Machine project log for details about its new functionality. As for AutoSummary, I came up with a good idea about how to implement topic detection within the current framework of the program. I was checking out this post at the Search Science blog that I read, and thought "I can do that."

What I plan on doing is after determining the likely sense of a given word, I'll build a list of all of the possible topics that word is connected to (using the WordNet domain function). From that I'll be able to find the topic of a sentence by taking the best intersection of all the anchor words (not "the" or "and" etc).

You can probably see how it will scale from there, building intersections of sentences into paragraphs, and paragraphs into entire texts. So very shortly I just might be able to take an fully body of text and determine just what the heck it is all about. Could be an interesting step forward in search relevance and data mining...

PHP: Longest Common Substring

While working on my answer machine program, I came across a need to find recurring patterns in strings. What I wanted to do was take two strings and return the longest substring contained by both. After about 30 minutes worth of searching Google for a quick solution, I realized that this was not a trivial problem. It seems that finding the longest common substring is a classical problem in computer science. Helpful examples of LCS algorithms were very hard to come by, and there was virtually nothing available for PHP. Maybe when I earn a PhD I will try to impress people with useless formulas and diagrams, but for now I figured I would just write some realtively straightforward code that gets the job done.

The solution that seemed the simplest to me was to compare the strings character by character looking for matches that would signify the possible beginning of a common substring. I really don't consider one character substrings to be significant, so my solution only initiates a match when it finds two identical substrings two characters in length. It continues down each string char-by-char as long they match, and then tosses the completed substring into an array. Every common substring is obtained this way, and then we simply return the longest of these as the result. If more than one common substring is longest, the one that appears first in the first source string is returned.

See it in action and view the source.

After all that, I'm starting to think it might be more appropriate for my application to tokenize the strings and then capture the longest common sequence of tokens. In other words, break the string down into words and return the longest common phrase. It won't be that much more difficult to implement both methods in my answer machine, and compare their performance to see which one is better.

Have you ever seen the sun rise ... twice in a row ... three times...?

Paul Graham recently had a very interesting article about what businesses can learn from open source.

The entire piece was very well written, and the author makes a lot of good points, but what captured my imagination the most was the part about the optimal working environment for a programmer. Paul says that people working in the comfortable surroundings of their own home are often exponentially more productive than corporate rats in a stuffy cubicle farm. Based on my own personal experience, I would certainly agree. I find I do my best work in marathon sessions, often involving massive amounts of caffeine and highly irregular sleep patterns. I understand many programmers share similar experiences. Once I get 'in the zone,' as they say, I will work solidly for hours on end paying little attention to time or the world around me. Were I restricted to a structured work environment constantly struggling against interruptions and distractions like co-workers, meetings and email, I fear my programming would suffer.

I am currently working hard to finish up the next release of JWords, as well as the initial release of another semantic analysis tool. I've been trying to complete this stuff for weeks now, but I find the only way I can get anything done is if I rush straight home from work and devote the entire evening to programming. If I decide to go workout, play basketball, see a movie or go out to dinner, and try to pick up where I left off and program a little bit at a time, I never get anything done. By the time I sit down and get going, its time to sign off for the night. My old friend the all-nighter is no longer an option with my responsibilities at work. Usually weekends offer a real chance to get down to business, but I'm afraid my willpower is just barely too weak to resist the temptation of living it up at the beach. But on those rare occasions when I can devote a significant amount of time to this endeavor, and everything is firing on all cylinders, nothing else compares.

Translating and Sorting 2D Arrays for Fun

Just a quick project update. Yesterday, I succeeded in making my probability algorithm much more efficient, vastly reducing the number of wasteful steps and minimizing the memory footprint. Then, tonight, I straightened out the sorting functionality for the results using Arrays.sort(Object[] a, Comparator c). Next up, I want to write something that will generate a 'confidence level' number to accompany the results. After that, I will clean up all the code and put it in a presentable format for you all to see... I swear!

Java: Extracting All Possible Combinations from 2D Arrays of Varying Size

Recently I was having a hell of a time trying to get a snippet of code to work. Generally speaking, it really shouldn't have been that difficult to do, but I just couldn't figure out how to straighten everything out. When faced with this sort of situation, a quick web search will often bring you to the answer, but that was not the case this time. I did eventually get the whole thing working, and offer the solution here in the hopes that no one else will have to waste as much time on this as I did!

I needed to take a 2D array of integers and create another 2D array containing every possible combination of elements from each row in the original array. Sounds simple enough, but I had to allow for varying numbers of both rows and columns in the starting array. That is, I had no idea beforehand how many rows I would get, or more importantly, how many elements would be in each row. Each row could have a different number of elements. So I could have something as simple as:

0 1
0 2

to something as complex as:

1 2 3
1 2
0
0 1 2 3
0 3
0 1 2 3
0 2 3
1 3
1

I would have to take any sort of 2D array like those and construct another 2D array with every possible combination taking one element from each row in the first array. So the first array above would yield:

0 0
1 0
0 2
1 2

and the second would start like this:

1 1 0 0 0 0 0 1 1
2 1 0 0 0 0 0 1 1
3 1 0 0 0 0 0 1 1
1 2 0 0 0 0 0 1 1
2 2 0 0 0 0 0 1 1
3 2 0 0 0 0 0 1 1
1 1 0 1 0 0 0 1 1
2 1 0 1 0 0 0 1 1
3 1 0 1 0 0 0 1 1
and so on...

I could have gone the easy route and assumed each row in the original array was equal in length to the longest row, but that really wasn't correct for my application, plus it would result in many, many wasted steps. To make things more efficient, I needed to process only the possible combinations. So this is how I eventually got it all to work:

First thing I needed to do was calculate how many possible combinations would result.

int validCombos = 1;

for (int i=0; i < my2DArray.length; i++)
    validCombos *= my2DArray[i].length;

By multiplying the all of the lengths of each row together, we get the number of possible combination we can create. You need to start the validCombos counter at 1 instead of zero because we are multiplying, not adding (and don't want to remain at zero forever!).

Next we will construct our new 2D array to contain the results.

combosArray = new int[validCombos][my2DArray.length];

This gives us a final array with as many rows as there are possible combinations, with each row taking one element from each row in the original array.

Next we'll need a counter to keep track of which combination we're working on, and an offset value to track how we're changing the element in each combination.

int combo;
int offset = 1;

Now for the main part of the algorithm. Obviously, we will need to loop through each row in the first array, and make sure we start from the first combination for each iteration.

for (int i=0; i < my2DArray.length; i++) {
    combo = 0;

We need to make sure the 'pattern' we construct stays within the confines of the total number of possible combinations, so we add this line:

while (combo < validCombos) {

We also need to loop though each element in the first array.

for (int j=0; j < my2DArray[i].length; j++) {

And we will use the offset value to determine the rate of repetition of the 'pattern' for each element.

for (int k=0; k < offset; k++) {

We'll need to add this line to make doubly sure we don't grow beyond the maximum size of our resulting array:

if (combo < validCombos) {

And here we can finally start building our combination, one element at a time. Each row in combosArray represents one combination consisting of one value from each row in the original array.

combosArray[combo][i] = my2DArray[i][j];

We also need to increment our combo counter to ensure we fill out the entire array and not just each row over and over!

combo++;

Now we can add close brackets for all except the first for loop.

}
}
}
}

Finally, we need to adjust the offset value for the next element in the combination to ensure that every possible combination is created, and then we can close out the final for loop.

offset *= my2DArray[i].length;
}

And that's it. combosArray now contains rows representing every possible combination from the original 2D array. Print the contents and have a look if you like.

for (int i=0; i < combosArray.length; i++)
{
    System.out.print("[ ");
    for (int j=0; j < combosArray[i].length; j++)
        System.out.print(combosArray[i][j] + " ");
    System.out.println("]");
}

After all that I finally have something working exactly the way I need it to. Given a 2D array of varying row length, we have created another 2D array containing every possible combination taking one value from each original row, without wasting any memory space or unnecessary steps.

Now this might all be a little confusing, and not very useful unless you are working on something very similar to this, but hopefully if someone out there finds themselves in the jam I was in, they will be able make some use of it. The entire block of code is below:

int validCombos = 1;

for (int i=0; i < my2DArray.length; i++)
    validCombos *= my2DArray[i].length;

combosArray = new int[validCombos][my2DArray.length];

int combo;
int offset = 1;

for (int i=0; i < my2DArray.length; i++)
{
    combo = 0;
    while (combo < validCombos)
    {
        for (int j=0; j < my2DArray[i].length; j++)
        {
            for (int k=0; k < offset; k++)
            {
                if (combo < validCombos)
                {
                    combosArray[combo][i] = my2DArray[i][j];
                    combo++;
                }
            }
        }
    }
    offset *= my2DArray[i].length;
}

for (int i=0; i < combosArray.length; i++)
{
    System.out.print("[ ");
    for (int j=0; j < combosArray[i].length; j++)
        System.out.print(combosArray[i][j] + " ");
    System.out.println("]");
}

And just in case you are wondering, this code was used to increase the efficiency of the part-of-speech tagging tool I'm working on.

It Knows...

That's what I said to myself while working on my project tonight.

Work was really slow today, so I had some time to scrutinize the probability algorithm for my part-of-speech disambiguator. Basically, the tool I'm working on now is meant to correctly identify the part-of-speech for each word in a given phrase. When I got home and tinkered with the code a bit, I was astonished with how well it worked. The program is now analyzing all possible combinations, and reports the instance it determines is most likely to occur, based on general usage statistics.

When I realized it was doing what I hoped it would do, and the statistical formula was working properly, I was pleasantly surprised. Later on, I will combine this with other methods of semantic analysis in an attempt to determine the specifc meaning of each word in a sentence. But for now, I'm cleaning up the code a bit, and improving the performance by eliminating unnecessary steps. The algorithm is working... but its slow, with an efficiency on the order of O(4^n)! Once I speed it up and get it into a presentable format, I will make it available to download and try out.

Not exactly what you would call a 'Eureka!' moment, but I was pleased nonetheless.

JWords Alpha Release

I am pleased to announce that the first alpha testing version of the JWords Java Interface for WordNet has been released under the BSD License.

JWords is a simple and easy to use Java interface for the WordNet 2.0 command line tool. It provides classes and methods to create and use JWord objects containing the information stored in the WordNet lexical reference system.

I created JWords because I wasn't happy with any of the other Java APIs available for WordNet. I plan on using WordNet as the primary lexicon for autosummary software I am creating, and I needed to create a custom-tailored interface to suit my needs. By treating words as objects, and using the WordNet command line tool to handle the burden of reading the database files, JWords offers a simple and versatile way to access a wealth of lexical information.

JWords is available for download at SourceForge.net http://sourceforge.net/projects/jwords/

Javadoc documentation for JWords is available here.

I guess this makes me a pro?

Finally got a chance to write (well, edit actually) some code at work today. Besides some freelance web design I did a while back, this was the first time I was paid for programming.

In all reality, it really wasn't that big of a deal. Last week, I was asked to take a look at some PHP for a web interface to a pretty high-profile database we use. There was a bug somewhere that was generating incorrect entries. Today I got a chance to poke around in there, and I quickly isolated the problem and wrote a very elegant fix if I do say so myself.

I showed it to the database administrator, and she was visibly excited when she realized it was working properly. Now she won't have to go in and manually edit every single new entry.

I showed it to my supervisor, and he was pretty impressed. He doesn't have much experience in this area, but he had had another CS grad working on the problem for at least a couple of weeks, to no avail. When I showed him exactly how simple my solution was, he remarked that the other guy will be kicking himself when he sees it.

I honestly didn't think it was that I did anything special, but I certainly impressed a few people. What I did fixed an annoying problem in a pretty important system we use. Hopefully, this will lead to more oppurtunities for me to work directly on projects like this in the future.

And besides, it's pretty sweet to think that code I helped to write is running on a military system. :)