草庐IT

c# - 带通配符的拼字游戏词查找器

coder 2023-10-03 原文

我遇到了一个问题,在我之前似乎有一些类似的问题,但我一直无法找到适合我的解决方案。

我目前正在使用 C#、MySQL、HTML5 和 Javascript 构建一个移动 Web 应用程序。该应用程序将用于帮助用户在玩拼字游戏等游戏时找到可能的单词。

我遇到的问题:
如何从包含用户字母输入的字典的 MySQL 数据库中获取正确的单词?

更多细节:
- 用户可以输入任意数量的字母,也可以使用通配符(代表任意字母)。
- 如果用户输入“TEST”,结果不能包含超过1个E和S的单词和超过2个T的单词,其中包含“TESTER”的结果将是不好的。
- 结果不能包含比输入更多字母的单词。

更新:按照 Eric Lippert here 的建议,似乎 Trie 是我问题的解决方案.
问题是我是 C# 和 MySQL 的初学者,所以这里有一些后续问题:

  • 如何从我的 MySQL 字典创建一个 Trie? (400k+ 字)
  • 如何存储 Trie 以便将来快速访问?
  • 如何使用 C# 访问 Trie 并从中提取单词?

  • 非常感谢你的帮助!

    最佳答案

    How do I get the right words from a MySQL database containing a dictionary from user letter input?



    你没有。关系数据库表不是像您需要的那样高效地解决此问题的合适数据结构。

    相反,您要做的是构建一个 trie 字典中的数据结构(或者,如果你真的很喜欢,你可以构建一个 dawg ——一个有向无环词图——这是一种压缩的特里树。)

    一旦你有了一个 trie/dawg,在给定的机架上测试字典中的每个词就变得非常便宜,因为你可以“删减”机架不可能匹配的整个字典的巨大分支。

    让我们看一个小例子。假设您有字典“OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS”,您从中构建了此树:(带有 $ 的节点是标记为“单词可以在此处结束”的节点) .
               ^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 在共享节点方面做得很好,但在最后共享节点方面做得很糟糕。例如,您可以注意到“没有 child 的 S$”模式非常常见,并将特里树变成:
               ^root^
              / |  \
            O   P    S
            |   |   / \
            P$  O  O   T   
           /  \ |  |   |
          T$  | T$ P$  O
          |    \ | |   |
           \    \| /   P$
            \    |/    |
             \   |    /
              \  |   /  
               \ |  /
                \| /  
                 |/
                 |       
                 S$
    

    保存一大堆节点。然后您可能会注意到现在有两个词以 O-P$-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

    关于c# - 带通配符的拼字游戏词查找器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7418910/

    有关c# - 带通配符的拼字游戏词查找器的更多相关文章

    1. ruby - 当使用::指定模块时,为什么 Ruby 不在更高范围内查找类? - 2

      我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后,我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是,如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误,还是仅仅是Ruby解析变量名的方式的逻辑结果? 最佳答案 Isthisabug,or

    2. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

      我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如,CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

    3. c# - 如何在 ruby​​ 中调用 C# dll? - 2

      如何在ruby​​中调用C#dll? 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器,如果它还没有,则使用Ruby的WIN32OLE库来调用它;看看RubyCLR,其中一位作者是JohnLam,他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了,可能不支持.Net2.0以上的版本);正如其他地方已经提到的,看看使用IronRuby,如果这是您的技术选择。有一个主题是here.请注意,最后一篇文章实际上来自JohnLam(看起来像是2009年3月),他似乎很自在地断言RubyCL

    4. C# 到 Ruby sha1 base64 编码 - 2

      我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时,我得到了相同sha

    5. 基于C#实现简易绘图工具【100010177】 - 2

      C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.

    6. ruby-on-rails - 在 Rails 中更高效地查找或创建多条记录 - 2

      我有一个应用需要发送用户事件邀请。当用户邀请friend(用户)参加事件时,如果尚不存在将用户连接到该事件的新记录,则会创建该记录。我的模型由用户、事件和events_user组成。classEventdefinvite(user_id,*args)user_id.eachdo|u|e=EventsUser.find_or_create_by_event_id_and_user_id(self.id,u)e.save!endendend用法Event.first.invite([1,2,3])我不认为以上是完成我的任务的最有效方法。我设想了一种方法,例如Model.find_or_cr

    7. ruby - 查找重叠的正则表达式匹配项 - 2

      我想找到给定字符串中的所有匹配项,包括重叠匹配项。我怎样才能实现它?#Example"a-b-c-d".???(/\w-\w/)#=>["a-b","b-c","c-d"]expected#Solutionwithoutoverlappedresults"a-b-c-d".scan(/\w-\w/)#=>["a-b","c-d"],but"b-c"ismissing 最佳答案 在积极的前瞻中使用捕获:"a-b-c-d".scan(/(?=(\w-\w))/).flatten#=>["a-b","b-c","c-d"]参见Rubyde

    8. ruby - 在 Ruby 中查找多个正则表达式匹配的模式和位置 - 2

      这应该是一个简单的问题,但我找不到任何相关信息。给定一个Ruby中的正则表达式,对于每个匹配项,我需要检索匹配的模式$1、$2,但我还需要匹配位置。我知道=~运算符为我提供了第一个匹配项的位置,而string.scan(/regex/)为我提供了所有匹配模式。如果可能,我需要在同一步骤中获得两个结果。 最佳答案 MatchDatastring.scan(regex)do$1#Patternatfirstposition$2#Patternatsecondposition$~.offset(1)#Startingandendingpo

    9. arrays - Ruby 可枚举 - 查找最多 n 次匹配元素 - 2

      我有以下数组:arr=[1,3,2,5,2,4,2,2,4,4,2,2,4,2,1,5]我想要一个包含前三个奇数元素的数组。我知道我可以做到:arr.select(&:odd?).take(3)但我想避免遍历整个数组,而是在找到第三个匹配项后返回。我想出了以下解决方案,我相信它可以满足我的要求:my_arr.each_with_object([])do|el,memo|memo但是有没有更简单/惯用的方法来做到这一点? 最佳答案 使用lazyenumerator与Enumerable#lazy:arr.lazy.select(&:o

    10. c# - C# 中的 Flatten Ruby 方法 - 2

      我如何做Ruby方法"Flatten"RubyMethod在C#中。此方法将锯齿状数组展平为一维数组。例如:s=[1,2,3]#=>[1,2,3]t=[4,5,6,[7,8]]#=>[4,5,6,[7,8]]a=[s,t,9,10]#=>[[1,2,3],[4,5,6,[7,8]],9,10]a.flatten#=>[1,2,3,4,5,6,7,8,9,10 最佳答案 递归解决方案:IEnumerableFlatten(IEnumerablearray){foreach(variteminarray){if(itemisIEnume

    随机推荐