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

有谁知道Objective-c的模糊搜索匹配的快速实现吗？（levenshtein-distance算法）。Objective-c：快速模糊搜索匹配

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

任何想法？

来源

2013-02-21 Wesley

如果NSString的+分数，你想要做什么，但速度太慢，你可以通过加速它开始。 -scoreAgainst:fuzziness:options:中的第23至28行是设置代码，只需执行一次，而不是每次进行200次比较。因此，将该代码拉出到设置方法中并再次测量。

编辑：

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

因此，比较一个单词到1000大约需要11毫秒。现在你只需要1到200个，所以它可能会低于10毫秒。这应该适合你吗？

（顺便说一句，将近一半的时间花在仍然在rangeOfString：找到一个字符，这大概可以做了很多更快，但我不想在算法的细节来获得。）

来源

2013-02-21 23:48:33

谢谢，这确实可以大大改善它，但它仍然太慢。 – Wesley 2013-02-22 07:36:32

@韦斯利它让我感到它对你来说太慢了，所以我测量了它。请参阅修改帖子。 – 2013-02-22 11:15:54

我很抱歉地说，但你是对的。我还有另一位观察者，同时也是被触发的罪魁祸首。尽管如此，你的优化是值得的。谢谢！ – Wesley 2013-02-23 09:15:12

我不知道你在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

来源

2013-02-21 22:57:22 Mindeater

谢谢，由于模糊匹配太慢，我正在寻找可以找到包含所有单词的匹配项的内容。所以，如果我正在寻找“堆栈溢出”，匹配的对象将是“堆栈溢出”和“溢出堆栈”。我想这可以用NSPredicate来完成，如果我分开所有单词并单独为每个单词尝试它。我会试一试。 – Wesley 2013-02-22 07:13:20

@韦斯利，但这只是[NSSet setWithArray：[string componentsSeparatedByString：@“”] isEqual：otherSet] – 2013-02-22 09:07:20

@wm嗯，不完全是，它也应该匹配“溢出匹配堆栈”等。无论如何，看起来像我有对每个单词执行正则表达式搜索或对每个单词执行谓词搜索。 – Wesley 2013-02-22 09:23:40

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

回答

相关问题