Out of Memory Exception when using Levenshtein Algorithm

[kaparapu madhu]

I am comparing two html files, using Levenshtein Algorithm. I am reading these two files in arraylist and giving as input to Levenshteing Algorithm. This algorithm uses Edit matrix for comparision with size m*n ( arrayList1.size() * arrayList2.size() ).
It is working good and efficient for small files, but for large file it throws out of memory exception. To overcome this we used -Xmx700000000. But the problem is, it takes lot of time to generate diffReport nearly 15 minutes and above. I am searching for a possible solution to reduce the time

[Geoffrey Falk]

You do not need to allocate a 2x2 array. It is possible to implement the Levenshtein algorithm using only 1-dimensional arrays.

Calculate the matrix one row at a time. You only need the previous row to determine the values in the next row.

Geoffrey

[Geoffrey Falk]

This uses JDK 1.5:

import java.util.Arrays;
 
/**
 * Demo of the Levenshtein algorithm. Computes the edit distance between two
 * strings.
 *
 *@author   gtf
 */
public class Levenshtein {
 
  private final static int DEFAULT_COST_INS = 1;
  private final static int DEFAULT_COST_DEL = 1;
  private final static int DEFAULT_COST_SUB = 1;
 
  private final int costIns;
  private final int costDel;
  private final int costSub;
 
  private final String str1;
  private final String str2;
 
  private final int n1, n2;
 
  private Integer result = null;
 
  /**
   * Constructor for the Levenshtein object
   *
   *@param str1  The initial string
   *@param str2  The target string
   */
  public Levenshtein(String str1, String str2) {
    this(str1, str2, DEFAULT_COST_INS, DEFAULT_COST_DEL, DEFAULT_COST_SUB);
  }
 
  /**
   * Constructor for the Levenshtein object
   *
   *@param str1     The source string
   *@param str2     The target string
   *@param costIns  The cost of inserting a character
   *@param costDel  The cost of deleting a character
   *@param costSub  The cost of substituting a character
   */
  public Levenshtein(String str1, String str2, int costIns, int costDel, int costSub) {
    this.str1 = str1;
    this.str2 = str2;
    n1 = str1.length();
    n2 = str2.length();
    this.costIns = costIns;
    this.costDel = costDel;
    this.costSub = costSub;
  }
 
  /**
   * Calculate the edit distance.
   */
  public int distance() {
    if (result != null) {
      return result;
    }
    int[] x = new int[n1 + 1];
    for (int i = 0; i <= n1; i++) {
      x[i] = i * costDel;
    }
    int[] y = new int[n1 + 1];
    for (int j = 1; j <= n2; j++) {
//    System.out.println(Arrays.toString(x));
      y[0] = j * costIns;
      for (int i = 1; i <= n1; i++) {
        int cost = ((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : costSub);
        y[i] = Util.min(x[i] + costIns, y[i - 1] + costDel, x[i - 1] + cost);
      }
      // swap the two working arrays
      int[] temp = x;
      x = y;
      y = temp;
    }
//  System.out.println(Arrays.toString(x));
    result = x[n1];
    return result;
  }
 
  /**
   * Displays a usage message.
   */
  private static void usage() {
    System.err.println("Usage: java Levenstein string1 string2 [insertCost deleteCost substCost]");
  }
 
  /**
   * Exercises the Levenshtein algorithm.
   *
   *@param args  The command line arguments
   */
  public static void main(String[] args) {
    if (args.length != 2 && args.length != 5) {
      usage();
      return;
    }
    String argStr1 = args[0];
    String argStr2 = args[1];
    Levenshtein engine;
    if (args.length == 2) {
      engine = new Levenshtein(argStr1, argStr2);
    } else {
      try {
        int argCostIns = Integer.parseInt(args[2]);
        int argCostDel = Integer.parseInt(args[3]);
        int argCostSub = Integer.parseInt(args[4]);
        engine = new Levenshtein(argStr1, argStr2, argCostIns, argCostDel, argCostSub);
      } catch (NumberFormatException e) {
        usage();
        return;
      }
    }
    System.out.println(engine.distance());
  }
}

public final class Util {
 
  private Util() {}
 
  public static int min(int x1, int x2) {
    return (x1 < x2 ? x1 : x2);
  }
 
  public static int min(int ... x) {
    if (x.length == 0) {
      throw new IllegalArgumentException("no arguments");
    }
 
    int v = x[0];
    for (int i = 1; i < x.length; i++) {
      if (x[i] < v) {
        v = x[i];
      }
    }
    return v;
  }
}

[ June 14, 2005: Message edited by: Geoffrey Falk ]