Objective-c:快速模糊搜索匹配

Question

有没有人知道Objective-c模糊搜索匹配的快速实现？(levenshtein-distance算法)。

我发现了这个：https://github.com/thetron/StringScore/blob/master/NSString%2BScore.m --但不幸的是它太慢了。我需要将它与大约200个字符串进行比较，而且它是连续的-每次新键入的按键。

有什么想法吗？

Answer 1

如果NSString+Score做了你想做的，但是太慢了，你可以从加速开始。-scoreAgainst:fuzziness:options:中的第23到28行是设置代码，只需执行一次，而不是每次执行200次比较。因此，将代码提取到一个设置方法中，并再次进行测量。

编辑：

作为练习，我使用forked StringScore，提取了设置代码，并进行了最小程度的更改以获得一些性能改进，然后对其进行了测量。我随机使用了1000个单词，将它们分成三个(例如“中断的点饮酒”)。对于这些组中的每一个，我都进行了设置(如这个原始答案中所述)，然后将字符串与所有1000个组进行比较。在我的Core 2 Duo上，这大约需要11秒。

因此，将一个单词与1000个单词进行比较大约需要11毫秒。现在您只需要1到200，所以它很可能在10毫秒以下。这对你来说应该没问题吧？

(顺便说一句，几乎一半的时间仍然花在rangeOfString上:查找单个字符；这可能会快得多，但我不想了解算法的细节。)

Answer 2

我不知道你提到的用Objective-C实现的算法

您没有在CoreData中使用NSPredicate的内置功能有什么原因吗？我发现这个搜索速度非常快，搜索了200多个字符串。

例如，给定一个NSString *searchText和一个fetchedResultsController

NSPredicate * predicate = [NSPredicate predicateWithFormat:@"name CONTAINS[cd] %@", searchText];

self.filteredListContents = [[[self fetchedResultsController] fetchedObjects] filteredArrayUsingPredicate:predicate];

您也可以在NSArray上使用NSPredicate，我假设您已经尝试过，但发现它太慢了。

来自苹果文档

NSMutableArray *array =
[NSMutableArray arrayWithObjects:@"Nick", @"Ben", @"Adam", @"Melissa", nil];

NSPredicate *bPredicate = [NSPredicate predicateWithFormat:@"SELF beginswith[c] 'a'"];

NSArray *beginWithB = [array filteredArrayUsingPredicate:bPredicate];
// beginWithB contains { @"Adam" }.

NSPredicate *sPredicate = [NSPredicate predicateWithFormat:@"SELF contains[c] 'e'"];

[array filterUsingPredicate:sPredicate];
// array now contains { @"Nick", @"Ben", @"Melissa" }

https://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/Predicates/Articles/pSyntax.html