Author is Viterbi or Bellman.I didn't find anything about it in the Internet.
For example exists dictionary: mother, uncle, cat, dog. And you typed smth like
"maaather", as the result will be "maaather" -> mother.
This algorithm possible to use in spell checking,sound recognition etc.
Algorithm description will be later
Here is the source code:
/**
*
* This class is for finding coefficient of similarity of the two words
* using Viterbi(Bellman) algorithm
* @author Sergey
*/
public class Analyzer {
private double init[][];
private double result[][];
private int n;
private int m;
public void calculateASCIIDifference(String str1, String str2) {
n = str1.length();
m = str2.length();
init = new double[n][m];
for (int i = n - 1,i2 = 0; i >= 0; i--, i2++) {
for (int j = 0; j < m; j++) {
init[i2][j] = Math.abs((int) str1.charAt(i) - (int) str2.charAt(j));
}
}
}
public double[][] getASCIIDifference() {
return init;
}
public void setASCIIDifference(double[][] a,int n, int m) {
this.n = n;
this.m = m;
this.init = a;
}
// Calculate matrix by values from calculateASCIIDifference()
public void calculateSimilarity() {
result = new double[n][m];
double res, val1, val2, val3;
//initialize first element
result[n - 1][0] = init[n - 1][0];
//initialize first column
for (int i = n - 2; i >= 0; i--) {
result[i][0] = result[i + 1][0] + init[i][0];
}
//initialize first row(from down)
for (int j = 1; j < m; j++) {
result[n - 1][j] = result[n - 1][j - 1] + init[n - 1][j];
}
//initialize others
for (int i = n - 2; i >= 0; i--) {
for (int j = 1; j < m; j++) {
val1 = result[i][j - 1] + init[i][j];
val2 = result[i + 1][j] + init[i][j];
val3 = result[i + 1][j - 1] + (init[i][j] * 2);
//minimum of the 3 val's
res = val1 < val2 ? val1 : val2;
res = res < val3 ? res : val3;
result[i][j] = res;
}
}
}
//getting result of Similarity
public double getSimilarityValue() {
//need to devide if m != n
return result[0][m - 1] / (m + n);
}
// getting result array
public double[][] getSimilarityArray() {
return result;
}
}
//to test
public class Main {
public static void main(String[] args) {
double result1,results2;
Analyzer an = new Analyzer();
an.calculateASCIIDifference("mother","maaather");
an.calculateSimilarity();
result1 = an.getSimilarityValue();
an.calculateASCIIDifference("uncle","maaather");
an.calculateSimilarity();
result2 = an.getSimilarityValue();
//result1 will be less than result2
}
}
