我有一个用于解决填字游戏的大型数据库，由一个单词和一个描述组成。我的应用程序允许搜索特定长度的单词和特定位置的字符（这是很难做到的……遍历所有单词并检查每个单词）。加上按描述搜索（如有必要）
例如查找单词_ _ A _ _ B（6个字母单词，第三个字符A和最后一个B）
我想以搜索速度非常快的方式对单词进行索引。我的第一个想法是使用平衡的树结构，还有其他建议吗？
问问题
5443 次
5 回答
9
好的，我要提出一些奇怪的东西，但是来自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参数，以最小化散列的大小，从而使搜索更好。此外，集合按长度排序，以便更好地计算交集:)
如果您愿意，请继续使用其他解决方案对其进行测试:)
于 2010-02-19T14:30:35.727 回答
4
这个问题：用于查找缺少字母的单词的良好算法和数据结构？开始时与您所要求的完全一样，但随后将其编辑为完全不同且更容易的内容。不过，您仍然可以在那里找到一些想法。
简而言之，大家建议将整个字典加载到内存中，并根据单词的长度将单词分组。从那里，你可以去许多不同的方向。您愿意使用的内存越多，您可以走得越快。
一个不错的建议是保留给定长度的单词列表的哈希表，这些单词在给定位置具有给定字母。您可以像这样构建它（在 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 匹配。
于 2010-02-18T16:17:48.650 回答
2
由于您使用数据库，因此请创建一个 Suffixes 表。
例如 ：
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
获取所有包含't'at 的单词2。
更新：如果你想节省空间，牺牲一点速度，你可以使用后缀数组。
您可以将所有单词存储在一行（数组）中，其中包含一个分隔符，即$, 并创建一个后缀数组，该数组将具有指向字符的指针。现在，给定一个字符c，您可以相当快地找到包含它的所有单词实例。不过，您必须检查它是否处于正确的位置。（通过检查距离s
有多远）$
可能使用上述技术，搜索将比搜索原始程序中的所有单词快 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
于 2010-02-18T13:49:41.237 回答
1
您可以使用Suffix Tree或 Trie。
于 2010-02-18T13:54:21.203 回答
1
您可以将您的信息存储在某种类型的树中（可能是三元搜索树）。Sedgewick 和 Bentley在本文的第 6 节中描述了使用 trie 进行部分搜索的算法。您当然希望对不同长度的单词进行不同的尝试。该论文说，部分搜索算法需要 O(n^((ks)/k)) 的时间，以便在 n 个 k 长度单词的 trie 中指定 s 个字母。
于 2010-02-19T14:55:00.653 回答