3

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

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

现在我改用 sqlite，所以我不必将整个 dict 保存在内存中，并减少加载时间。

我有两个挑战：

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

  2. 我如何为一组字母找到所有可能的单词...当我将 wordDictionary 放在一个数组中时，我可以遍历整个内容并验证每个单词。查询每一行（约 700,000 行）并使用 sqlite 进行验证会非常慢。

4

3 回答 3

2

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

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

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

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

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

关键是先“欺骗” SQL 编译器使用哈希索引，然后再进行比较。

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

不幸的是，SQLite 没有任何内置的散列函数。您可以通过将字符串中的字符值成对相加来自己构建一个。

于 2013-01-15T19:23:45.093 回答
1

我已经在回答你之前的问题了。我不是数据库专家，我对字母算法如何工作有一些想法。

  1. 您将只使用数据库来加快搜索速度，即减少结果数量，然后您将检查内存中的数据库结果。

  2. 对于数据库中的每个单词，您还将保存一个哈希。该哈希将是一个数字或一个字符串。

  3. 如果您有一组字母，例如 {a, b, b, c, x, t, u, v}，您将计算一组可以从字母创建的散列，并且对于每个可能的散列，您将询问所有结果的数据库。

  4. 测试结果是否仅包含您的集合中的字母（我们已经在您的上一个问题中讨论过）。

一些可能的哈希函数：

  1. 没有重复的有序元音，例如 hash(transformers) = "aeo"。从上面的集合中，您将获得可能的哈希“”、“a”、“u”、“au”、“ua”。请注意，很少有没有元音的单词，所以 "" 请求不应该造成问题。

  2. 带有重复的有序元音，例如 hash(request) = "ee"。从集合 {w, h, y, a, a, x, e} 你会得到散列 "", "a", "e", "y", "aa", "ae", "ay", "ea ”、“ey”、“ya”、“ye”、“aae”、“aay”。一般来说 - 更多的请求，更少的结果。

  3. 没有重复的有序字母，例如 hash(transfomers) = "aefmnorst"。如果N是字母的数量，我们忽略长度<2的单词，你最多需要（如果没有字母重复）(N 3) + (N 4) + (N 5) + .... + (N N)，如果N是20，那就是几千个或请求......让我们忽略这个想法。

  4. ASCII 字母的位掩码（忽略任何非 ASCII 字母）。位置 0 的位表示单词包含“a”，位置 1 包含“b”等。如果我们为字母创建相同的位掩码，我们可以选择单词，例如(wordMask & ~lettersMask) == 0

于 2013-01-15T20:08:31.557 回答
0

对于第二个问题，每个单词添加一个按字母顺序排列的第二列。然后对可用的图块进行排序并搜索该列。这将为您提供用于搜索的所有图块的所有可能单词。

不幸的是，它不适用于某些瓷砖。为此，您必须一次消除一个图块并重新进行搜索。

于 2013-01-17T01:56:34.210 回答