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

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 参数，以最小化散列的大小，从而使搜索更好。此外，集合按长度排序，以便交集的计算更好:)

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