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

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论点,以最小化哈希的大小,从而使搜索更好.此外,集合按长度排序,以便交集的计算更好:)

如果你愿意,请继续测试它与其他解决方案:)