有谁知道Objective-c模糊搜索匹配的快速实现？（levenshtein-距离算法）。
我发现了这个：https ://github.com/thetron/StringScore/blob/master/NSString%2BScore.m - 但不幸的是它很慢。我需要将其与大约 200 个字符串进行比较，并且它是连续的——每次键入新的击键。
有任何想法吗？
user429620
问问题
4565 次
2 回答
10
如果 NSString+Score 可以满足您的要求，但速度太慢，您可以从加快速度开始。第 23 到 28 行-scoreAgainst:fuzziness:options:是设置代码，只需要执行一次，而不是每次 200 次比较。因此，将该代码提取到设置方法中并再次测量。
编辑：
作为一个练习，我分叉了 StringScore，提取了设置代码并进行了最小的更改以获得一些性能改进，然后对其进行了测量。我使用了 1000 个随机单词，将它们分成三组（例如“打断点饮酒”）。对于这些组中的每一个，我都进行了设置（如原始答案中所述），然后将字符串与所有 1000 个组进行比较。这在我的 Core 2 Duo 上大约需要 11 秒。
因此，将一个单词与 1000 个单词进行比较大约需要 11 毫秒。现在您只需要 1 到 200 个，因此它可能会远低于 10 毫秒。那应该对你有用吗？
（顺便说一句，近一半的时间仍然花在 rangeOfString 上：查找单个字符；这可能会做得更快，但我不想了解算法的细节。）
于 2013-02-21T23:48:33.060 回答
2
我不知道您指的是在 Objective-C 中实现的算法
您是否有理由不将 NSPredicate 的内置功能与 CoreData 一起使用。我发现搜索 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" }
于 2013-02-21T22:57:22.970 回答