1
$\begingroup$

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."

$\endgroup$
  • $\begingroup$ Have you considered other algorithms, apart from running Wagner-Fischer on all pairs w,d? There's lots written on edit distance and spelling correction; search this site and elsewhere to find many resources and algorithms and data structures. Also, if this is a practical problem, I suggest you edit the question to characterize your problem more clearly: what is the typical size of D, typical value of n, and typical values for the edit distance (including how many words are at edit distance 0 from some word in D; at edit distance 1 from some word in D)? $\endgroup$ – D.W. Feb 1 '17 at 23:32
  • $\begingroup$ Finally, it might be nice to credit the source of the problem by linking to the problem on the programming contest site. $\endgroup$ – D.W. Feb 1 '17 at 23:33
  • $\begingroup$ I'm afraid the task specifically asks for Wagner-Fischer.. Right, I will add that information to my post! And sorry for not posting the site, but it's exclusive to my university. I can post the description though!Thanks for your answer. $\endgroup$ – Nyfiken Gul Feb 2 '17 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.