Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I'm trying to find a 'similar' name to every item in a list

 nearName[name_, namesList_] := 
   Module[{lista, pos},
     lista = EditDistance[ToLowerCase[name], ToLowerCase[ToString[#]]] & /@ (namesList);
     pos = Flatten[Position[lista, Min[lista]]];
     If[Length[pos] > 1 || Min[lista] > 3 , Missing["NotAvailable"], namesList[[pos]]]]

The problem is that with a very large input (nameList contains about 400k items and I make about 1k calls to nearName), nearName is using a lot of CPU. Is there any way I can make this faster?

share|improve this question
    
I think it would certainly help if you did ToLowerCase[ToString[#]] & /@ namesList just once before any calls your nearName function. –  m_goldberg Jun 6 at 0:13

2 Answers 2

up vote 4 down vote accepted

I'd think this more efficient:

names = {"rob", "joe", "jack"};

find = Module[{nf = Nearest[#2], res},
              If[EditDistance[#, res = First@nf[#]] <= 3,res, Missing["NotAvailable"]]] &;

find["boc", names]
find["franny", names]

(*
"rob"
Missing["NotAvailable"]
*)

Do Lowercase conversion if case matters, and if you plan on many repeated look-ups, probably best to generate the nearest function nf once and re-use it.

Re-reading your OP, I think this better fits the question (based on my interpretation of the code):

find = Module[{nf = Nearest[#2], res},
              If[EditDistance[#, First@(res = nf[#])] <= 3 && (Length@res == 1 || 
                 EditDistance[#, res[[1]]] != EditDistance[#, res[[2]]]), 
                 First@res, Missing["NotAvailable"]]] &
share|improve this answer

EditDistance is an expensive computation ( O(longestStringLength + distance^2) ), so it is helpful to do whatever you can to eliminate candidates before you use it. The idea here is to minimize the distance^2 contribution to your overall testing time. You can start by filtering on StringLength, to within +/- x characters of your test string since that is implicit. If that shrinks the list sufficiently, then do your EditDistance, but if the list is still very large you could also do a second pass and check whether the number of mismatching Characters is within tolerance; this isn't free (computationally), so whether this would be worth it will depend on how much you can shave off the list with StringLength. Nearest uses EditDistance for strings, so it could be used to tidy up your code a bit but it will still be slow if you run it on a very large list. However, querying with Nearest (as rasher noted) will be faster than applying EditDistance to the whole list first. EditDistance also has an IgnoreCase option which is cheaper than making separate calls to ToLowerCase, but in any case ToLowerCase is Listable so you should take advantage of that if you use it.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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