2
\$\begingroup\$

I'm working on an implementation of a Wagner-Fischer-Algorithm for an online programming challenge site, but I can't seem to push the time down to where it needs to be. The assignment is to, for a number of different 'misspelled' words \$w_1, w_2, \dots , w_n\$ and a dictionary \$D\$ compute the editing distances between all words \$w_i\$ and all words \$di\$ in the dictionary and, for every \$w_i\$, output the word(s) in the dictionary with the smallest editing distance from \$w_i\$.

At the moment this is how I've implemented my algorithm:

main():
  minDistance = 1000 // arbitrary large number
  Let D be the dictionary
  Let W be the set of words that needs ‘correcting’
  For every w in W:
    For every d in D:
      dist = distance(w, d)
      if dist < minDistance:
        minDistance = dist
        Make a linked list minList and add d to it
      if dist == minDistance:
        Add d to minList
    Output minDistance aswell as minList 

distance(w, d):
  Make a matrix M with dimensions (m,n)
  If the last d and this d has any p (start)-letters in common => use M(m, p) from last computation (no need to compute it again) 
  Fill the first row and the first column with their respective ‘index’ //Look at table on Wiki
  For col = 1 to m:
    For row = p to n:
      wagner-fischer(w, d, col, row)

wagner-fischer(w, d, col, row):
  res = M(col-1, row-1) + (1 if w have the same letter at index col-1 as d at row-1)
  addLetter = M(col-1, row) + 1
  deleteLetter = M(col, row-1) + 1
  if addLetter < res:
    res = addLetter
  if deleteLetter < res:
    res = deleteLetter
  return res

Does anyone have any tips on how to optimize my implementation further? I'm really struggling at this point and I don't really know how to improve it further. I've done it in Java if that's of any importance.

Here is my Java code. Don't mind the one-letter variables and stuff. I will refactor for readability but can't right now.

import java.util.LinkedList;
import java.util.List;
import java.util.Arrays;
import java.lang.Math;

public class ClosestWords {
  public LinkedList<String> closestWords = null;

  public int closestDistance = 16;
  String lastWord = "#";
  int[][] M;

  static int partDist(String w1, String w2, int x, int y, int[][] M) {

    int res = M[x-1][y-1] + (w1.charAt(x - 1) == w2.charAt(y - 1) ? 0 : 1);
    int addLetter = M[x-1][y] + 1;
    int deleteLetter = M[x][y-1] + 1;
    if (addLetter < res) {
      res = addLetter;
    } if (deleteLetter < res) {
      res = deleteLetter;
    }
    return res;
  }

  public int Distance(String w1, String w2, int matchDist) {
    int x = w1.length();
    int y = w2.length();

    if (matchDist > 0) {
      M = copyMatrix(M, y+1);
    } else {
      M = new int [x+1][y+1];
      for (int i = 0; i <= x; i++) {
        M[i][0] = i;
      }
    }

    for (int i = matchDist+1; i <= y; i++) {
      M[0][i] = i;
    }

    for (int i = 1; i <= x; i++) {
      for (int j = matchDist+1; j <= y; j++) {
        if (w1.charAt(i-1) == w2.charAt(j-1)) {
          M[i][j] = M[i-1][j-1];
        } else {
          M[i][j] = partDist(w1, w2, i, j, M);
        }
      }
    }
    return M[x][y];
  }

  public ClosestWords(String w, List<String> wordList) {
    for (String s : wordList) {
      int matchDist = matchDistance(s, lastWord);
      int dist = Distance(w, s, matchDist);
      if (dist < closestDistance) {
        closestDistance = dist;
        closestWords = new LinkedList<String>();
        closestWords.add(s);
      }
      else if (dist == closestDistance)
        closestWords.add(s);
      lastWord = s;
    }
  }

  static int matchDistance (String w1, String w2) {
    int w1len = w1.length();
    int w2len = w2.length();

    int matchDist = 0;
    while (matchDist < Math.min(w1len, w2len) && (w1.charAt(matchDist) == (w2.charAt(matchDist)))) {
      matchDist++;
    }
    return matchDist;
  }

  public static int[][] copyMatrix(int[][] original, int newDimY) {
    if (newDimY == original[1].length) {
      return original;
    }
    final int[][] result = new int[original.length][newDimY];
    for (int i = 0; i < original.length; i++) {
      for (int j = 0; j < Math.min(original[0].length, newDimY); j++) {
        result[i][j] = original[i][j];
      }
    }
    return result;
  }

  public static void printMatrix (int[][] matrix) {
    int x = matrix.length;
    int y = matrix[0].length;
    for (int i = 0; i < x; i++) {
      for (int j = 0; j < y; j++) {
        System.out.print(Integer.toString(matrix[i][j]) + " ");
      } System.out.print("\n");
    }
  }

  int getMinDistance() {
    return closestDistance;
  }

  List<String> getClosestWords() {
    return closestWords;
  }

  /*public static void main(String args[]) {
    int[][] oneArray = new int[5][5];
  }*/
}

The main() method is in another class but it's basically just reading from the standard input stream and creating an object of ClosestWords with the misspelled word and a list containing the dictionary words.

\$\endgroup\$
5
  • \$\begingroup\$ Does the challenge really require you to calculate the distances between all candidate and dictionary words? Doesn't it just ask for the best match(es)? Please provide a link to the challenge. \$\endgroup\$
    – Rainer P.
    Jan 31, 2017 at 17:57
  • \$\begingroup\$ @Rainer P - Yea, it asks for the best matches solely. How can I use that though? Thanks for answering \$\endgroup\$ Jan 31, 2017 at 19:51
  • \$\begingroup\$ An answer to this question is not really a code review anymore, since it requires development of an algorithm to replace you brute force solution, which is the whole point of the challenge. See this meta post on questions like yours. I can, however, give you some hints: preprocess the dictionary in a way that queries against it become cheap; lower bounds to the edit distance can be calculated from the length or from a prefix of a string; the A* algorithm requires a lower-bound-heuristic. \$\endgroup\$
    – Rainer P.
    Feb 4, 2017 at 11:59
  • \$\begingroup\$ @NyfikenGul my advice is to find out where the program is actually stalling. it turns out that the vast majority of the time eaten up is in some small routine associated with the program. once you identify where the time is going, then you can work solidly on optimizing the problem \$\endgroup\$
    – BenKoshy
    Jun 7, 2017 at 5:41
  • \$\begingroup\$ You don't need to keep the whole M matrix. You need only one item of the current row and two items of the previous row to compute a new item, so at any time it's enough to keep just the current row and the previous row in memory. \$\endgroup\$
    – CiaPan
    Sep 4, 2017 at 20:19

1 Answer 1

1
\$\begingroup\$

You should use System.arraycopy or Arrays.copyOf to copy the matrix, it uses a compiler instrinsic and should be faster.

As a minor thing: "lastWord" should not be a field - it is used exclusively in one method. Limit its scope.

Using a List of words instead of a Set of words can cause you to calculate the distance between the same words multiple times. imagine this list: [hello, world, hello, world]. You would make three comparisons of the same result, while a set would only yield one comparison.

 public int Distance(..

This tricked me into thinking it was a constructor for quite some time, until I spotted the return value declaration. Always start a method name in lower caps, like so:

 public int distance(...

and the field name "M" should be lower case too.

for (int i = 0; i <= x; i++) {
    M[i][0] = i;
 }

You might like to take a look at the method Arrays.parallelSetAll or at Java 8's Stream-API, like Arrays.stream(array).parallel().forEach(..).

You might find a speedup there.

Kind regards.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.