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

Question

有没有人知道Objective-c中模糊搜索匹配的快速实现方法？（利用Levenshtein距离算法）

我找到了这个：https://github.com/thetron/StringScore/blob/master/NSString%2BScore.m，但是它非常慢。我需要将其与大约200个字符串进行比较，并且是连续的——每次键入新字符都要进行比较。

有什么想法吗？

- user429620

Answer 1

如果NSString + Score可以满足您的需求，但速度太慢，您可以开始加速它。在-scoreAgainst：fuzziness：options：中的第23到28行是设置代码，只需要执行一次，而不是每个200个比较都要执行。因此，将该代码提取到设置方法中并重新测量。

编辑:

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

因此，将一个单词与1000个单词进行比较大约需要11毫秒。现在您只需要1到200，所以它可能会远远低于10毫秒。那应该适合你吧？

（顺便说一句，几乎一半的时间仍然花费在rangeOfString：查找单个字符上；这可能可以做得更快，但我不想涉及算法的细节。）

- w-m

---

谢谢，这确实有所改善，但仍然太慢了。 - user429620

@Wesley，我很惊讶你觉得它太慢了，所以我对其进行了测量。请查看帖子的编辑。 - w-m

很抱歉要说，但你是对的。我有另一个观察者也在同一时间被触发，这就是罪魁祸首。尽管如此，你的优化是值得的。谢谢！ - user429620

@w.m 感谢你的提示！你想在那个更改上开一个拉取请求，这样我就可以将其合并到主分支中吗？端口转换非常快，但性能方面并没有进行仔细测量，我很想得到一些更新。 - theTRON

@w-m 你有空吗？ :) - Galip

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/archive/documentation/Cocoa/Conceptual/Predicates/Articles/pSyntax.html

- Mindeater

---

谢谢，由于模糊匹配太慢了，我正在寻找一些可以找到包含所有单词的匹配项的东西。因此，如果我正在寻找“Stack Overflow”，匹配的对象将是“Stack Overflow”和“Overflow Stack”。我想，如果我拆开所有单词并分别尝试每个单词，这可以通过NSPredicate实现。我会尝试一下。 - user429620

@Wesley 但那只是[NSSet setWithArray：[string componentsSeparatedByString:@" "] isEqual:otherSet]。 - w-m

@w.m 嗯，不完全是，它还应该匹配“Overflow match stack”等。无论如何，看起来我必须对每个单词进行正则表达式搜索或谓词搜索。 - user429620

你可以使用谓词进行一些相当强大的匹配。这里有一个来自实际代码的例子，NSPredicate * mechPredicate = [NSPredicate predicateWithFormat:@"id CONTAINS[cd] %@ || product.brand.heading CONTAINS[cd] %@ || product.category.name CONTAINS[cd] %@ && count = 1"，searchText，searchText，searchText]; - Mindeater