Old English NLP

I started working through the SharpNLP library as referenced in my last blog post. To recap, the SharpNLP library depends on some source binaries from the SharpEntropy library which depend on sonce data files that have to be placed in a specific location on your file system.

I cracked open the SharpNLP with reflector and took a spin through the more commonly used methods. It looks like you deal with strings and a couple of classes called “chunk” and “word” that have a couple of supporting enumerations.

With the library, you can split paragraphs into sentences, sentences into words, sentences into phrases (what they call chunks), and then identify each word and/or phrase with its part of speech. These functions seem perfect for my Old English translator.

Here is an example of a basic console application with the parser output.

    public class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("--Start--");
            string testSentence = "A quick brown dog jumped over a lazy cat.";
            Parse parse = ParseSentence(testSentence);
            PrintParse(parse);
            Console.WriteLine("---End---");
            Console.ReadLine();
        }
 
 
        private static Parse ParseSentence(string sentence)
        {
            string path = @"C:\ProgramData\OpenNLP\Models\\";
            EnglishTreebankParser parser = new EnglishTreebankParser(path, true, false);
            return parser.DoParse(sentence);
        }
 
        private static void PrintParse(Parse parse)
        {
            Parse rootNode = parse.GetChildren()[0];
            Parse[] parses = rootNode.GetChildren();
            foreach (Parse currentParse in parses)
            {
                Console.WriteLine(String.Format("{0} : {1}", currentParse.ToString(), currentParse.Type));
            }
        }
    }

I then wanted to change the order from S-V-O to S-O-V or O-S-V. In this example, the output should be “A quick brown dog over a lazy cat jumped.” or even “Over a lazy cat a quick brown dog jumped.”

Looking at the output, the VP needs to be broken down even further. I changed the PrintParse to handle the children (using recursion):

        private static void PrintParse(Parse parse)
        {
            Parse[] parses = parse.GetChildren();
            foreach (Parse currentParse in parses)
            {
                Console.WriteLine(String.Format("{0} : {1}", currentParse.ToString(), currentParse.Type));
                PrintParse(currentParse);
            }
        }

The output is now:

Things looks better – except I can’t figure out what the “TK” is – it is duplicating each word and it is not a part of speech (at least according to the WordType enum)…

Removing the TK, I get this (I dropped the Console window and went to the Output window) :

A quick brown dog jumped over a lazy cat . : S

A quick brown dog : NP

A : DT

quick : JJ

brown : JJ

dog : NN

jumped over a lazy cat : VP

jumped : VBD

over a lazy cat : PP

over : IN

a lazy cat : NP

a : DT

lazy : JJ

cat : NN

. : .

So to take a sentence and take it from S-V-O to O-S-V, I need to map the parsing word types to either a S,V,or O. In this example:

• NP = S
• VBD = V
• PP=O

I can then rearrange the words into Old English. The challenge is that the word types are not context-free – the 1^st NP that is in the sentence (“A quick brown dog”)is the Subject, but the second NP (“a lazy cat”) is the object – the PP is for the prepositional phrase. So the 1^st NP that is encountered is the subject and the second NP is ignored if it is in a PP, but if it is alone (“A quick brown dog jumped a lazy cat”), then it becomes the object. I can build a table with the different patterns – at least the common ones, and leave it at that. Here is an example of the function (yes, I know this is procedural code at its worst, I’ll refactor once I have all of my thoughts down)

        private static void AssignOldEnglishOrder(List<Phrase> phrases)
        {
            int nounCount = 0;
            int verbCount = 0;
            int objectCount = 0;
 
            foreach (Phrase phrase in phrases)
            {
                switch (phrase.ParseType)
                {
                    case "NP":
                        if (nounCount == 0)
                        {
                            phrase.SentenceSection = "S";
                        }
                        else if (nounCount == 1)
                        {
                            phrase.SentenceSection = "O";
                        }
                        else
                        {
                            phrase.SentenceSection = "Z";
                        }
                        nounCount++;
                        break;
                    case "VBD":
                        if (verbCount == 0)
                        {
                            phrase.SentenceSection = "V";
                        }
                        else
                        {
                            phrase.SentenceSection = "Z";
                        }
                        verbCount++;
                        break;
                    case "PP":
                        if (objectCount == 0)
                        {
                            phrase.SentenceSection = "O";
                        }
                        else
                        {
                            phrase.SentenceSection = "Z";
                        }
                        objectCount++;
                        break;
                    default:
                        break;
                }
            }
        }

I then whipped up a function that spits out the phrase in Old-English:

        private static void PrintPhrases(List<Phrase> phrases)
        {
            StringBuilder stringBuilder = new StringBuilder();
 
            foreach (Phrase phrase in phrases)
            {
                switch (phrase.SentenceSection)
                {
                    case "O":
                        stringBuilder.Insert(0, phrase.Text);
                        break;
                    case "S":
                        if (stringBuilder.Length > 1)
                            stringBuilder.Insert(1, phrase.Text);   
                        else
                            stringBuilder.Append(phrase.Text);
                        break;
                    case "V":
                        stringBuilder.Append(phrase.Text);
                        break;
                    case "Z":
                        break;
                    default:
                        stringBuilder.Append(phrase.Text);
                        break;
                }
 
            }
            Debug.WriteLine(stringBuilder.ToString());
        }

And the output looks like this:

over a lazy catA quick brown dogjumped

My next steps are:

• Spacing between words
• Sentences formatted correctly (all lower case until final output)
• Find..Replace key words for Old English
• More patterns to match O-S-V from a variety of input sentences
• Handle the apostrophe (Don’t comes down as [Don] ‘[t] from the parser)
• Refactor using Unit tests to better patterns (strategy seems appropriate here)
• Stick into a WCF service
• Probably a bunch more stuff that I haven’t thought of

That’s it. I’ll pick it up more later.

Natural Language Parsing

I wanted to go back to a project that I started working on <gulp> three years ago. There is a great website called the Efanchiser that translates English into Jive/VallyGirl/Sweedish Chef. There are some knock-off sites like this one, but I prefer the original. When you go through the header file (written in C) of the translation methods (not the page’s html), you can see this comment:

/* chef.x - convert English on stdin to Mock Swedish on stdout
 *
 * The WC definition matches any word character, and the NW definition matches
 * any non-word character.  Two start conditions are maintained: INW (in word)
 * and NIW (not in word).  The first rule passes TeX commands without change.
 *
 * HISTORY
 *
 * Apr 26, 1993; John Hagerman: Added ! and ? to the Bork Bork Bork rule.
 *
 * Apr 15, 1992; John Hagerman: Created.
 */

Some guy at AT&T back in the 80s came up with the code – check out this comment for the language parsing. Looks like Google and Microsoft weren’t the 1^st to come up with the idea about parsing English speech 😉

/*    Copyright (c) 1989 AT&T    */
/*      All Rights Reserved      */

/*    THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T    */
/*    The copyright notice above does not evidence any       */
/*    actual or intended publication of such source code.    */

The actual .c file has the logic like this:

# line 28 "chef.l"
    { BEGIN NIW; i_seen = 0;
          printf("%c\nBork Bork Bork!",yytext[0]); }
break;
case 4:

# line 31 "chef.l"
ECHO;
break;
case 5:

# line 32 "chef.l"
ECHO;
break;
case 6:

# line 34 "chef.l"
    { BEGIN INW; printf("un"); }
break;
case 7:

# line 35 "chef.l"
    { BEGIN INW; printf("Un"); }
break;
case 8:

Basically, it is one big Select…Case statement with certain words/phrases replaced and throwing the words “Bork Bork Bork” at the end. The implementation uses word positioning like this:

0};
# define YYTYPE unsigned char
struct yywork { YYTYPE verify, advance; } yycrank[] = {
0,0,    0,0,    1,7,    0,0,    
0,0,    0,0,    0,0,    0,0,    
0,0,    0,0,    0,0,    1,8,    
9,34,    0,0,    0,0,    0,0,    
0,0,    0,0,    0,0,    0,0,    
15,39,    0,0,    0,0,    0,0,    
0,0,    0,0,    0,0,    0,0,    
0,0,    15,0,    0,0,    39,0,    
0,0,    1,7,    1,9,    0,0,    
0,0,    0,0,    0,0,    0,0,    
1,10,    0,0,    0,0,    0,0,    
0,0,    0,0,    3,7,    0,0

Which is pretty cool but really hard to duplicate or extend.

I wanted to add an old-english translator. Instead of adding to the C++ project, I thought of creating a WCF Service that creates an Old-English translation using C#.

My first step was to find a natural language parser that can break the input sentence into its words and tag each word as a part of speech. A quick bing search found a couple of options:

· This site has what I am looking for – but he does not expose the tokenizing as a web service or provide the API source code. I really am not interested in parsing the html so I moved on.

· The Sharp Natural Language Parser (SNLP) found on the codeplex seems to fit the bill – but it is complex to implement and it is a very brittle solution – it relies on a third party library called Maximum Entropy Models (MEM) that has to have a certain folder structure created. The SNLP has a database alternative (called Wordnet Lexical Database) but that link is not working.

· This site has what I am looking for – but he wants to charge a fee to use it. No thanks.

· There is another codeplex project that uses Pyton called ConceptNetUtils found here. I really don’t want to learn Python for this.

There are more hits, but the quality of the sites gets worse and worse.

Biting the bullet, I decided to use the SNLP project from codeplex and therefore use the MEM on my local file system. A great example is found here. Perhaps as a follow up project I will abstract the MEM from the file system. I did have to peek at the MEM to see if it would be an easy port – here is one of the files in notepad:

Bummer – looks like that project will be harder said than done….

So I added the directories to my source folder and hit F5 – sure enough it worked. I then started to dive into the examples and see how the API was structured. That is the subject of my next post.

To get an idea of how to make an English phrase an old English phrase, I turned to Bing. There are a couple of sites that translate individual words (like this one). I also got a laugh because there are TONS of sites that willtranslate Shakespeare to modern English – doubtlessly helping High School English students everywhere.

There are a couple of components:

· Rearrange the sentence structure as recommended here

· Find..replace certain words/phrases as found here

There are obviously other things I could do to make the Old English better, but I thought I would start with the basics.