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