Wes*_*ley 7 search cocoa fuzzy-search objective-c levenshtein-distance
有没有人知道Objective-c的模糊搜索匹配的快速实现？(levenshtein距离算法).
我发现了这个:https://github.com/thetron/StringScore/blob/master/NSString%2BScore.m - 但不幸的是它很慢.我需要将它与大约200个字符串进行比较,并且它是连续的 - 每次键入新键击.
有任何想法吗？
w-m*_*w-m 10
如果NSString + Score做你想要的但速度太慢,你可以从加速它开始.第23到28行-scoreAgainst:fuzziness:options:是设置代码,只需要进行一次,而不是每次进行200次比较.因此,将该代码拉入设置方法并再次测量.
编辑:
作为练习,我分叉了StringScore,提取了设置代码并进行了微小的更改以获得一些性能改进,然后对其进行测量.我使用了1000个随机单词,每个单词分为三个(例如"disrupted dot drinking").对于这些组中的每一组,我进行了设置(如本原始答案中所述),然后将字符串与所有1000组进行比较.我的Core 2 Duo大约需要11秒.
因此,将一个字与1000比较大约需要11毫秒.现在你只需要1到200,所以它可能不到10毫秒.这对你有用吗？
(顺便说一句,将近一半的时间仍然花在rangeOfString上:找到一个单个字符;这可能要快得多,但我不想深入了解算法的细节.)