Well, you will obviously not use the levenshtein distance algo as it is. After cutting down the search space using some hash table based approximations and using lazy evaluation it is known to be done in O (m (1+d)), where m = length of string and d = maximum levenshtein distance, which IMO is as close enough to linear time as you can get (for such a problem) :)
On Sun, Aug 23, 2009 at 6:18 PM, Amit Saha<lists.amitsaha at gmail.com> wrote: > Angad Singh wrote: >> >> On Sun, Aug 23, 2009 at 12:55 PM, Amit Saha<lists.amitsaha at gmail.com> >> wrote: >>> >>> Angad Singh wrote: >>> <snip> >>> >>>> Completely unrelated: how about adding "Did you mean" kind of >>>> suggestions. User tries - "spkg install openoffce". Instead of the >>>> usual, package not found, spkg could output a possible list of >>>> suggestions - Did you mean openoffice? This can be implemented using >>>> the Levenshtein word distance algorithm >>>> (http://en.wikipedia.org/wiki/Levenshtein_distance). For invalid >>>> names, just calculate the levenshtein distance of the input package >>>> name with a list of all the packages and show few of the closest >>>> matches. >>> >>> IMMHO, would that not cause "some" substantial delay, considering the >>> fact >>> that number of packages are usually high? Don't flame if you have already >>> worked on that :) >> >> No it would not :) > > Now, I am curious- Is it O(1)? :) > > -Amit >> > > > -- > Journal: http://amitksaha.wordpress.com > ?-blog: http://twitter.com/amitsaha > IRC: cornucopic on #scheme, #lisp, #math, #linux > -- Angad Singh http://angadsingh.in
