拼字游戏单词查找器与通配符
我遇到了一个问题，似乎有些人遇到类似的问题，但我找不到适合我的解决方案。
我目前正在使用C＃，MySQL，HTML5和Javascript构建移动Web应用程序。 该应用程序将用于帮助用户在玩拼字游戏等游戏时找到可玩的单词。
我遇到的问题：如何从包含用户字母输入字典的MySQL数据库中获取正确的单词？
更多细节： – 用户可以输入任意数量的字母，也可以使用通配符（代表任何字母）。 – 如果用户输入“TEST”，则结果不能包含超过1 E和S的单词以及超过2 T的单词，其中包含“TESTER”的结果将是错误的。 – 结果不能包含字母数多于输入的字数。
更新：似乎Trie是Eric Lippert 在此提出的问题的解决方案。
问题是我是C＃和MySQL的初学者，所以这里有一些后续问题：
- 如何从MySQL字典创建Trie？ （400k +字）
- 如何存储Trie以便快速和将来访问？
- 如何使用C＃访问Trie并从中提取单词？
非常感谢你的帮助！
如何从包含用户字母输入字典的MySQL数据库中获取正确的单词？
你没有。 关系数据库表不是一个合适的数据结构，可以根据需要有效地解决这个问题。
你做的是你从字典中构建一个trie数据结构（或者，如果你真的是buff，你构建一个dawg – 一个有向无环的字图 – 这是一种压缩的trie。）
一旦你有了trie / dawg，就可以非常便宜地在字典中测试给定机架上的每个单词，因为你可以“删除”机架无法匹配的字典的整个巨大分支。
我们来看一个小例子。 假设您有字典“OP，OPS，OPT，OPTS，POT，POTS，SOP，SOPS，STOP，STOPS”从中构建此trie :(带有$的节点是标记为“word can end here”的节点） 。
^root^ / | \ OPS | | / \ P$ OOT / \ | | | T$ S$ T$ P$ O | | | | S$ S$ S$ P$ | S$ 你有机架“OPS” – 你做什么？
首先你说“我可以走下O分支吗？” 是的你可以。 所以现在问题是将“PS”与O分支相匹配。 你可以沿着P支柱下去吗？ 是。 它有一个单词结束标记吗？ 是的，所以OP是一个匹配。 现在问题是将“S”与OP分支匹配。 你可以去T分店吗？ 不，你可以去S分店吗？ 是。 现在你有了空架子，你必须将它与OPS分支相匹配。 它有一个单词结束标记吗？ 是! 所以OPS也匹配。 现在回溯到root。
你可以去P分店吗？ 是。 现在的问题是将OS与P分支相匹配。 沿着PO分支向下并匹配S – 失败。 回溯到根。
再一次，你看到这是怎么回事。 最后，我们走下SOP分支，找到SOP的结尾，所以“SOP”匹配这个机架。 我们不去ST分支，因为我们没有T.
我们在字典中尝试了所有可能的单词，发现OP，OPS和SOP都匹配。 但我们从来没有调查OPTS，POTS，STOP或STOPS，因为我们没有T.
您看到这种数据结构如何使其高效？ 一旦确定您没有机架上的字母来开始单词，您就不必调查以该开头开头的任何字典单词。 如果你有PO而没有T，你不必调查POTSHERD或POTATO或POTASH或POTLATCH或POTABLE; 所有那些昂贵且毫无结果的搜索都会很快消失。
调整系统以处理“野外”瓷砖非常简单; 如果你有OPS ?,那么只需在OPSA，OPSB，OPSC上运行搜索算法26次……它应该足够快，这样做26次便宜（如果你有两个空白就做26 x 26次）。 ）
这是专业Scrabble AI程序使用的基本算法，当然它们还必须处理诸如电路板位置，机架管理等问题，这使得算法有些复杂化。 这个简单的算法版本足够快，可以在机架上生成所有可能的单词。
不要忘记，如果字典没有随时间变化，你只需要计算一次 trie / dawg。 从字典中构建trie可能非常耗时，因此您可能希望这样做一次 ，然后找出一些方法将磁带存储在磁盘上，其forms可以从磁盘快速重建。
您可以通过构建一个DAWG来优化内存使用。 注意有很多重复，因为在英语中，很多单词结尾相同，就像许多单词开头一样。 trie在开始时很好地共享节点，但在最后分享它们是一项糟糕的工作。 你可以注意到例如“没有孩子的S $”模式是非常常见的，并将trie转换为：
^root^ / | \ OPS | | / \ P$ OOT / \ | | | T$ | T$ P$ O | \ | | | \ \| / P$ \ |/ | \ | / \ | / \ | / \| / |/ | S$
保存一堆节点。 然后您可能会注意到两个单词现在以OP $ -S $结尾，两个单词以T $ -S $结尾，因此您可以将其进一步压缩为：
^root^ / | \ OPS | | / \ P$ O \ T / \| \ | | | \| | | O | T$ | \ | P$ \ | / \| / | / |/ S$
现在我们为这本词典提供了最小的DAWG。
进一步阅读：
http://dl.acm.org/citation.cfm?id=42420
以下是我将如何解决问题（假设您当然可以控制数据库，并且可以修改表/添加表，甚至可以控制数据库的原始负载）。
我的解决方案将使用2个表 – >一个表只是您字典中每个可能的字母组合的列表，其中组件字母按字母顺序排序。 （IE TEST将是ESTT，TESTER将是ERSTT，DAD将是ADD）。
第二个表将包含每个单词和对表一的键的引用。
表一 – LetterInWord
Index Letters 1 ESTT 2 ESTTER 3 EST 4 ADD 5 APST
在表1中，您按字母顺序插入单词 – test成为estt
表二 – 单词
Index LetterInWordIndex Word 1 1 TEST 2 2 TESTER 3 3 SET 4 4 ADD 5 4 DAD 6 5 SPAT 7 5 PAST
在表2中，您插入带有适当的单词和索引引用的单词。
这将是一对多的关系 – > LetterInWord表中的一个条目可以在Words表中有多个条目
非外卡查询：说我的输入字母是SETT按字母顺序排序。
然后在查找中，从LetterInWord中选择所有“Letters”，其中Letters = value并加入表Words – 您在一个查询中的输出是仅包含这些字母的所有单词的列表
现在对于外卡：说我的输入字母是EST *记住长度 – 4去掉通配符 – 你得到EST（确保按字母顺序排序）现在查找所有包含EST和字母长度<= 4的情况单词表
这将返回TEST，REST，SET等
我不确定这是否是最有效的方法，但它确实有效。 我过去曾用它来从字典中进行单词查找，它具有合理的性能和最小的复杂性。
如果你拥有的只是字典，那将很难做到。 如果您能够制作新表或新列，我会：
创建一个包含该列的列的表，以及26列（每个字母一个）运行存储的proc / backend进程，计算单词中每个字母的出现次数，并将它们放入相应的列中。
然后（忽略通配符）你可以做到
从字典中选择单词，其中tcount <= 2且ecount <= 1且scount <= 1
对于你可以做的通配符和长度<= number_of_letters
实际上总是使用length子句，因为您可以对其进行索引以提高性能。
在查询过程中，其他任何事情都会exception缓慢