填字游戏搜索的最佳数据结构

Question

我有一个用于解决填字游戏的大型数据库，其中包含单词和描述。 我的应用程序允许搜索特定长度的单词和特定位置上的字符（这是通过困难的方式完成的......遍历所有单词并检查每个单词）。 再加上按描述的搜索（如有必要）

例如查找单词_ _ A _ _ B（6个字母的单词，第三个字符A和最后一个B）

我想以这样的方式对单词进行索引，以便搜索速度非常快。 我的第一个想法是使用平衡树结构，还有其他建议吗？

Answer 1

好吧，我要提出一些奇怪的建议，但来自 C++ 的我已经使用 Boost 很长时间了，我来看看 MultiIndex库。

该库的想法是创建一个集合，但有多种不同的方式来查询它。事实上，它可以对数据库进行建模。

因此，让我们将单词放入表中，并将必要的索引放在适当的位置：

word                     |length|c0|c1|c2| ... |c26|
-------------------------|------|--|--|--| ... |---|
Singapour                |9     |S |i |n | ... |0  |

现在查询将如下所示：

Select word From table Where length=9 And c2='n' And c8='u';

很简单不是吗？

为了获得最大效率，表应按长度分区，并且索引（每个 cX 列一个）应位于分区的本地。

对于内存中的解决方案，每个长度有一个容器，包含与长度一样多的索引，每个索引都是一个指向排序列表的哈希表（更容易合并）

这是一个Python描述：

class Dictionary:
  def __init__(self, length):
    self.length = length
    self.words = set([])
    self.indexes = collections.defaultdict(set)

  def add(self, word):
    if len(word) != self.length:
      raise RuntimeException(word + ' is not ' + `self.length` + ' characters long')

    if word in self.words:
      raise RuntimeException(word + ' is already in the dictionary')

    self.words.add(word)

    for i in range(0,length):
      self.indexes[(i,word[i])].add(word)

  def search(self, list):
    """list: list of tuples (position,character)
    """
    def compare(lhs,rhs): return cmp(len(lhs),len(rhs))

    sets = [self.indexes[elem] for elem in list]
    sets.sort(compare)
    return reduce(intersection, sets)

我自愿提供了<代码>length 参数，以最小化哈希的大小，从而使搜索更好。此外，这些集合按长度排序，以便更好地计算交集:)

如果您愿意，请继续针对其他解决方案进行测试:)

Answer 2

这个问题：好的算法和数据结构用于查找缺少字母的单词？ 一开始与您所要求的完全一样，但后来被编辑为相当不同且更简单的内容。不过，您仍然可以在那里找到一些想法。

简而言之，大家建议将整个词典加载到内存中，并根据单词的长度将单词分组。从那里，您可以走向许多不同的方向。您愿意使用的内存越多，速度就越快。

一个很好的建议是保留一个给定长度的单词列表的哈希表，这些单词在给定位置具有给定字母。你可以像这样构建它（在 Python 中）：

# Build a whole lot of sorted word lists
wordlists = collections.defaultdict(list)
for word in sorted(all_words):
    for position, letter in enumerate(word):
        wordlists[len(word), position, letter].append(word)

现在，如果你需要一个以 B 结尾的 6 个字母的单词，你可以只要求 wordlists[6, 5, 'B'] 并且你已经得到了完整的清单。当您知道多个字母时（如..A..B），您可以选择最短的列表并根据所需的模式测试每个单词。我的电脑词典只有21个以B结尾的六字母单词，其中只有SCARAB匹配。

Answer 3

由于您使用数据库，因此创建一个后缀表。
例如：

  Suffix          |   WordID   | SN
  ----------------+------------+----   
  StackOverflow           10      1
  tackOverflow            10      2
  ackOverflow             10      3
  ckOverflow              10      4
  kOverflow               10      5
  ...

使用该表，可以轻松获取在特定位置包含特定字符的所有单词，
像这样：

SELECT WordID FROM suffixes
WHERE suffix >= 't' AND suffix < 'u' AND SN = 2

获取在位置2处包含't'的所有单词。

更新：如果您想节省空间并牺牲一点速度，您可以使用 后缀数组。

您可以将所有单词存储在一行（数组）中，其中之间有分隔符，即 $，并创建
一个后缀数组，其中包含指向字符的指针。现在，给定一个 char c ，您可以相当快地找到包含它的单词的所有实例。不过，您必须检查它是否处于正确的位置。
（通过检查它与 $ 的距离）

可能使用上述技术，搜索速度将比搜索原始程序中的所有单词快 10 倍。

更新 2： 我在我的一个实用程序中使用了数据库方法，例如，我需要查找“ne”等后缀，但我忘记针对此特定问题调整（优化）它。

您可以只存储单个字符作为后缀：

  Suffix   |   WordID   | SN
  ---------+------------+----   
  S                10      1
  t                10      2
  a                10      3
  c                10      4
  k                10      5
  ...

这可以节省大量空间。现在，查询变成

SELECT WordID FROM suffixes
WHERE suffix = 't' AND SN = 2

Answer 4

您可以使用 后缀树 或 Trie。

Answer 5

您可以将信息存储在某种类型的字典树中（可能是三元搜索树）。 这篇论文，作者：Sedgewick 和 Bentley。你当然希望对不同长度的单词进行不同的尝试。论文称，部分搜索算法需要 O(n^((ks)/k)) 的时间来在 n k 长度单词的 trie 中指定 s 个字母。