So 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 w1, w2, ... , wn and a dictionary D compute the editing distances between all words wi and all words di in the dictionary and, for every wi, output the word(s) in the dictionary with the smallest editing distance from wi.
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.
EDIT: The online challenge says as follows;
"The input consists of two parts, the first being the dictionary (max 500 000 words) and the second being the words to be corrected (max 100 words). Each word can be max 40 characters long."