Graphing grammar parses from CMU Sphinx 4

CMU Sphinx comes with some neat grammar parsing stuff that I never knew about. It uses JSGF (as detailed here) and comes with several demos, showing how to use a basic grammar, arc weights, tags, and even getting a javascript representation of the final parse! At work I've been needing to do some custom processing of the grammar output, but it was more conceptually difficult than I'd planned. So after figuring out how to traverse a parse tree, I decided to write a little application to print out the parse of a given sentence. The eclipse project for it can be found here.

Given this small gramamar:

#JSGF V1.0;
grammar sidTests ;


public <greet> = <greeting> [<person>] [i am <person>];


<greeting> = konnichiwa {language:japanese} | hello {language:english} | guten tag {language:german};


<person> = john {gender:man} | martha {gender:female} | kelly;

If we parse the sentence "konnichiwa kelly i am john", the program outputs the following:



digraph {
"greet-2147483647" [label="greet" color=magenta];
"greet-2147483647" -> "(<sidTests.greeting> = konnichiwa {language:japanese}) ( (<sidTests.person> = kelly) ) ( i am (<sidTests.person> = john {gender:man}) )-2147483646";
"(<sidTests.greeting> = konnichiwa {language:japanese}) ( (<sidTests.person> = kelly) ) ( i am (<sidTests.person> = john {gender:man}) )-2147483646" [label="(<sidTests.greeting> = konnichiwa {language:japanese}) ( (<sidTests.person> = kelly) ) ( i am (<sidTests.person> = john {gender:man}) )" color=green];
"(<sidTests.greeting> = konnichiwa {language:japanese}) ( (<sidTests.person> = kelly) ) ( i am (<sidTests.person> = john {gender:man}) )-2147483646" -> "greeting-2147483645";
"greeting-2147483645" [label="greeting" color=magenta];
"greeting-2147483645" -> "konnichiwa {language:japanese}-2147483644";
"konnichiwa {language:japanese}-2147483644" [label="konnichiwa {language:japanese}" color=green];
"konnichiwa {language:japanese}-2147483644" -> "language:japanese-2147483643";
"language:japanese-2147483643" [label="{language:japanese}" color=red];
"language:japanese-2147483643" -> "konnichiwa-2147483642";
"konnichiwa-2147483642" [label="konnichiwa" color=cadetblue shape=box];
"(<sidTests.greeting> = konnichiwa {language:japanese}) ( (<sidTests.person> = kelly) ) ( i am (<sidTests.person> = john {gender:man}) )-2147483646" -> "(<sidTests.person> = kelly)-2147483641";
"(<sidTests.person> = kelly)-2147483641" [label="(<sidTests.person> = kelly)" color=green];
"(<sidTests.person> = kelly)-2147483641" -> "person-2147483640";
"person-2147483640" [label="person" color=magenta];
"person-2147483640" -> "kelly-2147483639";
"kelly-2147483639" [label="kelly" color=green];
"kelly-2147483639" -> "kelly-2147483638";
"kelly-2147483638" [label="kelly" color=cadetblue shape=box];
"(<sidTests.greeting> = konnichiwa {language:japanese}) ( (<sidTests.person> = kelly) ) ( i am (<sidTests.person> = john {gender:man}) )-2147483646" -> "i am (<sidTests.person> = john {gender:man})-2147483637";
"i am (<sidTests.person> = john {gender:man})-2147483637" [label="i am (<sidTests.person> = john {gender:man})" color=green];
"i am (<sidTests.person> = john {gender:man})-2147483637" -> "i-2147483636";
"i-2147483636" [label="i" color=cadetblue shape=box];
"i am (<sidTests.person> = john {gender:man})-2147483637" -> "am-2147483635";
"am-2147483635" [label="am" color=cadetblue shape=box];
"i am (<sidTests.person> = john {gender:man})-2147483637" -> "person-2147483634";
"person-2147483634" [label="person" color=magenta];
"person-2147483634" -> "john {gender:man}-2147483633";
"john {gender:man}-2147483633" [label="john {gender:man}" color=green];
"john {gender:man}-2147483633" -> "gender:man-2147483632";
"gender:man-2147483632" [label="{gender:man}" color=red];
"gender:man-2147483632" -> "john-2147483631";
"john-2147483631" [label="john" color=cadetblue shape=box];
}

which is all a big mess until we run it through GraphViz and see this:

A graph explaining how our sentence was parsed! I color code the parse: green is a RuleSequence, magenta is a RuleParse, light blue is a Token, red is a Tag, yellow (which there strangely aren't any of) is a RuleName.
I notice two very strange things here. First, RuleParses don't have anything as a direct child except for RuleSequences (RuleName is also possible but not shown). So RuleSequences will always be present and may only have one child. Second, text is treated as a sub-component of a tag instead of the other way around. So the text is tagging the tag? I don't know why they designed it that way, but at least now that I have a graph of the parse so I can figure out how to properly process it.

Getting WordNet Verb Frames with JAWS

I love using JAWS to access WordNet. It has a rather extensive API, runs quickly, and doesn't require too much configuration. All you have to do is download the Jaws binary jar and WordNet, and then specify to JAWS where the WordNet files are (I will demonstrate this later).
One thing that did take a while to figure out was how to get verb frames from it. A verb frame is an indication of how the verb may be used. For example, the entry for the verb "fax" in WordNet contains the following frames:

• Somebody ----s something to somebody
• Somebody ----s somebody something
• Somebody ----s somebody
• Somebody ----s something
• Somebody ----s

Let's look at the WordNet file to see how frames are specified. If you open data.verb, you will see that "sun" occurs twice. The frames are listed like so:

02112546 39 v 04 sun 0 insolate 0 solarize 0 solarise ... 01 + 08 00 | expose to the rays of the sun or affect by exposure to the sun


00104147 29 v 02 sun 0 sunbathe ... 03 + 02 00 + 22 00 + 09 01 | expose one's body to the sun 

The 01 and 03 indicate the number of verb frames, 08, 02, 22, and 09 are frame numbers. The 00's and 01 that follow the frame numbers indicate which words in the synset the numbers apply to. 00 means the frame is applicable to all members. The 01 in the second entry means that frame 9 is only for the word sun, and not for the second word, sunbathe.
There are two methods provided by JAWS to get frames. They are both contained in the VerbSynset class:

 /**
  * Returns the sentence frames (if any) associated with this verb meaning.
  * Sentence frames are examples of how the verb can be used / applied, and
  * all the frames returned by this method apply to all word forms in the
  * synset.
  * 
  * @return Sentence frames associated with all word forms in this synset.
  * @see    
  *         Format of Lexicographer Files ("Verb Frames")
  */
 public String[] getSentenceFrames();

 /**
  * Returns the sentence frames (if any) that are specific to a particular
  * word form within this synset, where sentence frames are examples of
  * how the word form can be used / applied.
  * 
  * @param  wordForm Word form for which to return sentence frames.
  * @return Sentence frames that are specific to the word form.
  * @see    
  *         Format of Lexicographer Files ("Verb Frames")
  */
 public String[] getSentenceFrames(String wordForm);

Keep in mind that the VerbSynset class is completely divorced from the actual orthographic representation of a word, since a synset may belong to several different words. The first method returns all of the frames that apply to every word in the synset, or to all of the frames marked with a 00 in the data.verb file as shown above. The second method returns only the frames which are marked as being specific to a single orthographic representation, specified by the one argument for the method. The return values are complementary and each is incomplete by itself. However, given only the synset offset or only the word to look up, JAWS is returning as much information as is possible. If you know both the synset number and the orthographic representation of a word you need frames for (and I don't see why you wouldn't), then the getWordFramesComplete method in the program below demonstrates how to get all of the available frames:

package edu.byu.xnlsoar.test;

import java.util.ArrayList;
import java.util.List;

import edu.smu.tspell.wordnet.Synset;
import edu.smu.tspell.wordnet.SynsetType;
import edu.smu.tspell.wordnet.VerbSynset;
import edu.smu.tspell.wordnet.WordNetDatabase;
import edu.smu.tspell.wordnet.impl.file.SampleFrameFactory;
import edu.smu.tspell.wordnet.impl.file.SynsetFactory;
import edu.smu.tspell.wordnet.impl.file.SynsetPointer;

public class DemoFrames {

 private static WordNetDatabase database;
 private static SynsetFactory synsetFactory;
 //initialize everything here
 static{
  System.setProperty("wordnet.database.dir", "./lib/3.0/dict");
  database = WordNetDatabase.getFileInstance();
  synsetFactory = SynsetFactory.getInstance();
 }
 
 /**
  * 
  * @param synsetOffset Synset number to look up frames for
  * @return Array of frames for the synset; only returns frames
  * which apply to every word in the synset
  * frames 
  */
 public static List<string> getGeneralSynsetFrames(int synsetOffset){
  SynsetPointer sp = new SynsetPointer(SynsetType.VERB, synsetOffset);
  VerbSynset vSynset = (VerbSynset) synsetFactory.getSynset(sp);
  List<string> frames = new ArrayList<string>(); 
  for(String s : vSynset.getSentenceFrames())
   frames.add(s);
  return frames;
 }

 /**
  * 
  * @param lemma Base form of the word you want to look up
  * @return Array of frames for the lemma; only returns those
  * that are specific to a particular word form within each synset.
  * frames 
  */
 public static List<string> getWordFramesSpecific(String lemma){
  List<string> frames = new ArrayList<string>();
  Synset[] synsets = database.getSynsets(lemma,SynsetType.VERB);
  for(Synset synset : synsets){
   for(String s : ((VerbSynset) synset).getSentenceFrames(lemma))
    frames.add(s);
  }
  return frames;
 }
 
 /**
  * This one is more difficult to understand...
  * @param lemma Base form of the word you want to look up
  * @return Array of frames for the lemma; only returns those
  * that match every word in each of the synsets that contain this word.
  */
 public static List<string> getWordFramesGeneral(String lemma){
  List<string> frames = new ArrayList<string>(); 
  Synset[] synsets = database.getSynsets(lemma,SynsetType.VERB);
  for(Synset synset : synsets){
   for(String s : ((VerbSynset) synset).getSentenceFrames())
    frames.add(s);
  }
  return frames;
 }

 /**
  * This method is the best. It returns all possible frames
  * given a synset number and the accompanying word.
  * @param lemma Base form of the word you want to look up
  * @param synsetOffset Synset number to look up frames for
  * @return Array of frames for the synset; returns all frames
  * for this word within this synset.
  * frames 
  */
 public static List<string> getWordFramesComplete(String lemma, int synsetOffset){
  SynsetPointer sp = new SynsetPointer(SynsetType.VERB, synsetOffset);
  VerbSynset vSynset = (VerbSynset) synsetFactory.getSynset(sp);
  List<string> frames = new ArrayList<string>(); 
  for(String s : vSynset.getSentenceFrames(lemma))
   frames.add(s);
  for(String s : vSynset.getSentenceFrames()) 
   frames.add(s);
  return frames;
 }
 
 /**
  * Prints out several different queries for the frames of "fax"
  */
 public static void main(String[] args) {
  int offset = 104147;//the synset meaning "expose one's body to the sun"
  System.out.println(getGeneralSynsetFrames(offset));//returns 2 frames
  System.out.println(getWordFramesSpecific("sun"));//returns 1 frame
  System.out.println(getWordFramesGeneral("sun"));//returns 3 frames
  System.out.println(getWordFramesComplete("sunbathe",offset));//returns 2 frames
  System.out.println(getWordFramesComplete("sun",offset));//returns 3 frames (different from before)
 }
}

getWordFramesComplete calls both of the available methods in JAWS, retrieving both frames that apply to all words in a synset and the frames that are specific to a single word in the synset.

Review: The Development of Language Processing Strategies: A Cross-linguistic Study Between Japanese and English

The Development of Language Processing Strategies: A Cross-linguistic Study Between Japanese and English by Reiko Mazuka
My rating: 4 of 5 stars

This is basically an updated version of Mazuka's PHD thesis. This book is a significant work on human sentence processing involving data from a head final and a head initial language.
Mazuka presents data on sentence processing experiments with English speaking adults and Japanese speaking children and adults. She shows that sentence processing strategies are the same in children and adults (though their ability differs with age), and that sentence processing strategies differ cross-linguistically. Her experimental data include probe latency tasks (PLTs) for lexical and semantic information in English and Japanese sentences.
A probe latency task involves a subject listening to a sentence and responding to questions about its contents. In lexical PLT, a subject is asked if the sentence contained the specified lexical item. In semantic PLT, the subject is asked if a sentence contained a portion which has a similar meaning to a specified word or phrase. The experimenter then carefully designs sentences which test the subjects' ability to process different types of sentences. Mazuka's experiment measure response time and also the accuracy of the subjects' responses. Her findings for cross-linguistic processing differences are as follows:
English speakers showed processing differences for main and subordinate clauses, while Japanese speakers did not.
English speakers showed different effects for semantic and lexical tasks, while Japanese speakers did not.
In English speakers, response time for semantic probe latency tasks involving sentence-initial subordinate clauses (an LB structure) was increased, while in Japanese speakers it was greatly decreased.
Japanese speaker response times to both lexical and semantic PLTs involving left-branching and coordinate structures were the same; English speakers showed much larger recency effects in LB than coordinate sentences.
Hypotheses about the human language processing mechanism which assume a single processing strategy do not account for these data. Japanese speakers process LB structures efficiently, and English speakers process RB structures efficiently. This is impossible in a parser which assumes only one processing strategy, and a parser which can efficiently process both would be too powerful to account for real human data. For Japanese speakers to process LB structures as efficiently as English speakers do RB structures, processing must be done bottom-up instead of top-down. Mazuka therefore hypothesizes that Universal Grammar (UG) contains a parameter which determines whether a language is right- or left-branching (RB or LB), and that this is linked with the processing strategy by specifying whether processing should be done top-down or bottom-up. She also hypothesizes that in English, main and subordinate clauses are processed to a different semantic level at some initial encoding stage, accounting differences in English main and subordinate clause PLT tasks. This needs to be further tested in the future with PLTs involving two clause sentences beginning with an explicit subordinator in Japanese.
She states that future research is required to determine the exact relationship between her experimental data and the operation of the human sentence parser as she has hypothesized.
Since some languages such as German, actually branch in different directions for different types of clauses, her hypothesis needs to be revised to account for this. I'm hoping that her hypotheses can be tested in detail in some sort of a cogntive modeling system.

View all my reviews

List of Japanese NLP tools

I haven't tried out all of these so I don't have comments for everything, but hopefully this list will come in useful for someone.

Morphological analyzers/tokenizers

Itadaki: a Japanese processing module for OpenOffice. I've done a tiny bit of work and issue documentation on a fork here, and someone forked that to work with a Japanese/German dictionary here.

GoSen: Uses sen as a base, and is part of Itadaki; a pure Java version of ChaSen. See my previous post on where to download it from.

MeCab: This page also contains a comparison of MeCab, ChaSen, JUMAN, and Kakasi.

ChaSen

JUMAN

Cabocha: Uses support vector machines for morphological and dependency structure analysis.

Gomoku

Igo

Kuromoji: Donated to Apache and used in Solr. Looks nice.

Corpora

Hypermedia Corpus

TüBa-J/S: Japanese treebank from universityu of Tübingen. Not as heavily annotated as I'd hoped. You have to send them an agreement to download it, but it's free.

GSK: Not free, but very cheap.

LDC: Expensive unless your institution is a member

Other lexical resources

Kakasi: Gives readings for kanji compounds.

WordNet: Stil under development by NiCT. The sense numbers are cross-indexed with those in the English WordNet, so it could be useful for translation. Also, there are no verb frames like there are in English.

LCS Database: From Okayama University

Framenet: Unfortunately you can only do online browsing.

Chakoshi: Online collocation search engine.

Itadaki GoSen and IPADIC 2.7

Update3: I've forked the Itadaki project on GitHub to keep track of it better.
Update2: I made an executable JAR for GoSen that runs the ReadingProcessorDemo. It requires Java 6; just unzip the contents of this zip file to your computer and click on the jar file.
Update1: The IPADIC dictionary is no longer available from its original location. It has been replaced by the NAIST dictionary. I have edited the following post to reflect the needed changes.

Itadaki is a software suite for processing Japanese in OpenOffice. GoSen, part of the Itadaki project, is a pure Java morphological analysis tool for Japanese, and I have found it extremely useful in my research. Unfortunately, the page for this project went down recently, making the tools harder to find. Itadaki is still available through Google code here, but I can't find a separate installment of GoSen. The old GoSen website can still be accessed through the way-back-machine here. The other problem is that GoSen hasn't been updated since 2007, and in it's current release cannot handle the latest release of IPADIC. I'll describe how to fix it in this post.
Why does it matter that we can't use the latest version of IPADIC? Well, here's an example. I am using GoSen in my thesis work right now, and I put in a sentence which included a negative, past tense verb, such as 行かなかった. It analyzed it as な being used for negation, and かった being the past tense of the verb かう. That is indeed a problem! Using the newer IPADIC fixed it for me, though. To do that, download this modified version of GoSen. The explanation for the fix is here. Basically, a change in the new IPADIC versions to work better with MeCab adds a bunch of commas that break GoSen.


Edit: Once you've downloaded and unzipped GoSen, run ant in the top directory to build an executable JAR file. Note that if you want javadoc, you'll have to change build.xml so that the javadoc command has 'encoding="utf-8"'. Next, you must download the IPADIC dictionary from its legacy repository, here. Unpack the contents into testdata/dictionary. Change testdata/dictionary/build.xml so that the value of "ipadic.version" is "2.7.0" (the version that you downloaded). Now run ant in this directory to build the dictionary. [If you had errors, you may have forgotten to run ant in the top level directory first.]


Then, to run a demo and see what amazing things GoSen can do, copy the dictionary.xml file from the testdata/dictionary directory to the dictionary/dictionary directory, go back to the root directory of GoSen, and then run java -cp bin examples.ReadingProcessorDemo testData/dictionary/dictionary.xml. The GoSen site says to run using the testdata folder, but that means you'll have to download the dictionary twice, which is dumb. When you run the above command, you'll get this GUI:

Notice that it tokenizes the sentence, gives readings, and allows you to choose among alternatives analyses. It also gives information on part of speech and inflection.
To use GoSen in an Eclipse project, add gosen-1.0beta.jar to the project build path. You also need to have the dictionary directory somewhere, along with the dictionary.xml file. This code will get you started:

package edu.byu.xnlsoar.jp.lexacc;

import java.io.IOException;
import java.util.List;

import edu.byu.xnlsoar.utils.Constants;



import net.java.sen.SenFactory;
import net.java.sen.StringTagger;
import net.java.sen.dictionary.Morpheme;
import net.java.sen.dictionary.Token;

public class GoSenInterface {
 public List tokenize(String sentence){
  StringTagger tagger = SenFactory.getStringTagger(Constants.getProperty("GOSEN_DICT_CONFIG"));
  try {
   return tagger.analyze(sentence);
  } catch (IOException e) {
   e.printStackTrace();
   System.exit(-1);
  }
  return null;
 }
 public static void main(String[] args){
  String sentence = "やっぱり日本語情報処理って簡単に出来ちゃうんだもんな。";
  GoSenInterface dict = new GoSenInterface();
  System.out.println("tokenizing " + sentence);
  List tokens = dict.tokenize(sentence);
  System.out.println(tokens);
  Morpheme m;
  System.out.println("surface, lemma, POS, conjugation");
  for(Token t : tokens){
   System.out.print(t + ", ");
   m = t.getMorpheme();
   System.out.print(m.getBasicForm() + ", ");
   System.out.print(m.getPartOfSpeech() + ", ");
   System.out.println(m.getConjugationalType());
  }
 }
}

If you run that you will get:
tokenizing やっぱり日本語情報処理って簡単に出来ちゃうんだもんな。
[やっぱり, 日本語, 情報処理, って, 簡単, に, 出来, ちゃう, ん, だ, もん, な, 。]
surface, lemma, POS, conjugation
やっぱり, やっぱり, 副詞-一般, *
日本語, 日本語, 名詞-一般, *
情報処理, 情報処理, 名詞-一般, *
って, って, 助詞-格助詞-連語, *
簡単, 簡単, 名詞-形容動詞語幹, *
に, に, 助詞-副詞化, *
出来, 出来る, 動詞-自立, 一段
ちゃう, ちゃう, 動詞-非自立, 五段・ワ行促音便
ん, ん, 名詞-非自立-一般, *
だ, だ, 助動詞, 特殊・ダ
もん, もん, 名詞-非自立-一般, *
な, だ, 助動詞, 特殊・ダ
。, 。, 記号-句点, *


You have plenty of other options while processing, like grabbing alternate readings, etc. Notice that it got one wrong here: ちゃう is a contraction of てしまう, not a verb whose lemma is ちゃう. It doesn't seem to work on contractions because every token needs a surface form. So this might not work well on informal registers such as tweets or blogs unless some pre-preprocessing is done.
Feel free to leave any questions or comments.

CS 240 Web Crawler at BYU

I recently polished off the web crawler project for CS 240 at BYU. It's probably the most talked-about project in the CS major, and the cause of so many students retaking the class.
The specification for the web crawler assignment can be found here. Basically, given a start URL, the crawler finds every link on a page, follows them, downloads the pages, and indexes each of the words on a page, as long as they are not in a given stop words file; then it follows the links from that page, and so on.  All of the indexed information is printed out to XML files. The code also has to conform to proper style, and no memory leaks are allowed.
For those who still need to do the project or haven't taken the following exam yet, I thought I'd post a note or two of help.
First off, check your constructors! In an initialization for a templatized BST node, I had been invoking the default copy constructor. A copy constructor looks like this:

T(const T & other)


In the contained object, I had only implemented the operator= construction. My class T had pointers in it, and those pointers were to objects which were allocated on the heap with the new keyword. The default copy constructor copied the pointers, and when the copy of the object of type T was deleted, so were the structures that its pointers pointed to. Since the original object pointed to the same structures, that object would then cause a segfault when destroyed because it would try to delete non-existent structures. Ouch!

That bug wasted a good 6 hours of my life. Needless to say, I was a little scared of the next assignment: a debugging exam. The class TAs put 4 bugs into our code (they didn't touch comments, asserts, or unit tests), and we had 3 hours to find them. Here's what the TA's did to my code:

1. In my URL class, I call erase on a string representing a relative URL to get ride of the "../" at the beginning. The correct code is url.erase(0,3), but the TAs changed it to url.erase(0,2).
2. In my BST Insert method, there is a control structure that determines whether to put a value on a node's left or right, and the TA's changed one of the left's to right's, i.e. node->left = new BSTNode<T> (v); was changed to node->right = new BSTNode<T> (v);.
3. I have several boolean flags in an HTMLparser class which keep track of whether processing is inside of a header, title, body, or html tag. They should all be false at the beginning of processing, but one of them was changed to true, e.g.
   constructor():titleFlag(false),bodyFlag(false),headerFlag(true){...
4. The last bug was a memory leak. In my linked list Insert method, I declare a linked list node, use a control structure to determine the proper location of the new node, and then set the node with a call to new and insert it in that location. The TA's changed the declaration to be a definition which used the new keyword, so I always allocated one extra node on the heap.

The first three bugs I was I able find through unit testing. The last one I pinpointed using valgrind and print statements; however, even though it was staring me in the face, I couldn't find it and only got 75% on the exam.

In case somebody finds the code interesting/useful, I'll post it here (no cheating!). Make with make bin. Run with bin/crawler <start url> <stopwords file> <output file>.

String Allignment with Edit Operations

A common way to measure the distance between two strings is using Levenshtein distance. Levenshtein distance is the minimum number of deletions, insertions, and substitutions needed to transform one string into another. Finding the distance between two strings is useful in certain applications such as spell checking (a word processor will suggest dictionary words that are close to your misspelled word). See wikipedia for more details and an example of Levenshtein distance calculation.
Another related and also important operation is to find the minimum edit alignment; that is, once the minimum edit distance between the two strings is found, output the sequence of operations that can be used to change the one string into the other. For example, if we let C mean "correct", S mean "substitution", D mean "deletion" and I mean "insertion", then the edit alignment between the characters in "construction" and "distortions" would be ISSCCISSCCCCD. Here is an explanation of the alignment:

• I: Insert a "c" ->cdistortions
• S: Substitute "d" for "o" ->coistortions
• S: Substitute "i" for "n" -> constortions
• CC: Leave the "st" alone
• I: Insert "r" -> constrortion
• S: Substitute "u" for "o" -> contrurtion
• S: Substitute "c" for "r" -> constructions
• CCCC: Leave "tion" alone
• D: delete "s" -> construction

This sort of an allignment operation is commonly used in grading the output of machine translation and speech recognition systems, though the operations are done at the word level instead of the character level. When I needed a quick piece of code to do the alignment in my own application, though, there was none to be found on the internet! So I made my own and am posting it here. The logic for determining the proper string of edit operations is taken from a StackOverflow answer here. And now the code:

	/**
	 * @return List of Operations representing allignment between list1 and
	 * list2. The allignment represents operations to change list2 into list1.
	 */
	
	public static List levenshteinAllignment(Object[] list1, Object[] list2) {
		int[][] distanceMatrix = getDistanceMatrix(list1, list2);
		List ops= new ArrayList(
				list1.length > list2.length ? list1.length : list2.length);
		//think of distance chart as going from bottom left to top right;
		//current position coordinates; start at top right.
		int row = list1.length;
		int col = list2.length;
		//could have moved to current position from three others; store their scores here.
		int diag;
		int left;
		int below;
		int current;
		
		while (row != 0 || col != 0) {
			diag = getVal(row-1,col-1,distanceMatrix);
			left = getVal(row,col-1,distanceMatrix);
			below = getVal(row-1,col,distanceMatrix);
			current = distanceMatrix[row][col];

//			   if the value in the diagonal cell (going up+left) is smaller or equal to the
//			      values found in the other two cells
				
//			   AND 
//			      if this is same or 1 minus the value of the current cell 
			if(diag <= left && diag <= below && (diag == current || diag == current - 1)){
//				   then  "take the diagonal cell"
//		         if the value of the diagonal cell is one less than the current cell:
				if(diag == current - 1)
//		            Add a SUBSTITUTION operation (from the letters corresponding to
//		            the _current_ cell)
					ops.add(new Operation(Operation.Type.SUBSTITUTION,list1[row-1],list2[col-1]));
				else
//			        otherwise: do not add an operation this was a no-operation.
					ops.add(new Operation(Operation.Type.CORRECT,list1[row-1]));
				//move diagonally
				row--;
				col--;
			}
//
//		    elseif the value in the cell to the left is smaller or equal to the value of
//		  		the cell below current cell
//		   	AND 
//	       	if this value is same or 1 minus the value of the current cell 
			else if(left < below && (left == current || left == current - 1)){
//		        add an INSERTION of the cell to the left
				ops.add(new Operation(Operation.Type.INSERTION,list2[col-1]));
				//move left
				col--;
			}
//		   	else
			else{
//		       take the cell below, add
//		       Add a DELETION operation
				ops.add(new Operation(Operation.Type.DELETION,list1[row-1]));
				//move down
				row--;
			}
		}
		Collections.reverse(ops);
		return ops;
	}
	private static int getVal(int row, int col, int[][] distanceMatrix){
		if(row < 0 || row > distanceMatrix.length)
			return Integer.MAX_VALUE;
		if(col < 0 || col > distanceMatrix.length)
			return Integer.MAX_VALUE;
		else return distanceMatrix[row][col];
	}
	public static class Operation{
		private Type type;
		private Object object1;
		private Object object2;
		public enum Type{
			CORRECT,SUBSTITUTION,DELETION,INSERTION
		}
		public Operation(Type t, Object o1){
			type = t;
			object1 = o1;
			object2 = null;
		}
		public Operation(Type t, Object o1, Object o2){
			type = t;
			object1 = o1;
			object2 = o2;
		}
		@Override
		public String toString(){
			if(type == Type.SUBSTITUTION)
				return "Substitution: " + object1.toString() + " -> " + object2.toString();
			if(type == Type.CORRECT)
				return "Correct:      " + object1.toString();
			if(type == Type.DELETION)
				return "Deletion:     " + object1.toString();
			if(type == Type.INSERTION)
				return "Insertion:    " + object1.toString();
			return null;
		}
	}

	/**
	 * 
	 * @param array of objects to compare
	 * @param array of objects to compare
	 * @return Levenshtein distance between arrays.
	 * This method uses the equals(Object o) method to compare the
	 * objects in the two arrays, returning the Levenshtein distance between them.
	 */
	public static int levenshteinDistance(Object[] list1, Object[] list2) {

		int[][] distance = getDistanceMatrix(list1, list2);
		return distance[list1.length][list2.length];
	}

	/**
	 * 
	 * @param list1
	 * @param list2
	 * @return A completely filled distance matrix; movement from [i-1][j]
	 *         represents insertion, from [i][j-1] represents deletion, and from
	 *         [i-1][j-1] represents substitution or no operation.
	 */
	private static int[][] getDistanceMatrix(Object[] list1, Object[] list2) {
		int[][] distanceMatrix = new int[list1.length + 1][list2.length + 1];

		for (int i = 0; i <= list1.length; i++)
			distanceMatrix[i][0] = i;
		for (int j = 0; j <= list2.length; j++)
			distanceMatrix[0][j] = j;

		for (int i = 1; i <= list1.length; i++)
			for (int j = 1; j <= list2.length; j++)
				distanceMatrix[i][j] = minimum(distanceMatrix[i - 1][j] + 1,// insertion
						distanceMatrix[i][j - 1] + 1,// deletion
						distanceMatrix[i - 1][j - 1]// substitution or correct
								+ ((list1[i - 1].equals(list2[j - 1])) ? 0 : 1));
		return distanceMatrix;
	}

	/**
	 * Same as Math.min, but returns the minimum of three arguments instead of
	 * two.
	 */
	private static int minimum(int a, int b, int c) {
		return Math.min(Math.min(a, b), c);
	}

For word level alignment, you can call it on Strings using the split function like so:

for(Operation o : levenshteinAllignment(
			"What My house gleams with the light of the moon and your face"
					.split(" "),
			"Your house with the light of the the moon and my face"
					.split(" "))
		)
			System.out.println(o);

And the output would be:
Deletion: What
Substitution: My -> Your
Correct: house
Deletion: gleams
Correct: with
Correct: the
Correct: light
Correct: of
Correct: the
Insertion: the
Correct: moon
Correct: and
Substitution: your -> my
Correct: face
Feel free to use and edit this as you like. Many applications disregard the strings that are correct and only output the edit operations, and that should be an easy edit.