IOS:SQLite。快速查找记录

Question

我正在构建一个拼字游戏，并且正在根据 wordDictionary 验证单词。

在我的第一次尝试中，我将字典加载到一个数组中并进行了二进制搜索以进行验证。

现在我改用了 sqlite，所以我不必将整个字典都放在内存中，也不必减少加载时间。

我有两个挑战:

1. 查询数据库以查看其中是否包含单词的最有效方法是什么？

2. 我如何找到一组字母的所有可能单词...当我在数组中有 wordDictionary 时，我可以循环遍历整个事物并验证每个单词。查询每一行(~700,000)并使用 sqlite 进行验证会非常慢。

Answer 1

“显而易见”的解决方案是建立一个索引。但是，如果您在内存中的二分查找不起作用，我不太确定索引是否能解决问题。它将占用大约相同数量的内存。

如果您可以搜索可能的匹配项，一次从外部内存中获取少量，然后快速进行比较，这不是很好吗？

这可以通过数据库实现。这个想法是创建一个“哈希”函数。具有相同散列值的所有内容都将存储在 words 表中。然后将其提取到内存中进行搜索。

一旦获得具有相同散列的单词集，您就可以自己进行搜索，或者这可能有效:

select word
from (select word
      from words
      where hash(word) = hash(YOURWORD)
     ) t
where t.word = YOURWORD

重点是“欺骗”SQL 编译器先使用散列索引，然后再进行比较。

一个非常简单的哈希函数可能是前五个字母。因此，像“ spy ”这样的词只有一个条目。但是，像“multi”这样的词会有很多。您的单词表将有两列，“单词”和“哈希”。然后您将在 hash 上有一个索引。 . .为了获得最佳性能，请按哈希对单词表进行排序。将单词列表排序后，所有匹配的单词很有可能会出现在一页或两页上，从而最大限度地减少外部 I/O。

不幸的是，SQLite 没有任何内置的哈希函数。您可以自己构建一个，方法是将字符串中的字符值成对相加。