8

我正在为 iOS 应用程序实现一种自动完成功能。我用于自动完成值的数据是一个逗号分隔的文本文件，包含大约 100,000 个字符串。这就是我现在正在做的事情：

  1. 阅读文本文件，并创建一个NSArray100,000 NSString。
  2. 当用户键入时，执行[array containsObject:text]

当然有更好/更快的方法来进行此查找。有什么想法吗？

4

2 回答 2

20

绝对有！但它不是“在 Objective-C 中”：很可能，您需要自己编写代码。

这个想法是将您的字符串列表转换为后缀树，这是一种可以让您非常快速地按前缀搜索的数据结构。在后缀树中搜索可能的补全非常快，但结构本身并不容易构建。在 Internet 上进行的快速搜索显示，在 Objective C 中没有现成的实现，但您可以移植 另一种语言的实现，使用 C 实现，或者如果您不是特别紧迫，甚至可以编写自己的实现。

也许更简单的方法是按字母顺序对字符串进行排序，并对到目前为止输入的前缀运行二进制搜索。尽管不如后缀树高效，但排序数组方法对于 100K 字符串来说是可以接受的，因为您在 17 次检查中就找到了正确的位置。

于 2012-07-20T20:42:34.573 回答
2

最简单的可能是二进制搜索。见-[NSArray indexOfObject:inSortedRange:options:usingComparator:]。

特别是，我会尝试这样的事情：

  • 对保存到文件的数组进行预排序
  • 当您加载数组时，可能@selector(compare:)（如果您担心它会意外地未排序或 Unicode 排序顺序会因某些边缘情况而改变）。假设数组大部分已经排序，这应该大约是 O(n)。
  • 为了找到第一个潜在的匹配，[array indexOfObject:searchString inSortedRange:(NSRange){0,[array count]} options:NSBinarySearchingInsertionIndex|NSBinarySearchingFirstEqual usingComparator:@selector(compare:)]
  • 遍历数组，直到条目不再包含 searchString 作为前缀。您可能想要进行大小写/变音符号/宽度不敏感比较以确定它是否是前缀 (NSAnchoredSearch|NSCaseInsensitiveSearch|NSDiacriticInsensitiveSearch|NSWidthInsensitiveSearch)

这可能无法“正确”处理所有语言环境（尤其是土耳其语），但也不会替换compare:为localizedCompare:，也不会天真的字符串折叠。（它只有 9 行长，但花了大约一天的工作时间才弄好，大约有 40 行代码和 200 行测试，所以我可能不应该在这里分享。）

于 2012-07-20T20:59:14.747 回答