iOS中的全文子字符串搜索

Question

对于记录中包含的任何子字符串,我需要我的iPhone/iPad应用程序能够快速搜索大约10,000条记录(大约一段文本,每条记录).因此,如果记录包含单词"Flame",则查询"lame"应该匹配.

我目前正在使用SQLite,但"LIKE%term%"搜索对于这么多记录来说太慢了.启用全文搜索似乎不能完全满足我的需求,因为SQLite只支持前缀通配符(例如"Flam*",而不是"*lame").

我已经尝试使用一个巨大的文本blob(~350K),并做[NSString rangeOfString:...],我认为它使用Boyer-Moore算法.这比"LIKE%term%"搜索更快,但仍然不是我希望的那种速度.

对于实现这种可扩展子字符串搜索的方法或库的任何建议,哪些可以在iPhone上运行？

Answer 1

这里有许多不同的选项。我不知道每个的基准，所以你必须做一些测试。

首先是 SQLite 的 FTS3 扩展。这应该为您提供快速的索引全文搜索： http://regularrateandrhythm.com/regular-rate-rhythm-blog/sqlite3-fts-in-IOS4.html

那么，iOS 4 中引入的正则表达式怎么样：
http://developer.apple.com/library/ios/#documentation/Foundation/Reference/NSRegularExpression_Class/Reference/Reference.html

对于 iOS 4 之前的版本，您可以使用 RegexKitLite：
http://regexkit.sourceforge.net/RegexKitLite/index.html

如果您决定使用正则表达式，请查看此条目以了解如何优化它们：
如何使用 NSRegularExpression 加速 iPhone 正则表达式？