纵横字谜搜索的最佳数据结构
纵横字谜搜索的最佳数据结构
提问于 2010-02-18 21:34:31
我有一个解决纵横填字游戏的大型数据库，由一个单词和一个描述组成。我的应用程序允许搜索特定长度的单词和特定位置上的字符(这是很难做到的……检查所有单词并检查每个单词)。加上按描述进行搜索(如有必要)
例如，查找单词__A__B (6个字母的单词，第三个字符A和最后一个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 = 2页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2288901
复制相关文章
相似问题
腾讯云开发者
