纵横字谜搜索的最佳数据结构
我有一个解决纵横填字游戏的大型数据库，由一个单词和一个描述组成。我的应用程序允许搜索特定长度的单词和特定位置上的字符(这是很难做到的……检查所有单词并检查每个单词)。加上按描述进行搜索(如有必要)
例如，查找单词__A__B (6个字母的单词，第三个字符A和最后一个B)
我想以这样的方式索引单词，以便搜索将真的很快。我的第一个想法是使用平衡的树结构，还有其他建议吗？
回答 5
Stack Overflow用户
发布于 2010-02-19 22:30:36
好吧，我将提出一些奇怪的东西，但我来自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参数，以最小化散列的大小，从而使搜索更好。此外，集合按长度排序，以便更好地计算交集:)
如果您愿意，可以使用其他解决方案对其进行测试:)
Stack Overflow用户
发布于 2010-02-19 00:17:49
这个问题：Good algorithm and data structure for looking up words with missing letters?一开始和你所问的一模一样，但后来它被编辑成了一些不同的、更容易的东西。不过，你仍然可以在那里找到一些想法。
简而言之，每个人都建议将整个字典加载到内存中，并根据单词的长度将单词分组。从那里，你可以走很多不同的方向。你愿意使用的内存越多，你的速度就会越快。
一个很好的建议是保留一个哈希表，其中包含给定长度的单词列表，这些单词在给定位置具有给定的字母。您可以这样构建它(在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结尾的六个字母的单词，其中只有圣甲虫匹配。
Stack Overflow用户
发布于 2010-02-18 21:49:41
由于您使用的是数据库，因此需要创建一个后缀表。
例如：
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'的所有单词。
如果你想节省空间，并牺牲一点速度，你可以使用suffix array。
您可以将所有单词存储在行(数组)中，并在它们之间使用分隔符，即$，并创建一个后缀数组，该数组将包含指向字符的指针。现在，给定一个char c，您可以相当快地找到包含它的所有单词实例。不过，您必须检查它是否处于正确的位置。
(通过检查它离$有多远)
使用上面的技术，搜索速度可能会比搜索原始程序中的所有单词都要快( x10 )。
更新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 = 2https://stackoverflow.com/questions/2288901
复制相似问题
腾讯云开发者
