我遇到了一个问题,似乎有些问题出现在我之前,但是我找不到适合我的解决方案.
我目前正在使用C#,MySQL,HTML5和Javascript构建移动Web应用程序.该应用程序将用于帮助用户在玩像Scrabble这样的游戏时找到可玩的单词.
我遇到的问题:如何从包含用户字母输入字典的MySQL数据库中获取正确的单词？
更多细节: - 用户可以输入任意数量的字母,也可以使用通配符(代表任何字母). - 如果用户输入"TEST",则结果不能包含超过1 E和S的单词以及超过2 T的单词,其中包含"TESTER"的结果将是错误的. - 结果不能包含字母数多于输入的字数.
更新:似乎Trie是Eric Lippert 在此提出的问题的解决方案.
问题是我是C#和MySQL的初学者,所以这里有一些后续问题:
非常感谢你的帮助!
Eri*_*ert 23
如何从包含用户字母输入字典的MySQL数据库中获取正确的单词？
你没有.关系数据库表不是一个合适的数据结构,可以根据需要有效地解决这个问题.
你做的是你从字典中构建一个trie数据结构(或者,如果你真的是buff,你构建一个dawg - 一个有向的非循环字图 - 这是一种压缩的trie.)
一旦你有一个trie/dawg,在一个给定的机架上测试字典中的每个单词变得非常便宜,因为你可以"删除"机架无法匹配的字典的整个巨大分支.
我们来看一个小例子.假设您有字典"OP,OPS,OPT,OPTS,POT,POTS,SOP,SOPS,STOP,STOPS"从中构建此trie :(带有$的节点是标记为"word can end here"的节点) .
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ S$ T$ P$ O
| | | |
S$ S$ S$ P$
|
S$
你有机架"OPS" - 你做什么？
首先你说"我可以沿着O分支走吗？" 是的你可以.所以现在问题是将"PS"与O分支相匹配.你可以沿着P支柱下去吗？是.它有一个单词结束标记吗？是的,所以OP是一个匹配.现在问题是将"S"与OP分支匹配.你可以去T分店吗？不,你可以去S分店吗？是.现在你有了空架子,你必须将它与OPS分支相匹配.它有一个单词结束标记吗？是! 因此OPS也匹配.现在回溯到根.
你可以去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可能非常耗时,因此您可能希望这样做一次,然后找出一些方法将磁带以一种可以从磁盘快速重建的形式存储在磁盘上.
您可以通过在trie中构建DAWG来优化内存使用.注意有很多重复,因为在英语中,很多单词结尾相同,就像许多单词开头一样.trie在开始时很好地共享节点,但在最后分享它们是一项糟糕的工作.你可以注意到例如"没有孩子的S $"模式是非常常见的,并将trie转换为:
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ | T$ P$ O
| \ | | |
\ \| / P$
\ |/ |
\ | /
\ | /
\ | /
\| /
|/
|
S$
保存一堆节点.然后您可能会注意到两个单词现在以OP $ -S $结尾,两个单词以T $ -S $结尾,因此您可以将其进一步压缩为:
^root^
/ | \
O P S
| | / \
P$ O \ T
/ \| \ |
| | \|
| | O
| T$ |
\ | P$
\ | /
\| /
| /
|/
S$
现在我们为这本词典提供了最小的DAWG.
进一步阅读:
http://dl.acm.org/citation.cfm?id=42420
http://archive.msdn.microsoft.com/dawg1
http://www.gtoal.com/wordgames/scrabble.html
| 归档时间： |
|
| 查看次数： |
3900 次 |
| 最近记录： |