algorithm: Levenshtein Distance, Edit Distance

Algorithm

Dynamic Programming

Levenshtein Distance / Edit Distance

Sometimes you want to determine how similar a string s is to another string t. This is represented by the concept of Edit Distance, also called Levenshtein Distance. The smaller the Edit Distance, the more "closer" or "similar".

The Edit Distance is the cost to change the string s to the string t by adding the following 3 operations. Costs are ususally set for each of the 3 types of operations.

SUBSTITUTE ... Replace one character in string s with another one. (ex.) apble → apple
INSERT ... Insert one character in string s. (ex.) aple → apple
DELETE ... delete one character in string s. (ex.) applet → apple

To calculate the Edit Distance, we use Dynamic Programming. In order to find the Edit Distance between strings of length $n$ and length $m$, each element of the 2-dimensional matrix $(n+1) \times (m+1)$ is calculated, so the computational complexty is $O(mn)$.

[Points to Understand]

Carefully check the state of the string in each cell in "Table 1: State of the string being edited". If you understand that the state of the string consists of three elements:

generated string
consumed string
cursor position (edit point)

you can easily understand the algorithm.

Example of Edit Distance Calculation

Consider an edit operation to minimize the cost of generating the string "ara" from the string "saka". We want to reuse the reusable characters in the string "saka" while consuming other characters to generate the string "ara" as efficiently as possible.

To solve with Dynamic Programming, we use a table with the original (to be consumed) string in the vertical direction and the target (to be generated) string in the horizontal direction. Leave a blank space at the beginning of each string.

The state of the string being edited corresponding to each cell in this table is as follows.

The position where the string is being edited is called "cursor position" or "editing point", and is represented by '|' (vertical bar).
The characters to the left of '|' are "generated characters" in the target string.
The caracters to the right of '|' are "characters to be consumed" in the original string.

Table 1: State of the string being edited.

		a	r	a
	\|saka	a\|saka	ar\|saka	ara\|saka
s	\|aka	a\|aka	ar\|aka	ara\|aka
a	\|ka	a\|ka	ar\|ka	ara\|ka
k	\|a	a\|a	ar\|a	ara\|a
a	\|	a\|	ar\|	ara\|

If you just want to find the minimum cost, one table is fine. If you need to record the steps of your editing operations, prepare another table.

In this example, we assume the cost of each operation as follows. Of course you can set these values however you like.

Table 2: Costs of each Edit Operation

Operation	Simbol	Const	Explanation
INSERT	$I$	$1$	Insert a character to the left of the cursor.
DELETE	$D$	$1$	Delete a character to the right of the cursor.
SUBSTITUTE	$S$	$1$	Substitute a character to the right of the cursor, and move the cursor position one character to the right.
MATCH	$M$	$0$	Move the cursor position one character to the right.

In the following, the $L$ row and $R$ column elements of the table are expressed as $(L,R)$.

Of the two tables, the left table records the minimum costs and the right table records the last operation performed.

Enter cost $0$ at ($0$, $0$) in the left table, and enter '$-$' character to the ($0$, $0$) cell in the right table, because no operation has been performed yet.

cell	operation	String being edited
(0,0)	the initial state	\|saka

Fill in the leftmost column ($L$, $0$) of the left table while adding the DELETE cost. Since the operation is "DELETE", enter '$D$' in ($L$, $0$) cells of the right table.

cell	operation	String being edited
(0,0)	initial state	\|saka
(1,0)	DELETE 's'	\|aka
(2,0)	DELETE 'a'	\|ka
(3,0)	DELETE 'k'	\|a
(4,0)	DELETE 'a'	\|

Enter the cost of INSERT in the column ($0$, $R$) of the top row of the left table while adding the INSERT cost. Since the operation is INSERT, enter '$I$' in ($0$, $R$) in the right table.

cell	operation	string being edited
(0,0)	initial state	\|saka
(0,1)	INSERT 'a'	a\|saka
(0,2)	INSERT 'r'	ar\|saka
(0,3)	INSERT 'a'	ara\|saka

$L=1$, $R=1$.
The cost to be enterd in ($L$, $R$) in the left table is one of the following.

SUBSTITUTE from the upper left cell ($L-1$, $R-1$)
MATCH (= Cursor Move) from the upper left cell ($L-1$,$R-1$) $\quad$ Only when the characters are equal.
DELETE from the upper cell ($L-1$,$R$)
INSERT from the left cell ($L$, $R-1$)

Calculate the minimum cost and enter it in the ($L$, $R$) cell of left table, and enter the selected operation in the ($L$, $R$) cell of the right table.

Let's consider the minimum cost to reach the state ($1$, $1$) in the left table. Since the character 's' at the cursor position is not equal to the character 'a' to be generated, "MATCH (= Cursor Move)" can not be used. Therefore, we consider 3 kinds of operations to arrive at ($1$, $1$):

SUBSTITUTE 's' with 'a' from state ($0$, $0$), the cost is $0+1=1$.
DELETE 's' from state ($0$, $1$) where 'a' was previously INSERTed, the cost is $1+1=2$.
INSERT 'a' from state ($1$, $0$) where 's' was previously DELETEd, the cost is $1+1=2$.

Among them, "REPLACE 's' with 'a'" has the lowest cost of 1, so 1 in the left table ($1$, $1$) and '$S$' in the right table ($1$, $1$).

cell	operation	String being edited
(0,0)	initial state	\|saka
(1,1)	SUBSTITUTE 's' with 'a'	a\|aka

Regardless of the operation order, the state of ($1$, $1$) is the state where "the leading 's' is disappeared from the string to be consumed" and "the leading 'a' has been generated from the string to be generated". The minimum cost to reach that state is $1$.

$L=2$, $R=1$.
The cost to be enterd in ($L$, $R$) in the left table is one of the following.

SUBSTITUTE from the upper left cell ($L-1$, $R-1$)
MATCH (= Cursor Move) from the upper left cell ($L-1$,$R-1$) $\quad$ Only when the characters are equal.
DELETE from the upper cell ($L-1$,$R$)
INSERT from the left cell ($L$, $R-1$)

Calculate the minimum cost and enter it in the ($L$, $R$) cell of left table, and enter the selected operation in the ($L$, $R$) cell of the right table.

In ($2$, $1$) of the left table, the character to "be consumed" and the character to "be generated" are both 'a', so MATCH (= Cursor Move) can be used. There are other ways to "DELETE 'a'" from ($1$, $1$) and "INSERT 'a'" from ($2$, $0$), but "MATCH (= Cursor Move)" from ($1$, $0$) is the minimum cost. Enter $1+0=1$ in the left table ($2$, $1$) and '$M$' in the right table ($2$, $1$).

cell	operation	String being edited
(1,0)	DELETE 's'	\|aka
(2,1)	MATCH (= Cursor Move) 'a'	a\|ka

The state of ($2$, $1$) is "First, DELETE the leading 's' from the original string, then MOVE CURSOR through 'a' for the character of the orignal and the target is the same. The minimum cost of the operations is $1 \mbox{(DELETE cost)} + 0 \mbox{(MATCH cost)} = 1$.

In ($3$, $1$) of the left table, the character 'k' to "be consumed" is different from the character 'a' to "be generated", so MATCH (= Cursor Move) cannot be used. The cost of "SUBSTITUTE from ($2$, $0$)" is 3, the cost of "INSERT from ($3$, $0$)" is 4, and the cost of "DELETE from ($2$, $1$)" is 2.

cell	operation	String being edited
(1,0)	DELETE 's'	\|aka
(2,1)	MATCH (= Cursor Move) 'a'	a\|ka
(3,1)	DELETE 'k'	a\|a

All the cell is filled.

If multiple symbols are written together in the right table, it means that either operation has the lowest cost. For example, the symbol "SI" means "either SUBSTITUTE or INSERT is OK".

You can see that the minimum cost is $2$ by looking at the bottom right cell of the left table ($4$, $3$).

You can see how to get to the minimum cost by going backwards starting from the bottom right cell of the right table.

In case of '$S$' or '$M$', go to the upper left cell.
In case of '$I$', go to the left cell.
In case of '$D$', goto the upper cell.

The operation sequence with the lowest cost is as follows.

cell/th>	operation	String being edited
(0,0)	initial state	\|saka
(1,0)	DELETE 's'	\|aka
(2,1)	MATCH 'a'	a\|ka
(3,2)	SUBSTITUTE 'k' with'r'	ar\|a
(4,3)	'MATCH a'	ara\|

Program of Edit Distance (python, Cost only)

EditDistance.py

import sys

COST_DEL = 1
COST_INS = 1
COST_SUBST = 1
COST_MATCH = 0

COST = []

def solve(s,t,flag = False):
  global COST
  sl = len(s)
  tl = len(t)
  COST = [[0 for i in range(tl+1)] for j in range(sl+1)]
  COST[0][0] = 0
  for i in range(1,sl+1):
    COST[i][0] = COST[i-1][0] + COST_DEL
  for i in range(1,tl+1):
    COST[0][i] = COST[0][i-1] + COST_INS
  for i in range(1,sl+1):
    for j in range(1,tl+1):
      c_d = COST[i][j-1] + COST_DEL
      c_i = COST[i-1][j] + COST_INS
      c_s = COST[i-1][j-1] + COST_SUBST
      if s[i-1]==t[j-1]: c_m = COST[i-1][j-1] + COST_MATCH
      else: c_m = sys.maxsize
      COST[i][j] = min(c_d, c_i, c_s, c_m)
  return COST[sl][tl]

Log of EditDistance.py

$ python  
Python 3.9.13 (main, Aug 25 2022, 23:26:10) 
[GCC 11.2.0] :: Anaconda, Inc. on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import EditDistance  
>>> EditDistance.solve('saka','ara')  
2
>>> print(EditDistance.COST)  
[[0, 1, 2, 3], [1, 1, 2, 3], [2, 1, 2, 2], [3, 2, 2, 3], [4, 3, 3, 2]]
>>> exit()

Program of Edit Distance (python, Cost and Operations)

EditDistancePath.py

import sys

COST_DEL = 1
COST_INS = 1
COST_SUBST = 1
COST_MATCH = 0

COST = []
OP = []

def solve(s,t):
  global COST, OP
  sl = len(s)
  tl = len(t)
  COST = [[0 for i in range(tl+1)] for j in range(sl+1)]
  OP = [['' for i in range(tl+1)] for j in range(sl+1)]
  COST[0][0] = 0
  for i in range(1,sl+1):
    COST[i][0] = COST[i-1][0] + COST_DEL
    OP[i][0] += 'D'
  for i in range(1,tl+1):
    COST[0][i] = COST[0][i-1] + COST_INS
    OP[0][i] += 'I'
  for i in range(1,sl+1):
    for j in range(1,tl+1):
      c_d = COST[i][j-1] + COST_DEL
      c_i = COST[i-1][j] + COST_INS
      c_s = COST[i-1][j-1] + COST_SUBST
      if s[i-1]==t[j-1]: c_m = COST[i-1][j-1] + COST_MATCH
      else: c_m = sys.maxsize
      COST[i][j] = min(c_d, c_i, c_s, c_m)
      if (c_d == COST[i][j]): OP[i][j] += 'D'
      if (c_i == COST[i][j]): OP[i][j] += 'I'
      if (c_s == COST[i][j]): OP[i][j] += 'S'
      if (c_m == COST[i][j]): OP[i][j] += 'M'
  return COST[sl][tl], getPath(s,t)

def getPath(s,t):
  global OP
  r = []
  row = len(s)
  col = len(t)
  while row > 0 or col > 0:
    s_ch = s[row-1]
    t_ch = t[col-1]
    if  'M' in OP[row][col]:
      r.append('MATCH '+s_ch)
      row -= 1
      col -= 1
    elif 'S' in OP[row][col]:
      r.append('SUBSTITUTE '+s_ch+' with '+t_ch)
      row -= 1
      col -= 1
    elif 'I' in OP[row][col]:
      r.append('INSERT '+t_ch)
      col -= 1
    elif 'D' in OP[row][col]:
      r.append('DELETE '+s_ch)
      row -= 1
  r.reverse()
  return r

Log of EditDistancePath.py

$ python  
Python 3.9.13 (main, Aug 25 2022, 23:26:10) 
[GCC 11.2.0] :: Anaconda, Inc. on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import EditDistancePath  
>>> EditDistancePath.solve('saka','ara')  
(2, ['DELETE s', 'MATCH a', 'SUBSTITUTE k with r', 'MATCH a'])
>>> print(EditDistancePath.COST)  
[[0, 1, 2, 3], [1, 1, 2, 3], [2, 1, 2, 2], [3, 2, 2, 3], [4, 3, 3, 2]]
>>> print(EditDistancePath.OP)  
[['', 'I', 'I', 'I'], ['D', 'S', 'DS', 'DS'], ['D', 'M', 'DS', 'M'], ['D', 'I', 'S', 'DIS'], ['D', 'IM', 'IS', 'M']]
>>> exit()

Program of Edit Distance (java)

Consider a program that calculates the edit distance between two strings.

In the following program, the array cost is "the minimum cost to reach each state" and the array parent records "the most recent operation to reach that state with the minimum cost". Since each type of operation is represented by a different bit, even multiple operations can be recorded at the same time.

MATCH ... the rightmost bit ($2^0 = 1$)
SUBSTITUTE ... 2nd bit from th right ($2^1 = 2$)
INSERT ... 3rd bit from the right ($2^2 = 4$)
DELETE ... 右から4番目のbit (= 8) ($2^3 = 8$)

For example, if the operation is "$SI$" (= SUBSTITUTE or INSERT), the operations are recorded as $2+4=6$.

For simplicity, only one operation sequence of the minimal cost is shown, even if there are multiple.

EditDistance.java

import java.util.*;
public class EditDistance {
    int COST_M = 0, COST_S = 1, COST_D = 1, COST_I = 1;
    public static final int OP_M = 1, OP_S = 2, OP_I = 4, OP_D = 8;
    String s,t;
    int[][] cost, op;
    public EditDistance(String s,String t) { this.s = s; this.t = t; }
    public void setSubstituteCost(int COST_S) { this.COST_S = COST_S; }
    public void setInsertCost(int COST_I) { this.COST_I = COST_I; }
    public void setDeleteCost(int COST_D) { this.COST_D = COST_D; }
    public int solve() {
	cost = new int[s.length()+1][t.length()+1];
	cost[0][0] = 0;
	op = new int[s.length()+1][t.length()+1];
	op[0][0] = 0;
	for (int i=1; i<cost.length; i++) {
	    cost[i][0] = cost[i-1][0] + COST_D;
	    op[i][0] = OP_D;
	}
	for (int i=1; i<cost[0].length; i++) {
	    cost[0][i] = cost[0][i-1] + COST_I;
	    op[0][i] = OP_I;
	}
	for (int si=1; si<cost.length; si++) {
	    for (int ti=1; ti<cost[0].length; ti++) {
		int c_m = (s.charAt(si-1) == t.charAt(ti-1)) ? cost[si-1][ti-1] + COST_M : Integer.MAX_VALUE;
		int c_s = cost[si-1][ti-1] + COST_S;
		int c_i = cost[si][ti-1] + COST_I;
		int c_d = cost[si-1][ti] + COST_D;
		cost[si][ti] = Math.min(c_m,Math.min(c_s,Math.min(c_i,c_d)));
		op[si][ti] = 0;
		if (cost[si][ti] == c_m) op[si][ti] |= OP_M;
		if (cost[si][ti] == c_s) op[si][ti] |= OP_S;
		if (cost[si][ti] == c_i) op[si][ti] |= OP_I;
		if (cost[si][ti] == c_d) op[si][ti] |= OP_D;
	    }
	}
	return cost[s.length()][t.length()];
    }
    public String[] getPath() {
	ArrayList<String> v = new ArrayList<String>();
	int si=cost.length-1;
	int ti=cost[0].length-1;
	while (si > 0 || ti > 0) {
	    if ((op[si][ti] & OP_M) != 0) {
		v.add("matches '"+s.charAt(si-1)+"' and '"+t.charAt(ti-1)+"'");
		si--; ti--;
	    } else if ((op[si][ti] & OP_S) != 0) {
		v.add("substitute '"+s.charAt(si-1)+"' by '"+t.charAt(ti-1)+"'");
		si--; ti--;
	    } else if ((op[si][ti] & OP_I) != 0) {
		v.add("insert '"+t.charAt(ti-1)+"'");
		ti--;
	    } else if ((op[si][ti] & OP_D) != 0) {
		v.add("delete '"+s.charAt(si-1)+"'");
		si--;
	    } else throw new RuntimeException("bad op");
	}
	Collections.reverse(v);
	return v.toArray(new String[0]);
    }
    public String showCostTable() { return toString(cost); }
    public String showOpTable() { return toString(op); }
    public String toString(int[][] x) {
	StringBuilder sb = new StringBuilder(" |   ");
	for (int i=0; i<t.length(); i++) sb.append("  "+t.charAt(i));
	int w = sb.toString().length();
	sb.append("\n");
	for (int i=0; i<w; i++) sb.append((i==1) ? "+" : "-");
	sb.append("\n");
	for (int line=0; line < x.length; line++) {
	    if (line == 0) sb.append(" | ");
	    else sb.append(s.charAt(line-1)+"| ");
	    for (int col=0; col < x[line].length; col++) {
		int v=x[line][col];
		if (v < 10 && v>=0) sb.append(" ");
		sb.append(v + " ");
	    }
	    sb.append("\n");
	}
	return sb.toString();
    }
}

RunEditDistance.java

/*
 * [Usage]
 * $ java RunEditDistance saka ara
 */
import java.util.*;
public class RunEditDistance {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String s,t;
	if (args.length > 0) s=args[0];
	else { System.out.print("s="); s = sc.next();}
	if (args.length > 1) t=args[1];
	else { System.out.print("t="); t = sc.next();}
	
	EditDistance ed = new EditDistance(s,t);
	System.out.println(ed.solve());
	System.out.println(ed.showCostTable());
	System.out.println(ed.showOpTable());
	String[] a = ed.getPath();
	for (int i=0; i<a.length; i++)
	    System.out.println(a[i]);
    }
}

RunEditDistance.javaの実行例

$ javac RunEditDistance.java EditDistance.java
$ java RunEditDistance "saka" "ara"
2
 |     a  r  a
-+------------
 |  0  1  2  3 
s|  1  1  2  3 
a|  2  1  2  2 
k|  3  2  2  3 
a|  4  3  3  2 

 |     a  r  a
-+------------
 |  0  4  4  4 
s|  8  2  6  6 
a|  8  1  6  1 
k|  8  8  2 14 
a|  8  9 10  1 

delete 's'
matches 'a' and 'a'
substitute 'k' by 'r'
matches 'a' and 'a'

$ java RunEditDistance "apple is good" "applet is god"
2
 |     a  p  p  l  e  t     i  s     g  o  d
-+------------------------------------------
 |  0  1  2  3  4  5  6  7  8  9 10 11 12 13 
a|  1  0  1  2  3  4  5  6  7  8  9 10 11 12 
p|  2  1  0  1  2  3  4  5  6  7  8  9 10 11 
p|  3  2  1  0  1  2  3  4  5  6  7  8  9 10 
l|  4  3  2  1  0  1  2  3  4  5  6  7  8  9 
e|  5  4  3  2  1  0  1  2  3  4  5  6  7  8 
 |  6  5  4  3  2  1  1  1  2  3  4  5  6  7 
i|  7  6  5  4  3  2  2  2  1  2  3  4  5  6 
s|  8  7  6  5  4  3  3  3  2  1  2  3  4  5 
 |  9  8  7  6  5  4  4  3  3  2  1  2  3  4 
g| 10  9  8  7  6  5  5  4  4  3  2  1  2  3 
o| 11 10  9  8  7  6  6  5  5  4  3  2  1  2 
o| 12 11 10  9  8  7  7  6  6  5  4  3  2  2 
d| 13 12 11 10  9  8  8  7  7  6  5  4  3  2 

 |     a  p  p  l  e  t     i  s     g  o  d
-+------------------------------------------
 |  0  4  4  4  4  4  4  4  4  4  4  4  4  4 
a|  8  1  4  4  4  4  4  4  4  4  4  4  4  4 
p|  8  8  1  5  4  4  4  4  4  4  4  4  4  4 
p|  8  8  9  1  4  4  4  4  4  4  4  4  4  4 
l|  8  8  8  8  1  4  4  4  4  4  4  4  4  4 
e|  8  8  8  8  8  1  4  4  4  4  4  4  4  4 
 |  8  8  8  8  8  8  2  1  4  4  5  4  4  4 
i|  8  8  8  8  8  8 10 10  1  4  4  4  4  4 
s|  8  8  8  8  8  8 10 10  8  1  4  4  4  4 
 |  8  8  8  8  8  8 10  1  8  8  1  4  4  4 
g|  8  8  8  8  8  8 10  8 10  8  8  1  4  4 
o|  8  8  8  8  8  8 10  8 10  8  8  8  1  4 
o|  8  8  8  8  8  8 10  8 10  8  8  8  9  2 
d|  8  8  8  8  8  8 10  8 10  8  8  8  8  1 

matches 'a' and 'a'
matches 'p' and 'p'
matches 'p' and 'p'
matches 'l' and 'l'
matches 'e' and 'e'
insert 't'
matches ' ' and ' '
matches 'i' and 'i'
matches 's' and 's'
matches ' ' and ' '
matches 'g' and 'g'
delete 'o'
matches 'o' and 'o'
matches 'd' and 'd'

$ java RunEditDistance "thou shalt not" "you should not"
5
 |     y  o  u     s  h  o  u  l  d     n  o  t
-+---------------------------------------------
 |  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 
t|  1  1  2  3  4  5  6  7  8  9 10 11 12 13 13 
h|  2  2  2  3  4  5  5  6  7  8  9 10 11 12 13 
o|  3  3  2  3  4  5  6  5  6  7  8  9 10 11 12 
u|  4  4  3  2  3  4  5  6  5  6  7  8  9 10 11 
 |  5  5  4  3  2  3  4  5  6  6  7  7  8  9 10 
s|  6  6  5  4  3  2  3  4  5  6  7  8  8  9 10 
h|  7  7  6  5  4  3  2  3  4  5  6  7  8  9 10 
a|  8  8  7  6  5  4  3  3  4  5  6  7  8  9 10 
l|  9  9  8  7  6  5  4  4  4  4  5  6  7  8  9 
t| 10 10  9  8  7  6  5  5  5  5  5  6  7  8  8 
 | 11 11 10  9  8  7  6  6  6  6  6  5  6  7  8 
n| 12 12 11 10  9  8  7  7  7  7  7  6  5  6  7 
o| 13 13 12 11 10  9  8  7  8  8  8  7  6  5  6 
t| 14 14 13 12 11 10  9  8  8  9  9  8  7  6  5 

 |     y  o  u     s  h  o  u  l  d     n  o  t
-+---------------------------------------------
 |  0  4  4  4  4  4  4  4  4  4  4  4  4  4  4 
t|  8  2  6  6  6  6  6  6  6  6  6  6  6  6  1 
h|  8 10  2  6  6  6  1  4  4  4  4  4  4  4  4 
o|  8 10  1  6  6  6 14  1  4  4  4  4  4  5  4 
u|  8 10  8  1  4  4  4 12  1  4  4  4  4  4  4 
 |  8 10  8  8  1  4  4  4 12  2  6  1  4  4  4 
s|  8 10  8  8  8  1  4  4  4  4  6 14  2  6  6 
h|  8 10  8  8  8  8  1  4  4  4  4  4  4  6  6 
a|  8 10  8  8  8  8  8  2  6  6  6  6  6  6  6 
l|  8 10  8  8  8  8  8 10  2  1  4  4  4  4  4 
t|  8 10  8  8  8  8  8 10 10 10  2  6  6  6  1 
 |  8 10  8  8  9  8  8 10 10 10 10  1  4  4  4 
n|  8 10  8  8  8  8  8 10 10 10 10  8  1  4  4 
o|  8 10  9  8  8  8  8  1 14 10 10  8  8  1  4 
t|  8 10  8  8  8  8  8  8  2 14 10  8  8  8  1 

delete 't'
substitute 'h' by 'y'
matches 'o' and 'o'
matches 'u' and 'u'
matches ' ' and ' '
matches 's' and 's'
matches 'h' and 'h'
insert 'o'
substitute 'a' by 'u'
matches 'l' and 'l'
substitute 't' by 'd'
matches ' ' and ' '
matches 'n' and 'n'
matches 'o' and 'o'
matches 't' and 't'

Exercise

Exercise a

Submission File	EditDistance.java
Comment:	Minimum cost of editing the original string "sushi and wine belong to food" to the target string "sun shines and window blows, good"
Submit to:

Assume that the cost of SUBSTITUTE, INSERT, DELETE and MATCH operations are $1$, $1$, $1$, $0$, respectively. Find the minimum cost to edit from the original string "sushi and wine belong to food" to the target string "sun shines and window blows, good".

Exercise b

NearWord.java

Comment:

Note that the input dataset is different for each student. The input dataset is assigned by the result of modulo 3 of the last digit of the student number. Paste the output of the program for each input data. (Paste the 7 execution result).

Group 0	Group 1	Group 2
abcense explasion foorin irerebant nowlege rigitemite newclear	akcept exagelat forine embaras misaile gaard okacionally	colligion forhedd riblaly haight hipoksicy laiing brouchere

Submit to:

Write a program that points out typos in English and suggests correct words. However, it must meet the following specifications.

User input should be one line. You can include whitespace characters in the input
Use mwords_74550common.txt as a dictionary.
To find the "line in the dictionary" that has the minimum edit distance to the input
The first line of the output is the mininum edit distance. The second and subsequent lines should be "the dictinary line with the minimum edit distance".
If there are multiple solutions, list all solutions, on per line.
SUBSTITUTE, INSERT, DELETE of MATCH cost are $1$, $1$, $1$ and $0$, respectively.

The contents of "mwords_74550common.txt" are take from the list of 74550 words including in several dictionaries which is available from Grady Ward's Moby Project http://icon.shef.ac.uk/Moby/mwords.html .

Part of "mwords_74550common.txt"

...(omitted)...
alow
alp
alpaca
alpenglow
alpenhorn
alpenstock
alpestrine
alpha
alpha and omega
alpha decay
...(omitted)...

NearWord.java

import java.util.*;
import java.io.*;

public class NearWord {
    private Vector<String> dic;
    private int minCost;
    public NearWord(String fname) {
	try {
	    Scanner sc = new Scanner(new File(fname));
	    dic = new Vector<String>();
	    while (sc.hasNext())
		dic.add(sc.nextLine());
	} catch (Exception e) {
	    e.printStackTrace();
	    System.exit(-1);
	}
    }
    public int cost() { return minCost; }
    public Vector<String> find(String s) {
	minCost = Integer.MAX_VALUE;

	// [Exercise] Write the appropriate code hear.

    }
    public static void main(String[] args) {
	NearWord nw = new NearWord("mwords_74550common.txt");
	Scanner sc = new Scanner(System.in);
	String s = sc.nextLine();
	Vector<String> words = nw.find(s);
	System.out.println(nw.cost());
	for (String w: words)
	    System.out.println(w);
    }
}

Execution log of NearWord.java

$ javac NearWord.java 
$ java NearWord 
Amanda's applet 
5
Adam's apple
$ java NearWord 
womin 
1
woman
women
$ java NearWord 
thiatar 
2
theater
$ java NearWord 
the Internet 
6
eterne
herb bennet
interne
internee
phenanthrene
tenter
theater
theatre

Yoshihisa Nitta

http://karel.tsuda.ac.jp/

		a	r	a
	\|saka	a\|saka	ar\|saka	ara\|saka
s	\|aka	a\|aka	ar\|aka	ara\|aka
a	\|ka	a\|ka	ar\|ka	ara\|ka
k	\|a	a\|a	ar\|a	ara\|a
a	\|	a\|	ar\|	ara\|