问通配符拼字机

EN

如何从包含字典的MySQL数据库中从用户字母输入中获得正确的单词？

没有。关系数据库表并不是解决这个问题所需要的合适的数据结构。

相反，您要做的是从字典中构建一个数据结构(或者，如果您真的很喜欢的话，您可以构建一个 --一个有向无圈字图--这是一种压缩的trie)。

一旦您有一个trie/dawg，它变得非常便宜的测试，在字典中的每一个词在给定的货架，因为你可以“剪出”整个大分支的字典，架不可能匹配。

让我们看一个小例子。假设您有字典OP、OPS、OPT、OPTS、POT、POT、SOP、SOPS、STOP、STOP“，”您可以构建这个trie：(带有$的节点是标记为"word可以在这里结束“的节点。

           ^root^
           /  |  \
         O    P    S
         |    |   / \
         P$   O  O   T   
        / \   |  |   |
       T$  S$ T$ P$  O
       |      |  |   |
       S$     S$ S$  P$
                     |
                     S$

你有机架“老年退休金”--你是做什么的？

首先你说：“我能从O支部下来吗？”可以，停那儿吧。因此，现在的问题是将"PS“与O分支相匹配。你能沿着P支行走吗？是。它有字尾标记吗？是的，所以OP是匹配的。现在的问题是将"S“与OP分支匹配。你能沿着T支行走吗？不是的。你能沿着S支行走吗？是。现在，您有了空的机架，您必须将它与老年退休金分支相匹配。它有字尾标记吗？是!所以老年退休金也匹配。现在追溯到根部。

你能沿着P支行走吗？是。现在的问题是如何将OS与P分支相匹配。沿着PO分支，匹配S --失败了。回溯到根。

再说一遍，你看这是怎么回事。最后，我们沿着SOP分支，在SOP上找到了一个单词的结尾，所以"SOP“与这个支架相匹配。我们不去ST支行，因为我们没有T。

我们试过字典中的每一个可能的单词，发现OP、OPS和SOP都匹配。但我们从来不需要调查选择，盆栽，停止或停止，因为我们没有一个T。

你知道这种数据结构是如何使它非常高效的吗？一旦你确定你没有在架子上的字母来做一个单词的开头，你就不需要去调查任何从这个开始开始的字典单词。如果你有PO，但没有T，你就不必去调查陶片、土豆、钾肥、土豆或便宜货；所有那些昂贵而毫无结果的搜索都会很快消失。

调整系统以处理“野生”块是非常简单的；如果您有OPS?，那么只需运行26次搜索算法，在OPSA，OPSB，OPSC上.它应该足够快，这样做26次是便宜的(或26次，如果你有两个空白)。

这是专业拼字AI程序使用的基本算法，当然，它们也必须处理诸如板子位置、机架管理等问题，这使算法变得有些复杂。这个简单版本的算法将足够快，以生成所有可能的字架上。

当然，如果字典没有随时间变化，你只需要计算trie/dawg一次。从字典中构建trie可能很费时，所以您可能需要这样做一次，然后想出某种方法将trie存储在磁盘上，以便能够快速地从磁盘重新构建它。

您可以通过从trie中构建一个DAWG来优化内存使用。注意很多重复，因为在英语中，很多单词的结尾都是一样的，就像很多单词的开头一样。trie在一开始就很好地共享节点，但在最后共享节点却是一项糟糕的工作。例如，您可以注意到"S$ with子“模式非常常见，并将trie转换为：

           ^root^
          / |  \
        O   P    S
        |   |   / \
        P$  O  O   T   
       /  \ |  |   |
      T$  | T$ P$  O
      |    \ | |   |
       \    \| /   P$
        \    |/    |
         \   |    /
          \  |   /  
           \ |  /
            \| /  
             |/
             |       
             S$

节省了一整堆节点。然后您可能会注意到，两个单词现在以O$-S$结尾，两个单词以T$-S$结尾，所以您可以进一步压缩它：

           ^root^
           / | \
          O  P  S
          |  | / \
          P$ O \  T   
         /  \|  \ |
         |   |   \|
         |   |    O
         |   T$   |
          \  |    P$
           \ |   /
            \|  /  
             | /
             |/   
             S$

现在我们有了这本字典的最小道格。

进一步读：

http://dl.acm.org/citation.cfm?id=42420

http://archive.msdn.microsoft.com/dawg1

http://www.gtoal.com/wordgames/scrabble.html

下面是我如何解决这个问题的方法(当然，假设您控制了DB，并且可以修改表/添加表，甚至可以控制DB的原始负载)。

我的解决方案是使用两个表，->，一个表将是字典中每一个可能的字母组合的列表，并按字母顺序排列组件字母。(即测试将是ESTT，测试人员将是ERSTT，DAD将添加)。

第二个表将包含每个单词，并引用表1的键。

表一- LetterInWord

Index Letters
1     ESTT
2     ESTTER
3     EST
4     ADD
5     APST

在表一中，您按字母顺序插入单词- 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中插入带有适当单词和索引引用的单词。

这将是一个一对多的关系->表中的一个条目可能在Word表中有多个条目

非通配符查找:假设我的输入字母设置为字母排序。

然后在查找中，从LetterInWord中选择所有的“字母”，其中Letters = value并连接表单词--在一个查询中，您的输出是一个只包含这些字母的所有单词的列表。

现在对于通配符:假设我的输入字母是EST*请记住长度-4划出通配符-您得到了EST (确保按字母顺序排序)现在查找所有字母包含EST和字母长度<= 4的情况，这些字母连接在Word表上。

返回测试、休息、设置等

我不确定这是否是最有效的方法，但它有效。我过去曾使用它从字典中查找单词，它具有合理的性能和最小的复杂性。

如果你只有字典的话，这将是非常困难的。如果您有能力创建一个新表或新列，我会：

创建一个包含单词列的表，再加上26列(每个字母一列)，运行存储的proc/后端进程，计算单词中每个字母的出现情况，并将它们放入适当的列中。

然后(忽略通配符)你可以做到

从字典中选择单词，其中tcount <=2和ecount <=1和scount <=1

对于通配符，您可以这样做和长度<= number_of_letters

实际上，始终使用length子句，因为这样您就能够对其进行索引以提高性能。

在查询过程中，其他任何事情都将异常缓慢。