Edit Distance in Java

This is a simple implementation of edit distance, which is used in spell error correction in NLP.

public class MED{
public static void main(String[] args){
MED med = new MED();
med.min_edit_dic("abc", "cabc");
}
public int min_edit_dic( String target ,String source){
int n = target.length();
int m = source.length();
int[][] distance = new int[ n+1 ][ m+1 ];
distance[ 0 ][ 0 ] = 0;
for ( int i = 1; i <= n; i++){
distance[ i ][ 0 ] = distance[ i-1 ][ 0 ] + ins_cost(target.charAt(i-1));
}
for ( int j = 1; j <= n; j++){
distance[ 0 ][ j ] = distance[ 0 ][ j-1 ] + ins_cost(target.charAt(j-1));
}
for ( int i = 1; i <= n; i++){
for ( int j = 1; j <= m; j++){
int ins = distance[ i-1 ][ j ] +ins_cost(target.charAt(i-1));
int sub = distance[ i-1 ][ j-1 ] + subs_cost(target.charAt(i-1),source.charAt(j-1));
int del = distance[ i ][ j -1 ] + del_cost(source.charAt(j-1));
distance[i][j] =  min( ins, min(sub,del));
}
}

for ( int i = 0; i <= n; i++){
for ( int j = 0; j <= m; j++){
System.out.print(distance[i][j]+"\t");
}
System.out.println();
}

return 1;
}

private int min(int d1, int d2){
return d1 < d2 ? d1: d2;
}

private int ins_cost(char c){
return 1;
}

private int del_cost(char c){
return 1;
}

private int subs_cost(char c1 , char c2){
return c1 != c2 ? 2 : 0;
}
}

Comparison of StringBuilder and StringBuffer

StringBuilder and StringBuffer are very common classes in Java.
Here, I am comparing with these two classes.
Generally speaking,
StringBuilder is
1) non-synchronized
2) be careful when using multithreads
3) faster  

StringBuffer 
1) synchronized.
2) safer but slower

>>Java test codes
public class StringDemo{
public static void main(String[] args){
int N = 100000;
StringBuffer buffer = new StringBuffer();
StringBuilder builder = new StringBuilder();
long begin = System.currentTimeMillis();
for(int i = 0; i < N; i++){
buffer.append(" ");
}
System.out.println("StringBuffer takes " + (System.currentTimeMillis() - begin) + " ms");
begin = System.currentTimeMillis();
for(int i= 0; i < N; i++){
builder.append(" ");
}
System.out.println("StringBuilder takes " + (System.currentTimeMillis() - begin) + " ms");
}
}

output >>
StringBuffer takes 8 ms
StringBuilder takes 1 ms

parameters in function

As everyone knows, there are two ways to pass value in java. The first one is passed by value (only prime type such as: int, float, double), the other one is passed by inference(object). Given the sample code below, what is the answer?
1.
Mon Dec 20 00:00:00 JST 1999
Wed Dec 20 00:00:00 JST 2000
1
2.
Mon Dec 20 00:00:00 JST 1999
Mon Dec 20 00:00:00 JST 1999
1
3.
Wed Dec 20 00:00:00 JST 2000
Wed Dec 20 00:00:00 JST 2000
2
4.
Mon Dec 20 00:00:00 JST 1999
Wed Dec 20 00:00:00 JST 2000
2

public class Demo{
       public static void main(String[] args){
  Date d1 = new Date(99, 11, 20);
  Date d2 = new Date(99, 11, 20);
  method(d1, d2);
  System.out.println(d1);
  System.out.println(d2);
  ArrayList list = new ArrayList();
  list.add(1);
  inferencePara(list);
  System.out.println(list.get(0));
 }

 public static void method(Date d1, Date d2){
  d2.setYear(100);
  d1 = d2;
 }
 
 public static void inferencePara(ArrayList list){
  list = new ArrayList();
  list.add(2);
 }
}

Compute height of a binary tree

A very easy and neat way to compute height of tree is using recursive function.

private int height(Node node) {
	if (null == node)
		return 0;
	else {
		return (1 + Math.max(height(node.left), height(node.right)));
	}
}

public int height() {
	return height(root);
}

As an alternative, we can use iterative way to compute it. Here, I used the breadth first to compute height of a tree.

public int iterativeHeight() {
	int rvl = 0;
	int numNode = 0;
	Node node = root;
	// queue
	LinkedList> que = new LinkedList();
	que.addLast(node);
	numNode = 1; // in root level
	while (!que.isEmpty()) {
		rvl++;
		int localNum = 0; //record how many node added in level
		for (; numNode > 0; numNode--) {
			node = que.removeFirst();
			if (node.right != null) {
				que.addLast(node.right);
				localNum++;
			}
			if (node.left != null) {
				que.addLast(node.left);
				localNum++;
			}
		}
		numNode = localNum;
	}
	return rvl;
}

A generic java library for binary tree

A practice java code for generic binary tree java code.

package tree;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Stack;

public class Tree> implements Serializable {
	private static final long serialVersionUID = 1L;
	private Node root;

	public static void main(String[] args) {
		Tree tree = new Tree();
		tree.insert(10);
		tree.insert(7);
		tree.insert(3);
		tree.insert(5);
		tree.insert(4);
		tree.insert(13);
		tree.insert(12);
		tree.insert(14);
		tree.inorder();
		System.out.println();
		tree.preorder();
		System.out.println();
		tree.postorder();
		System.out.println();

		ArrayList list = tree.morrisInorder();
		for (Integer i : list)
			System.out.print(i + " ");
		System.out.println();
		System.out.println(tree.isExist(12));
		tree.deleteByMerg(10);
		tree.preorder();
		tree.deleteByCopy(7);
		System.out.println();
		tree.postorder();

	}

	public Tree() {
		root = null;
	}

	public void visit(Node node) {
		System.out.print(node.ele + " ");
	}

	public void postorder() {
		postorder(root);
	}

	private void postorder(Node node) {
		if (null != node) {
			postorder(node.left);
			postorder(node.right);
			visit(node);
		}
	}

	public void preorder() {
		preorder(root);
	}

	private void preorder(Node node) {
		if (null != node) {
			visit(node);
			preorder(node.left);
			preorder(node.right);
		}
	}

	public void inorder() {
		inorder(root);
	}

	private void inorder(Node node) {
		if (null != node) {
			inorder(node.left);
			visit(node);
			inorder(node.right);
		}
	}

	public void insert(E ele) {
		Node tmp = root, pre = null;
		while (null != tmp) {
			pre = tmp;
			if (tmp.ele.compareTo(ele) < 0)
				tmp = tmp.right;
			else
				tmp = tmp.left;
		}
		if (null == root)
			root = new Node(ele);
		else if (pre.ele.compareTo(ele) < 0)
			pre.right = new Node(ele);
		else if (pre.ele.compareTo(ele) > 0)
			pre.left = new Node(ele);
		else {
			throw new IllegalArgumentException("duplicate element: " + ele);
		}
	}

	public void deleteByCopy(E ele) {
		Node tmp, node, p = root, pre = null;
		while (null != p && !p.ele.equals(ele)) {
			pre = p;
			if (p.ele.compareTo(ele) < 0)
				p = p.right;
			else
				p = p.left;
		}
		node = p;
		if (null != p && p.ele.equals(ele)) {
			Node previous = node;
			for (tmp = node.left; tmp.right != null; tmp = tmp.right){
				previous = tmp;
			}
			node.ele = tmp.ele; // right-most of left child
			if(previous == node)
				tmp = tmp.right;
			else
				previous.right = tmp.left;
			
		} else if (null != root)
			throw new IllegalArgumentException("not exist:" + ele);
		else
			throw new IllegalArgumentException("empty tree");
	}

	public void deleteByMerg(E ele) {
		Node tmp, node, p = root, pre = null;
		while (p != null && !p.ele.equals(ele)) {
			pre = p;
			if (p.ele.compareTo(ele) < 0)
				p = p.right;
			else
				p = p.left;
		}
		node = p;
		// find the element needed to delete
		if (node != null && node.ele.equals(ele)) {
			// only have left child
			if (node.left == null)
				node = node.right;
			// only have right child
			else if (node.right == null)
				node = node.left;
			// have two children, first find the right-most child of left child
			else {
				for (tmp = node.left; tmp.right != null; tmp = tmp.right)
					;
				tmp.right = node.right;
				node = node.left;
			}
			if (root == p)
				root = node;
			else if (pre.left == p)
				pre.left = node;
			else
				pre.right = node;
		} else if (null != root)
			throw new IllegalArgumentException("not exist element: " + ele);
		else
			throw new IllegalArgumentException("empty tree~");

	}

	public boolean isExist(E ele) {
		if (null == root)
			return false;
		Node node = root;
		while (node != null && !node.ele.equals(ele)) {
			if (node.ele.compareTo(ele) < 0)
				node = node.right;
			else
				node = node.left;
		}
		if (node == null)
			return false;
		else
			return true;
	}

	public ArrayList iteratorPostOrder() {
		ArrayList list = new ArrayList();
		if (null == root)
			return list;
		Stack> stack = new Stack>();
		Node p = root, q = root;
		while (null != p) {
			for (; p.left != null; p = p.left)
				stack.push(p);
			while (p != null && (p.right == null || p.right == q)) {
				list.add(p.ele);
				q = p;
				if (stack.isEmpty())
					return list;
				else
					p = stack.pop();
			}
			stack.push(p); // with right node
			p = p.right;
		}

		return list;
	}

	public ArrayList iteratorPreOrder() {
		ArrayList list = new ArrayList();
		if (null == root)
			return list;
		Node p = root;
		Stack> stack = new Stack>();
		stack.push(p);
		while (null != p && !stack.isEmpty()) {
			p = stack.pop();
			list.add(p.ele);
			if (p.right != null)
				stack.push(p.right);
			if (p.left != null)
				stack.push(p.left);
		}
		return list;
	}

	public ArrayList iteratorInorder() {
		ArrayList list = new ArrayList();
		if (null == root) {
			System.err.println("empty tree~");
			return list;
		}
		Node p = root;
		Stack> stack = new Stack>();
		while (null != p) {
			// find the left most node
			while (null != p) {
				if (p.right != null)
					stack.push(p.right);
				stack.push(p);
				p = p.left;
			}
			p = stack.pop(); // left node
			while (!stack.isEmpty() && p.right == null) {
				list.add(p.ele);
				p = stack.pop();
			}
			list.add(p.ele); // get the right node
			if (!stack.isEmpty())
				p = stack.pop();
			else
				p = null;

		}
		return list;
	}

	public ArrayList morrisInorder() {
		ArrayList list = new ArrayList();
		if (null == root) {
			System.err.println("empty tree");
			return list;
		}

		Node p = root, tmp;
		while (null != p) {
			if (null == p.left) {
				list.add(p.ele);
				p = p.right;
			} else {
				tmp = p.left;
				for (; tmp.right != null && tmp.right != p; tmp = tmp.right)
					;
				if (tmp.right == null) {
					tmp.right = p;
					p = p.left;
				} else {
					list.add(p.ele);
					tmp.right = null;
					p = p.right;
				}
			}
		}

		return list;
	}

	private static class Node> {
		E ele;
		Node left, right;

		Node(E ele, Node left, Node right) {
			this.ele = ele;
			this.left = left;
			this.right = right;
		}

		Node(E ele) {
			this(ele, null, null);
		}
	}

}

Command Editing Shortcuts

Command Editing Shortcuts

• Ctrl + a – go to the start of the command line
• Ctrl + e – go to the end of the command line
• Ctrl + k – delete from cursor to the end of the command line
• Ctrl + u – delete from cursor to the start of the command line
• Ctrl + w – delete from cursor to start of word (i.e. delete backwards one word)
• Ctrl + y – paste word or text that was cut using one of the deletion shortcuts (such as the one above) after the cursor
• Ctrl + xx – move between start of command line and current cursor position (and back again)
• Alt + b – move backward one word (or go to start of word the cursor is currently on)
• Alt + f – move forward one word (or go to end of word the cursor is currently on)
• Alt + d – delete to end of word starting at cursor (whole word if cursor is at the beginning of word)
• Alt + c – capitalize to end of word starting at cursor (whole word if cursor is at the beginning of word)
• Alt + u – make uppercase from cursor to end of word
• Alt + l – make lowercase from cursor to end of word
• Alt + t – swap current word with previous
• Ctrl + f – move forward one character
• Ctrl + b – move backward one character
• Ctrl + d – delete character under the cursor
• Ctrl + h – delete character before the cursor
• Ctrl + t – swap character under cursor with the previous one

Get it from http://www.skorks.com/2009/09/bash-shortcuts-for-maximum-productivity/

Fix Yamacha installation errors

1. Following the document, install TinySVM.

2. Configure Yamacha as following:

./configure --prefix=/locations-you-like/

make

Error 1:

param.cpp: In member function 'bool YamCha::Param::open(int, char**, const YamCha::Option*)':

param.cpp:102:42: error: 'strlen' was not declared in this scope

param.cpp:103:68: error: 'strncmp' was not declared in this scope

param.cpp: In member function 'bool YamCha::Param::open(const char*, const YamCha::Option*)':

param.cpp:182:28: error: 'strncpy' was not declared in this scope

param.cpp:185:14: warning: deprecated conversion from string constant to 'char*' [-Wwrite-strings]

param.cpp: In member function 'void YamCha::Param::help(std::ostream&, const YamCha::Option*)':

param.cpp:205:42: error: 'strlen' was not declared in this scope

param.cpp:211:38: error: 'strlen' was not declared in this scope

#vi param.h

#change include -> include

make

Error 2:

mkdarts.cpp: In function ‘int main(int, char**)’:

mkdarts.cpp:83:14: error: ‘atoi’ is not a member of ‘std’

Solution:

add following to the mkdarts:

#include

make

make install

string parser c++

Splitting a string to a vector of words is very common task in text processing field. And I try to write  several lines of C++ code to deal this problem.

size_t split(const std::string &line, std::vector<std::string> &wordVec, const char sep)

{

    wordVec.clear();

    std::string::size_type pos = 0, prev_pos = 0;

    while (std::string::npos != (pos = line.find_first_of(' ', pos))) {

        wordVec.push_back(line.substr(prev_pos, pos - prev_pos));

        prev_pos = ++pos;

    }

    if(prev_pos < line.size())

    {

        wordVec.push_back(line.substr(prev_pos, pos-prev_pos));

//        std::cout<<"["<

    }

    

    return wordVec.size();

}

Evaluating models note

How to evaluate a language model?

To evaluate a model good or bad, it really depends on the performance on the test data. Therefore given
test data, we can write it symbolically as:

p(model | test-data),

Using Bayes rule:

p(model | test-data) = p(model) * p(test-data | model) / p(test-data) (1)

For simplifying the model, we assume that p(model) is the same for all models. Since given the test-data, p(test-data) is also the same for all models. As a consequence, the formula is simplified as:

p(model | test-mode) ~ p(test-data | model) (2)

Take the Bigram as a example, given a test-data, the formula (2) can be broken down into multiply components which is less than one. If the test data is very long, the value is computed by formula (2) is very small.  In many practice cases, people use perplexity install of (2), which depicted as:

-log( p(test-data | model) / #(terms) ) (3)

where #(terms) means the number of words in the test data.

As (2) increases, the (3) decreases, which means the best model is the one with the lowest perplexity.

mecab buffer error

Today, I try the Mecab to deal with Japanese word segmentation problem.

But the buffer-errors comes out.

input-buffer overflow. The line is split. use -b #SIZE option.

we can set a bigger buffer to fixed this problem. 

for example, the default size is 8192, we can change it to 8192 * 5

mecab -b 40960 < data

Best paper VS Top Cited Papers in CS

I found a very interesting web sits. It compares the best paper and top cited papers in computer science conference.

click

Fix the problem "tar: Failed to set default locale" in Mac OS X

write the following in terminal

defaults write org.R-project.R force.LANG en_US.UTF-8

and restart R

from:
http://davidprakash.blogspot.jp/2011/05/r-error-tar-failed-to-set-default.html